xref: /freebsd/contrib/llvm-project/llvm/lib/Analysis/CFG.cpp (revision 6ba2210ee039f2f12878c217bcf058e9c8b26b29)
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(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(BB);
45   VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
46   InStack.insert(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(ParentBB)) {
54       BB = *I++;
55       if (Visited.insert(BB).second) {
56         FoundNew = true;
57         break;
58       }
59       // Successor is in VisitStack, it's a back edge.
60       if (InStack.count(BB))
61         Result.push_back(std::make_pair(ParentBB, BB));
62     }
63 
64     if (FoundNew) {
65       // Go down one level if there is a unvisited successor.
66       InStack.insert(BB);
67       VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
68     } else {
69       // Go up one level.
70       InStack.erase(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(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, TI->getSuccessor(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(Dest), E = pred_end(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   if (L) {
131     while (const Loop *Parent = L->getParentLoop())
132       L = Parent;
133   }
134   return L;
135 }
136 
137 bool llvm::isPotentiallyReachableFromMany(
138     SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB,
139     const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
140     const LoopInfo *LI) {
141   // When the stop block is unreachable, it's dominated from everywhere,
142   // regardless of whether there's a path between the two blocks.
143   if (DT && !DT->isReachableFromEntry(StopBB))
144     DT = nullptr;
145 
146   // We can't skip directly from a block that dominates the stop block if the
147   // exclusion block is potentially in between.
148   if (ExclusionSet && !ExclusionSet->empty())
149     DT = nullptr;
150 
151   // Normally any block in a loop is reachable from any other block in a loop,
152   // however excluded blocks might partition the body of a loop to make that
153   // untrue.
154   SmallPtrSet<const Loop *, 8> LoopsWithHoles;
155   if (LI && ExclusionSet) {
156     for (auto BB : *ExclusionSet) {
157       if (const Loop *L = getOutermostLoop(LI, BB))
158         LoopsWithHoles.insert(L);
159     }
160   }
161 
162   const Loop *StopLoop = LI ? getOutermostLoop(LI, StopBB) : nullptr;
163 
164   unsigned Limit = DefaultMaxBBsToExplore;
165   SmallPtrSet<const BasicBlock*, 32> Visited;
166   do {
167     BasicBlock *BB = Worklist.pop_back_val();
168     if (!Visited.insert(BB).second)
169       continue;
170     if (BB == StopBB)
171       return true;
172     if (ExclusionSet && ExclusionSet->count(BB))
173       continue;
174     if (DT && DT->dominates(BB, StopBB))
175       return true;
176 
177     const Loop *Outer = nullptr;
178     if (LI) {
179       Outer = getOutermostLoop(LI, BB);
180       // If we're in a loop with a hole, not all blocks in the loop are
181       // reachable from all other blocks. That implies we can't simply jump to
182       // the loop's exit blocks, as that exit might need to pass through an
183       // excluded block. Clear Outer so we process BB's successors.
184       if (LoopsWithHoles.count(Outer))
185         Outer = nullptr;
186       if (StopLoop && Outer == StopLoop)
187         return true;
188     }
189 
190     if (!--Limit) {
191       // We haven't been able to prove it one way or the other. Conservatively
192       // answer true -- that there is potentially a path.
193       return true;
194     }
195 
196     if (Outer) {
197       // All blocks in a single loop are reachable from all other blocks. From
198       // any of these blocks, we can skip directly to the exits of the loop,
199       // ignoring any other blocks inside the loop body.
200       Outer->getExitBlocks(Worklist);
201     } else {
202       Worklist.append(succ_begin(BB), succ_end(BB));
203     }
204   } while (!Worklist.empty());
205 
206   // We have exhausted all possible paths and are certain that 'To' can not be
207   // reached from 'From'.
208   return false;
209 }
210 
211 bool llvm::isPotentiallyReachable(const BasicBlock *A, const BasicBlock *B,
212                                   const DominatorTree *DT, const LoopInfo *LI) {
213   assert(A->getParent() == B->getParent() &&
214          "This analysis is function-local!");
215 
216   SmallVector<BasicBlock*, 32> Worklist;
217   Worklist.push_back(const_cast<BasicBlock*>(A));
218 
219   return isPotentiallyReachableFromMany(Worklist, const_cast<BasicBlock *>(B),
220                                         nullptr, DT, LI);
221 }
222 
223 bool llvm::isPotentiallyReachable(
224     const Instruction *A, const Instruction *B,
225     const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
226     const LoopInfo *LI) {
227   assert(A->getParent()->getParent() == B->getParent()->getParent() &&
228          "This analysis is function-local!");
229 
230   SmallVector<BasicBlock*, 32> Worklist;
231 
232   if (A->getParent() == B->getParent()) {
233     // The same block case is special because it's the only time we're looking
234     // within a single block to see which instruction comes first. Once we
235     // start looking at multiple blocks, the first instruction of the block is
236     // reachable, so we only need to determine reachability between whole
237     // blocks.
238     BasicBlock *BB = const_cast<BasicBlock *>(A->getParent());
239 
240     // If the block is in a loop then we can reach any instruction in the block
241     // from any other instruction in the block by going around a backedge.
242     if (LI && LI->getLoopFor(BB) != nullptr)
243       return true;
244 
245     // Linear scan, start at 'A', see whether we hit 'B' or the end first.
246     for (BasicBlock::const_iterator I = A->getIterator(), E = BB->end(); I != E;
247          ++I) {
248       if (&*I == B)
249         return true;
250     }
251 
252     // Can't be in a loop if it's the entry block -- the entry block may not
253     // have predecessors.
254     if (BB == &BB->getParent()->getEntryBlock())
255       return false;
256 
257     // Otherwise, continue doing the normal per-BB CFG walk.
258     Worklist.append(succ_begin(BB), succ_end(BB));
259 
260     if (Worklist.empty()) {
261       // We've proven that there's no path!
262       return false;
263     }
264   } else {
265     Worklist.push_back(const_cast<BasicBlock*>(A->getParent()));
266   }
267 
268   if (DT) {
269     if (DT->isReachableFromEntry(A->getParent()) &&
270         !DT->isReachableFromEntry(B->getParent()))
271       return false;
272     if (!ExclusionSet || ExclusionSet->empty()) {
273       if (A->getParent() == &A->getParent()->getParent()->getEntryBlock() &&
274           DT->isReachableFromEntry(B->getParent()))
275         return true;
276       if (B->getParent() == &A->getParent()->getParent()->getEntryBlock() &&
277           DT->isReachableFromEntry(A->getParent()))
278         return false;
279     }
280   }
281 
282   return isPotentiallyReachableFromMany(
283       Worklist, const_cast<BasicBlock *>(B->getParent()), ExclusionSet, DT, LI);
284 }
285