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