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) {
70     if (G->includeInGraph(D)) {
71       CallGraphNode *CalleeNode = G->getOrInsertNode(D);
72       CallerNode->addCallee(CalleeNode);
73     }
74   }
75 
76   void VisitCallExpr(CallExpr *CE) {
77     if (Decl *D = getDeclFromCall(CE))
78       addCalledDecl(D);
79     VisitChildren(CE);
80   }
81 
82   void VisitLambdaExpr(LambdaExpr *LE) {
83     if (CXXMethodDecl *MD = LE->getCallOperator())
84       G->VisitFunctionDecl(MD);
85   }
86 
87   void VisitCXXNewExpr(CXXNewExpr *E) {
88     if (FunctionDecl *FD = E->getOperatorNew())
89       addCalledDecl(FD);
90     VisitChildren(E);
91   }
92 
93   void VisitCXXConstructExpr(CXXConstructExpr *E) {
94     CXXConstructorDecl *Ctor = E->getConstructor();
95     if (FunctionDecl *Def = Ctor->getDefinition())
96       addCalledDecl(Def);
97     VisitChildren(E);
98   }
99 
100   // Include the evaluation of the default argument.
101   void VisitCXXDefaultArgExpr(CXXDefaultArgExpr *E) {
102     Visit(E->getExpr());
103   }
104 
105   // Include the evaluation of the default initializers in a class.
106   void VisitCXXDefaultInitExpr(CXXDefaultInitExpr *E) {
107     Visit(E->getExpr());
108   }
109 
110   // Adds may-call edges for the ObjC message sends.
111   void VisitObjCMessageExpr(ObjCMessageExpr *ME) {
112     if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) {
113       Selector Sel = ME->getSelector();
114 
115       // Find the callee definition within the same translation unit.
116       Decl *D = nullptr;
117       if (ME->isInstanceMessage())
118         D = IDecl->lookupPrivateMethod(Sel);
119       else
120         D = IDecl->lookupPrivateClassMethod(Sel);
121       if (D) {
122         addCalledDecl(D);
123         NumObjCCallEdges++;
124       }
125     }
126   }
127 
128   void VisitChildren(Stmt *S) {
129     for (Stmt *SubStmt : S->children())
130       if (SubStmt)
131         this->Visit(SubStmt);
132   }
133 };
134 
135 } // namespace
136 
137 void CallGraph::addNodesForBlocks(DeclContext *D) {
138   if (BlockDecl *BD = dyn_cast<BlockDecl>(D))
139     addNodeForDecl(BD, true);
140 
141   for (auto *I : D->decls())
142     if (auto *DC = dyn_cast<DeclContext>(I))
143       addNodesForBlocks(DC);
144 }
145 
146 CallGraph::CallGraph() {
147   Root = getOrInsertNode(nullptr);
148 }
149 
150 CallGraph::~CallGraph() = default;
151 
152 bool CallGraph::includeInGraph(const Decl *D) {
153   assert(D);
154   if (!D->hasBody())
155     return false;
156 
157   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
158     // We skip function template definitions, as their semantics is
159     // only determined when they are instantiated.
160     if (FD->isDependentContext())
161       return false;
162 
163     IdentifierInfo *II = FD->getIdentifier();
164     if (II && II->getName().startswith("__inline"))
165       return false;
166   }
167 
168   return true;
169 }
170 
171 void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) {
172   assert(D);
173 
174   // Allocate a new node, mark it as root, and process its calls.
175   CallGraphNode *Node = getOrInsertNode(D);
176 
177   // Process all the calls by this function as well.
178   CGBuilder builder(this, Node);
179   if (Stmt *Body = D->getBody())
180     builder.Visit(Body);
181 
182   // Include C++ constructor member initializers.
183   if (auto constructor = dyn_cast<CXXConstructorDecl>(D)) {
184     for (CXXCtorInitializer *init : constructor->inits()) {
185       builder.Visit(init->getInit());
186     }
187   }
188 }
189 
190 CallGraphNode *CallGraph::getNode(const Decl *F) const {
191   FunctionMapTy::const_iterator I = FunctionMap.find(F);
192   if (I == FunctionMap.end()) return nullptr;
193   return I->second.get();
194 }
195 
196 CallGraphNode *CallGraph::getOrInsertNode(Decl *F) {
197   if (F && !isa<ObjCMethodDecl>(F))
198     F = F->getCanonicalDecl();
199 
200   std::unique_ptr<CallGraphNode> &Node = FunctionMap[F];
201   if (Node)
202     return Node.get();
203 
204   Node = std::make_unique<CallGraphNode>(F);
205   // Make Root node a parent of all functions to make sure all are reachable.
206   if (F)
207     Root->addCallee(Node.get());
208   return Node.get();
209 }
210 
211 void CallGraph::print(raw_ostream &OS) const {
212   OS << " --- Call graph Dump --- \n";
213 
214   // We are going to print the graph in reverse post order, partially, to make
215   // sure the output is deterministic.
216   llvm::ReversePostOrderTraversal<const CallGraph *> RPOT(this);
217   for (llvm::ReversePostOrderTraversal<const CallGraph *>::rpo_iterator
218          I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
219     const CallGraphNode *N = *I;
220 
221     OS << "  Function: ";
222     if (N == Root)
223       OS << "< root >";
224     else
225       N->print(OS);
226 
227     OS << " calls: ";
228     for (CallGraphNode::const_iterator CI = N->begin(),
229                                        CE = N->end(); CI != CE; ++CI) {
230       assert(*CI != Root && "No one can call the root node.");
231       (*CI)->print(OS);
232       OS << " ";
233     }
234     OS << '\n';
235   }
236   OS.flush();
237 }
238 
239 LLVM_DUMP_METHOD void CallGraph::dump() const {
240   print(llvm::errs());
241 }
242 
243 void CallGraph::viewGraph() const {
244   llvm::ViewGraph(this, "CallGraph");
245 }
246 
247 void CallGraphNode::print(raw_ostream &os) const {
248   if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(FD))
249       return ND->printQualifiedName(os);
250   os << "< >";
251 }
252 
253 LLVM_DUMP_METHOD void CallGraphNode::dump() const {
254   print(llvm::errs());
255 }
256 
257 namespace llvm {
258 
259 template <>
260 struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits {
261   DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
262 
263   static std::string getNodeLabel(const CallGraphNode *Node,
264                                   const CallGraph *CG) {
265     if (CG->getRoot() == Node) {
266       return "< root >";
267     }
268     if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Node->getDecl()))
269       return ND->getNameAsString();
270     else
271       return "< >";
272   }
273 };
274 
275 } // namespace llvm
276