LLVM 20.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
19#include <utility>
20
21namespace llvm {
22
23class BasicBlock;
24class DominatorTree;
25class Function;
26class Instruction;
27class LoopInfo;
28template <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.
43unsigned 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///
49bool isCriticalEdge(const Instruction *TI, unsigned SuccNum,
50 bool AllowIdenticalEdges = false);
51bool 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.
81 const BasicBlock *From, const BasicBlock *To,
82 const SmallPtrSetImpl<BasicBlock *> *ExclusionSet = nullptr,
83 const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr);
84
85/// Determine whether there is at least one path from a block in
86/// 'Worklist' to 'StopBB' without passing through any blocks in
87/// 'ExclusionSet', returning true if uncertain.
88///
89/// Determine whether there is a path from at least one block in Worklist to
90/// StopBB within a single function without passing through any of the blocks
91/// in 'ExclusionSet'. Returns false only if we can prove that once any block
92/// in 'Worklist' has been reached then 'StopBB' can not be executed.
93/// Conservatively returns true.
95 SmallVectorImpl<BasicBlock *> &Worklist, const BasicBlock *StopBB,
96 const SmallPtrSetImpl<BasicBlock *> *ExclusionSet,
97 const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr);
98
99/// Determine whether there is a potentially a path from at least one block in
100/// 'Worklist' to at least one block in 'StopSet' within a single function
101/// without passing through any of the blocks in 'ExclusionSet'. Returns false
102/// only if we can prove that once any block in 'Worklist' has been reached then
103/// no blocks in 'StopSet' can be executed without passing through any blocks in
104/// 'ExclusionSet'. Conservatively returns true.
106 SmallVectorImpl<BasicBlock *> &Worklist,
107 const SmallPtrSetImpl<const BasicBlock *> &StopSet,
108 const SmallPtrSetImpl<BasicBlock *> *ExclusionSet,
109 const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr);
110
111/// Return true if the control flow in \p RPOTraversal is irreducible.
112///
113/// This is a generic implementation to detect CFG irreducibility based on loop
114/// info analysis. It can be used for any kind of CFG (Loop, MachineLoop,
115/// Function, MachineFunction, etc.) by providing an RPO traversal (\p
116/// RPOTraversal) and the loop info analysis (\p LI) of the CFG. This utility
117/// function is only recommended when loop info analysis is available. If loop
118/// info analysis isn't available, please, don't compute it explicitly for this
119/// purpose. There are more efficient ways to detect CFG irreducibility that
120/// don't require recomputing loop info analysis (e.g., T1/T2 or Tarjan's
121/// algorithm).
122///
123/// Requirements:
124/// 1) GraphTraits must be implemented for NodeT type. It is used to access
125/// NodeT successors.
126// 2) \p RPOTraversal must be a valid reverse post-order traversal of the
127/// target CFG with begin()/end() iterator interfaces.
128/// 3) \p LI must be a valid LoopInfoBase that contains up-to-date loop
129/// analysis information of the CFG.
130///
131/// This algorithm uses the information about reducible loop back-edges already
132/// computed in \p LI. When a back-edge is found during the RPO traversal, the
133/// algorithm checks whether the back-edge is one of the reducible back-edges in
134/// loop info. If it isn't, the CFG is irreducible. For example, for the CFG
135/// below (canonical irreducible graph) loop info won't contain any loop, so the
136/// algorithm will return that the CFG is irreducible when checking the B <-
137/// -> C back-edge.
138///
139/// (A->B, A->C, B->C, C->B, C->D)
140/// A
141/// / \
142/// B<- ->C
143/// |
144/// D
145///
146template <class NodeT, class RPOTraversalT, class LoopInfoT,
147 class GT = GraphTraits<NodeT>>
148bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI) {
149 /// Check whether the edge (\p Src, \p Dst) is a reducible loop backedge
150 /// according to LI. I.e., check if there exists a loop that contains Src and
151 /// where Dst is the loop header.
152 auto isProperBackedge = [&](NodeT Src, NodeT Dst) {
153 for (const auto *Lp = LI.getLoopFor(Src); Lp; Lp = Lp->getParentLoop()) {
154 if (Lp->getHeader() == Dst)
155 return true;
156 }
157 return false;
158 };
159
161 for (NodeT Node : RPOTraversal) {
162 Visited.insert(Node);
163 for (NodeT Succ : make_range(GT::child_begin(Node), GT::child_end(Node))) {
164 // Succ hasn't been visited yet
165 if (!Visited.count(Succ))
166 continue;
167 // We already visited Succ, thus Node->Succ must be a backedge. Check that
168 // the head matches what we have in the loop information. Otherwise, we
169 // have an irreducible graph.
170 if (!isProperBackedge(Node, Succ))
171 return true;
172 }
173 }
174
175 return false;
176}
177} // End llvm namespace
178
179#endif
BlockVerifier::State From
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
#define F(x, y, z)
Definition: MD5.cpp:55
This file defines the SmallPtrSet class.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:436
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:368
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:503
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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
bool isPotentiallyReachableFromMany(SmallVectorImpl< BasicBlock * > &Worklist, const BasicBlock *StopBB, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether there is at least one path from a block in 'Worklist' to 'StopBB' without passing t...
Definition: CFG.cpp:239
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI)
Return true if the control flow in RPOTraversal is irreducible.
Definition: CFG.h:148
bool isManyPotentiallyReachableFromMany(SmallVectorImpl< BasicBlock * > &Worklist, const SmallPtrSetImpl< const BasicBlock * > &StopSet, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether there is a potentially a path from at least one block in 'Worklist' to at least one...
Definition: CFG.cpp:248
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition: CFG.cpp:95
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
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:281