LLVM  13.0.0git
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/ADT/GraphTraits.h"
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include <utility>
20 
21 namespace llvm {
22 
23 class BasicBlock;
24 class DominatorTree;
25 class Function;
26 class Instruction;
27 class LoopInfo;
28 template <typename T> class SmallVectorImpl;
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 Instruction *TI, unsigned SuccNum,
50  bool AllowIdenticalEdges = false);
51 bool isCriticalEdge(const Instruction *TI, const BasicBlock *Succ,
52  bool AllowIdenticalEdges = false);
53 
54 /// Determine whether instruction 'To' is reachable from 'From', without passing
55 /// through any blocks in ExclusionSet, returning true if uncertain.
56 ///
57 /// Determine whether there is a path from From to To within a single function.
58 /// Returns false only if we can prove that once 'From' has been executed then
59 /// 'To' can not be executed. Conservatively returns true.
60 ///
61 /// This function is linear with respect to the number of blocks in the CFG,
62 /// walking down successors from From to reach To, with a fixed threshold.
63 /// Using DT or LI allows us to answer more quickly. LI reduces the cost of
64 /// an entire loop of any number of blocks to be the same as the cost of a
65 /// single block. DT reduces the cost by allowing the search to terminate when
66 /// we find a block that dominates the block containing 'To'. DT is most useful
67 /// on branchy code but not loops, and LI is most useful on code with loops but
68 /// does not help on branchy code outside loops.
70  const Instruction *From, const Instruction *To,
71  const SmallPtrSetImpl<BasicBlock *> *ExclusionSet = nullptr,
72  const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr);
73 
74 /// Determine whether block 'To' is reachable from 'From', returning
75 /// true if uncertain.
76 ///
77 /// Determine whether there is a path from From to To within a single function.
78 /// Returns false only if we can prove that once 'From' has been reached then
79 /// 'To' can not be executed. Conservatively returns true.
80 bool isPotentiallyReachable(const BasicBlock *From, const BasicBlock *To,
81  const DominatorTree *DT = nullptr,
82  const LoopInfo *LI = nullptr);
83 
84 /// Determine whether there is at least one path from a block in
85 /// 'Worklist' to 'StopBB', returning true if uncertain.
86 ///
87 /// Determine whether there is a path from at least one block in Worklist to
88 /// StopBB within a single function. Returns false only if we can prove that
89 /// once any block in 'Worklist' has been reached then 'StopBB' can not be
90 /// executed. Conservatively returns true.
91 bool isPotentiallyReachableFromMany(SmallVectorImpl<BasicBlock *> &Worklist,
92  BasicBlock *StopBB,
93  const DominatorTree *DT = nullptr,
94  const LoopInfo *LI = nullptr);
95 
96 /// Determine whether there is at least one path from a block in
97 /// 'Worklist' to 'StopBB' without passing through any blocks in
98 /// 'ExclusionSet', returning true if uncertain.
99 ///
100 /// Determine whether there is a path from at least one block in Worklist to
101 /// StopBB within a single function without passing through any of the blocks
102 /// in 'ExclusionSet'. Returns false only if we can prove that once any block
103 /// in 'Worklist' has been reached then 'StopBB' can not be executed.
104 /// Conservatively returns true.
106  SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB,
107  const SmallPtrSetImpl<BasicBlock *> *ExclusionSet,
108  const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr);
109 
110 /// Return true if the control flow in \p RPOTraversal is irreducible.
111 ///
112 /// This is a generic implementation to detect CFG irreducibility based on loop
113 /// info analysis. It can be used for any kind of CFG (Loop, MachineLoop,
114 /// Function, MachineFunction, etc.) by providing an RPO traversal (\p
115 /// RPOTraversal) and the loop info analysis (\p LI) of the CFG. This utility
116 /// function is only recommended when loop info analysis is available. If loop
117 /// info analysis isn't available, please, don't compute it explicitly for this
118 /// purpose. There are more efficient ways to detect CFG irreducibility that
119 /// don't require recomputing loop info analysis (e.g., T1/T2 or Tarjan's
120 /// algorithm).
121 ///
122 /// Requirements:
123 /// 1) GraphTraits must be implemented for NodeT type. It is used to access
124 /// NodeT successors.
125 // 2) \p RPOTraversal must be a valid reverse post-order traversal of the
126 /// target CFG with begin()/end() iterator interfaces.
127 /// 3) \p LI must be a valid LoopInfoBase that contains up-to-date loop
128 /// analysis information of the CFG.
129 ///
130 /// This algorithm uses the information about reducible loop back-edges already
131 /// computed in \p LI. When a back-edge is found during the RPO traversal, the
132 /// algorithm checks whether the back-edge is one of the reducible back-edges in
133 /// loop info. If it isn't, the CFG is irreducible. For example, for the CFG
134 /// below (canonical irreducible graph) loop info won't contain any loop, so the
135 /// algorithm will return that the CFG is irreducible when checking the B <-
136 /// -> C back-edge.
137 ///
138 /// (A->B, A->C, B->C, C->B, C->D)
139 /// A
140 /// / \
141 /// B<- ->C
142 /// |
143 /// D
144 ///
145 template <class NodeT, class RPOTraversalT, class LoopInfoT,
146  class GT = GraphTraits<NodeT>>
147 bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI) {
148  /// Check whether the edge (\p Src, \p Dst) is a reducible loop backedge
149  /// according to LI. I.e., check if there exists a loop that contains Src and
150  /// where Dst is the loop header.
151  auto isProperBackedge = [&](NodeT Src, NodeT Dst) {
152  for (const auto *Lp = LI.getLoopFor(Src); Lp; Lp = Lp->getParentLoop()) {
153  if (Lp->getHeader() == Dst)
154  return true;
155  }
156  return false;
157  };
158 
159  SmallPtrSet<NodeT, 32> Visited;
160  for (NodeT Node : RPOTraversal) {
161  Visited.insert(Node);
162  for (NodeT Succ : make_range(GT::child_begin(Node), GT::child_end(Node))) {
163  // Succ hasn't been visited yet
164  if (!Visited.count(Succ))
165  continue;
166  // We already visited Succ, thus Node->Succ must be a backedge. Check that
167  // the head matches what we have in the loop information. Otherwise, we
168  // have an irreducible graph.
169  if (!isProperBackedge(Node, Succ))
170  return true;
171  }
172  }
173 
174  return false;
175 }
176 } // End llvm namespace
177 
178 #endif
llvm
Definition: AllocatorList.h:23
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::isPotentiallyReachableFromMany
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 'Worklist' to 'StopBB',...
llvm::FindFunctionBackedges
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:34
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::isCriticalEdge
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition: CFG.cpp:95
F
#define F(x, y, z)
Definition: MD5.cpp:56
GraphTraits.h
llvm::isPotentiallyReachable
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...
Definition: CFG.cpp:223
SmallPtrSet.h
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:64
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::GetSuccessorNumber
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:79
Node
Definition: ItaniumDemangle.h:114
llvm::AArch64CC::GT
@ GT
Definition: AArch64BaseInfo.h:248
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::containsIrreducibleCFG
bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI)
Return true if the control flow in RPOTraversal is irreducible.
Definition: CFG.h:147
llvm::SmallPtrSetImpl::insert
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:364