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