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
  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
  25 namespace clang {
  26
  27 class CFGBlock;
  28 typedef 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 ///
  33 class DominatorTree : public ManagedAnalysis {
  34   virtual void anchor();
  35 public:
  36   llvm::DominatorTreeBase<CFGBlock>* DT;
  37
  38   DominatorTree() {
  39     DT = new llvm::DominatorTreeBase<CFGBlock>(false);
  40   }
  41
  42   ~DominatorTree() {
  43     delete DT;
  44   }
  45
  46   llvm::DominatorTreeBase<CFGBlock>& getBase() { return *DT; }
  47
  48   /// \brief This method returns the root CFGBlock of the dominators tree.
  49   ///
  50   inline CFGBlock *getRoot() const {
  51     return DT->getRoot();
  52   }
  53
  54   /// \brief This method returns the root DomTreeNode, which is the wrapper
  55   /// for CFGBlock.
  56   inline DomTreeNode *getRootNode() const {
  57     return DT->getRootNode();
  58   }
  59
  60   /// \brief This method compares two dominator trees.
  61   /// The method returns false if the other dominator tree matches this
  62   /// dominator tree, otherwise returns true.
  63   ///
  64   inline bool compare(DominatorTree &Other) const {
  65     DomTreeNode *R = getRootNode();
  66     DomTreeNode *OtherR = Other.getRootNode();
  67
  68     if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
  69       return true;
  70
  71     if (DT->compare(Other.getBase()))
  72       return true;
  73
  74     return false;
  75   }
  76
  77   /// \brief This method builds the dominator tree for a given CFG
  78   /// The CFG information is passed via AnalysisDeclContext
  79   ///
  80   void buildDominatorTree(AnalysisDeclContext &AC) {
  81     cfg = AC.getCFG();
  82     DT->recalculate(*cfg);
  83   }
  84
  85   /// \brief This method dumps immediate dominators for each block,
  86   /// mainly used for debug purposes.
  87   ///
  88   void dump() {
  89     llvm::errs() << "Immediate dominance tree (Node#,IDom#):\n";
  90     for (CFG::const_iterator I = cfg->begin(),
  91         E = cfg->end(); I != E; ++I) {
  92       if(DT->getNode(*I)->getIDom())
  93         llvm::errs() << "(" << (*I)->getBlockID()
  94                      << ","
  95                      << DT->getNode(*I)->getIDom()->getBlock()->getBlockID()
  96                      << ")\n";
  97       else llvm::errs() << "(" << (*I)->getBlockID()
  98                         << "," << (*I)->getBlockID() << ")\n";
  99     }
 100   }
 101
 102   /// \brief This method tests if one CFGBlock dominates the other.
 103   /// The method return true if A dominates B, false otherwise.
 104   /// Note a block always dominates itself.
 105   ///
 106   inline bool dominates(const CFGBlock* A, const CFGBlock* B) const {
 107     return DT->dominates(A, B);
 108   }
 109
 110   /// \brief This method tests if one CFGBlock properly dominates the other.
 111   /// The method return true if A properly dominates B, false otherwise.
 112   ///
 113   bool properlyDominates(const CFGBlock*A, const CFGBlock*B) const {
 114     return DT->properlyDominates(A, B);
 115   }
 116
 117   /// \brief This method finds the nearest common dominator CFG block
 118   /// for CFG block A and B. If there is no such block then return NULL.
 119   ///
 120   inline CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) {
 121     return DT->findNearestCommonDominator(A, B);
 122   }
 123
 124   inline const CFGBlock *findNearestCommonDominator(const CFGBlock *A,
 125                                                       const CFGBlock *B) {
 126     return DT->findNearestCommonDominator(A, B);
 127   }
 128
 129   /// \brief This method is used to update the dominator
 130   /// tree information when a node's immediate dominator changes.
 131   ///
 132   inline void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) {
 133     DT->changeImmediateDominator(N, NewIDom);
 134   }
 135
 136   /// \brief This method tests if the given CFGBlock can be reachable from root.
 137   /// Returns true if reachable, false otherwise.
 138   ///
 139   bool isReachableFromEntry(const CFGBlock *A) {
 140     return DT->isReachableFromEntry(A);
 141   }
 142
 143   /// \brief This method releases the memory held by the dominator tree.
 144   ///
 145   virtual void releaseMemory() {
 146     DT->releaseMemory();
 147   }
 148
 149   /// \brief This method converts the dominator tree to human readable form.
 150   ///
 151   virtual void print(raw_ostream &OS, const llvm::Module* M= 0) const {
 152     DT->print(OS);
 153   }
 154
 155 private:
 156   CFG *cfg;
 157 };
 158
 159 inline void WriteAsOperand(raw_ostream &OS, const CFGBlock *BB,
 160                           bool t) {
 161   OS << "BB#" << BB->getBlockID();
 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