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/AnalysisDeclContext.h"
  18 #include "clang/Analysis/CFG.h"
  19 #include "llvm/ADT/DepthFirstIterator.h"
  20 #include "llvm/ADT/GraphTraits.h"
  21 #include "llvm/ADT/iterator.h"
  22 #include "llvm/Support/GenericDomTree.h"
  23 #include "llvm/Support/GenericDomTreeConstruction.h"
  24 #include "llvm/Support/raw_ostream.h"
  25
  26 // FIXME: There is no good reason for the domtree to require a print method
  27 // which accepts an LLVM Module, so remove this (and the method's argument that
  28 // needs it) when that is fixed.
  29
  30 namespace llvm {
  31
  32 class Module;
  33
  34 } // namespace llvm
  35
  36 namespace clang {
  37
  38 using DomTreeNode = llvm::DomTreeNodeBase<CFGBlock>;
  39
  40 /// Concrete subclass of DominatorTreeBase for Clang
  41 /// This class implements the dominators tree functionality given a Clang CFG.
  42 ///
  43 class DominatorTree : public ManagedAnalysis {
  44   virtual void anchor();
  45
  46 public:
  47   llvm::DomTreeBase<CFGBlock> *DT;
  48
  49   DominatorTree() {
  50     DT = new llvm::DomTreeBase<CFGBlock>();
  51   }
  52
  53   ~DominatorTree() override { delete DT; }
  54
  55   llvm::DomTreeBase<CFGBlock>& getBase() { return *DT; }
  56
  57   /// This method returns the root CFGBlock of the dominators tree.
  58   CFGBlock *getRoot() const {
  59     return DT->getRoot();
  60   }
  61
  62   /// This method returns the root DomTreeNode, which is the wrapper
  63   /// for CFGBlock.
  64   DomTreeNode *getRootNode() const {
  65     return DT->getRootNode();
  66   }
  67
  68   /// This method compares two dominator trees.
  69   /// The method returns false if the other dominator tree matches this
  70   /// dominator tree, otherwise returns true.
  71   bool compare(DominatorTree &Other) const {
  72     DomTreeNode *R = getRootNode();
  73     DomTreeNode *OtherR = Other.getRootNode();
  74
  75     if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
  76       return true;
  77
  78     if (DT->compare(Other.getBase()))
  79       return true;
  80
  81     return false;
  82   }
  83
  84   /// This method builds the dominator tree for a given CFG
  85   /// The CFG information is passed via AnalysisDeclContext
  86   void buildDominatorTree(AnalysisDeclContext &AC) {
  87     cfg = AC.getCFG();
  88     DT->recalculate(*cfg);
  89   }
  90
  91   /// This method dumps immediate dominators for each block,
  92   /// mainly used for debug purposes.
  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   /// 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   bool dominates(const CFGBlock *A, const CFGBlock *B) const {
 111     return DT->dominates(A, B);
 112   }
 113
 114   /// This method tests if one CFGBlock properly dominates the other.
 115   /// The method return true if A properly dominates B, false otherwise.
 116   bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const {
 117     return DT->properlyDominates(A, B);
 118   }
 119
 120   /// 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   CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) {
 123     return DT->findNearestCommonDominator(A, B);
 124   }
 125
 126   const CFGBlock *findNearestCommonDominator(const CFGBlock *A,
 127                                              const CFGBlock *B) {
 128     return DT->findNearestCommonDominator(A, B);
 129   }
 130
 131   /// This method is used to update the dominator
 132   /// tree information when a node's immediate dominator changes.
 133   void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) {
 134     DT->changeImmediateDominator(N, NewIDom);
 135   }
 136
 137   /// This method tests if the given CFGBlock can be reachable from root.
 138   /// Returns true if reachable, false otherwise.
 139   bool isReachableFromEntry(const CFGBlock *A) {
 140     return DT->isReachableFromEntry(A);
 141   }
 142
 143   /// This method releases the memory held by the dominator tree.
 144   virtual void releaseMemory() {
 145     DT->releaseMemory();
 146   }
 147
 148   /// This method converts the dominator tree to human readable form.
 149   virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const {
 150     DT->print(OS);
 151   }
 152
 153 private:
 154   CFG *cfg;
 155 };
 156
 157 } // namespace clang
 158
 159 //===-------------------------------------
 160 /// DominatorTree GraphTraits specialization so the DominatorTree can be
 161 /// iterable by generic graph iterators.
 162 ///
 163 namespace llvm {
 164
 165 template <> struct GraphTraits< ::clang::DomTreeNode* > {
 166   using NodeRef = ::clang::DomTreeNode *;
 167   using ChildIteratorType = ::clang::DomTreeNode::iterator;
 168
 169   static NodeRef getEntryNode(NodeRef N) { return N; }
 170   static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
 171   static ChildIteratorType child_end(NodeRef N) { return N->end(); }
 172
 173   using nodes_iterator =
 174       llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>;
 175
 176   static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {
 177     return nodes_iterator(df_begin(getEntryNode(N)));
 178   }
 179
 180   static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
 181     return nodes_iterator(df_end(getEntryNode(N)));
 182   }
 183 };
 184
 185 template <> struct GraphTraits< ::clang::DominatorTree* >
 186     : public GraphTraits< ::clang::DomTreeNode* > {
 187   static NodeRef getEntryNode(::clang::DominatorTree *DT) {
 188     return DT->getRootNode();
 189   }
 190
 191   static nodes_iterator nodes_begin(::clang::DominatorTree *N) {
 192     return nodes_iterator(df_begin(getEntryNode(N)));
 193   }
 194
 195   static nodes_iterator nodes_end(::clang::DominatorTree *N) {
 196     return nodes_iterator(df_end(getEntryNode(N)));
 197   }
 198 };
 199
 200 } // namespace llvm
 201
 202 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H