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