LLVM  6.0.0svn
CFG.h
Go to the documentation of this file.
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.
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
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Various leaf nodes.
Definition: ISDOpcodes.h:60
F(f)
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction &#39;To&#39; is reachable from &#39;From&#39;, returning true if uncertain.
Definition: CFG.cpp:186
unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ)
Search for the specified successor of basic block BB and return its position in the terminator instru...
Definition: CFG.cpp:72
void FindFunctionBackedges(const Function &F, SmallVectorImpl< std::pair< const BasicBlock *, const BasicBlock *> > &Result)
Analyze the specified function to find all of the loop backedges in the function and return them...
Definition: CFG.cpp:27
bool isPotentiallyReachableFromMany(SmallVectorImpl< BasicBlock *> &Worklist, BasicBlock *StopBB, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether there is at least one path from a block in &#39;Worklist&#39; to &#39;StopBB&#39;, returning true if uncertain.
Definition: CFG.cpp:130
bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition: CFG.cpp:88