BasicBlockUtils.h revision 198892
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_BASICBLOCK_H 16#define LLVM_TRANSFORMS_UTILS_BASICBLOCK_H 17 18// FIXME: Move to this file: BasicBlock::removePredecessor, BB::splitBasicBlock 19 20#include "llvm/BasicBlock.h" 21#include "llvm/Support/CFG.h" 22 23namespace llvm { 24 25class Instruction; 26class Pass; 27class AliasAnalysis; 28 29/// DeleteDeadBlock - Delete the specified block, which must have no 30/// predecessors. 31void DeleteDeadBlock(BasicBlock *BB); 32 33 34/// FoldSingleEntryPHINodes - We know that BB has one predecessor. If there are 35/// any single-entry PHI nodes in it, fold them away. This handles the case 36/// when all entries to the PHI nodes in a block are guaranteed equal, such as 37/// when the block has exactly one predecessor. 38void FoldSingleEntryPHINodes(BasicBlock *BB); 39 40/// DeleteDeadPHIs - Examine each PHI in the given block and delete it if it 41/// is dead. Also recursively delete any operands that become dead as 42/// a result. This includes tracing the def-use list from the PHI to see if 43/// it is ultimately unused or if it reaches an unused cycle. 44void DeleteDeadPHIs(BasicBlock *BB); 45 46/// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor, 47/// if possible. The return value indicates success or failure. 48bool MergeBlockIntoPredecessor(BasicBlock* BB, Pass* P = 0); 49 50// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI) 51// with a value, then remove and delete the original instruction. 52// 53void ReplaceInstWithValue(BasicBlock::InstListType &BIL, 54 BasicBlock::iterator &BI, Value *V); 55 56// ReplaceInstWithInst - Replace the instruction specified by BI with the 57// instruction specified by I. The original instruction is deleted and BI is 58// updated to point to the new instruction. 59// 60void ReplaceInstWithInst(BasicBlock::InstListType &BIL, 61 BasicBlock::iterator &BI, Instruction *I); 62 63// ReplaceInstWithInst - Replace the instruction specified by From with the 64// instruction specified by To. 65// 66void ReplaceInstWithInst(Instruction *From, Instruction *To); 67 68/// CopyPrecedingStopPoint - If I is immediately preceded by a StopPoint, 69/// make a copy of the stoppoint before InsertPos (presumably before copying 70/// or moving I). 71void CopyPrecedingStopPoint(Instruction *I, BasicBlock::iterator InsertPos); 72 73/// FindAvailableLoadedValue - Scan the ScanBB block backwards (starting at the 74/// instruction before ScanFrom) checking to see if we have the value at the 75/// memory address *Ptr locally available within a small number of instructions. 76/// If the value is available, return it. 77/// 78/// If not, return the iterator for the last validated instruction that the 79/// value would be live through. If we scanned the entire block and didn't find 80/// something that invalidates *Ptr or provides it, ScanFrom would be left at 81/// begin() and this returns null. ScanFrom could also be left 82/// 83/// MaxInstsToScan specifies the maximum instructions to scan in the block. If 84/// it is set to 0, it will scan the whole block. You can also optionally 85/// specify an alias analysis implementation, which makes this more precise. 86Value *FindAvailableLoadedValue(Value *Ptr, BasicBlock *ScanBB, 87 BasicBlock::iterator &ScanFrom, 88 unsigned MaxInstsToScan = 6, 89 AliasAnalysis *AA = 0); 90 91/// FindFunctionBackedges - Analyze the specified function to find all of the 92/// loop backedges in the function and return them. This is a relatively cheap 93/// (compared to computing dominators and loop info) analysis. 94/// 95/// The output is added to Result, as pairs of <from,to> edge info. 96void FindFunctionBackedges(const Function &F, 97 SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result); 98 99 100// RemoveSuccessor - Change the specified terminator instruction such that its 101// successor #SuccNum no longer exists. Because this reduces the outgoing 102// degree of the current basic block, the actual terminator instruction itself 103// may have to be changed. In the case where the last successor of the block is 104// deleted, a return instruction is inserted in its place which can cause a 105// suprising change in program behavior if it is not expected. 106// 107void RemoveSuccessor(TerminatorInst *TI, unsigned SuccNum); 108 109/// isCriticalEdge - Return true if the specified edge is a critical edge. 110/// Critical edges are edges from a block with multiple successors to a block 111/// with multiple predecessors. 112/// 113bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, 114 bool AllowIdenticalEdges = false); 115 116/// SplitCriticalEdge - If this edge is a critical edge, insert a new node to 117/// split the critical edge. This will update DominatorTree and 118/// DominatorFrontier information if it is available, thus calling this pass 119/// will not invalidate either of them. This returns the new block if the edge 120/// was split, null otherwise. 121/// 122/// If MergeIdenticalEdges is true (not the default), *all* edges from TI to the 123/// specified successor will be merged into the same critical edge block. 124/// This is most commonly interesting with switch instructions, which may 125/// have many edges to any one destination. This ensures that all edges to that 126/// dest go to one block instead of each going to a different block, but isn't 127/// the standard definition of a "critical edge". 128/// 129/// It is invalid to call this function on a critical edge that starts at an 130/// IndirectBrInst. Splitting these edges will almost always create an invalid 131/// program because the address of the new block won't be the one that is jumped 132/// to. 133/// 134BasicBlock *SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, 135 Pass *P = 0, bool MergeIdenticalEdges = false); 136 137inline BasicBlock *SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, 138 Pass *P = 0) { 139 return SplitCriticalEdge(BB->getTerminator(), SI.getSuccessorIndex(), P); 140} 141 142/// SplitCriticalEdge - If the edge from *PI to BB is not critical, return 143/// false. Otherwise, split all edges between the two blocks and return true. 144/// This updates all of the same analyses as the other SplitCriticalEdge 145/// function. If P is specified, it updates the analyses 146/// described above. 147inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, Pass *P = 0) { 148 bool MadeChange = false; 149 TerminatorInst *TI = (*PI)->getTerminator(); 150 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 151 if (TI->getSuccessor(i) == Succ) 152 MadeChange |= !!SplitCriticalEdge(TI, i, P); 153 return MadeChange; 154} 155 156/// SplitCriticalEdge - If an edge from Src to Dst is critical, split the edge 157/// and return true, otherwise return false. This method requires that there be 158/// an edge between the two blocks. If P is specified, it updates the analyses 159/// described above. 160inline BasicBlock *SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst, 161 Pass *P = 0, 162 bool MergeIdenticalEdges = false) { 163 TerminatorInst *TI = Src->getTerminator(); 164 unsigned i = 0; 165 while (1) { 166 assert(i != TI->getNumSuccessors() && "Edge doesn't exist!"); 167 if (TI->getSuccessor(i) == Dst) 168 return SplitCriticalEdge(TI, i, P, MergeIdenticalEdges); 169 ++i; 170 } 171} 172 173/// SplitEdge - Split the edge connecting specified block. Pass P must 174/// not be NULL. 175BasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To, Pass *P); 176 177/// SplitBlock - Split the specified block at the specified instruction - every 178/// thing before SplitPt stays in Old and everything starting with SplitPt moves 179/// to a new block. The two blocks are joined by an unconditional branch and 180/// the loop info is updated. 181/// 182BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P); 183 184/// SplitBlockPredecessors - This method transforms BB by introducing a new 185/// basic block into the function, and moving some of the predecessors of BB to 186/// be predecessors of the new block. The new predecessors are indicated by the 187/// Preds array, which has NumPreds elements in it. The new block is given a 188/// suffix of 'Suffix'. This function returns the new block. 189/// 190/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree, 191/// DominanceFrontier, LoopInfo, and LCCSA but no other analyses. 192/// In particular, it does not preserve LoopSimplify (because it's 193/// complicated to handle the case where one of the edges being split 194/// is an exit of a loop with other exits). 195/// 196BasicBlock *SplitBlockPredecessors(BasicBlock *BB, BasicBlock *const *Preds, 197 unsigned NumPreds, const char *Suffix, 198 Pass *P = 0); 199 200} // End llvm namespace 201 202#endif 203