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 // Create a join block 107 BasicBlock *ExitingBB = R.getExitingBlock(); 108 BasicBlock *ExitBB = R.getExit(); 109 assert(ExitingBB && "Must be a simple region"); 110 BasicBlock *MergeBlock = 111 splitEdge(ExitingBB, ExitBB, ".merge_new_and_old", &DT, &LI, &RI); 112 MergeBlock->setName("polly.merge_new_and_old"); 113 114 // Exclude the join block from the region. 115 R.replaceExitRecursive(MergeBlock); 116 RI.setRegionFor(MergeBlock, R.getParent()); 117 118 // \ / // 119 // EnteringBB // 120 // | // 121 // SplitBlock // 122 // _____|_____ // 123 // / EntryBB \ // 124 // | (region) | // 125 // \_ExitingBB_/ // 126 // | // 127 // MergeBlock // 128 // | // 129 // ExitBB // 130 // / \ // 131 132 // Create the start block. 133 Function *F = SplitBlock->getParent(); 134 BasicBlock *StartBlock = 135 BasicBlock::Create(F->getContext(), "polly.start", F); 136 SplitBlock->getTerminator()->eraseFromParent(); 137 Builder.SetInsertPoint(SplitBlock); 138 Builder.CreateCondBr(RTC, StartBlock, R.getEntry()); 139 if (Loop *L = LI.getLoopFor(SplitBlock)) 140 L->addBasicBlockToLoop(StartBlock, LI); 141 DT.addNewBlock(StartBlock, SplitBlock); 142 RI.setRegionFor(StartBlock, RI.getRegionFor(SplitBlock)); 143 144 // \ / // 145 // EnteringBB // 146 // | // 147 // SplitBlock---------\ // 148 // _____|_____ | // 149 // / EntryBB \ StartBlock // 150 // | (region) | // 151 // \_ExitingBB_/ // 152 // | // 153 // MergeBlock // 154 // | // 155 // ExitBB // 156 // / \ // 157 158 // Connect start block to the join block. 159 Builder.SetInsertPoint(StartBlock); 160 Builder.CreateBr(MergeBlock); 161 DT.changeImmediateDominator(MergeBlock, SplitBlock); 162 163 // \ / // 164 // EnteringBB // 165 // | // 166 // SplitBlock---------\ // 167 // _____|_____ | // 168 // / EntryBB \ StartBlock // 169 // | (region) | | // 170 // \_ExitingBB_/ | // 171 // | | // 172 // MergeBlock---------/ // 173 // | // 174 // ExitBB // 175 // / \ // 176 177 return StartBlock; 178 } 179