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