LLVM API Documentation
00001 //===-- Transform/Utils/BasicBlockUtils.h - BasicBlock Utils ----*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This family of functions perform manipulations on basic blocks, and 00011 // instructions contained within basic blocks. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #ifndef LLVM_TRANSFORMS_UTILS_BASICBLOCK_H 00016 #define LLVM_TRANSFORMS_UTILS_BASICBLOCK_H 00017 00018 // FIXME: Move to this file: BasicBlock::removePredecessor, BB::splitBasicBlock 00019 00020 #include "llvm/BasicBlock.h" 00021 #include "llvm/Support/CFG.h" 00022 00023 namespace llvm { 00024 00025 class Instruction; 00026 class Pass; 00027 class AliasAnalysis; 00028 00029 /// DeleteDeadBlock - Delete the specified block, which must have no 00030 /// predecessors. 00031 void DeleteDeadBlock(BasicBlock *BB); 00032 00033 00034 /// FoldSingleEntryPHINodes - We know that BB has one predecessor. If there are 00035 /// any single-entry PHI nodes in it, fold them away. This handles the case 00036 /// when all entries to the PHI nodes in a block are guaranteed equal, such as 00037 /// when the block has exactly one predecessor. 00038 void FoldSingleEntryPHINodes(BasicBlock *BB); 00039 00040 /// DeleteDeadPHIs - Examine each PHI in the given block and delete it if it 00041 /// is dead. Also recursively delete any operands that become dead as 00042 /// a result. This includes tracing the def-use list from the PHI to see if 00043 /// it is ultimately unused or if it reaches an unused cycle. 00044 void DeleteDeadPHIs(BasicBlock *BB); 00045 00046 /// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor, 00047 /// if possible. The return value indicates success or failure. 00048 bool MergeBlockIntoPredecessor(BasicBlock* BB, Pass* P = 0); 00049 00050 // ReplaceInstWithValue - Replace all uses of an instruction (specified by BI) 00051 // with a value, then remove and delete the original instruction. 00052 // 00053 void ReplaceInstWithValue(BasicBlock::InstListType &BIL, 00054 BasicBlock::iterator &BI, Value *V); 00055 00056 // ReplaceInstWithInst - Replace the instruction specified by BI with the 00057 // instruction specified by I. The original instruction is deleted and BI is 00058 // updated to point to the new instruction. 00059 // 00060 void ReplaceInstWithInst(BasicBlock::InstListType &BIL, 00061 BasicBlock::iterator &BI, Instruction *I); 00062 00063 // ReplaceInstWithInst - Replace the instruction specified by From with the 00064 // instruction specified by To. 00065 // 00066 void ReplaceInstWithInst(Instruction *From, Instruction *To); 00067 00068 /// CopyPrecedingStopPoint - If I is immediately preceded by a StopPoint, 00069 /// make a copy of the stoppoint before InsertPos (presumably before copying 00070 /// or moving I). 00071 void CopyPrecedingStopPoint(Instruction *I, BasicBlock::iterator InsertPos); 00072 00073 /// FindAvailableLoadedValue - Scan the ScanBB block backwards (starting at the 00074 /// instruction before ScanFrom) checking to see if we have the value at the 00075 /// memory address *Ptr locally available within a small number of instructions. 00076 /// If the value is available, return it. 00077 /// 00078 /// If not, return the iterator for the last validated instruction that the 00079 /// value would be live through. If we scanned the entire block and didn't find 00080 /// something that invalidates *Ptr or provides it, ScanFrom would be left at 00081 /// begin() and this returns null. ScanFrom could also be left 00082 /// 00083 /// MaxInstsToScan specifies the maximum instructions to scan in the block. If 00084 /// it is set to 0, it will scan the whole block. You can also optionally 00085 /// specify an alias analysis implementation, which makes this more precise. 00086 Value *FindAvailableLoadedValue(Value *Ptr, BasicBlock *ScanBB, 00087 BasicBlock::iterator &ScanFrom, 00088 unsigned MaxInstsToScan = 6, 00089 AliasAnalysis *AA = 0); 00090 00091 /// FindFunctionBackedges - Analyze the specified function to find all of the 00092 /// loop backedges in the function and return them. This is a relatively cheap 00093 /// (compared to computing dominators and loop info) analysis. 00094 /// 00095 /// The output is added to Result, as pairs of <from,to> edge info. 00096 void FindFunctionBackedges(const Function &F, 00097 SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result); 00098 00099 00100 // RemoveSuccessor - Change the specified terminator instruction such that its 00101 // successor #SuccNum no longer exists. Because this reduces the outgoing 00102 // degree of the current basic block, the actual terminator instruction itself 00103 // may have to be changed. In the case where the last successor of the block is 00104 // deleted, a return instruction is inserted in its place which can cause a 00105 // suprising change in program behavior if it is not expected. 00106 // 00107 void RemoveSuccessor(TerminatorInst *TI, unsigned SuccNum); 00108 00109 /// isCriticalEdge - Return true if the specified edge is a critical edge. 00110 /// Critical edges are edges from a block with multiple successors to a block 00111 /// with multiple predecessors. 00112 /// 00113 bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, 00114 bool AllowIdenticalEdges = false); 00115 00116 /// SplitCriticalEdge - If this edge is a critical edge, insert a new node to 00117 /// split the critical edge. This will update DominatorTree and 00118 /// DominatorFrontier information if it is available, thus calling this pass 00119 /// will not invalidate either of them. This returns true if the edge was split, 00120 /// false otherwise. 00121 /// 00122 /// If MergeIdenticalEdges is true (not the default), *all* edges from TI to the 00123 /// specified successor will be merged into the same critical edge block. 00124 /// This is most commonly interesting with switch instructions, which may 00125 /// have many edges to any one destination. This ensures that all edges to that 00126 /// dest go to one block instead of each going to a different block, but isn't 00127 /// the standard definition of a "critical edge". 00128 /// 00129 bool SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P = 0, 00130 bool MergeIdenticalEdges = false); 00131 00132 inline bool SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, Pass *P = 0) { 00133 return SplitCriticalEdge(BB->getTerminator(), SI.getSuccessorIndex(), P); 00134 } 00135 00136 /// SplitCriticalEdge - If the edge from *PI to BB is not critical, return 00137 /// false. Otherwise, split all edges between the two blocks and return true. 00138 /// This updates all of the same analyses as the other SplitCriticalEdge 00139 /// function. If P is specified, it updates the analyses 00140 /// described above. 00141 inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, Pass *P = 0) { 00142 bool MadeChange = false; 00143 TerminatorInst *TI = (*PI)->getTerminator(); 00144 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 00145 if (TI->getSuccessor(i) == Succ) 00146 MadeChange |= SplitCriticalEdge(TI, i, P); 00147 return MadeChange; 00148 } 00149 00150 /// SplitCriticalEdge - If an edge from Src to Dst is critical, split the edge 00151 /// and return true, otherwise return false. This method requires that there be 00152 /// an edge between the two blocks. If P is specified, it updates the analyses 00153 /// described above. 00154 inline bool SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst, Pass *P = 0, 00155 bool MergeIdenticalEdges = false) { 00156 TerminatorInst *TI = Src->getTerminator(); 00157 unsigned i = 0; 00158 while (1) { 00159 assert(i != TI->getNumSuccessors() && "Edge doesn't exist!"); 00160 if (TI->getSuccessor(i) == Dst) 00161 return SplitCriticalEdge(TI, i, P, MergeIdenticalEdges); 00162 ++i; 00163 } 00164 } 00165 00166 /// SplitEdge - Split the edge connecting specified block. Pass P must 00167 /// not be NULL. 00168 BasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To, Pass *P); 00169 00170 /// SplitBlock - Split the specified block at the specified instruction - every 00171 /// thing before SplitPt stays in Old and everything starting with SplitPt moves 00172 /// to a new block. The two blocks are joined by an unconditional branch and 00173 /// the loop info is updated. 00174 /// 00175 BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P); 00176 00177 /// SplitBlockPredecessors - This method transforms BB by introducing a new 00178 /// basic block into the function, and moving some of the predecessors of BB to 00179 /// be predecessors of the new block. The new predecessors are indicated by the 00180 /// Preds array, which has NumPreds elements in it. The new block is given a 00181 /// suffix of 'Suffix'. This function returns the new block. 00182 /// 00183 /// This currently updates the LLVM IR, AliasAnalysis, DominatorTree and 00184 /// DominanceFrontier, but no other analyses. 00185 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, BasicBlock *const *Preds, 00186 unsigned NumPreds, const char *Suffix, 00187 Pass *P = 0); 00188 00189 } // End llvm namespace 00190 00191 #endif