Coverage Report

Created: 2020-11-24 06:42

/Users/buildslave/jenkins/workspace/coverage/llvm-project/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
4.66k
  CFGDominatorTreeImpl(CFG *cfg) {
51
4.66k
    buildDominatorTree(cfg);
52
4.66k
  }
53
54
4.68k
  ~CFGDominatorTreeImpl() override = default;
clang::CFGDominatorTreeImpl<false>::~CFGDominatorTreeImpl()
Line
Count
Source
54
8
  ~CFGDominatorTreeImpl() override = default;
clang::CFGDominatorTreeImpl<true>::~CFGDominatorTreeImpl()
Line
Count
Source
54
4.67k
  ~CFGDominatorTreeImpl() override = default;
55
56
4.66k
  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
4.68k
  void buildDominatorTree(CFG *cfg) {
88
4.68k
    assert(cfg);
89
4.68k
    this->cfg = cfg;
90
4.68k
    DT.recalculate(*cfg);
91
4.68k
  }
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
4.67k
  void buildDominatorTree(CFG *cfg) {
88
4.67k
    assert(cfg);
89
4.67k
    this->cfg = cfg;
90
4.67k
    DT.recalculate(*cfg);
91
4.67k
  }
92
93
  /// Dumps immediate dominators for each block.
