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