1 //===- Transform/Utils/BasicBlockUtils.h - BasicBlock Utils -----*- 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 family of functions perform manipulations on basic blocks, and 10 // instructions contained within basic blocks. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H 15 #define LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H 16 17 // FIXME: Move to this file: BasicBlock::removePredecessor, BB::splitBasicBlock 18 19 #include "llvm/ADT/ArrayRef.h" 20 #include "llvm/ADT/SetVector.h" 21 #include "llvm/Analysis/DomTreeUpdater.h" 22 #include "llvm/Analysis/LoopInfo.h" 23 #include "llvm/IR/BasicBlock.h" 24 #include "llvm/IR/CFG.h" 25 #include "llvm/IR/InstrTypes.h" 26 #include <cassert> 27 28 namespace llvm { 29 30 class BlockFrequencyInfo; 31 class BranchProbabilityInfo; 32 class DominatorTree; 33 class DomTreeUpdater; 34 class Function; 35 class Instruction; 36 class LoopInfo; 37 class MDNode; 38 class MemoryDependenceResults; 39 class MemorySSAUpdater; 40 class PostDominatorTree; 41 class ReturnInst; 42 class TargetLibraryInfo; 43 class Value; 44 45 /// Replace contents of every block in \p BBs with single unreachable 46 /// instruction. If \p Updates is specified, collect all necessary DT updates 47 /// into this vector. If \p KeepOneInputPHIs is true, one-input Phis in 48 /// successors of blocks being deleted will be preserved. 49 void DetatchDeadBlocks(ArrayRef <BasicBlock *> BBs, 50 SmallVectorImpl<DominatorTree::UpdateType> *Updates, 51 bool KeepOneInputPHIs = false); 52 53 /// Delete the specified block, which must have no predecessors. 54 void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU = nullptr, 55 bool KeepOneInputPHIs = false); 56 57 /// Delete the specified blocks from \p BB. The set of deleted blocks must have 58 /// no predecessors that are not being deleted themselves. \p BBs must have no 59 /// duplicating blocks. If there are loops among this set of blocks, all 60 /// relevant loop info updates should be done before this function is called. 61 /// If \p KeepOneInputPHIs is true, one-input Phis in successors of blocks 62 /// being deleted will be preserved. 63 void DeleteDeadBlocks(ArrayRef <BasicBlock *> BBs, 64 DomTreeUpdater *DTU = nullptr, 65 bool KeepOneInputPHIs = false); 66 67 /// Delete all basic blocks from \p F that are not reachable from its entry 68 /// node. If \p KeepOneInputPHIs is true, one-input Phis in successors of 69 /// blocks being deleted will be preserved. 70 bool EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU = nullptr, 71 bool KeepOneInputPHIs = false); 72 73 /// We know that BB has one predecessor. If there are any single-entry PHI nodes 74 /// in it, fold them away. This handles the case when all entries to the PHI 75 /// nodes in a block are guaranteed equal, such as when the block has exactly 76 /// one predecessor. 77 bool FoldSingleEntryPHINodes(BasicBlock *BB, 78 MemoryDependenceResults *MemDep = nullptr); 79 80 /// Examine each PHI in the given block and delete it if it is dead. Also 81 /// recursively delete any operands that become dead as a result. This includes 82 /// tracing the def-use list from the PHI to see if it is ultimately unused or 83 /// if it reaches an unused cycle. Return true if any PHIs were deleted. 84 bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr, 85 MemorySSAUpdater *MSSAU = nullptr); 86 87 /// Attempts to merge a block into its predecessor, if possible. The return 88 /// value indicates success or failure. 89 /// By default do not merge blocks if BB's predecessor has multiple successors. 90 /// If PredecessorWithTwoSuccessors = true, the blocks can only be merged 91 /// if BB's Pred has a branch to BB and to AnotherBB, and BB has a single 92 /// successor Sing. In this case the branch will be updated with Sing instead of 93 /// BB, and BB will still be merged into its predecessor and removed. 94 bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU = nullptr, 95 LoopInfo *LI = nullptr, 96 MemorySSAUpdater *MSSAU = nullptr, 97 MemoryDependenceResults *MemDep = nullptr, 98 bool PredecessorWithTwoSuccessors = false); 99 100 /// Merge block(s) sucessors, if possible. Return true if at least two 101 /// of the blocks were merged together. 102 /// In order to merge, each block must be terminated by an unconditional 103 /// branch. If L is provided, then the blocks merged into their predecessors 104 /// must be in L. In addition, This utility calls on another utility: 105 /// MergeBlockIntoPredecessor. Blocks are successfully merged when the call to 106 /// MergeBlockIntoPredecessor returns true. 107 bool MergeBlockSuccessorsIntoGivenBlocks( 108 SmallPtrSetImpl<BasicBlock *> &MergeBlocks, Loop *L = nullptr, 109 DomTreeUpdater *DTU = nullptr, LoopInfo *LI = nullptr); 110 111 /// Try to remove redundant dbg.value instructions from given basic block. 112 /// Returns true if at least one instruction was removed. Remove redundant 113 /// pseudo ops when RemovePseudoOp is true. 114 bool RemoveRedundantDbgInstrs(BasicBlock *BB, bool RemovePseudoOp = false); 115 116 /// Replace all uses of an instruction (specified by BI) with a value, then 117 /// remove and delete the original instruction. 118 void ReplaceInstWithValue(BasicBlock::InstListType &BIL, 119 BasicBlock::iterator &BI, Value *V); 120 121 /// Replace the instruction specified by BI with the instruction specified by I. 122 /// Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. The 123 /// original instruction is deleted and BI is updated to point to the new 124 /// instruction. 125 void ReplaceInstWithInst(BasicBlock::InstListType &BIL, 126 BasicBlock::iterator &BI, Instruction *I); 127 128 /// Replace the instruction specified by From with the instruction specified by 129 /// To. Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. 130 void ReplaceInstWithInst(Instruction *From, Instruction *To); 131 132 /// Option class for critical edge splitting. 133 /// 134 /// This provides a builder interface for overriding the default options used 135 /// during critical edge splitting. 136 struct CriticalEdgeSplittingOptions { 137 DominatorTree *DT; 138 PostDominatorTree *PDT; 139 LoopInfo *LI; 140 MemorySSAUpdater *MSSAU; 141 bool MergeIdenticalEdges = false; 142 bool KeepOneInputPHIs = false; 143 bool PreserveLCSSA = false; 144 bool IgnoreUnreachableDests = false; 145 /// SplitCriticalEdge is guaranteed to preserve loop-simplify form if LI is 146 /// provided. If it cannot be preserved, no splitting will take place. If it 147 /// is not set, preserve loop-simplify form if possible. 148 bool PreserveLoopSimplify = true; 149 150 CriticalEdgeSplittingOptions(DominatorTree *DT = nullptr, 151 LoopInfo *LI = nullptr, 152 MemorySSAUpdater *MSSAU = nullptr, 153 PostDominatorTree *PDT = nullptr) 154 : DT(DT), PDT(PDT), LI(LI), MSSAU(MSSAU) {} 155 156 CriticalEdgeSplittingOptions &setMergeIdenticalEdges() { 157 MergeIdenticalEdges = true; 158 return *this; 159 } 160 161 CriticalEdgeSplittingOptions &setKeepOneInputPHIs() { 162 KeepOneInputPHIs = true; 163 return *this; 164 } 165 166 CriticalEdgeSplittingOptions &setPreserveLCSSA() { 167 PreserveLCSSA = true; 168 return *this; 169 } 170 171 CriticalEdgeSplittingOptions &setIgnoreUnreachableDests() { 172 IgnoreUnreachableDests = true; 173 return *this; 174 } 175 176 CriticalEdgeSplittingOptions &unsetPreserveLoopSimplify() { 177 PreserveLoopSimplify = false; 178 return *this; 179 } 180 }; 181 182 /// When a loop exit edge is split, LCSSA form may require new PHIs in the new 183 /// exit block. This function inserts the new PHIs, as needed. Preds is a list 184 /// of preds inside the loop, SplitBB is the new loop exit block, and DestBB is 185 /// the old loop exit, now the successor of SplitBB. 186 void createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds, 187 BasicBlock *SplitBB, BasicBlock *DestBB); 188 189 /// If this edge is a critical edge, insert a new node to split the critical 190 /// edge. This will update the analyses passed in through the option struct. 191 /// This returns the new block if the edge was split, null otherwise. 192 /// 193 /// If MergeIdenticalEdges in the options struct is true (not the default), 194 /// *all* edges from TI to the specified successor will be merged into the same 195 /// critical edge block. This is most commonly interesting with switch 196 /// instructions, which may have many edges to any one destination. This 197 /// ensures that all edges to that dest go to one block instead of each going 198 /// to a different block, but isn't the standard definition of a "critical 199 /// edge". 200 /// 201 /// It is invalid to call this function on a critical edge that starts at an 202 /// IndirectBrInst. Splitting these edges will almost always create an invalid 203 /// program because the address of the new block won't be the one that is jumped 204 /// to. 205 BasicBlock *SplitCriticalEdge(Instruction *TI, unsigned SuccNum, 206 const CriticalEdgeSplittingOptions &Options = 207 CriticalEdgeSplittingOptions(), 208 const Twine &BBName = ""); 209 210 /// If it is known that an edge is critical, SplitKnownCriticalEdge can be 211 /// called directly, rather than calling SplitCriticalEdge first. 212 BasicBlock *SplitKnownCriticalEdge(Instruction *TI, unsigned SuccNum, 213 const CriticalEdgeSplittingOptions &Options = 214 CriticalEdgeSplittingOptions(), 215 const Twine &BBName = ""); 216 217 inline BasicBlock * 218 SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, 219 const CriticalEdgeSplittingOptions &Options = 220 CriticalEdgeSplittingOptions()) { 221 return SplitCriticalEdge(BB->getTerminator(), SI.getSuccessorIndex(), 222 Options); 223 } 224 225 /// If the edge from *PI to BB is not critical, return false. Otherwise, split 226 /// all edges between the two blocks and return true. This updates all of the 227 /// same analyses as the other SplitCriticalEdge function. If P is specified, it 228 /// updates the analyses described above. 229 inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, 230 const CriticalEdgeSplittingOptions &Options = 231 CriticalEdgeSplittingOptions()) { 232 bool MadeChange = false; 233 Instruction *TI = (*PI)->getTerminator(); 234 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 235 if (TI->getSuccessor(i) == Succ) 236 MadeChange |= !!SplitCriticalEdge(TI, i, Options); 237 return MadeChange; 238 } 239 240 /// If an edge from Src to Dst is critical, split the edge and return true, 241 /// otherwise return false. This method requires that there be an edge between 242 /// the two blocks. It updates the analyses passed in the options struct 243 inline BasicBlock * 244 SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst, 245 const CriticalEdgeSplittingOptions &Options = 246 CriticalEdgeSplittingOptions()) { 247 Instruction *TI = Src->getTerminator(); 248 unsigned i = 0; 249 while (true) { 250 assert(i != TI->getNumSuccessors() && "Edge doesn't exist!"); 251 if (TI->getSuccessor(i) == Dst) 252 return SplitCriticalEdge(TI, i, Options); 253 ++i; 254 } 255 } 256 257 /// Loop over all of the edges in the CFG, breaking critical edges as they are 258 /// found. Returns the number of broken edges. 259 unsigned SplitAllCriticalEdges(Function &F, 260 const CriticalEdgeSplittingOptions &Options = 261 CriticalEdgeSplittingOptions()); 262 263 /// Split the edge connecting the specified blocks, and return the newly created 264 /// basic block between \p From and \p To. 265 BasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To, 266 DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, 267 MemorySSAUpdater *MSSAU = nullptr, 268 const Twine &BBName = ""); 269 270 /// Sets the unwind edge of an instruction to a particular successor. 271 void setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ); 272 273 /// Replaces all uses of OldPred with the NewPred block in all PHINodes in a 274 /// block. 275 void updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred, 276 BasicBlock *NewPred, PHINode *Until = nullptr); 277 278 /// Split the edge connect the specficed blocks in the case that \p Succ is an 279 /// Exception Handling Block 280 BasicBlock *ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ, 281 LandingPadInst *OriginalPad = nullptr, 282 PHINode *LandingPadReplacement = nullptr, 283 const CriticalEdgeSplittingOptions &Options = 284 CriticalEdgeSplittingOptions(), 285 const Twine &BBName = ""); 286 287 /// Split the specified block at the specified instruction. 288 /// 289 /// If \p Before is true, splitBlockBefore handles the block 290 /// splitting. Otherwise, execution proceeds as described below. 291 /// 292 /// Everything before \p SplitPt stays in \p Old and everything starting with \p 293 /// SplitPt moves to a new block. The two blocks are joined by an unconditional 294 /// branch. The new block with name \p BBName is returned. 295 /// 296 /// FIXME: deprecated, switch to the DomTreeUpdater-based one. 297 BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, 298 LoopInfo *LI = nullptr, 299 MemorySSAUpdater *MSSAU = nullptr, 300 const Twine &BBName = "", bool Before = false); 301 302 /// Split the specified block at the specified instruction. 303 /// 304 /// If \p Before is true, splitBlockBefore handles the block 305 /// splitting. Otherwise, execution proceeds as described below. 306 /// 307 /// Everything before \p SplitPt stays in \p Old and everything starting with \p 308 /// SplitPt moves to a new block. The two blocks are joined by an unconditional 309 /// branch. The new block with name \p BBName is returned. 310 BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, 311 DomTreeUpdater *DTU = nullptr, LoopInfo *LI = nullptr, 312 MemorySSAUpdater *MSSAU = nullptr, 313 const Twine &BBName = "", bool Before = false); 314 315 /// Split the specified block at the specified instruction \p SplitPt. 316 /// All instructions before \p SplitPt are moved to a new block and all 317 /// instructions after \p SplitPt stay in the old block. The new block and the 318 /// old block are joined by inserting an unconditional branch to the end of the 319 /// new block. The new block with name \p BBName is returned. 320 BasicBlock *splitBlockBefore(BasicBlock *Old, Instruction *SplitPt, 321 DomTreeUpdater *DTU, LoopInfo *LI, 322 MemorySSAUpdater *MSSAU, const Twine &BBName = ""); 323 324 /// This method introduces at least one new basic block into the function and 325 /// moves some of the predecessors of BB to be predecessors of the new block. 326 /// The new predecessors are indicated by the Preds array. The new block is 327 /// given a suffix of 'Suffix'. Returns new basic block to which predecessors 328 /// from Preds are now pointing. 329 /// 330 /// If BB is a landingpad block then additional basicblock might be introduced. 331 /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more 332 /// details on this case. 333 /// 334 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but 335 /// no other analyses. In particular, it does not preserve LoopSimplify 336 /// (because it's complicated to handle the case where one of the edges being 337 /// split is an exit of a loop with other exits). 338 /// 339 /// FIXME: deprecated, switch to the DomTreeUpdater-based one. 340 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, 341 const char *Suffix, DominatorTree *DT, 342 LoopInfo *LI = nullptr, 343 MemorySSAUpdater *MSSAU = nullptr, 344 bool PreserveLCSSA = false); 345 346 /// This method introduces at least one new basic block into the function and 347 /// moves some of the predecessors of BB to be predecessors of the new block. 348 /// The new predecessors are indicated by the Preds array. The new block is 349 /// given a suffix of 'Suffix'. Returns new basic block to which predecessors 350 /// from Preds are now pointing. 351 /// 352 /// If BB is a landingpad block then additional basicblock might be introduced. 353 /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more 354 /// details on this case. 355 /// 356 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but 357 /// no other analyses. In particular, it does not preserve LoopSimplify 358 /// (because it's complicated to handle the case where one of the edges being 359 /// split is an exit of a loop with other exits). 360 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, 361 const char *Suffix, 362 DomTreeUpdater *DTU = nullptr, 363 LoopInfo *LI = nullptr, 364 MemorySSAUpdater *MSSAU = nullptr, 365 bool PreserveLCSSA = false); 366 367 /// This method transforms the landing pad, OrigBB, by introducing two new basic 368 /// blocks into the function. One of those new basic blocks gets the 369 /// predecessors listed in Preds. The other basic block gets the remaining 370 /// predecessors of OrigBB. The landingpad instruction OrigBB is clone into both 371 /// of the new basic blocks. The new blocks are given the suffixes 'Suffix1' and 372 /// 'Suffix2', and are returned in the NewBBs vector. 373 /// 374 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but 375 /// no other analyses. In particular, it does not preserve LoopSimplify 376 /// (because it's complicated to handle the case where one of the edges being 377 /// split is an exit of a loop with other exits). 378 /// 379 /// FIXME: deprecated, switch to the DomTreeUpdater-based one. 380 void SplitLandingPadPredecessors(BasicBlock *OrigBB, 381 ArrayRef<BasicBlock *> Preds, 382 const char *Suffix, const char *Suffix2, 383 SmallVectorImpl<BasicBlock *> &NewBBs, 384 DominatorTree *DT, LoopInfo *LI = nullptr, 385 MemorySSAUpdater *MSSAU = nullptr, 386 bool PreserveLCSSA = false); 387 388 /// This method transforms the landing pad, OrigBB, by introducing two new basic 389 /// blocks into the function. One of those new basic blocks gets the 390 /// predecessors listed in Preds. The other basic block gets the remaining 391 /// predecessors of OrigBB. The landingpad instruction OrigBB is clone into both 392 /// of the new basic blocks. The new blocks are given the suffixes 'Suffix1' and 393 /// 'Suffix2', and are returned in the NewBBs vector. 394 /// 395 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but 396 /// no other analyses. In particular, it does not preserve LoopSimplify 397 /// (because it's complicated to handle the case where one of the edges being 398 /// split is an exit of a loop with other exits). 399 void SplitLandingPadPredecessors( 400 BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix, 401 const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs, 402 DomTreeUpdater *DTU = nullptr, LoopInfo *LI = nullptr, 403 MemorySSAUpdater *MSSAU = nullptr, bool PreserveLCSSA = false); 404 405 /// This method duplicates the specified return instruction into a predecessor 406 /// which ends in an unconditional branch. If the return instruction returns a 407 /// value defined by a PHI, propagate the right value into the return. It 408 /// returns the new return instruction in the predecessor. 409 ReturnInst *FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, 410 BasicBlock *Pred, 411 DomTreeUpdater *DTU = nullptr); 412 413 /// Split the containing block at the specified instruction - everything before 414 /// SplitBefore stays in the old basic block, and the rest of the instructions 415 /// in the BB are moved to a new block. The two blocks are connected by a 416 /// conditional branch (with value of Cmp being the condition). 417 /// Before: 418 /// Head 419 /// SplitBefore 420 /// Tail 421 /// After: 422 /// Head 423 /// if (Cond) 424 /// ThenBlock 425 /// SplitBefore 426 /// Tail 427 /// 428 /// If \p ThenBlock is not specified, a new block will be created for it. 429 /// If \p Unreachable is true, the newly created block will end with 430 /// UnreachableInst, otherwise it branches to Tail. 431 /// Returns the NewBasicBlock's terminator. 432 /// 433 /// Updates DT and LI if given. 434 /// 435 /// FIXME: deprecated, switch to the DomTreeUpdater-based one. 436 Instruction *SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, 437 bool Unreachable, MDNode *BranchWeights, 438 DominatorTree *DT, 439 LoopInfo *LI = nullptr, 440 BasicBlock *ThenBlock = nullptr); 441 442 /// Split the containing block at the specified instruction - everything before 443 /// SplitBefore stays in the old basic block, and the rest of the instructions 444 /// in the BB are moved to a new block. The two blocks are connected by a 445 /// conditional branch (with value of Cmp being the condition). 446 /// Before: 447 /// Head 448 /// SplitBefore 449 /// Tail 450 /// After: 451 /// Head 452 /// if (Cond) 453 /// ThenBlock 454 /// SplitBefore 455 /// Tail 456 /// 457 /// If \p ThenBlock is not specified, a new block will be created for it. 458 /// If \p Unreachable is true, the newly created block will end with 459 /// UnreachableInst, otherwise it branches to Tail. 460 /// Returns the NewBasicBlock's terminator. 461 /// 462 /// Updates DT and LI if given. 463 Instruction *SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, 464 bool Unreachable, 465 MDNode *BranchWeights = nullptr, 466 DomTreeUpdater *DTU = nullptr, 467 LoopInfo *LI = nullptr, 468 BasicBlock *ThenBlock = nullptr); 469 470 /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, 471 /// but also creates the ElseBlock. 472 /// Before: 473 /// Head 474 /// SplitBefore 475 /// Tail 476 /// After: 477 /// Head 478 /// if (Cond) 479 /// ThenBlock 480 /// else 481 /// ElseBlock 482 /// SplitBefore 483 /// Tail 484 void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, 485 Instruction **ThenTerm, 486 Instruction **ElseTerm, 487 MDNode *BranchWeights = nullptr); 488 489 /// Check whether BB is the merge point of a if-region. 490 /// If so, return the boolean condition that determines which entry into 491 /// BB will be taken. Also, return by references the block that will be 492 /// entered from if the condition is true, and the block that will be 493 /// entered if the condition is false. 494 /// 495 /// This does no checking to see if the true/false blocks have large or unsavory 496 /// instructions in them. 497 Value *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, 498 BasicBlock *&IfFalse); 499 500 // Split critical edges where the source of the edge is an indirectbr 501 // instruction. This isn't always possible, but we can handle some easy cases. 502 // This is useful because MI is unable to split such critical edges, 503 // which means it will not be able to sink instructions along those edges. 504 // This is especially painful for indirect branches with many successors, where 505 // we end up having to prepare all outgoing values in the origin block. 506 // 507 // Our normal algorithm for splitting critical edges requires us to update 508 // the outgoing edges of the edge origin block, but for an indirectbr this 509 // is hard, since it would require finding and updating the block addresses 510 // the indirect branch uses. But if a block only has a single indirectbr 511 // predecessor, with the others being regular branches, we can do it in a 512 // different way. 513 // Say we have A -> D, B -> D, I -> D where only I -> D is an indirectbr. 514 // We can split D into D0 and D1, where D0 contains only the PHIs from D, 515 // and D1 is the D block body. We can then duplicate D0 as D0A and D0B, and 516 // create the following structure: 517 // A -> D0A, B -> D0A, I -> D0B, D0A -> D1, D0B -> D1 518 // If BPI and BFI aren't non-null, BPI/BFI will be updated accordingly. 519 bool SplitIndirectBrCriticalEdges(Function &F, 520 BranchProbabilityInfo *BPI = nullptr, 521 BlockFrequencyInfo *BFI = nullptr); 522 523 /// Given a set of incoming and outgoing blocks, create a "hub" such that every 524 /// edge from an incoming block InBB to an outgoing block OutBB is now split 525 /// into two edges, one from InBB to the hub and another from the hub to 526 /// OutBB. The hub consists of a series of guard blocks, one for each outgoing 527 /// block. Each guard block conditionally branches to the corresponding outgoing 528 /// block, or the next guard block in the chain. These guard blocks are returned 529 /// in the argument vector. 530 /// 531 /// Since the control flow edges from InBB to OutBB have now been replaced, the 532 /// function also updates any PHINodes in OutBB. For each such PHINode, the 533 /// operands corresponding to incoming blocks are moved to a new PHINode in the 534 /// hub, and the hub is made an operand of the original PHINode. 535 /// 536 /// Input CFG: 537 /// ---------- 538 /// 539 /// Def 540 /// | 541 /// v 542 /// In1 In2 543 /// | | 544 /// | | 545 /// v v 546 /// Foo ---> Out1 Out2 547 /// | 548 /// v 549 /// Use 550 /// 551 /// 552 /// Create hub: Incoming = {In1, In2}, Outgoing = {Out1, Out2} 553 /// ---------------------------------------------------------- 554 /// 555 /// Def 556 /// | 557 /// v 558 /// In1 In2 Foo 559 /// | Hub | | 560 /// | + - - | - - + | 561 /// | ' v ' V 562 /// +------> Guard1 -----> Out1 563 /// ' | ' 564 /// ' v ' 565 /// ' Guard2 -----> Out2 566 /// ' ' | 567 /// + - - - - - + | 568 /// v 569 /// Use 570 /// 571 /// Limitations: 572 /// ----------- 573 /// 1. This assumes that all terminators in the CFG are direct branches (the 574 /// "br" instruction). The presence of any other control flow such as 575 /// indirectbr, switch or callbr will cause an assert. 576 /// 577 /// 2. The updates to the PHINodes are not sufficient to restore SSA 578 /// form. Consider a definition Def, its use Use, incoming block In2 and 579 /// outgoing block Out2, such that: 580 /// a. In2 is reachable from D or contains D. 581 /// b. U is reachable from Out2 or is contained in Out2. 582 /// c. U is not a PHINode if U is contained in Out2. 583 /// 584 /// Clearly, Def dominates Out2 since the program is valid SSA. But when the 585 /// hub is introduced, there is a new path through the hub along which Use is 586 /// reachable from entry without passing through Def, and SSA is no longer 587 /// valid. To fix this, we need to look at all the blocks post-dominated by 588 /// the hub on the one hand, and dominated by Out2 on the other. This is left 589 /// for the caller to accomplish, since each specific use of this function 590 /// may have additional information which simplifies this fixup. For example, 591 /// see restoreSSA() in the UnifyLoopExits pass. 592 BasicBlock *CreateControlFlowHub(DomTreeUpdater *DTU, 593 SmallVectorImpl<BasicBlock *> &GuardBlocks, 594 const SetVector<BasicBlock *> &Predecessors, 595 const SetVector<BasicBlock *> &Successors, 596 const StringRef Prefix); 597 598 } // end namespace llvm 599 600 #endif // LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H 601
Indexes created Tue Feb 24 08:35:24 UTC 2026