polly/lib/CodeGen/Utils.cpp

   1 //===--- Utils.cpp - Utility functions for the code generation --*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file contains utility functions for the code generation.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "polly/CodeGen/Utils.h"
  14 #include "polly/CodeGen/IRBuilder.h"
  15 #include "polly/ScopInfo.h"
  16 #include "llvm/Analysis/LoopInfo.h"
  17 #include "llvm/Analysis/RegionInfo.h"
  18 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  19
  20 using namespace llvm;
  21
  22 // Alternative to llvm::SplitCriticalEdge.
  23 //
  24 // Creates a new block which branches to Succ. The edge to split is redirected
  25 // to the new block.
  26 //
  27 // The issue with llvm::SplitCriticalEdge is that it does nothing if the edge is
  28 // not critical.
  29 // The issue with llvm::SplitEdge is that it does not always create the middle
  30 // block, but reuses Prev/Succ if it can. We always want a new middle block.
  31 static BasicBlock *splitEdge(BasicBlock *Prev, BasicBlock *Succ,
  32                              const char *Suffix, DominatorTree *DT,
  33                              LoopInfo *LI, RegionInfo *RI) {
  34   assert(Prev && Succ);
  35
  36   // Before:
  37   //   \    /     /   //
  38   //    Prev     /    //
  39   //     |  \___/     //
  40   //     |   ___      //
  41   //     |  /   \     //
  42   //    Succ     \    //
  43   //   /    \     \   //
  44
  45   // The algorithm to update DominatorTree and LoopInfo of
  46   // llvm::SplitCriticalEdge is more efficient than
  47   // llvm::SplitBlockPredecessors, which is more general. In the future we might
  48   // either modify llvm::SplitCriticalEdge to allow skipping the critical edge
  49   // check; or Copy&Pase it here.
  50   BasicBlock *MiddleBlock = SplitBlockPredecessors(
  51       Succ, ArrayRef<BasicBlock *>(Prev), Suffix, DT, LI);
  52
  53   if (RI) {
  54     Region *PrevRegion = RI->getRegionFor(Prev);
  55     Region *SuccRegion = RI->getRegionFor(Succ);
  56     if (PrevRegion->contains(MiddleBlock)) {
  57       RI->setRegionFor(MiddleBlock, PrevRegion);
  58     } else {
  59       RI->setRegionFor(MiddleBlock, SuccRegion);
  60     }
  61   }
  62
  63   // After:
  64   //   \    /     /   //
  65   //    Prev     /    //
  66   //     |  \___/     //
  67   //     |            //
  68   // MiddleBlock      //
  69   //     |   ___      //
  70   //     |  /   \     //
  71   //    Succ     \    //
  72   //   /    \     \   //
  73
  74   return MiddleBlock;
  75 }
  76
  77 std::pair<polly::BBPair, BranchInst *>
  78 polly::executeScopConditionally(Scop &S, Value *RTC, DominatorTree &DT,
  79                                 RegionInfo &RI, LoopInfo &LI) {
  80   Region &R = S.getRegion();
  81   PollyIRBuilder Builder(S.getEntry());
  82
  83   // Before:
  84   //
  85   //      \   /      //
  86   //    EnteringBB   //
  87   //   _____|_____   //
  88   //  /  EntryBB  \  //
  89   //  |  (region) |  //
  90   //  \_ExitingBB_/  //
  91   //        |        //
  92   //      ExitBB     //
  93   //      /    \     //
  94
  95   // Create a fork block.
  96   BasicBlock *EnteringBB = S.getEnteringBlock();
  97   BasicBlock *EntryBB = S.getEntry();
  98   assert(EnteringBB && "Must be a simple region");
  99   BasicBlock *SplitBlock =
 100       splitEdge(EnteringBB, EntryBB, ".split_new_and_old", &DT, &LI, &RI);
 101   SplitBlock->setName("polly.split_new_and_old");
 102
 103   // If EntryBB is the exit block of the region that includes Prev, exclude
 104   // SplitBlock from that region by making it itself the exit block. This is
 105   // trivially possible because there is just one edge to EnteringBB.
 106   // This is necessary because we will add an outgoing edge from SplitBlock,
 107   // which would violate the single exit block requirement of PrevRegion.
 108   Region *PrevRegion = RI.getRegionFor(EnteringBB);
 109   while (PrevRegion->getExit() == EntryBB) {
 110     PrevRegion->replaceExit(SplitBlock);
 111     PrevRegion = PrevRegion->getParent();
 112   }
 113   RI.setRegionFor(SplitBlock, PrevRegion);
 114
 115   // Create a join block
 116   BasicBlock *ExitingBB = S.getExitingBlock();
 117   BasicBlock *ExitBB = S.getExit();
 118   assert(ExitingBB && "Must be a simple region");
 119   BasicBlock *MergeBlock =
 120       splitEdge(ExitingBB, ExitBB, ".merge_new_and_old", &DT, &LI, &RI);
 121   MergeBlock->setName("polly.merge_new_and_old");
 122
 123   // Exclude the join block from the region.
 124   R.replaceExitRecursive(MergeBlock);
 125   RI.setRegionFor(MergeBlock, R.getParent());
 126
 127   //      \   /      //
 128   //    EnteringBB   //
 129   //        |        //
 130   //    SplitBlock   //
 131   //   _____|_____   //
 132   //  /  EntryBB  \  //
 133   //  |  (region) |  //
 134   //  \_ExitingBB_/  //
 135   //        |        //
 136   //    MergeBlock   //
 137   //        |        //
 138   //      ExitBB     //
 139   //      /    \     //
 140
 141   // Create the start and exiting block.
 142   Function *F = SplitBlock->getParent();
 143   BasicBlock *StartBlock =
 144       BasicBlock::Create(F->getContext(), "polly.start", F);
 145   BasicBlock *ExitingBlock =
 146       BasicBlock::Create(F->getContext(), "polly.exiting", F);
 147   SplitBlock->getTerminator()->eraseFromParent();
 148   Builder.SetInsertPoint(SplitBlock);
 149   BranchInst *CondBr = Builder.CreateCondBr(RTC, StartBlock, S.getEntry());
 150
 151   if (Loop *L = LI.getLoopFor(SplitBlock)) {
 152     L->addBasicBlockToLoop(StartBlock, LI);
 153     L->addBasicBlockToLoop(ExitingBlock, LI);
 154   }
 155   DT.addNewBlock(StartBlock, SplitBlock);
 156   DT.addNewBlock(ExitingBlock, StartBlock);
 157   RI.setRegionFor(StartBlock, RI.getRegionFor(SplitBlock));
 158   RI.setRegionFor(ExitingBlock, RI.getRegionFor(SplitBlock));
 159
 160   //      \   /                    //
 161   //    EnteringBB                 //
 162   //        |                      //
 163   //    SplitBlock---------\       //
 164   //   _____|_____         |       //
 165   //  /  EntryBB  \    StartBlock  //
 166   //  |  (region) |        |       //
 167   //  \_ExitingBB_/   ExitingBlock //
 168   //        |                      //
 169   //    MergeBlock                 //
 170   //        |                      //
 171   //      ExitBB                   //
 172   //      /    \                   //
 173
 174   // Connect start block to exiting block.
 175   Builder.SetInsertPoint(StartBlock);
 176   Builder.CreateBr(ExitingBlock);
 177   DT.changeImmediateDominator(ExitingBlock, StartBlock);
 178
 179   // Connect exiting block to join block.
 180   Builder.SetInsertPoint(ExitingBlock);
 181   Builder.CreateBr(MergeBlock);
 182   DT.changeImmediateDominator(MergeBlock, SplitBlock);
 183
 184   //      \   /                    //
 185   //    EnteringBB                 //
 186   //        |                      //
 187   //    SplitBlock---------\       //
 188   //   _____|_____         |       //
 189   //  /  EntryBB  \    StartBlock  //
 190   //  |  (region) |        |       //
 191   //  \_ExitingBB_/   ExitingBlock //
 192   //        |              |       //
 193   //    MergeBlock---------/       //
 194   //        |                      //
 195   //      ExitBB                   //
 196   //      /    \                   //
 197   //
 198
 199   // Split the edge between SplitBlock and EntryBB, to avoid a critical edge.
 200   splitEdge(SplitBlock, EntryBB, ".pre_entry_bb", &DT, &LI, &RI);
 201
 202   //      \   /                    //
 203   //    EnteringBB                 //
 204   //        |                      //
 205   //    SplitBlock---------\       //
 206   //        |              |       //
 207   //    PreEntryBB         |       //
 208   //   _____|_____         |       //
 209   //  /  EntryBB  \    StartBlock  //
 210   //  |  (region) |        |       //
 211   //  \_ExitingBB_/   ExitingBlock //
 212   //        |              |       //
 213   //    MergeBlock---------/       //
 214   //        |                      //
 215   //      ExitBB                   //
 216   //      /    \                   //
 217
 218   return std::make_pair(std::make_pair(StartBlock, ExitingBlock), CondBr);
 219 }