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/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() override { delete DT; }
48
49  llvm::DominatorTreeBase<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
158private:
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///
168namespace llvm {
169template <> struct GraphTraits< ::clang::DomTreeNode* > {
170  typedef ::clang::DomTreeNode NodeType;
171  typedef NodeType::iterator  ChildIteratorType;
172
173  static NodeType *getEntryNode(NodeType *N) {
174    return N;
175  }
176  static inline ChildIteratorType child_begin(NodeType *N) {
177    return N->begin();
178  }
179  static inline ChildIteratorType child_end(NodeType *N) {
180    return N->end();
181  }
182
183  typedef df_iterator< ::clang::DomTreeNode* > nodes_iterator;
184
185  static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {
186    return df_begin(getEntryNode(N));
187  }
188
189  static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
190    return df_end(getEntryNode(N));
191  }
192};
193
194template <> struct GraphTraits< ::clang::DominatorTree* >
195  : public GraphTraits< ::clang::DomTreeNode* > {
196  static NodeType *getEntryNode(::clang::DominatorTree *DT) {
197    return DT->getRootNode();
198  }
199
200  static nodes_iterator nodes_begin(::clang::DominatorTree *N) {
201    return df_begin(getEntryNode(N));
202  }
203
204  static nodes_iterator nodes_end(::clang::DominatorTree *N) {
205    return df_end(getEntryNode(N));
206  }
207};
208} // end namespace llvm
209
210#endif
211