Coverage Report

Created: 2020-09-15 12:33

/Users/buildslave/jenkins/workspace/coverage/llvm-project/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 "llvm/ADT/iterator_range.h"
28
#include <memory>
29
30
namespace clang {
31
32
class CallGraphNode;
33
class Decl;
34
class DeclContext;
35
class Stmt;
36
37
/// The AST-based call graph.
38
///
39
/// The call graph extends itself with the given declarations by implementing
40
/// the recursive AST visitor, which constructs the graph by visiting the given
41
/// declarations.
42
class CallGraph : public RecursiveASTVisitor<CallGraph> {
43
  friend class CallGraphNode;
44
45
  using FunctionMapTy =
46
      llvm::DenseMap<const Decl *, std::unique_ptr<CallGraphNode>>;
47
48
  /// FunctionMap owns all CallGraphNodes.
49
  FunctionMapTy FunctionMap;
50
51
  /// This is a virtual root node that has edges to all the functions.
52
  CallGraphNode *Root;
53
54
public:
55
  CallGraph();
56
  ~CallGraph();
57
58
  /// Populate the call graph with the functions in the given
59
  /// declaration.
60
  ///
61
  /// Recursively walks the declaration to find all the dependent Decls as well.
62
33.9k
  void addToCallGraph(Decl *D) {
63
33.9k
    TraverseDecl(D);
64
33.9k
  }
65
66
  /// Determine if a declaration should be included in the graph.
67
  static bool includeInGraph(const Decl *D);
68
69
  /// Determine if a declaration should be included in the graph for the 
70
  /// purposes of being a callee. This is similar to includeInGraph except
71
  /// it permits declarations, not just definitions.
72
  static bool includeCalleeInGraph(const Decl *D);
73
74
  /// Lookup the node for the given declaration.
75
  CallGraphNode *getNode(const Decl *) const;
76
77
  /// Lookup the node for the given declaration. If none found, insert
78
  /// one into the graph.
79
  CallGraphNode *getOrInsertNode(Decl *);
80
81
  using iterator = FunctionMapTy::iterator;
82
  using const_iterator = FunctionMapTy::const_iterator;
83
84
  /// Iterators through all the elements in the graph. Note, this gives
85
  /// non-deterministic order.
86
0
  iterator begin() { return FunctionMap.begin(); }
87
0
  iterator end()   { return FunctionMap.end();   }
88
0
  const_iterator begin() const { return FunctionMap.begin(); }
89
0
  const_iterator end()   const { return FunctionMap.end();   }
90
91
  /// Get the number of nodes in the graph.
92
0
  unsigned size() const { return FunctionMap.size(); }
93
94
  /// \ brief Get the virtual root of the graph, all the functions available
95
  /// externally are represented as callees of the node.
96
1.30k
  CallGraphNode *getRoot() const { return Root; }
97
98
  /// Iterators through all the nodes of the graph that have no parent. These
99
  /// are the unreachable nodes, which are either unused or are due to us
100
  /// failing to add a call edge due to the analysis imprecision.
101
  using nodes_iterator = llvm::SetVector<CallGraphNode *>::iterator;
102
  using const_nodes_iterator = llvm::SetVector<CallGraphNode *>::const_iterator;
103
104
  void print(raw_ostream &os) const;
105
  void dump() const;
106
  void viewGraph() const;
107
108
  void addNodesForBlocks(DeclContext *D);
109
110
  /// Part of recursive declaration visitation. We recursively visit all the
111
  /// declarations to collect the root functions.
112
79.3k
  bool VisitFunctionDecl(FunctionDecl *FD) {
113
    // We skip function template definitions, as their semantics is
114
    // only determined when they are instantiated.
115
79.3k
    if (includeInGraph(FD) && 
FD->isThisDeclarationADefinition()20.4k
) {
116
      // Add all blocks declared inside this function to the graph.
117
20.2k
      addNodesForBlocks(FD);
118
      // If this function has external linkage, anything could call it.
119
      // Note, we are not precise here. For example, the function could have
120
      // its address taken.
121
20.2k
      addNodeForDecl(FD, FD->isGlobal());
122
20.2k
    }
123
79.3k
    return true;
124
79.3k
  }
125
126
  /// Part of recursive declaration visitation.
127
5.72k
  bool VisitObjCMethodDecl(ObjCMethodDecl *MD) {
128
5.72k
    if (includeInGraph(MD)) {
129
1.14k
      addNodesForBlocks(MD);
130
1.14k
      addNodeForDecl(MD, true);
131
1.14k
    }
132
5.72k
    return true;
133
5.72k
  }
134
135
  // We are only collecting the declarations, so do not step into the bodies.
136
58.7k
  bool TraverseStmt(Stmt *S) { return true; }
137
138
359k
  bool shouldWalkTypesOfTypeLocs() const { return false; }
139
15.0k
  bool shouldVisitTemplateInstantiations() const { return true; }
140
286k
  bool shouldVisitImplicitCode() const { return true; }
141
142
private:
143
  /// Add the given declaration to the call graph.
144
  void addNodeForDecl(Decl *D, bool IsGlobal);
145
};
146
147
class CallGraphNode {
148
public:
149
  struct CallRecord {
150
    CallGraphNode *Callee;
151
    Expr *CallExpr;
152
153
    CallRecord() = default;
154
155
    CallRecord(CallGraphNode *Callee_, Expr *CallExpr_)
156
75.9k
        : Callee(Callee_), CallExpr(CallExpr_) {}
157
158
    // The call destination is the only important data here,
159
    // allow to transparently unwrap into it.
160
75.9k
    operator CallGraphNode *() const { return Callee; }
161
  };
162
163
private:
164
  /// The function/method declaration.
165
  Decl *FD;
166
167
  /// The list of functions called from this node.
168
  SmallVector<CallRecord, 5> CalledFunctions;
169
170
public:
171
27.6k
  CallGraphNode(Decl *D) : FD(D) {}
172
173
  using iterator = SmallVectorImpl<CallRecord>::iterator;
174
  using const_iterator = SmallVectorImpl<CallRecord>::const_iterator;
175
176
  /// Iterators through all the callees/children of the node.
177
27.5k
  iterator begin() { return CalledFunctions.begin(); }
178
103k
  iterator end() { return CalledFunctions.end(); }
179
62
  const_iterator begin() const { return CalledFunctions.begin(); }
180
116
  const_iterator end() const { return CalledFunctions.end(); }
181
182
  /// Iterator access to callees/children of the node.
183
0
  llvm::iterator_range<iterator> callees() {
184
0
    return llvm::make_range(begin(), end());
185
0
  }
186
0
  llvm::iterator_range<const_iterator> callees() const {
187
0
    return llvm::make_range(begin(), end());
188
0
  }
189
190
0
  bool empty() const { return CalledFunctions.empty(); }
191
0
  unsigned size() const { return CalledFunctions.size(); }
192
193
75.9k
  void addCallee(CallRecord Call) { CalledFunctions.push_back(Call); }
194
195
27.5k
  Decl *getDecl() const { return FD; }
196
197
0
  FunctionDecl *getDefinition() const {
198
0
    return getDecl()->getAsFunction()->getDefinition();
199
0
  }
200
201
  void print(raw_ostream &os) const;
202
  void dump() const;
203
};
204
205
// NOTE: we are comparing based on the callee only. So different call records
206
// (with different call expressions) to the same callee will compare equal!
207
inline bool operator==(const CallGraphNode::CallRecord &LHS,
208
0
                       const CallGraphNode::CallRecord &RHS) {
209
0
  return LHS.Callee == RHS.Callee;
210
0
}
211
212
} // namespace clang
213
214
namespace llvm {
215
216
// Specialize DenseMapInfo for clang::CallGraphNode::CallRecord.
217
template <> struct DenseMapInfo<clang::CallGraphNode::CallRecord> {
218
0
  static inline clang::CallGraphNode::CallRecord getEmptyKey() {
219
0
    return clang::CallGraphNode::CallRecord(
220
0
        DenseMapInfo<clang::CallGraphNode *>::getEmptyKey(),
221
0
        DenseMapInfo<clang::Expr *>::getEmptyKey());
222
0
  }
223
224
0
  static inline clang::CallGraphNode::CallRecord getTombstoneKey() {
225
0
    return clang::CallGraphNode::CallRecord(
226
0
        DenseMapInfo<clang::CallGraphNode *>::getTombstoneKey(),
227
0
        DenseMapInfo<clang::Expr *>::getTombstoneKey());
228
0
  }
229
230
0
  static unsigned getHashValue(const clang::CallGraphNode::CallRecord &Val) {
231
0
    // NOTE: we are comparing based on the callee only.
232
0
    // Different call records with the same callee will compare equal!
233
0
    return DenseMapInfo<clang::CallGraphNode *>::getHashValue(Val.Callee);
234
0
  }
235
236
  static bool isEqual(const clang::CallGraphNode::CallRecord &LHS,
237
0
                      const clang::CallGraphNode::CallRecord &RHS) {
238
0
    return LHS == RHS;
239
0
  }
240
};
241
242
// Graph traits for iteration, viewing.
243
template <> struct GraphTraits<clang::CallGraphNode*> {
244
  using NodeType = clang::CallGraphNode;
245
  using NodeRef = clang::CallGraphNode *;
246
  using ChildIteratorType = NodeType::iterator;
247
248
1.30k
  static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; }
249
27.5k
  static ChildIteratorType child_begin(NodeType *N) { return N->begin();  }
250
103k
  static ChildIteratorType child_end(NodeType *N) { return N->end(); }
251
};
252
253
template <> struct GraphTraits<const clang::CallGraphNode*> {
254
  using NodeType = const clang::CallGraphNode;
255
  using NodeRef = const clang::CallGraphNode *;
256
  using ChildIteratorType = NodeType::const_iterator;
257
258
2
  static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; }