94
14
  void dump() {
95
7
    llvm::errs() << "Immediate " << (IsPostDom ? "post " : "")
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
100
124
      assert(*I &&
101
124
             "LLVM's Dominator tree builder uses nullpointers to signify the "
102
124
             "virtual root!");
103
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
114
14
        bool IsDomTreeRoot = !IDom && 
!IsPostDom0
&&
IsEntryBlock7
;
115
14
        bool IsPostDomTreeRoot =
116
14
            IDom && 
!IDom->getBlock()7
&&
IsPostDom0
&&
IsExitBlock7
;
117
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
125
14
        (void)IsDomTreeRoot;
126
14
        (void)IsPostDomTreeRoot;
127
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
100
62
      assert(*I &&
101
62
             "LLVM's Dominator tree builder uses nullpointers to signify the "
102
62
             "virtual root!");
103
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
114
7
        bool IsDomTreeRoot = !IDom && 
!IsPostDom0
&& IsEntryBlock;
115
7
        bool IsPostDomTreeRoot =
116
7
            IDom && 
!IDom->getBlock()0
&&
IsPostDom0
&&
IsExitBlock0
;
117
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
125
7
        (void)IsDomTreeRoot;
126
7
        (void)IsPostDomTreeRoot;
127
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
100
62
      assert(*I &&
101
62
             "LLVM's Dominator tree builder uses nullpointers to signify the "
102
62
             "virtual root!");
103
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
114
7
        bool IsDomTreeRoot = !IDom && 
!IsPostDom0
&&
IsEntryBlock0
;
115
7
        bool IsPostDomTreeRoot =
116
7
            IDom && !IDom->getBlock() && 
IsPostDom0
&& IsExitBlock;
117
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
125
7
        (void)IsDomTreeRoot;
126
7
        (void)IsPostDomTreeRoot;
127
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() { DT.reset(); }
Unexecuted instantiation: clang::CFGDominatorTreeImpl<false>::releaseMemory()
Unexecuted instantiation: clang::CFGDominatorTreeImpl<true>::releaseMemory()
171
172
  /// Converts the dominator tree to human readable form.
173
0
  virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const {
174
0
    DT.print(OS);
175
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
176
177
private:
178
  CFG *cfg;
179
  DominatorTreeBase DT;
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> {
196
  using NodeRef = typename GraphTraits<clang::CFGBlock>::NodeRef;
197
  using ChildrenTy = SmallVector<NodeRef, 8>;
198
199
15.7k
  ChildrenTy get(const NodeRef &N) {
200
15.7k
    using OrderedNodeTy =
201
15.7k
        typename IDFCalculatorBase<clang::CFGBlock, IsPostDom>::OrderedNodeTy;
202
203
15.7k
    auto Children = children<OrderedNodeTy>(N);
204
15.7k
    ChildrenTy Ret{Children.begin(), Children.end()};
205
15.7k
    Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
206
15.7k
    return Ret;
207
15.7k
  }
208
};
209
210
} // end of namespace IDFCalculatorDetail
211
} // end of namespace llvm
212
213
namespace clang {
214
215
class ControlDependencyCalculator : public ManagedAnalysis {
216
  using IDFCalculator = llvm::IDFCalculatorBase<CFGBlock, /*IsPostDom=*/true>;
217
  using CFGBlockVector = llvm::SmallVector<CFGBlock *, 4>;
218
  using CFGBlockSet = llvm::SmallPtrSet<CFGBlock *, 4>;
219
220
  CFGPostDomTree PostDomTree;
221
  IDFCalculator IDFCalc;
222
223
  llvm::DenseMap<CFGBlock *, CFGBlockVector> ControlDepenencyMap;
224
225
public:
226
  ControlDependencyCalculator(CFG *cfg)
227
4.66k
    : PostDomTree(cfg), IDFCalc(PostDomTree.getBase()) {}
228
229
0
  const CFGPostDomTree &getCFGPostDomTree() const { return PostDomTree; }
230
231
  // Lazily retrieves the set of control dependencies to \p A.
232
9.15k
  const CFGBlockVector &getControlDependencies(CFGBlock *A) {
233
9.15k
    auto It = ControlDepenencyMap.find(A);
234
9.15k
    if (It == ControlDepenencyMap.end()) {
235
4.59k
      CFGBlockSet DefiningBlock = {A};
236
4.59k
      IDFCalc.setDefiningBlocks(DefiningBlock);
237
238
4.59k
      CFGBlockVector ControlDependencies;
239
4.59k
      IDFCalc.calculate(ControlDependencies);
240
241
4.59k
      It = ControlDepenencyMap.insert({A, ControlDependencies}).first;
242
4.59k
    }
243
244
9.15k
    assert(It != ControlDepenencyMap.end());
245
9.15k
    return It->second;
246
9.15k
  }
247
248
  /// Whether \p A is control dependent on \p B.
249
9.09k
  bool isControlDependent(CFGBlock *A, CFGBlock *B) {
250
9.09k
    return llvm::is_contained(getControlDependencies(A), B);
251
9.09k
  }
252
253
  // Dumps immediate control dependencies for each block.
254
7
  LLVM_DUMP_METHOD void dump() {
255
7
    CFG *cfg = PostDomTree.getCFG();
256
7
    llvm::errs() << "Control dependencies (Node#,Dependency#):\n";
257
62
    for (CFGBlock *BB : *cfg) {
258
259
62
      assert(BB &&
260
62
             "LLVM's Dominator tree builder uses nullpointers to signify the "
261
62
             "virtual root!");
262
263
62
      for (CFGBlock *isControlDependency : getControlDependencies(BB))
264
68
        llvm::errs() << "(" << BB->getBlockID()
265
68
                     << ","
266
68
                     << isControlDependency->getBlockID()
267
68
                     << ")\n";
268
62
    }
269
7
  }
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 *> {
281
  using NodeRef = ::clang::DomTreeNode *;
282
  using ChildIteratorType = ::clang::DomTreeNode::const_iterator;
283
284
0
  static NodeRef getEntryNode(NodeRef N) { return N; }
285
0
  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
286
0
  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
287
288
  using nodes_iterator =
289
      llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>;
290
291
0
  static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {
292
0
    return nodes_iterator(df_begin(getEntryNode(N)));
293
0
  }
294
295
0
  static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
296
0
    return nodes_iterator(df_end(getEntryNode(N)));
297
0
  }
298
};
299
300
template <> struct GraphTraits<clang::CFGDomTree *>
301
    : public GraphTraits<clang::DomTreeNode *> {
302
0
  static NodeRef getEntryNode(clang::CFGDomTree *DT) {
303
0
    return DT->getRootNode();
304
0
  }
305
306
0
  static nodes_iterator nodes_begin(clang::CFGDomTree *N) {
307
0
    return nodes_iterator(df_begin(getEntryNode(N)));
308
0
  }
309
310
0
  static nodes_iterator nodes_end(clang::CFGDomTree *N) {
311
0
    return nodes_iterator(df_end(getEntryNode(N)));
312
0
  }
313
};
314
315
} // namespace llvm
316
317
#endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H