480 lines · cpp
1//===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===//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// BreakCriticalEdges pass - Break all of the critical edges in the CFG by10// inserting a dummy basic block. This pass may be "required" by passes that11// cannot deal with critical edges. For this usage, the structure type is12// forward declared. This pass obviously invalidates the CFG, but can update13// dominator trees.14//15//===----------------------------------------------------------------------===//16 17#include "llvm/Transforms/Utils/BreakCriticalEdges.h"18#include "llvm/ADT/SetVector.h"19#include "llvm/ADT/SmallVector.h"20#include "llvm/ADT/Statistic.h"21#include "llvm/Analysis/BlockFrequencyInfo.h"22#include "llvm/Analysis/BranchProbabilityInfo.h"23#include "llvm/Analysis/CFG.h"24#include "llvm/Analysis/LoopInfo.h"25#include "llvm/Analysis/MemorySSAUpdater.h"26#include "llvm/Analysis/PostDominators.h"27#include "llvm/IR/CFG.h"28#include "llvm/IR/Dominators.h"29#include "llvm/IR/Instructions.h"30#include "llvm/InitializePasses.h"31#include "llvm/Transforms/Utils.h"32#include "llvm/Transforms/Utils/BasicBlockUtils.h"33#include "llvm/Transforms/Utils/Cloning.h"34#include "llvm/Transforms/Utils/ValueMapper.h"35using namespace llvm;36 37#define DEBUG_TYPE "break-crit-edges"38 39STATISTIC(NumBroken, "Number of blocks inserted");40 41namespace {42struct BreakCriticalEdges : public FunctionPass {43 static char ID; // Pass identification, replacement for typeid44 BreakCriticalEdges() : FunctionPass(ID) {45 initializeBreakCriticalEdgesPass(*PassRegistry::getPassRegistry());46 }47 48 bool runOnFunction(Function &F) override {49 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();50 auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;51 52 auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();53 auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;54 55 auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();56 auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;57 unsigned N = SplitAllCriticalEdges(58 F, CriticalEdgeSplittingOptions(DT, LI, nullptr, PDT));59 NumBroken += N;60 return N > 0;61 }62 63 void getAnalysisUsage(AnalysisUsage &AU) const override {64 AU.addPreserved<DominatorTreeWrapperPass>();65 AU.addPreserved<LoopInfoWrapperPass>();66 67 // No loop canonicalization guarantees are broken by this pass.68 AU.addPreservedID(LoopSimplifyID);69 }70};71} // namespace72 73char BreakCriticalEdges::ID = 0;74INITIALIZE_PASS(BreakCriticalEdges, "break-crit-edges",75 "Break critical edges in CFG", false, false)76 77// Publicly exposed interface to pass...78char &llvm::BreakCriticalEdgesID = BreakCriticalEdges::ID;79 80FunctionPass *llvm::createBreakCriticalEdgesPass() {81 return new BreakCriticalEdges();82}83 84PreservedAnalyses BreakCriticalEdgesPass::run(Function &F,85 FunctionAnalysisManager &AM) {86 auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);87 auto *LI = AM.getCachedResult<LoopAnalysis>(F);88 unsigned N = SplitAllCriticalEdges(F, CriticalEdgeSplittingOptions(DT, LI));89 NumBroken += N;90 if (N == 0)91 return PreservedAnalyses::all();92 PreservedAnalyses PA;93 PA.preserve<DominatorTreeAnalysis>();94 PA.preserve<LoopAnalysis>();95 return PA;96}97 98//===----------------------------------------------------------------------===//99// Implementation of the external critical edge manipulation functions100//===----------------------------------------------------------------------===//101 102BasicBlock *llvm::SplitCriticalEdge(Instruction *TI, unsigned SuccNum,103 const CriticalEdgeSplittingOptions &Options,104 const Twine &BBName) {105 if (!isCriticalEdge(TI, SuccNum, Options.MergeIdenticalEdges))106 return nullptr;107 108 return SplitKnownCriticalEdge(TI, SuccNum, Options, BBName);109}110 111BasicBlock *112llvm::SplitKnownCriticalEdge(Instruction *TI, unsigned SuccNum,113 const CriticalEdgeSplittingOptions &Options,114 const Twine &BBName) {115 BasicBlock *TIBB = TI->getParent();116 BasicBlock *DestBB = TI->getSuccessor(SuccNum);117 118 // Splitting the critical edge to a pad block is non-trivial.119 // And we cannot split block with IndirectBr as a terminator.120 // Don't do it in this generic function.121 if (DestBB->isEHPad() || isa<IndirectBrInst>(TI))122 return nullptr;123 124 if (Options.IgnoreUnreachableDests &&125 isa<UnreachableInst>(DestBB->getFirstNonPHIOrDbgOrLifetime()))126 return nullptr;127 128 auto *LI = Options.LI;129 SmallVector<BasicBlock *, 4> LoopPreds;130 // Check if extra modifications will be required to preserve loop-simplify131 // form after splitting. If it would require splitting blocks with IndirectBr132 // terminators, bail out if preserving loop-simplify form is requested.133 if (LI) {134 if (Loop *TIL = LI->getLoopFor(TIBB)) {135 136 // The only way that we can break LoopSimplify form by splitting a137 // critical edge is if after the split there exists some edge from TIL to138 // DestBB *and* the only edge into DestBB from outside of TIL is that of139 // NewBB. If the first isn't true, then LoopSimplify still holds, NewBB140 // is the new exit block and it has no non-loop predecessors. If the141 // second isn't true, then DestBB was not in LoopSimplify form prior to142 // the split as it had a non-loop predecessor. In both of these cases,143 // the predecessor must be directly in TIL, not in a subloop, or again144 // LoopSimplify doesn't hold.145 for (BasicBlock *P : predecessors(DestBB)) {146 if (P == TIBB)147 continue; // The new block is known.148 if (LI->getLoopFor(P) != TIL) {149 // No need to re-simplify, it wasn't to start with.150 LoopPreds.clear();151 break;152 }153 LoopPreds.push_back(P);154 }155 // Loop-simplify form can be preserved, if we can split all in-loop156 // predecessors.157 if (any_of(LoopPreds, [](BasicBlock *Pred) {158 return isa<IndirectBrInst>(Pred->getTerminator());159 })) {160 if (Options.PreserveLoopSimplify)161 return nullptr;162 LoopPreds.clear();163 }164 }165 }166 167 // Create a new basic block, linking it into the CFG.168 BasicBlock *NewBB = nullptr;169 if (BBName.str() != "")170 NewBB = BasicBlock::Create(TI->getContext(), BBName);171 else172 NewBB = BasicBlock::Create(TI->getContext(), TIBB->getName() + "." +173 DestBB->getName() +174 "_crit_edge");175 // Create our unconditional branch.176 BranchInst *NewBI = BranchInst::Create(DestBB, NewBB);177 NewBI->setDebugLoc(TI->getDebugLoc());178 if (auto *LoopMD = TI->getMetadata(LLVMContext::MD_loop))179 NewBI->setMetadata(LLVMContext::MD_loop, LoopMD);180 181 // Insert the block into the function... right after the block TI lives in.182 Function &F = *TIBB->getParent();183 Function::iterator FBBI = TIBB->getIterator();184 F.insert(++FBBI, NewBB);185 186 // Branch to the new block, breaking the edge.187 TI->setSuccessor(SuccNum, NewBB);188 189 // If there are any PHI nodes in DestBB, we need to update them so that they190 // merge incoming values from NewBB instead of from TIBB.191 {192 unsigned BBIdx = 0;193 for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {194 // We no longer enter through TIBB, now we come in through NewBB.195 // Revector exactly one entry in the PHI node that used to come from196 // TIBB to come from NewBB.197 PHINode *PN = cast<PHINode>(I);198 199 // Reuse the previous value of BBIdx if it lines up. In cases where we200 // have multiple phi nodes with *lots* of predecessors, this is a speed201 // win because we don't have to scan the PHI looking for TIBB. This202 // happens because the BB list of PHI nodes are usually in the same203 // order.204 if (PN->getIncomingBlock(BBIdx) != TIBB)205 BBIdx = PN->getBasicBlockIndex(TIBB);206 PN->setIncomingBlock(BBIdx, NewBB);207 }208 }209 210 unsigned NumSplitIdenticalEdges = 1;211 212 // If there are any other edges from TIBB to DestBB, update those to go213 // through the split block, making those edges non-critical as well (and214 // reducing the number of phi entries in the DestBB if relevant).215 if (Options.MergeIdenticalEdges) {216 for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {217 if (TI->getSuccessor(i) != DestBB) continue;218 219 // Remove an entry for TIBB from DestBB phi nodes.220 DestBB->removePredecessor(TIBB, Options.KeepOneInputPHIs);221 222 // We found another edge to DestBB, go to NewBB instead.223 TI->setSuccessor(i, NewBB);224 225 // Record the number of split identical edges to DestBB.226 NumSplitIdenticalEdges++;227 }228 }229 230 // If we have nothing to update, just return.231 auto *DT = Options.DT;232 auto *PDT = Options.PDT;233 auto *MSSAU = Options.MSSAU;234 if (MSSAU)235 MSSAU->wireOldPredecessorsToNewImmediatePredecessor(236 DestBB, NewBB, {TIBB}, Options.MergeIdenticalEdges);237 238 if (!DT && !PDT && !LI)239 return NewBB;240 241 if (DT || PDT) {242 // Update the DominatorTree.243 // ---> NewBB -----\244 // / V245 // TIBB -------\\------> DestBB246 //247 // First, inform the DT about the new path from TIBB to DestBB via NewBB,248 // then delete the old edge from TIBB to DestBB. By doing this in that order249 // DestBB stays reachable in the DT the whole time and its subtree doesn't250 // get disconnected.251 SmallVector<DominatorTree::UpdateType, 3> Updates;252 Updates.push_back({DominatorTree::Insert, TIBB, NewBB});253 Updates.push_back({DominatorTree::Insert, NewBB, DestBB});254 if (!llvm::is_contained(successors(TIBB), DestBB))255 Updates.push_back({DominatorTree::Delete, TIBB, DestBB});256 257 if (DT)258 DT->applyUpdates(Updates);259 if (PDT)260 PDT->applyUpdates(Updates);261 }262 263 // Update LoopInfo if it is around.264 if (LI) {265 if (Loop *TIL = LI->getLoopFor(TIBB)) {266 // If one or the other blocks were not in a loop, the new block is not267 // either, and thus LI doesn't need to be updated.268 if (Loop *DestLoop = LI->getLoopFor(DestBB)) {269 if (TIL == DestLoop) {270 // Both in the same loop, the NewBB joins loop.271 DestLoop->addBasicBlockToLoop(NewBB, *LI);272 } else if (TIL->contains(DestLoop)) {273 // Edge from an outer loop to an inner loop. Add to the outer loop.274 TIL->addBasicBlockToLoop(NewBB, *LI);275 } else if (DestLoop->contains(TIL)) {276 // Edge from an inner loop to an outer loop. Add to the outer loop.277 DestLoop->addBasicBlockToLoop(NewBB, *LI);278 } else {279 // Edge from two loops with no containment relation. Because these280 // are natural loops, we know that the destination block must be the281 // header of its loop (adding a branch into a loop elsewhere would282 // create an irreducible loop).283 assert(DestLoop->getHeader() == DestBB &&284 "Should not create irreducible loops!");285 if (Loop *P = DestLoop->getParentLoop())286 P->addBasicBlockToLoop(NewBB, *LI);287 }288 }289 290 // If TIBB is in a loop and DestBB is outside of that loop, we may need291 // to update LoopSimplify form and LCSSA form.292 if (!TIL->contains(DestBB)) {293 assert(!TIL->contains(NewBB) &&294 "Split point for loop exit is contained in loop!");295 296 // Update LCSSA form in the newly created exit block.297 if (Options.PreserveLCSSA) {298 // If > 1 identical edges to be split, we need to introduce the same299 // number of the incoming blocks for the new PHINode.300 createPHIsForSplitLoopExit(301 SmallVector<BasicBlock *, 4>(NumSplitIdenticalEdges, TIBB), NewBB,302 DestBB);303 }304 305 if (!LoopPreds.empty()) {306 assert(!DestBB->isEHPad() && "We don't split edges to EH pads!");307 BasicBlock *NewExitBB = SplitBlockPredecessors(308 DestBB, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA);309 if (Options.PreserveLCSSA)310 createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB);311 }312 }313 }314 }315 316 return NewBB;317}318 319// Return the unique indirectbr predecessor of a block. This may return null320// even if such a predecessor exists, if it's not useful for splitting.321// If a predecessor is found, OtherPreds will contain all other (non-indirectbr)322// predecessors of BB.323static BasicBlock *324findIBRPredecessor(BasicBlock *BB, SmallVectorImpl<BasicBlock *> &OtherPreds) {325 // Verify we have exactly one IBR predecessor.326 // Conservatively bail out if one of the other predecessors is not a "regular"327 // terminator (that is, not a switch or a br).328 BasicBlock *IBB = nullptr;329 for (BasicBlock *PredBB : predecessors(BB)) {330 Instruction *PredTerm = PredBB->getTerminator();331 switch (PredTerm->getOpcode()) {332 case Instruction::IndirectBr:333 if (IBB)334 return nullptr;335 IBB = PredBB;336 break;337 case Instruction::Br:338 case Instruction::Switch:339 OtherPreds.push_back(PredBB);340 continue;341 default:342 return nullptr;343 }344 }345 346 return IBB;347}348 349bool llvm::SplitIndirectBrCriticalEdges(Function &F,350 bool IgnoreBlocksWithoutPHI,351 BranchProbabilityInfo *BPI,352 BlockFrequencyInfo *BFI) {353 // Check whether the function has any indirectbrs, and collect which blocks354 // they may jump to. Since most functions don't have indirect branches,355 // this lowers the common case's overhead to O(Blocks) instead of O(Edges).356 SmallSetVector<BasicBlock *, 16> Targets;357 for (auto &BB : F) {358 if (isa<IndirectBrInst>(BB.getTerminator()))359 Targets.insert_range(successors(&BB));360 }361 362 if (Targets.empty())363 return false;364 365 bool ShouldUpdateAnalysis = BPI && BFI;366 bool Changed = false;367 for (BasicBlock *Target : Targets) {368 if (IgnoreBlocksWithoutPHI && Target->phis().empty())369 continue;370 371 SmallVector<BasicBlock *, 16> OtherPreds;372 BasicBlock *IBRPred = findIBRPredecessor(Target, OtherPreds);373 // If we did not found an indirectbr, or the indirectbr is the only374 // incoming edge, this isn't the kind of edge we're looking for.375 if (!IBRPred || OtherPreds.empty())376 continue;377 378 // Don't even think about ehpads/landingpads.379 auto FirstNonPHIIt = Target->getFirstNonPHIIt();380 if (FirstNonPHIIt->isEHPad() || Target->isLandingPad())381 continue;382 383 // Remember edge probabilities if needed.384 SmallVector<BranchProbability, 4> EdgeProbabilities;385 if (ShouldUpdateAnalysis) {386 EdgeProbabilities.reserve(Target->getTerminator()->getNumSuccessors());387 for (unsigned I = 0, E = Target->getTerminator()->getNumSuccessors();388 I < E; ++I)389 EdgeProbabilities.emplace_back(BPI->getEdgeProbability(Target, I));390 BPI->eraseBlock(Target);391 }392 393 BasicBlock *BodyBlock = Target->splitBasicBlock(FirstNonPHIIt, ".split");394 if (ShouldUpdateAnalysis) {395 // Copy the BFI/BPI from Target to BodyBlock.396 BPI->setEdgeProbability(BodyBlock, EdgeProbabilities);397 BFI->setBlockFreq(BodyBlock, BFI->getBlockFreq(Target));398 }399 // It's possible Target was its own successor through an indirectbr.400 // In this case, the indirectbr now comes from BodyBlock.401 if (IBRPred == Target)402 IBRPred = BodyBlock;403 404 // At this point Target only has PHIs, and BodyBlock has the rest of the405 // block's body. Create a copy of Target that will be used by the "direct"406 // preds.407 ValueToValueMapTy VMap;408 BasicBlock *DirectSucc = CloneBasicBlock(Target, VMap, ".clone", &F);409 if (!VMap.AtomMap.empty())410 for (Instruction &I : *DirectSucc)411 RemapSourceAtom(&I, VMap);412 413 BlockFrequency BlockFreqForDirectSucc;414 for (BasicBlock *Pred : OtherPreds) {415 // If the target is a loop to itself, then the terminator of the split416 // block (BodyBlock) needs to be updated.417 BasicBlock *Src = Pred != Target ? Pred : BodyBlock;418 Src->getTerminator()->replaceUsesOfWith(Target, DirectSucc);419 if (ShouldUpdateAnalysis)420 BlockFreqForDirectSucc += BFI->getBlockFreq(Src) *421 BPI->getEdgeProbability(Src, DirectSucc);422 }423 if (ShouldUpdateAnalysis) {424 BFI->setBlockFreq(DirectSucc, BlockFreqForDirectSucc);425 BlockFrequency NewBlockFreqForTarget =426 BFI->getBlockFreq(Target) - BlockFreqForDirectSucc;427 BFI->setBlockFreq(Target, NewBlockFreqForTarget);428 }429 430 // Ok, now fix up the PHIs. We know the two blocks only have PHIs, and that431 // they are clones, so the number of PHIs are the same.432 // (a) Remove the edge coming from IBRPred from the "Direct" PHI433 // (b) Leave that as the only edge in the "Indirect" PHI.434 // (c) Merge the two in the body block.435 BasicBlock::iterator Indirect = Target->begin(),436 End = Target->getFirstNonPHIIt();437 BasicBlock::iterator Direct = DirectSucc->begin();438 BasicBlock::iterator MergeInsert = BodyBlock->getFirstInsertionPt();439 440 assert(&*End == Target->getTerminator() &&441 "Block was expected to only contain PHIs");442 443 while (Indirect != End) {444 PHINode *DirPHI = cast<PHINode>(Direct);445 PHINode *IndPHI = cast<PHINode>(Indirect);446 BasicBlock::iterator InsertPt = Indirect;447 448 // Now, clean up - the direct block shouldn't get the indirect value,449 // and vice versa.450 DirPHI->removeIncomingValue(IBRPred);451 Direct++;452 453 // Advance the pointer here, to avoid invalidation issues when the old454 // PHI is erased.455 Indirect++;456 457 PHINode *NewIndPHI = PHINode::Create(IndPHI->getType(), 1, "ind", InsertPt);458 NewIndPHI->addIncoming(IndPHI->getIncomingValueForBlock(IBRPred),459 IBRPred);460 NewIndPHI->setDebugLoc(IndPHI->getDebugLoc());461 462 // Create a PHI in the body block, to merge the direct and indirect463 // predecessors.464 PHINode *MergePHI = PHINode::Create(IndPHI->getType(), 2, "merge");465 MergePHI->insertBefore(MergeInsert);466 MergePHI->addIncoming(NewIndPHI, Target);467 MergePHI->addIncoming(DirPHI, DirectSucc);468 MergePHI->applyMergedLocation(DirPHI->getDebugLoc(),469 IndPHI->getDebugLoc());470 471 IndPHI->replaceAllUsesWith(MergePHI);472 IndPHI->eraseFromParent();473 }474 475 Changed = true;476 }477 478 return Changed;479}480