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 BasicBlock *polly::executeScopConditionally(Scop &S, Pass *P, Value *RTC) { 80 Region &R = S.getRegion(); 81 PollyIRBuilder Builder(S.getEntry()); 82 DominatorTree &DT = P->getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 83 RegionInfo &RI = P->getAnalysis<RegionInfoPass>().getRegionInfo(); 84 LoopInfo &LI = P->getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 85 86 // Before: 87 // 88 // \ / // 89 // EnteringBB // 90 // _____|_____ // 91 // / EntryBB \ // 92 // | (region) | // 93 // \_ExitingBB_/ // 94 // | // 95 // ExitBB // 96 // / \ // 97 98 // Create a fork block. 99 BasicBlock *EnteringBB = S.getEnteringBlock(); 100 BasicBlock *EntryBB = S.getEntry(); 101 assert(EnteringBB && "Must be a simple region"); 102 BasicBlock *SplitBlock = 103 splitEdge(EnteringBB, EntryBB, ".split_new_and_old", &DT, &LI, &RI); 104 SplitBlock->setName("polly.split_new_and_old"); 105 106 // If EntryBB is the exit block of the region that includes Prev, exclude 107 // SplitBlock from that region by making it itself the exit block. This is 108 // trivially possible because there is just one edge to EnteringBB. 109 // This is necessary because we will add an outgoing edge from SplitBlock, 110 // which would violate the single exit block requirement of PrevRegion. 111 Region *PrevRegion = RI.getRegionFor(EnteringBB); 112 while (PrevRegion->getExit() == EntryBB) { 113 PrevRegion->replaceExit(SplitBlock); 114 PrevRegion = PrevRegion->getParent(); 115 } 116 RI.setRegionFor(SplitBlock, PrevRegion); 117 118 // Create a join block 119 BasicBlock *ExitingBB = S.getExitingBlock(); 120 BasicBlock *ExitBB = S.getExit(); 121 assert(ExitingBB && "Must be a simple region"); 122 BasicBlock *MergeBlock = 123 splitEdge(ExitingBB, ExitBB, ".merge_new_and_old", &DT, &LI, &RI); 124 MergeBlock->setName("polly.merge_new_and_old"); 125 126 // Exclude the join block from the region. 127 R.replaceExitRecursive(MergeBlock); 128 RI.setRegionFor(MergeBlock, R.getParent()); 129 130 // \ / // 131 // EnteringBB // 132 // | // 133 // SplitBlock // 134 // _____|_____ // 135 // / EntryBB \ // 136 // | (region) | // 137 // \_ExitingBB_/ // 138 // | // 139 // MergeBlock // 140 // | // 141 // ExitBB // 142 // / \ // 143 144 // Create the start and exiting block. 145 Function *F = SplitBlock->getParent(); 146 BasicBlock *StartBlock = 147 BasicBlock::Create(F->getContext(), "polly.start", F); 148 BasicBlock *ExitingBlock = 149 BasicBlock::Create(F->getContext(), "polly.exiting", F); 150 SplitBlock->getTerminator()->eraseFromParent(); 151 Builder.SetInsertPoint(SplitBlock); 152 Builder.CreateCondBr(RTC, StartBlock, S.getEntry()); 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 StartBlock; 221 } 222