LLVM 19.0.0git
Dominators.cpp
Go to the documentation of this file.
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"
23#include "llvm/IR/PassManager.h"
25#include "llvm/PassRegistry.h"
30
31#include <cassert>
32
33namespace llvm {
34class Argument;
35class Constant;
36class Value;
37} // namespace llvm
38using namespace llvm;
39
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
52 unsigned NumEdgesToEnd = 0;
53 for (const BasicBlock *Succ : successors(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
74template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase
75template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase
76
78
79template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
81template void
82llvm::DomTreeBuilder::CalculateWithUpdates<DomTreeBuilder::BBDomTree>(
83 DomTreeBuilder::BBDomTree &DT, BBUpdates U);
84
85template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
87// No CalculateWithUpdates<PostDomTree> instantiation, unless a usecase arises.
88
89template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>(
91template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>(
93
94template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
96template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
98
99template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
102template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
105
106template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
109template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
112
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>(U.getUser());
124 if (auto *PN = dyn_cast<PHINode>(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(BB, PN->getIncomingBlock(U));
128 else
129 return properlyDominates(BB, 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!
136 const Instruction *User) const {
137 const Instruction *Def = dyn_cast<Instruction>(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(UseBB))
149 return true;
150
151 // Unreachable definitions don't dominate anything.
152 if (!isReachableFromEntry(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>(Def) || isa<CallBrInst>(Def) || isa<PHINode>(User))
164 return dominates(Def, UseBB);
165
166 if (DefBB != UseBB)
167 return dominates(DefBB, UseBB);
168
169 return Def->comesBefore(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.
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(UseBB))
180 return true;
181
182 // Unreachable definitions don't dominate anything.
183 if (!isReachableFromEntry(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>(Def)) {
192 BasicBlock *NormalDest = II->getNormalDest();
193 BasicBlockEdge E(DefBB, NormalDest);
194 return dominates(E, UseBB);
195 }
196
197 return dominates(DefBB, UseBB);
198}
199
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(End, 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(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(End, 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>(U.getUser());
252 // A PHI in the end of the edge is dominated by it.
253 PHINode *PN = dyn_cast<PHINode>(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>(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>(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>(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(UseBB))
290 return true;
291
292 // Unreachable definitions don't dominate anything.
293 if (!isReachableFromEntry(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>(Def)) {
302 BasicBlock *NormalDest = II->getNormalDest();
303 BasicBlockEdge E(DefBB, NormalDest);
304 return dominates(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(DefBB, 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>(UserInst))
316 return true;
317
318 return Def->comesBefore(UserInst);
319}
320
322 Instruction *I = dyn_cast<Instruction>(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>(I))
330 return isReachableFromEntry(PN->getIncomingBlock(U));
331
332 // Everything else uses their operands in their own block.
333 return isReachableFromEntry(I->getParent());
334}
335
336// Edge BBE1 dominates edge BBE2 if they match or BBE1 dominates start of BBE2.
338 const BasicBlockEdge &BBE2) const {
339 if (BBE1.getStart() == BBE2.getStart() && BBE1.getEnd() == BBE2.getEnd())
340 return true;
341 return dominates(BBE1, BBE2.getStart());
342}
343
345 Instruction *I2) const {
346 BasicBlock *BB1 = I1->getParent();
347 BasicBlock *BB2 = I2->getParent();
348 if (BB1 == BB2)
349 return I1->comesBefore(I2) ? I1 : I2;
350 if (!isReachableFromEntry(BB2))
351 return I1;
352 if (!isReachableFromEntry(BB1))
353 return I2;
354 BasicBlock *DomBB = findNearestCommonDominator(BB1, 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
373 DominatorTree DT;
374 DT.recalculate(F);
375 return DT;
376}
377
378AnalysisKey DominatorTreeAnalysis::Key;
379
381
384 OS << "DominatorTree for function: " << F.getName() << "\n";
386
387 return PreservedAnalyses::all();
388}
389
392 auto &DT = AM.getResult<DominatorTreeAnalysis>(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
408
411}
412
414 "Dominator Tree Construction", true, true)
415
417 DT.recalculate(F);
418 return false;
419}
420
422 if (VerifyDomInfo)
423 assert(DT.verify(DominatorTree::VerificationLevel::Full));
424 else if (ExpensiveChecksEnabled)
425 assert(DT.verify(DominatorTree::VerificationLevel::Basic));
426}
427
429 DT.print(OS);
430}
BlockVerifier::State From
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static constexpr bool ExpensiveChecksEnabled
Definition: Dominators.cpp:48
static cl::opt< bool, true > VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), cl::Hidden, cl::desc("Verify dominator info (time consuming)"))
bool End
Definition: ELF_riscv.cpp:480
static bool runOnFunction(Function &F, bool PostInlining)
Generic dominator tree construction - this file provides routines to construct immediate dominator in...
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
static constexpr bool ExpensiveChecksEnabled
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: Analysis.h:47
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:387
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
const BasicBlock * getEnd() const
Definition: Dominators.h:112
const BasicBlock * getStart() const
Definition: Dominators.h:108
bool isSingleEdge() const
Check if this is the only edge between Start and End.
Definition: Dominators.cpp:51
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:220
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:70
This is an important base class in LLVM.
Definition: Constant.h:41
Base class for the actual dominator tree node.
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
DominatorTree run(Function &F, FunctionAnalysisManager &)
Run the analysis pass over a function and produce a dominator tree.
Definition: Dominators.cpp:371
Core dominator tree base class.
void print(raw_ostream &O) const
print - Convert to human readable form
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
bool properlyDominates(const DomTreeNodeBase< BasicBlock > *A, const DomTreeNodeBase< BasicBlock > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
DominatorTreePrinterPass(raw_ostream &OS)
Definition: Dominators.cpp:380
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Dominators.cpp:382
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:317
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: Dominators.cpp:428
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: Dominators.cpp:421
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:321
Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const
Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...
Definition: Dominators.cpp:344
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: Dominators.cpp:113
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
const BasicBlock * getParent() const
Definition: Instruction.h:151
Invoke instruction.
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: Analysis.h:264
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:470
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto successors(const MachineBasicBlock *BB)
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
void initializeDominatorTreeWrapperPassPass(PassRegistry &)
bool VerifyDomInfo
Enables verification of dominator trees.
Definition: Dominators.cpp:40
auto predecessors(const MachineBasicBlock *BB)
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:26
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Dominators.cpp:390