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