Home | History | Annotate | Download | only in Analyses 
      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/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::DomTreeBase<CFGBlock>* DT;
     42 
     43   DominatorTree() {
     44     DT = new llvm::DomTreeBase<CFGBlock>();
     45   }
     46 
     47   ~DominatorTree() override { delete DT; }
     48 
     49   llvm::DomTreeBase<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 *NodeRef;
    171   typedef ::clang::DomTreeNode::iterator ChildIteratorType;
    172 
    173   static NodeRef getEntryNode(NodeRef N) { return N; }
    174   static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
    175   static ChildIteratorType child_end(NodeRef N) { return N->end(); }
    176 
    177   typedef llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>
    178       nodes_iterator;
    179 
    180   static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {
    181     return nodes_iterator(df_begin(getEntryNode(N)));
    182   }
    183 
    184   static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
    185     return nodes_iterator(df_end(getEntryNode(N)));
    186   }
    187 };
    188 
    189 template <> struct GraphTraits< ::clang::DominatorTree* >
    190   : public GraphTraits< ::clang::DomTreeNode* > {
    191   static NodeRef getEntryNode(::clang::DominatorTree *DT) {
    192     return DT->getRootNode();
    193   }
    194 
    195   static nodes_iterator nodes_begin(::clang::DominatorTree *N) {
    196     return nodes_iterator(df_begin(getEntryNode(N)));
    197   }
    198 
    199   static nodes_iterator nodes_end(::clang::DominatorTree *N) {
    200     return nodes_iterator(df_end(getEntryNode(N)));
    201   }
    202 };
    203 } // end namespace llvm
    204 
    205 #endif
    206