/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Analysis/CFG.cpp
Line | Count | Source (jump to first uncovered line) |
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 | | void llvm::FindFunctionBackedges(const Function &F, |
28 | 5.76M | SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) { |
29 | 5.76M | const BasicBlock *BB = &F.getEntryBlock(); |
30 | 5.76M | if (succ_empty(BB)) |
31 | 3.29M | return; |
32 | 2.47M | |
33 | 2.47M | SmallPtrSet<const BasicBlock*, 8> Visited; |
34 | 2.47M | SmallVector<std::pair<const BasicBlock*, succ_const_iterator>, 8> VisitStack; |
35 | 2.47M | SmallPtrSet<const BasicBlock*, 8> InStack; |
36 | 2.47M | |
37 | 2.47M | Visited.insert(BB); |
38 | 2.47M | VisitStack.push_back(std::make_pair(BB, succ_begin(BB))); |
39 | 2.47M | InStack.insert(BB); |
40 | 73.5M | do { |
41 | 73.5M | std::pair<const BasicBlock*, succ_const_iterator> &Top = VisitStack.back(); |
42 | 73.5M | const BasicBlock *ParentBB = Top.first; |
43 | 73.5M | succ_const_iterator &I = Top.second; |
44 | 73.5M | |
45 | 73.5M | bool FoundNew = false; |
46 | 93.2M | while (I != succ_end(ParentBB)93.2M ) { |
47 | 55.2M | BB = *I++; |
48 | 55.2M | if (Visited.insert(BB).second55.2M ) { |
49 | 35.5M | FoundNew = true; |
50 | 35.5M | break; |
51 | 35.5M | } |
52 | 19.6M | // Successor is in VisitStack, it's a back edge. |
53 | 19.6M | if (19.6M InStack.count(BB)19.6M ) |
54 | 3.64M | Result.push_back(std::make_pair(ParentBB, BB)); |
55 | 55.2M | } |
56 | 73.5M | |
57 | 73.5M | if (FoundNew73.5M ) { |
58 | 35.5M | // Go down one level if there is a unvisited successor. |
59 | 35.5M | InStack.insert(BB); |
60 | 35.5M | VisitStack.push_back(std::make_pair(BB, succ_begin(BB))); |
61 | 73.5M | } else { |
62 | 37.9M | // Go up one level. |
63 | 37.9M | InStack.erase(VisitStack.pop_back_val().first); |
64 | 37.9M | } |
65 | 73.5M | } while (!VisitStack.empty()); |
66 | 5.76M | } |
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 | | unsigned llvm::GetSuccessorNumber(const BasicBlock *BB, |
73 | 46.5k | const BasicBlock *Succ) { |
74 | 46.5k | const TerminatorInst *Term = BB->getTerminator(); |
75 | | #ifndef NDEBUG |
76 | | unsigned e = Term->getNumSuccessors(); |
77 | | #endif |
78 | 46.5k | for (unsigned i = 0; ; ++i6.33k ) { |
79 | 52.9k | assert(i != e && "Didn't find edge?"); |
80 | 52.9k | if (Term->getSuccessor(i) == Succ) |
81 | 46.5k | return i; |
82 | 52.9k | } |
83 | 46.5k | } |
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 | | bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, |
89 | 182k | bool AllowIdenticalEdges) { |
90 | 182k | assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!"); |
91 | 182k | if (TI->getNumSuccessors() == 1182k ) return false34.7k ; |
92 | 147k | |
93 | 147k | const BasicBlock *Dest = TI->getSuccessor(SuccNum); |
94 | 147k | const_pred_iterator I = pred_begin(Dest), E = pred_end(Dest); |
95 | 147k | |
96 | 147k | // If there is more than one predecessor, this is a critical edge... |
97 | 147k | assert(I != E && "No preds, but we have an edge to the block?"); |
98 | 147k | const BasicBlock *FirstPred = *I; |
99 | 147k | ++I; // Skip one edge due to the incoming arc from TI. |
100 | 147k | if (!AllowIdenticalEdges) |
101 | 139k | return I != E; |
102 | 8.82k | |
103 | 8.82k | // If AllowIdenticalEdges is true, then we allow this edge to be considered |
104 | 8.82k | // non-critical iff all preds come from TI's block. |
105 | 8.84k | for (; 8.82k I != E8.84k ; ++I24 ) |
106 | 8.84k | if (8.84k *I != FirstPred8.84k ) |
107 | 8.82k | return true; |
108 | 3 | return false; |
109 | 182k | } |
110 | | |
111 | | // LoopInfo contains a mapping from basic block to the innermost loop. Find |
112 | | // the outermost loop in the loop nest that contains BB. |
113 | 7.72M | static const Loop *getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB) { |
114 | 7.72M | const Loop *L = LI->getLoopFor(BB); |
115 | 7.72M | if (L7.72M ) { |
116 | 1.41M | while (const Loop *Parent = L->getParentLoop()) |
117 | 359k | L = Parent; |
118 | 1.05M | } |
119 | 7.72M | return L; |
120 | 7.72M | } |
121 | | |
122 | | // True if there is a loop which contains both BB1 and BB2. |
123 | | static bool loopContainsBoth(const LoopInfo *LI, |
124 | 2.67M | const BasicBlock *BB1, const BasicBlock *BB2) { |
125 | 2.67M | const Loop *L1 = getOutermostLoop(LI, BB1); |
126 | 2.67M | const Loop *L2 = getOutermostLoop(LI, BB2); |
127 | 519k | return L1 != nullptr && L1 == L2; |
128 | 2.67M | } |
129 | | |
130 | | bool llvm::isPotentiallyReachableFromMany( |
131 | | SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB, |
132 | 1.48M | const DominatorTree *DT, const LoopInfo *LI) { |
133 | 1.48M | // When the stop block is unreachable, it's dominated from everywhere, |
134 | 1.48M | // regardless of whether there's a path between the two blocks. |
135 | 1.48M | if (DT && 1.48M !DT->isReachableFromEntry(StopBB)1.48M ) |
136 | 664 | DT = nullptr; |
137 | 1.48M | |
138 | 1.48M | // Limit the number of blocks we visit. The goal is to avoid run-away compile |
139 | 1.48M | // times on large CFGs without hampering sensible code. Arbitrarily chosen. |
140 | 1.48M | unsigned Limit = 32; |
141 | 1.48M | SmallPtrSet<const BasicBlock*, 32> Visited; |
142 | 10.9M | do { |
143 | 10.9M | BasicBlock *BB = Worklist.pop_back_val(); |
144 | 10.9M | if (!Visited.insert(BB).second) |
145 | 1.89M | continue; |
146 | 9.10M | if (9.10M BB == StopBB9.10M ) |
147 | 460k | return true; |
148 | 8.64M | if (8.64M DT && 8.64M DT->dominates(BB, StopBB)8.63M ) |
149 | 216k | return true; |
150 | 8.42M | if (8.42M LI && 8.42M loopContainsBoth(LI, BB, StopBB)2.67M ) |
151 | 281k | return true; |
152 | 8.14M | |
153 | 8.14M | if (8.14M !--Limit8.14M ) { |
154 | 141k | // We haven't been able to prove it one way or the other. Conservatively |
155 | 141k | // answer true -- that there is potentially a path. |
156 | 141k | return true; |
157 | 141k | } |
158 | 8.00M | |
159 | 8.00M | if (const Loop *8.00M Outer8.00M = LI ? getOutermostLoop(LI, BB) : nullptr) { |
160 | 235k | // All blocks in a single loop are reachable from all other blocks. From |
161 | 235k | // any of these blocks, we can skip directly to the exits of the loop, |
162 | 235k | // ignoring any other blocks inside the loop body. |
163 | 235k | Outer->getExitBlocks(Worklist); |
164 | 8.00M | } else { |
165 | 7.76M | Worklist.append(succ_begin(BB), succ_end(BB)); |
166 | 7.76M | } |
167 | 9.89M | } while (!Worklist.empty()); |
168 | 1.48M | |
169 | 1.48M | // We have exhausted all possible paths and are certain that 'To' can not be |
170 | 1.48M | // reached from 'From'. |
171 | 385k | return false; |
172 | 1.48M | } |
173 | | |
174 | | bool llvm::isPotentiallyReachable(const BasicBlock *A, const BasicBlock *B, |
175 | 1.02M | const DominatorTree *DT, const LoopInfo *LI) { |
176 | 1.02M | assert(A->getParent() == B->getParent() && |
177 | 1.02M | "This analysis is function-local!"); |
178 | 1.02M | |
179 | 1.02M | SmallVector<BasicBlock*, 32> Worklist; |
180 | 1.02M | Worklist.push_back(const_cast<BasicBlock*>(A)); |
181 | 1.02M | |
182 | 1.02M | return isPotentiallyReachableFromMany(Worklist, const_cast<BasicBlock *>(B), |
183 | 1.02M | DT, LI); |
184 | 1.02M | } |
185 | | |
186 | | bool llvm::isPotentiallyReachable(const Instruction *A, const Instruction *B, |
187 | 740k | const DominatorTree *DT, const LoopInfo *LI) { |
188 | 740k | assert(A->getParent()->getParent() == B->getParent()->getParent() && |
189 | 740k | "This analysis is function-local!"); |
190 | 740k | |
191 | 740k | SmallVector<BasicBlock*, 32> Worklist; |
192 | 740k | |
193 | 740k | if (A->getParent() == B->getParent()740k ) { |
194 | 203k | // The same block case is special because it's the only time we're looking |
195 | 203k | // within a single block to see which instruction comes first. Once we |
196 | 203k | // start looking at multiple blocks, the first instruction of the block is |
197 | 203k | // reachable, so we only need to determine reachability between whole |
198 | 203k | // blocks. |
199 | 203k | BasicBlock *BB = const_cast<BasicBlock *>(A->getParent()); |
200 | 203k | |
201 | 203k | // If the block is in a loop then we can reach any instruction in the block |
202 | 203k | // from any other instruction in the block by going around a backedge. |
203 | 203k | if (LI && 203k LI->getLoopFor(BB) != nullptr19.8k ) |
204 | 19.0k | return true; |
205 | 184k | |
206 | 184k | // Linear scan, start at 'A', see whether we hit 'B' or the end first. |
207 | 777k | for (BasicBlock::const_iterator I = A->getIterator(), E = BB->end(); 184k I != E777k ; |
208 | 593k | ++I593k ) { |
209 | 777k | if (&*I == B) |
210 | 184k | return true; |
211 | 777k | } |
212 | 184k | |
213 | 184k | // Can't be in a loop if it's the entry block -- the entry block may not |
214 | 184k | // have predecessors. |
215 | 10 | if (10 BB == &BB->getParent()->getEntryBlock()10 ) |
216 | 4 | return false; |
217 | 6 | |
218 | 6 | // Otherwise, continue doing the normal per-BB CFG walk. |
219 | 6 | Worklist.append(succ_begin(BB), succ_end(BB)); |
220 | 6 | |
221 | 6 | if (Worklist.empty()6 ) { |
222 | 0 | // We've proven that there's no path! |
223 | 0 | return false; |
224 | 0 | } |
225 | 536k | } else { |
226 | 536k | Worklist.push_back(const_cast<BasicBlock*>(A->getParent())); |
227 | 536k | } |
228 | 740k | |
229 | 536k | if (536k A->getParent() == &A->getParent()->getParent()->getEntryBlock()536k ) |
230 | 8 | return true; |
231 | 536k | if (536k B->getParent() == &A->getParent()->getParent()->getEntryBlock()536k ) |
232 | 141k | return false; |
233 | 395k | |
234 | 395k | return isPotentiallyReachableFromMany( |
235 | 395k | Worklist, const_cast<BasicBlock *>(B->getParent()), DT, LI); |
236 | 395k | } |