259
31
  static ChildIteratorType child_begin(NodeType *N) { return N->begin();}
260
85
  static ChildIteratorType child_end(NodeType *N) { return N->end(); }
261
};
262
263
template <> struct GraphTraits<clang::CallGraph*>
264
  : public GraphTraits<clang::CallGraphNode*> {
265
1.30k
  static NodeType *getEntryNode(clang::CallGraph *CGN) {
266
1.30k
    return CGN->getRoot();  // Start at the external node!
267
1.30k
  }
268
269
  static clang::CallGraphNode *
270
0
  CGGetValue(clang::CallGraph::const_iterator::value_type &P) {
271
0
    return P.second.get();
272
0
  }
273
274
  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
275
  using nodes_iterator =
276
      mapped_iterator<clang::CallGraph::iterator, decltype(&CGGetValue)>;
277
278
0
  static nodes_iterator nodes_begin(clang::CallGraph *CG) {
279
0
    return nodes_iterator(CG->begin(), &CGGetValue);
280
0
  }
281
282
0
  static nodes_iterator nodes_end  (clang::CallGraph *CG) {
283
0
    return nodes_iterator(CG->end(), &CGGetValue);
284
0
  }
285
286
0
  static unsigned size(clang::CallGraph *CG) { return CG->size(); }
287
};
288
289
template <> struct GraphTraits<const clang::CallGraph*> :
290
  public GraphTraits<const clang::CallGraphNode*> {
291
2
  static NodeType *getEntryNode(const clang::CallGraph *CGN) {
292
2
    return CGN->getRoot();
293
2
  }
294
295
  static clang::CallGraphNode *
296
0
  CGGetValue(clang::CallGraph::const_iterator::value_type &P) {
297
0
    return P.second.get();
298
0
  }
299
300
  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
301
  using nodes_iterator =
302
      mapped_iterator<clang::CallGraph::const_iterator, decltype(&CGGetValue)>;
303
304
0
  static nodes_iterator nodes_begin(const clang::CallGraph *CG) {
305
0
    return nodes_iterator(CG->begin(), &CGGetValue);
306
0
  }
307
308
0
  static nodes_iterator nodes_end(const clang::CallGraph *CG) {
309
0
    return nodes_iterator(CG->end(), &CGGetValue);
310
0
  }
311
312
0
  static unsigned size(const clang::CallGraph *CG) { return CG->size(); }
313
};
314
315
} // namespace llvm
316
317
#endif // LLVM_CLANG_ANALYSIS_CALLGRAPH_H