1 //===--- Utils.cpp - Utility functions for the code generation --*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file contains utility functions for the code generation. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "polly/CodeGen/Utils.h" 14 #include "polly/CodeGen/IRBuilder.h" 15 #include "polly/ScopInfo.h" 16 #include "llvm/Analysis/LoopInfo.h" 17 #include "llvm/Analysis/RegionInfo.h" 18 #include "llvm/Support/Debug.h" 19 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 20 21 using namespace llvm; 22 23 // Alternative to llvm::SplitCriticalEdge. 24 // 25 // Creates a new block which branches to Succ. The edge to split is redirected 26 // to the new block. 27 // 28 // The issue with llvm::SplitCriticalEdge is that it does nothing if the edge is 29 // not critical. 30 // The issue with llvm::SplitEdge is that it does not always create the middle 31 // block, but reuses Prev/Succ if it can. We always want a new middle block. 32 static BasicBlock *splitEdge(BasicBlock *Prev, BasicBlock *Succ, 33 const char *Suffix, DominatorTree *DT, 34 LoopInfo *LI, RegionInfo *RI) { 35 assert(Prev && Succ); 36 37 // Before: 38 // \ / / // 39 // Prev / // 40 // | \___/ // 41 // | ___ // 42 // | / \ // 43 // Succ \ // 44 // / \ \ // 45 46 // The algorithm to update DominatorTree and LoopInfo of 47 // llvm::SplitCriticalEdge is more efficient than 48 // llvm::SplitBlockPredecessors, which is more general. In the future we might 49 // either modify llvm::SplitCriticalEdge to allow skipping the critical edge 50 // check; or Copy&Pase it here. 51 BasicBlock *MiddleBlock = SplitBlockPredecessors( 52 Succ, ArrayRef<BasicBlock *>(Prev), Suffix, DT, LI); 53 54 if (RI) { 55 Region *PrevRegion = RI->getRegionFor(Prev); 56 Region *SuccRegion = RI->getRegionFor(Succ); 57 if (PrevRegion->contains(MiddleBlock)) { 58 RI->setRegionFor(MiddleBlock, PrevRegion); 59 } else { 60 RI->setRegionFor(MiddleBlock, SuccRegion); 61 } 62 } 63 64 // After: 65 // \ / / // 66 // Prev / // 67 // | \___/ // 68 // | // 69 // MiddleBlock // 70 // | ___ // 71 // | / \ // 72 // Succ \ // 73 // / \ \ // 74 75 return MiddleBlock; 76 } 77 78 std::pair<polly::BBPair, BranchInst *> 79 polly::executeScopConditionally(Scop &S, Value *RTC, DominatorTree &DT, 80 RegionInfo &RI, LoopInfo &LI) { 81 Region &R = S.getRegion(); 82 PollyIRBuilder Builder(S.getEntry()); 83 84 // Before: 85 // 86 // \ / // 87 // EnteringBB // 88 // _____|_____ // 89 // / EntryBB \ // 90 // | (region) | // 91 // \_ExitingBB_/ // 92 // | // 93 // ExitBB // 94 // / \ // 95 96 // Create a fork block. 97 BasicBlock *EnteringBB = S.getEnteringBlock(); 98 BasicBlock *EntryBB = S.getEntry(); 99 assert(EnteringBB && "Must be a simple region"); 100 BasicBlock *SplitBlock = 101 splitEdge(EnteringBB, EntryBB, ".split_new_and_old", &DT, &LI, &RI); 102 SplitBlock->setName("polly.split_new_and_old"); 103 104 // If EntryBB is the exit block of the region that includes Prev, exclude 105 // SplitBlock from that region by making it itself the exit block. This is 106 // trivially possible because there is just one edge to EnteringBB. 107 // This is necessary because we will add an outgoing edge from SplitBlock, 108 // which would violate the single exit block requirement of PrevRegion. 109 Region *PrevRegion = RI.getRegionFor(EnteringBB); 110 while (PrevRegion->getExit() == EntryBB) { 111 PrevRegion->replaceExit(SplitBlock); 112 PrevRegion = PrevRegion->getParent(); 113 } 114 RI.setRegionFor(SplitBlock, PrevRegion); 115 116 // Create a join block 117 BasicBlock *ExitingBB = S.getExitingBlock(); 118 BasicBlock *ExitBB = S.getExit(); 119 assert(ExitingBB && "Must be a simple region"); 120 BasicBlock *MergeBlock = 121 splitEdge(ExitingBB, ExitBB, ".merge_new_and_old", &DT, &LI, &RI); 122 MergeBlock->setName("polly.merge_new_and_old"); 123 124 // Exclude the join block from the region. 125 R.replaceExitRecursive(MergeBlock); 126 RI.setRegionFor(MergeBlock, R.getParent()); 127 128 // \ / // 129 // EnteringBB // 130 // | // 131 // SplitBlock // 132 // _____|_____ // 133 // / EntryBB \ // 134 // | (region) | // 135 // \_ExitingBB_/ // 136 // | // 137 // MergeBlock // 138 // | // 139 // ExitBB // 140 // / \ // 141 142 // Create the start and exiting block. 143 Function *F = SplitBlock->getParent(); 144 BasicBlock *StartBlock = 145 BasicBlock::Create(F->getContext(), "polly.start", F); 146 BasicBlock *ExitingBlock = 147 BasicBlock::Create(F->getContext(), "polly.exiting", F); 148 SplitBlock->getTerminator()->eraseFromParent(); 149 Builder.SetInsertPoint(SplitBlock); 150 BranchInst *CondBr = Builder.CreateCondBr(RTC, StartBlock, S.getEntry()); 151 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 std::make_pair(std::make_pair(StartBlock, ExitingBlock), CondBr); 220 } 221