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