LLVM  10.0.0svn
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"
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/Config/llvm-config.h"
20 #include "llvm/IR/CFG.h"
21 #include "llvm/IR/Constants.h"
22 #include "llvm/IR/Instructions.h"
23 #include "llvm/IR/PassManager.h"
25 #include "llvm/Support/Debug.h"
28 #include <algorithm>
29 using namespace llvm;
30 
31 bool llvm::VerifyDomInfo = false;
34  cl::desc("Verify dominator info (time consuming)"));
35 
36 #ifdef EXPENSIVE_CHECKS
37 static constexpr bool ExpensiveChecksEnabled = true;
38 #else
39 static constexpr bool ExpensiveChecksEnabled = false;
40 #endif
41 
43  const Instruction *TI = Start->getTerminator();
44  unsigned NumEdgesToEnd = 0;
45  for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) {
46  if (TI->getSuccessor(i) == End)
47  ++NumEdgesToEnd;
48  if (NumEdgesToEnd >= 2)
49  return false;
50  }
51  assert(NumEdgesToEnd == 1);
52  return true;
53 }
54 
55 //===----------------------------------------------------------------------===//
56 // DominatorTree Implementation
57 //===----------------------------------------------------------------------===//
58 //
59 // Provide public access to DominatorTree information. Implementation details
60 // can be found in Dominators.h, GenericDomTree.h, and
61 // GenericDomTreeConstruction.h.
62 //
63 //===----------------------------------------------------------------------===//
64 
66 template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase
67 template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase
68 
69 template class llvm::cfg::Update<BasicBlock *>;
70 
71 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
73 template void
74 llvm::DomTreeBuilder::CalculateWithUpdates<DomTreeBuilder::BBDomTree>(
76 
77 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
79 // No CalculateWithUpdates<PostDomTree> instantiation, unless a usecase arises.
80 
81 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>(
83 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>(
85 
86 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
88 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
90 
91 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
93 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
95 
96 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
97  const DomTreeBuilder::BBDomTree &DT,
99 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
102 
104  FunctionAnalysisManager::Invalidator &) {
105  // Check whether the analysis, all analyses on functions, or the function's
106  // CFG have been preserved.
107  auto PAC = PA.getChecker<DominatorTreeAnalysis>();
108  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
109  PAC.preservedSet<CFGAnalyses>());
110 }
111 
112 // dominates - Return true if Def dominates a use in User. This performs
113 // the special checks necessary if Def and User are in the same basic block.
114 // Note that Def doesn't dominate a use in Def itself!
116  const Instruction *User) const {
117  const BasicBlock *UseBB = User->getParent();
118  const BasicBlock *DefBB = Def->getParent();
119 
120  // Any unreachable use is dominated, even if Def == User.
121  if (!isReachableFromEntry(UseBB))
122  return true;
123 
124  // Unreachable definitions don't dominate anything.
125  if (!isReachableFromEntry(DefBB))
126  return false;
127 
128  // An instruction doesn't dominate a use in itself.
129  if (Def == User)
130  return false;
131 
132  // The value defined by an invoke dominates an instruction only if it
133  // dominates every instruction in UseBB.
134  // A PHI is dominated only if the instruction dominates every possible use in
135  // the UseBB.
136  if (isa<InvokeInst>(Def) || isa<PHINode>(User))
137  return dominates(Def, UseBB);
138 
139  if (DefBB != UseBB)
140  return dominates(DefBB, UseBB);
141 
142  // Loop through the basic block until we find Def or User.
144  for (; &*I != Def && &*I != User; ++I)
145  /*empty*/;
146 
147  return &*I == Def;
148 }
149 
150 // true if Def would dominate a use in any instruction in UseBB.
151 // note that dominates(Def, Def->getParent()) is false.
153  const BasicBlock *UseBB) const {
154  const BasicBlock *DefBB = Def->getParent();
155 
156  // Any unreachable use is dominated, even if DefBB == UseBB.
157  if (!isReachableFromEntry(UseBB))
158  return true;
159 
160  // Unreachable definitions don't dominate anything.
161  if (!isReachableFromEntry(DefBB))
162  return false;
163 
164  if (DefBB == UseBB)
165  return false;
166 
167  // Invoke results are only usable in the normal destination, not in the
168  // exceptional destination.
169  if (const auto *II = dyn_cast<InvokeInst>(Def)) {
170  BasicBlock *NormalDest = II->getNormalDest();
171  BasicBlockEdge E(DefBB, NormalDest);
172  return dominates(E, UseBB);
173  }
174 
175  return dominates(DefBB, UseBB);
176 }
177 
179  const BasicBlock *UseBB) const {
180  // If the BB the edge ends in doesn't dominate the use BB, then the
181  // edge also doesn't.
182  const BasicBlock *Start = BBE.getStart();
183  const BasicBlock *End = BBE.getEnd();
184  if (!dominates(End, UseBB))
185  return false;
186 
187  // Simple case: if the end BB has a single predecessor, the fact that it
188  // dominates the use block implies that the edge also does.
189  if (End->getSinglePredecessor())
190  return true;
191 
192  // The normal edge from the invoke is critical. Conceptually, what we would
193  // like to do is split it and check if the new block dominates the use.
194  // With X being the new block, the graph would look like:
195  //
196  // DefBB
197  // /\ . .
198  // / \ . .
199  // / \ . .
200  // / \ | |
201  // A X B C
202  // | \ | /
203  // . \|/
204  // . NormalDest
205  // .
206  //
207  // Given the definition of dominance, NormalDest is dominated by X iff X
208  // dominates all of NormalDest's predecessors (X, B, C in the example). X
209  // trivially dominates itself, so we only have to find if it dominates the
210  // other predecessors. Since the only way out of X is via NormalDest, X can
211  // only properly dominate a node if NormalDest dominates that node too.
212  int IsDuplicateEdge = 0;
213  for (const_pred_iterator PI = pred_begin(End), E = pred_end(End);
214  PI != E; ++PI) {
215  const BasicBlock *BB = *PI;
216  if (BB == Start) {
217  // If there are multiple edges between Start and End, by definition they
218  // can't dominate anything.
219  if (IsDuplicateEdge++)
220  return false;
221  continue;
222  }
223 
224  if (!dominates(End, BB))
225  return false;
226  }
227  return true;
228 }
229 
230 bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
231  Instruction *UserInst = cast<Instruction>(U.getUser());
232  // A PHI in the end of the edge is dominated by it.
233  PHINode *PN = dyn_cast<PHINode>(UserInst);
234  if (PN && PN->getParent() == BBE.getEnd() &&
235  PN->getIncomingBlock(U) == BBE.getStart())
236  return true;
237 
238  // Otherwise use the edge-dominates-block query, which
239  // handles the crazy critical edge cases properly.
240  const BasicBlock *UseBB;
241  if (PN)
242  UseBB = PN->getIncomingBlock(U);
243  else
244  UseBB = UserInst->getParent();
245  return dominates(BBE, UseBB);
246 }
247 
248 bool DominatorTree::dominates(const Instruction *Def, const Use &U) const {
249  Instruction *UserInst = cast<Instruction>(U.getUser());
250  const BasicBlock *DefBB = Def->getParent();
251 
252  // Determine the block in which the use happens. PHI nodes use
253  // their operands on edges; simulate this by thinking of the use
254  // happening at the end of the predecessor block.
255  const BasicBlock *UseBB;
256  if (PHINode *PN = dyn_cast<PHINode>(UserInst))
257  UseBB = PN->getIncomingBlock(U);
258  else
259  UseBB = UserInst->getParent();
260 
261  // Any unreachable use is dominated, even if Def == User.
262  if (!isReachableFromEntry(UseBB))
263  return true;
264 
265  // Unreachable definitions don't dominate anything.
266  if (!isReachableFromEntry(DefBB))
267  return false;
268 
269  // Invoke instructions define their return values on the edges to their normal
270  // successors, so we have to handle them specially.
271  // Among other things, this means they don't dominate anything in
272  // their own block, except possibly a phi, so we don't need to
273  // walk the block in any case.
274  if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) {
275  BasicBlock *NormalDest = II->getNormalDest();
276  BasicBlockEdge E(DefBB, NormalDest);
277  return dominates(E, U);
278  }
279 
280  // If the def and use are in different blocks, do a simple CFG dominator
281  // tree query.
282  if (DefBB != UseBB)
283  return dominates(DefBB, UseBB);
284 
285  // Ok, def and use are in the same block. If the def is an invoke, it
286  // doesn't dominate anything in the block. If it's a PHI, it dominates
287  // everything in the block.
288  if (isa<PHINode>(UserInst))
289  return true;
290 
291  // Otherwise, just loop through the basic block until we find Def or User.
292  BasicBlock::const_iterator I = DefBB->begin();
293  for (; &*I != Def && &*I != UserInst; ++I)
294  /*empty*/;
295 
296  return &*I != UserInst;
297 }
298 
301 
302  // ConstantExprs aren't really reachable from the entry block, but they
303  // don't need to be treated like unreachable code either.
304  if (!I) return true;
305 
306  // PHI nodes use their operands on their incoming edges.
307  if (PHINode *PN = dyn_cast<PHINode>(I))
308  return isReachableFromEntry(PN->getIncomingBlock(U));
309 
310  // Everything else uses their operands in their own block.
311  return isReachableFromEntry(I->getParent());
312 }
313 
314 //===----------------------------------------------------------------------===//
315 // DominatorTreeAnalysis and related pass implementations
316 //===----------------------------------------------------------------------===//
317 //
318 // This implements the DominatorTreeAnalysis which is used with the new pass
319 // manager. It also implements some methods from utility passes.
320 //
321 //===----------------------------------------------------------------------===//
322 
325  DominatorTree DT;
326  DT.recalculate(F);
327  return DT;
328 }
329 
330 AnalysisKey DominatorTreeAnalysis::Key;
331 
333 
336  OS << "DominatorTree for function: " << F.getName() << "\n";
338 
339  return PreservedAnalyses::all();
340 }
341 
344  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
345  assert(DT.verify());
346  (void)DT;
347  return PreservedAnalyses::all();
348 }
349 
350 //===----------------------------------------------------------------------===//
351 // DominatorTreeWrapperPass Implementation
352 //===----------------------------------------------------------------------===//
353 //
354 // The implementation details of the wrapper pass that holds a DominatorTree
355 // suitable for use with the legacy pass manager.
356 //
357 //===----------------------------------------------------------------------===//
358 
361  "Dominator Tree Construction", true, true)
362 
364  DT.recalculate(F);
365  return false;
366 }
367 
369  if (VerifyDomInfo)
371  else if (ExpensiveChecksEnabled)
373 }
374 
376  DT.print(OS);
377 }
378 
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
static constexpr bool ExpensiveChecksEnabled
Definition: Dominators.cpp:39
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
F(f)
const BasicBlock * getEnd() const
Definition: Dominators.h:94
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.cpp:137
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:299
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
bool isSingleEdge() const
Check if this is the only edge between Start and End.
Definition: Dominators.cpp:42
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:311
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: Dominators.cpp:368
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Definition: Use.cpp:40
DominatorTreePrinterPass(raw_ostream &OS)
Definition: Dominators.cpp:332
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
static bool runOnFunction(Function &F, bool PostInlining)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:233
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
DominatorTree run(Function &F, FunctionAnalysisManager &)
Run the analysis pass over a function and produce a dominator tree.
Definition: Dominators.cpp:323
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:112
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:115
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
bool VerifyDomInfo
Enables verification of dominator trees.
Definition: Dominators.cpp:31
ArrayRef< llvm::cfg::Update< BasicBlock * > > BBUpdates
Definition: Dominators.h:45
INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree", "Dominator Tree Construction", true, true) bool DominatorTreeWrapperPass
Definition: Dominators.cpp:360
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
Iterator for intrusive lists based on ilist_node.
BlockVerifier::State From
Generic dominator tree construction - This file provides routines to construct immediate dominator in...
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:248
static cl::opt< bool, true > VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), cl::Hidden, cl::desc("Verify dominator info (time consuming)"))
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: Dominators.cpp:375
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: Dominators.cpp:103
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This templated class represents "all analyses that operate over <a particular IR unit>" (e...
Definition: PassManager.h:91
const BasicBlock * getStart() const
Definition: Dominators.h:90
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Dominators.cpp:334
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
Invoke instruction.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
This header defines various interfaces for pass management in LLVM.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:448
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Dominators.cpp:342
const BasicBlock * getParent() const
Definition: Instruction.h:66