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