clang 22.0.0git
CallGraph.cpp
Go to the documentation of this file.
1//===- CallGraph.cpp - AST-based Call graph -------------------------------===//
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 defines the AST-based CallGraph.
10//
11//===----------------------------------------------------------------------===//
12
14#include "clang/AST/Decl.h"
15#include "clang/AST/DeclBase.h"
16#include "clang/AST/DeclObjC.h"
17#include "clang/AST/Expr.h"
18#include "clang/AST/ExprObjC.h"
19#include "clang/AST/Stmt.h"
22#include "clang/Basic/LLVM.h"
23#include "llvm/ADT/PostOrderIterator.h"
24#include "llvm/ADT/Statistic.h"
25#include "llvm/Support/Casting.h"
26#include "llvm/Support/Compiler.h"
27#include "llvm/Support/DOTGraphTraits.h"
28#include "llvm/Support/GraphWriter.h"
29#include "llvm/Support/raw_ostream.h"
30#include <cassert>
31#include <memory>
32#include <string>
33
34using namespace clang;
35
36#define DEBUG_TYPE "CallGraph"
37
38STATISTIC(NumObjCCallEdges, "Number of Objective-C method call edges");
39STATISTIC(NumBlockCallEdges, "Number of block call edges");
40
41namespace {
42
43/// A helper class, which walks the AST and locates all the call sites in the
44/// given function body.
45class CGBuilder : public StmtVisitor<CGBuilder> {
46 CallGraph *G;
47 CallGraphNode *CallerNode;
48
49public:
50 CGBuilder(CallGraph *g, CallGraphNode *N) : G(g), CallerNode(N) {}
51
52 void VisitStmt(Stmt *S) { VisitChildren(S); }
53
54 Decl *getDeclFromCall(CallExpr *CE) {
55 if (FunctionDecl *CalleeDecl = CE->getDirectCallee())
56 return CalleeDecl;
57
58 // Simple detection of a call through a block.
59 Expr *CEE = CE->getCallee()->IgnoreParenImpCasts();
60 if (BlockExpr *Block = dyn_cast<BlockExpr>(CEE)) {
61 NumBlockCallEdges++;
62 return Block->getBlockDecl();
63 }
64
65 return nullptr;
66 }
67
68 void addCalledDecl(Decl *D, Expr *CallExpr) {
69 if (G->includeCalleeInGraph(D)) {
70 CallGraphNode *CalleeNode = G->getOrInsertNode(D);
71 CallerNode->addCallee({CalleeNode, CallExpr});
72 }
73 }
74
75 void VisitCallExpr(CallExpr *CE) {
76 if (Decl *D = getDeclFromCall(CE))
77 addCalledDecl(D, CE);
78 VisitChildren(CE);
79 }
80
81 void VisitLambdaExpr(LambdaExpr *LE) {
82 if (FunctionTemplateDecl *FTD = LE->getDependentCallOperator())
83 for (FunctionDecl *FD : FTD->specializations())
84 G->VisitFunctionDecl(FD);
85 else if (CXXMethodDecl *MD = LE->getCallOperator())
86 G->VisitFunctionDecl(MD);
87 }
88
89 void VisitCXXNewExpr(CXXNewExpr *E) {
90 if (FunctionDecl *FD = E->getOperatorNew())
91 addCalledDecl(FD, E);
92 VisitChildren(E);
93 }
94
95 void VisitCXXConstructExpr(CXXConstructExpr *E) {
96 CXXConstructorDecl *Ctor = E->getConstructor();
97 if (FunctionDecl *Def = Ctor->getDefinition())
98 addCalledDecl(Def, E);
99 VisitChildren(E);
100 }
101
102 // Include the evaluation of the default argument.
103 void VisitCXXDefaultArgExpr(CXXDefaultArgExpr *E) {
104 Visit(E->getExpr());
105 }
106
107 // Include the evaluation of the default initializers in a class.
108 void VisitCXXDefaultInitExpr(CXXDefaultInitExpr *E) {
109 Visit(E->getExpr());
110 }
111
112 // Adds may-call edges for the ObjC message sends.
113 void VisitObjCMessageExpr(ObjCMessageExpr *ME) {
114 if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) {
115 Selector Sel = ME->getSelector();
116
117 // Find the callee definition within the same translation unit.
118 Decl *D = nullptr;
119 if (ME->isInstanceMessage())
120 D = IDecl->lookupPrivateMethod(Sel);
121 else
122 D = IDecl->lookupPrivateClassMethod(Sel);
123 if (D) {
124 addCalledDecl(D, ME);
125 NumObjCCallEdges++;
126 }
127 }
128 }
129
130 void VisitChildren(Stmt *S) {
131 for (Stmt *SubStmt : S->children())
132 if (SubStmt)
133 this->Visit(SubStmt);
134 }
135};
136
137} // namespace
138
140 if (BlockDecl *BD = dyn_cast<BlockDecl>(D))
141 addNodeForDecl(BD, true);
142
143 for (auto *I : D->decls())
144 if (auto *DC = dyn_cast<DeclContext>(I))
146}
147
152 Root = getOrInsertNode(nullptr);
153}
154
155CallGraph::~CallGraph() = default;
156
158 assert(D);
159 if (!D->hasBody())
160 return false;
161
162 return includeCalleeInGraph(D);
163}
164
166 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
167 // We skip function template definitions, as their semantics is
168 // only determined when they are instantiated.
169 if (FD->isDependentContext())
170 return false;
171
172 IdentifierInfo *II = FD->getIdentifier();
173 if (II && II->getName().starts_with("__inline"))
174 return false;
175 }
176
177 return true;
178}
179
180void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) {
181 assert(D);
182
183 // Allocate a new node, mark it as root, and process its calls.
185
186 // Process all the calls by this function as well.
187 CGBuilder builder(this, Node);
188 if (Stmt *Body = D->getBody())
189 builder.Visit(Body);
190
191 // Include C++ constructor member initializers.
192 if (auto constructor = dyn_cast<CXXConstructorDecl>(D)) {
193 for (CXXCtorInitializer *init : constructor->inits()) {
194 builder.Visit(init->getInit());
195 }
196 }
197}
198
200 FunctionMapTy::const_iterator I = FunctionMap.find(F);
201 if (I == FunctionMap.end()) return nullptr;
202 return I->second.get();
203}
204
206 if (F && !isa<ObjCMethodDecl>(F))
207 F = F->getCanonicalDecl();
208
209 std::unique_ptr<CallGraphNode> &Node = FunctionMap[F];
210 if (Node)
211 return Node.get();
212
213 Node = std::make_unique<CallGraphNode>(F);
214 // Make Root node a parent of all functions to make sure all are reachable.
215 if (F)
216 Root->addCallee({Node.get(), /*Call=*/nullptr});
217 return Node.get();
218}
219
220void CallGraph::print(raw_ostream &OS) const {
221 OS << " --- Call graph Dump --- \n";
222
223 // We are going to print the graph in reverse post order, partially, to make
224 // sure the output is deterministic.
225 llvm::ReversePostOrderTraversal<const CallGraph *> RPOT(this);
226 for (const CallGraphNode *N : RPOT) {
227 OS << " Function: ";
228 if (N == Root)
229 OS << "< root >";
230 else
231 N->print(OS);
232
233 OS << " calls: ";
234 for (CallGraphNode::const_iterator CI = N->begin(),
235 CE = N->end(); CI != CE; ++CI) {
236 assert(CI->Callee != Root && "No one can call the root node.");
237 CI->Callee->print(OS);
238 OS << " ";
239 }
240 OS << '\n';
241 }
242 OS.flush();
243}
244
245LLVM_DUMP_METHOD void CallGraph::dump() const {
246 print(llvm::errs());
247}
248
250 llvm::ViewGraph(this, "CallGraph");
251}
252
253void CallGraphNode::print(raw_ostream &os) const {
254 if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(FD))
255 return ND->printQualifiedName(os);
256 os << "< >";
257}
258
259LLVM_DUMP_METHOD void CallGraphNode::dump() const {
260 print(llvm::errs());
261}
262
263namespace llvm {
264
265template <>
266struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits {
267 DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
268
269 static std::string getNodeLabel(const CallGraphNode *Node,
270 const CallGraph *CG) {
271 if (CG->getRoot() == Node) {
272 return "< root >";
273 }
274 if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Node->getDecl()))
275 return ND->getNameAsString();
276 else
277 return "< >";
278 }
279};
280
281} // namespace llvm
DynTypedNode Node
STATISTIC(NumObjCCallEdges, "Number of Objective-C method call edges")
const Decl * D
Expr * E
const CFGBlock * Block
Definition: HTMLLogger.cpp:152
Defines the clang::IdentifierInfo, clang::IdentifierTable, and clang::Selector interfaces.
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified.
Represents a block literal declaration, which is like an unnamed FunctionDecl.
Definition: Decl.h:4634
BlockExpr - Adaptor class for mixing a BlockDecl with expressions.
Definition: Expr.h:6560
Represents a call to a C++ constructor.
Definition: ExprCXX.h:1549
Represents a C++ constructor within a class.
Definition: DeclCXX.h:2604
Represents a C++ base or member initializer.
Definition: DeclCXX.h:2369
A default argument (C++ [dcl.fct.default]).
Definition: ExprCXX.h:1271
A use of a default initializer in a constructor or in aggregate initialization.
Definition: ExprCXX.h:1378
Represents a static or instance method of a struct/union/class.
Definition: DeclCXX.h:2129
Represents a new-expression for memory allocation and constructor calls, e.g: "new CXXNewExpr(foo)".
Definition: ExprCXX.h:2349
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2879
FunctionDecl * getDirectCallee()
If the callee is a FunctionDecl, return it. Otherwise return null.
Definition: Expr.h:3062
Expr * getCallee()
Definition: Expr.h:3026
void dump() const
Definition: CallGraph.cpp:259
void print(raw_ostream &os) const
Definition: CallGraph.cpp:253
SmallVectorImpl< CallRecord >::const_iterator const_iterator
Definition: CallGraph.h:171
void addCallee(CallRecord Call)
Definition: CallGraph.h:190
The AST-based call graph.
Definition: CallGraph.h:43
void viewGraph() const
Definition: CallGraph.cpp:249
CallGraphNode * getNode(const Decl *) const
Lookup the node for the given declaration.
Definition: CallGraph.cpp:199
void dump() const
Definition: CallGraph.cpp:245
void addNodesForBlocks(DeclContext *D)
Definition: CallGraph.cpp:139
bool VisitFunctionDecl(FunctionDecl *FD) override
Part of recursive declaration visitation.
Definition: CallGraph.h:113
CallGraphNode * getOrInsertNode(Decl *)
Lookup the node for the given declaration.
Definition: CallGraph.cpp:205
void print(raw_ostream &os) const
Definition: CallGraph.cpp:220
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:165
CallGraphNode * getRoot() const
Get the virtual root of the graph, all the functions available externally are represented as callees ...
Definition: CallGraph.h:97
static bool includeInGraph(const Decl *D)
Determine if a declaration should be included in the graph.
Definition: CallGraph.cpp:157
DeclContext - This is used only as base class of specific decl types that can act as declaration cont...
Definition: DeclBase.h:1449
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
virtual Stmt * getBody() const
getBody - If this Decl represents a declaration for a body of code, such as a function or method defi...
Definition: DeclBase.h:1087
virtual bool hasBody() const
Returns true if this Decl represents a declaration for a body of code, such as a function or method d...
Definition: DeclBase.h:1093
virtual Decl * getCanonicalDecl()
Retrieves the "canonical" declaration of the given declaration.
Definition: DeclBase.h:978
const T * get() const
Retrieve the stored node as type T.
bool ShouldVisitTemplateInstantiations
Whether this visitor should recurse into template instantiations.
bool ShouldVisitImplicitCode
Whether this visitor should recurse into implicit code, e.g.
bool ShouldWalkTypesOfTypeLocs
Whether this visitor should recurse into the types of TypeLocs.
This represents one expression.
Definition: Expr.h:112
Expr * IgnoreParenImpCasts() LLVM_READONLY
Skip past any parentheses and implicit casts which might surround this expression until reaching a fi...
Definition: Expr.cpp:3073
Represents a function declaration or definition.
Definition: Decl.h:1999
FunctionDecl * getDefinition()
Get the definition for this declaration.
Definition: Decl.h:2281
Declaration of a template function.
Definition: DeclTemplate.h:952
One of these records is kept for each identifier that is lexed.
StringRef getName() const
Return the actual identifier string.
A C++ lambda expression, which produces a function object (of unspecified type) that can be invoked l...
Definition: ExprCXX.h:1970
This represents a decl that may have a name.
Definition: Decl.h:273
Represents an ObjC class declaration.
Definition: DeclObjC.h:1154
An expression that sends a message to the given Objective-C object or class.
Definition: ExprObjC.h:940
Selector getSelector() const
Definition: ExprObjC.cpp:289
bool isInstanceMessage() const
Determine whether this is an instance message to either a computed object or to super.
Definition: ExprObjC.h:1256
ObjCInterfaceDecl * getReceiverInterface() const
Retrieve the Objective-C interface to which this message is being directed, if known.
Definition: ExprObjC.cpp:310
Smart pointer class that efficiently represents Objective-C method names.
RetTy Visit(PTR(Stmt) S, ParamTys... P)
Definition: StmtVisitor.h:45
StmtVisitor - This class implements a simple visitor for Stmt subclasses.
Definition: StmtVisitor.h:186
Stmt - This represents one statement.
Definition: Stmt.h:85
bool LE(InterpState &S, CodePtr OpPC)
Definition: Interp.h:1274
The JSON file list parser is used to communicate input to InstallAPI.
Diagnostic wrappers for TextAPI types for error reporting.
Definition: Dominators.h:30
static std::string getNodeLabel(const CallGraphNode *Node, const CallGraph *CG)
Definition: CallGraph.cpp:269