Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/include/clang/Analysis/Analyses/Dominators.h
Line
Count
Source (jump to first uncovered line)
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
16
#include "clang/Analysis/AnalysisDeclContext.h"
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>
42
class CFGDominatorTreeImpl : public ManagedAnalysis {
43
  virtual void anchor();
44
45
public:
46
  using DominatorTreeBase = llvm::DominatorTreeBase<CFGBlock, IsPostDom>;
47
48
16
  CFGDominatorTreeImpl() = default;
clang::CFGDominatorTreeImpl<false>::CFGDominatorTreeImpl()
Line
Count
Source
48
8
  CFGDominatorTreeImpl() = default;
clang::CFGDominatorTreeImpl<true>::CFGDominatorTreeImpl()
Line
Count
Source
48
8
  CFGDominatorTreeImpl() = default;
49
50
99
  CFGDominatorTreeImpl(CFG *cfg) {
51
99
    buildDominatorTree(cfg);
52
99
  }
53
54
115
  ~CFGDominatorTreeImpl() override = default;
clang::CFGDominatorTreeImpl<false>::~CFGDominatorTreeImpl()
Line
Count
Source
54
8
  ~CFGDominatorTreeImpl() override = default;
clang::CFGDominatorTreeImpl<true>::~CFGDominatorTreeImpl()
Line
Count
Source
54
107
  ~CFGDominatorTreeImpl() override = default;
55
56
99
  DominatorTreeBase &getBase() { return DT; }
57
58
7
  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.
66
0
  DomTreeNode *getRootNode() {
67
0
    return DT.getRootNode();
68
0
  }
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
115
  void buildDominatorTree(CFG *cfg) {
88
115
    assert(cfg);
89
115
    this->cfg = cfg;
90
115
    DT.recalculate(*cfg);
91
115
  }
clang::CFGDominatorTreeImpl<false>::buildDominatorTree(clang::CFG*)
Line
Count
Source
87
8
  void buildDominatorTree(CFG *cfg) {
88
8
    assert(cfg);
89
8
    this->cfg = cfg;
90
8
    DT.recalculate(*cfg);
91
8
  }
clang::CFGDominatorTreeImpl<true>::buildDominatorTree(clang::CFG*)
Line
Count
Source
87
107
  void buildDominatorTree(CFG *cfg) {
88
107
    assert(cfg);
89
107
    this->cfg = cfg;
90
107
    DT.recalculate(*cfg);
91
107
  }
92
93
  /// Dumps immediate dominators for each block.
94
14
  void dump() {
95
14
    llvm::errs() << "Immediate " << (IsPostDom ? 
"post "7
:
""7
)
96
14
                 << "dominance tree (Node#,IDom#):\n";
97
14
    for (CFG::const_iterator I = cfg->begin(),
98
138
        E = cfg->end(); I != E; 
++I124
) {
99
124
100
124
      assert(*I &&
101
124
             "LLVM's Dominator tree builder uses nullpointers to signify the "
102
124
             "virtual root!");
103
124
104
124
      DomTreeNode *IDom = DT.getNode(*I)->getIDom();
105
124
      if (IDom && 
IDom->getBlock()117
)
106
110
        llvm::errs() << "(" << (*I)->getBlockID()
107
110
                     << ","
108
110
                     << IDom->getBlock()->getBlockID()
109
110
                     << ")\n";
110
14
      else {
111
14
        bool IsEntryBlock = *I == &(*I)->getParent()->getEntry();
112
14
        bool IsExitBlock = *I == &(*I)->getParent()->getExit();
113
14
114
14
        bool IsDomTreeRoot = !IDom && 
!IsPostDom0
&&
IsEntryBlock7
;
115
14
        bool IsPostDomTreeRoot =
116
14
            IDom && 
!IDom->getBlock()7
&&
IsPostDom0
&&
IsExitBlock7
;
117
14
118
14
        assert((IsDomTreeRoot || IsPostDomTreeRoot) &&
119
14
               "If the immediate dominator node is nullptr, the CFG block "
120
14
               "should be the exit point (since it's the root of the dominator "
121
14
               "tree), or if the CFG block it refers to is a nullpointer, it "
122
14
               "must be the entry block (since it's the root of the post "
123
14
               "dominator tree)");
124
14
125
14
        (void)IsDomTreeRoot;
126
14
        (void)IsPostDomTreeRoot;
127
14
128
14
        llvm::errs() << "(" << (*I)->getBlockID()
129
14
                     << "," << (*I)->getBlockID() << ")\n";
130
14
      }
131
124
    }
132
14
  }
clang::CFGDominatorTreeImpl<false>::dump()
Line
Count
Source
94
7
  void dump() {
95
7
    llvm::errs() << "Immediate " << (IsPostDom ? 
"post "0
: "")
96
7
                 << "dominance tree (Node#,IDom#):\n";
97
7
    for (CFG::const_iterator I = cfg->begin(),
98
69
        E = cfg->end(); I != E; 
++I62
) {
99
62
100
62
      assert(*I &&
101
62
             "LLVM's Dominator tree builder uses nullpointers to signify the "
102
62
             "virtual root!");
103
62
104
62
      DomTreeNode *IDom = DT.getNode(*I)->getIDom();
105
62
      if (IDom && 
IDom->getBlock()55
)
106
55
        llvm::errs() << "(" << (*I)->getBlockID()
107
55
                     << ","
108
55
                     << IDom->getBlock()->getBlockID()
109
55
                     << ")\n";
110
7
      else {
111
7
        bool IsEntryBlock = *I == &(*I)->getParent()->getEntry();
112
7
        bool IsExitBlock = *I == &(*I)->getParent()->getExit();
113
7
114
7
        bool IsDomTreeRoot = !IDom && 
!IsPostDom0
&& IsEntryBlock;
115
7
        bool IsPostDomTreeRoot =
116
7
            IDom && 
!IDom->getBlock()0
&&
IsPostDom0
&&
IsExitBlock0
;
117
7
118
7
        assert((IsDomTreeRoot || IsPostDomTreeRoot) &&
119
7
               "If the immediate dominator node is nullptr, the CFG block "
120
7
               "should be the exit point (since it's the root of the dominator "
121
7
               "tree), or if the CFG block it refers to is a nullpointer, it "
122
7
               "must be the entry block (since it's the root of the post "
123
7
               "dominator tree)");
124
7
125
7
        (void)IsDomTreeRoot;
126
7
        (void)IsPostDomTreeRoot;
127
7
128
7
        llvm::errs() << "(" << (*I)->getBlockID()
129
7
                     << "," << (*I)->getBlockID() << ")\n";
130
7
      }
131
62
    }
132
7
  }
clang::CFGDominatorTreeImpl<true>::dump()
Line
Count
Source
94
7
  void dump() {
95
7
    llvm::errs() << "Immediate " << (IsPostDom ? "post " : 
""0
)
96
7
                 << "dominance tree (Node#,IDom#):\n";
97
7
    for (CFG::const_iterator I = cfg->begin(),
98
69
        E = cfg->end(); I != E; 
++I62
) {
99
62
100
62
      assert(*I &&
101
62
             "LLVM's Dominator tree builder uses nullpointers to signify the "
102
62
             "virtual root!");
103
62
104
62
      DomTreeNode *IDom = DT.getNode(*I)->getIDom();
105
62
      if (IDom && IDom->getBlock())
106
55
        llvm::errs() << "(" << (*I)->getBlockID()
107
55
                     << ","
108
55
                     << IDom->getBlock()->getBlockID()
109
55
                     << ")\n";
110
7
      else {
111
7
        bool IsEntryBlock = *I == &(*I)->getParent()->getEntry();
112
7
        bool IsExitBlock = *I == &(*I)->getParent()->getExit();
113
7
114
7
        bool IsDomTreeRoot = !IDom && 
!IsPostDom0
&&
IsEntryBlock0
;
115
7
        bool IsPostDomTreeRoot =
116
7
            IDom && !IDom->getBlock() && 
IsPostDom0
&& IsExitBlock;
117
7
118
7
        assert((IsDomTreeRoot || IsPostDomTreeRoot) &&
119
7
               "If the immediate dominator node is nullptr, the CFG block "
120
7
               "should be the exit point (since it's the root of the dominator "
121
7
               "tree), or if the CFG block it refers to is a nullpointer, it "
122
7
               "must be the entry block (since it's the root of the post "
123
7
               "dominator tree)");
124
7
125
7
        (void)IsDomTreeRoot;
126
7
        (void)IsPostDomTreeRoot;
127
7
128
7
        llvm::errs() << "(" << (*I)->getBlockID()
129
7
                     << "," << (*I)->getBlockID() << ")\n";
130
7
      }
131
62
    }
132
7
  }
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.
149
  CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) {
150
    return DT.findNearestCommonDominator(A, B);
151
  }
