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 
13 #include "clang/Analysis/CallGraph.h"
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"
21 #include "clang/Basic/IdentifierTable.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) {
83     if (FunctionTemplateDecl *FTD = LE->getDependentCallOperator())
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) {
97     CXXConstructorDecl *Ctor = E->getConstructor();
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 
140 void CallGraph::addNodesForBlocks(DeclContext *D) {
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 
149 CallGraph::CallGraph() {
150   Root = getOrInsertNode(nullptr);
151 }
152 
153 CallGraph::~CallGraph() = default;
154 
155 bool CallGraph::includeInGraph(const Decl *D) {
156   assert(D);
157   if (!D->hasBody())
158     return false;
159 
160   return includeCalleeInGraph(D);
161 }
162 
163 bool CallGraph::includeCalleeInGraph(const Decl *D) {
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().starts_with("__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 
197 CallGraphNode *CallGraph::getNode(const Decl *F) const {
198   FunctionMapTy::const_iterator I = FunctionMap.find(F);
199   if (I == FunctionMap.end()) return nullptr;
200   return I->second.get();
201 }
202 
203 CallGraphNode *CallGraph::getOrInsertNode(Decl *F) {
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 <>
267 struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits {
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
283