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 32namespace 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. 36template <typename IRUnitT> class AnalysisManager; 37class PreservedAnalyses; 38 39EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>); 40EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>); 41 42#define LLVM_COMMA , 43EXTERN_TEMPLATE_INSTANTIATION(void Calculate<Function LLVM_COMMA BasicBlock *>( 44 DominatorTreeBase<GraphTraits<BasicBlock *>::NodeType> &DT LLVM_COMMA 45 Function &F)); 46EXTERN_TEMPLATE_INSTANTIATION( 47 void Calculate<Function LLVM_COMMA Inverse<BasicBlock *> >( 48 DominatorTreeBase<GraphTraits<Inverse<BasicBlock *> >::NodeType> &DT 49 LLVM_COMMA Function &F)); 50#undef LLVM_COMMA 51 52typedef DomTreeNodeBase<BasicBlock> DomTreeNode; 53 54class BasicBlockEdge { 55 const BasicBlock *Start; 56 const BasicBlock *End; 57public: 58 BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) : 59 Start(Start_), End(End_) { } 60 const BasicBlock *getStart() const { 61 return Start; 62 } 63 const BasicBlock *getEnd() const { 64 return End; 65 } 66 bool isSingleEdge() const; 67}; 68 69/// \brief Concrete subclass of DominatorTreeBase that is used to compute a 70/// normal dominator tree. 71class DominatorTree : public DominatorTreeBase<BasicBlock> { 72public: 73 typedef DominatorTreeBase<BasicBlock> Base; 74 75 DominatorTree() : DominatorTreeBase<BasicBlock>(false) {} 76 77 DominatorTree(DominatorTree &&Arg) 78 : Base(std::move(static_cast<Base &>(Arg))) {} 79 DominatorTree &operator=(DominatorTree &&RHS) { 80 Base::operator=(std::move(static_cast<Base &>(RHS))); 81 return *this; 82 } 83 84 /// \brief Returns *false* if the other dominator tree matches this dominator 85 /// tree. 86 inline bool compare(const DominatorTree &Other) const { 87 const DomTreeNode *R = getRootNode(); 88 const DomTreeNode *OtherR = Other.getRootNode(); 89 90 if (!R || !OtherR || R->getBlock() != OtherR->getBlock()) 91 return true; 92 93 if (Base::compare(Other)) 94 return true; 95 96 return false; 97 } 98 99 // Ensure base-class overloads are visible. 100 using Base::dominates; 101 102 /// \brief Return true if Def dominates a use in User. 103 /// 104 /// This performs the special checks necessary if Def and User are in the same 105 /// basic block. Note that Def doesn't dominate a use in Def itself! 106 bool dominates(const Instruction *Def, const Use &U) const; 107 bool dominates(const Instruction *Def, const Instruction *User) const; 108 bool dominates(const Instruction *Def, const BasicBlock *BB) const; 109 bool dominates(const BasicBlockEdge &BBE, const Use &U) const; 110 bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const; 111 112 // Ensure base class overloads are visible. 113 using Base::isReachableFromEntry; 114 115 /// \brief Provide an overload for a Use. 116 bool isReachableFromEntry(const Use &U) const; 117 118 /// \brief Verify the correctness of the domtree by re-computing it. 119 /// 120 /// This should only be used for debugging as it aborts the program if the 121 /// verification fails. 122 void verifyDomTree() const; 123}; 124 125//===------------------------------------- 126// DominatorTree GraphTraits specializations so the DominatorTree can be 127// iterable by generic graph iterators. 128 129template <> struct GraphTraits<DomTreeNode*> { 130 typedef DomTreeNode NodeType; 131 typedef NodeType::iterator ChildIteratorType; 132 133 static NodeType *getEntryNode(NodeType *N) { 134 return N; 135 } 136 static inline ChildIteratorType child_begin(NodeType *N) { 137 return N->begin(); 138 } 139 static inline ChildIteratorType child_end(NodeType *N) { 140 return N->end(); 141 } 142 143 typedef df_iterator<DomTreeNode*> nodes_iterator; 144 145 static nodes_iterator nodes_begin(DomTreeNode *N) { 146 return df_begin(getEntryNode(N)); 147 } 148 149 static nodes_iterator nodes_end(DomTreeNode *N) { 150 return df_end(getEntryNode(N)); 151 } 152}; 153 154template <> struct GraphTraits<DominatorTree*> 155 : public GraphTraits<DomTreeNode*> { 156 static NodeType *getEntryNode(DominatorTree *DT) { 157 return DT->getRootNode(); 158 } 159 160 static nodes_iterator nodes_begin(DominatorTree *N) { 161 return df_begin(getEntryNode(N)); 162 } 163 164 static nodes_iterator nodes_end(DominatorTree *N) { 165 return df_end(getEntryNode(N)); 166 } 167}; 168 169/// \brief Analysis pass which computes a \c DominatorTree. 170class DominatorTreeAnalysis { 171public: 172 /// \brief Provide the result typedef for this analysis pass. 173 typedef DominatorTree Result; 174 175 /// \brief Opaque, unique identifier for this analysis pass. 176 static void *ID() { return (void *)&PassID; } 177 178 /// \brief Run the analysis pass over a function and produce a dominator tree. 179 DominatorTree run(Function &F); 180 181 /// \brief Provide access to a name for this pass for debugging purposes. 182 static StringRef name() { return "DominatorTreeAnalysis"; } 183 184private: 185 static char PassID; 186}; 187 188/// \brief Printer pass for the \c DominatorTree. 189class DominatorTreePrinterPass { 190 raw_ostream &OS; 191 192public: 193 explicit DominatorTreePrinterPass(raw_ostream &OS); 194 PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM); 195 196 static StringRef name() { return "DominatorTreePrinterPass"; } 197}; 198 199/// \brief Verifier pass for the \c DominatorTree. 200struct DominatorTreeVerifierPass { 201 PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM); 202 203 static StringRef name() { return "DominatorTreeVerifierPass"; } 204}; 205 206/// \brief Legacy analysis pass which computes a \c DominatorTree. 207class DominatorTreeWrapperPass : public FunctionPass { 208 DominatorTree DT; 209 210public: 211 static char ID; 212 213 DominatorTreeWrapperPass() : FunctionPass(ID) { 214 initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry()); 215 } 216 217 DominatorTree &getDomTree() { return DT; } 218 const DominatorTree &getDomTree() const { return DT; } 219 220 bool runOnFunction(Function &F) override; 221 222 void verifyAnalysis() const override; 223 224 void getAnalysisUsage(AnalysisUsage &AU) const override { 225 AU.setPreservesAll(); 226 } 227 228 void releaseMemory() override { DT.releaseMemory(); } 229 230 void print(raw_ostream &OS, const Module *M = nullptr) const override; 231}; 232 233} // End llvm namespace 234 235#endif 236