LLVM  14.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.
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, BasicBlock *StopBB,
96  const SmallPtrSetImpl<BasicBlock *> *ExclusionSet,
97  const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr);
98 
99 /// Return true if the control flow in \p RPOTraversal is irreducible.
100 ///
101 /// This is a generic implementation to detect CFG irreducibility based on loop
102 /// info analysis. It can be used for any kind of CFG (Loop, MachineLoop,
103 /// Function, MachineFunction, etc.) by providing an RPO traversal (\p
104 /// RPOTraversal) and the loop info analysis (\p LI) of the CFG. This utility
105 /// function is only recommended when loop info analysis is available. If loop
106 /// info analysis isn't available, please, don't compute it explicitly for this
107 /// purpose. There are more efficient ways to detect CFG irreducibility that
108 /// don't require recomputing loop info analysis (e.g., T1/T2 or Tarjan's
109 /// algorithm).
110 ///
111 /// Requirements:
112 /// 1) GraphTraits must be implemented for NodeT type. It is used to access
113 /// NodeT successors.
114 // 2) \p RPOTraversal must be a valid reverse post-order traversal of the
115 /// target CFG with begin()/end() iterator interfaces.
116 /// 3) \p LI must be a valid LoopInfoBase that contains up-to-date loop
117 /// analysis information of the CFG.
118 ///
119 /// This algorithm uses the information about reducible loop back-edges already
120 /// computed in \p LI. When a back-edge is found during the RPO traversal, the
121 /// algorithm checks whether the back-edge is one of the reducible back-edges in
122 /// loop info. If it isn't, the CFG is irreducible. For example, for the CFG
123 /// below (canonical irreducible graph) loop info won't contain any loop, so the
124 /// algorithm will return that the CFG is irreducible when checking the B <-
125 /// -> C back-edge.
126 ///
127 /// (A->B, A->C, B->C, C->B, C->D)
128 /// A
129 /// / \
130 /// B<- ->C
131 /// |
132 /// D
133 ///
134 template <class NodeT, class RPOTraversalT, class LoopInfoT,
135  class GT = GraphTraits<NodeT>>
136 bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI) {
137  /// Check whether the edge (\p Src, \p Dst) is a reducible loop backedge
138  /// according to LI. I.e., check if there exists a loop that contains Src and
139  /// where Dst is the loop header.
140  auto isProperBackedge = [&](NodeT Src, NodeT Dst) {
141  for (const auto *Lp = LI.getLoopFor(Src); Lp; Lp = Lp->getParentLoop()) {
142  if (Lp->getHeader() == Dst)
143  return true;
144  }
145  return false;
146  };
147 
148  SmallPtrSet<NodeT, 32> Visited;
149  for (NodeT Node : RPOTraversal) {
150  Visited.insert(Node);
151  for (NodeT Succ : make_range(GT::child_begin(Node), GT::child_end(Node))) {
152  // Succ hasn't been visited yet
153  if (!Visited.count(Succ))
154  continue;
155  // We already visited Succ, thus Node->Succ must be a backedge. Check that
156  // the head matches what we have in the loop information. Otherwise, we
157  // have an irreducible graph.
158  if (!isProperBackedge(Node, Succ))
159  return true;
160  }
161  }
162 
163  return false;
164 }
165 } // End llvm namespace
166 
167 #endif
llvm
---------------------— PointerInfo ------------------------------------—
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 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:137
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:236
SmallPtrSet.h
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
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:235
llvm::AArch64CC::GT
@ GT
Definition: AArch64BaseInfo.h:267
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:136
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