• Home
  • History
  • Annotate
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/Analysis/Dominators.h"
18  #include "llvm/Support/CFG.h"
19  #include "llvm/Support/Compiler.h"
20  #include "llvm/Support/Debug.h"
21  #include "llvm/ADT/DepthFirstIterator.h"
22  #include "llvm/ADT/SmallPtrSet.h"
23  #include "llvm/ADT/SmallVector.h"
24  #include "llvm/Analysis/DominatorInternals.h"
25  #include "llvm/Assembly/Writer.h"
26  #include "llvm/Instructions.h"
27  #include "llvm/Support/raw_ostream.h"
28  #include "llvm/Support/CommandLine.h"
29  #include <algorithm>
30  using namespace llvm;
31  
32  // Always verify dominfo if expensive checking is enabled.
33  #ifdef XDEBUG
34  static bool VerifyDomInfo = true;
35  #else
36  static bool VerifyDomInfo = false;
37  #endif
38  static cl::opt<bool,true>
39  VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo),
40                 cl::desc("Verify dominator info (time consuming)"));
41  
42  //===----------------------------------------------------------------------===//
43  //  DominatorTree Implementation
44  //===----------------------------------------------------------------------===//
45  //
46  // Provide public access to DominatorTree information.  Implementation details
47  // can be found in DominatorInternals.h.
48  //
49  //===----------------------------------------------------------------------===//
50  
51  TEMPLATE_INSTANTIATION(class llvm::DomTreeNodeBase<BasicBlock>);
52  TEMPLATE_INSTANTIATION(class llvm::DominatorTreeBase<BasicBlock>);
53  
54  char DominatorTree::ID = 0;
55  INITIALIZE_PASS(DominatorTree, "domtree",
56                  "Dominator Tree Construction", true, true)
57  
runOnFunction(Function & F)58  bool DominatorTree::runOnFunction(Function &F) {
59    DT->recalculate(F);
60    return false;
61  }
62  
verifyAnalysis() const63  void DominatorTree::verifyAnalysis() const {
64    if (!VerifyDomInfo) return;
65  
66    Function &F = *getRoot()->getParent();
67  
68    DominatorTree OtherDT;
69    OtherDT.getBase().recalculate(F);
70    if (compare(OtherDT)) {
71      errs() << "DominatorTree is not up to date!\nComputed:\n";
72      print(errs());
73      errs() << "\nActual:\n";
74      OtherDT.print(errs());
75      abort();
76    }
77  }
78  
print(raw_ostream & OS,const Module *) const79  void DominatorTree::print(raw_ostream &OS, const Module *) const {
80    DT->print(OS);
81  }
82  
83  // dominates - Return true if A dominates a use in B. This performs the
84  // special checks necessary if A and B are in the same basic block.
dominates(const Instruction * A,const Instruction * B) const85  bool DominatorTree::dominates(const Instruction *A, const Instruction *B) const{
86    const BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
87  
88    // If A is an invoke instruction, its value is only available in this normal
89    // successor block.
90    if (const InvokeInst *II = dyn_cast<InvokeInst>(A))
91      BBA = II->getNormalDest();
92  
93    if (BBA != BBB) return dominates(BBA, BBB);
94  
95    // It is not possible to determine dominance between two PHI nodes
96    // based on their ordering.
97    if (isa<PHINode>(A) && isa<PHINode>(B))
98      return false;
99  
100    // Loop through the basic block until we find A or B.
101    BasicBlock::const_iterator I = BBA->begin();
102    for (; &*I != A && &*I != B; ++I)
103      /*empty*/;
104  
105    return &*I == A;
106  }
107