clang  9.0.0svn
Dominators.h
Go to the documentation of this file.
1 //- Dominators.h - Implementation of dominators tree for Clang CFG -*- C++ -*-//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the dominators tree functionality for Clang CFGs.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
14 #define LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
15 
17 #include "clang/Analysis/CFG.h"
18 #include "llvm/ADT/DepthFirstIterator.h"
19 #include "llvm/ADT/GraphTraits.h"
20 #include "llvm/ADT/iterator.h"
21 #include "llvm/Support/GenericDomTree.h"
22 #include "llvm/Support/GenericDomTreeConstruction.h"
23 #include "llvm/Support/raw_ostream.h"
24 
25 // FIXME: There is no good reason for the domtree to require a print method
26 // which accepts an LLVM Module, so remove this (and the method's argument that
27 // needs it) when that is fixed.
28 
29 namespace llvm {
30 
31 class Module;
32 
33 } // namespace llvm
34 
35 namespace clang {
36 
37 using DomTreeNode = llvm::DomTreeNodeBase<CFGBlock>;
38 
39 /// Concrete subclass of DominatorTreeBase for Clang
40 /// This class implements the dominators tree functionality given a Clang CFG.
41 ///
43  virtual void anchor();
44 
45 public:
46  llvm::DomTreeBase<CFGBlock> *DT;
47 
49  DT = new llvm::DomTreeBase<CFGBlock>();
50  }
51 
52  ~DominatorTree() override { delete DT; }
53 
54  llvm::DomTreeBase<CFGBlock>& getBase() { return *DT; }
55 
56  /// This method returns the root CFGBlock of the dominators tree.
57  CFGBlock *getRoot() const {
58  return DT->getRoot();
59  }
60 
61  /// This method returns the root DomTreeNode, which is the wrapper
62  /// for CFGBlock.
64  return DT->getRootNode();
65  }
66 
67  /// This method compares two dominator trees.
68  /// The method returns false if the other dominator tree matches this
69  /// dominator tree, otherwise returns true.
70  bool compare(DominatorTree &Other) const {
71  DomTreeNode *R = getRootNode();
72  DomTreeNode *OtherR = Other.getRootNode();
73 
74  if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
75  return true;
76 
77  if (DT->compare(Other.getBase()))
78  return true;
79 
80  return false;
81  }
82 
83  /// This method builds the dominator tree for a given CFG
84  /// The CFG information is passed via AnalysisDeclContext
86  cfg = AC.getCFG();
87  DT->recalculate(*cfg);
88  }
89 
90  /// This method dumps immediate dominators for each block,
91  /// mainly used for debug purposes.
92  void dump() {
93  llvm::errs() << "Immediate dominance tree (Node#,IDom#):\n";
94  for (CFG::const_iterator I = cfg->begin(),
95  E = cfg->end(); I != E; ++I) {
96  if(DT->getNode(*I)->getIDom())
97  llvm::errs() << "(" << (*I)->getBlockID()
98  << ","
99  << DT->getNode(*I)->getIDom()->getBlock()->getBlockID()
100  << ")\n";
101  else llvm::errs() << "(" << (*I)->getBlockID()
102  << "," << (*I)->getBlockID() << ")\n";
103  }
104  }
105 
106  /// This method tests if one CFGBlock dominates the other.
107  /// The method return true if A dominates B, false otherwise.
108  /// Note a block always dominates itself.
109  bool dominates(const CFGBlock *A, const CFGBlock *B) const {
110  return DT->dominates(A, B);
111  }
112 
113  /// This method tests if one CFGBlock properly dominates the other.
114  /// The method return true if A properly dominates B, false otherwise.
115  bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const {
116  return DT->properlyDominates(A, B);
117  }
118 
119  /// This method finds the nearest common dominator CFG block
120  /// for CFG block A and B. If there is no such block then return NULL.
122  return DT->findNearestCommonDominator(A, B);
123  }
124 
126  const CFGBlock *B) {
127  return DT->findNearestCommonDominator(A, B);
128  }
129 
130  /// This method is used to update the dominator
131  /// tree information when a node's immediate dominator changes.
133  DT->changeImmediateDominator(N, NewIDom);
134  }
135 
136  /// This method tests if the given CFGBlock can be reachable from root.
137  /// Returns true if reachable, false otherwise.
139  return DT->isReachableFromEntry(A);
140  }
141 
142  /// This method releases the memory held by the dominator tree.
143  virtual void releaseMemory() {
144  DT->releaseMemory();
145  }
146 
147  /// This method converts the dominator tree to human readable form.
148  virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const {
149  DT->print(OS);
150  }
151 
152 private:
153  CFG *cfg;
154 };
155 
156 } // namespace clang
157 
158 //===-------------------------------------
159 /// DominatorTree GraphTraits specialization so the DominatorTree can be
160 /// iterable by generic graph iterators.
161 ///
162 namespace llvm {
163 
164 template <> struct GraphTraits< ::clang::DomTreeNode* > {
166  using ChildIteratorType = ::clang::DomTreeNode::iterator;
167 
168  static NodeRef getEntryNode(NodeRef N) { return N; }
169  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
170  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
171 
172  using nodes_iterator =
173  llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>;
174 
176  return nodes_iterator(df_begin(getEntryNode(N)));
177  }
178 
180  return nodes_iterator(df_end(getEntryNode(N)));
181  }
182 };
183 
184 template <> struct GraphTraits< ::clang::DominatorTree* >
185  : public GraphTraits< ::clang::DomTreeNode* > {
186  static NodeRef getEntryNode(::clang::DominatorTree *DT) {
187  return DT->getRootNode();
188  }
189 
190  static nodes_iterator nodes_begin(::clang::DominatorTree *N) {
191  return nodes_iterator(df_begin(getEntryNode(N)));
192  }
193 
194  static nodes_iterator nodes_end(::clang::DominatorTree *N) {
195  return nodes_iterator(df_end(getEntryNode(N)));
196  }
197 };
198 
199 } // namespace llvm
200 
201 #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:92
static nodes_iterator nodes_end(::clang::DomTreeNode *N)
Definition: Dominators.h:179
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: Dominators.h:29
const CFGBlock * findNearestCommonDominator(const CFGBlock *A, const CFGBlock *B)
Definition: Dominators.h:125
llvm::DomTreeBase< CFGBlock > & getBase()
Definition: Dominators.h:54
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:138
static NodeRef getEntryNode(NodeRef N)
Definition: Dominators.h:168
static NodeRef getEntryNode(::clang::DominatorTree *DT)
Definition: Dominators.h:186
static ChildIteratorType child_begin(NodeRef N)
Definition: Dominators.h:169
Concrete subclass of DominatorTreeBase for Clang This class implements the dominators tree functional...
Definition: Dominators.h:42
CFGBlockListTy::const_iterator const_iterator
Definition: CFG.h:1070
Represents a single basic block in a source-level CFG.
Definition: CFG.h:551
llvm::DomTreeNodeBase< CFGBlock > DomTreeNode
Definition: Dominators.h:37
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:1002
void buildDominatorTree(AnalysisDeclContext &AC)
This method builds the dominator tree for a given CFG The CFG information is passed via AnalysisDeclC...
Definition: Dominators.h:85
virtual void releaseMemory()
This method releases the memory held by the dominator tree.
Definition: Dominators.h:143
bool compare(DominatorTree &Other) const
This method compares two dominator trees.
Definition: Dominators.h:70
static ChildIteratorType child_end(NodeRef N)
Definition: Dominators.h:170
static nodes_iterator nodes_begin(::clang::DominatorTree *N)
Definition: Dominators.h:190
CFGBlock * getRoot() const
This method returns the root CFGBlock of the dominators tree.
Definition: Dominators.h:57
static nodes_iterator nodes_begin(::clang::DomTreeNode *N)
Definition: Dominators.h:175
CFGBlock * findNearestCommonDominator(CFGBlock *A, CFGBlock *B)
This method finds the nearest common dominator CFG block for CFG block A and B.
Definition: Dominators.h:121
DomTreeNode * getRootNode() const
This method returns the root DomTreeNode, which is the wrapper for CFGBlock.
Definition: Dominators.h:63
::clang::DomTreeNode::iterator ChildIteratorType
Definition: Dominators.h:166
static nodes_iterator nodes_end(::clang::DominatorTree *N)
Definition: Dominators.h:194
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:148
llvm::pointer_iterator< df_iterator<::clang::DomTreeNode * > > nodes_iterator
Definition: Dominators.h:173
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:46
bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const
This method tests if one CFGBlock properly dominates the other.
Definition: Dominators.h:115
~DominatorTree() override
Definition: Dominators.h:52
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:132