/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/IR/Dominators.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- Dominators.cpp - Dominator Calculation -----------------------------===// |
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 file implements simple dominator construction algorithms for finding |
10 | | // forward dominators. Postdominators are available in libanalysis, but are not |
11 | | // included in libvmcore, because it's not needed. Forward dominators are |
12 | | // needed to support the Verifier pass. |
13 | | // |
14 | | //===----------------------------------------------------------------------===// |
15 | | |
16 | | #include "llvm/IR/Dominators.h" |
17 | | #include "llvm/ADT/DepthFirstIterator.h" |
18 | | #include "llvm/ADT/SmallPtrSet.h" |
19 | | #include "llvm/Config/llvm-config.h" |
20 | | #include "llvm/IR/CFG.h" |
21 | | #include "llvm/IR/Constants.h" |
22 | | #include "llvm/IR/Instructions.h" |
23 | | #include "llvm/IR/PassManager.h" |
24 | | #include "llvm/Support/CommandLine.h" |
25 | | #include "llvm/Support/Debug.h" |
26 | | #include "llvm/Support/GenericDomTreeConstruction.h" |
27 | | #include "llvm/Support/raw_ostream.h" |
28 | | #include <algorithm> |
29 | | using namespace llvm; |
30 | | |
31 | | bool llvm::VerifyDomInfo = false; |
32 | | static cl::opt<bool, true> |
33 | | VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), cl::Hidden, |
34 | | cl::desc("Verify dominator info (time consuming)")); |
35 | | |
36 | | #ifdef EXPENSIVE_CHECKS |
37 | | static constexpr bool ExpensiveChecksEnabled = true; |
38 | | #else |
39 | | static constexpr bool ExpensiveChecksEnabled = false; |
40 | | #endif |
41 | | |
42 | 4.39M | bool BasicBlockEdge::isSingleEdge() const { |
43 | 4.39M | const Instruction *TI = Start->getTerminator(); |
44 | 4.39M | unsigned NumEdgesToEnd = 0; |
45 | 13.1M | for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i8.79M ) { |
46 | 8.79M | if (TI->getSuccessor(i) == End) |
47 | 4.39M | ++NumEdgesToEnd; |
48 | 8.79M | if (NumEdgesToEnd >= 2) |
49 | 6 | return false; |
50 | 8.79M | } |
51 | 4.39M | assert(NumEdgesToEnd == 1); |
52 | 4.39M | return true; |
53 | 4.39M | } |
54 | | |
55 | | //===----------------------------------------------------------------------===// |
56 | | // DominatorTree Implementation |
57 | | //===----------------------------------------------------------------------===// |
58 | | // |
59 | | // Provide public access to DominatorTree information. Implementation details |
60 | | // can be found in Dominators.h, GenericDomTree.h, and |
61 | | // GenericDomTreeConstruction.h. |
62 | | // |
63 | | //===----------------------------------------------------------------------===// |
64 | | |
65 | | template class llvm::DomTreeNodeBase<BasicBlock>; |
66 | | template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase |
67 | | template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase |
68 | | |
69 | | template class llvm::cfg::Update<BasicBlock *>; |
70 | | |
71 | | template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>( |
72 | | DomTreeBuilder::BBDomTree &DT); |
73 | | template void |
74 | | llvm::DomTreeBuilder::CalculateWithUpdates<DomTreeBuilder::BBDomTree>( |
75 | | DomTreeBuilder::BBDomTree &DT, BBUpdates U); |
76 | | |
77 | | template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>( |
78 | | DomTreeBuilder::BBPostDomTree &DT); |
79 | | // No CalculateWithUpdates<PostDomTree> instantiation, unless a usecase arises. |
80 | | |
81 | | template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>( |
82 | | DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To); |
83 | | template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>( |
84 | | DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To); |
85 | | |
86 | | template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>( |
87 | | DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To); |
88 | | template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>( |
89 | | DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To); |
90 | | |
91 | | template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>( |
92 | | DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBUpdates); |
93 | | template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>( |
94 | | DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBUpdates); |
95 | | |
96 | | template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>( |
97 | | const DomTreeBuilder::BBDomTree &DT, |
98 | | DomTreeBuilder::BBDomTree::VerificationLevel VL); |
99 | | template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>( |
100 | | const DomTreeBuilder::BBPostDomTree &DT, |
101 | | DomTreeBuilder::BBPostDomTree::VerificationLevel VL); |
102 | | |
103 | | bool DominatorTree::invalidate(Function &F, const PreservedAnalyses &PA, |
104 | 6.93k | FunctionAnalysisManager::Invalidator &) { |
105 | 6.93k | // Check whether the analysis, all analyses on functions, or the function's |
106 | 6.93k | // CFG have been preserved. |
107 | 6.93k | auto PAC = PA.getChecker<DominatorTreeAnalysis>(); |
108 | 6.93k | return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()5.02k || |
109 | 6.93k | PAC.preservedSet<CFGAnalyses>()5.00k ); |
110 | 6.93k | } |
111 | | |
112 | | // dominates - Return true if Def dominates a use in User. This performs |
113 | | // the special checks necessary if Def and User are in the same basic block. |
114 | | // Note that Def doesn't dominate a use in Def itself! |
115 | | bool DominatorTree::dominates(const Instruction *Def, |
116 | 13.1M | const Instruction *User) const { |
117 | 13.1M | const BasicBlock *UseBB = User->getParent(); |
118 | 13.1M | const BasicBlock *DefBB = Def->getParent(); |
119 | 13.1M | |
120 | 13.1M | // Any unreachable use is dominated, even if Def == User. |
121 | 13.1M | if (!isReachableFromEntry(UseBB)) |
122 | 6 | return true; |
123 | 13.1M | |
124 | 13.1M | // Unreachable definitions don't dominate anything. |
125 | 13.1M | if (!isReachableFromEntry(DefBB)) |
126 | 6 | return false; |
127 | 13.1M | |
128 | 13.1M | // An instruction doesn't dominate a use in itself. |
129 | 13.1M | if (Def == User) |
130 | 220k | return false; |
131 | 12.9M | |
132 | 12.9M | // The value defined by an invoke dominates an instruction only if it |
133 | 12.9M | // dominates every instruction in UseBB. |
134 | 12.9M | // A PHI is dominated only if the instruction dominates every possible use in |
135 | 12.9M | // the UseBB. |
136 | 12.9M | if (isa<InvokeInst>(Def) || isa<PHINode>(User)11.2M ) |
137 | 3.56M | return dominates(Def, UseBB); |
138 | 9.35M | |
139 | 9.35M | if (DefBB != UseBB) |
140 | 8.38M | return dominates(DefBB, UseBB); |
141 | 968k | |
142 | 968k | // Loop through the basic block until we find Def or User. |
143 | 968k | BasicBlock::const_iterator I = DefBB->begin(); |
144 | 47.8M | for (; &*I != Def && &*I != User46.9M ; ++I46.8M ) |
145 | 46.8M | /*empty*/; |
146 | 968k | |
147 | 968k | return &*I == Def; |
148 | 968k | } |
149 | | |
150 | | // true if Def would dominate a use in any instruction in UseBB. |
151 | | // note that dominates(Def, Def->getParent()) is false. |
152 | | bool DominatorTree::dominates(const Instruction *Def, |
153 | 4.20M | const BasicBlock *UseBB) const { |
154 | 4.20M | const BasicBlock *DefBB = Def->getParent(); |
155 | 4.20M | |
156 | 4.20M | // Any unreachable use is dominated, even if DefBB == UseBB. |
157 | 4.20M | if (!isReachableFromEntry(UseBB)) |
158 | 3 | return true; |
159 | 4.20M | |
160 | 4.20M | // Unreachable definitions don't dominate anything. |
161 | 4.20M | if (!isReachableFromEntry(DefBB)) |
162 | 9 | return false; |
163 | 4.20M | |
164 | 4.20M | if (DefBB == UseBB) |
165 | 608k | return false; |
166 | 3.59M | |
167 | 3.59M | // Invoke results are only usable in the normal destination, not in the |
168 | 3.59M | // exceptional destination. |
169 | 3.59M | if (const auto *II = dyn_cast<InvokeInst>(Def)) { |
170 | 1.68M | BasicBlock *NormalDest = II->getNormalDest(); |
171 | 1.68M | BasicBlockEdge E(DefBB, NormalDest); |
172 | 1.68M | return dominates(E, UseBB); |
173 | 1.68M | } |
174 | 1.90M | |
175 | 1.90M | return dominates(DefBB, UseBB); |
176 | 1.90M | } |
177 | | |
178 | | bool DominatorTree::dominates(const BasicBlockEdge &BBE, |
179 | 12.6M | const BasicBlock *UseBB) const { |
180 | 12.6M | // If the BB the edge ends in doesn't dominate the use BB, then the |
181 | 12.6M | // edge also doesn't. |
182 | 12.6M | const BasicBlock *Start = BBE.getStart(); |
183 | 12.6M | const BasicBlock *End = BBE.getEnd(); |
184 | 12.6M | if (!dominates(End, UseBB)) |
185 | 11.3M | return false; |
186 | 1.26M | |
187 | 1.26M | // Simple case: if the end BB has a single predecessor, the fact that it |
188 | 1.26M | // dominates the use block implies that the edge also does. |
189 | 1.26M | if (End->getSinglePredecessor()) |
190 | 643k | return true; |
191 | 617k | |
192 | 617k | // The normal edge from the invoke is critical. Conceptually, what we would |
193 | 617k | // like to do is split it and check if the new block dominates the use. |
194 | 617k | // With X being the new block, the graph would look like: |
195 | 617k | // |
196 | 617k | // DefBB |
197 | 617k | // /\ . . |
198 | 617k | // / \ . . |
199 | 617k | // / \ . . |
200 | 617k | // / \ | | |
201 | 617k | // A X B C |
202 | 617k | // | \ | / |
203 | 617k | // . \|/ |
204 | 617k | // . NormalDest |
205 | 617k | // . |
206 | 617k | // |
207 | 617k | // Given the definition of dominance, NormalDest is dominated by X iff X |
208 | 617k | // dominates all of NormalDest's predecessors (X, B, C in the example). X |
209 | 617k | // trivially dominates itself, so we only have to find if it dominates the |
210 | 617k | // other predecessors. Since the only way out of X is via NormalDest, X can |
211 | 617k | // only properly dominate a node if NormalDest dominates that node too. |
212 | 617k | int IsDuplicateEdge = 0; |
213 | 617k | for (const_pred_iterator PI = pred_begin(End), E = pred_end(End); |
214 | 789k | PI != E; ++PI172k ) { |
215 | 789k | const BasicBlock *BB = *PI; |
216 | 789k | if (BB == Start) { |
217 | 171k | // If there are multiple edges between Start and End, by definition they |
218 | 171k | // can't dominate anything. |
219 | 171k | if (IsDuplicateEdge++) |
220 | 2 | return false; |
221 | 171k | continue; |
222 | 171k | } |
223 | 617k | |
224 | 617k | if (!dominates(End, BB)) |
225 | 616k | return false; |
226 | 617k | } |
227 | 617k | return true627 ; |
228 | 617k | } |
229 | | |
230 | 7.11M | bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const { |
231 | 7.11M | Instruction *UserInst = cast<Instruction>(U.getUser()); |
232 | 7.11M | // A PHI in the end of the edge is dominated by it. |
233 | 7.11M | PHINode *PN = dyn_cast<PHINode>(UserInst); |
234 | 7.11M | if (PN && PN->getParent() == BBE.getEnd()1.00M && |
235 | 7.11M | PN->getIncomingBlock(U) == BBE.getStart()311k ) |
236 | 249k | return true; |
237 | 6.86M | |
238 | 6.86M | // Otherwise use the edge-dominates-block query, which |
239 | 6.86M | // handles the crazy critical edge cases properly. |
240 | 6.86M | const BasicBlock *UseBB; |
241 | 6.86M | if (PN) |
242 | 760k | UseBB = PN->getIncomingBlock(U); |
243 | 6.10M | else |
244 | 6.10M | UseBB = UserInst->getParent(); |
245 | 6.86M | return dominates(BBE, UseBB); |
246 | 6.86M | } |
247 | | |
248 | 564k | bool DominatorTree::dominates(const Instruction *Def, const Use &U) const { |
249 | 564k | Instruction *UserInst = cast<Instruction>(U.getUser()); |
250 | 564k | const BasicBlock *DefBB = Def->getParent(); |
251 | 564k | |
252 | 564k | // Determine the block in which the use happens. PHI nodes use |
253 | 564k | // their operands on edges; simulate this by thinking of the use |
254 | 564k | // happening at the end of the predecessor block. |
255 | 564k | const BasicBlock *UseBB; |
256 | 564k | if (PHINode *PN = dyn_cast<PHINode>(UserInst)) |
257 | 125k | UseBB = PN->getIncomingBlock(U); |
258 | 439k | else |
259 | 439k | UseBB = UserInst->getParent(); |
260 | 564k | |
261 | 564k | // Any unreachable use is dominated, even if Def == User. |
262 | 564k | if (!isReachableFromEntry(UseBB)) |
263 | 956 | return true; |
264 | 563k | |
265 | 563k | // Unreachable definitions don't dominate anything. |
266 | 563k | if (!isReachableFromEntry(DefBB)) |
267 | 0 | return false; |
268 | 563k | |
269 | 563k | // Invoke instructions define their return values on the edges to their normal |
270 | 563k | // successors, so we have to handle them specially. |
271 | 563k | // Among other things, this means they don't dominate anything in |
272 | 563k | // their own block, except possibly a phi, so we don't need to |
273 | 563k | // walk the block in any case. |
274 | 563k | if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) { |
275 | 1.28k | BasicBlock *NormalDest = II->getNormalDest(); |
276 | 1.28k | BasicBlockEdge E(DefBB, NormalDest); |
277 | 1.28k | return dominates(E, U); |
278 | 1.28k | } |
279 | 562k | |
280 | 562k | // If the def and use are in different blocks, do a simple CFG dominator |
281 | 562k | // tree query. |
282 | 562k | if (DefBB != UseBB) |
283 | 453k | return dominates(DefBB, UseBB); |
284 | 108k | |
285 | 108k | // Ok, def and use are in the same block. If the def is an invoke, it |
286 | 108k | // doesn't dominate anything in the block. If it's a PHI, it dominates |
287 | 108k | // everything in the block. |
288 | 108k | if (isa<PHINode>(UserInst)) |
289 | 108k | return true; |
290 | 281 | |
291 | 281 | // Otherwise, just loop through the basic block until we find Def or User. |
292 | 281 | BasicBlock::const_iterator I = DefBB->begin(); |
293 | 580 | for (; &*I != Def && &*I != UserInst319 ; ++I299 ) |
294 | 299 | /*empty*/; |
295 | 281 | |
296 | 281 | return &*I != UserInst; |
297 | 281 | } |
298 | | |
299 | 126 | bool DominatorTree::isReachableFromEntry(const Use &U) const { |
300 | 126 | Instruction *I = dyn_cast<Instruction>(U.getUser()); |
301 | 126 | |
302 | 126 | // ConstantExprs aren't really reachable from the entry block, but they |
303 | 126 | // don't need to be treated like unreachable code either. |
304 | 126 | if (!I) return true0 ; |
305 | 126 | |
306 | 126 | // PHI nodes use their operands on their incoming edges. |
307 | 126 | if (PHINode *PN = dyn_cast<PHINode>(I)) |
308 | 8 | return isReachableFromEntry(PN->getIncomingBlock(U)); |
309 | 118 | |
310 | 118 | // Everything else uses their operands in their own block. |
311 | 118 | return isReachableFromEntry(I->getParent()); |
312 | 118 | } |
313 | | |
314 | | //===----------------------------------------------------------------------===// |
315 | | // DominatorTreeAnalysis and related pass implementations |
316 | | //===----------------------------------------------------------------------===// |
317 | | // |
318 | | // This implements the DominatorTreeAnalysis which is used with the new pass |
319 | | // manager. It also implements some methods from utility passes. |
320 | | // |
321 | | //===----------------------------------------------------------------------===// |
322 | | |
323 | | DominatorTree DominatorTreeAnalysis::run(Function &F, |
324 | 9.02k | FunctionAnalysisManager &) { |
325 | 9.02k | DominatorTree DT; |
326 | 9.02k | DT.recalculate(F); |
327 | 9.02k | return DT; |
328 | 9.02k | } |
329 | | |
330 | | AnalysisKey DominatorTreeAnalysis::Key; |
331 | | |
332 | 2 | DominatorTreePrinterPass::DominatorTreePrinterPass(raw_ostream &OS) : OS(OS) {} |
333 | | |
334 | | PreservedAnalyses DominatorTreePrinterPass::run(Function &F, |
335 | 3 | FunctionAnalysisManager &AM) { |
336 | 3 | OS << "DominatorTree for function: " << F.getName() << "\n"; |
337 | 3 | AM.getResult<DominatorTreeAnalysis>(F).print(OS); |
338 | 3 | |
339 | 3 | return PreservedAnalyses::all(); |
340 | 3 | } |
341 | | |
342 | | PreservedAnalyses DominatorTreeVerifierPass::run(Function &F, |
343 | 32 | FunctionAnalysisManager &AM) { |
344 | 32 | auto &DT = AM.getResult<DominatorTreeAnalysis>(F); |
345 | 32 | assert(DT.verify()); |
346 | 32 | (void)DT; |
347 | 32 | return PreservedAnalyses::all(); |
348 | 32 | } |
349 | | |
350 | | //===----------------------------------------------------------------------===// |
351 | | // DominatorTreeWrapperPass Implementation |
352 | | //===----------------------------------------------------------------------===// |
353 | | // |
354 | | // The implementation details of the wrapper pass that holds a DominatorTree |
355 | | // suitable for use with the legacy pass manager. |
356 | | // |
357 | | //===----------------------------------------------------------------------===// |
358 | | |
359 | | char DominatorTreeWrapperPass::ID = 0; |
360 | | INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree", |
361 | | "Dominator Tree Construction", true, true) |
362 | | |
363 | 9.23M | bool DominatorTreeWrapperPass::runOnFunction(Function &F) { |
364 | 9.23M | DT.recalculate(F); |
365 | 9.23M | return false; |
366 | 9.23M | } |
367 | | |
368 | 0 | void DominatorTreeWrapperPass::verifyAnalysis() const { |
369 | 0 | if (VerifyDomInfo) |
370 | 0 | assert(DT.verify(DominatorTree::VerificationLevel::Full)); |
371 | 0 | else if (ExpensiveChecksEnabled) |
372 | 0 | assert(DT.verify(DominatorTree::VerificationLevel::Basic)); |
373 | 0 | } |
374 | | |
375 | 6 | void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const { |
376 | 6 | DT.print(OS); |
377 | 6 | } |
378 | | |