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 21namespace llvm { 22 23class BasicBlock; 24class DominatorTree; 25class Function; 26class Instruction; 27class LoopInfo; 28class 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. 35void 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. 43unsigned 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/// 49bool 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. 67bool 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. 77bool isPotentiallyReachable(const BasicBlock *From, const BasicBlock *To, 78 const DominatorTree *DT = nullptr, 79 const LoopInfo *LI = nullptr); 80 81} // End llvm namespace 82 83#endif 84