Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/include/clang/Analysis/CallGraph.h
Line
Count
Source (jump to first uncovered line)
1
//===- CallGraph.h - AST-based Call graph -----------------------*- 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 declares the AST-based CallGraph.
10
//
11
//  A call graph for functions whose definitions/bodies are available in the
12
//  current translation unit. The graph has a "virtual" root node that contains
13
//  edges to all externally available functions.
14
//
15
//===----------------------------------------------------------------------===//
16
17
#ifndef LLVM_CLANG_ANALYSIS_CALLGRAPH_H
18
#define LLVM_CLANG_ANALYSIS_CALLGRAPH_H
19
20
#include "clang/AST/Decl.h"
21
#include "clang/AST/RecursiveASTVisitor.h"
22
#include "llvm/ADT/DenseMap.h"
23
#include "llvm/ADT/GraphTraits.h"
24
#include "llvm/ADT/STLExtras.h"
25
#include "llvm/ADT/SetVector.h"
26
#include "llvm/ADT/SmallVector.h"
27
#include <memory>
28
29
namespace clang {
30
31
class CallGraphNode;
32
class Decl;
33
class DeclContext;
34
class Stmt;
35
36
/// The AST-based call graph.
37
///
38
/// The call graph extends itself with the given declarations by implementing
39
/// the recursive AST visitor, which constructs the graph by visiting the given
40
/// declarations.
41
class CallGraph : public RecursiveASTVisitor<CallGraph> {
42
  friend class CallGraphNode;
43
44
  using FunctionMapTy =
45
      llvm::DenseMap<const Decl *, std::unique_ptr<CallGraphNode>>;
46
47
  /// FunctionMap owns all CallGraphNodes.
48
  FunctionMapTy FunctionMap;
49
50
  /// This is a virtual root node that has edges to all the functions.
51
  CallGraphNode *Root;
52
53
public:
54
  CallGraph();
55
  ~CallGraph();
56
57
  /// Populate the call graph with the functions in the given
58
  /// declaration.
59
  ///
60
  /// Recursively walks the declaration to find all the dependent Decls as well.
61
27.1k
  void addToCallGraph(Decl *D) {
62
27.1k
    TraverseDecl(D);
63
27.1k
  }
64
65
  /// Determine if a declaration should be included in the graph.
66
  static bool includeInGraph(const Decl *D);
67
68
  /// Lookup the node for the given declaration.
69
  CallGraphNode *getNode(const Decl *) const;
70
71
  /// Lookup the node for the given declaration. If none found, insert
72
  /// one into the graph.
73
  CallGraphNode *getOrInsertNode(Decl *);
74
75
  using iterator = FunctionMapTy::iterator;
76
  using const_iterator = FunctionMapTy::const_iterator;
77
78
  /// Iterators through all the elements in the graph. Note, this gives
79
  /// non-deterministic order.
80
0
  iterator begin() { return FunctionMap.begin(); }
81
0
  iterator end()   { return FunctionMap.end();   }
82
0
  const_iterator begin() const { return FunctionMap.begin(); }
83
0
  const_iterator end()   const { return FunctionMap.end();   }
84
85
  /// Get the number of nodes in the graph.
86
0
  unsigned size() const { return FunctionMap.size(); }
87
88
  /// \ brief Get the virtual root of the graph, all the functions available
89
  /// externally are represented as callees of the node.
90
883
  CallGraphNode *getRoot() const { return Root; }
91
92
  /// Iterators through all the nodes of the graph that have no parent. These
93
  /// are the unreachable nodes, which are either unused or are due to us
94
  /// failing to add a call edge due to the analysis imprecision.
95
  using nodes_iterator = llvm::SetVector<CallGraphNode *>::iterator;
96
  using const_nodes_iterator = llvm::SetVector<CallGraphNode *>::const_iterator;
97
98
  void print(raw_ostream &os) const;
99
  void dump() const;
100
  void viewGraph() const;
101
102
  void addNodesForBlocks(DeclContext *D);
103
104
  /// Part of recursive declaration visitation. We recursively visit all the
105
  /// declarations to collect the root functions.
106
51.5k
  bool VisitFunctionDecl(FunctionDecl *FD) {
107
51.5k
    // We skip function template definitions, as their semantics is
108
51.5k
    // only determined when they are instantiated.
109
51.5k
    if (includeInGraph(FD) && 
FD->isThisDeclarationADefinition()15.4k
) {
110
15.2k
      // Add all blocks declared inside this function to the graph.
111
15.2k
      addNodesForBlocks(FD);
112
15.2k
      // If this function has external linkage, anything could call it.
113
15.2k
      // Note, we are not precise here. For example, the function could have
114
15.2k
      // its address taken.
115
15.2k
      addNodeForDecl(FD, FD->isGlobal());
116
15.2k
    }
117
51.5k
    return true;
118
51.5k
  }
119
120
  /// Part of recursive declaration visitation.
121
4.16k
  bool VisitObjCMethodDecl(ObjCMethodDecl *MD) {
122
4.16k
    if (includeInGraph(MD)) {
123
1.11k
      addNodesForBlocks(MD);
124
1.11k
      addNodeForDecl(MD, true);
125
1.11k
    }
126
4.16k
    return true;
127
4.16k
  }
128
129
  // We are only collecting the declarations, so do not step into the bodies.
130
40.8k
  bool TraverseStmt(Stmt *S) { return true; }
131
132
250k
  bool shouldWalkTypesOfTypeLocs() const { return false; }
133
8.90k
  bool shouldVisitTemplateInstantiations() const { return true; }
134
135
private:
136
  /// Add the given declaration to the call graph.
137
  void addNodeForDecl(Decl *D, bool IsGlobal);
138
139
  /// Allocate a new node in the graph.
140
  CallGraphNode *allocateNewNode(Decl *);
141
};
142
143
class CallGraphNode {
144
public:
145
  using CallRecord = CallGraphNode *;
146
147
private:
148
  /// The function/method declaration.
149
  Decl *FD;
150
151
  /// The list of functions called from this node.
152
  SmallVector<CallRecord, 5> CalledFunctions;
153
154
public:
155
17.0k
  CallGraphNode(Decl *D) : FD(D) {}
156
157
  using iterator = SmallVectorImpl<CallRecord>::iterator;
158
  using const_iterator = SmallVectorImpl<CallRecord>::const_iterator;
159
160
  /// Iterators through all the callees/children of the node.
161
17.0k
  iterator begin() { return CalledFunctions.begin(); }
162
39.4k
  iterator end() { return CalledFunctions.end(); }
163
36
  const_iterator begin() const { return CalledFunctions.begin(); }
164
66
  const_iterator end() const { return CalledFunctions.end(); }
165
166
0
  bool empty() const { return CalledFunctions.empty(); }
167
0
  unsigned size() const { return CalledFunctions.size(); }
168
169
22.3k
  void addCallee(CallGraphNode *N) {
170
22.3k
    CalledFunctions.push_back(N);
171
22.3k
  }
172
173
17.0k
  Decl *getDecl() const { return FD; }
174
175
  void print(raw_ostream &os) const;
176
  void dump() const;
177
};
178
179
} // namespace clang
180
181
// Graph traits for iteration, viewing.
182
namespace llvm {
183
184
template <> struct GraphTraits<clang::CallGraphNode*> {
185
  using NodeType = clang::CallGraphNode;
186
  using NodeRef = clang::CallGraphNode *;
187
  using ChildIteratorType = NodeType::iterator;
188
189
882
  static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; }
190
17.0k
  static ChildIteratorType child_begin(NodeType *N) { return N->begin();  }
191
39.4k
  static ChildIteratorType child_end(NodeType *N) { return N->end(); }
192
};
193
194
template <> struct GraphTraits<const clang::CallGraphNode*> {
195
  using NodeType = const clang::CallGraphNode;
196
  using NodeRef = const clang::CallGraphNode *;
197
  using ChildIteratorType = NodeType::const_iterator;
198
199
1
  static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; }
