Coverage Report

Created: 2019-02-21 13:17

/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/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
///
42
class DominatorTree : public ManagedAnalysis {
43
  virtual void anchor();
44
45
public:
46
  llvm::DomTreeBase<CFGBlock> *DT;
47
48
5
  DominatorTree() {
49
5
    DT = new llvm::DomTreeBase<CFGBlock>();
50
5
  }
51
52
5
  ~DominatorTree() override { delete DT; }
53
54
0
  llvm::DomTreeBase<CFGBlock>& getBase() { return *DT; }
55
56
  /// This method returns the root CFGBlock of the dominators tree.
57
0
  CFGBlock *getRoot() const {
58
0
    return DT->getRoot();
59
0
  }
60
61
  /// This method returns the root DomTreeNode, which is the wrapper
62
  /// for CFGBlock.
63
0
  DomTreeNode *getRootNode() const {
64
0
    return DT->getRootNode();
65
0
  }
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
0
  bool compare(DominatorTree &Other) const {
71
0
    DomTreeNode *R = getRootNode();
72
0
    DomTreeNode *OtherR = Other.getRootNode();
73
0
74
0
    if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
75
0
      return true;
76
0
77
0
    if (DT->compare(Other.getBase()))
78
0
      return true;
79
0
80
0
    return false;
81
0
  }
82
83
  /// This method builds the dominator tree for a given CFG
84
  /// The CFG information is passed via AnalysisDeclContext
85
5
  void buildDominatorTree(AnalysisDeclContext &AC) {
86
5
    cfg = AC.getCFG();
87
5
    DT->recalculate(*cfg);
88
5
  }
89
90
  /// This method dumps immediate dominators for each block,
91
  /// mainly used for debug purposes.
92
5
  void dump() {
93
5
    llvm::errs() << "Immediate dominance tree (Node#,IDom#):\n";
94
5
    for (CFG::const_iterator I = cfg->begin(),
95
57
        E = cfg->end(); I != E; 
++I52
) {
96
52
      if(DT->getNode(*I)->getIDom())
97
47
        llvm::errs() << "(" << (*I)->getBlockID()
98
47
                     << ","
99
47
                     << DT->getNode(*I)->getIDom()->getBlock()->getBlockID()
100
47
                     << ")\n";
101
5
      else llvm::errs() << "(" << (*I)->getBlockID()
102
5
                        << "," << (*I)->getBlockID() << ")\n";
103
52
    }
104
5
  }
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
0
  bool dominates(const CFGBlock *A, const CFGBlock *B) const {
110
0
    return DT->dominates(A, B);
111
0
  }
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
0
  bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const {
116
0
    return DT->properlyDominates(A, B);
117
0
  }
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.
121
0
  CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) {
122
0
    return DT->findNearestCommonDominator(A, B);
123
0
  }
124
125
  const CFGBlock *findNearestCommonDominator(const CFGBlock *A,
126
0
                                             const CFGBlock *B) {
127
0
    return DT->findNearestCommonDominator(A, B);
128
0
  }
129
130
  /// This method is used to update the dominator
131
  /// tree information when a node's immediate dominator changes.
132
0
  void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) {
133
0
    DT->changeImmediateDominator(N, NewIDom);
134
0
  }
135
136
  /// This method tests if the given CFGBlock can be reachable from root.
137
  /// Returns true if reachable, false otherwise.
138
0
  bool isReachableFromEntry(const CFGBlock *A) {
139
0
    return DT->isReachableFromEntry(A);
140
0
  }
141
142
  /// This method releases the memory held by the dominator tree.
143
0
  virtual void releaseMemory() {
144
0
    DT->releaseMemory();
145
0
  }
146
147
  /// This method converts the dominator tree to human readable form.
148
0
  virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const {
149
0
    DT->print(OS);
150
0
  }
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* > {
165
  using NodeRef = ::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
175
  static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {
176
    return nodes_iterator(df_begin(getEntryNode(N)));
177
  }
178
179
  static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
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