clang  8.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/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 ///
44  virtual void anchor();
45 
46 public:
47  llvm::DomTreeBase<CFGBlock> *DT;
48 
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.
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
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.
123  return DT->findNearestCommonDominator(A, B);
124  }
125 
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.
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.
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* > {
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 
177  return nodes_iterator(df_begin(getEntryNode(N)));
178  }
179 
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
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:93
static nodes_iterator nodes_end(::clang::DomTreeNode *N)
Definition: Dominators.h:180
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: Dominators.h:30
const CFGBlock * findNearestCommonDominator(const CFGBlock *A, const CFGBlock *B)
Definition: Dominators.h:126
llvm::DomTreeBase< CFGBlock > & getBase()
Definition: Dominators.h:55
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:139
static NodeRef getEntryNode(NodeRef N)
Definition: Dominators.h:169
static NodeRef getEntryNode(::clang::DominatorTree *DT)
Definition: Dominators.h:187
static ChildIteratorType child_begin(NodeRef N)
Definition: Dominators.h:170
Concrete subclass of DominatorTreeBase for Clang This class implements the dominators tree functional...
Definition: Dominators.h:43
CFGBlockListTy::const_iterator const_iterator
Definition: CFG.h:1071
Represents a single basic block in a source-level CFG.
Definition: CFG.h:552
llvm::DomTreeNodeBase< CFGBlock > DomTreeNode
Definition: Dominators.h:38
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:1003
void buildDominatorTree(AnalysisDeclContext &AC)
This method builds the dominator tree for a given CFG The CFG information is passed via AnalysisDeclC...
Definition: Dominators.h:86
virtual void releaseMemory()
This method releases the memory held by the dominator tree.
Definition: Dominators.h:144
bool compare(DominatorTree &Other) const
This method compares two dominator trees.
Definition: Dominators.h:71
static ChildIteratorType child_end(NodeRef N)
Definition: Dominators.h:171
static nodes_iterator nodes_begin(::clang::DominatorTree *N)
Definition: Dominators.h:191
CFGBlock * getRoot() const
This method returns the root CFGBlock of the dominators tree.
Definition: Dominators.h:58
static nodes_iterator nodes_begin(::clang::DomTreeNode *N)
Definition: Dominators.h:176
CFGBlock * findNearestCommonDominator(CFGBlock *A, CFGBlock *B)
This method finds the nearest common dominator CFG block for CFG block A and B.
Definition: Dominators.h:122
DomTreeNode * getRootNode() const
This method returns the root DomTreeNode, which is the wrapper for CFGBlock.
Definition: Dominators.h:64
::clang::DomTreeNode::iterator ChildIteratorType
Definition: Dominators.h:167
static nodes_iterator nodes_end(::clang::DominatorTree *N)
Definition: Dominators.h:195
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:149
llvm::pointer_iterator< df_iterator<::clang::DomTreeNode * > > nodes_iterator
Definition: Dominators.h:174
bool dominates(const CFGBlock *A, const CFGBlock *B) const
This method tests if one CFGBlock dominates the other.
Definition: Dominators.h:110
llvm::DomTreeBase< CFGBlock > * DT
Definition: Dominators.h:47
bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const
This method tests if one CFGBlock properly dominates the other.
Definition: Dominators.h:116
~DominatorTree() override
Definition: Dominators.h:53
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:133