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