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/StringRef.h"
18#include "llvm/Config/llvm-config.h"
19#include "llvm/IR/CFG.h"
20#include "llvm/IR/Function.h"
21#include "llvm/IR/Instruction.h"
22#include "llvm/IR/Instructions.h"
23#include "llvm/IR/PassManager.h"
24#include "llvm/InitializePasses.h"
25#include "llvm/PassRegistry.h"
26#include "llvm/Support/Casting.h"
27#include "llvm/Support/CommandLine.h"
28#include "llvm/Support/Compiler.h"
29#include "llvm/Support/GenericDomTreeConstruction.h"
30#include "llvm/Support/raw_ostream.h"
31
32#include <cassert>
33
34namespace llvm {
35class Argument;
36class Constant;
37class Value;
38} // namespace llvm
39using namespace llvm;
40
41bool llvm::VerifyDomInfo = false;
42static cl::opt<bool, true>
43 VerifyDomInfoX("verify-dom-info", cl::location(L&: VerifyDomInfo), cl::Hidden,
44 cl::desc("Verify dominator info (time consuming)"));
45
46#ifdef EXPENSIVE_CHECKS
47static constexpr bool ExpensiveChecksEnabled = true;
48#else
49static constexpr bool ExpensiveChecksEnabled = false;
50#endif
51
52bool BasicBlockEdge::isSingleEdge() const {
53 unsigned NumEdgesToEnd = 0;
54 for (const BasicBlock *Succ : successors(BB: Start)) {
55 if (Succ == End)
56 ++NumEdgesToEnd;
57 if (NumEdgesToEnd >= 2)
58 return false;
59 }
60 assert(NumEdgesToEnd == 1);
61 return true;
62}
63
64//===----------------------------------------------------------------------===//
65// DominatorTree Implementation
66//===----------------------------------------------------------------------===//
67//
68// Provide public access to DominatorTree information. Implementation details
69// can be found in Dominators.h, GenericDomTree.h, and
70// GenericDomTreeConstruction.h.
71//
72//===----------------------------------------------------------------------===//
73
74template class LLVM_EXPORT_TEMPLATE llvm::DomTreeNodeBase<BasicBlock>;
75template class LLVM_EXPORT_TEMPLATE
76 llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase
77template class LLVM_EXPORT_TEMPLATE
78 llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase
79
80template class llvm::cfg::Update<BasicBlock *>;
81
82template LLVM_EXPORT_TEMPLATE void
83llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
84 DomTreeBuilder::BBDomTree &DT);
85template LLVM_EXPORT_TEMPLATE void
86llvm::DomTreeBuilder::CalculateWithUpdates<DomTreeBuilder::BBDomTree>(
87 DomTreeBuilder::BBDomTree &DT, BBUpdates U);
88
89template LLVM_EXPORT_TEMPLATE void
90llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
91 DomTreeBuilder::BBPostDomTree &DT);
92// No CalculateWithUpdates<PostDomTree> instantiation, unless a usecase arises.
93
94template LLVM_EXPORT_TEMPLATE void
95llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>(
96 DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
97template LLVM_EXPORT_TEMPLATE void
98llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>(
99 DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
100
101template LLVM_EXPORT_TEMPLATE void
102llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
103 DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
104template LLVM_EXPORT_TEMPLATE void
105llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
106 DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
107
108template LLVM_EXPORT_TEMPLATE void
109llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
110 DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBDomTreeGraphDiff &,
111 DomTreeBuilder::BBDomTreeGraphDiff *);
112template LLVM_EXPORT_TEMPLATE void
113llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
114 DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBPostDomTreeGraphDiff &,
115 DomTreeBuilder::BBPostDomTreeGraphDiff *);
116
117template LLVM_EXPORT_TEMPLATE bool
118llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
119 const DomTreeBuilder::BBDomTree &DT,
120 DomTreeBuilder::BBDomTree::VerificationLevel VL);
121template LLVM_EXPORT_TEMPLATE bool
122llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
123 const DomTreeBuilder::BBPostDomTree &DT,
124 DomTreeBuilder::BBPostDomTree::VerificationLevel VL);
125
126bool DominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
127 FunctionAnalysisManager::Invalidator &) {
128 // Check whether the analysis, all analyses on functions, or the function's
129 // CFG have been preserved.
130 auto PAC = PA.getChecker<DominatorTreeAnalysis>();
131 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
132 PAC.preservedSet<CFGAnalyses>());
133}
134
135bool DominatorTree::dominates(const BasicBlock *BB, const Use &U) const {
136 Instruction *UserInst = cast<Instruction>(Val: U.getUser());
137 if (auto *PN = dyn_cast<PHINode>(Val: UserInst))
138 // A phi use using a value from a block is dominated by the end of that
139 // block. Note that the phi's parent block may not be.
140 return dominates(A: BB, B: PN->getIncomingBlock(U));
141 else
142 return properlyDominates(A: BB, B: UserInst->getParent());
143}
144
145// dominates - Return true if Def dominates a use in User. This performs
146// the special checks necessary if Def and User are in the same basic block.
147// Note that Def doesn't dominate a use in Def itself!
148bool DominatorTree::dominates(const Value *DefV,
149 const Instruction *User) const {
150 const Instruction *Def = dyn_cast<Instruction>(Val: DefV);
151 if (!Def) {
152 assert((isa<Argument>(DefV) || isa<Constant>(DefV)) &&
153 "Should be called with an instruction, argument or constant");
154 return true; // Arguments and constants dominate everything.
155 }
156
157 const BasicBlock *UseBB = User->getParent();
158 const BasicBlock *DefBB = Def->getParent();
159
160 // Any unreachable use is dominated, even if Def == User.
161 if (!isReachableFromEntry(A: UseBB))
162 return true;
163
164 // Unreachable definitions don't dominate anything.
165 if (!isReachableFromEntry(A: DefBB))
166 return false;
167
168 // An instruction doesn't dominate a use in itself.
169 if (Def == User)
170 return false;
171
172 // The value defined by an invoke dominates an instruction only if it
173 // dominates every instruction in UseBB.
174 // A PHI is dominated only if the instruction dominates every possible use in
175 // the UseBB.
176 if (isa<InvokeInst>(Val: Def) || isa<CallBrInst>(Val: Def) || isa<PHINode>(Val: User))
177 return dominates(Def, BB: UseBB);
178
179 if (DefBB != UseBB)
180 return dominates(A: DefBB, B: UseBB);
181
182 return Def->comesBefore(Other: User);
183}
184
185// true if Def would dominate a use in any instruction in UseBB.
186// note that dominates(Def, Def->getParent()) is false.
187bool DominatorTree::dominates(const Instruction *Def,
188 const BasicBlock *UseBB) const {
189 const BasicBlock *DefBB = Def->getParent();
190
191 // Any unreachable use is dominated, even if DefBB == UseBB.
192 if (!isReachableFromEntry(A: UseBB))
193 return true;
194
195 // Unreachable definitions don't dominate anything.
196 if (!isReachableFromEntry(A: DefBB))
197 return false;
198
199 if (DefBB == UseBB)
200 return false;
201
202 // Invoke results are only usable in the normal destination, not in the
203 // exceptional destination.
204 if (const auto *II = dyn_cast<InvokeInst>(Val: Def)) {
205 BasicBlock *NormalDest = II->getNormalDest();
206 BasicBlockEdge E(DefBB, NormalDest);
207 return dominates(BBE: E, BB: UseBB);
208 }
209
210 return dominates(A: DefBB, B: UseBB);
211}
212
213bool DominatorTree::dominates(const BasicBlockEdge &BBE,
214 const BasicBlock *UseBB) const {
215 // If the BB the edge ends in doesn't dominate the use BB, then the
216 // edge also doesn't.
217 const BasicBlock *Start = BBE.getStart();
218 const BasicBlock *End = BBE.getEnd();
219 if (!dominates(A: End, B: UseBB))
220 return false;
221
222 // Simple case: if the end BB has a single predecessor, the fact that it
223 // dominates the use block implies that the edge also does.
224 if (End->getSinglePredecessor())
225 return true;
226
227 // The normal edge from the invoke is critical. Conceptually, what we would
228 // like to do is split it and check if the new block dominates the use.
229 // With X being the new block, the graph would look like:
230 //
231 // DefBB
232 // /\ . .
233 // / \ . .
234 // / \ . .
235 // / \ | |
236 // A X B C
237 // | \ | /
238 // . \|/
239 // . NormalDest
240 // .
241 //
242 // Given the definition of dominance, NormalDest is dominated by X iff X
243 // dominates all of NormalDest's predecessors (X, B, C in the example). X
244 // trivially dominates itself, so we only have to find if it dominates the
245 // other predecessors. Since the only way out of X is via NormalDest, X can
246 // only properly dominate a node if NormalDest dominates that node too.
247 int IsDuplicateEdge = 0;
248 for (const BasicBlock *BB : predecessors(BB: End)) {
249 if (BB == Start) {
250 // If there are multiple edges between Start and End, by definition they
251 // can't dominate anything.
252 if (IsDuplicateEdge++)
253 return false;
254 continue;
255 }
256
257 if (!dominates(A: End, B: BB))
258 return false;
259 }
260 return true;
261}
262
263bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
264 Instruction *UserInst = cast<Instruction>(Val: U.getUser());
265 // A PHI in the end of the edge is dominated by it.
266 PHINode *PN = dyn_cast<PHINode>(Val: UserInst);
267 if (PN && PN->getParent() == BBE.getEnd() &&
268 PN->getIncomingBlock(U) == BBE.getStart())
269 return true;
270
271 // Otherwise use the edge-dominates-block query, which
272 // handles the crazy critical edge cases properly.
273 const BasicBlock *UseBB;
274 if (PN)
275 UseBB = PN->getIncomingBlock(U);
276 else
277 UseBB = UserInst->getParent();
278 return dominates(BBE, UseBB);
279}
280
281bool DominatorTree::dominates(const Value *DefV, const Use &U) const {
282 const Instruction *Def = dyn_cast<Instruction>(Val: DefV);
283 if (!Def) {
284 assert((isa<Argument>(DefV) || isa<Constant>(DefV)) &&
285 "Should be called with an instruction, argument or constant");
286 return true; // Arguments and constants dominate everything.
287 }
288
289 Instruction *UserInst = cast<Instruction>(Val: U.getUser());
290 const BasicBlock *DefBB = Def->getParent();
291
292 // Determine the block in which the use happens. PHI nodes use
293 // their operands on edges; simulate this by thinking of the use
294 // happening at the end of the predecessor block.
295 const BasicBlock *UseBB;
296 if (PHINode *PN = dyn_cast<PHINode>(Val: UserInst))
297 UseBB = PN->getIncomingBlock(U);
298 else
299 UseBB = UserInst->getParent();
300
301 // Any unreachable use is dominated, even if Def == User.
302 if (!isReachableFromEntry(A: UseBB))
303 return true;
304
305 // Unreachable definitions don't dominate anything.
306 if (!isReachableFromEntry(A: DefBB))
307 return false;
308
309 // Invoke instructions define their return values on the edges to their normal
310 // successors, so we have to handle them specially.
311 // Among other things, this means they don't dominate anything in
312 // their own block, except possibly a phi, so we don't need to
313 // walk the block in any case.
314 if (const InvokeInst *II = dyn_cast<InvokeInst>(Val: Def)) {
315 BasicBlock *NormalDest = II->getNormalDest();
316 BasicBlockEdge E(DefBB, NormalDest);
317 return dominates(BBE: E, U);
318 }
319
320 // If the def and use are in different blocks, do a simple CFG dominator
321 // tree query.
322 if (DefBB != UseBB)
323 return dominates(A: DefBB, B: UseBB);
324
325 // Ok, def and use are in the same block. If the def is an invoke, it
326 // doesn't dominate anything in the block. If it's a PHI, it dominates
327 // everything in the block.
328 if (isa<PHINode>(Val: UserInst))
329 return true;
330
331 return Def->comesBefore(Other: UserInst);
332}
333
334bool DominatorTree::isReachableFromEntry(const Use &U) const {
335 Instruction *I = dyn_cast<Instruction>(Val: U.getUser());
336
337 // ConstantExprs aren't really reachable from the entry block, but they
338 // don't need to be treated like unreachable code either.
339 if (!I) return true;
340
341 // PHI nodes use their operands on their incoming edges.
342 if (PHINode *PN = dyn_cast<PHINode>(Val: I))
343 return isReachableFromEntry(A: PN->getIncomingBlock(U));
344
345 // Everything else uses their operands in their own block.
346 return isReachableFromEntry(A: I->getParent());
347}
348
349// Edge BBE1 dominates edge BBE2 if they match or BBE1 dominates start of BBE2.
350bool DominatorTree::dominates(const BasicBlockEdge &BBE1,
351 const BasicBlockEdge &BBE2) const {
352 if (BBE1.getStart() == BBE2.getStart() && BBE1.getEnd() == BBE2.getEnd())
353 return true;
354 return dominates(BBE: BBE1, UseBB: BBE2.getStart());
355}
356
357Instruction *DominatorTree::findNearestCommonDominator(Instruction *I1,
358 Instruction *I2) const {
359 BasicBlock *BB1 = I1->getParent();
360 BasicBlock *BB2 = I2->getParent();
361 if (BB1 == BB2)
362 return I1->comesBefore(Other: I2) ? I1 : I2;
363 if (!isReachableFromEntry(A: BB2))
364 return I1;
365 if (!isReachableFromEntry(A: BB1))
366 return I2;
367 BasicBlock *DomBB = findNearestCommonDominator(A: BB1, B: BB2);
368 if (BB1 == DomBB)
369 return I1;
370 if (BB2 == DomBB)
371 return I2;
372 return DomBB->getTerminator();
373}
374
375//===----------------------------------------------------------------------===//
376// DominatorTreeAnalysis and related pass implementations
377//===----------------------------------------------------------------------===//
378//
379// This implements the DominatorTreeAnalysis which is used with the new pass
380// manager. It also implements some methods from utility passes.
381//
382//===----------------------------------------------------------------------===//
383
384DominatorTree DominatorTreeAnalysis::run(Function &F,
385 FunctionAnalysisManager &) {
386 DominatorTree DT;
387 DT.recalculate(Func&: F);
388 return DT;
389}
390
391AnalysisKey DominatorTreeAnalysis::Key;
392
393DominatorTreePrinterPass::DominatorTreePrinterPass(raw_ostream &OS) : OS(OS) {}
394
395PreservedAnalyses DominatorTreePrinterPass::run(Function &F,
396 FunctionAnalysisManager &AM) {
397 OS << "DominatorTree for function: " << F.getName() << "\n";
398 AM.getResult<DominatorTreeAnalysis>(IR&: F).print(O&: OS);
399
400 return PreservedAnalyses::all();
401}
402
403PreservedAnalyses DominatorTreeVerifierPass::run(Function &F,
404 FunctionAnalysisManager &AM) {
405 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
406 assert(DT.verify());
407 (void)DT;
408 return PreservedAnalyses::all();
409}
410
411//===----------------------------------------------------------------------===//
412// DominatorTreeWrapperPass Implementation
413//===----------------------------------------------------------------------===//
414//
415// The implementation details of the wrapper pass that holds a DominatorTree
416// suitable for use with the legacy pass manager.
417//
418//===----------------------------------------------------------------------===//
419
420char DominatorTreeWrapperPass::ID = 0;
421
422DominatorTreeWrapperPass::DominatorTreeWrapperPass() : FunctionPass(ID) {
423 initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
424}
425
426INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree",
427 "Dominator Tree Construction", true, true)
428
429bool DominatorTreeWrapperPass::runOnFunction(Function &F) {
430 DT.recalculate(Func&: F);
431 return false;
432}
433
434void DominatorTreeWrapperPass::verifyAnalysis() const {
435 if (VerifyDomInfo)
436 assert(DT.verify(DominatorTree::VerificationLevel::Full));
437 else if (ExpensiveChecksEnabled)
438 assert(DT.verify(DominatorTree::VerificationLevel::Basic));
439}
440
441void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
442 DT.print(O&: OS);
443}
444