clang  10.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/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() {
171  DT.releaseMemory();
172  }
173 
174  /// Converts the dominator tree to human readable form.
175  virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const {
176  DT.print(OS);
177  }
178 
179 private:
180  CFG *cfg;
182 };
183 
184 using CFGDomTree = CFGDominatorTreeImpl</*IsPostDom*/ false>;
185 using CFGPostDomTree = CFGDominatorTreeImpl</*IsPostDom*/ true>;
186 
187 template<> void CFGDominatorTreeImpl<true>::anchor();
188 template<> void CFGDominatorTreeImpl<false>::anchor();
189 
190 } // end of namespace clang
191 
192 namespace llvm {
193 namespace IDFCalculatorDetail {
194 
195 /// Specialize ChildrenGetterTy to skip nullpointer successors.
196 template <bool IsPostDom>
197 struct ChildrenGetterTy<clang::CFGBlock, IsPostDom> {
200 
201  ChildrenTy get(const NodeRef &N) {
202  using OrderedNodeTy =
203  typename IDFCalculatorBase<clang::CFGBlock, IsPostDom>::OrderedNodeTy;
204 
205  auto Children = children<OrderedNodeTy>(N);
206  ChildrenTy Ret{Children.begin(), Children.end()};
207  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
208  return Ret;
209  }
210 };
211 
212 } // end of namespace IDFCalculatorDetail
213 } // end of namespace llvm
214 
215 namespace clang {
216 
218  using IDFCalculator = llvm::IDFCalculatorBase<CFGBlock, /*IsPostDom=*/true>;
220  using CFGBlockSet = llvm::SmallPtrSet<CFGBlock *, 4>;
221 
222  CFGPostDomTree PostDomTree;
223  IDFCalculator IDFCalc;
224 
225  llvm::DenseMap<CFGBlock *, CFGBlockVector> ControlDepenencyMap;
226 
227 public:
229  : PostDomTree(cfg), IDFCalc(PostDomTree.getBase()) {}
230 
231  const CFGPostDomTree &getCFGPostDomTree() const { return PostDomTree; }
232 
233  // Lazily retrieves the set of control dependencies to \p A.
235  auto It = ControlDepenencyMap.find(A);
236  if (It == ControlDepenencyMap.end()) {
237  CFGBlockSet DefiningBlock = {A};
238  IDFCalc.setDefiningBlocks(DefiningBlock);
239 
240  CFGBlockVector ControlDependencies;
241  IDFCalc.calculate(ControlDependencies);
242 
243  It = ControlDepenencyMap.insert({A, ControlDependencies}).first;
244  }
245 
246  assert(It != ControlDepenencyMap.end());
247  return It->second;
248  }
249 
250  /// Whether \p A is control dependent on \p B.
251  bool isControlDependent(CFGBlock *A, CFGBlock *B) {
252  return llvm::is_contained(getControlDependencies(A), B);
253  }
254 
255  // Dumps immediate control dependencies for each block.
256  LLVM_DUMP_METHOD void dump() {
257  CFG *cfg = PostDomTree.getCFG();
258  llvm::errs() << "Control dependencies (Node#,Dependency#):\n";
259  for (CFGBlock *BB : *cfg) {
260 
261  assert(BB &&
262  "LLVM's Dominator tree builder uses nullpointers to signify the "
263  "virtual root!");
264 
265  for (CFGBlock *isControlDependency : getControlDependencies(BB))
266  llvm::errs() << "(" << BB->getBlockID()
267  << ","
268  << isControlDependency->getBlockID()
269  << ")\n";
270  }
271  }
272 };
273 
274 } // namespace clang
275 
276 namespace llvm {
277 
278 /// Clang's CFG contains nullpointers for unreachable succesors, e.g. when an
279 /// if statement's condition is always false, it's 'then' branch is represented
280 /// with a nullptr. This however will result in a nullpointer derefernece for
281 /// dominator tree calculation.
282 ///
283 /// To circumvent this, let's just crudely specialize the children getters
284 /// used in LLVM's dominator tree builder.
285 namespace DomTreeBuilder {
286 
288 SemiNCAInfo<clang::CFGDomTree::DominatorTreeBase>::ChildrenGetter<
289  /*Inverse=*/false>;
290 
291 template <>
292 template <>
293 inline ClangCFGDomChildrenGetter::ResultTy ClangCFGDomChildrenGetter::Get(
294  clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/false>) {
295  auto RChildren = reverse(children<NodePtr>(N));
296  ResultTy Ret(RChildren.begin(), RChildren.end());
297  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
298  return Ret;
299 }
300 
302 SemiNCAInfo<clang::CFGDomTree::DominatorTreeBase>::ChildrenGetter<
303  /*Inverse=*/true>;
304 
305 template <>
306 template <>
307 inline ClangCFGDomReverseChildrenGetter::ResultTy
308 ClangCFGDomReverseChildrenGetter::Get(
309  clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/true>) {
310  auto IChildren = inverse_children<NodePtr>(N);
311  ResultTy Ret(IChildren.begin(), IChildren.end());
312  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
313  return Ret;
314 }
315 
317 SemiNCAInfo<clang::CFGPostDomTree::DominatorTreeBase>::ChildrenGetter<
318  /*Inverse=*/false>;
319 
320 template <>
321 template <>
322 inline ClangCFGPostDomChildrenGetter::ResultTy
323 ClangCFGPostDomChildrenGetter::Get(
324  clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/false>) {
325  auto RChildren = reverse(children<NodePtr>(N));
326  ResultTy Ret(RChildren.begin(), RChildren.end());
327  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
328  return Ret;
329 }
330 
332 SemiNCAInfo<clang::CFGPostDomTree::DominatorTreeBase>::ChildrenGetter<
333  /*Inverse=*/true>;
334 
335 template <>
336 template <>
337 inline ClangCFGPostDomReverseChildrenGetter::ResultTy
338 ClangCFGPostDomReverseChildrenGetter::Get(
339  clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/true>) {
340  auto IChildren = inverse_children<NodePtr>(N);
341  ResultTy Ret(IChildren.begin(), IChildren.end());
342  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
343  return Ret;
344 }
345 
346 } // end of namespace DomTreeBuilder
347 
348 //===-------------------------------------
349 /// DominatorTree GraphTraits specialization so the DominatorTree can be
350 /// iterable by generic graph iterators.
351 ///
352 template <> struct GraphTraits<clang::DomTreeNode *> {
354  using ChildIteratorType = ::clang::DomTreeNode::iterator;
355 
356  static NodeRef getEntryNode(NodeRef N) { return N; }
357  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
358  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
359 
360  using nodes_iterator =
361  llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>;
362 
364  return nodes_iterator(df_begin(getEntryNode(N)));
365  }
366 
368  return nodes_iterator(df_end(getEntryNode(N)));
369  }
370 };
371 
372 template <> struct GraphTraits<clang::CFGDomTree *>
373  : public GraphTraits<clang::DomTreeNode *> {
374  static NodeRef getEntryNode(clang::CFGDomTree *DT) {
375  return DT->getRootNode();
376  }
377 
378  static nodes_iterator nodes_begin(clang::CFGDomTree *N) {
379  return nodes_iterator(df_begin(getEntryNode(N)));
380  }
381 
382  static nodes_iterator nodes_end(clang::CFGDomTree *N) {
383  return nodes_iterator(df_end(getEntryNode(N)));
384  }
385 };
386 
387 } // namespace llvm
388 
389 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
::clang::DomTreeNode::iterator ChildIteratorType
Definition: Dominators.h:354
The base class of a hierarchy of objects representing analyses tied to AnalysisDeclContext.
static nodes_iterator nodes_end(::clang::DomTreeNode *N)
Definition: Dominators.h:367
bool isReachableFromEntry(const CFGBlock *A)
Tests whether A is reachable from the entry block.
Definition: Dominators.h:165
Specialize PointerLikeTypeTraits to allow LazyGenerationalUpdatePtr to be placed into a PointerUnion...
Definition: Dominators.h:30
const CFGBlock * findNearestCommonDominator(const CFGBlock *A, const CFGBlock *B)
Definition: Dominators.h:153
CFGDominatorTreeImpl< false > CFGDomTree
Definition: Dominators.h:184
static nodes_iterator nodes_end(clang::CFGDomTree *N)
Definition: Dominators.h:382
bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const
Tests whether A properly dominates B.
Definition: Dominators.h:143
llvm::pointer_iterator< df_iterator<::clang::DomTreeNode * > > nodes_iterator
Definition: Dominators.h:361
DomTreeNode * getRootNode()
Definition: Dominators.h:66
static nodes_iterator nodes_begin(::clang::DomTreeNode *N)
Definition: Dominators.h:363
bool compare(CFGDominatorTreeImpl &Other) const
Compares two dominator trees.
Definition: Dominators.h:73
static ChildIteratorType child_begin(NodeRef N)
Definition: Dominators.h:357
CFGBlockListTy::const_iterator const_iterator
Definition: CFG.h:1294
Represents a single basic block in a source-level CFG.
Definition: CFG.h:576
static ChildIteratorType child_end(NodeRef N)
Definition: Dominators.h:358
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:1225
bool isControlDependent(CFGBlock *A, CFGBlock *B)
Whether A is control dependent on B.
Definition: Dominators.h:251
Dominator tree builder for Clang&#39;s CFG based on llvm::DominatorTreeBase.
Definition: Dominators.h:42
SemiNCAInfo< clang::CFGDomTree::DominatorTreeBase >::ChildrenGetter< false > ClangCFGDomChildrenGetter
Definition: Dominators.h:289
LLVM_DUMP_METHOD void dump()
Definition: Dominators.h:256
void dump()
Dumps immediate dominators for each block.
Definition: Dominators.h:94
ASTEdit remove(RangeSelector S)
Removes the source selected by S.
Definition: RewriteRule.h:218
llvm::DominatorTreeBase< CFGBlock, IsPostDom > DominatorTreeBase
Definition: Dominators.h:46
void buildDominatorTree(CFG *cfg)
Builds the dominator tree for a given CFG.
Definition: Dominators.h:87
CFGBlock * findNearestCommonDominator(CFGBlock *A, CFGBlock *B)
Definition: Dominators.h:149
SemiNCAInfo< clang::CFGDomTree::DominatorTreeBase >::ChildrenGetter< true > ClangCFGDomReverseChildrenGetter
Definition: Dominators.h:303
virtual void print(raw_ostream &OS, const llvm::Module *M=nullptr) const
Converts the dominator tree to human readable form.
Definition: Dominators.h:175
static bool Ret(InterpState &S, CodePtr &PC, APValue &Result)
Definition: Interp.cpp:34
DominatorTreeBase & getBase()
Definition: Dominators.h:56
static NodeRef getEntryNode(NodeRef N)
Definition: Dominators.h:356
CFGBlock * getRoot() const
Definition: Dominators.h:61
Dataflow Directional Tag Classes.
static nodes_iterator nodes_begin(clang::CFGDomTree *N)
Definition: Dominators.h:378
SemiNCAInfo< clang::CFGPostDomTree::DominatorTreeBase >::ChildrenGetter< true > ClangCFGPostDomReverseChildrenGetter
Definition: Dominators.h:333
virtual void releaseMemory()
Releases the memory held by the dominator tree.
Definition: Dominators.h:170
SemiNCAInfo< clang::CFGPostDomTree::DominatorTreeBase >::ChildrenGetter< false > ClangCFGPostDomChildrenGetter
Definition: Dominators.h:318
void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom)
Update the dominator tree information when a node&#39;s immediate dominator changes.
Definition: Dominators.h:160
typename GraphTraits< clang::CFGBlock >::NodeRef NodeRef
Definition: Dominators.h:198
bool dominates(const CFGBlock *A, const CFGBlock *B) const
Tests whether A dominates B.
Definition: Dominators.h:136
const CFGPostDomTree & getCFGPostDomTree() const
Definition: Dominators.h:231
static NodeRef getEntryNode(clang::CFGDomTree *DT)
Definition: Dominators.h:374
const CFGBlockVector & getControlDependencies(CFGBlock *A)
Definition: Dominators.h:234