152
153
  const CFGBlock *findNearestCommonDominator(const CFGBlock *A,
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.
160
  void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) {
161
    DT.changeImmediateDominator(N, NewIDom);
162
  }
163
164
  /// Tests whether \p A is reachable from the entry block.
165
  bool isReachableFromEntry(const CFGBlock *A) {
166
    return DT.isReachableFromEntry(A);
167
  }
168
169
  /// Releases the memory held by the dominator tree.
170
0
  virtual void releaseMemory() {
171
0
    DT.releaseMemory();
172
0
  }
Unexecuted instantiation: clang::CFGDominatorTreeImpl<false>::releaseMemory()
Unexecuted instantiation: clang::CFGDominatorTreeImpl<true>::releaseMemory()
173
174
  /// Converts the dominator tree to human readable form.
175
0
  virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const {
176
0
    DT.print(OS);
177
0
  }
Unexecuted instantiation: clang::CFGDominatorTreeImpl<false>::print(llvm::raw_ostream&, llvm::Module const*) const
Unexecuted instantiation: clang::CFGDominatorTreeImpl<true>::print(llvm::raw_ostream&, llvm::Module const*) const
178
179
private:
180
  CFG *cfg;
181
  DominatorTreeBase DT;
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> {
198
  using NodeRef = typename GraphTraits<clang::CFGBlock>::NodeRef;
199
  using ChildrenTy = SmallVector<NodeRef, 8>;
200
201
646
  ChildrenTy get(const NodeRef &N) {
202
646
    using OrderedNodeTy =
203
646
        typename IDFCalculatorBase<clang::CFGBlock, IsPostDom>::OrderedNodeTy;
204
646
205
646
    auto Children = children<OrderedNodeTy>(N);
206
646
    ChildrenTy Ret{Children.begin(), Children.end()};
207
646
    Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
208
646
    return Ret;
209
646
  }
210
};
211
212
} // end of namespace IDFCalculatorDetail
213
} // end of namespace llvm
214
215
namespace clang {
216
217
class ControlDependencyCalculator : public ManagedAnalysis {
218
  using IDFCalculator = llvm::IDFCalculatorBase<CFGBlock, /*IsPostDom=*/true>;
219
  using CFGBlockVector = llvm::SmallVector<CFGBlock *, 4>;
220
  using CFGBlockSet = llvm::SmallPtrSet<CFGBlock *, 4>;
221
222
  CFGPostDomTree PostDomTree;
223
  IDFCalculator IDFCalc;
224
225
  llvm::DenseMap<CFGBlock *, CFGBlockVector> ControlDepenencyMap;
226
227
public:
228
  ControlDependencyCalculator(CFG *cfg)
229
99
    : PostDomTree(cfg), IDFCalc(PostDomTree.getBase()) {}
230
231
0
  const CFGPostDomTree &getCFGPostDomTree() const { return PostDomTree; }
232
233
  // Lazily retrieves the set of control dependencies to \p A.
234
202
  const CFGBlockVector &getControlDependencies(CFGBlock *A) {
235
202
    auto It = ControlDepenencyMap.find(A);
236
202
    if (It == ControlDepenencyMap.end()) {
237
154
      CFGBlockSet DefiningBlock = {A};
238
154
      IDFCalc.setDefiningBlocks(DefiningBlock);
239
154
240
154
      CFGBlockVector ControlDependencies;
241
154
      IDFCalc.calculate(ControlDependencies);
242
154
243
154
      It = ControlDepenencyMap.insert({A, ControlDependencies}).first;
244
154
    }
245
202
246
202
    assert(It != ControlDepenencyMap.end());
247
202
    return It->second;
248
202
  }
249
250
  /// Whether \p A is control dependent on \p B.
251
140
  bool isControlDependent(CFGBlock *A, CFGBlock *B) {
252
140
    return llvm::is_contained(getControlDependencies(A), B);
253
140
  }
254
255
  // Dumps immediate control dependencies for each block.
256
7
  LLVM_DUMP_METHOD void dump() {
257
7
    CFG *cfg = PostDomTree.getCFG();
258
7
    llvm::errs() << "Control dependencies (Node#,Dependency#):\n";
259
62
    for (CFGBlock *BB : *cfg) {
260
62
261
62
      assert(BB &&
262
62
             "LLVM's Dominator tree builder uses nullpointers to signify the "
263
62
             "virtual root!");
264
62
265
62
      for (CFGBlock *isControlDependency : getControlDependencies(BB))
266
68
        llvm::errs() << "(" << BB->getBlockID()
267
68
                     << ","
268
68
                     << isControlDependency->getBlockID()
269
68
                     << ")\n";
270
62
    }
271
7
  }
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
287
using ClangCFGDomChildrenGetter =
288
SemiNCAInfo<clang::CFGDomTree::DominatorTreeBase>::ChildrenGetter<
289
                                                             /*Inverse=*/false>;
290
291
template <>
292
template <>
293
inline ClangCFGDomChildrenGetter::ResultTy ClangCFGDomChildrenGetter::Get(
294
66
    clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/false>) {
295
66
  auto RChildren = reverse(children<NodePtr>(N));
296
66
  ResultTy Ret(RChildren.begin(), RChildren.end());
297
66
  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
298
66
  return Ret;
299
66
}
300
301
using ClangCFGDomReverseChildrenGetter =
302
SemiNCAInfo<clang::CFGDomTree::DominatorTreeBase>::ChildrenGetter<
303
                                                              /*Inverse=*/true>;
304
305
template <>
306
template <>
307
inline ClangCFGDomReverseChildrenGetter::ResultTy
308
ClangCFGDomReverseChildrenGetter::Get(
309
0
    clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/true>) {
310
0
  auto IChildren = inverse_children<NodePtr>(N);
311
0
  ResultTy Ret(IChildren.begin(), IChildren.end());
312
0
  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
313
0
  return Ret;
314
0
}
315
316
using ClangCFGPostDomChildrenGetter =
317
SemiNCAInfo<clang::CFGPostDomTree::DominatorTreeBase>::ChildrenGetter<
318
                                                             /*Inverse=*/false>;
319
320
template <>
321
template <>
322
inline ClangCFGPostDomChildrenGetter::ResultTy
323
ClangCFGPostDomChildrenGetter::Get(
324
549
    clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/false>) {
325
549
  auto RChildren = reverse(children<NodePtr>(N));
326
549
  ResultTy Ret(RChildren.begin(), RChildren.end());
327
549
  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
328
549
  return Ret;
329
549
}
330
331
using ClangCFGPostDomReverseChildrenGetter =
332
SemiNCAInfo<clang::CFGPostDomTree::DominatorTreeBase>::ChildrenGetter<
333
                                                              /*Inverse=*/true>;
334
335
template <>
336
template <>
337
inline ClangCFGPostDomReverseChildrenGetter::ResultTy
338
ClangCFGPostDomReverseChildrenGetter::Get(
339
1.09k
    clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/true>) {
340
1.09k
  auto IChildren = inverse_children<NodePtr>(N);
341
1.09k
  ResultTy Ret(IChildren.begin(), IChildren.end());
342
1.09k
  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
343
1.09k
  return Ret;
344
1.09k
}
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 *> {
353
  using NodeRef = ::clang::DomTreeNode *;
354
  using ChildIteratorType = ::clang::DomTreeNode::iterator;
355
356
0
  static NodeRef getEntryNode(NodeRef N) { return N; }
357
0
  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
358
0
  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
359
360
  using nodes_iterator =
361
      llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>;
362
363
0
  static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {
364
0
    return nodes_iterator(df_begin(getEntryNode(N)));
365
0
  }
366
367
0
  static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
368
0
    return nodes_iterator(df_end(getEntryNode(N)));
369
0
  }
370
};
371
372
template <> struct GraphTraits<clang::CFGDomTree *>
373
    : public GraphTraits<clang::DomTreeNode *> {
374
0
  static NodeRef getEntryNode(clang::CFGDomTree *DT) {
375
0
    return DT->getRootNode();
376
0
  }
377
378
0
  static nodes_iterator nodes_begin(clang::CFGDomTree *N) {
379
0
    return nodes_iterator(df_begin(getEntryNode(N)));
380
0
  }
381
382
0
  static nodes_iterator nodes_end(clang::CFGDomTree *N) {
383
0
    return nodes_iterator(df_end(getEntryNode(N)));
384
0
  }
385
};
386
387
} // namespace llvm
388
389
#endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H