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_ANALYSIS_ANALYSES_DOMINATORS_H
  15 #define LLVM_CLANG_ANALYSIS_ANALYSES_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() override { delete DT; }
  48
  49   llvm::DominatorTreeBase<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
 158 private:
 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 ///
 168 namespace llvm {
 169 template <> struct GraphTraits< ::clang::DomTreeNode* > {
 170   typedef ::clang::DomTreeNode NodeType;
 171   typedef NodeType::iterator  ChildIteratorType;
 172
 173   static NodeType *getEntryNode(NodeType *N) {
 174     return N;
 175   }
 176   static inline ChildIteratorType child_begin(NodeType *N) {
 177     return N->begin();
 178   }
 179   static inline ChildIteratorType child_end(NodeType *N) {
 180     return N->end();
 181   }
 182
 183   typedef df_iterator< ::clang::DomTreeNode* > nodes_iterator;
 184
 185   static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {
 186     return df_begin(getEntryNode(N));
 187   }
 188
 189   static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
 190     return df_end(getEntryNode(N));
 191   }
 192 };
 193
 194 template <> struct GraphTraits< ::clang::DominatorTree* >
 195   : public GraphTraits< ::clang::DomTreeNode* > {
 196   static NodeType *getEntryNode(::clang::DominatorTree *DT) {
 197     return DT->getRootNode();
 198   }
 199
 200   static nodes_iterator nodes_begin(::clang::DominatorTree *N) {
 201     return df_begin(getEntryNode(N));
 202   }
 203
 204   static nodes_iterator nodes_end(::clang::DominatorTree *N) {
 205     return df_end(getEntryNode(N));
 206   }
 207 };
 208 } // end namespace llvm
 209
 210 #endif