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