Coverage Report

Created: 2018-07-22 10: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
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
// This file implements the dominators tree functionality for Clang CFGs.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
15
#define LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
16
17
#include "clang/Analysis/AnalysisDeclContext.h"
18
#include "clang/Analysis/CFG.h"
19
#include "llvm/ADT/DepthFirstIterator.h"
20
#include "llvm/ADT/GraphTraits.h"
21
#include "llvm/ADT/iterator.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
/// Concrete subclass of DominatorTreeBase for Clang
41
/// This class implements the dominators tree functionality given a Clang CFG.
42
///
43
class DominatorTree : public ManagedAnalysis {
44
  virtual void anchor();
45
46
public:
47
  llvm::DomTreeBase<CFGBlock> *DT;
48
49
5
  DominatorTree() {
50
5
    DT = new llvm::DomTreeBase<CFGBlock>();
51
5
  }
52
53
5
  ~DominatorTree() override { delete DT; }
54
55
0
  llvm::DomTreeBase<CFGBlock>& getBase() { return *DT; }
56
57
  /// This method returns the root CFGBlock of the dominators tree.
58
0
  CFGBlock *getRoot() const {
59
0
    return DT->getRoot();
60
0
  }
61
62
  /// This method returns the root DomTreeNode, which is the wrapper
63
  /// for CFGBlock.
64
0
  DomTreeNode *getRootNode() const {
65
0
    return DT->getRootNode();
66
0
  }
67
68
  /// This method compares two dominator trees.
69
  /// The method returns false if the other dominator tree matches this
70
  /// dominator tree, otherwise returns true.
71
0
  bool compare(DominatorTree &Other) const {
72
0
    DomTreeNode *R = getRootNode();
73
0
    DomTreeNode *OtherR = Other.getRootNode();
74
0
75
0
    if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
76
0
      return true;
77
0
78
0
    if (DT->compare(Other.getBase()))
79
0
      return true;
80
0
81
0
    return false;
82
0
  }
83
84
  /// This method builds the dominator tree for a given CFG
85
  /// The CFG information is passed via AnalysisDeclContext
86
5
  void buildDominatorTree(AnalysisDeclContext &AC) {
87
5
    cfg = AC.getCFG();
88
5
    DT->recalculate(*cfg);
89
5
  }
90
91
  /// This method dumps immediate dominators for each block,
92
  /// mainly used for debug purposes.
93
5
  void dump() {
94
5
    llvm::errs() << "Immediate dominance tree (Node#,IDom#):\n";
95
5
    for (CFG::const_iterator I = cfg->begin(),
96
57
        E = cfg->end(); I != E; 
++I52
) {
97
52
      if(DT->getNode(*I)->getIDom())
98
47
        llvm::errs() << "(" << (*I)->getBlockID()
99
47
                     << ","
100
47
                     << DT->getNode(*I)->getIDom()->getBlock()->getBlockID()
101
47
                     << ")\n";
102
5
      else llvm::errs() << "(" << (*I)->getBlockID()
103
5
                        << "," << (*I)->getBlockID() << ")\n";
104
52
    }
105
5
  }
106
107
  /// This method tests if one CFGBlock dominates the other.
108
  /// The method return true if A dominates B, false otherwise.
109
  /// Note a block always dominates itself.
110
0
  bool dominates(const CFGBlock *A, const CFGBlock *B) const {
111
0
    return DT->dominates(A, B);
112
0
  }
113
114
  /// This method tests if one CFGBlock properly dominates the other.
115
  /// The method return true if A properly dominates B, false otherwise.
116
0
  bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const {
117
0
    return DT->properlyDominates(A, B);
118
0
  }
119
120
  /// This method finds the nearest common dominator CFG block
121
  /// for CFG block A and B. If there is no such block then return NULL.
122
0
  CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) {
123
0
    return DT->findNearestCommonDominator(A, B);
124
0
  }
125
126
  const CFGBlock *findNearestCommonDominator(const CFGBlock *A,
127
0
                                             const CFGBlock *B) {
128
0
    return DT->findNearestCommonDominator(A, B);
129
0
  }
130
131
  /// This method is used to update the dominator
132
  /// tree information when a node's immediate dominator changes.
133
0
  void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) {
134
0
    DT->changeImmediateDominator(N, NewIDom);
135
0
  }
136
137
  /// This method tests if the given CFGBlock can be reachable from root.
138
  /// Returns true if reachable, false otherwise.
139
0
  bool isReachableFromEntry(const CFGBlock *A) {
140
0
    return DT->isReachableFromEntry(A);
141
0
  }
142
143
  /// This method releases the memory held by the dominator tree.
144
0
  virtual void releaseMemory() {
145
0
    DT->releaseMemory();
146
0
  }
147
148
  /// This method converts the dominator tree to human readable form.
149
0
  virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const {
150
0
    DT->print(OS);
151
0
  }
152
153
private:
154
  CFG *cfg;
155
};
156
157
} // namespace clang
158
159
//===-------------------------------------
160
/// DominatorTree GraphTraits specialization so the DominatorTree can be
161
/// iterable by generic graph iterators.
162
///
163
namespace llvm {
164
165
template <> struct GraphTraits< ::clang::DomTreeNode* > {
166
  using NodeRef = ::clang::DomTreeNode *;
167
  using ChildIteratorType = ::clang::DomTreeNode::iterator;
168
169
  static NodeRef getEntryNode(NodeRef N) { return N; }
170
  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
171
  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
172
173
  using nodes_iterator =
174
      llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>;
175
176
  static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {
177
    return nodes_iterator(df_begin(getEntryNode(N)));
178
  }
179
180
  static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
181
    return nodes_iterator(df_end(getEntryNode(N)));
182
  }
183
};
184
185
template <> struct GraphTraits< ::clang::DominatorTree* >
186
    : public GraphTraits< ::clang::DomTreeNode* > {
187
  static NodeRef getEntryNode(::clang::DominatorTree *DT) {
188
    return DT->getRootNode();
189
  }
190
191
  static nodes_iterator nodes_begin(::clang::DominatorTree *N) {
192
    return nodes_iterator(df_begin(getEntryNode(N)));
193
  }
194
195
  static nodes_iterator nodes_end(::clang::DominatorTree *N) {
196
    return nodes_iterator(df_end(getEntryNode(N)));
197
  }
198
};
199
200
} // namespace llvm
201
202
#endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H