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.
35 void FindFunctionBackedges(
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.
69 bool isPotentiallyReachable(
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(
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.
94 bool isPotentiallyReachableFromMany(
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>>
containsIrreducibleCFG(RPOTraversalT & RPOTraversal,const LoopInfoT & LI)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
168