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/Transforms/Utils/BasicBlockUtils.h" 19 20 using namespace llvm; 21 22 // Alternative to llvm::SplitCriticalEdge. 23 // 24 // Creates a new block which branches to Succ. The edge to split is redirected 25 // to the new block. 26 // 27 // The issue with llvm::SplitCriticalEdge is that it does nothing if the edge is 28 // not critical. 29 // The issue with llvm::SplitEdge is that it does not always create the middle 30 // block, but reuses Prev/Succ if it can. We always want a new middle block. 31 static BasicBlock *splitEdge(BasicBlock *Prev, BasicBlock *Succ, 32 const char *Suffix, DominatorTree *DT, 33 LoopInfo *LI, RegionInfo *RI) { 34 assert(Prev && Succ); 35 36 // Before: 37 // \ / / // 38 // Prev / // 39 // | \___/ // 40 // | ___ // 41 // | / \ // 42 // Succ \ // 43 // / \ \ // 44 45 // The algorithm to update DominatorTree and LoopInfo of 46 // llvm::SplitCriticalEdge is more efficient than 47 // llvm::SplitBlockPredecessors, which is more general. In the future we might 48 // either modify llvm::SplitCriticalEdge to allow skipping the critical edge 49 // check; or Copy&Paste it here. 50 BasicBlock *MiddleBlock = SplitBlockPredecessors( 51 Succ, ArrayRef<BasicBlock *>(Prev), Suffix, DT, LI); 52 53 if (RI) { 54 Region *PrevRegion = RI->getRegionFor(Prev); 55 Region *SuccRegion = RI->getRegionFor(Succ); 56 if (PrevRegion->contains(MiddleBlock)) { 57 RI->setRegionFor(MiddleBlock, PrevRegion); 58 } else { 59 RI->setRegionFor(MiddleBlock, SuccRegion); 60 } 61 } 62 63 // After: 64 // \ / / // 65 // Prev / // 66 // | \___/ // 67 // | // 68 // MiddleBlock // 69 // | ___ // 70 // | / \ // 71 // Succ \ // 72 // / \ \ // 73 74 return MiddleBlock; 75 } 76 77 std::pair<polly::BBPair, BranchInst *> 78 polly::executeScopConditionally(Scop &S, Value *RTC, DominatorTree &DT, 79 RegionInfo &RI, LoopInfo &LI) { 80 Region &R = S.getRegion(); 81 PollyIRBuilder Builder(S.getEntry()); 82 83 // Before: 84 // 85 // \ / // 86 // EnteringBB // 87 // _____|_____ // 88 // / EntryBB \ // 89 // | (region) | // 90 // \_ExitingBB_/ // 91 // | // 92 // ExitBB // 93 // / \ // 94 95 // Create a fork block. 96 BasicBlock *EnteringBB = S.getEnteringBlock(); 97 BasicBlock *EntryBB = S.getEntry(); 98 assert(EnteringBB && "Must be a simple region"); 99 BasicBlock *SplitBlock = 100 splitEdge(EnteringBB, EntryBB, ".split_new_and_old", &DT, &LI, &RI); 101 SplitBlock->setName("polly.split_new_and_old"); 102 103 // If EntryBB is the exit block of the region that includes Prev, exclude 104 // SplitBlock from that region by making it itself the exit block. This is 105 // trivially possible because there is just one edge to EnteringBB. 106 // This is necessary because we will add an outgoing edge from SplitBlock, 107 // which would violate the single exit block requirement of PrevRegion. 108 Region *PrevRegion = RI.getRegionFor(EnteringBB); 109 while (PrevRegion->getExit() == EntryBB) { 110 PrevRegion->replaceExit(SplitBlock); 111 PrevRegion = PrevRegion->getParent(); 112 } 113 RI.setRegionFor(SplitBlock, PrevRegion); 114 115 // Create a join block 116 BasicBlock *ExitingBB = S.getExitingBlock(); 117 BasicBlock *ExitBB = S.getExit(); 118 assert(ExitingBB && "Must be a simple region"); 119 BasicBlock *MergeBlock = 120 splitEdge(ExitingBB, ExitBB, ".merge_new_and_old", &DT, &LI, &RI); 121 MergeBlock->setName("polly.merge_new_and_old"); 122 123 // Exclude the join block from the region. 124 R.replaceExitRecursive(MergeBlock); 125 RI.setRegionFor(MergeBlock, R.getParent()); 126 127 // \ / // 128 // EnteringBB // 129 // | // 130 // SplitBlock // 131 // _____|_____ // 132 // / EntryBB \ // 133 // | (region) | // 134 // \_ExitingBB_/ // 135 // | // 136 // MergeBlock // 137 // | // 138 // ExitBB // 139 // / \ // 140 141 // Create the start and exiting block. 142 Function *F = SplitBlock->getParent(); 143 BasicBlock *StartBlock = 144 BasicBlock::Create(F->getContext(), "polly.start", F); 145 BasicBlock *ExitingBlock = 146 BasicBlock::Create(F->getContext(), "polly.exiting", F); 147 SplitBlock->getTerminator()->eraseFromParent(); 148 Builder.SetInsertPoint(SplitBlock); 149 BranchInst *CondBr = Builder.CreateCondBr(RTC, StartBlock, S.getEntry()); 150 151 if (Loop *L = LI.getLoopFor(SplitBlock)) { 152 L->addBasicBlockToLoop(StartBlock, LI); 153 L->addBasicBlockToLoop(ExitingBlock, LI); 154 } 155 DT.addNewBlock(StartBlock, SplitBlock); 156 DT.addNewBlock(ExitingBlock, StartBlock); 157 RI.setRegionFor(StartBlock, RI.getRegionFor(SplitBlock)); 158 RI.setRegionFor(ExitingBlock, RI.getRegionFor(SplitBlock)); 159 160 // \ / // 161 // EnteringBB // 162 // | // 163 // SplitBlock---------\ // 164 // _____|_____ | // 165 // / EntryBB \ StartBlock // 166 // | (region) | | // 167 // \_ExitingBB_/ ExitingBlock // 168 // | // 169 // MergeBlock // 170 // | // 171 // ExitBB // 172 // / \ // 173 174 // Connect start block to exiting block. 175 Builder.SetInsertPoint(StartBlock); 176 Builder.CreateBr(ExitingBlock); 177 DT.changeImmediateDominator(ExitingBlock, StartBlock); 178 179 // Connect exiting block to join block. 180 Builder.SetInsertPoint(ExitingBlock); 181 Builder.CreateBr(MergeBlock); 182 DT.changeImmediateDominator(MergeBlock, SplitBlock); 183 184 // \ / // 185 // EnteringBB // 186 // | // 187 // SplitBlock---------\ // 188 // _____|_____ | // 189 // / EntryBB \ StartBlock // 190 // | (region) | | // 191 // \_ExitingBB_/ ExitingBlock // 192 // | | // 193 // MergeBlock---------/ // 194 // | // 195 // ExitBB // 196 // / \ // 197 // 198 199 // Split the edge between SplitBlock and EntryBB, to avoid a critical edge. 200 splitEdge(SplitBlock, EntryBB, ".pre_entry_bb", &DT, &LI, &RI); 201 202 // \ / // 203 // EnteringBB // 204 // | // 205 // SplitBlock---------\ // 206 // | | // 207 // PreEntryBB | // 208 // _____|_____ | // 209 // / EntryBB \ StartBlock // 210 // | (region) | | // 211 // \_ExitingBB_/ ExitingBlock // 212 // | | // 213 // MergeBlock---------/ // 214 // | // 215 // ExitBB // 216 // / \ // 217 218 return std::make_pair(std::make_pair(StartBlock, ExitingBlock), CondBr); 219 } 220