clang 19.0.0git
CallGraph.h
Go to the documentation of this file.
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"
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
30namespace clang {
31
32class CallGraphNode;
33class Decl;
34class DeclContext;
35class 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.
42class 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
54public:
55 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.
63 TraverseDecl(D);
64 }
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.
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 iterator begin() { return FunctionMap.begin(); }
87 iterator end() { return FunctionMap.end(); }
88 const_iterator begin() const { return FunctionMap.begin(); }
89 const_iterator end() const { return FunctionMap.end(); }
90
91 /// Get the number of nodes in the graph.
92 unsigned size() const { return FunctionMap.size(); }
93
94 /// Get the virtual root of the graph, all the functions available externally
95 /// are represented as callees of the node.
96 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
109
110 /// Part of recursive declaration visitation. We recursively visit all the
111 /// declarations to collect the root functions.
113 // We skip function template definitions, as their semantics is
114 // only determined when they are instantiated.
116 // Add all blocks declared inside this function to the graph.
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 addNodeForDecl(FD, FD->isGlobal());
122 }
123 return true;
124 }
125
126 /// Part of recursive declaration visitation.
128 if (includeInGraph(MD)) {
130 addNodeForDecl(MD, true);
131 }
132 return true;
133 }
134
135 // We are only collecting the declarations, so do not step into the bodies.
136 bool TraverseStmt(Stmt *S) { return true; }
137
138 bool shouldWalkTypesOfTypeLocs() const { return false; }
139 bool shouldVisitTemplateInstantiations() const { return true; }
140 bool shouldVisitImplicitCode() const { return true; }
141
142private:
143 /// Add the given declaration to the call graph.
144 void addNodeForDecl(Decl *D, bool IsGlobal);
145};
146
148public:
149 struct CallRecord {
152
153 CallRecord() = default;
154
155 CallRecord(CallGraphNode *Callee_, Expr *CallExpr_)
156 : Callee(Callee_), CallExpr(CallExpr_) {}
157
158 // The call destination is the only important data here,
159 // allow to transparently unwrap into it.
160 operator CallGraphNode *() const { return Callee; }
161 };
162
163private:
164 /// The function/method declaration.
165 Decl *FD;
166
167 /// The list of functions called from this node.
168 SmallVector<CallRecord, 5> CalledFunctions;
169
170public:
171 CallGraphNode(Decl *D) : FD(D) {}
172
175
176 /// Iterators through all the callees/children of the node.
177 iterator begin() { return CalledFunctions.begin(); }
178 iterator end() { return CalledFunctions.end(); }
179 const_iterator begin() const { return CalledFunctions.begin(); }
180 const_iterator end() const { return CalledFunctions.end(); }
181
182 /// Iterator access to callees/children of the node.
183 llvm::iterator_range<iterator> callees() {
184 return llvm::make_range(begin(), end());
185 }
186 llvm::iterator_range<const_iterator> callees() const {
187 return llvm::make_range(begin(), end());
188 }
189
190 bool empty() const { return CalledFunctions.empty(); }
191 unsigned size() const { return CalledFunctions.size(); }
192
193 void addCallee(CallRecord Call) { CalledFunctions.push_back(Call); }
194
195 Decl *getDecl() const { return FD; }
196
198 return getDecl()->getAsFunction()->getDefinition();
199 }
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!
208 const CallGraphNode::CallRecord &RHS) {
209 return LHS.Callee == RHS.Callee;
210}
211
212} // namespace clang
213
214namespace llvm {
215
216// Specialize DenseMapInfo for clang::CallGraphNode::CallRecord.
217template <> struct DenseMapInfo<clang::CallGraphNode::CallRecord> {
220 DenseMapInfo<clang::CallGraphNode *>::getEmptyKey(),
221 DenseMapInfo<clang::Expr *>::getEmptyKey());
222 }
223
226 DenseMapInfo<clang::CallGraphNode *>::getTombstoneKey(),
227 DenseMapInfo<clang::Expr *>::getTombstoneKey());
228 }
229
230 static unsigned getHashValue(const clang::CallGraphNode::CallRecord &Val) {
231 // NOTE: we are comparing based on the callee only.
232 // Different call records with the same callee will compare equal!
233 return DenseMapInfo<clang::CallGraphNode *>::getHashValue(Val.Callee);
234 }
235
238 return LHS == RHS;
239 }
240};
241
242// Graph traits for iteration, viewing.
243template <> struct GraphTraits<clang::CallGraphNode*> {
247
248 static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; }
249 static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
250 static ChildIteratorType child_end(NodeType *N) { return N->end(); }
251};
252
253template <> struct GraphTraits<const clang::CallGraphNode*> {
257
258 static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; }
259 static ChildIteratorType child_begin(NodeType *N) { return N->begin();}
260 static ChildIteratorType child_end(NodeType *N) { return N->end(); }
261};
262
263template <> struct GraphTraits<clang::CallGraph*>
264 : public GraphTraits<clang::CallGraphNode*> {
266 return CGN->getRoot(); // Start at the external node!
267 }
268
269 static clang::CallGraphNode *
270 CGGetValue(clang::CallGraph::const_iterator::value_type &P) {
271 return P.second.get();
272 }
273
274 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
276 mapped_iterator<clang::CallGraph::iterator, decltype(&CGGetValue)>;
277
279 return nodes_iterator(CG->begin(), &CGGetValue);
280 }
281
283 return nodes_iterator(CG->end(), &CGGetValue);
284 }
285
286 static unsigned size(clang::CallGraph *CG) { return CG->size(); }
287};
288
289template <> struct GraphTraits<const clang::CallGraph*> :
290 public GraphTraits<const clang::CallGraphNode*> {
292 return CGN->getRoot();
293 }
294
295 static clang::CallGraphNode *
296 CGGetValue(clang::CallGraph::const_iterator::value_type &P) {
297 return P.second.get();
298 }
299
300 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
302 mapped_iterator<clang::CallGraph::const_iterator, decltype(&CGGetValue)>;
303
305 return nodes_iterator(CG->begin(), &CGGetValue);
306 }
307
309 return nodes_iterator(CG->end(), &CGGetValue);
310 }
311
312 static unsigned size(const clang::CallGraph *CG) { return CG->size(); }
313};
314
315} // namespace llvm
316
317#endif // LLVM_CLANG_ANALYSIS_CALLGRAPH_H
StringRef P
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2819
CallGraphNode(Decl *D)
Definition: CallGraph.h:171
SmallVectorImpl< CallRecord >::iterator iterator
Definition: CallGraph.h:173
FunctionDecl * getDefinition() const
Definition: CallGraph.h:197
llvm::iterator_range< const_iterator > callees() const
Definition: CallGraph.h:186
const_iterator begin() const
Definition: CallGraph.h:179
void dump() const
Definition: CallGraph.cpp:260
llvm::iterator_range< iterator > callees()
Iterator access to callees/children of the node.
Definition: CallGraph.h:183
Decl * getDecl() const
Definition: CallGraph.h:195
iterator begin()
Iterators through all the callees/children of the node.
Definition: CallGraph.h:177
void print(raw_ostream &os) const
Definition: CallGraph.cpp:254
bool empty() const
Definition: CallGraph.h:190
const_iterator end() const
Definition: CallGraph.h:180
SmallVectorImpl< CallRecord >::const_iterator const_iterator
Definition: CallGraph.h:174
unsigned size() const
Definition: CallGraph.h:191
void addCallee(CallRecord Call)
Definition: CallGraph.h:193
The AST-based call graph.
Definition: CallGraph.h:42
bool TraverseStmt(Stmt *S)
Definition: CallGraph.h:136
void viewGraph() const
Definition: CallGraph.cpp:250
bool VisitObjCMethodDecl(ObjCMethodDecl *MD)
Part of recursive declaration visitation.
Definition: CallGraph.h:127
const_iterator begin() const
Definition: CallGraph.h:88
iterator end()
Definition: CallGraph.h:87
void addToCallGraph(Decl *D)
Populate the call graph with the functions in the given declaration.
Definition: CallGraph.h:62
CallGraphNode * getNode(const Decl *) const
Lookup the node for the given declaration.
Definition: CallGraph.cpp:197
void dump() const
Definition: CallGraph.cpp:246
bool VisitFunctionDecl(FunctionDecl *FD)
Part of recursive declaration visitation.
Definition: CallGraph.h:112
bool shouldWalkTypesOfTypeLocs() const
Definition: CallGraph.h:138
iterator begin()
Iterators through all the elements in the graph.
Definition: CallGraph.h:86
void addNodesForBlocks(DeclContext *D)
Definition: CallGraph.cpp:140
CallGraphNode * getOrInsertNode(Decl *)
Lookup the node for the given declaration.
Definition: CallGraph.cpp:203
FunctionMapTy::const_iterator const_iterator
Definition: CallGraph.h:82
bool shouldVisitImplicitCode() const
Definition: CallGraph.h:140
bool shouldVisitTemplateInstantiations() const
Definition: CallGraph.h:139
llvm::SetVector< CallGraphNode * >::iterator nodes_iterator
Iterators through all the nodes of the graph that have no parent.
Definition: CallGraph.h:101
FunctionMapTy::iterator iterator
Definition: CallGraph.h:81
llvm::SetVector< CallGraphNode * >::const_iterator const_nodes_iterator
Definition: CallGraph.h:102
void print(raw_ostream &os) const
Definition: CallGraph.cpp:218
static bool includeCalleeInGraph(const Decl *D)
Determine if a declaration should be included in the graph for the purposes of being a callee.
Definition: CallGraph.cpp:163
CallGraphNode * getRoot() const
Get the virtual root of the graph, all the functions available externally are represented as callees ...
Definition: CallGraph.h:96
unsigned size() const
Get the number of nodes in the graph.
Definition: CallGraph.h:92
const_iterator end() const
Definition: CallGraph.h:89
static bool includeInGraph(const Decl *D)
Determine if a declaration should be included in the graph.
Definition: CallGraph.cpp:155
DeclContext - This is used only as base class of specific decl types that can act as declaration cont...
Definition: DeclBase.h:1446
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:85
FunctionDecl * getAsFunction() LLVM_READONLY
Returns the function itself, or the templated function if this is a function template.
Definition: DeclBase.cpp:227
This represents one expression.
Definition: Expr.h:110
Represents a function declaration or definition.
Definition: Decl.h:1959
bool isThisDeclarationADefinition() const
Returns whether this specific declaration of the function is also a definition that does not contain ...
Definition: Decl.h:2258
FunctionDecl * getDefinition()
Get the definition for this declaration.
Definition: Decl.h:2226
bool isGlobal() const
Determines whether this is a global function.
Definition: Decl.cpp:3471
ObjCMethodDecl - Represents an instance or class method declaration.
Definition: DeclObjC.h:140
A class that does preorder or postorder depth-first traversal on the entire Clang AST and visits each...
bool TraverseDecl(Decl *D)
Recursively visit a declaration, by dispatching to Traverse*Decl() based on the argument's dynamic ty...
Stmt - This represents one statement.
Definition: Stmt.h:84
@ Decl
The l-value was an access to a declared entity or something equivalently strong, like the address of ...
The JSON file list parser is used to communicate input to InstallAPI.
bool operator==(const CallGraphNode::CallRecord &LHS, const CallGraphNode::CallRecord &RHS)
Definition: CallGraph.h:207
YAML serialization mapping.
Definition: Dominators.h:30
CallRecord(CallGraphNode *Callee_, Expr *CallExpr_)
Definition: CallGraph.h:155
static clang::CallGraphNode::CallRecord getTombstoneKey()
Definition: CallGraph.h:224
static unsigned getHashValue(const clang::CallGraphNode::CallRecord &Val)
Definition: CallGraph.h:230
static bool isEqual(const clang::CallGraphNode::CallRecord &LHS, const clang::CallGraphNode::CallRecord &RHS)
Definition: CallGraph.h:236
static clang::CallGraphNode::CallRecord getEmptyKey()
Definition: CallGraph.h:218
static ChildIteratorType child_begin(NodeType *N)
Definition: CallGraph.h:249
static NodeType * getEntryNode(clang::CallGraphNode *CGN)
Definition: CallGraph.h:248
static ChildIteratorType child_end(NodeType *N)
Definition: CallGraph.h:250
static clang::CallGraphNode * CGGetValue(clang::CallGraph::const_iterator::value_type &P)
Definition: CallGraph.h:270
static NodeType * getEntryNode(clang::CallGraph *CGN)
Definition: CallGraph.h:265
static nodes_iterator nodes_end(clang::CallGraph *CG)
Definition: CallGraph.h:282
static nodes_iterator nodes_begin(clang::CallGraph *CG)
Definition: CallGraph.h:278
static unsigned size(clang::CallGraph *CG)
Definition: CallGraph.h:286
mapped_iterator< clang::CallGraph::iterator, decltype(&CGGetValue)> nodes_iterator
Definition: CallGraph.h:276
static ChildIteratorType child_begin(NodeType *N)
Definition: CallGraph.h:259
static ChildIteratorType child_end(NodeType *N)
Definition: CallGraph.h:260
static NodeType * getEntryNode(const clang::CallGraphNode *CGN)
Definition: CallGraph.h:258
static nodes_iterator nodes_begin(const clang::CallGraph *CG)
Definition: CallGraph.h:304
static unsigned size(const clang::CallGraph *CG)
Definition: CallGraph.h:312
mapped_iterator< clang::CallGraph::const_iterator, decltype(&CGGetValue)> nodes_iterator
Definition: CallGraph.h:302
static clang::CallGraphNode * CGGetValue(clang::CallGraph::const_iterator::value_type &P)
Definition: CallGraph.h:296
static NodeType * getEntryNode(const clang::CallGraph *CGN)
Definition: CallGraph.h:291
static nodes_iterator nodes_end(const clang::CallGraph *CG)
Definition: CallGraph.h:308