200
18
  static ChildIteratorType child_begin(NodeType *N) { return N->begin();}
201
48
  static ChildIteratorType child_end(NodeType *N) { return N->end(); }
202
};
203
204
template <> struct GraphTraits<clang::CallGraph*>
205
  : public GraphTraits<clang::CallGraphNode*> {
206
882
  static NodeType *getEntryNode(clang::CallGraph *CGN) {
207
882
    return CGN->getRoot();  // Start at the external node!
208
882
  }
209
210
  static clang::CallGraphNode *
211
0
  CGGetValue(clang::CallGraph::const_iterator::value_type &P) {
212
0
    return P.second.get();
213
0
  }
214
215
  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
216
  using nodes_iterator =
217
      mapped_iterator<clang::CallGraph::iterator, decltype(&CGGetValue)>;
218
219
0
  static nodes_iterator nodes_begin(clang::CallGraph *CG) {
220
0
    return nodes_iterator(CG->begin(), &CGGetValue);
221
0
  }
222
223
0
  static nodes_iterator nodes_end  (clang::CallGraph *CG) {
224
0
    return nodes_iterator(CG->end(), &CGGetValue);
225
0
  }
226
227
0
  static unsigned size(clang::CallGraph *CG) { return CG->size(); }
228
};
229
230
template <> struct GraphTraits<const clang::CallGraph*> :
231
  public GraphTraits<const clang::CallGraphNode*> {
232
1
  static NodeType *getEntryNode(const clang::CallGraph *CGN) {
233
1
    return CGN->getRoot();
234
1
  }
235
236
  static clang::CallGraphNode *
237
0
  CGGetValue(clang::CallGraph::const_iterator::value_type &P) {
238
0
    return P.second.get();
239
0
  }
240
241
  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
242
  using nodes_iterator =
243
      mapped_iterator<clang::CallGraph::const_iterator, decltype(&CGGetValue)>;
244
245
0
  static nodes_iterator nodes_begin(const clang::CallGraph *CG) {
246
0
    return nodes_iterator(CG->begin(), &CGGetValue);
247
0
  }
248
249
0
  static nodes_iterator nodes_end(const clang::CallGraph *CG) {
250
0
    return nodes_iterator(CG->end(), &CGGetValue);
251
0
  }
252
253
0
  static unsigned size(const clang::CallGraph *CG) { return CG->size(); }
254
};
255
256
} // namespace llvm
257
258
#endif // LLVM_CLANG_ANALYSIS_CALLGRAPH_H