LLVM API Documentation

BasicBlockUtils.h
Go to the documentation of this file.
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_BASICBLOCKUTILS_H
00016 #define LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H
00017 
00018 // FIXME: Move to this file: BasicBlock::removePredecessor, BB::splitBasicBlock
00019 
00020 #include "llvm/IR/BasicBlock.h"
00021 #include "llvm/IR/CFG.h"
00022 
00023 namespace llvm {
00024 
00025 class AliasAnalysis;
00026 class Instruction;
00027 class MDNode;
00028 class Pass;
00029 class ReturnInst;
00030 class TargetLibraryInfo;
00031 class TerminatorInst;
00032 
00033 /// DeleteDeadBlock - Delete the specified block, which must have no
00034 /// predecessors.
00035 void DeleteDeadBlock(BasicBlock *BB);
00036 
00037 
00038 /// FoldSingleEntryPHINodes - We know that BB has one predecessor.  If there are
00039 /// any single-entry PHI nodes in it, fold them away.  This handles the case
00040 /// when all entries to the PHI nodes in a block are guaranteed equal, such as
00041 /// when the block has exactly one predecessor.
00042 void FoldSingleEntryPHINodes(BasicBlock *BB, Pass *P = nullptr);
00043 
00044 /// DeleteDeadPHIs - Examine each PHI in the given block and delete it if it
00045 /// is dead. Also recursively delete any operands that become dead as
00046 /// a result. This includes tracing the def-use list from the PHI to see if
00047 /// it is ultimately unused or if it reaches an unused cycle. Return true
00048 /// if any PHIs were deleted.
00049 bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr);
00050 
00051 /// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor,
00052 /// if possible.  The return value indicates success or failure.
00053 bool MergeBlockIntoPredecessor(BasicBlock *BB, Pass *P = nullptr);
00054 
00055 // ReplaceInstWithValue - Replace all uses of an instruction (specified by BI)
00056 // with a value, then remove and delete the original instruction.
00057 //
00058 void ReplaceInstWithValue(BasicBlock::InstListType &BIL,
00059                           BasicBlock::iterator &BI, Value *V);
00060 
00061 // ReplaceInstWithInst - Replace the instruction specified by BI with the
00062 // instruction specified by I.  The original instruction is deleted and BI is
00063 // updated to point to the new instruction.
00064 //
00065 void ReplaceInstWithInst(BasicBlock::InstListType &BIL,
00066                          BasicBlock::iterator &BI, Instruction *I);
00067 
00068 // ReplaceInstWithInst - Replace the instruction specified by From with the
00069 // instruction specified by To.
00070 //
00071 void ReplaceInstWithInst(Instruction *From, Instruction *To);
00072 
00073 /// SplitCriticalEdge - If this edge is a critical edge, insert a new node to
00074 /// split the critical edge.  This will update DominatorTree and
00075 /// DominatorFrontier information if it is available, thus calling this pass
00076 /// will not invalidate either of them. This returns the new block if the edge
00077 /// was split, null otherwise.
00078 ///
00079 /// If MergeIdenticalEdges is true (not the default), *all* edges from TI to the
00080 /// specified successor will be merged into the same critical edge block.
00081 /// This is most commonly interesting with switch instructions, which may
00082 /// have many edges to any one destination.  This ensures that all edges to that
00083 /// dest go to one block instead of each going to a different block, but isn't
00084 /// the standard definition of a "critical edge".
00085 ///
00086 /// It is invalid to call this function on a critical edge that starts at an
00087 /// IndirectBrInst.  Splitting these edges will almost always create an invalid
00088 /// program because the address of the new block won't be the one that is jumped
00089 /// to.
00090 ///
00091 BasicBlock *SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
00092                               Pass *P = nullptr,
00093                               bool MergeIdenticalEdges = false,
00094                               bool DontDeleteUselessPHIs = false,
00095                               bool SplitLandingPads = false);
00096 
00097 inline BasicBlock *SplitCriticalEdge(BasicBlock *BB, succ_iterator SI,
00098                                      Pass *P = nullptr) {
00099   return SplitCriticalEdge(BB->getTerminator(), SI.getSuccessorIndex(), P);
00100 }
00101 
00102 /// SplitCriticalEdge - If the edge from *PI to BB is not critical, return
00103 /// false.  Otherwise, split all edges between the two blocks and return true.
00104 /// This updates all of the same analyses as the other SplitCriticalEdge
00105 /// function.  If P is specified, it updates the analyses
00106 /// described above.
00107 inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI,
00108                               Pass *P = nullptr) {
00109   bool MadeChange = false;
00110   TerminatorInst *TI = (*PI)->getTerminator();
00111   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
00112     if (TI->getSuccessor(i) == Succ)
00113       MadeChange |= !!SplitCriticalEdge(TI, i, P);
00114   return MadeChange;
00115 }
00116 
00117 /// SplitCriticalEdge - If an edge from Src to Dst is critical, split the edge
00118 /// and return true, otherwise return false.  This method requires that there be
00119 /// an edge between the two blocks.  If P is specified, it updates the analyses
00120 /// described above.
00121 inline BasicBlock *SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst,
00122                                      Pass *P = nullptr,
00123                                      bool MergeIdenticalEdges = false,
00124                                      bool DontDeleteUselessPHIs = false) {
00125   TerminatorInst *TI = Src->getTerminator();
00126   unsigned i = 0;
00127   while (1) {
00128     assert(i != TI->getNumSuccessors() && "Edge doesn't exist!");
00129     if (TI->getSuccessor(i) == Dst)
00130       return SplitCriticalEdge(TI, i, P, MergeIdenticalEdges,
00131                                DontDeleteUselessPHIs);
00132     ++i;
00133   }
00134 }
00135 
00136 /// SplitEdge -  Split the edge connecting specified block. Pass P must
00137 /// not be NULL.
00138 BasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To, Pass *P);
00139 
00140 /// SplitBlock - Split the specified block at the specified instruction - every
00141 /// thing before SplitPt stays in Old and everything starting with SplitPt moves
00142 /// to a new block.  The two blocks are joined by an unconditional branch and
00143 /// the loop info is updated.
00144 ///
00145 BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P);
00146 
00147 /// SplitBlockPredecessors - This method transforms BB by introducing a new
00148 /// basic block into the function, and moving some of the predecessors of BB to
00149 /// be predecessors of the new block.  The new predecessors are indicated by the
00150 /// Preds array, which has NumPreds elements in it.  The new block is given a
00151 /// suffix of 'Suffix'.  This function returns the new block.
00152 ///
00153 /// This currently updates the LLVM IR, AliasAnalysis, DominatorTree,
00154 /// DominanceFrontier, LoopInfo, and LCCSA but no other analyses.
00155 /// In particular, it does not preserve LoopSimplify (because it's
00156 /// complicated to handle the case where one of the edges being split
00157 /// is an exit of a loop with other exits).
00158 ///
00159 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock*> Preds,
00160                                    const char *Suffix, Pass *P = nullptr);
00161 
00162 /// SplitLandingPadPredecessors - This method transforms the landing pad,
00163 /// OrigBB, by introducing two new basic blocks into the function. One of those
00164 /// new basic blocks gets the predecessors listed in Preds. The other basic
00165 /// block gets the remaining predecessors of OrigBB. The landingpad instruction
00166 /// OrigBB is clone into both of the new basic blocks. The new blocks are given
00167 /// the suffixes 'Suffix1' and 'Suffix2', and are returned in the NewBBs vector.
00168 ///
00169 /// This currently updates the LLVM IR, AliasAnalysis, DominatorTree,
00170 /// DominanceFrontier, LoopInfo, and LCCSA but no other analyses. In particular,
00171 /// it does not preserve LoopSimplify (because it's complicated to handle the
00172 /// case where one of the edges being split is an exit of a loop with other
00173 /// exits).
00174 ///
00175 void SplitLandingPadPredecessors(BasicBlock *OrigBB,ArrayRef<BasicBlock*> Preds,
00176                                  const char *Suffix, const char *Suffix2,
00177                                  Pass *P, SmallVectorImpl<BasicBlock*> &NewBBs);
00178 
00179 /// FoldReturnIntoUncondBranch - This method duplicates the specified return
00180 /// instruction into a predecessor which ends in an unconditional branch. If
00181 /// the return instruction returns a value defined by a PHI, propagate the
00182 /// right value into the return. It returns the new return instruction in the
00183 /// predecessor.
00184 ReturnInst *FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB,
00185                                        BasicBlock *Pred);
00186 
00187 /// SplitBlockAndInsertIfThen - Split the containing block at the
00188 /// specified instruction - everything before and including SplitBefore stays
00189 /// in the old basic block, and everything after SplitBefore is moved to a
00190 /// new block. The two blocks are connected by a conditional branch
00191 /// (with value of Cmp being the condition).
00192 /// Before:
00193 ///   Head
00194 ///   SplitBefore
00195 ///   Tail
00196 /// After:
00197 ///   Head
00198 ///   if (Cond)
00199 ///     ThenBlock
00200 ///   SplitBefore
00201 ///   Tail
00202 ///
00203 /// If Unreachable is true, then ThenBlock ends with
00204 /// UnreachableInst, otherwise it branches to Tail.
00205 /// Returns the NewBasicBlock's terminator.
00206 TerminatorInst *SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore,
00207                                           bool Unreachable,
00208                                           MDNode *BranchWeights = nullptr);
00209 
00210 
00211 /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen,
00212 /// but also creates the ElseBlock.
00213 /// Before:
00214 ///   Head
00215 ///   SplitBefore
00216 ///   Tail
00217 /// After:
00218 ///   Head
00219 ///   if (Cond)
00220 ///     ThenBlock
00221 ///   else
00222 ///     ElseBlock
00223 ///   SplitBefore
00224 ///   Tail
00225 void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore,
00226                                    TerminatorInst **ThenTerm,
00227                                    TerminatorInst **ElseTerm,
00228                                    MDNode *BranchWeights = nullptr);
00229 
00230 ///
00231 /// GetIfCondition - Check whether BB is the merge point of a if-region.
00232 /// If so, return the boolean condition that determines which entry into
00233 /// BB will be taken.  Also, return by references the block that will be
00234 /// entered from if the condition is true, and the block that will be
00235 /// entered if the condition is false.
00236 Value *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue,
00237                       BasicBlock *&IfFalse);
00238 } // End llvm namespace
00239 
00240 #endif