1 //===- CallGraph.cpp - AST-based Call graph -------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 //  This file defines the AST-based CallGraph.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "clang/Analysis/CallGraph.h"
15 #include "clang/AST/Decl.h"
16 #include "clang/AST/DeclBase.h"
17 #include "clang/AST/DeclObjC.h"
18 #include "clang/AST/Expr.h"
19 #include "clang/AST/ExprObjC.h"
20 #include "clang/AST/Stmt.h"
21 #include "clang/AST/StmtVisitor.h"
22 #include "clang/Basic/IdentifierTable.h"
23 #include "clang/Basic/LLVM.h"
24 #include "llvm/ADT/PostOrderIterator.h"
25 #include "llvm/ADT/STLExtras.h"
26 #include "llvm/ADT/Statistic.h"
27 #include "llvm/Support/Casting.h"
28 #include "llvm/Support/Compiler.h"
29 #include "llvm/Support/DOTGraphTraits.h"
30 #include "llvm/Support/GraphWriter.h"
31 #include "llvm/Support/raw_ostream.h"
32 #include <cassert>
33 #include <memory>
34 #include <string>
35 
36 using namespace clang;
37 
38 #define DEBUG_TYPE "CallGraph"
39 
40 STATISTIC(NumObjCCallEdges, "Number of Objective-C method call edges");
41 STATISTIC(NumBlockCallEdges, "Number of block call edges");
42 
43 namespace {
44 
45 /// A helper class, which walks the AST and locates all the call sites in the
46 /// given function body.
47 class CGBuilder : public StmtVisitor<CGBuilder> {
48   CallGraph *G;
49   CallGraphNode *CallerNode;
50 
51 public:
52   CGBuilder(CallGraph *g, CallGraphNode *N) : G(g), CallerNode(N) {}
53 
54   void VisitStmt(Stmt *S) { VisitChildren(S); }
55 
56   Decl *getDeclFromCall(CallExpr *CE) {
57     if (FunctionDecl *CalleeDecl = CE->getDirectCallee())
58       return CalleeDecl;
59 
60     // Simple detection of a call through a block.
61     Expr *CEE = CE->getCallee()->IgnoreParenImpCasts();
62     if (BlockExpr *Block = dyn_cast<BlockExpr>(CEE)) {
63       NumBlockCallEdges++;
64       return Block->getBlockDecl();
65     }
66 
67     return nullptr;
68   }
69 
70   void addCalledDecl(Decl *D) {
71     if (G->includeInGraph(D)) {
72       CallGraphNode *CalleeNode = G->getOrInsertNode(D);
73       CallerNode->addCallee(CalleeNode);
74     }
75   }
76 
77   void VisitCallExpr(CallExpr *CE) {
78     if (Decl *D = getDeclFromCall(CE))
79       addCalledDecl(D);
80     VisitChildren(CE);
81   }
82 
83   // Adds may-call edges for the ObjC message sends.
84   void VisitObjCMessageExpr(ObjCMessageExpr *ME) {
85     if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) {
86       Selector Sel = ME->getSelector();
87 
88       // Find the callee definition within the same translation unit.
89       Decl *D = nullptr;
90       if (ME->isInstanceMessage())
91         D = IDecl->lookupPrivateMethod(Sel);
92       else
93         D = IDecl->lookupPrivateClassMethod(Sel);
94       if (D) {
95         addCalledDecl(D);
96         NumObjCCallEdges++;
97       }
98     }
99   }
100 
101   void VisitChildren(Stmt *S) {
102     for (Stmt *SubStmt : S->children())
103       if (SubStmt)
104         this->Visit(SubStmt);
105   }
106 };
107 
108 } // namespace
109 
110 void CallGraph::addNodesForBlocks(DeclContext *D) {
111   if (BlockDecl *BD = dyn_cast<BlockDecl>(D))
112     addNodeForDecl(BD, true);
113 
114   for (auto *I : D->decls())
115     if (auto *DC = dyn_cast<DeclContext>(I))
116       addNodesForBlocks(DC);
117 }
118 
119 CallGraph::CallGraph() {
120   Root = getOrInsertNode(nullptr);
121 }
122 
123 CallGraph::~CallGraph() = default;
124 
125 bool CallGraph::includeInGraph(const Decl *D) {
126   assert(D);
127   if (!D->hasBody())
128     return false;
129 
130   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
131     // We skip function template definitions, as their semantics is
132     // only determined when they are instantiated.
133     if (FD->isDependentContext())
134       return false;
135 
136     IdentifierInfo *II = FD->getIdentifier();
137     if (II && II->getName().startswith("__inline"))
138       return false;
139   }
140 
141   return true;
142 }
143 
144 void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) {
145   assert(D);
146 
147   // Allocate a new node, mark it as root, and process it's calls.
148   CallGraphNode *Node = getOrInsertNode(D);
149 
150   // Process all the calls by this function as well.
151   CGBuilder builder(this, Node);
152   if (Stmt *Body = D->getBody())
153     builder.Visit(Body);
154 }
155 
156 CallGraphNode *CallGraph::getNode(const Decl *F) const {
157   FunctionMapTy::const_iterator I = FunctionMap.find(F);
158   if (I == FunctionMap.end()) return nullptr;
159   return I->second.get();
160 }
161 
162 CallGraphNode *CallGraph::getOrInsertNode(Decl *F) {
163   if (F && !isa<ObjCMethodDecl>(F))
164     F = F->getCanonicalDecl();
165 
166   std::unique_ptr<CallGraphNode> &Node = FunctionMap[F];
167   if (Node)
168     return Node.get();
169 
170   Node = llvm::make_unique<CallGraphNode>(F);
171   // Make Root node a parent of all functions to make sure all are reachable.
172   if (F)
173     Root->addCallee(Node.get());
174   return Node.get();
175 }
176 
177 void CallGraph::print(raw_ostream &OS) const {
178   OS << " --- Call graph Dump --- \n";
179 
180   // We are going to print the graph in reverse post order, partially, to make
181   // sure the output is deterministic.
182   llvm::ReversePostOrderTraversal<const CallGraph *> RPOT(this);
183   for (llvm::ReversePostOrderTraversal<const CallGraph *>::rpo_iterator
184          I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
185     const CallGraphNode *N = *I;
186 
187     OS << "  Function: ";
188     if (N == Root)
189       OS << "< root >";
190     else
191       N->print(OS);
192 
193     OS << " calls: ";
194     for (CallGraphNode::const_iterator CI = N->begin(),
195                                        CE = N->end(); CI != CE; ++CI) {
196       assert(*CI != Root && "No one can call the root node.");
197       (*CI)->print(OS);
198       OS << " ";
199     }
200     OS << '\n';
201   }
202   OS.flush();
203 }
204 
205 LLVM_DUMP_METHOD void CallGraph::dump() const {
206   print(llvm::errs());
207 }
208 
209 void CallGraph::viewGraph() const {
210   llvm::ViewGraph(this, "CallGraph");
211 }
212 
213 void CallGraphNode::print(raw_ostream &os) const {
214   if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(FD))
215       return ND->printName(os);
216   os << "< >";
217 }
218 
219 LLVM_DUMP_METHOD void CallGraphNode::dump() const {
220   print(llvm::errs());
221 }
222 
223 namespace llvm {
224 
225 template <>
226 struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits {
227   DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
228 
229   static std::string getNodeLabel(const CallGraphNode *Node,
230                                   const CallGraph *CG) {
231     if (CG->getRoot() == Node) {
232       return "< root >";
233     }
234     if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Node->getDecl()))
235       return ND->getNameAsString();
236     else
237       return "< >";
238   }
239 };
240 
241 } // namespace llvm
242