LLVM 18.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 const Instruction *TI = Start->getTerminator();
53 unsigned NumEdgesToEnd = 0;
54 for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) {
55 if (TI->getSuccessor(i) == End)
56 ++NumEdgesToEnd;
57 if (NumEdgesToEnd >= 2)
58 return false;
59 }
60 assert(NumEdgesToEnd == 1);
61 return true;
62}
63
64//===----------------------------------------------------------------------===//
65// DominatorTree Implementation
66//===----------------------------------------------------------------------===//
67//
68// Provide public access to DominatorTree information. Implementation details
69// can be found in Dominators.h, GenericDomTree.h, and
70// GenericDomTreeConstruction.h.
71//
72//===----------------------------------------------------------------------===//
73
75template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase
76template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase
77
79
80template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
82template void
83llvm::DomTreeBuilder::CalculateWithUpdates<DomTreeBuilder::BBDomTree>(
84 DomTreeBuilder::BBDomTree &DT, BBUpdates U);
85
86template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
88// No CalculateWithUpdates<PostDomTree> instantiation, unless a usecase arises.
89
90template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>(
92template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>(
94
95template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
97template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
99
100template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
103template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
106
107template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
110template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
113
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>(U.getUser());
125 if (auto *PN = dyn_cast<PHINode>(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(BB, PN->getIncomingBlock(U));
129 else
130 return properlyDominates(BB, 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!
137 const Instruction *User) const {
138 const Instruction *Def = dyn_cast<Instruction>(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(UseBB))
150 return true;
151
152 // Unreachable definitions don't dominate anything.
153 if (!isReachableFromEntry(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>(Def) || isa<CallBrInst>(Def) || isa<PHINode>(User))
165 return dominates(Def, UseBB);
166
167 if (DefBB != UseBB)
168 return dominates(DefBB, UseBB);
169
170 return Def->comesBefore(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.
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(UseBB))
181 return true;
182
183 // Unreachable definitions don't dominate anything.
184 if (!isReachableFromEntry(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>(Def)) {
193 BasicBlock *NormalDest = II->getNormalDest();
194 BasicBlockEdge E(DefBB, NormalDest);
195 return dominates(E, UseBB);
196 }
197
198 return dominates(DefBB, UseBB);
199}
200
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(End, 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(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(End, 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>(U.getUser());
253 // A PHI in the end of the edge is dominated by it.
254 PHINode *PN = dyn_cast<PHINode>(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>(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>(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>(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(UseBB))
291 return true;
292
293 // Unreachable definitions don't dominate anything.
294 if (!isReachableFromEntry(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>(Def)) {
303 BasicBlock *NormalDest = II->getNormalDest();
304 BasicBlockEdge E(DefBB, NormalDest);
305 return dominates(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(DefBB, 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>(UserInst))
317 return true;
318
319 return Def->comesBefore(UserInst);
320}
321
323 Instruction *I = dyn_cast<Instruction>(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>(I))
331 return isReachableFromEntry(PN->getIncomingBlock(U));
332
333 // Everything else uses their operands in their own block.
334 return isReachableFromEntry(I->getParent());
335}
336
337// Edge BBE1 dominates edge BBE2 if they match or BBE1 dominates start of BBE2.
339 const BasicBlockEdge &BBE2) const {
340 if (BBE1.getStart() == BBE2.getStart() && BBE1.getEnd() == BBE2.getEnd())
341 return true;
342 return dominates(BBE1, BBE2.getStart());
343}
344
346 Instruction *I2) const {
347 BasicBlock *BB1 = I1->getParent();
348 BasicBlock *BB2 = I2->getParent();
349 if (BB1 == BB2)
350 return I1->comesBefore(I2) ? I1 : I2;
351 if (!isReachableFromEntry(BB2))
352 return I1;
353 if (!isReachableFromEntry(BB1))
354 return I2;
355 BasicBlock *DomBB = findNearestCommonDominator(BB1, 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
374 DominatorTree DT;
375 DT.recalculate(F);
376 return DT;
377}
378
379AnalysisKey DominatorTreeAnalysis::Key;
380
382
385 OS << "DominatorTree for function: " << F.getName() << "\n";
387
388 return PreservedAnalyses::all();
389}
390
393 auto &DT = AM.getResult<DominatorTreeAnalysis>(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
409
412}
413
415 "Dominator Tree Construction", true, true)
416
418 DT.recalculate(F);
419 return false;
420}
421
423 if (VerifyDomInfo)
424 assert(DT.verify(DominatorTree::VerificationLevel::Full));
425 else if (ExpensiveChecksEnabled)
426 assert(DT.verify(DominatorTree::VerificationLevel::Basic));
427}
428
430 DT.print(OS);
431}
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:478
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: PassManager.h:110
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:690
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:649
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:803
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
const BasicBlock * getEnd() const
Definition: Dominators.h:114
const BasicBlock * getStart() const
Definition: Dominators.h:110
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:228
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:133
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:277
DominatorTree run(Function &F, FunctionAnalysisManager &)
Run the analysis pass over a function and produce a dominator tree.
Definition: Dominators.cpp:372
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:381
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Dominators.cpp:383
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:312
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: Dominators.cpp:429
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: Dominators.cpp:422
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:164
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:322
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:345
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:123
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: Dominators.cpp:114
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
const BasicBlock * getParent() const
Definition: Instruction.h:139
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
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: PassManager.h:172
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:178
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:330
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:465
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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: PassManager.h:89
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Dominators.cpp:391