| 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/Support/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 = 0, |
| 69 |
const LoopInfo *LI = 0); |
| 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 = 0, |
| 79 |
const LoopInfo *LI = 0); |
| 80 |
|
| 81 |
} // End llvm namespace |
| 82 |
|
| 83 |
#endif |
