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