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/IR/IntrinsicInst.h"
18#include "llvm/Support/CommandLine.h"
19
20using namespace llvm;
21
22// The max number of basic blocks explored during reachability analysis between
23// two basic blocks. This is kept reasonably small to limit compile time when
24// repeatedly used by clients of this analysis (such as captureTracking).
25static cl::opt<unsigned> DefaultMaxBBsToExplore(
26 "dom-tree-reachability-max-bbs-to-explore", cl::Hidden,
27 cl::desc("Max number of BBs to explore for reachability analysis"),
28 cl::init(Val: 32));
29
30/// FindFunctionBackedges - Analyze the specified function to find all of the
31/// loop backedges in the function and return them. This is a relatively cheap
32/// (compared to computing dominators and loop info) analysis.
33///
34/// The output is added to Result, as pairs of <from,to> edge info.
35void llvm::FindFunctionBackedges(const Function &F,
36 SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) {
37 const BasicBlock *BB = &F.getEntryBlock();
38 if (succ_empty(BB))
39 return;
40
41 SmallPtrSet<const BasicBlock*, 8> Visited;
42 SmallVector<std::pair<const BasicBlock *, const_succ_iterator>, 8> VisitStack;
43 SmallPtrSet<const BasicBlock*, 8> InStack;
44
45 Visited.insert(Ptr: BB);
46 VisitStack.push_back(Elt: std::make_pair(x&: BB, y: succ_begin(BB)));
47 InStack.insert(Ptr: BB);
48 do {
49 std::pair<const BasicBlock *, const_succ_iterator> &Top = VisitStack.back();
50 const BasicBlock *ParentBB = Top.first;
51 const_succ_iterator &I = Top.second;
52
53 bool FoundNew = false;
54 while (I != succ_end(BB: ParentBB)) {
55 BB = *I++;
56 if (Visited.insert(Ptr: BB).second) {
57 FoundNew = true;
58 break;
59 }
60 // Successor is in VisitStack, it's a back edge.
61 if (InStack.count(Ptr: BB))
62 Result.push_back(Elt: std::make_pair(x&: ParentBB, y&: BB));
63 }
64
65 if (FoundNew) {
66 // Go down one level if there is a unvisited successor.
67 InStack.insert(Ptr: BB);
68 VisitStack.push_back(Elt: std::make_pair(x&: BB, y: succ_begin(BB)));
69 } else {
70 // Go up one level.
71 InStack.erase(Ptr: VisitStack.pop_back_val().first);
72 }
73 } while (!VisitStack.empty());
74}
75
76/// GetSuccessorNumber - Search for the specified successor of basic block BB
77/// and return its position in the terminator instruction's list of
78/// successors. It is an error to call this with a block that is not a
79/// successor.
80unsigned llvm::GetSuccessorNumber(const BasicBlock *BB,
81 const BasicBlock *Succ) {
82 const Instruction *Term = BB->getTerminator();
83#ifndef NDEBUG
84 unsigned e = Term->getNumSuccessors();
85#endif
86 for (unsigned i = 0; ; ++i) {
87 assert(i != e && "Didn't find edge?");
88 if (Term->getSuccessor(Idx: i) == Succ)
89 return i;
90 }
91}
92
93/// isCriticalEdge - Return true if the specified edge is a critical edge.
94/// Critical edges are edges from a block with multiple successors to a block
95/// with multiple predecessors.
96bool llvm::isCriticalEdge(const Instruction *TI, unsigned SuccNum,
97 bool AllowIdenticalEdges) {
98 assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!");
99 return isCriticalEdge(TI, Succ: TI->getSuccessor(Idx: SuccNum), AllowIdenticalEdges);
100}
101
102bool llvm::isCriticalEdge(const Instruction *TI, const BasicBlock *Dest,
103 bool AllowIdenticalEdges) {
104 assert(TI->isTerminator() && "Must be a terminator to have successors!");
105 if (TI->getNumSuccessors() == 1) return false;
106
107 assert(is_contained(predecessors(Dest), TI->getParent()) &&
108 "No edge between TI's block and Dest.");
109
110 const_pred_iterator I = pred_begin(BB: Dest), E = pred_end(BB: Dest);
111
112 // If there is more than one predecessor, this is a critical edge...
113 assert(I != E && "No preds, but we have an edge to the block?");
114 const BasicBlock *FirstPred = *I;
115 ++I; // Skip one edge due to the incoming arc from TI.
116 if (!AllowIdenticalEdges)
117 return I != E;
118
119 // If AllowIdenticalEdges is true, then we allow this edge to be considered
120 // non-critical iff all preds come from TI's block.
121 for (; I != E; ++I)
122 if (*I != FirstPred)
123 return true;
124 return false;
125}
126
127// LoopInfo contains a mapping from basic block to the innermost loop. Find
128// the outermost loop in the loop nest that contains BB.
129static const Loop *getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB) {
130 const Loop *L = LI->getLoopFor(BB);
131 return L ? L->getOutermostLoop() : nullptr;
132}
133
134template <class StopSetT>
135static bool isReachableImpl(SmallVectorImpl<BasicBlock *> &Worklist,
136 const StopSetT &StopSet,
137 const SmallPtrSetImpl<BasicBlock *> *ExclusionSet,
138 const DominatorTree *DT, const LoopInfo *LI) {
139 // When a stop block is unreachable, it's dominated from everywhere,
140 // regardless of whether there's a path between the two blocks.
141 if (DT) {
142 for (auto *BB : StopSet) {
143 if (!DT->isReachableFromEntry(BB)) {
144 DT = nullptr;
145 break;
146 }
147 }
148 }
149
150 // We can't skip directly from a block that dominates the stop block if the
151 // exclusion block is potentially in between.
152 if (ExclusionSet && !ExclusionSet->empty())
153 DT = nullptr;
154
155 // Normally any block in a loop is reachable from any other block in a loop,
156 // however excluded blocks might partition the body of a loop to make that
157 // untrue.
158 SmallPtrSet<const Loop *, 8> LoopsWithHoles;
159 if (LI && ExclusionSet) {
160 for (auto *BB : *ExclusionSet) {
161 if (const Loop *L = getOutermostLoop(LI, BB))
162 LoopsWithHoles.insert(Ptr: L);
163 }
164 }
165
166 SmallPtrSet<const Loop *, 2> StopLoops;
167 if (LI) {
168 for (auto *StopSetBB : StopSet) {
169 if (const Loop *L = getOutermostLoop(LI, StopSetBB))
170 StopLoops.insert(Ptr: L);
171 }
172 }
173
174 unsigned Limit = DefaultMaxBBsToExplore;
175 SmallPtrSet<const BasicBlock*, 32> Visited;
176 do {
177 BasicBlock *BB = Worklist.pop_back_val();
178 if (!Visited.insert(Ptr: BB).second)
179 continue;
180 if (StopSet.contains(BB))
181 return true;
182 if (ExclusionSet && ExclusionSet->count(Ptr: BB))
183 continue;
184 if (DT) {
185 if (llvm::any_of(StopSet, [&](const BasicBlock *StopBB) {
186 return DT->dominates(A: BB, B: StopBB);
187 }))
188 return true;
189 }
190
191 const Loop *Outer = nullptr;
192 if (LI) {
193 Outer = getOutermostLoop(LI, BB);
194 // If we're in a loop with a hole, not all blocks in the loop are
195 // reachable from all other blocks. That implies we can't simply jump to
196 // the loop's exit blocks, as that exit might need to pass through an
197 // excluded block. Clear Outer so we process BB's successors.
198 if (LoopsWithHoles.count(Ptr: Outer))
199 Outer = nullptr;
200 if (StopLoops.contains(Ptr: Outer))
201 return true;
202 }
203
204 if (!--Limit) {
205 // We haven't been able to prove it one way or the other. Conservatively
206 // answer true -- that there is potentially a path.
207 return true;
208 }
209
210 if (Outer) {
211 // All blocks in a single loop are reachable from all other blocks. From
212 // any of these blocks, we can skip directly to the exits of the loop,
213 // ignoring any other blocks inside the loop body.
214 Outer->getExitBlocks(ExitBlocks&: Worklist);
215 } else {
216 Worklist.append(in_start: succ_begin(BB), in_end: succ_end(BB));
217 }
218 } while (!Worklist.empty());
219
220 // We have exhausted all possible paths and are certain that 'To' can not be
221 // reached from 'From'.
222 return false;
223}
224
225template <class T> class SingleEntrySet {
226public:
227 using const_iterator = const T *;
228
229 SingleEntrySet(T Elem) : Elem(Elem) {}
230
231 bool contains(T Other) const { return Elem == Other; }
232
233 const_iterator begin() const { return &Elem; }
234 const_iterator end() const { return &Elem + 1; }
235
236private:
237 T Elem;
238};
239
240bool llvm::isPotentiallyReachableFromMany(
241 SmallVectorImpl<BasicBlock *> &Worklist, const BasicBlock *StopBB,
242 const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
243 const LoopInfo *LI) {
244 return isReachableImpl<SingleEntrySet<const BasicBlock *>>(
245 Worklist, StopSet: SingleEntrySet<const BasicBlock *>(StopBB), ExclusionSet, DT,
246 LI);
247}
248
249bool llvm::isManyPotentiallyReachableFromMany(
250 SmallVectorImpl<BasicBlock *> &Worklist,
251 const SmallPtrSetImpl<const BasicBlock *> &StopSet,
252 const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
253 const LoopInfo *LI) {
254 return isReachableImpl<SmallPtrSetImpl<const BasicBlock *>>(
255 Worklist, StopSet, ExclusionSet, DT, LI);
256}
257
258bool llvm::isPotentiallyReachable(
259 const BasicBlock *A, const BasicBlock *B,
260 const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
261 const LoopInfo *LI) {
262 assert(A->getParent() == B->getParent() &&
263 "This analysis is function-local!");
264
265 if (DT) {
266 if (DT->isReachableFromEntry(A) && !DT->isReachableFromEntry(A: B))
267 return false;
268 if (!ExclusionSet || ExclusionSet->empty()) {
269 if (A->isEntryBlock() && DT->isReachableFromEntry(A: B))
270 return true;
271 if (B->isEntryBlock() && DT->isReachableFromEntry(A))
272 return false;
273 }
274 }
275
276 SmallVector<BasicBlock*, 32> Worklist;
277 Worklist.push_back(Elt: const_cast<BasicBlock*>(A));
278
279 return isPotentiallyReachableFromMany(Worklist, StopBB: B, ExclusionSet, DT, LI);
280}
281
282bool llvm::isPotentiallyReachable(
283 const Instruction *A, const Instruction *B,
284 const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
285 const LoopInfo *LI) {
286 assert(A->getParent()->getParent() == B->getParent()->getParent() &&
287 "This analysis is function-local!");
288
289 if (A->getParent() == B->getParent()) {
290 // The same block case is special because it's the only time we're looking
291 // within a single block to see which instruction comes first. Once we
292 // start looking at multiple blocks, the first instruction of the block is
293 // reachable, so we only need to determine reachability between whole
294 // blocks.
295 BasicBlock *BB = const_cast<BasicBlock *>(A->getParent());
296
297 // If the block is in a loop then we can reach any instruction in the block
298 // from any other instruction in the block by going around a backedge.
299 if (LI && LI->getLoopFor(BB) != nullptr)
300 return true;
301
302 // If A comes before B, then B is definitively reachable from A.
303 if (A == B || A->comesBefore(Other: B))
304 return true;
305
306 // Can't be in a loop if it's the entry block -- the entry block may not
307 // have predecessors.
308 if (BB->isEntryBlock())
309 return false;
310
311 // Otherwise, continue doing the normal per-BB CFG walk.
312 SmallVector<BasicBlock*, 32> Worklist;
313 Worklist.append(in_start: succ_begin(BB), in_end: succ_end(BB));
314 if (Worklist.empty()) {
315 // We've proven that there's no path!
316 return false;
317 }
318
319 return isPotentiallyReachableFromMany(Worklist, StopBB: B->getParent(),
320 ExclusionSet, DT, LI);
321 }
322
323 return isPotentiallyReachable(
324 A: A->getParent(), B: B->getParent(), ExclusionSet, DT, LI);
325}
326
327static bool instructionDoesNotReturn(const Instruction &I) {
328 if (auto *CB = dyn_cast<CallBase>(Val: &I))
329 return CB->hasFnAttr(Kind: Attribute::NoReturn);
330 return false;
331}
332
333// A basic block can only return if it terminates with a ReturnInst and does not
334// contain calls to noreturn functions.
335static bool basicBlockCanReturn(const BasicBlock &BB) {
336 if (!isa<ReturnInst>(Val: BB.getTerminator()))
337 return false;
338 return none_of(Range: BB, P: instructionDoesNotReturn);
339}
340
341// FIXME: this doesn't handle recursion.
342bool llvm::canReturn(const Function &F) {
343 SmallVector<const BasicBlock *, 16> Worklist;
344 SmallPtrSet<const BasicBlock *, 16> Visited;
345
346 Visited.insert(Ptr: &F.front());
347 Worklist.push_back(Elt: &F.front());
348
349 do {
350 const BasicBlock *BB = Worklist.pop_back_val();
351 if (basicBlockCanReturn(BB: *BB))
352 return true;
353 for (const BasicBlock *Succ : successors(BB))
354 if (Visited.insert(Ptr: Succ).second)
355 Worklist.push_back(Elt: Succ);
356 } while (!Worklist.empty());
357
358 return false;
359}
360
361bool llvm::isPresplitCoroSuspendExitEdge(const BasicBlock &Src,
362 const BasicBlock &Dest) {
363 assert(Src.getParent() == Dest.getParent());
364 if (!Src.getParent()->isPresplitCoroutine())
365 return false;
366 if (auto *SW = dyn_cast<SwitchInst>(Val: Src.getTerminator()))
367 if (auto *Intr = dyn_cast<IntrinsicInst>(Val: SW->getCondition()))
368 return Intr->getIntrinsicID() == Intrinsic::coro_suspend &&
369 SW->getDefaultDest() == &Dest;
370 return false;
371}
372