1 //===-- Analysis/CFG.h - BasicBlock Analyses --------------------*- 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 performs analyses on basic blocks, and instructions 11 // contained within basic blocks. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_ANALYSIS_CFG_H 16 #define LLVM_ANALYSIS_CFG_H 17 18 #include "llvm/IR/BasicBlock.h" 19 #include "llvm/IR/CFG.h" 20 21 namespace llvm { 22 23 class BasicBlock; 24 class DominatorTree; 25 class Function; 26 class Instruction; 27 class LoopInfo; 28 class TerminatorInst; 29 30 /// Analyze the specified function to find all of the loop backedges in the 31 /// function and return them. This is a relatively cheap (compared to 32 /// computing dominators and loop info) analysis. 33 /// 34 /// The output is added to Result, as pairs of <from,to> edge info. 35 void FindFunctionBackedges( 36 const Function &F, 37 SmallVectorImpl<std::pair<const BasicBlock *, const BasicBlock *> > & 38 Result); 39 40 /// Search for the specified successor of basic block BB and return its position 41 /// in the terminator instruction's list of successors. It is an error to call 42 /// this with a block that is not a successor. 43 unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ); 44 45 /// Return true if the specified edge is a critical edge. Critical edges are 46 /// edges from a block with multiple successors to a block with multiple 47 /// predecessors. 48 /// 49 bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, 50 bool AllowIdenticalEdges = false); 51 52 /// \brief Determine whether instruction 'To' is reachable from 'From', 53 /// returning true if uncertain. 54 /// 55 /// Determine whether there is a path from From to To within a single function. 56 /// Returns false only if we can prove that once 'From' has been executed then 57 /// 'To' can not be executed. Conservatively returns true. 58 /// 59 /// This function is linear with respect to the number of blocks in the CFG, 60 /// walking down successors from From to reach To, with a fixed threshold. 61 /// Using DT or LI allows us to answer more quickly. LI reduces the cost of 62 /// an entire loop of any number of blocks to be the same as the cost of a 63 /// single block. DT reduces the cost by allowing the search to terminate when 64 /// we find a block that dominates the block containing 'To'. DT is most useful 65 /// on branchy code but not loops, and LI is most useful on code with loops but 66 /// does not help on branchy code outside loops. 67 bool isPotentiallyReachable(const Instruction *From, const Instruction *To, 68 const DominatorTree *DT = nullptr, 69 const LoopInfo *LI = nullptr); 70 71 /// \brief Determine whether block 'To' is reachable from 'From', returning 72 /// true if uncertain. 73 /// 74 /// Determine whether there is a path from From to To within a single function. 75 /// Returns false only if we can prove that once 'From' has been reached then 76 /// 'To' can not be executed. Conservatively returns true. 77 bool isPotentiallyReachable(const BasicBlock *From, const BasicBlock *To, 78 const DominatorTree *DT = nullptr, 79 const LoopInfo *LI = nullptr); 80 81 /// \brief Determine whether there is at least one path from a block in 82 /// 'Worklist' to 'StopBB', returning true if uncertain. 83 /// 84 /// Determine whether there is a path from at least one block in Worklist to 85 /// StopBB within a single function. Returns false only if we can prove that 86 /// once any block in 'Worklist' has been reached then 'StopBB' can not be 87 /// executed. Conservatively returns true. 88 bool isPotentiallyReachableFromMany(SmallVectorImpl<BasicBlock *> &Worklist, 89 BasicBlock *StopBB, 90 const DominatorTree *DT = nullptr, 91 const LoopInfo *LI = nullptr); 92 } // End llvm namespace 93 94 #endif 95
