clang  14.0.0git
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/GenericIteratedDominanceFrontier.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 /// Dominator tree builder for Clang's CFG based on llvm::DominatorTreeBase.
41 template <bool IsPostDom>
43  virtual void anchor();
44 
45 public:
46  using DominatorTreeBase = llvm::DominatorTreeBase<CFGBlock, IsPostDom>;
47 
48  CFGDominatorTreeImpl() = default;
49 
51  buildDominatorTree(cfg);
52  }
53 
54  ~CFGDominatorTreeImpl() override = default;
55 
56  DominatorTreeBase &getBase() { return DT; }
57 
58  CFG *getCFG() { return cfg; }
59 
60  /// \returns the root CFGBlock of the dominators tree.
61  CFGBlock *getRoot() const {
62  return DT.getRoot();
63  }
64 
65  /// \returns the root DomTreeNode, which is the wrapper for CFGBlock.
67  return DT.getRootNode();
68  }
69 
70  /// Compares two dominator trees.
71  /// \returns false if the other dominator tree matches this dominator tree,
72  /// false otherwise.
73  bool compare(CFGDominatorTreeImpl &Other) const {
74  DomTreeNode *R = getRootNode();
75  DomTreeNode *OtherR = Other.getRootNode();
76 
77  if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
78  return true;
79 
80  if (DT.compare(Other.getBase()))
81  return true;
82 
83  return false;
84  }
85 
86  /// Builds the dominator tree for a given CFG.
87  void buildDominatorTree(CFG *cfg) {
88  assert(cfg);
89  this->cfg = cfg;
90  DT.recalculate(*cfg);
91  }
92 
93  /// Dumps immediate dominators for each block.
94  void dump() {
95  llvm::errs() << "Immediate " << (IsPostDom ? "post " : "")
96  << "dominance tree (Node#,IDom#):\n";
97  for (CFG::const_iterator I = cfg->begin(),
98  E = cfg->end(); I != E; ++I) {
99 
100  assert(*I &&
101  "LLVM's Dominator tree builder uses nullpointers to signify the "
102  "virtual root!");
103 
104  DomTreeNode *IDom = DT.getNode(*I)->getIDom();
105  if (IDom && IDom->getBlock())
106  llvm::errs() << "(" << (*I)->getBlockID()
107  << ","
108  << IDom->getBlock()->getBlockID()
109  << ")\n";
110  else {
111  bool IsEntryBlock = *I == &(*I)->getParent()->getEntry();
112  bool IsExitBlock = *I == &(*I)->getParent()->getExit();
113 
114  bool IsDomTreeRoot = !IDom && !IsPostDom && IsEntryBlock;
115  bool IsPostDomTreeRoot =
116  IDom && !IDom->getBlock() && IsPostDom && IsExitBlock;
117 
118  assert((IsDomTreeRoot || IsPostDomTreeRoot) &&
119  "If the immediate dominator node is nullptr, the CFG block "
120  "should be the exit point (since it's the root of the dominator "
121  "tree), or if the CFG block it refers to is a nullpointer, it "
122  "must be the entry block (since it's the root of the post "
123  "dominator tree)");
124 
125  (void)IsDomTreeRoot;
126  (void)IsPostDomTreeRoot;
127 
128  llvm::errs() << "(" << (*I)->getBlockID()
129  << "," << (*I)->getBlockID() << ")\n";
130  }
131  }
132  }
133 
134  /// Tests whether \p A dominates \p B.
135  /// Note a block always dominates itself.
136  bool dominates(const CFGBlock *A, const CFGBlock *B) const {
137  return DT.dominates(A, B);
138  }
139 
140  /// Tests whether \p A properly dominates \p B.
141  /// \returns false if \p A is the same block as \p B, otherwise whether A
142  /// dominates B.
143  bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const {
144  return DT.properlyDominates(A, B);
145  }
146 
147  /// \returns the nearest common dominator CFG block for CFG block \p A and \p
148  /// B. If there is no such block then return NULL.
150  return DT.findNearestCommonDominator(A, B);
151  }
152 
154  const CFGBlock *B) {
155  return DT.findNearestCommonDominator(A, B);
156  }
157 
158  /// Update the dominator tree information when a node's immediate dominator
159  /// changes.
161  DT.changeImmediateDominator(N, NewIDom);
162  }
163 
164  /// Tests whether \p A is reachable from the entry block.
166  return DT.isReachableFromEntry(A);
167  }
168 
169  /// Releases the memory held by the dominator tree.
170  virtual void releaseMemory() { DT.reset(); }
171 
172  /// Converts the dominator tree to human readable form.
173  virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const {
174  DT.print(OS);
175  }
176 
177 private:
178  CFG *cfg;
180 };
181 
182 using CFGDomTree = CFGDominatorTreeImpl</*IsPostDom*/ false>;
183 using CFGPostDomTree = CFGDominatorTreeImpl</*IsPostDom*/ true>;
184 
185 template<> void CFGDominatorTreeImpl<true>::anchor();
186 template<> void CFGDominatorTreeImpl<false>::anchor();
187 
188 } // end of namespace clang
189 
190 namespace llvm {
191 namespace IDFCalculatorDetail {
192 
193 /// Specialize ChildrenGetterTy to skip nullpointer successors.
194 template <bool IsPostDom>
195 struct ChildrenGetterTy<clang::CFGBlock, IsPostDom> {
198 
199  ChildrenTy get(const NodeRef &N) {
200  using OrderedNodeTy =
201  typename IDFCalculatorBase<clang::CFGBlock, IsPostDom>::OrderedNodeTy;
202 
203  auto Children = children<OrderedNodeTy>(N);
204  ChildrenTy Ret{Children.begin(), Children.end()};
205  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
206  return Ret;
207  }
208 };
209 
210 } // end of namespace IDFCalculatorDetail
211 } // end of namespace llvm
212 
213 namespace clang {
214 
216  using IDFCalculator = llvm::IDFCalculatorBase<CFGBlock, /*IsPostDom=*/true>;
219 
220  CFGPostDomTree PostDomTree;
221  IDFCalculator IDFCalc;
222 
223  llvm::DenseMap<CFGBlock *, CFGBlockVector> ControlDepenencyMap;
224 
225 public:
227  : PostDomTree(cfg), IDFCalc(PostDomTree.getBase()) {}
228 
229  const CFGPostDomTree &getCFGPostDomTree() const { return PostDomTree; }
230 
231  // Lazily retrieves the set of control dependencies to \p A.
233  auto It = ControlDepenencyMap.find(A);
234  if (It == ControlDepenencyMap.end()) {
235  CFGBlockSet DefiningBlock = {A};
236  IDFCalc.setDefiningBlocks(DefiningBlock);
237 
238  CFGBlockVector ControlDependencies;
239  IDFCalc.calculate(ControlDependencies);
240 
241  It = ControlDepenencyMap.insert({A, ControlDependencies}).first;
242  }
243 
244  assert(It != ControlDepenencyMap.end());
245  return It->second;
246  }
247 
248  /// Whether \p A is control dependent on \p B.
250  return llvm::is_contained(getControlDependencies(A), B);
251  }
252 
253  // Dumps immediate control dependencies for each block.
254  LLVM_DUMP_METHOD void dump() {
255  CFG *cfg = PostDomTree.getCFG();
256  llvm::errs() << "Control dependencies (Node#,Dependency#):\n";
257  for (CFGBlock *BB : *cfg) {
258 
259  assert(BB &&
260  "LLVM's Dominator tree builder uses nullpointers to signify the "
261  "virtual root!");
262 
263  for (CFGBlock *isControlDependency : getControlDependencies(BB))
264  llvm::errs() << "(" << BB->getBlockID()
265  << ","
266  << isControlDependency->getBlockID()
267  << ")\n";
268  }
269  }
270 };
271 
272 } // namespace clang
273 
274 namespace llvm {
275 
276 //===-------------------------------------
277 /// DominatorTree GraphTraits specialization so the DominatorTree can be
278 /// iterable by generic graph iterators.
279 ///
280 template <> struct GraphTraits<clang::DomTreeNode *> {
282  using ChildIteratorType = ::clang::DomTreeNode::const_iterator;
283 
284  static NodeRef getEntryNode(NodeRef N) { return N; }
285  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
286  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
287 
288  using nodes_iterator =
289  llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>;
290 
292  return nodes_iterator(df_begin(getEntryNode(N)));
293  }
294 
296  return nodes_iterator(df_end(getEntryNode(N)));
297  }
298 };
299 
300 template <> struct GraphTraits<clang::CFGDomTree *>
301  : public GraphTraits<clang::DomTreeNode *> {
303  return DT->getRootNode();
304  }
305 
307  return nodes_iterator(df_begin(getEntryNode(N)));
308  }
309 
311  return nodes_iterator(df_end(getEntryNode(N)));
312  }
313 };
314 
315 } // namespace llvm
316 
317 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
llvm
Definition: Dominators.h:30
clang::CFGDominatorTreeImpl::properlyDominates
bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const
Tests whether A properly dominates B.
Definition: Dominators.h:143
Ret
static bool Ret(InterpState &S, CodePtr &PC, APValue &Result)
Definition: Interp.cpp:34
clang::CFGDominatorTreeImpl::isReachableFromEntry
bool isReachableFromEntry(const CFGBlock *A)
Tests whether A is reachable from the entry block.
Definition: Dominators.h:165
AnalysisDeclContext.h
llvm::SmallVector
Definition: LLVM.h:38
clang::CFGDominatorTreeImpl::compare
bool compare(CFGDominatorTreeImpl &Other) const
Compares two dominator trees.
Definition: Dominators.h:73
clang::CFGDominatorTreeImpl::getRootNode
DomTreeNode * getRootNode()
Definition: Dominators.h:66
clang::CFGDominatorTreeImpl::CFGDominatorTreeImpl
CFGDominatorTreeImpl()=default
clang::CFGDominatorTreeImpl::findNearestCommonDominator
const CFGBlock * findNearestCommonDominator(const CFGBlock *A, const CFGBlock *B)
Definition: Dominators.h:153
clang::CFGDominatorTreeImpl::~CFGDominatorTreeImpl
~CFGDominatorTreeImpl() override=default
clang::CFG::end
iterator end()
Definition: CFG.h:1304
llvm::GraphTraits< clang::DomTreeNode * >::nodes_end
static nodes_iterator nodes_end(::clang::DomTreeNode *N)
Definition: Dominators.h:295
llvm::SmallPtrSet
Definition: ASTContext.h:82
clang::CFG
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
Definition: CFG.h:1225
clang::CFGDomTree
CFGDominatorTreeImpl< false > CFGDomTree
Definition: Dominators.h:182
clang::CFGBlock
Represents a single basic block in a source-level CFG.
Definition: CFG.h:576
llvm::IDFCalculatorDetail::ChildrenGetterTy< clang::CFGBlock, IsPostDom >::NodeRef
typename GraphTraits< clang::CFGBlock >::NodeRef NodeRef
Definition: Dominators.h:196
llvm::GraphTraits< clang::CFGDomTree * >::nodes_end
static nodes_iterator nodes_end(clang::CFGDomTree *N)
Definition: Dominators.h:310
clang::ControlDependencyCalculator::dump
LLVM_DUMP_METHOD void dump()
Definition: Dominators.h:254
clang::ManagedAnalysis
The base class of a hierarchy of objects representing analyses tied to AnalysisDeclContext.
Definition: AnalysisDeclContext.h:51
clang::CFGDominatorTreeImpl::buildDominatorTree
void buildDominatorTree(CFG *cfg)
Builds the dominator tree for a given CFG.
Definition: Dominators.h:87
clang::CFGDominatorTreeImpl::findNearestCommonDominator
CFGBlock * findNearestCommonDominator(CFGBlock *A, CFGBlock *B)
Definition: Dominators.h:149
clang::CFGDominatorTreeImpl::getCFG
CFG * getCFG()
Definition: Dominators.h:58
llvm::GraphTraits< clang::DomTreeNode * >::NodeRef
::clang::DomTreeNode * NodeRef
Definition: Dominators.h:281
clang::ControlDependencyCalculator::getControlDependencies
const CFGBlockVector & getControlDependencies(CFGBlock *A)
Definition: Dominators.h:232
clang::CFGDominatorTreeImpl::getRoot
CFGBlock * getRoot() const
Definition: Dominators.h:61
clang::transformer::remove
ASTEdit remove(RangeSelector S)
Removes the source selected by S.
Definition: RewriteRule.cpp:146
clang::ControlDependencyCalculator::ControlDependencyCalculator
ControlDependencyCalculator(CFG *cfg)
Definition: Dominators.h:226
llvm::GraphTraits< clang::DomTreeNode * >::ChildIteratorType
::clang::DomTreeNode::const_iterator ChildIteratorType
Definition: Dominators.h:282
clang::CFGDominatorTreeImpl::dump
void dump()
Dumps immediate dominators for each block.
Definition: Dominators.h:94
clang::CFGDominatorTreeImpl< true >::DominatorTreeBase
llvm::DominatorTreeBase< CFGBlock, IsPostDom > DominatorTreeBase
Definition: Dominators.h:46
GraphTraits
llvm::IDFCalculatorDetail::ChildrenGetterTy< clang::CFGBlock, IsPostDom >::get
ChildrenTy get(const NodeRef &N)
Definition: Dominators.h:199
llvm::GraphTraits< clang::DomTreeNode * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: Dominators.h:286
clang::ControlDependencyCalculator::getCFGPostDomTree
const CFGPostDomTree & getCFGPostDomTree() const
Definition: Dominators.h:229
clang::DomTreeNode
llvm::DomTreeNodeBase< CFGBlock > DomTreeNode
Definition: Dominators.h:38
clang::CFGDominatorTreeImpl::print
virtual void print(raw_ostream &OS, const llvm::Module *M=nullptr) const
Converts the dominator tree to human readable form.
Definition: Dominators.h:173
clang::CFGDominatorTreeImpl::getBase
DominatorTreeBase & getBase()
Definition: Dominators.h:56
clang
Definition: CalledOnceCheck.h:17
CFG.h
llvm::GraphTraits< clang::CFGDomTree * >::getEntryNode
static NodeRef getEntryNode(clang::CFGDomTree *DT)
Definition: Dominators.h:302
llvm::GraphTraits< clang::CFGDomTree * >::nodes_begin
static nodes_iterator nodes_begin(clang::CFGDomTree *N)
Definition: Dominators.h:306
clang::ControlDependencyCalculator
Definition: Dominators.h:215
clang::CFG::begin
iterator begin()
Definition: CFG.h:1303
llvm::GraphTraits< clang::DomTreeNode * >::nodes_begin
static nodes_iterator nodes_begin(::clang::DomTreeNode *N)
Definition: Dominators.h:291
clang::CFGDominatorTreeImpl::releaseMemory
virtual void releaseMemory()
Releases the memory held by the dominator tree.
Definition: Dominators.h:170
clang::CFGDominatorTreeImpl
Dominator tree builder for Clang's CFG based on llvm::DominatorTreeBase.
Definition: Dominators.h:42
clang::CFGDominatorTreeImpl::changeImmediateDominator
void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom)
Update the dominator tree information when a node's immediate dominator changes.
Definition: Dominators.h:160
llvm::GraphTraits< clang::DomTreeNode * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: Dominators.h:285
clang::ControlDependencyCalculator::isControlDependent
bool isControlDependent(CFGBlock *A, CFGBlock *B)
Whether A is control dependent on B.
Definition: Dominators.h:249
llvm::GraphTraits< clang::DomTreeNode * >::getEntryNode
static NodeRef getEntryNode(NodeRef N)
Definition: Dominators.h:284
llvm::GraphTraits< clang::DomTreeNode * >::nodes_iterator
llvm::pointer_iterator< df_iterator<::clang::DomTreeNode * > > nodes_iterator
Definition: Dominators.h:289
clang::CFGDominatorTreeImpl::CFGDominatorTreeImpl
CFGDominatorTreeImpl(CFG *cfg)
Definition: Dominators.h:50
clang::CFGDominatorTreeImpl::dominates
bool dominates(const CFGBlock *A, const CFGBlock *B) const
Tests whether A dominates B.
Definition: Dominators.h:136