1327952Sdim//===- Transform/Utils/BasicBlockUtils.h - BasicBlock Utils -----*- C++ -*-===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9193323Sed// This family of functions perform manipulations on basic blocks, and 10193323Sed// instructions contained within basic blocks. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14249423Sdim#ifndef LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H 15249423Sdim#define LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H 16193323Sed 17193323Sed// FIXME: Move to this file: BasicBlock::removePredecessor, BB::splitBasicBlock 18193323Sed 19314564Sdim#include "llvm/ADT/ArrayRef.h" 20353358Sdim#include "llvm/Analysis/DomTreeUpdater.h" 21249423Sdim#include "llvm/IR/BasicBlock.h" 22276479Sdim#include "llvm/IR/CFG.h" 23314564Sdim#include "llvm/IR/InstrTypes.h" 24314564Sdim#include <cassert> 25193323Sed 26193323Sednamespace llvm { 27193323Sed 28327952Sdimclass BlockFrequencyInfo; 29327952Sdimclass BranchProbabilityInfo; 30276479Sdimclass DominatorTree; 31344779Sdimclass DomTreeUpdater; 32327952Sdimclass Function; 33327952Sdimclass Instruction; 34288943Sdimclass LoopInfo; 35243830Sdimclass MDNode; 36327952Sdimclass MemoryDependenceResults; 37344779Sdimclass MemorySSAUpdater; 38353358Sdimclass PostDominatorTree; 39218893Sdimclass ReturnInst; 40243830Sdimclass TargetLibraryInfo; 41327952Sdimclass Value; 42193323Sed 43353358Sdim/// Replace contents of every block in \p BBs with single unreachable 44353358Sdim/// instruction. If \p Updates is specified, collect all necessary DT updates 45353358Sdim/// into this vector. If \p KeepOneInputPHIs is true, one-input Phis in 46353358Sdim/// successors of blocks being deleted will be preserved. 47353358Sdimvoid DetatchDeadBlocks(ArrayRef <BasicBlock *> BBs, 48353358Sdim SmallVectorImpl<DominatorTree::UpdateType> *Updates, 49353358Sdim bool KeepOneInputPHIs = false); 50353358Sdim 51309124Sdim/// Delete the specified block, which must have no predecessors. 52353358Sdimvoid DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU = nullptr, 53353358Sdim bool KeepOneInputPHIs = false); 54226633Sdim 55344779Sdim/// Delete the specified blocks from \p BB. The set of deleted blocks must have 56344779Sdim/// no predecessors that are not being deleted themselves. \p BBs must have no 57344779Sdim/// duplicating blocks. If there are loops among this set of blocks, all 58344779Sdim/// relevant loop info updates should be done before this function is called. 59353358Sdim/// If \p KeepOneInputPHIs is true, one-input Phis in successors of blocks 60353358Sdim/// being deleted will be preserved. 61353358Sdimvoid DeleteDeadBlocks(ArrayRef <BasicBlock *> BBs, 62353358Sdim DomTreeUpdater *DTU = nullptr, 63353358Sdim bool KeepOneInputPHIs = false); 64344779Sdim 65353358Sdim/// Delete all basic blocks from \p F that are not reachable from its entry 66353358Sdim/// node. If \p KeepOneInputPHIs is true, one-input Phis in successors of 67353358Sdim/// blocks being deleted will be preserved. 68353358Sdimbool EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU = nullptr, 69353358Sdim bool KeepOneInputPHIs = false); 70353358Sdim 71309124Sdim/// We know that BB has one predecessor. If there are any single-entry PHI nodes 72309124Sdim/// in it, fold them away. This handles the case when all entries to the PHI 73309124Sdim/// nodes in a block are guaranteed equal, such as when the block has exactly 74309124Sdim/// one predecessor. 75296417Sdimvoid FoldSingleEntryPHINodes(BasicBlock *BB, 76309124Sdim MemoryDependenceResults *MemDep = nullptr); 77193323Sed 78309124Sdim/// Examine each PHI in the given block and delete it if it is dead. Also 79309124Sdim/// recursively delete any operands that become dead as a result. This includes 80309124Sdim/// tracing the def-use list from the PHI to see if it is ultimately unused or 81309124Sdim/// if it reaches an unused cycle. Return true if any PHIs were deleted. 82276479Sdimbool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr); 83193323Sed 84309124Sdim/// Attempts to merge a block into its predecessor, if possible. The return 85309124Sdim/// value indicates success or failure. 86360784Sdim/// By default do not merge blocks if BB's predecessor has multiple successors. 87360784Sdim/// If PredecessorWithTwoSuccessors = true, the blocks can only be merged 88360784Sdim/// if BB's Pred has a branch to BB and to AnotherBB, and BB has a single 89360784Sdim/// successor Sing. In this case the branch will be updated with Sing instead of 90360784Sdim/// BB, and BB will still be merged into its predecessor and removed. 91344779Sdimbool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU = nullptr, 92288943Sdim LoopInfo *LI = nullptr, 93344779Sdim MemorySSAUpdater *MSSAU = nullptr, 94360784Sdim MemoryDependenceResults *MemDep = nullptr, 95360784Sdim bool PredecessorWithTwoSuccessors = false); 96193323Sed 97360784Sdim/// Try to remove redundant dbg.value instructions from given basic block. 98360784Sdim/// Returns true if at least one instruction was removed. 99360784Sdimbool RemoveRedundantDbgInstrs(BasicBlock *BB); 100360784Sdim 101309124Sdim/// Replace all uses of an instruction (specified by BI) with a value, then 102309124Sdim/// remove and delete the original instruction. 103193323Sedvoid ReplaceInstWithValue(BasicBlock::InstListType &BIL, 104193323Sed BasicBlock::iterator &BI, Value *V); 105193323Sed 106309124Sdim/// Replace the instruction specified by BI with the instruction specified by I. 107309124Sdim/// Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. The 108309124Sdim/// original instruction is deleted and BI is updated to point to the new 109309124Sdim/// instruction. 110193323Sedvoid ReplaceInstWithInst(BasicBlock::InstListType &BIL, 111193323Sed BasicBlock::iterator &BI, Instruction *I); 112193323Sed 113309124Sdim/// Replace the instruction specified by From with the instruction specified by 114309124Sdim/// To. Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. 115193323Sedvoid ReplaceInstWithInst(Instruction *From, Instruction *To); 116193323Sed 117309124Sdim/// Option class for critical edge splitting. 118288943Sdim/// 119288943Sdim/// This provides a builder interface for overriding the default options used 120288943Sdim/// during critical edge splitting. 121288943Sdimstruct CriticalEdgeSplittingOptions { 122288943Sdim DominatorTree *DT; 123353358Sdim PostDominatorTree *PDT; 124288943Sdim LoopInfo *LI; 125344779Sdim MemorySSAUpdater *MSSAU; 126321369Sdim bool MergeIdenticalEdges = false; 127353358Sdim bool KeepOneInputPHIs = false; 128321369Sdim bool PreserveLCSSA = false; 129353358Sdim bool IgnoreUnreachableDests = false; 130288943Sdim 131296417Sdim CriticalEdgeSplittingOptions(DominatorTree *DT = nullptr, 132344779Sdim LoopInfo *LI = nullptr, 133353358Sdim MemorySSAUpdater *MSSAU = nullptr, 134353358Sdim PostDominatorTree *PDT = nullptr) 135353358Sdim : DT(DT), PDT(PDT), LI(LI), MSSAU(MSSAU) {} 136288943Sdim 137288943Sdim CriticalEdgeSplittingOptions &setMergeIdenticalEdges() { 138288943Sdim MergeIdenticalEdges = true; 139288943Sdim return *this; 140288943Sdim } 141288943Sdim 142353358Sdim CriticalEdgeSplittingOptions &setKeepOneInputPHIs() { 143353358Sdim KeepOneInputPHIs = true; 144288943Sdim return *this; 145288943Sdim } 146288943Sdim 147288943Sdim CriticalEdgeSplittingOptions &setPreserveLCSSA() { 148288943Sdim PreserveLCSSA = true; 149288943Sdim return *this; 150288943Sdim } 151353358Sdim 152353358Sdim CriticalEdgeSplittingOptions &setIgnoreUnreachableDests() { 153353358Sdim IgnoreUnreachableDests = true; 154353358Sdim return *this; 155353358Sdim } 156288943Sdim}; 157288943Sdim 158309124Sdim/// If this edge is a critical edge, insert a new node to split the critical 159309124Sdim/// edge. This will update the analyses passed in through the option struct. 160309124Sdim/// This returns the new block if the edge was split, null otherwise. 161193323Sed/// 162288943Sdim/// If MergeIdenticalEdges in the options struct is true (not the default), 163288943Sdim/// *all* edges from TI to the specified successor will be merged into the same 164288943Sdim/// critical edge block. This is most commonly interesting with switch 165288943Sdim/// instructions, which may have many edges to any one destination. This 166288943Sdim/// ensures that all edges to that dest go to one block instead of each going 167288943Sdim/// to a different block, but isn't the standard definition of a "critical 168288943Sdim/// edge". 169193323Sed/// 170198892Srdivacky/// It is invalid to call this function on a critical edge that starts at an 171198892Srdivacky/// IndirectBrInst. Splitting these edges will almost always create an invalid 172198892Srdivacky/// program because the address of the new block won't be the one that is jumped 173198892Srdivacky/// to. 174344779SdimBasicBlock *SplitCriticalEdge(Instruction *TI, unsigned SuccNum, 175288943Sdim const CriticalEdgeSplittingOptions &Options = 176288943Sdim CriticalEdgeSplittingOptions()); 177193323Sed 178288943Sdiminline BasicBlock * 179288943SdimSplitCriticalEdge(BasicBlock *BB, succ_iterator SI, 180288943Sdim const CriticalEdgeSplittingOptions &Options = 181288943Sdim CriticalEdgeSplittingOptions()) { 182288943Sdim return SplitCriticalEdge(BB->getTerminator(), SI.getSuccessorIndex(), 183288943Sdim Options); 184193323Sed} 185193323Sed 186309124Sdim/// If the edge from *PI to BB is not critical, return false. Otherwise, split 187309124Sdim/// all edges between the two blocks and return true. This updates all of the 188309124Sdim/// same analyses as the other SplitCriticalEdge function. If P is specified, it 189309124Sdim/// updates the analyses described above. 190276479Sdiminline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, 191288943Sdim const CriticalEdgeSplittingOptions &Options = 192288943Sdim CriticalEdgeSplittingOptions()) { 193193323Sed bool MadeChange = false; 194344779Sdim Instruction *TI = (*PI)->getTerminator(); 195193323Sed for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 196193323Sed if (TI->getSuccessor(i) == Succ) 197288943Sdim MadeChange |= !!SplitCriticalEdge(TI, i, Options); 198193323Sed return MadeChange; 199193323Sed} 200193323Sed 201309124Sdim/// If an edge from Src to Dst is critical, split the edge and return true, 202309124Sdim/// otherwise return false. This method requires that there be an edge between 203309124Sdim/// the two blocks. It updates the analyses passed in the options struct 204288943Sdiminline BasicBlock * 205288943SdimSplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst, 206288943Sdim const CriticalEdgeSplittingOptions &Options = 207288943Sdim CriticalEdgeSplittingOptions()) { 208344779Sdim Instruction *TI = Src->getTerminator(); 209193323Sed unsigned i = 0; 210314564Sdim while (true) { 211193323Sed assert(i != TI->getNumSuccessors() && "Edge doesn't exist!"); 212193323Sed if (TI->getSuccessor(i) == Dst) 213288943Sdim return SplitCriticalEdge(TI, i, Options); 214193323Sed ++i; 215193323Sed } 216193323Sed} 217193323Sed 218309124Sdim/// Loop over all of the edges in the CFG, breaking critical edges as they are 219309124Sdim/// found. Returns the number of broken edges. 220288943Sdimunsigned SplitAllCriticalEdges(Function &F, 221288943Sdim const CriticalEdgeSplittingOptions &Options = 222288943Sdim CriticalEdgeSplittingOptions()); 223280031Sdim 224309124Sdim/// Split the edge connecting specified block. 225288943SdimBasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To, 226344779Sdim DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, 227344779Sdim MemorySSAUpdater *MSSAU = nullptr); 228193323Sed 229309124Sdim/// Split the specified block at the specified instruction - everything before 230309124Sdim/// SplitPt stays in Old and everything starting with SplitPt moves to a new 231309124Sdim/// block. The two blocks are joined by an unconditional branch and the loop 232309124Sdim/// info is updated. 233288943SdimBasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, 234344779Sdim DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, 235360784Sdim MemorySSAUpdater *MSSAU = nullptr, 236360784Sdim const Twine &BBName = ""); 237226633Sdim 238309124Sdim/// This method introduces at least one new basic block into the function and 239309124Sdim/// moves some of the predecessors of BB to be predecessors of the new block. 240309124Sdim/// The new predecessors are indicated by the Preds array. The new block is 241309124Sdim/// given a suffix of 'Suffix'. Returns new basic block to which predecessors 242309124Sdim/// from Preds are now pointing. 243193323Sed/// 244288943Sdim/// If BB is a landingpad block then additional basicblock might be introduced. 245288943Sdim/// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more 246288943Sdim/// details on this case. 247288943Sdim/// 248296417Sdim/// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but 249296417Sdim/// no other analyses. In particular, it does not preserve LoopSimplify 250296417Sdim/// (because it's complicated to handle the case where one of the edges being 251296417Sdim/// split is an exit of a loop with other exits). 252288943SdimBasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, 253288943Sdim const char *Suffix, 254288943Sdim DominatorTree *DT = nullptr, 255288943Sdim LoopInfo *LI = nullptr, 256344779Sdim MemorySSAUpdater *MSSAU = nullptr, 257288943Sdim bool PreserveLCSSA = false); 258218893Sdim 259309124Sdim/// This method transforms the landing pad, OrigBB, by introducing two new basic 260309124Sdim/// blocks into the function. One of those new basic blocks gets the 261309124Sdim/// predecessors listed in Preds. The other basic block gets the remaining 262309124Sdim/// predecessors of OrigBB. The landingpad instruction OrigBB is clone into both 263309124Sdim/// of the new basic blocks. The new blocks are given the suffixes 'Suffix1' and 264309124Sdim/// 'Suffix2', and are returned in the NewBBs vector. 265226633Sdim/// 266296417Sdim/// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but 267296417Sdim/// no other analyses. In particular, it does not preserve LoopSimplify 268296417Sdim/// (because it's complicated to handle the case where one of the edges being 269296417Sdim/// split is an exit of a loop with other exits). 270344779Sdimvoid SplitLandingPadPredecessors( 271344779Sdim BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix, 272344779Sdim const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs, 273344779Sdim DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, 274344779Sdim MemorySSAUpdater *MSSAU = nullptr, bool PreserveLCSSA = false); 275226633Sdim 276309124Sdim/// This method duplicates the specified return instruction into a predecessor 277309124Sdim/// which ends in an unconditional branch. If the return instruction returns a 278309124Sdim/// value defined by a PHI, propagate the right value into the return. It 279309124Sdim/// returns the new return instruction in the predecessor. 280218893SdimReturnInst *FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, 281344779Sdim BasicBlock *Pred, 282344779Sdim DomTreeUpdater *DTU = nullptr); 283218893Sdim 284309124Sdim/// Split the containing block at the specified instruction - everything before 285314564Sdim/// SplitBefore stays in the old basic block, and the rest of the instructions 286314564Sdim/// in the BB are moved to a new block. The two blocks are connected by a 287309124Sdim/// conditional branch (with value of Cmp being the condition). 288243830Sdim/// Before: 289243830Sdim/// Head 290276479Sdim/// SplitBefore 291243830Sdim/// Tail 292243830Sdim/// After: 293243830Sdim/// Head 294276479Sdim/// if (Cond) 295243830Sdim/// ThenBlock 296276479Sdim/// SplitBefore 297243830Sdim/// Tail 298243830Sdim/// 299353358Sdim/// If \p ThenBlock is not specified, a new block will be created for it. 300353358Sdim/// If \p Unreachable is true, the newly created block will end with 301243830Sdim/// UnreachableInst, otherwise it branches to Tail. 302243830Sdim/// Returns the NewBasicBlock's terminator. 303276479Sdim/// 304309124Sdim/// Updates DT and LI if given. 305344779SdimInstruction *SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, 306344779Sdim bool Unreachable, 307344779Sdim MDNode *BranchWeights = nullptr, 308344779Sdim DominatorTree *DT = nullptr, 309353358Sdim LoopInfo *LI = nullptr, 310353358Sdim BasicBlock *ThenBlock = nullptr); 311243830Sdim 312276479Sdim/// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, 313276479Sdim/// but also creates the ElseBlock. 314276479Sdim/// Before: 315276479Sdim/// Head 316276479Sdim/// SplitBefore 317276479Sdim/// Tail 318276479Sdim/// After: 319276479Sdim/// Head 320276479Sdim/// if (Cond) 321276479Sdim/// ThenBlock 322276479Sdim/// else 323276479Sdim/// ElseBlock 324276479Sdim/// SplitBefore 325276479Sdim/// Tail 326276479Sdimvoid SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, 327344779Sdim Instruction **ThenTerm, 328344779Sdim Instruction **ElseTerm, 329276479Sdim MDNode *BranchWeights = nullptr); 330243830Sdim 331309124Sdim/// Check whether BB is the merge point of a if-region. 332261991Sdim/// If so, return the boolean condition that determines which entry into 333261991Sdim/// BB will be taken. Also, return by references the block that will be 334261991Sdim/// entered from if the condition is true, and the block that will be 335261991Sdim/// entered if the condition is false. 336309124Sdim/// 337309124Sdim/// This does no checking to see if the true/false blocks have large or unsavory 338309124Sdim/// instructions in them. 339261991SdimValue *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, 340276479Sdim BasicBlock *&IfFalse); 341193323Sed 342327952Sdim// Split critical edges where the source of the edge is an indirectbr 343327952Sdim// instruction. This isn't always possible, but we can handle some easy cases. 344327952Sdim// This is useful because MI is unable to split such critical edges, 345327952Sdim// which means it will not be able to sink instructions along those edges. 346327952Sdim// This is especially painful for indirect branches with many successors, where 347327952Sdim// we end up having to prepare all outgoing values in the origin block. 348327952Sdim// 349327952Sdim// Our normal algorithm for splitting critical edges requires us to update 350327952Sdim// the outgoing edges of the edge origin block, but for an indirectbr this 351327952Sdim// is hard, since it would require finding and updating the block addresses 352327952Sdim// the indirect branch uses. But if a block only has a single indirectbr 353327952Sdim// predecessor, with the others being regular branches, we can do it in a 354327952Sdim// different way. 355327952Sdim// Say we have A -> D, B -> D, I -> D where only I -> D is an indirectbr. 356327952Sdim// We can split D into D0 and D1, where D0 contains only the PHIs from D, 357327952Sdim// and D1 is the D block body. We can then duplicate D0 as D0A and D0B, and 358327952Sdim// create the following structure: 359327952Sdim// A -> D0A, B -> D0A, I -> D0B, D0A -> D1, D0B -> D1 360327952Sdim// If BPI and BFI aren't non-null, BPI/BFI will be updated accordingly. 361327952Sdimbool SplitIndirectBrCriticalEdges(Function &F, 362327952Sdim BranchProbabilityInfo *BPI = nullptr, 363327952Sdim BlockFrequencyInfo *BFI = nullptr); 364327952Sdim 365314564Sdim} // end namespace llvm 366314564Sdim 367314564Sdim#endif // LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H 368