clang  6.0.0svn
Dominators.h
Go to the documentation of this file.
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 
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 ///
39  virtual void anchor();
40 public:
41  llvm::DomTreeBase<CFGBlock>* DT;
42 
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  ///
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  ///
124  return DT->findNearestCommonDominator(A, B);
125  }
126 
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  ///
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* > {
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 *>>
179 
181  return nodes_iterator(df_begin(getEntryNode(N)));
182  }
183 
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
The base class of a hierarchy of objects representing analyses tied to AnalysisDeclContext.
void dump()
This method dumps immediate dominators for each block, mainly used for debug purposes.
Definition: Dominators.h:91
::clang::DomTreeNode::iterator ChildIteratorType
Definition: Dominators.h:171
static nodes_iterator nodes_end(::clang::DomTreeNode *N)
Definition: Dominators.h:184
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: Dominators.h:26
const CFGBlock * findNearestCommonDominator(const CFGBlock *A, const CFGBlock *B)
Definition: Dominators.h:127
llvm::DomTreeBase< CFGBlock > & getBase()
Definition: Dominators.h:49
AnalysisDeclContext contains the context data for the function or method under analysis.
bool isReachableFromEntry(const CFGBlock *A)
This method tests if the given CFGBlock can be reachable from root.
Definition: Dominators.h:142
static NodeRef getEntryNode(NodeRef N)
Definition: Dominators.h:173
static NodeRef getEntryNode(::clang::DominatorTree *DT)
Definition: Dominators.h:191
static ChildIteratorType child_begin(NodeRef N)
Definition: Dominators.h:174
Concrete subclass of DominatorTreeBase for Clang This class implements the dominators tree functional...
Definition: Dominators.h:38
CFGBlockListTy::const_iterator const_iterator
Definition: CFG.h:899
CFGBlock - Represents a single basic block in a source-level CFG.
Definition: CFG.h:422
CFG - Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:834
void buildDominatorTree(AnalysisDeclContext &AC)
This method builds the dominator tree for a given CFG The CFG information is passed via AnalysisDeclC...
Definition: Dominators.h:83
virtual void releaseMemory()
This method releases the memory held by the dominator tree.
Definition: Dominators.h:148
bool compare(DominatorTree &Other) const
This method compares two dominator trees.
Definition: Dominators.h:67
static ChildIteratorType child_end(NodeRef N)
Definition: Dominators.h:175
llvm::DomTreeNodeBase< CFGBlock > DomTreeNode
Definition: Dominators.h:32
static nodes_iterator nodes_begin(::clang::DominatorTree *N)
Definition: Dominators.h:195
CFGBlock * getRoot() const
This method returns the root CFGBlock of the dominators tree.
Definition: Dominators.h:53
static nodes_iterator nodes_begin(::clang::DomTreeNode *N)
Definition: Dominators.h:180
CFGBlock * findNearestCommonDominator(CFGBlock *A, CFGBlock *B)
This method finds the nearest common dominator CFG block for CFG block A and B.
Definition: Dominators.h:123
DomTreeNode * getRootNode() const
This method returns the root DomTreeNode, which is the wrapper for CFGBlock.
Definition: Dominators.h:59
static nodes_iterator nodes_end(::clang::DominatorTree *N)
Definition: Dominators.h:199
Dataflow Directional Tag Classes.
virtual void print(raw_ostream &OS, const llvm::Module *M=nullptr) const
This method converts the dominator tree to human readable form.
Definition: Dominators.h:154
bool dominates(const CFGBlock *A, const CFGBlock *B) const
This method tests if one CFGBlock dominates the other.
Definition: Dominators.h:109
llvm::DomTreeBase< CFGBlock > * DT
Definition: Dominators.h:41
bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const
This method tests if one CFGBlock properly dominates the other.
Definition: Dominators.h:116
llvm::pointer_iterator< df_iterator<::clang::DomTreeNode * > > nodes_iterator
Definition: Dominators.h:178
~DominatorTree() override
Definition: Dominators.h:47
void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom)
This method is used to update the dominator tree information when a node&#39;s immediate dominator change...
Definition: Dominators.h:135