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 // FIXME: Replace this brittle forward declaration with the include of the new 35 // PassManager.h when doing so doesn't break the PassManagerBuilder. 36 template <typename IRUnitT> class AnalysisManager; 37 class PreservedAnalyses; 38 39 extern template class DomTreeNodeBase<BasicBlock>; 40 extern template class DominatorTreeBase<BasicBlock>; 41 42 extern template void Calculate<Function, BasicBlock *>( 43 DominatorTreeBase<GraphTraits<BasicBlock *>::NodeType> &DT, Function &F); 44 extern template void Calculate<Function, Inverse<BasicBlock *>>( 45 DominatorTreeBase<GraphTraits<Inverse<BasicBlock *>>::NodeType> &DT, 46 Function &F); 47 48 typedef DomTreeNodeBase<BasicBlock> DomTreeNode; 49 50 class BasicBlockEdge { 51 const BasicBlock *Start; 52 const BasicBlock *End; 53 public: BasicBlockEdge(const BasicBlock * Start_,const BasicBlock * End_)54 BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) : 55 Start(Start_), End(End_) { } getStart()56 const BasicBlock *getStart() const { 57 return Start; 58 } getEnd()59 const BasicBlock *getEnd() const { 60 return End; 61 } 62 bool isSingleEdge() const; 63 }; 64 65 /// \brief Concrete subclass of DominatorTreeBase that is used to compute a 66 /// normal dominator tree. 67 /// 68 /// Definition: A block is said to be forward statically reachable if there is 69 /// a path from the entry of the function to the block. A statically reachable 70 /// block may become statically unreachable during optimization. 71 /// 72 /// A forward unreachable block may appear in the dominator tree, or it may 73 /// not. If it does, dominance queries will return results as if all reachable 74 /// blocks dominate it. When asking for a Node corresponding to a potentially 75 /// unreachable block, calling code must handle the case where the block was 76 /// unreachable and the result of getNode() is nullptr. 77 /// 78 /// Generally, a block known to be unreachable when the dominator tree is 79 /// constructed will not be in the tree. One which becomes unreachable after 80 /// the dominator tree is initially constructed may still exist in the tree, 81 /// even if the tree is properly updated. Calling code should not rely on the 82 /// preceding statements; this is stated only to assist human understanding. 83 class DominatorTree : public DominatorTreeBase<BasicBlock> { 84 public: 85 typedef DominatorTreeBase<BasicBlock> Base; 86 DominatorTree()87 DominatorTree() : DominatorTreeBase<BasicBlock>(false) {} DominatorTree(Function & F)88 explicit DominatorTree(Function &F) : DominatorTreeBase<BasicBlock>(false) { 89 recalculate(F); 90 } 91 DominatorTree(DominatorTree && Arg)92 DominatorTree(DominatorTree &&Arg) 93 : Base(std::move(static_cast<Base &>(Arg))) {} 94 DominatorTree &operator=(DominatorTree &&RHS) { 95 Base::operator=(std::move(static_cast<Base &>(RHS))); 96 return *this; 97 } 98 99 /// \brief Returns *false* if the other dominator tree matches this dominator 100 /// tree. compare(const DominatorTree & Other)101 inline bool compare(const DominatorTree &Other) const { 102 const DomTreeNode *R = getRootNode(); 103 const DomTreeNode *OtherR = Other.getRootNode(); 104 105 if (!R || !OtherR || R->getBlock() != OtherR->getBlock()) 106 return true; 107 108 if (Base::compare(Other)) 109 return true; 110 111 return false; 112 } 113 114 // Ensure base-class overloads are visible. 115 using Base::dominates; 116 117 /// \brief Return true if Def dominates a use in User. 118 /// 119 /// This performs the special checks necessary if Def and User are in the same 120 /// basic block. Note that Def doesn't dominate a use in Def itself! 121 bool dominates(const Instruction *Def, const Use &U) const; 122 bool dominates(const Instruction *Def, const Instruction *User) const; 123 bool dominates(const Instruction *Def, const BasicBlock *BB) const; 124 bool dominates(const BasicBlockEdge &BBE, const Use &U) const; 125 bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const; 126 127 // Ensure base class overloads are visible. 128 using Base::isReachableFromEntry; 129 130 /// \brief Provide an overload for a Use. 131 bool isReachableFromEntry(const Use &U) const; 132 133 /// \brief Verify the correctness of the domtree by re-computing it. 134 /// 135 /// This should only be used for debugging as it aborts the program if the 136 /// verification fails. 137 void verifyDomTree() const; 138 }; 139 140 //===------------------------------------- 141 // DominatorTree GraphTraits specializations so the DominatorTree can be 142 // iterable by generic graph iterators. 143 144 template <class Node, class ChildIterator> struct DomTreeGraphTraitsBase { 145 typedef Node NodeType; 146 typedef ChildIterator ChildIteratorType; 147 typedef df_iterator<Node *, SmallPtrSet<NodeType *, 8>> nodes_iterator; 148 getEntryNodeDomTreeGraphTraitsBase149 static NodeType *getEntryNode(NodeType *N) { return N; } child_beginDomTreeGraphTraitsBase150 static inline ChildIteratorType child_begin(NodeType *N) { 151 return N->begin(); 152 } child_endDomTreeGraphTraitsBase153 static inline ChildIteratorType child_end(NodeType *N) { return N->end(); } 154 nodes_beginDomTreeGraphTraitsBase155 static nodes_iterator nodes_begin(NodeType *N) { 156 return df_begin(getEntryNode(N)); 157 } 158 nodes_endDomTreeGraphTraitsBase159 static nodes_iterator nodes_end(NodeType *N) { 160 return df_end(getEntryNode(N)); 161 } 162 }; 163 164 template <> 165 struct GraphTraits<DomTreeNode *> 166 : public DomTreeGraphTraitsBase<DomTreeNode, DomTreeNode::iterator> {}; 167 168 template <> 169 struct GraphTraits<const DomTreeNode *> 170 : public DomTreeGraphTraitsBase<const DomTreeNode, 171 DomTreeNode::const_iterator> {}; 172 173 template <> struct GraphTraits<DominatorTree*> 174 : public GraphTraits<DomTreeNode*> { 175 static NodeType *getEntryNode(DominatorTree *DT) { 176 return DT->getRootNode(); 177 } 178 179 static nodes_iterator nodes_begin(DominatorTree *N) { 180 return df_begin(getEntryNode(N)); 181 } 182 183 static nodes_iterator nodes_end(DominatorTree *N) { 184 return df_end(getEntryNode(N)); 185 } 186 }; 187 188 /// \brief Analysis pass which computes a \c DominatorTree. 189 class DominatorTreeAnalysis { 190 public: 191 /// \brief Provide the result typedef for this analysis pass. 192 typedef DominatorTree Result; 193 194 /// \brief Opaque, unique identifier for this analysis pass. 195 static void *ID() { return (void *)&PassID; } 196 197 /// \brief Run the analysis pass over a function and produce a dominator tree. 198 DominatorTree run(Function &F); 199 200 /// \brief Provide access to a name for this pass for debugging purposes. 201 static StringRef name() { return "DominatorTreeAnalysis"; } 202 203 private: 204 static char PassID; 205 }; 206 207 /// \brief Printer pass for the \c DominatorTree. 208 class DominatorTreePrinterPass { 209 raw_ostream &OS; 210 211 public: 212 explicit DominatorTreePrinterPass(raw_ostream &OS); 213 PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM); 214 215 static StringRef name() { return "DominatorTreePrinterPass"; } 216 }; 217 218 /// \brief Verifier pass for the \c DominatorTree. 219 struct DominatorTreeVerifierPass { 220 PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM); 221 222 static StringRef name() { return "DominatorTreeVerifierPass"; } 223 }; 224 225 /// \brief Legacy analysis pass which computes a \c DominatorTree. 226 class DominatorTreeWrapperPass : public FunctionPass { 227 DominatorTree DT; 228 229 public: 230 static char ID; 231 232 DominatorTreeWrapperPass() : FunctionPass(ID) { 233 initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry()); 234 } 235 236 DominatorTree &getDomTree() { return DT; } 237 const DominatorTree &getDomTree() const { return DT; } 238 239 bool runOnFunction(Function &F) override; 240 241 void verifyAnalysis() const override; 242 243 void getAnalysisUsage(AnalysisUsage &AU) const override { 244 AU.setPreservesAll(); 245 } 246 247 void releaseMemory() override { DT.releaseMemory(); } 248 249 void print(raw_ostream &OS, const Module *M = nullptr) const override; 250 }; 251 252 } // End llvm namespace 253 254 #endif 255