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, const 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 |
168 | |