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