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, Value *RTC, 80 DominatorTree &DT, RegionInfo &RI, 81 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 Builder.CreateCondBr(RTC, StartBlock, S.getEntry()); 152 if (Loop *L = LI.getLoopFor(SplitBlock)) { 153 L->addBasicBlockToLoop(StartBlock, LI); 154 L->addBasicBlockToLoop(ExitingBlock, LI); 155 } 156 DT.addNewBlock(StartBlock, SplitBlock); 157 DT.addNewBlock(ExitingBlock, StartBlock); 158 RI.setRegionFor(StartBlock, RI.getRegionFor(SplitBlock)); 159 RI.setRegionFor(ExitingBlock, RI.getRegionFor(SplitBlock)); 160 161 // \ / // 162 // EnteringBB // 163 // | // 164 // SplitBlock---------\ // 165 // _____|_____ | // 166 // / EntryBB \ StartBlock // 167 // | (region) | | // 168 // \_ExitingBB_/ ExitingBlock // 169 // | // 170 // MergeBlock // 171 // | // 172 // ExitBB // 173 // / \ // 174 175 // Connect start block to exiting block. 176 Builder.SetInsertPoint(StartBlock); 177 Builder.CreateBr(ExitingBlock); 178 DT.changeImmediateDominator(ExitingBlock, StartBlock); 179 180 // Connect exiting block to join block. 181 Builder.SetInsertPoint(ExitingBlock); 182 Builder.CreateBr(MergeBlock); 183 DT.changeImmediateDominator(MergeBlock, SplitBlock); 184 185 // \ / // 186 // EnteringBB // 187 // | // 188 // SplitBlock---------\ // 189 // _____|_____ | // 190 // / EntryBB \ StartBlock // 191 // | (region) | | // 192 // \_ExitingBB_/ ExitingBlock // 193 // | | // 194 // MergeBlock---------/ // 195 // | // 196 // ExitBB // 197 // / \ // 198 // 199 200 // Split the edge between SplitBlock and EntryBB, to avoid a critical edge. 201 splitEdge(SplitBlock, EntryBB, ".pre_entry_bb", &DT, &LI, &RI); 202 203 // \ / // 204 // EnteringBB // 205 // | // 206 // SplitBlock---------\ // 207 // | | // 208 // PreEntryBB | // 209 // _____|_____ | // 210 // / EntryBB \ StartBlock // 211 // | (region) | | // 212 // \_ExitingBB_/ ExitingBlock // 213 // | | // 214 // MergeBlock---------/ // 215 // | // 216 // ExitBB // 217 // / \ // 218 219 return StartBlock; 220 } 221