220 lines · cpp
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-exception6//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 20using namespace llvm;21 22// Alternative to llvm::SplitCriticalEdge.23//24// Creates a new block which branches to Succ. The edge to split is redirected25// to the new block.26//27// The issue with llvm::SplitCriticalEdge is that it does nothing if the edge is28// not critical.29// The issue with llvm::SplitEdge is that it does not always create the middle30// block, but reuses Prev/Succ if it can. We always want a new middle block.31static 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 of46 // llvm::SplitCriticalEdge is more efficient than47 // llvm::SplitBlockPredecessors, which is more general. In the future we might48 // either modify llvm::SplitCriticalEdge to allow skipping the critical edge49 // 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 77std::pair<polly::BBPair, BranchInst *>78polly::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, exclude104 // SplitBlock from that region by making it itself the exit block. This is105 // 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 block116 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