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 IRBuilderBase; 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 detachDeadBlocks(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 /// If \p DT is not nullptr, update it directly; in that case, DTU must be 95 /// nullptr. 96 bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU = nullptr, 97 LoopInfo *LI = nullptr, 98 MemorySSAUpdater *MSSAU = nullptr, 99 MemoryDependenceResults *MemDep = nullptr, 100 bool PredecessorWithTwoSuccessors = false, 101 DominatorTree *DT = nullptr); 102 103 /// Merge block(s) sucessors, if possible. Return true if at least two 104 /// of the blocks were merged together. 105 /// In order to merge, each block must be terminated by an unconditional 106 /// branch. If L is provided, then the blocks merged into their predecessors 107 /// must be in L. In addition, This utility calls on another utility: 108 /// MergeBlockIntoPredecessor. Blocks are successfully merged when the call to 109 /// MergeBlockIntoPredecessor returns true. 110 bool MergeBlockSuccessorsIntoGivenBlocks( 111 SmallPtrSetImpl<BasicBlock *> &MergeBlocks, Loop *L = nullptr, 112 DomTreeUpdater *DTU = nullptr, LoopInfo *LI = nullptr); 113 114 /// Try to remove redundant dbg.value instructions from given basic block. 115 /// Returns true if at least one instruction was removed. Remove redundant 116 /// pseudo ops when RemovePseudoOp is true. 117 bool RemoveRedundantDbgInstrs(BasicBlock *BB); 118 119 /// Replace all uses of an instruction (specified by BI) with a value, then 120 /// remove and delete the original instruction. 121 void ReplaceInstWithValue(BasicBlock::iterator &BI, Value *V); 122 123 /// Replace the instruction specified by BI with the instruction specified by I. 124 /// Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. The 125 /// original instruction is deleted and BI is updated to point to the new 126 /// instruction. 127 void ReplaceInstWithInst(BasicBlock *BB, BasicBlock::iterator &BI, 128 Instruction *I); 129 130 /// Replace the instruction specified by From with the instruction specified by 131 /// To. Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. 132 void ReplaceInstWithInst(Instruction *From, Instruction *To); 133 134 /// Check if we can prove that all paths starting from this block converge 135 /// to a block that either has a @llvm.experimental.deoptimize call 136 /// prior to its terminating return instruction or is terminated by unreachable. 137 /// All blocks in the traversed sequence must have an unique successor, maybe 138 /// except for the last one. 139 bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB); 140 141 /// Option class for critical edge splitting. 142 /// 143 /// This provides a builder interface for overriding the default options used 144 /// during critical edge splitting. 145 struct CriticalEdgeSplittingOptions { 146 DominatorTree *DT; 147 PostDominatorTree *PDT; 148 LoopInfo *LI; 149 MemorySSAUpdater *MSSAU; 150 bool MergeIdenticalEdges = false; 151 bool KeepOneInputPHIs = false; 152 bool PreserveLCSSA = false; 153 bool IgnoreUnreachableDests = false; 154 /// SplitCriticalEdge is guaranteed to preserve loop-simplify form if LI is 155 /// provided. If it cannot be preserved, no splitting will take place. If it 156 /// is not set, preserve loop-simplify form if possible. 157 bool PreserveLoopSimplify = true; 158 159 CriticalEdgeSplittingOptions(DominatorTree *DT = nullptr, 160 LoopInfo *LI = nullptr, 161 MemorySSAUpdater *MSSAU = nullptr, 162 PostDominatorTree *PDT = nullptr) 163 : DT(DT), PDT(PDT), LI(LI), MSSAU(MSSAU) {} 164 165 CriticalEdgeSplittingOptions &setMergeIdenticalEdges() { 166 MergeIdenticalEdges = true; 167 return *this; 168 } 169 170 CriticalEdgeSplittingOptions &setKeepOneInputPHIs() { 171 KeepOneInputPHIs = true; 172 return *this; 173 } 174 175 CriticalEdgeSplittingOptions &setPreserveLCSSA() { 176 PreserveLCSSA = true; 177 return *this; 178 } 179 180 CriticalEdgeSplittingOptions &setIgnoreUnreachableDests() { 181 IgnoreUnreachableDests = true; 182 return *this; 183 } 184 185 CriticalEdgeSplittingOptions &unsetPreserveLoopSimplify() { 186 PreserveLoopSimplify = false; 187 return *this; 188 } 189 }; 190 191 /// When a loop exit edge is split, LCSSA form may require new PHIs in the new 192 /// exit block. This function inserts the new PHIs, as needed. Preds is a list 193 /// of preds inside the loop, SplitBB is the new loop exit block, and DestBB is 194 /// the old loop exit, now the successor of SplitBB. 195 void createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds, 196 BasicBlock *SplitBB, BasicBlock *DestBB); 197 198 /// If this edge is a critical edge, insert a new node to split the critical 199 /// edge. This will update the analyses passed in through the option struct. 200 /// This returns the new block if the edge was split, null otherwise. 201 /// 202 /// If MergeIdenticalEdges in the options struct is true (not the default), 203 /// *all* edges from TI to the specified successor will be merged into the same 204 /// critical edge block. This is most commonly interesting with switch 205 /// instructions, which may have many edges to any one destination. This 206 /// ensures that all edges to that dest go to one block instead of each going 207 /// to a different block, but isn't the standard definition of a "critical 208 /// edge". 209 /// 210 /// It is invalid to call this function on a critical edge that starts at an 211 /// IndirectBrInst. Splitting these edges will almost always create an invalid 212 /// program because the address of the new block won't be the one that is jumped 213 /// to. 214 BasicBlock *SplitCriticalEdge(Instruction *TI, unsigned SuccNum, 215 const CriticalEdgeSplittingOptions &Options = 216 CriticalEdgeSplittingOptions(), 217 const Twine &BBName = ""); 218 219 /// If it is known that an edge is critical, SplitKnownCriticalEdge can be 220 /// called directly, rather than calling SplitCriticalEdge first. 221 BasicBlock *SplitKnownCriticalEdge(Instruction *TI, unsigned SuccNum, 222 const CriticalEdgeSplittingOptions &Options = 223 CriticalEdgeSplittingOptions(), 224 const Twine &BBName = ""); 225 226 /// If an edge from Src to Dst is critical, split the edge and return true, 227 /// otherwise return false. This method requires that there be an edge between 228 /// the two blocks. It updates the analyses passed in the options struct 229 inline BasicBlock * 230 SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst, 231 const CriticalEdgeSplittingOptions &Options = 232 CriticalEdgeSplittingOptions()) { 233 Instruction *TI = Src->getTerminator(); 234 unsigned i = 0; 235 while (true) { 236 assert(i != TI->getNumSuccessors() && "Edge doesn't exist!"); 237 if (TI->getSuccessor(i) == Dst) 238 return SplitCriticalEdge(TI, i, Options); 239 ++i; 240 } 241 } 242 243 /// Loop over all of the edges in the CFG, breaking critical edges as they are 244 /// found. Returns the number of broken edges. 245 unsigned SplitAllCriticalEdges(Function &F, 246 const CriticalEdgeSplittingOptions &Options = 247 CriticalEdgeSplittingOptions()); 248 249 /// Split the edge connecting the specified blocks, and return the newly created 250 /// basic block between \p From and \p To. 251 BasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To, 252 DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, 253 MemorySSAUpdater *MSSAU = nullptr, 254 const Twine &BBName = ""); 255 256 /// Sets the unwind edge of an instruction to a particular successor. 257 void setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ); 258 259 /// Replaces all uses of OldPred with the NewPred block in all PHINodes in a 260 /// block. 261 void updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred, 262 BasicBlock *NewPred, PHINode *Until = nullptr); 263 264 /// Split the edge connect the specficed blocks in the case that \p Succ is an 265 /// Exception Handling Block 266 BasicBlock *ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ, 267 LandingPadInst *OriginalPad = nullptr, 268 PHINode *LandingPadReplacement = nullptr, 269 const CriticalEdgeSplittingOptions &Options = 270 CriticalEdgeSplittingOptions(), 271 const Twine &BBName = ""); 272 273 /// Split the specified block at the specified instruction. 274 /// 275 /// If \p Before is true, splitBlockBefore handles the block 276 /// splitting. Otherwise, execution proceeds as described below. 277 /// 278 /// Everything before \p SplitPt stays in \p Old and everything starting with \p 279 /// SplitPt moves to a new block. The two blocks are joined by an unconditional 280 /// branch. The new block with name \p BBName is returned. 281 /// 282 /// FIXME: deprecated, switch to the DomTreeUpdater-based one. 283 BasicBlock *SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, 284 LoopInfo *LI = nullptr, 285 MemorySSAUpdater *MSSAU = nullptr, 286 const Twine &BBName = "", bool Before = false); 287 inline BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, 288 LoopInfo *LI = nullptr, 289 MemorySSAUpdater *MSSAU = nullptr, 290 const Twine &BBName = "", bool Before = false) { 291 return SplitBlock(Old, SplitPt->getIterator(), DT, LI, MSSAU, BBName, Before); 292 } 293 294 /// Split the specified block at the specified instruction. 295 /// 296 /// If \p Before is true, splitBlockBefore handles the block 297 /// splitting. Otherwise, execution proceeds as described below. 298 /// 299 /// Everything before \p SplitPt stays in \p Old and everything starting with \p 300 /// SplitPt moves to a new block. The two blocks are joined by an unconditional 301 /// branch. The new block with name \p BBName is returned. 302 BasicBlock *SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, 303 DomTreeUpdater *DTU = nullptr, LoopInfo *LI = nullptr, 304 MemorySSAUpdater *MSSAU = nullptr, 305 const Twine &BBName = "", bool Before = false); 306 inline BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, 307 DomTreeUpdater *DTU = nullptr, LoopInfo *LI = nullptr, 308 MemorySSAUpdater *MSSAU = nullptr, 309 const Twine &BBName = "", bool Before = false) { 310 return SplitBlock(Old, SplitPt->getIterator(), DTU, LI, MSSAU, BBName, Before); 311 } 312 313 /// Split the specified block at the specified instruction \p SplitPt. 314 /// All instructions before \p SplitPt are moved to a new block and all 315 /// instructions after \p SplitPt stay in the old block. The new block and the 316 /// old block are joined by inserting an unconditional branch to the end of the 317 /// new block. The new block with name \p BBName is returned. 318 BasicBlock *splitBlockBefore(BasicBlock *Old, BasicBlock::iterator SplitPt, 319 DomTreeUpdater *DTU, LoopInfo *LI, 320 MemorySSAUpdater *MSSAU, const Twine &BBName = ""); 321 inline BasicBlock *splitBlockBefore(BasicBlock *Old, Instruction *SplitPt, 322 DomTreeUpdater *DTU, LoopInfo *LI, 323 MemorySSAUpdater *MSSAU, const Twine &BBName = "") { 324 return splitBlockBefore(Old, SplitPt->getIterator(), DTU, LI, MSSAU, BBName); 325 } 326 327 /// This method introduces at least one new basic block into the function and 328 /// moves some of the predecessors of BB to be predecessors of the new block. 329 /// The new predecessors are indicated by the Preds array. The new block is 330 /// given a suffix of 'Suffix'. Returns new basic block to which predecessors 331 /// from Preds are now pointing. 332 /// 333 /// If BB is a landingpad block then additional basicblock might be introduced. 334 /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more 335 /// details on this case. 336 /// 337 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but 338 /// no other analyses. In particular, it does not preserve LoopSimplify 339 /// (because it's complicated to handle the case where one of the edges being 340 /// split is an exit of a loop with other exits). 341 /// 342 /// FIXME: deprecated, switch to the DomTreeUpdater-based one. 343 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, 344 const char *Suffix, DominatorTree *DT, 345 LoopInfo *LI = nullptr, 346 MemorySSAUpdater *MSSAU = nullptr, 347 bool PreserveLCSSA = false); 348 349 /// This method introduces at least one new basic block into the function and 350 /// moves some of the predecessors of BB to be predecessors of the new block. 351 /// The new predecessors are indicated by the Preds array. The new block is 352 /// given a suffix of 'Suffix'. Returns new basic block to which predecessors 353 /// from Preds are now pointing. 354 /// 355 /// If BB is a landingpad block then additional basicblock might be introduced. 356 /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more 357 /// details on this case. 358 /// 359 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but 360 /// no other analyses. In particular, it does not preserve LoopSimplify 361 /// (because it's complicated to handle the case where one of the edges being 362 /// split is an exit of a loop with other exits). 363 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, 364 const char *Suffix, 365 DomTreeUpdater *DTU = nullptr, 366 LoopInfo *LI = nullptr, 367 MemorySSAUpdater *MSSAU = nullptr, 368 bool PreserveLCSSA = false); 369 370 /// This method transforms the landing pad, OrigBB, by introducing two new basic 371 /// blocks into the function. One of those new basic blocks gets the 372 /// predecessors listed in Preds. The other basic block gets the remaining 373 /// predecessors of OrigBB. The landingpad instruction OrigBB is clone into both 374 /// of the new basic blocks. The new blocks are given the suffixes 'Suffix1' and 375 /// 'Suffix2', and are returned in the NewBBs vector. 376 /// 377 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but 378 /// no other analyses. In particular, it does not preserve LoopSimplify 379 /// (because it's complicated to handle the case where one of the edges being 380 /// split is an exit of a loop with other exits). 381 void SplitLandingPadPredecessors( 382 BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix, 383 const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs, 384 DomTreeUpdater *DTU = nullptr, LoopInfo *LI = nullptr, 385 MemorySSAUpdater *MSSAU = nullptr, bool PreserveLCSSA = false); 386 387 /// This method duplicates the specified return instruction into a predecessor 388 /// which ends in an unconditional branch. If the return instruction returns a 389 /// value defined by a PHI, propagate the right value into the return. It 390 /// returns the new return instruction in the predecessor. 391 ReturnInst *FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, 392 BasicBlock *Pred, 393 DomTreeUpdater *DTU = nullptr); 394 395 /// Split the containing block at the specified instruction - everything before 396 /// SplitBefore stays in the old basic block, and the rest of the instructions 397 /// in the BB are moved to a new block. The two blocks are connected by a 398 /// conditional branch (with value of Cmp being the condition). 399 /// Before: 400 /// Head 401 /// SplitBefore 402 /// Tail 403 /// After: 404 /// Head 405 /// if (Cond) 406 /// ThenBlock 407 /// SplitBefore 408 /// Tail 409 /// 410 /// If \p ThenBlock is not specified, a new block will be created for it. 411 /// If \p Unreachable is true, the newly created block will end with 412 /// UnreachableInst, otherwise it branches to Tail. 413 /// Returns the NewBasicBlock's terminator. 414 /// 415 /// Updates DTU and LI if given. 416 Instruction *SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, 417 bool Unreachable, 418 MDNode *BranchWeights = nullptr, 419 DomTreeUpdater *DTU = nullptr, 420 LoopInfo *LI = nullptr, 421 BasicBlock *ThenBlock = nullptr); 422 423 inline Instruction *SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, 424 bool Unreachable, 425 MDNode *BranchWeights = nullptr, 426 DomTreeUpdater *DTU = nullptr, 427 LoopInfo *LI = nullptr, 428 BasicBlock *ThenBlock = nullptr) { 429 return SplitBlockAndInsertIfThen(Cond, SplitBefore->getIterator(), 430 Unreachable, BranchWeights, DTU, LI, 431 ThenBlock); 432 } 433 434 /// Similar to SplitBlockAndInsertIfThen, but the inserted block is on the false 435 /// path of the branch. 436 Instruction *SplitBlockAndInsertIfElse(Value *Cond, BasicBlock::iterator SplitBefore, 437 bool Unreachable, 438 MDNode *BranchWeights = nullptr, 439 DomTreeUpdater *DTU = nullptr, 440 LoopInfo *LI = nullptr, 441 BasicBlock *ElseBlock = nullptr); 442 443 inline Instruction *SplitBlockAndInsertIfElse(Value *Cond, Instruction *SplitBefore, 444 bool Unreachable, 445 MDNode *BranchWeights = nullptr, 446 DomTreeUpdater *DTU = nullptr, 447 LoopInfo *LI = nullptr, 448 BasicBlock *ElseBlock = nullptr) { 449 return SplitBlockAndInsertIfElse(Cond, SplitBefore->getIterator(), 450 Unreachable, BranchWeights, DTU, LI, 451 ElseBlock); 452 } 453 454 /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, 455 /// but also creates the ElseBlock. 456 /// Before: 457 /// Head 458 /// SplitBefore 459 /// Tail 460 /// After: 461 /// Head 462 /// if (Cond) 463 /// ThenBlock 464 /// else 465 /// ElseBlock 466 /// SplitBefore 467 /// Tail 468 /// 469 /// Updates DT if given. 470 void SplitBlockAndInsertIfThenElse(Value *Cond, 471 BasicBlock::iterator SplitBefore, 472 Instruction **ThenTerm, 473 Instruction **ElseTerm, 474 MDNode *BranchWeights = nullptr, 475 DomTreeUpdater *DTU = nullptr, 476 LoopInfo *LI = nullptr); 477 478 inline void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, 479 Instruction **ThenTerm, 480 Instruction **ElseTerm, 481 MDNode *BranchWeights = nullptr, 482 DomTreeUpdater *DTU = nullptr, 483 LoopInfo *LI = nullptr) 484 { 485 SplitBlockAndInsertIfThenElse(Cond, SplitBefore->getIterator(), ThenTerm, 486 ElseTerm, BranchWeights, DTU, LI); 487 } 488 489 /// Split the containing block at the specified instruction - everything before 490 /// SplitBefore stays in the old basic block, and the rest of the instructions 491 /// in the BB are moved to a new block. The two blocks are connected by a 492 /// conditional branch (with value of Cmp being the condition). 493 /// Before: 494 /// Head 495 /// SplitBefore 496 /// Tail 497 /// After: 498 /// Head 499 /// if (Cond) 500 /// TrueBlock 501 /// else 502 //// FalseBlock 503 /// SplitBefore 504 /// Tail 505 /// 506 /// If \p ThenBlock is null, the resulting CFG won't contain the TrueBlock. If 507 /// \p ThenBlock is non-null and points to non-null BasicBlock pointer, that 508 /// block will be inserted as the TrueBlock. Otherwise a new block will be 509 /// created. Likewise for the \p ElseBlock parameter. 510 /// If \p UnreachableThen or \p UnreachableElse is true, the corresponding newly 511 /// created blocks will end with UnreachableInst, otherwise with branches to 512 /// Tail. The function will not modify existing basic blocks passed to it. The 513 /// caller must ensure that Tail is reachable from Head. 514 /// Returns the newly created blocks in \p ThenBlock and \p ElseBlock. 515 /// Updates DTU and LI if given. 516 void SplitBlockAndInsertIfThenElse(Value *Cond, 517 BasicBlock::iterator SplitBefore, 518 BasicBlock **ThenBlock, 519 BasicBlock **ElseBlock, 520 bool UnreachableThen = false, 521 bool UnreachableElse = false, 522 MDNode *BranchWeights = nullptr, 523 DomTreeUpdater *DTU = nullptr, 524 LoopInfo *LI = nullptr); 525 526 inline void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, 527 BasicBlock **ThenBlock, 528 BasicBlock **ElseBlock, 529 bool UnreachableThen = false, 530 bool UnreachableElse = false, 531 MDNode *BranchWeights = nullptr, 532 DomTreeUpdater *DTU = nullptr, 533 LoopInfo *LI = nullptr) { 534 SplitBlockAndInsertIfThenElse(Cond, SplitBefore->getIterator(), ThenBlock, 535 ElseBlock, UnreachableThen, UnreachableElse, BranchWeights, DTU, LI); 536 } 537 538 /// Insert a for (int i = 0; i < End; i++) loop structure (with the exception 539 /// that \p End is assumed > 0, and thus not checked on entry) at \p 540 /// SplitBefore. Returns the first insert point in the loop body, and the 541 /// PHINode for the induction variable (i.e. "i" above). 542 std::pair<Instruction*, Value*> 543 SplitBlockAndInsertSimpleForLoop(Value *End, Instruction *SplitBefore); 544 545 /// Utility function for performing a given action on each lane of a vector 546 /// with \p EC elements. To simplify porting legacy code, this defaults to 547 /// unrolling the implied loop for non-scalable element counts, but this is 548 /// not considered to be part of the contract of this routine, and is 549 /// expected to change in the future. The callback takes as arguments an 550 /// IRBuilder whose insert point is correctly set for instantiating the 551 /// given index, and a value which is (at runtime) the index to access. 552 /// This index *may* be a constant. 553 void SplitBlockAndInsertForEachLane(ElementCount EC, Type *IndexTy, 554 Instruction *InsertBefore, 555 std::function<void(IRBuilderBase&, Value*)> Func); 556 557 /// Utility function for performing a given action on each lane of a vector 558 /// with \p EVL effective length. EVL is assumed > 0. To simplify porting legacy 559 /// code, this defaults to unrolling the implied loop for non-scalable element 560 /// counts, but this is not considered to be part of the contract of this 561 /// routine, and is expected to change in the future. The callback takes as 562 /// arguments an IRBuilder whose insert point is correctly set for instantiating 563 /// the given index, and a value which is (at runtime) the index to access. This 564 /// index *may* be a constant. 565 void SplitBlockAndInsertForEachLane( 566 Value *End, Instruction *InsertBefore, 567 std::function<void(IRBuilderBase &, Value *)> Func); 568 569 /// Check whether BB is the merge point of a if-region. 570 /// If so, return the branch instruction that determines which entry into 571 /// BB will be taken. Also, return by references the block that will be 572 /// entered from if the condition is true, and the block that will be 573 /// entered if the condition is false. 574 /// 575 /// This does no checking to see if the true/false blocks have large or unsavory 576 /// instructions in them. 577 BranchInst *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, 578 BasicBlock *&IfFalse); 579 580 // Split critical edges where the source of the edge is an indirectbr 581 // instruction. This isn't always possible, but we can handle some easy cases. 582 // This is useful because MI is unable to split such critical edges, 583 // which means it will not be able to sink instructions along those edges. 584 // This is especially painful for indirect branches with many successors, where 585 // we end up having to prepare all outgoing values in the origin block. 586 // 587 // Our normal algorithm for splitting critical edges requires us to update 588 // the outgoing edges of the edge origin block, but for an indirectbr this 589 // is hard, since it would require finding and updating the block addresses 590 // the indirect branch uses. But if a block only has a single indirectbr 591 // predecessor, with the others being regular branches, we can do it in a 592 // different way. 593 // Say we have A -> D, B -> D, I -> D where only I -> D is an indirectbr. 594 // We can split D into D0 and D1, where D0 contains only the PHIs from D, 595 // and D1 is the D block body. We can then duplicate D0 as D0A and D0B, and 596 // create the following structure: 597 // A -> D0A, B -> D0A, I -> D0B, D0A -> D1, D0B -> D1 598 // If BPI and BFI aren't non-null, BPI/BFI will be updated accordingly. 599 // When `IgnoreBlocksWithoutPHI` is set to `true` critical edges leading to a 600 // block without phi-instructions will not be split. 601 bool SplitIndirectBrCriticalEdges(Function &F, bool IgnoreBlocksWithoutPHI, 602 BranchProbabilityInfo *BPI = nullptr, 603 BlockFrequencyInfo *BFI = nullptr); 604 605 /// Given a set of incoming and outgoing blocks, create a "hub" such that every 606 /// edge from an incoming block InBB to an outgoing block OutBB is now split 607 /// into two edges, one from InBB to the hub and another from the hub to 608 /// OutBB. The hub consists of a series of guard blocks, one for each outgoing 609 /// block. Each guard block conditionally branches to the corresponding outgoing 610 /// block, or the next guard block in the chain. These guard blocks are returned 611 /// in the argument vector. 612 /// 613 /// Since the control flow edges from InBB to OutBB have now been replaced, the 614 /// function also updates any PHINodes in OutBB. For each such PHINode, the 615 /// operands corresponding to incoming blocks are moved to a new PHINode in the 616 /// hub, and the hub is made an operand of the original PHINode. 617 /// 618 /// Input CFG: 619 /// ---------- 620 /// 621 /// Def 622 /// | 623 /// v 624 /// In1 In2 625 /// | | 626 /// | | 627 /// v v 628 /// Foo ---> Out1 Out2 629 /// | 630 /// v 631 /// Use 632 /// 633 /// 634 /// Create hub: Incoming = {In1, In2}, Outgoing = {Out1, Out2} 635 /// ---------------------------------------------------------- 636 /// 637 /// Def 638 /// | 639 /// v 640 /// In1 In2 Foo 641 /// | Hub | | 642 /// | + - - | - - + | 643 /// | ' v ' V 644 /// +------> Guard1 -----> Out1 645 /// ' | ' 646 /// ' v ' 647 /// ' Guard2 -----> Out2 648 /// ' ' | 649 /// + - - - - - + | 650 /// v 651 /// Use 652 /// 653 /// Limitations: 654 /// ----------- 655 /// 1. This assumes that all terminators in the CFG are direct branches (the 656 /// "br" instruction). The presence of any other control flow such as 657 /// indirectbr, switch or callbr will cause an assert. 658 /// 659 /// 2. The updates to the PHINodes are not sufficient to restore SSA 660 /// form. Consider a definition Def, its use Use, incoming block In2 and 661 /// outgoing block Out2, such that: 662 /// a. In2 is reachable from D or contains D. 663 /// b. U is reachable from Out2 or is contained in Out2. 664 /// c. U is not a PHINode if U is contained in Out2. 665 /// 666 /// Clearly, Def dominates Out2 since the program is valid SSA. But when the 667 /// hub is introduced, there is a new path through the hub along which Use is 668 /// reachable from entry without passing through Def, and SSA is no longer 669 /// valid. To fix this, we need to look at all the blocks post-dominated by 670 /// the hub on the one hand, and dominated by Out2 on the other. This is left 671 /// for the caller to accomplish, since each specific use of this function 672 /// may have additional information which simplifies this fixup. For example, 673 /// see restoreSSA() in the UnifyLoopExits pass. 674 BasicBlock *CreateControlFlowHub( 675 DomTreeUpdater *DTU, SmallVectorImpl<BasicBlock *> &GuardBlocks, 676 const SetVector<BasicBlock *> &Predecessors, 677 const SetVector<BasicBlock *> &Successors, const StringRef Prefix, 678 std::optional<unsigned> MaxControlFlowBooleans = std::nullopt); 679 680 // Utility function for inverting branch condition and for swapping its 681 // successors 682 void InvertBranch(BranchInst *PBI, IRBuilderBase &Builder); 683 684 // Check whether the function only has simple terminator: 685 // br/brcond/unreachable/ret 686 bool hasOnlySimpleTerminator(const Function &F); 687 688 // Returns true if these basic blocks belong to a presplit coroutine and the 689 // edge corresponds to the 'default' case in the switch statement in the 690 // pattern: 691 // 692 // %0 = call i8 @llvm.coro.suspend(token none, i1 false) 693 // switch i8 %0, label %suspend [i8 0, label %resume 694 // i8 1, label %cleanup] 695 // 696 // i.e. the edge to the `%suspend` BB. This edge is special in that it will 697 // be elided by coroutine lowering (coro-split), and the `%suspend` BB needs 698 // to be kept as-is. It's not a real CFG edge - post-lowering, it will end 699 // up being a `ret`, and it must be thus lowerable to support symmetric 700 // transfer. For example: 701 // - this edge is not a loop exit edge if encountered in a loop (and should 702 // be ignored) 703 // - must not be split for PGO instrumentation, for example. 704 bool isPresplitCoroSuspendExitEdge(const BasicBlock &Src, 705 const BasicBlock &Dest); 706 } // end namespace llvm 707 708 #endif // LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H 709