Line data Source code
1 : //===-- CFG.cpp - BasicBlock analysis --------------------------------------==//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This family of functions performs analyses on basic blocks, and instructions
11 : // contained within basic blocks.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #include "llvm/Analysis/CFG.h"
16 : #include "llvm/ADT/SmallSet.h"
17 : #include "llvm/Analysis/LoopInfo.h"
18 : #include "llvm/IR/Dominators.h"
19 :
20 : using namespace llvm;
21 :
22 : /// FindFunctionBackedges - Analyze the specified function to find all of the
23 : /// loop backedges in the function and return them. This is a relatively cheap
24 : /// (compared to computing dominators and loop info) analysis.
25 : ///
26 : /// The output is added to Result, as pairs of <from,to> edge info.
27 403975 : void llvm::FindFunctionBackedges(const Function &F,
28 : SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) {
29 : const BasicBlock *BB = &F.getEntryBlock();
30 403976 : if (succ_empty(BB))
31 269695 : return;
32 :
33 : SmallPtrSet<const BasicBlock*, 8> Visited;
34 : SmallVector<std::pair<const BasicBlock*, succ_const_iterator>, 8> VisitStack;
35 : SmallPtrSet<const BasicBlock*, 8> InStack;
36 :
37 134281 : Visited.insert(BB);
38 134281 : VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
39 134281 : InStack.insert(BB);
40 : do {
41 : std::pair<const BasicBlock*, succ_const_iterator> &Top = VisitStack.back();
42 4294281 : const BasicBlock *ParentBB = Top.first;
43 : succ_const_iterator &I = Top.second;
44 :
45 : bool FoundNew = false;
46 5043819 : while (I != succ_end(ParentBB)) {
47 : BB = *I++;
48 2829538 : if (Visited.insert(BB).second) {
49 : FoundNew = true;
50 : break;
51 : }
52 : // Successor is in VisitStack, it's a back edge.
53 749538 : if (InStack.count(BB))
54 45156 : Result.push_back(std::make_pair(ParentBB, BB));
55 : }
56 :
57 4294281 : if (FoundNew) {
58 : // Go down one level if there is a unvisited successor.
59 2080000 : InStack.insert(BB);
60 2080000 : VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
61 : } else {
62 : // Go up one level.
63 : InStack.erase(VisitStack.pop_back_val().first);
64 : }
65 4294281 : } while (!VisitStack.empty());
66 : }
67 :
68 : /// GetSuccessorNumber - Search for the specified successor of basic block BB
69 : /// and return its position in the terminator instruction's list of
70 : /// successors. It is an error to call this with a block that is not a
71 : /// successor.
72 3775 : unsigned llvm::GetSuccessorNumber(const BasicBlock *BB,
73 : const BasicBlock *Succ) {
74 3775 : const Instruction *Term = BB->getTerminator();
75 : #ifndef NDEBUG
76 : unsigned e = Term->getNumSuccessors();
77 : #endif
78 682 : for (unsigned i = 0; ; ++i) {
79 682 : assert(i != e && "Didn't find edge?");
80 4457 : if (Term->getSuccessor(i) == Succ)
81 3775 : return i;
82 : }
83 : }
84 :
85 : /// isCriticalEdge - Return true if the specified edge is a critical edge.
86 : /// Critical edges are edges from a block with multiple successors to a block
87 : /// with multiple predecessors.
88 10479 : bool llvm::isCriticalEdge(const Instruction *TI, unsigned SuccNum,
89 : bool AllowIdenticalEdges) {
90 : assert(TI->isTerminator() && "Must be a terminator to have successors!");
91 : assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!");
92 10479 : if (TI->getNumSuccessors() == 1) return false;
93 :
94 7333 : const BasicBlock *Dest = TI->getSuccessor(SuccNum);
95 7333 : const_pred_iterator I = pred_begin(Dest), E = pred_end(Dest);
96 :
97 : // If there is more than one predecessor, this is a critical edge...
98 : assert(I != E && "No preds, but we have an edge to the block?");
99 : const BasicBlock *FirstPred = *I;
100 : ++I; // Skip one edge due to the incoming arc from TI.
101 7333 : if (!AllowIdenticalEdges)
102 7160 : return I != E;
103 :
104 : // If AllowIdenticalEdges is true, then we allow this edge to be considered
105 : // non-critical iff all preds come from TI's block.
106 183 : for (; I != E; ++I)
107 180 : if (*I != FirstPred)
108 : return true;
109 : return false;
110 : }
111 :
112 : // LoopInfo contains a mapping from basic block to the innermost loop. Find
113 : // the outermost loop in the loop nest that contains BB.
114 697361 : static const Loop *getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB) {
115 : const Loop *L = LI->getLoopFor(BB);
116 62614 : if (L) {
117 81834 : while (const Loop *Parent = L->getParentLoop())
118 : L = Parent;
119 : }
120 697361 : return L;
121 : }
122 :
123 : // True if there is a loop which contains both BB1 and BB2.
124 237893 : static bool loopContainsBoth(const LoopInfo *LI,
125 : const BasicBlock *BB1, const BasicBlock *BB2) {
126 237893 : const Loop *L1 = getOutermostLoop(LI, BB1);
127 237893 : const Loop *L2 = getOutermostLoop(LI, BB2);
128 237893 : return L1 != nullptr && L1 == L2;
129 : }
130 :
131 237197 : bool llvm::isPotentiallyReachableFromMany(
132 : SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB,
133 : const DominatorTree *DT, const LoopInfo *LI) {
134 : // When the stop block is unreachable, it's dominated from everywhere,
135 : // regardless of whether there's a path between the two blocks.
136 237197 : if (DT && !DT->isReachableFromEntry(StopBB))
137 : DT = nullptr;
138 :
139 : // Limit the number of blocks we visit. The goal is to avoid run-away compile
140 : // times on large CFGs without hampering sensible code. Arbitrarily chosen.
141 : unsigned Limit = 32;
142 : SmallPtrSet<const BasicBlock*, 32> Visited;
143 : do {
144 : BasicBlock *BB = Worklist.pop_back_val();
145 2542940 : if (!Visited.insert(BB).second)
146 : continue;
147 2201471 : if (BB == StopBB)
148 : return true;
149 2179665 : if (DT && DT->dominates(BB, StopBB))
150 : return true;
151 2146588 : if (LI && loopContainsBoth(LI, BB, StopBB))
152 : return true;
153 :
154 2132593 : if (!--Limit) {
155 : // We haven't been able to prove it one way or the other. Conservatively
156 : // answer true -- that there is potentially a path.
157 : return true;
158 : }
159 :
160 2086367 : if (const Loop *Outer = LI ? getOutermostLoop(LI, BB) : nullptr) {
161 : // All blocks in a single loop are reachable from all other blocks. From
162 : // any of these blocks, we can skip directly to the exits of the loop,
163 : // ignoring any other blocks inside the loop body.
164 15408 : Outer->getExitBlocks(Worklist);
165 : } else {
166 2070959 : Worklist.append(succ_begin(BB), succ_end(BB));
167 : }
168 2427836 : } while (!Worklist.empty());
169 :
170 : // We have exhausted all possible paths and are certain that 'To' can not be
171 : // reached from 'From'.
172 : return false;
173 : }
174 :
175 51652 : bool llvm::isPotentiallyReachable(const BasicBlock *A, const BasicBlock *B,
176 : const DominatorTree *DT, const LoopInfo *LI) {
177 : assert(A->getParent() == B->getParent() &&
178 : "This analysis is function-local!");
179 :
180 : SmallVector<BasicBlock*, 32> Worklist;
181 51652 : Worklist.push_back(const_cast<BasicBlock*>(A));
182 :
183 51652 : return isPotentiallyReachableFromMany(Worklist, const_cast<BasicBlock *>(B),
184 51652 : DT, LI);
185 : }
186 :
187 222220 : bool llvm::isPotentiallyReachable(const Instruction *A, const Instruction *B,
188 : const DominatorTree *DT, const LoopInfo *LI) {
189 : assert(A->getParent()->getParent() == B->getParent()->getParent() &&
190 : "This analysis is function-local!");
191 :
192 : SmallVector<BasicBlock*, 32> Worklist;
193 :
194 222220 : if (A->getParent() == B->getParent()) {
195 : // The same block case is special because it's the only time we're looking
196 : // within a single block to see which instruction comes first. Once we
197 : // start looking at multiple blocks, the first instruction of the block is
198 : // reachable, so we only need to determine reachability between whole
199 : // blocks.
200 : BasicBlock *BB = const_cast<BasicBlock *>(A->getParent());
201 :
202 : // If the block is in a loop then we can reach any instruction in the block
203 : // from any other instruction in the block by going around a backedge.
204 23439 : if (LI && LI->getLoopFor(BB) != nullptr)
205 : return true;
206 :
207 : // Linear scan, start at 'A', see whether we hit 'B' or the end first.
208 126360 : for (BasicBlock::const_iterator I = A->getIterator(), E = BB->end(); I != E;
209 : ++I) {
210 126350 : if (&*I == B)
211 : return true;
212 : }
213 :
214 : // Can't be in a loop if it's the entry block -- the entry block may not
215 : // have predecessors.
216 20 : if (BB == &BB->getParent()->getEntryBlock())
217 : return false;
218 :
219 : // Otherwise, continue doing the normal per-BB CFG walk.
220 6 : Worklist.append(succ_begin(BB), succ_end(BB));
221 :
222 6 : if (Worklist.empty()) {
223 : // We've proven that there's no path!
224 : return false;
225 : }
226 : } else {
227 204779 : Worklist.push_back(const_cast<BasicBlock*>(A->getParent()));
228 : }
229 :
230 409570 : if (A->getParent() == &A->getParent()->getParent()->getEntryBlock())
231 : return true;
232 204777 : if (B->getParent() == &A->getParent()->getParent()->getEntryBlock())
233 : return false;
234 :
235 165448 : return isPotentiallyReachableFromMany(
236 165448 : Worklist, const_cast<BasicBlock *>(B->getParent()), DT, LI);
237 : }
|
