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(R.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 = R.getEnteringBlock(); 100 BasicBlock *EntryBB = R.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 = R.getExitingBlock(); 120 BasicBlock *ExitBB = R.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 block. 145 Function *F = SplitBlock->getParent(); 146 BasicBlock *StartBlock = 147 BasicBlock::Create(F->getContext(), "polly.start", F); 148 SplitBlock->getTerminator()->eraseFromParent(); 149 Builder.SetInsertPoint(SplitBlock); 150 Builder.CreateCondBr(RTC, StartBlock, R.getEntry()); 151 if (Loop *L = LI.getLoopFor(SplitBlock)) 152 L->addBasicBlockToLoop(StartBlock, LI); 153 DT.addNewBlock(StartBlock, SplitBlock); 154 RI.setRegionFor(StartBlock, RI.getRegionFor(SplitBlock)); 155 156 // \ / // 157 // EnteringBB // 158 // | // 159 // SplitBlock---------\ // 160 // _____|_____ | // 161 // / EntryBB \ StartBlock // 162 // | (region) | // 163 // \_ExitingBB_/ // 164 // | // 165 // MergeBlock // 166 // | // 167 // ExitBB // 168 // / \ // 169 170 // Connect start block to the join block. 171 Builder.SetInsertPoint(StartBlock); 172 Builder.CreateBr(MergeBlock); 173 DT.changeImmediateDominator(MergeBlock, SplitBlock); 174 175 // \ / // 176 // EnteringBB // 177 // | // 178 // SplitBlock---------\ // 179 // _____|_____ | // 180 // / EntryBB \ StartBlock // 181 // | (region) | | // 182 // \_ExitingBB_/ | // 183 // | | // 184 // MergeBlock---------/ // 185 // | // 186 // ExitBB // 187 // / \ // 188 189 return StartBlock; 190 } 191