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