Dominators.h revision 651f13cea278ec967336033dd032faef0e9fc2ec
1//==- Dominators.h - Implementation of dominators tree for Clang CFG 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 implements the dominators tree functionality for Clang CFGs. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_CLANG_DOMINATORS_H 15#define LLVM_CLANG_DOMINATORS_H 16 17#include "clang/Analysis/AnalysisContext.h" 18#include "clang/Analysis/CFG.h" 19#include "llvm/ADT/GraphTraits.h" 20#include "llvm/Support/GenericDomTree.h" 21#include "llvm/Support/GenericDomTreeConstruction.h" 22 23// FIXME: There is no good reason for the domtree to require a print method 24// which accepts an LLVM Module, so remove this (and the method's argument that 25// needs it) when that is fixed. 26namespace llvm { 27class Module; 28} 29 30namespace clang { 31 32class CFGBlock; 33typedef llvm::DomTreeNodeBase<CFGBlock> DomTreeNode; 34 35/// \brief Concrete subclass of DominatorTreeBase for Clang 36/// This class implements the dominators tree functionality given a Clang CFG. 37/// 38class DominatorTree : public ManagedAnalysis { 39 virtual void anchor(); 40public: 41 llvm::DominatorTreeBase<CFGBlock>* DT; 42 43 DominatorTree() { 44 DT = new llvm::DominatorTreeBase<CFGBlock>(false); 45 } 46 47 ~DominatorTree() { 48 delete DT; 49 } 50 51 llvm::DominatorTreeBase<CFGBlock>& getBase() { return *DT; } 52 53 /// \brief This method returns the root CFGBlock of the dominators tree. 54 /// 55 inline CFGBlock *getRoot() const { 56 return DT->getRoot(); 57 } 58 59 /// \brief This method returns the root DomTreeNode, which is the wrapper 60 /// for CFGBlock. 61 inline DomTreeNode *getRootNode() const { 62 return DT->getRootNode(); 63 } 64 65 /// \brief This method compares two dominator trees. 66 /// The method returns false if the other dominator tree matches this 67 /// dominator tree, otherwise returns true. 68 /// 69 inline bool compare(DominatorTree &Other) const { 70 DomTreeNode *R = getRootNode(); 71 DomTreeNode *OtherR = Other.getRootNode(); 72 73 if (!R || !OtherR || R->getBlock() != OtherR->getBlock()) 74 return true; 75 76 if (DT->compare(Other.getBase())) 77 return true; 78 79 return false; 80 } 81 82 /// \brief This method builds the dominator tree for a given CFG 83 /// The CFG information is passed via AnalysisDeclContext 84 /// 85 void buildDominatorTree(AnalysisDeclContext &AC) { 86 cfg = AC.getCFG(); 87 DT->recalculate(*cfg); 88 } 89 90 /// \brief This method dumps immediate dominators for each block, 91 /// mainly used for debug purposes. 92 /// 93 void dump() { 94 llvm::errs() << "Immediate dominance tree (Node#,IDom#):\n"; 95 for (CFG::const_iterator I = cfg->begin(), 96 E = cfg->end(); I != E; ++I) { 97 if(DT->getNode(*I)->getIDom()) 98 llvm::errs() << "(" << (*I)->getBlockID() 99 << "," 100 << DT->getNode(*I)->getIDom()->getBlock()->getBlockID() 101 << ")\n"; 102 else llvm::errs() << "(" << (*I)->getBlockID() 103 << "," << (*I)->getBlockID() << ")\n"; 104 } 105 } 106 107 /// \brief This method tests if one CFGBlock dominates the other. 108 /// The method return true if A dominates B, false otherwise. 109 /// Note a block always dominates itself. 110 /// 111 inline bool dominates(const CFGBlock* A, const CFGBlock* B) const { 112 return DT->dominates(A, B); 113 } 114 115 /// \brief This method tests if one CFGBlock properly dominates the other. 116 /// The method return true if A properly dominates B, false otherwise. 117 /// 118 bool properlyDominates(const CFGBlock*A, const CFGBlock*B) const { 119 return DT->properlyDominates(A, B); 120 } 121 122 /// \brief This method finds the nearest common dominator CFG block 123 /// for CFG block A and B. If there is no such block then return NULL. 124 /// 125 inline CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) { 126 return DT->findNearestCommonDominator(A, B); 127 } 128 129 inline const CFGBlock *findNearestCommonDominator(const CFGBlock *A, 130 const CFGBlock *B) { 131 return DT->findNearestCommonDominator(A, B); 132 } 133 134 /// \brief This method is used to update the dominator 135 /// tree information when a node's immediate dominator changes. 136 /// 137 inline void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) { 138 DT->changeImmediateDominator(N, NewIDom); 139 } 140 141 /// \brief This method tests if the given CFGBlock can be reachable from root. 142 /// Returns true if reachable, false otherwise. 143 /// 144 bool isReachableFromEntry(const CFGBlock *A) { 145 return DT->isReachableFromEntry(A); 146 } 147 148 /// \brief This method releases the memory held by the dominator tree. 149 /// 150 virtual void releaseMemory() { 151 DT->releaseMemory(); 152 } 153 154 /// \brief This method converts the dominator tree to human readable form. 155 /// 156 virtual void print(raw_ostream &OS, const llvm::Module* M= 0) const { 157 DT->print(OS); 158 } 159 160private: 161 CFG *cfg; 162}; 163 164} // end namespace clang 165 166//===------------------------------------- 167/// DominatorTree GraphTraits specialization so the DominatorTree can be 168/// iterable by generic graph iterators. 169/// 170namespace llvm { 171template <> struct GraphTraits< ::clang::DomTreeNode* > { 172 typedef ::clang::DomTreeNode NodeType; 173 typedef NodeType::iterator ChildIteratorType; 174 175 static NodeType *getEntryNode(NodeType *N) { 176 return N; 177 } 178 static inline ChildIteratorType child_begin(NodeType *N) { 179 return N->begin(); 180 } 181 static inline ChildIteratorType child_end(NodeType *N) { 182 return N->end(); 183 } 184 185 typedef df_iterator< ::clang::DomTreeNode* > nodes_iterator; 186 187 static nodes_iterator nodes_begin(::clang::DomTreeNode *N) { 188 return df_begin(getEntryNode(N)); 189 } 190 191 static nodes_iterator nodes_end(::clang::DomTreeNode *N) { 192 return df_end(getEntryNode(N)); 193 } 194}; 195 196template <> struct GraphTraits< ::clang::DominatorTree* > 197 : public GraphTraits< ::clang::DomTreeNode* > { 198 static NodeType *getEntryNode(::clang::DominatorTree *DT) { 199 return DT->getRootNode(); 200 } 201 202 static nodes_iterator nodes_begin(::clang::DominatorTree *N) { 203 return df_begin(getEntryNode(N)); 204 } 205 206 static nodes_iterator nodes_end(::clang::DominatorTree *N) { 207 return df_end(getEntryNode(N)); 208 } 209}; 210} // end namespace llvm 211 212#endif 213