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/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.
26namespace llvm {
27class Module;
28}
29
30namespace clang {
31
32class CFGBlock;
33typedef 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///
38class DominatorTree : public ManagedAnalysis {
39  virtual void anchor();
40public:
41  llvm::DominatorTreeBase<CFGBlock>* DT;
42
43  DominatorTree() {
44    DT = new llvm::DominatorTreeBase<CFGBlock>(false);
45  }
46
47  ~DominatorTree() {
48    delete DT;
49  }
50
51  llvm::DominatorTreeBase<CFGBlock>& getBase() { return *DT; }
52
53  /// \brief This method returns the root CFGBlock of the dominators tree.
54  ///
55  inline CFGBlock *getRoot() const {
56    return DT->getRoot();
57  }
58
59  /// \brief This method returns the root DomTreeNode, which is the wrapper
60  /// for CFGBlock.
61  inline DomTreeNode *getRootNode() const {
62    return DT->getRootNode();
63  }
64
65  /// \brief This method compares two dominator trees.
66  /// The method returns false if the other dominator tree matches this
67  /// dominator tree, otherwise returns true.
68  ///
69  inline bool compare(DominatorTree &Other) const {
70    DomTreeNode *R = getRootNode();
71    DomTreeNode *OtherR = Other.getRootNode();
72
73    if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
74      return true;
75
76    if (DT->compare(Other.getBase()))
77      return true;
78
79    return false;
80  }
81
82  /// \brief This method builds the dominator tree for a given CFG
83  /// The CFG information is passed via AnalysisDeclContext
84  ///
85  void buildDominatorTree(AnalysisDeclContext &AC) {
86    cfg = AC.getCFG();
87    DT->recalculate(*cfg);
88  }
89
90  /// \brief This method dumps immediate dominators for each block,
91  /// mainly used for debug purposes.
92  ///
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  /// \brief 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  ///
111  inline bool dominates(const CFGBlock* A, const CFGBlock* B) const {
112    return DT->dominates(A, B);
113  }
114
115  /// \brief This method tests if one CFGBlock properly dominates the other.
116  /// The method return true if A properly dominates B, false otherwise.
117  ///
118  bool properlyDominates(const CFGBlock*A, const CFGBlock*B) const {
119    return DT->properlyDominates(A, B);
120  }
121
122  /// \brief This method finds the nearest common dominator CFG block
123  /// for CFG block A and B. If there is no such block then return NULL.
124  ///
125  inline CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) {
126    return DT->findNearestCommonDominator(A, B);
127  }
128
129  inline const CFGBlock *findNearestCommonDominator(const CFGBlock *A,
130                                                      const CFGBlock *B) {
131    return DT->findNearestCommonDominator(A, B);
132  }
133
134  /// \brief This method is used to update the dominator
135  /// tree information when a node's immediate dominator changes.
136  ///
137  inline void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) {
138    DT->changeImmediateDominator(N, NewIDom);
139  }
140
141  /// \brief This method tests if the given CFGBlock can be reachable from root.
142  /// Returns true if reachable, false otherwise.
143  ///
144  bool isReachableFromEntry(const CFGBlock *A) {
145    return DT->isReachableFromEntry(A);
146  }
147
148  /// \brief This method releases the memory held by the dominator tree.
149  ///
150  virtual void releaseMemory() {
151    DT->releaseMemory();
152  }
153
154  /// \brief This method converts the dominator tree to human readable form.
155  ///
156  virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const {
157    DT->print(OS);
158  }
159
160private:
161  CFG *cfg;
162};
163
164} // end namespace clang
165
166//===-------------------------------------
167/// DominatorTree GraphTraits specialization so the DominatorTree can be
168/// iterable by generic graph iterators.
169///
170namespace llvm {
171template <> 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
196template <> 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
213