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/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::DomTreeBase<CFGBlock>* DT; 42 43 DominatorTree() { 44 DT = new llvm::DomTreeBase<CFGBlock>(); 45 } 46 47 ~DominatorTree() override { delete DT; } 48 49 llvm::DomTreeBase<CFGBlock>& getBase() { return *DT; } 50 51 /// \brief This method returns the root CFGBlock of the dominators tree. 52 /// 53 inline CFGBlock *getRoot() const { 54 return DT->getRoot(); 55 } 56 57 /// \brief This method returns the root DomTreeNode, which is the wrapper 58 /// for CFGBlock. 59 inline DomTreeNode *getRootNode() const { 60 return DT->getRootNode(); 61 } 62 63 /// \brief This method compares two dominator trees. 64 /// The method returns false if the other dominator tree matches this 65 /// dominator tree, otherwise returns true. 66 /// 67 inline bool compare(DominatorTree &Other) const { 68 DomTreeNode *R = getRootNode(); 69 DomTreeNode *OtherR = Other.getRootNode(); 70 71 if (!R || !OtherR || R->getBlock() != OtherR->getBlock()) 72 return true; 73 74 if (DT->compare(Other.getBase())) 75 return true; 76 77 return false; 78 } 79 80 /// \brief This method builds the dominator tree for a given CFG 81 /// The CFG information is passed via AnalysisDeclContext 82 /// 83 void buildDominatorTree(AnalysisDeclContext &AC) { 84 cfg = AC.getCFG(); 85 DT->recalculate(*cfg); 86 } 87 88 /// \brief This method dumps immediate dominators for each block, 89 /// mainly used for debug purposes. 90 /// 91 void dump() { 92 llvm::errs() << "Immediate dominance tree (Node#,IDom#):\n"; 93 for (CFG::const_iterator I = cfg->begin(), 94 E = cfg->end(); I != E; ++I) { 95 if(DT->getNode(*I)->getIDom()) 96 llvm::errs() << "(" << (*I)->getBlockID() 97 << "," 98 << DT->getNode(*I)->getIDom()->getBlock()->getBlockID() 99 << ")\n"; 100 else llvm::errs() << "(" << (*I)->getBlockID() 101 << "," << (*I)->getBlockID() << ")\n"; 102 } 103 } 104 105 /// \brief This method tests if one CFGBlock dominates the other. 106 /// The method return true if A dominates B, false otherwise. 107 /// Note a block always dominates itself. 108 /// 109 inline bool dominates(const CFGBlock* A, const CFGBlock* B) const { 110 return DT->dominates(A, B); 111 } 112 113 /// \brief This method tests if one CFGBlock properly dominates the other. 114 /// The method return true if A properly dominates B, false otherwise. 115 /// 116 bool properlyDominates(const CFGBlock*A, const CFGBlock*B) const { 117 return DT->properlyDominates(A, B); 118 } 119 120 /// \brief 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. 122 /// 123 inline CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) { 124 return DT->findNearestCommonDominator(A, B); 125 } 126 127 inline const CFGBlock *findNearestCommonDominator(const CFGBlock *A, 128 const CFGBlock *B) { 129 return DT->findNearestCommonDominator(A, B); 130 } 131 132 /// \brief This method is used to update the dominator 133 /// tree information when a node's immediate dominator changes. 134 /// 135 inline void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) { 136 DT->changeImmediateDominator(N, NewIDom); 137 } 138 139 /// \brief This method tests if the given CFGBlock can be reachable from root. 140 /// Returns true if reachable, false otherwise. 141 /// 142 bool isReachableFromEntry(const CFGBlock *A) { 143 return DT->isReachableFromEntry(A); 144 } 145 146 /// \brief This method releases the memory held by the dominator tree. 147 /// 148 virtual void releaseMemory() { 149 DT->releaseMemory(); 150 } 151 152 /// \brief This method converts the dominator tree to human readable form. 153 /// 154 virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const { 155 DT->print(OS); 156 } 157 158private: 159 CFG *cfg; 160}; 161 162} // end namespace clang 163 164//===------------------------------------- 165/// DominatorTree GraphTraits specialization so the DominatorTree can be 166/// iterable by generic graph iterators. 167/// 168namespace llvm { 169template <> struct GraphTraits< ::clang::DomTreeNode* > { 170 typedef ::clang::DomTreeNode *NodeRef; 171 typedef ::clang::DomTreeNode::iterator ChildIteratorType; 172 173 static NodeRef getEntryNode(NodeRef N) { return N; } 174 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } 175 static ChildIteratorType child_end(NodeRef N) { return N->end(); } 176 177 typedef llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>> 178 nodes_iterator; 179 180 static nodes_iterator nodes_begin(::clang::DomTreeNode *N) { 181 return nodes_iterator(df_begin(getEntryNode(N))); 182 } 183 184 static nodes_iterator nodes_end(::clang::DomTreeNode *N) { 185 return nodes_iterator(df_end(getEntryNode(N))); 186 } 187}; 188 189template <> struct GraphTraits< ::clang::DominatorTree* > 190 : public GraphTraits< ::clang::DomTreeNode* > { 191 static NodeRef getEntryNode(::clang::DominatorTree *DT) { 192 return DT->getRootNode(); 193 } 194 195 static nodes_iterator nodes_begin(::clang::DominatorTree *N) { 196 return nodes_iterator(df_begin(getEntryNode(N))); 197 } 198 199 static nodes_iterator nodes_end(::clang::DominatorTree *N) { 200 return nodes_iterator(df_end(getEntryNode(N))); 201 } 202}; 203} // end namespace llvm 204 205#endif 206