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