1 //===-- Transform/Utils/BasicBlockUtils.h - BasicBlock Utils ----*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This family of functions perform manipulations on basic blocks, and 11 // instructions contained within basic blocks. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H 16 #define LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H 17 18 // FIXME: Move to this file: BasicBlock::removePredecessor, BB::splitBasicBlock 19 20 #include "llvm/IR/BasicBlock.h" 21 #include "llvm/IR/CFG.h" 22 23 namespace llvm { 24 25 class MemoryDependenceResults; 26 class DominatorTree; 27 class LoopInfo; 28 class Instruction; 29 class MDNode; 30 class ReturnInst; 31 class TargetLibraryInfo; 32 class TerminatorInst; 33 34 /// Delete the specified block, which must have no predecessors. 35 void DeleteDeadBlock(BasicBlock *BB); 36 37 /// We know that BB has one predecessor. If there are any single-entry PHI nodes 38 /// in it, fold them away. This handles the case when all entries to the PHI 39 /// nodes in a block are guaranteed equal, such as when the block has exactly 40 /// one predecessor. 41 void FoldSingleEntryPHINodes(BasicBlock *BB, 42 MemoryDependenceResults *MemDep = nullptr); 43 44 /// Examine each PHI in the given block and delete it if it is dead. Also 45 /// recursively delete any operands that become dead as a result. This includes 46 /// tracing the def-use list from the PHI to see if it is ultimately unused or 47 /// if it reaches an unused cycle. Return true if any PHIs were deleted. 48 bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr); 49 50 /// Attempts to merge a block into its predecessor, if possible. The return 51 /// value indicates success or failure. 52 bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT = nullptr, 53 LoopInfo *LI = nullptr, 54 MemoryDependenceResults *MemDep = nullptr); 55 56 /// Replace all uses of an instruction (specified by BI) with a value, then 57 /// remove and delete the original instruction. 58 void ReplaceInstWithValue(BasicBlock::InstListType &BIL, 59 BasicBlock::iterator &BI, Value *V); 60 61 /// Replace the instruction specified by BI with the instruction specified by I. 62 /// Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. The 63 /// original instruction is deleted and BI is updated to point to the new 64 /// instruction. 65 void ReplaceInstWithInst(BasicBlock::InstListType &BIL, 66 BasicBlock::iterator &BI, Instruction *I); 67 68 /// Replace the instruction specified by From with the instruction specified by 69 /// To. Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. 70 void ReplaceInstWithInst(Instruction *From, Instruction *To); 71 72 /// Option class for critical edge splitting. 73 /// 74 /// This provides a builder interface for overriding the default options used 75 /// during critical edge splitting. 76 struct CriticalEdgeSplittingOptions { 77 DominatorTree *DT; 78 LoopInfo *LI; 79 bool MergeIdenticalEdges; 80 bool DontDeleteUselessPHIs; 81 bool PreserveLCSSA; 82 83 CriticalEdgeSplittingOptions(DominatorTree *DT = nullptr, 84 LoopInfo *LI = nullptr) 85 : DT(DT), LI(LI), MergeIdenticalEdges(false), 86 DontDeleteUselessPHIs(false), PreserveLCSSA(false) {} 87 88 CriticalEdgeSplittingOptions &setMergeIdenticalEdges() { 89 MergeIdenticalEdges = true; 90 return *this; 91 } 92 93 CriticalEdgeSplittingOptions &setDontDeleteUselessPHIs() { 94 DontDeleteUselessPHIs = true; 95 return *this; 96 } 97 98 CriticalEdgeSplittingOptions &setPreserveLCSSA() { 99 PreserveLCSSA = true; 100 return *this; 101 } 102 }; 103 104 /// If this edge is a critical edge, insert a new node to split the critical 105 /// edge. This will update the analyses passed in through the option struct. 106 /// This returns the new block if the edge was split, null otherwise. 107 /// 108 /// If MergeIdenticalEdges in the options struct is true (not the default), 109 /// *all* edges from TI to the specified successor will be merged into the same 110 /// critical edge block. This is most commonly interesting with switch 111 /// instructions, which may have many edges to any one destination. This 112 /// ensures that all edges to that dest go to one block instead of each going 113 /// to a different block, but isn't the standard definition of a "critical 114 /// edge". 115 /// 116 /// It is invalid to call this function on a critical edge that starts at an 117 /// IndirectBrInst. Splitting these edges will almost always create an invalid 118 /// program because the address of the new block won't be the one that is jumped 119 /// to. 120 /// 121 BasicBlock *SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, 122 const CriticalEdgeSplittingOptions &Options = 123 CriticalEdgeSplittingOptions()); 124 125 inline BasicBlock * 126 SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, 127 const CriticalEdgeSplittingOptions &Options = 128 CriticalEdgeSplittingOptions()) { 129 return SplitCriticalEdge(BB->getTerminator(), SI.getSuccessorIndex(), 130 Options); 131 } 132 133 /// If the edge from *PI to BB is not critical, return false. Otherwise, split 134 /// all edges between the two blocks and return true. This updates all of the 135 /// same analyses as the other SplitCriticalEdge function. If P is specified, it 136 /// updates the analyses described above. 137 inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, 138 const CriticalEdgeSplittingOptions &Options = 139 CriticalEdgeSplittingOptions()) { 140 bool MadeChange = false; 141 TerminatorInst *TI = (*PI)->getTerminator(); 142 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 143 if (TI->getSuccessor(i) == Succ) 144 MadeChange |= !!SplitCriticalEdge(TI, i, Options); 145 return MadeChange; 146 } 147 148 /// If an edge from Src to Dst is critical, split the edge and return true, 149 /// otherwise return false. This method requires that there be an edge between 150 /// the two blocks. It updates the analyses passed in the options struct 151 inline BasicBlock * 152 SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst, 153 const CriticalEdgeSplittingOptions &Options = 154 CriticalEdgeSplittingOptions()) { 155 TerminatorInst *TI = Src->getTerminator(); 156 unsigned i = 0; 157 while (1) { 158 assert(i != TI->getNumSuccessors() && "Edge doesn't exist!"); 159 if (TI->getSuccessor(i) == Dst) 160 return SplitCriticalEdge(TI, i, Options); 161 ++i; 162 } 163 } 164 165 /// Loop over all of the edges in the CFG, breaking critical edges as they are 166 /// found. Returns the number of broken edges. 167 unsigned SplitAllCriticalEdges(Function &F, 168 const CriticalEdgeSplittingOptions &Options = 169 CriticalEdgeSplittingOptions()); 170 171 /// Split the edge connecting specified block. 172 BasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To, 173 DominatorTree *DT = nullptr, LoopInfo *LI = nullptr); 174 175 /// Split the specified block at the specified instruction - everything before 176 /// SplitPt stays in Old and everything starting with SplitPt moves to a new 177 /// block. The two blocks are joined by an unconditional branch and the loop 178 /// info is updated. 179 BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, 180 DominatorTree *DT = nullptr, LoopInfo *LI = nullptr); 181 182 /// This method introduces at least one new basic block into the function and 183 /// moves some of the predecessors of BB to be predecessors of the new block. 184 /// The new predecessors are indicated by the Preds array. The new block is 185 /// given a suffix of 'Suffix'. Returns new basic block to which predecessors 186 /// from Preds are now pointing. 187 /// 188 /// If BB is a landingpad block then additional basicblock might be introduced. 189 /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more 190 /// details on this case. 191 /// 192 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but 193 /// no other analyses. In particular, it does not preserve LoopSimplify 194 /// (because it's complicated to handle the case where one of the edges being 195 /// split is an exit of a loop with other exits). 196 /// 197 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, 198 const char *Suffix, 199 DominatorTree *DT = nullptr, 200 LoopInfo *LI = nullptr, 201 bool PreserveLCSSA = false); 202 203 /// This method transforms the landing pad, OrigBB, by introducing two new basic 204 /// blocks into the function. One of those new basic blocks gets the 205 /// predecessors listed in Preds. The other basic block gets the remaining 206 /// predecessors of OrigBB. The landingpad instruction OrigBB is clone into both 207 /// of the new basic blocks. The new blocks are given the suffixes 'Suffix1' and 208 /// 'Suffix2', and are returned in the NewBBs vector. 209 /// 210 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but 211 /// no other analyses. In particular, it does not preserve LoopSimplify 212 /// (because it's complicated to handle the case where one of the edges being 213 /// split is an exit of a loop with other exits). 214 /// 215 void SplitLandingPadPredecessors(BasicBlock *OrigBB, 216 ArrayRef<BasicBlock *> Preds, 217 const char *Suffix, const char *Suffix2, 218 SmallVectorImpl<BasicBlock *> &NewBBs, 219 DominatorTree *DT = nullptr, 220 LoopInfo *LI = nullptr, 221 bool PreserveLCSSA = false); 222 223 /// This method duplicates the specified return instruction into a predecessor 224 /// which ends in an unconditional branch. If the return instruction returns a 225 /// value defined by a PHI, propagate the right value into the return. It 226 /// returns the new return instruction in the predecessor. 227 ReturnInst *FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, 228 BasicBlock *Pred); 229 230 /// Split the containing block at the specified instruction - everything before 231 /// and including SplitBefore stays in the old basic block, and everything after 232 /// SplitBefore is moved to a new block. The two blocks are connected by a 233 /// conditional branch (with value of Cmp being the condition). 234 /// Before: 235 /// Head 236 /// SplitBefore 237 /// Tail 238 /// After: 239 /// Head 240 /// if (Cond) 241 /// ThenBlock 242 /// SplitBefore 243 /// Tail 244 /// 245 /// If Unreachable is true, then ThenBlock ends with 246 /// UnreachableInst, otherwise it branches to Tail. 247 /// Returns the NewBasicBlock's terminator. 248 /// 249 /// Updates DT and LI if given. 250 TerminatorInst *SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, 251 bool Unreachable, 252 MDNode *BranchWeights = nullptr, 253 DominatorTree *DT = nullptr, 254 LoopInfo *LI = nullptr); 255 256 /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, 257 /// but also creates the ElseBlock. 258 /// Before: 259 /// Head 260 /// SplitBefore 261 /// Tail 262 /// After: 263 /// Head 264 /// if (Cond) 265 /// ThenBlock 266 /// else 267 /// ElseBlock 268 /// SplitBefore 269 /// Tail 270 void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, 271 TerminatorInst **ThenTerm, 272 TerminatorInst **ElseTerm, 273 MDNode *BranchWeights = nullptr); 274 275 /// Check whether BB is the merge point of a if-region. 276 /// If so, return the boolean condition that determines which entry into 277 /// BB will be taken. Also, return by references the block that will be 278 /// entered from if the condition is true, and the block that will be 279 /// entered if the condition is false. 280 /// 281 /// This does no checking to see if the true/false blocks have large or unsavory 282 /// instructions in them. 283 Value *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, 284 BasicBlock *&IfFalse); 285 } // End llvm namespace 286 287 #endif 288
