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