contrib/llvm/tools/clang/include/clang/Analysis/Analyses/Dominators.h

   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.
  26 namespace llvm {
  27 class Module;
  28 }
  29
  30 namespace clang {
  31
  32 class CFGBlock;
  33 typedef 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 ///
  38 class DominatorTree : public ManagedAnalysis {
  39   virtual void anchor();
  40 public:
  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= nullptr) const {
 157     DT->print(OS);
 158   }
 159
 160 private:
 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 ///
 170 namespace llvm {
 171 template <> 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
 196 template <> 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