LLVM  6.0.0svn
Dominators.cpp
Go to the documentation of this file.
1 //===- Dominators.cpp - Dominator Calculation -----------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements simple dominator construction algorithms for finding
11 // forward dominators. Postdominators are available in libanalysis, but are not
12 // included in libvmcore, because it's not needed. Forward dominators are
13 // needed to support the Verifier pass.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "llvm/IR/Dominators.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/IR/CFG.h"
21 #include "llvm/IR/Instructions.h"
22 #include "llvm/IR/PassManager.h"
24 #include "llvm/Support/Debug.h"
27 #include <algorithm>
28 using namespace llvm;
29 
30 // Always verify dominfo if expensive checking is enabled.
31 #ifdef EXPENSIVE_CHECKS
32 bool llvm::VerifyDomInfo = true;
33 #else
34 bool llvm::VerifyDomInfo = false;
35 #endif
36 static cl::opt<bool,true>
37 VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo),
38  cl::desc("Verify dominator info (time consuming)"));
39 
41  const TerminatorInst *TI = Start->getTerminator();
42  unsigned NumEdgesToEnd = 0;
43  for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) {
44  if (TI->getSuccessor(i) == End)
45  ++NumEdgesToEnd;
46  if (NumEdgesToEnd >= 2)
47  return false;
48  }
49  assert(NumEdgesToEnd == 1);
50  return true;
51 }
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 
64 template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase
65 template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase
66 
68 
69 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
71 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
73 
74 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>(
76 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>(
78 
79 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
81 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
83 
84 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
86 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
88 
89 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
90  const DomTreeBuilder::BBDomTree &DT);
91 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
93 
96  // Check whether the analysis, all analyses on functions, or the function's
97  // CFG have been preserved.
98  auto PAC = PA.getChecker<DominatorTreeAnalysis>();
99  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
100  PAC.preservedSet<CFGAnalyses>());
101 }
102 
103 // dominates - Return true if Def dominates a use in User. This performs
104 // the special checks necessary if Def and User are in the same basic block.
105 // Note that Def doesn't dominate a use in Def itself!
107  const Instruction *User) const {
108  const BasicBlock *UseBB = User->getParent();
109  const BasicBlock *DefBB = Def->getParent();
110 
111  // Any unreachable use is dominated, even if Def == User.
112  if (!isReachableFromEntry(UseBB))
113  return true;
114 
115  // Unreachable definitions don't dominate anything.
116  if (!isReachableFromEntry(DefBB))
117  return false;
118 
119  // An instruction doesn't dominate a use in itself.
120  if (Def == User)
121  return false;
122 
123  // The value defined by an invoke dominates an instruction only if it
124  // dominates every instruction in UseBB.
125  // A PHI is dominated only if the instruction dominates every possible use in
126  // the UseBB.
127  if (isa<InvokeInst>(Def) || isa<PHINode>(User))
128  return dominates(Def, UseBB);
129 
130  if (DefBB != UseBB)
131  return dominates(DefBB, UseBB);
132 
133  // Loop through the basic block until we find Def or User.
135  for (; &*I != Def && &*I != User; ++I)
136  /*empty*/;
137 
138  return &*I == Def;
139 }
140 
141 // true if Def would dominate a use in any instruction in UseBB.
142 // note that dominates(Def, Def->getParent()) is false.
144  const BasicBlock *UseBB) const {
145  const BasicBlock *DefBB = Def->getParent();
146 
147  // Any unreachable use is dominated, even if DefBB == UseBB.
148  if (!isReachableFromEntry(UseBB))
149  return true;
150 
151  // Unreachable definitions don't dominate anything.
152  if (!isReachableFromEntry(DefBB))
153  return false;
154 
155  if (DefBB == UseBB)
156  return false;
157 
158  // Invoke results are only usable in the normal destination, not in the
159  // exceptional destination.
160  if (const auto *II = dyn_cast<InvokeInst>(Def)) {
161  BasicBlock *NormalDest = II->getNormalDest();
162  BasicBlockEdge E(DefBB, NormalDest);
163  return dominates(E, UseBB);
164  }
165 
166  return dominates(DefBB, UseBB);
167 }
168 
170  const BasicBlock *UseBB) const {
171  // If the BB the edge ends in doesn't dominate the use BB, then the
172  // edge also doesn't.
173  const BasicBlock *Start = BBE.getStart();
174  const BasicBlock *End = BBE.getEnd();
175  if (!dominates(End, UseBB))
176  return false;
177 
178  // Simple case: if the end BB has a single predecessor, the fact that it
179  // dominates the use block implies that the edge also does.
180  if (End->getSinglePredecessor())
181  return true;
182 
183  // The normal edge from the invoke is critical. Conceptually, what we would
184  // like to do is split it and check if the new block dominates the use.
185  // With X being the new block, the graph would look like:
186  //
187  // DefBB
188  // /\ . .
189  // / \ . .
190  // / \ . .
191  // / \ | |
192  // A X B C
193  // | \ | /
194  // . \|/
195  // . NormalDest
196  // .
197  //
198  // Given the definition of dominance, NormalDest is dominated by X iff X
199  // dominates all of NormalDest's predecessors (X, B, C in the example). X
200  // trivially dominates itself, so we only have to find if it dominates the
201  // other predecessors. Since the only way out of X is via NormalDest, X can
202  // only properly dominate a node if NormalDest dominates that node too.
203  int IsDuplicateEdge = 0;
204  for (const_pred_iterator PI = pred_begin(End), E = pred_end(End);
205  PI != E; ++PI) {
206  const BasicBlock *BB = *PI;
207  if (BB == Start) {
208  // If there are multiple edges between Start and End, by definition they
209  // can't dominate anything.
210  if (IsDuplicateEdge++)
211  return false;
212  continue;
213  }
214 
215  if (!dominates(End, BB))
216  return false;
217  }
218  return true;
219 }
220 
221 bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
222  Instruction *UserInst = cast<Instruction>(U.getUser());
223  // A PHI in the end of the edge is dominated by it.
224  PHINode *PN = dyn_cast<PHINode>(UserInst);
225  if (PN && PN->getParent() == BBE.getEnd() &&
226  PN->getIncomingBlock(U) == BBE.getStart())
227  return true;
228 
229  // Otherwise use the edge-dominates-block query, which
230  // handles the crazy critical edge cases properly.
231  const BasicBlock *UseBB;
232  if (PN)
233  UseBB = PN->getIncomingBlock(U);
234  else
235  UseBB = UserInst->getParent();
236  return dominates(BBE, UseBB);
237 }
238 
239 bool DominatorTree::dominates(const Instruction *Def, const Use &U) const {
240  Instruction *UserInst = cast<Instruction>(U.getUser());
241  const BasicBlock *DefBB = Def->getParent();
242 
243  // Determine the block in which the use happens. PHI nodes use
244  // their operands on edges; simulate this by thinking of the use
245  // happening at the end of the predecessor block.
246  const BasicBlock *UseBB;
247  if (PHINode *PN = dyn_cast<PHINode>(UserInst))
248  UseBB = PN->getIncomingBlock(U);
249  else
250  UseBB = UserInst->getParent();
251 
252  // Any unreachable use is dominated, even if Def == User.
253  if (!isReachableFromEntry(UseBB))
254  return true;
255 
256  // Unreachable definitions don't dominate anything.
257  if (!isReachableFromEntry(DefBB))
258  return false;
259 
260  // Invoke instructions define their return values on the edges to their normal
261  // successors, so we have to handle them specially.
262  // Among other things, this means they don't dominate anything in
263  // their own block, except possibly a phi, so we don't need to
264  // walk the block in any case.
265  if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) {
266  BasicBlock *NormalDest = II->getNormalDest();
267  BasicBlockEdge E(DefBB, NormalDest);
268  return dominates(E, U);
269  }
270 
271  // If the def and use are in different blocks, do a simple CFG dominator
272  // tree query.
273  if (DefBB != UseBB)
274  return dominates(DefBB, UseBB);
275 
276  // Ok, def and use are in the same block. If the def is an invoke, it
277  // doesn't dominate anything in the block. If it's a PHI, it dominates
278  // everything in the block.
279  if (isa<PHINode>(UserInst))
280  return true;
281 
282  // Otherwise, just loop through the basic block until we find Def or User.
283  BasicBlock::const_iterator I = DefBB->begin();
284  for (; &*I != Def && &*I != UserInst; ++I)
285  /*empty*/;
286 
287  return &*I != UserInst;
288 }
289 
292 
293  // ConstantExprs aren't really reachable from the entry block, but they
294  // don't need to be treated like unreachable code either.
295  if (!I) return true;
296 
297  // PHI nodes use their operands on their incoming edges.
298  if (PHINode *PN = dyn_cast<PHINode>(I))
299  return isReachableFromEntry(PN->getIncomingBlock(U));
300 
301  // Everything else uses their operands in their own block.
302  return isReachableFromEntry(I->getParent());
303 }
304 
306  // Perform the expensive checks only when VerifyDomInfo is set.
307  if (VerifyDomInfo && !verify()) {
308  errs() << "\n~~~~~~~~~~~\n\t\tDomTree verification failed!\n~~~~~~~~~~~\n";
309  print(errs());
310  abort();
311  }
312 
313  Function &F = *getRoot()->getParent();
314 
315  DominatorTree OtherDT;
316  OtherDT.recalculate(F);
317  if (compare(OtherDT)) {
318  errs() << "DominatorTree is not up to date!\nComputed:\n";
319  print(errs());
320  errs() << "\nActual:\n";
321  OtherDT.print(errs());
322  errs() << "\nCFG:\n";
323  F.print(errs());
324  errs().flush();
325  abort();
326  }
327 }
328 
329 //===----------------------------------------------------------------------===//
330 // DominatorTreeAnalysis and related pass implementations
331 //===----------------------------------------------------------------------===//
332 //
333 // This implements the DominatorTreeAnalysis which is used with the new pass
334 // manager. It also implements some methods from utility passes.
335 //
336 //===----------------------------------------------------------------------===//
337 
340  DominatorTree DT;
341  DT.recalculate(F);
342  return DT;
343 }
344 
345 AnalysisKey DominatorTreeAnalysis::Key;
346 
348 
351  OS << "DominatorTree for function: " << F.getName() << "\n";
353 
354  return PreservedAnalyses::all();
355 }
356 
359  AM.getResult<DominatorTreeAnalysis>(F).verifyDomTree();
360 
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 
375  "Dominator Tree Construction", true, true)
376 
378  DT.recalculate(F);
379  return false;
380 }
381 
383  if (VerifyDomInfo)
384  DT.verifyDomTree();
385 }
386 
388  DT.print(OS);
389 }
390 
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
BasicBlock * getSuccessor(unsigned idx) const
Return the specified successor.
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:238
F(f)
const BasicBlock * getEnd() const
Definition: Dominators.h:90
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:290
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
bool isSingleEdge() const
Check if this is the only edge between Start and End.
Definition: Dominators.cpp:40
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:304
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: Dominators.cpp:382
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Definition: Use.cpp:41
void print(raw_ostream &OS, AssemblyAnnotationWriter *AAW=nullptr, bool ShouldPreserveUseListOrder=false, bool IsForDebug=false) const
Print the function to an output stream with an optional AssemblyAnnotationWriter. ...
Definition: AsmWriter.cpp:3400
DominatorTreePrinterPass(raw_ostream &OS)
Definition: Dominators.cpp:347
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
static bool runOnFunction(Function &F, bool PostInlining)
void verifyDomTree() const
Verify the correctness of the domtree by re-computing it.
Definition: Dominators.cpp:305
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:54
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:217
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
DominatorTree run(Function &F, FunctionAnalysisManager &)
Run the analysis pass over a function and produce a dominator tree.
Definition: Dominators.cpp:338
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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:113
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
bool VerifyDomInfo
Enables verification of dominator trees.
Definition: Dominators.cpp:34
INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree", "Dominator Tree Construction", true, true) bool DominatorTreeWrapperPass
Definition: Dominators.cpp:374
ArrayRef< Update< BasicBlock * > > BBUpdates
Definition: Dominators.h:46
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
bool verify(const TargetRegisterInfo &TRI) const
Check that information hold by this instance make sense for the given TRI.
void print(raw_ostream &O) const
print - Convert to human readable form
static cl::opt< bool, true > VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), cl::desc("Verify dominator info (time consuming)"))
Iterator for intrusive lists based on ilist_node.
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:239
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: Dominators.cpp:387
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: Dominators.cpp:94
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:220
#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:323
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:559
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Compare two scaled numbers.
Definition: ScaledNumber.h:252
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
unsigned getNumSuccessors() const
Return the number of successors that this terminator has.
const BasicBlock * getStart() const
Definition: Dominators.h:86
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Dominators.cpp:349
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
Invoke instruction.
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
const TerminatorInst * 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:120
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:422
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Dominators.cpp:357
const BasicBlock * getParent() const
Definition: Instruction.h:66