include/llvm/Analysis/CFG.h

   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(BasicBlock *BB, 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 blocsk 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