1 | //===-- CFG.cpp - BasicBlock analysis --------------------------------------==// |
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 | #include "llvm/Analysis/CFG.h" |
15 | #include "llvm/Analysis/LoopInfo.h" |
16 | #include "llvm/IR/Dominators.h" |
17 | #include "llvm/Support/CommandLine.h" |
18 | |
19 | using namespace llvm; |
20 | |
21 | // The max number of basic blocks explored during reachability analysis between |
22 | // two basic blocks. This is kept reasonably small to limit compile time when |
23 | // repeatedly used by clients of this analysis (such as captureTracking). |
24 | static cl::opt<unsigned> DefaultMaxBBsToExplore( |
25 | "dom-tree-reachability-max-bbs-to-explore" , cl::Hidden, |
26 | cl::desc("Max number of BBs to explore for reachability analysis" ), |
27 | cl::init(Val: 32)); |
28 | |
29 | /// FindFunctionBackedges - Analyze the specified function to find all of the |
30 | /// loop backedges in the function and return them. This is a relatively cheap |
31 | /// (compared to computing dominators and loop info) analysis. |
32 | /// |
33 | /// The output is added to Result, as pairs of <from,to> edge info. |
34 | void llvm::FindFunctionBackedges(const Function &F, |
35 | SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) { |
36 | const BasicBlock *BB = &F.getEntryBlock(); |
37 | if (succ_empty(BB)) |
38 | return; |
39 | |
40 | SmallPtrSet<const BasicBlock*, 8> Visited; |
41 | SmallVector<std::pair<const BasicBlock *, const_succ_iterator>, 8> VisitStack; |
42 | SmallPtrSet<const BasicBlock*, 8> InStack; |
43 | |
44 | Visited.insert(Ptr: BB); |
45 | VisitStack.push_back(Elt: std::make_pair(x&: BB, y: succ_begin(BB))); |
46 | InStack.insert(Ptr: BB); |
47 | do { |
48 | std::pair<const BasicBlock *, const_succ_iterator> &Top = VisitStack.back(); |
49 | const BasicBlock *ParentBB = Top.first; |
50 | const_succ_iterator &I = Top.second; |
51 | |
52 | bool FoundNew = false; |
53 | while (I != succ_end(BB: ParentBB)) { |
54 | BB = *I++; |
55 | if (Visited.insert(Ptr: BB).second) { |
56 | FoundNew = true; |
57 | break; |
58 | } |
59 | // Successor is in VisitStack, it's a back edge. |
60 | if (InStack.count(Ptr: BB)) |
61 | Result.push_back(Elt: std::make_pair(x&: ParentBB, y&: BB)); |
62 | } |
63 | |
64 | if (FoundNew) { |
65 | // Go down one level if there is a unvisited successor. |
66 | InStack.insert(Ptr: BB); |
67 | VisitStack.push_back(Elt: std::make_pair(x&: BB, y: succ_begin(BB))); |
68 | } else { |
69 | // Go up one level. |
70 | InStack.erase(Ptr: VisitStack.pop_back_val().first); |
71 | } |
72 | } while (!VisitStack.empty()); |
73 | } |
74 | |
75 | /// GetSuccessorNumber - Search for the specified successor of basic block BB |
76 | /// and return its position in the terminator instruction's list of |
77 | /// successors. It is an error to call this with a block that is not a |
78 | /// successor. |
79 | unsigned llvm::GetSuccessorNumber(const BasicBlock *BB, |
80 | const BasicBlock *Succ) { |
81 | const Instruction *Term = BB->getTerminator(); |
82 | #ifndef NDEBUG |
83 | unsigned e = Term->getNumSuccessors(); |
84 | #endif |
85 | for (unsigned i = 0; ; ++i) { |
86 | assert(i != e && "Didn't find edge?" ); |
87 | if (Term->getSuccessor(Idx: i) == Succ) |
88 | return i; |
89 | } |
90 | } |
91 | |
92 | /// isCriticalEdge - Return true if the specified edge is a critical edge. |
93 | /// Critical edges are edges from a block with multiple successors to a block |
94 | /// with multiple predecessors. |
95 | bool llvm::isCriticalEdge(const Instruction *TI, unsigned SuccNum, |
96 | bool AllowIdenticalEdges) { |
97 | assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!" ); |
98 | return isCriticalEdge(TI, Succ: TI->getSuccessor(Idx: SuccNum), AllowIdenticalEdges); |
99 | } |
100 | |
101 | bool llvm::isCriticalEdge(const Instruction *TI, const BasicBlock *Dest, |
102 | bool AllowIdenticalEdges) { |
103 | assert(TI->isTerminator() && "Must be a terminator to have successors!" ); |
104 | if (TI->getNumSuccessors() == 1) return false; |
105 | |
106 | assert(is_contained(predecessors(Dest), TI->getParent()) && |
107 | "No edge between TI's block and Dest." ); |
108 | |
109 | const_pred_iterator I = pred_begin(BB: Dest), E = pred_end(BB: Dest); |
110 | |
111 | // If there is more than one predecessor, this is a critical edge... |
112 | assert(I != E && "No preds, but we have an edge to the block?" ); |
113 | const BasicBlock *FirstPred = *I; |
114 | ++I; // Skip one edge due to the incoming arc from TI. |
115 | if (!AllowIdenticalEdges) |
116 | return I != E; |
117 | |
118 | // If AllowIdenticalEdges is true, then we allow this edge to be considered |
119 | // non-critical iff all preds come from TI's block. |
120 | for (; I != E; ++I) |
121 | if (*I != FirstPred) |
122 | return true; |
123 | return false; |
124 | } |
125 | |
126 | // LoopInfo contains a mapping from basic block to the innermost loop. Find |
127 | // the outermost loop in the loop nest that contains BB. |
128 | static const Loop *getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB) { |
129 | const Loop *L = LI->getLoopFor(BB); |
130 | return L ? L->getOutermostLoop() : nullptr; |
131 | } |
132 | |
133 | bool llvm::isPotentiallyReachableFromMany( |
134 | SmallVectorImpl<BasicBlock *> &Worklist, const BasicBlock *StopBB, |
135 | const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT, |
136 | const LoopInfo *LI) { |
137 | // When the stop block is unreachable, it's dominated from everywhere, |
138 | // regardless of whether there's a path between the two blocks. |
139 | if (DT && !DT->isReachableFromEntry(A: StopBB)) |
140 | DT = nullptr; |
141 | |
142 | // We can't skip directly from a block that dominates the stop block if the |
143 | // exclusion block is potentially in between. |
144 | if (ExclusionSet && !ExclusionSet->empty()) |
145 | DT = nullptr; |
146 | |
147 | // Normally any block in a loop is reachable from any other block in a loop, |
148 | // however excluded blocks might partition the body of a loop to make that |
149 | // untrue. |
150 | SmallPtrSet<const Loop *, 8> LoopsWithHoles; |
151 | if (LI && ExclusionSet) { |
152 | for (auto *BB : *ExclusionSet) { |
153 | if (const Loop *L = getOutermostLoop(LI, BB)) |
154 | LoopsWithHoles.insert(Ptr: L); |
155 | } |
156 | } |
157 | |
158 | const Loop *StopLoop = LI ? getOutermostLoop(LI, BB: StopBB) : nullptr; |
159 | |
160 | unsigned Limit = DefaultMaxBBsToExplore; |
161 | SmallPtrSet<const BasicBlock*, 32> Visited; |
162 | do { |
163 | BasicBlock *BB = Worklist.pop_back_val(); |
164 | if (!Visited.insert(Ptr: BB).second) |
165 | continue; |
166 | if (BB == StopBB) |
167 | return true; |
168 | if (ExclusionSet && ExclusionSet->count(Ptr: BB)) |
169 | continue; |
170 | if (DT && DT->dominates(A: BB, B: StopBB)) |
171 | return true; |
172 | |
173 | const Loop *Outer = nullptr; |
174 | if (LI) { |
175 | Outer = getOutermostLoop(LI, BB); |
176 | // If we're in a loop with a hole, not all blocks in the loop are |
177 | // reachable from all other blocks. That implies we can't simply jump to |
178 | // the loop's exit blocks, as that exit might need to pass through an |
179 | // excluded block. Clear Outer so we process BB's successors. |
180 | if (LoopsWithHoles.count(Ptr: Outer)) |
181 | Outer = nullptr; |
182 | if (StopLoop && Outer == StopLoop) |
183 | return true; |
184 | } |
185 | |
186 | if (!--Limit) { |
187 | // We haven't been able to prove it one way or the other. Conservatively |
188 | // answer true -- that there is potentially a path. |
189 | return true; |
190 | } |
191 | |
192 | if (Outer) { |
193 | // All blocks in a single loop are reachable from all other blocks. From |
194 | // any of these blocks, we can skip directly to the exits of the loop, |
195 | // ignoring any other blocks inside the loop body. |
196 | Outer->getExitBlocks(ExitBlocks&: Worklist); |
197 | } else { |
198 | Worklist.append(in_start: succ_begin(BB), in_end: succ_end(BB)); |
199 | } |
200 | } while (!Worklist.empty()); |
201 | |
202 | // We have exhausted all possible paths and are certain that 'To' can not be |
203 | // reached from 'From'. |
204 | return false; |
205 | } |
206 | |
207 | bool llvm::isPotentiallyReachable( |
208 | const BasicBlock *A, const BasicBlock *B, |
209 | const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT, |
210 | const LoopInfo *LI) { |
211 | assert(A->getParent() == B->getParent() && |
212 | "This analysis is function-local!" ); |
213 | |
214 | if (DT) { |
215 | if (DT->isReachableFromEntry(A) && !DT->isReachableFromEntry(A: B)) |
216 | return false; |
217 | if (!ExclusionSet || ExclusionSet->empty()) { |
218 | if (A->isEntryBlock() && DT->isReachableFromEntry(A: B)) |
219 | return true; |
220 | if (B->isEntryBlock() && DT->isReachableFromEntry(A)) |
221 | return false; |
222 | } |
223 | } |
224 | |
225 | SmallVector<BasicBlock*, 32> Worklist; |
226 | Worklist.push_back(Elt: const_cast<BasicBlock*>(A)); |
227 | |
228 | return isPotentiallyReachableFromMany(Worklist, StopBB: B, ExclusionSet, DT, LI); |
229 | } |
230 | |
231 | bool llvm::isPotentiallyReachable( |
232 | const Instruction *A, const Instruction *B, |
233 | const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT, |
234 | const LoopInfo *LI) { |
235 | assert(A->getParent()->getParent() == B->getParent()->getParent() && |
236 | "This analysis is function-local!" ); |
237 | |
238 | if (A->getParent() == B->getParent()) { |
239 | // The same block case is special because it's the only time we're looking |
240 | // within a single block to see which instruction comes first. Once we |
241 | // start looking at multiple blocks, the first instruction of the block is |
242 | // reachable, so we only need to determine reachability between whole |
243 | // blocks. |
244 | BasicBlock *BB = const_cast<BasicBlock *>(A->getParent()); |
245 | |
246 | // If the block is in a loop then we can reach any instruction in the block |
247 | // from any other instruction in the block by going around a backedge. |
248 | if (LI && LI->getLoopFor(BB) != nullptr) |
249 | return true; |
250 | |
251 | // If A comes before B, then B is definitively reachable from A. |
252 | if (A == B || A->comesBefore(Other: B)) |
253 | return true; |
254 | |
255 | // Can't be in a loop if it's the entry block -- the entry block may not |
256 | // have predecessors. |
257 | if (BB->isEntryBlock()) |
258 | return false; |
259 | |
260 | // Otherwise, continue doing the normal per-BB CFG walk. |
261 | SmallVector<BasicBlock*, 32> Worklist; |
262 | Worklist.append(in_start: succ_begin(BB), in_end: succ_end(BB)); |
263 | if (Worklist.empty()) { |
264 | // We've proven that there's no path! |
265 | return false; |
266 | } |
267 | |
268 | return isPotentiallyReachableFromMany(Worklist, StopBB: B->getParent(), |
269 | ExclusionSet, DT, LI); |
270 | } |
271 | |
272 | return isPotentiallyReachable( |
273 | A: A->getParent(), B: B->getParent(), ExclusionSet, DT, LI); |
274 | } |
275 | |