LLVM  10.0.0svn
CFG.h
Go to the documentation of this file.
1 //===-- Analysis/CFG.h - BasicBlock Analyses --------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This family of functions performs analyses on basic blocks, and instructions
10 // contained within basic blocks.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_ANALYSIS_CFG_H
15 #define LLVM_ANALYSIS_CFG_H
16 
17 #include "llvm/IR/BasicBlock.h"
18 #include "llvm/IR/CFG.h"
19 
20 namespace llvm {
21 
22 class BasicBlock;
23 class DominatorTree;
24 class Function;
25 class Instruction;
26 class LoopInfo;
27 
28 /// Analyze the specified function to find all of the loop backedges in the
29 /// function and return them. This is a relatively cheap (compared to
30 /// computing dominators and loop info) analysis.
31 ///
32 /// The output is added to Result, as pairs of <from,to> edge info.
34  const Function &F,
35  SmallVectorImpl<std::pair<const BasicBlock *, const BasicBlock *> > &
36  Result);
37 
38 /// Search for the specified successor of basic block BB and return its position
39 /// in the terminator instruction's list of successors. It is an error to call
40 /// this with a block that is not a successor.
41 unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ);
42 
43 /// Return true if the specified edge is a critical edge. Critical edges are
44 /// edges from a block with multiple successors to a block with multiple
45 /// predecessors.
46 ///
47 bool isCriticalEdge(const Instruction *TI, unsigned SuccNum,
48  bool AllowIdenticalEdges = false);
49 bool isCriticalEdge(const Instruction *TI, const BasicBlock *Succ,
50  bool AllowIdenticalEdges = false);
51 
52 /// Determine whether instruction 'To' is reachable from 'From', without passing
53 /// through any blocks in ExclusionSet, 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.
68  const Instruction *From, const Instruction *To,
69  const SmallPtrSetImpl<BasicBlock *> *ExclusionSet = nullptr,
70  const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr);
71 
72 /// Determine whether block 'To' is reachable from 'From', returning
73 /// true if uncertain.
74 ///
75 /// Determine whether there is a path from From to To within a single function.
76 /// Returns false only if we can prove that once 'From' has been reached then
77 /// 'To' can not be executed. Conservatively returns true.
78 bool isPotentiallyReachable(const BasicBlock *From, const BasicBlock *To,
79  const DominatorTree *DT = nullptr,
80  const LoopInfo *LI = nullptr);
81 
82 /// Determine whether there is at least one path from a block in
83 /// 'Worklist' to 'StopBB', returning true if uncertain.
84 ///
85 /// Determine whether there is a path from at least one block in Worklist to
86 /// StopBB within a single function. Returns false only if we can prove that
87 /// once any block in 'Worklist' has been reached then 'StopBB' can not be
88 /// executed. Conservatively returns true.
89 bool isPotentiallyReachableFromMany(SmallVectorImpl<BasicBlock *> &Worklist,
90  BasicBlock *StopBB,
91  const DominatorTree *DT = nullptr,
92  const LoopInfo *LI = nullptr);
93 
94 /// Determine whether there is at least one path from a block in
95 /// 'Worklist' to 'StopBB' without passing through any blocks in
96 /// 'ExclusionSet', returning true if uncertain.
97 ///
98 /// Determine whether there is a path from at least one block in Worklist to
99 /// StopBB within a single function without passing through any of the blocks
100 /// in 'ExclusionSet'. Returns false only if we can prove that once any block
101 /// in 'Worklist' has been reached then 'StopBB' can not be executed.
102 /// Conservatively returns true.
104  SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB,
105  const SmallPtrSetImpl<BasicBlock *> *ExclusionSet,
106  const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr);
107 
108 /// Return true if the control flow in \p RPOTraversal is irreducible.
109 ///
110 /// This is a generic implementation to detect CFG irreducibility based on loop
111 /// info analysis. It can be used for any kind of CFG (Loop, MachineLoop,
112 /// Function, MachineFunction, etc.) by providing an RPO traversal (\p
113 /// RPOTraversal) and the loop info analysis (\p LI) of the CFG. This utility
114 /// function is only recommended when loop info analysis is available. If loop
115 /// info analysis isn't available, please, don't compute it explicitly for this
116 /// purpose. There are more efficient ways to detect CFG irreducibility that
117 /// don't require recomputing loop info analysis (e.g., T1/T2 or Tarjan's
118 /// algorithm).
119 ///
120 /// Requirements:
121 /// 1) GraphTraits must be implemented for NodeT type. It is used to access
122 /// NodeT successors.
123 // 2) \p RPOTraversal must be a valid reverse post-order traversal of the
124 /// target CFG with begin()/end() iterator interfaces.
125 /// 3) \p LI must be a valid LoopInfoBase that contains up-to-date loop
126 /// analysis information of the CFG.
127 ///
128 /// This algorithm uses the information about reducible loop back-edges already
129 /// computed in \p LI. When a back-edge is found during the RPO traversal, the
130 /// algorithm checks whether the back-edge is one of the reducible back-edges in
131 /// loop info. If it isn't, the CFG is irreducible. For example, for the CFG
132 /// below (canonical irreducible graph) loop info won't contain any loop, so the
133 /// algorithm will return that the CFG is irreducible when checking the B <-
134 /// -> C back-edge.
135 ///
136 /// (A->B, A->C, B->C, C->B, C->D)
137 /// A
138 /// / \
139 /// B<- ->C
140 /// |
141 /// D
142 ///
143 template <class NodeT, class RPOTraversalT, class LoopInfoT,
144  class GT = GraphTraits<NodeT>>
145 bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI) {
146  /// Check whether the edge (\p Src, \p Dst) is a reducible loop backedge
147  /// according to LI. I.e., check if there exists a loop that contains Src and
148  /// where Dst is the loop header.
149  auto isProperBackedge = [&](NodeT Src, NodeT Dst) {
150  for (const auto *Lp = LI.getLoopFor(Src); Lp; Lp = Lp->getParentLoop()) {
151  if (Lp->getHeader() == Dst)
152  return true;
153  }
154  return false;
155  };
156 
157  SmallPtrSet<NodeT, 32> Visited;
158  for (NodeT Node : RPOTraversal) {
159  Visited.insert(Node);
160  for (NodeT Succ : make_range(GT::child_begin(Node), GT::child_end(Node))) {
161  // Succ hasn't been visited yet
162  if (!Visited.count(Succ))
163  continue;
164  // We already visited Succ, thus Node->Succ must be a backedge. Check that
165  // the head matches what we have in the loop information. Otherwise, we
166  // have an irreducible graph.
167  if (!isProperBackedge(Node, Succ))
168  return true;
169  }
170  }
171 
172  return false;
173 }
174 } // End llvm namespace
175 
176 #endif
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Various leaf nodes.
Definition: ISDOpcodes.h:59
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock *> *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction &#39;To&#39; is reachable from &#39;From&#39;, without passing through any blocks in Ex...
Definition: CFG.cpp:218
F(f)
bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI)
Return true if the control flow in RPOTraversal is irreducible.
Definition: CFG.h:145
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition: CFG.cpp:88
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
BlockVerifier::State From
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
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.