1 //===- Dominators.h - Dominator Info Calculation ----------------*- C++ -*-===// 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 defines the DominatorTree class, which provides fast and efficient 11 // dominance queries. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_IR_DOMINATORS_H 16 #define LLVM_IR_DOMINATORS_H 17 18 #include "llvm/ADT/DenseMap.h" 19 #include "llvm/ADT/DepthFirstIterator.h" 20 #include "llvm/ADT/GraphTraits.h" 21 #include "llvm/ADT/SmallPtrSet.h" 22 #include "llvm/ADT/SmallVector.h" 23 #include "llvm/IR/BasicBlock.h" 24 #include "llvm/IR/CFG.h" 25 #include "llvm/IR/Function.h" 26 #include "llvm/Pass.h" 27 #include "llvm/Support/Compiler.h" 28 #include "llvm/Support/GenericDomTree.h" 29 #include "llvm/Support/raw_ostream.h" 30 #include <algorithm> 31 32 namespace llvm { 33 34 EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>); 35 EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>); 36 37 #define LLVM_COMMA , 38 EXTERN_TEMPLATE_INSTANTIATION(void Calculate<Function LLVM_COMMA BasicBlock *>( 39 DominatorTreeBase<GraphTraits<BasicBlock *>::NodeType> &DT LLVM_COMMA 40 Function &F)); 41 EXTERN_TEMPLATE_INSTANTIATION( 42 void Calculate<Function LLVM_COMMA Inverse<BasicBlock *> >( 43 DominatorTreeBase<GraphTraits<Inverse<BasicBlock *> >::NodeType> &DT 44 LLVM_COMMA Function &F)); 45 #undef LLVM_COMMA 46 47 typedef DomTreeNodeBase<BasicBlock> DomTreeNode; 48 49 class BasicBlockEdge { 50 const BasicBlock *Start; 51 const BasicBlock *End; 52 public: 53 BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) : 54 Start(Start_), End(End_) { } 55 const BasicBlock *getStart() const { 56 return Start; 57 } 58 const BasicBlock *getEnd() const { 59 return End; 60 } 61 bool isSingleEdge() const; 62 }; 63 64 /// \brief Concrete subclass of DominatorTreeBase that is used to compute a 65 /// normal dominator tree. 66 class DominatorTree : public DominatorTreeBase<BasicBlock> { 67 public: 68 typedef DominatorTreeBase<BasicBlock> Base; 69 70 DominatorTree() : DominatorTreeBase<BasicBlock>(false) {} 71 72 /// \brief Returns *false* if the other dominator tree matches this dominator 73 /// tree. 74 inline bool compare(const DominatorTree &Other) const { 75 const DomTreeNode *R = getRootNode(); 76 const DomTreeNode *OtherR = Other.getRootNode(); 77 78 if (!R || !OtherR || R->getBlock() != OtherR->getBlock()) 79 return true; 80 81 if (Base::compare(Other)) 82 return true; 83 84 return false; 85 } 86 87 // Ensure base-class overloads are visible. 88 using Base::dominates; 89 90 /// \brief Return true if Def dominates a use in User. 91 /// 92 /// This performs the special checks necessary if Def and User are in the same 93 /// basic block. Note that Def doesn't dominate a use in Def itself! 94 bool dominates(const Instruction *Def, const Use &U) const; 95 bool dominates(const Instruction *Def, const Instruction *User) const; 96 bool dominates(const Instruction *Def, const BasicBlock *BB) const; 97 bool dominates(const BasicBlockEdge &BBE, const Use &U) const; 98 bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const; 99 100 // Ensure base class overloads are visible. 101 using Base::isReachableFromEntry; 102 103 /// \brief Provide an overload for a Use. 104 bool isReachableFromEntry(const Use &U) const; 105 106 /// \brief Verify the correctness of the domtree by re-computing it. 107 /// 108 /// This should only be used for debugging as it aborts the program if the 109 /// verification fails. 110 void verifyDomTree() const; 111 }; 112 113 //===------------------------------------- 114 // DominatorTree GraphTraits specializations so the DominatorTree can be 115 // iterable by generic graph iterators. 116 117 template <> struct GraphTraits<DomTreeNode*> { 118 typedef DomTreeNode NodeType; 119 typedef NodeType::iterator ChildIteratorType; 120 121 static NodeType *getEntryNode(NodeType *N) { 122 return N; 123 } 124 static inline ChildIteratorType child_begin(NodeType *N) { 125 return N->begin(); 126 } 127 static inline ChildIteratorType child_end(NodeType *N) { 128 return N->end(); 129 } 130 131 typedef df_iterator<DomTreeNode*> nodes_iterator; 132 133 static nodes_iterator nodes_begin(DomTreeNode *N) { 134 return df_begin(getEntryNode(N)); 135 } 136 137 static nodes_iterator nodes_end(DomTreeNode *N) { 138 return df_end(getEntryNode(N)); 139 } 140 }; 141 142 template <> struct GraphTraits<DominatorTree*> 143 : public GraphTraits<DomTreeNode*> { 144 static NodeType *getEntryNode(DominatorTree *DT) { 145 return DT->getRootNode(); 146 } 147 148 static nodes_iterator nodes_begin(DominatorTree *N) { 149 return df_begin(getEntryNode(N)); 150 } 151 152 static nodes_iterator nodes_end(DominatorTree *N) { 153 return df_end(getEntryNode(N)); 154 } 155 }; 156 157 /// \brief Analysis pass which computes a \c DominatorTree. 158 class DominatorTreeWrapperPass : public FunctionPass { 159 DominatorTree DT; 160 161 public: 162 static char ID; 163 164 DominatorTreeWrapperPass() : FunctionPass(ID) { 165 initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry()); 166 } 167 168 DominatorTree &getDomTree() { return DT; } 169 const DominatorTree &getDomTree() const { return DT; } 170 171 bool runOnFunction(Function &F) override; 172 173 void verifyAnalysis() const override; 174 175 void getAnalysisUsage(AnalysisUsage &AU) const override { 176 AU.setPreservesAll(); 177 } 178 179 void releaseMemory() override { DT.releaseMemory(); } 180 181 void print(raw_ostream &OS, const Module *M = nullptr) const override; 182 }; 183 184 } // End llvm namespace 185 186 #endif 187
