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 34EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>); 35EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>); 36 37#define LLVM_COMMA , 38EXTERN_TEMPLATE_INSTANTIATION(void Calculate<Function LLVM_COMMA BasicBlock *>( 39 DominatorTreeBase<GraphTraits<BasicBlock *>::NodeType> &DT LLVM_COMMA 40 Function &F)); 41EXTERN_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 47typedef DomTreeNodeBase<BasicBlock> DomTreeNode; 48 49class BasicBlockEdge { 50 const BasicBlock *Start; 51 const BasicBlock *End; 52public: 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. 66class DominatorTree : public DominatorTreeBase<BasicBlock> { 67public: 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 117template <> 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 142template <> 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. 158class DominatorTreeWrapperPass : public FunctionPass { 159 DominatorTree DT; 160 161public: 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