CFG.h revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338 
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 = 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.
77bool 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
84