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 #define DEBUG_TYPE "CallGraph"
14 
15 #include "clang/Analysis/CallGraph.h"
16 #include "clang/AST/ASTContext.h"
17 #include "clang/AST/Decl.h"
18 #include "clang/AST/StmtVisitor.h"
19 #include "llvm/ADT/PostOrderIterator.h"
20 #include "llvm/ADT/Statistic.h"
21 #include "llvm/Support/GraphWriter.h"
22 
23 using namespace clang;
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:
36   CGBuilder(CallGraph *g, CallGraphNode *N)
37     : G(g), CallerNode(N) {}
38 
39   void VisitStmt(Stmt *S) { VisitChildren(S); }
40 
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 0;
53   }
54 
55   void addCalledDecl(Decl *D) {
56     if (G->includeInGraph(D)) {
57       CallGraphNode *CalleeNode = G->getOrInsertNode(D);
58       CallerNode->addCallee(CalleeNode, G);
59     }
60   }
61 
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.
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 = 0;
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 
85   void VisitChildren(Stmt *S) {
86     for (Stmt::child_range I = S->children(); I; ++I)
87       if (*I)
88         static_cast<CGBuilder*>(this)->Visit(*I);
89   }
90 };
91 
92 } // end anonymous namespace
93 
94 void CallGraph::addNodesForBlocks(DeclContext *D) {
95   if (BlockDecl *BD = dyn_cast<BlockDecl>(D))
96     addNodeForDecl(BD, true);
97 
98   for (DeclContext::decl_iterator I = D->decls_begin(), E = D->decls_end();
99        I!=E; ++I)
100     if (DeclContext *DC = dyn_cast<DeclContext>(*I))
101       addNodesForBlocks(DC);
102 }
103 
104 CallGraph::CallGraph() {
105   Root = getOrInsertNode(0);
106 }
107 
108 CallGraph::~CallGraph() {
109   llvm::DeleteContainerSeconds(FunctionMap);
110 }
111 
112 bool CallGraph::includeInGraph(const Decl *D) {
113   assert(D);
114   if (!D->getBody())
115     return false;
116 
117   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
118     // We skip function template definitions, as their semantics is
119     // only determined when they are instantiated.
120     if (!FD->isThisDeclarationADefinition() ||
121         FD->isDependentContext())
122       return false;
123 
124     IdentifierInfo *II = FD->getIdentifier();
125     if (II && II->getName().startswith("__inline"))
126       return false;
127   }
128 
129   if (const ObjCMethodDecl *ID = dyn_cast<ObjCMethodDecl>(D)) {
130     if (!ID->isThisDeclarationADefinition())
131       return false;
132   }
133 
134   return true;
135 }
136 
137 void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) {
138   assert(D);
139 
140   // Allocate a new node, mark it as root, and process it's calls.
141   CallGraphNode *Node = getOrInsertNode(D);
142 
143   // Process all the calls by this function as well.
144   CGBuilder builder(this, Node);
145   if (Stmt *Body = D->getBody())
146     builder.Visit(Body);
147 }
148 
149 CallGraphNode *CallGraph::getNode(const Decl *F) const {
150   FunctionMapTy::const_iterator I = FunctionMap.find(F);
151   if (I == FunctionMap.end()) return 0;
152   return I->second;
153 }
154 
155 CallGraphNode *CallGraph::getOrInsertNode(Decl *F) {
156   CallGraphNode *&Node = FunctionMap[F];
157   if (Node)
158     return Node;
159 
160   Node = new CallGraphNode(F);
161   // Make Root node a parent of all functions to make sure all are reachable.
162   if (F != 0)
163     Root->addCallee(Node, this);
164   return Node;
165 }
166 
167 void CallGraph::print(raw_ostream &OS) const {
168   OS << " --- Call graph Dump --- \n";
169 
170   // We are going to print the graph in reverse post order, partially, to make
171   // sure the output is deterministic.
172   llvm::ReversePostOrderTraversal<const clang::CallGraph*> RPOT(this);
173   for (llvm::ReversePostOrderTraversal<const clang::CallGraph*>::rpo_iterator
174          I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
175     const CallGraphNode *N = *I;
176 
177     OS << "  Function: ";
178     if (N == Root)
179       OS << "< root >";
180     else
181       N->print(OS);
182 
183     OS << " calls: ";
184     for (CallGraphNode::const_iterator CI = N->begin(),
185                                        CE = N->end(); CI != CE; ++CI) {
186       assert(*CI != Root && "No one can call the root node.");
187       (*CI)->print(OS);
188       OS << " ";
189     }
190     OS << '\n';
191   }
192   OS.flush();
193 }
194 
195 void CallGraph::dump() const {
196   print(llvm::errs());
197 }
198 
199 void CallGraph::viewGraph() const {
200   llvm::ViewGraph(this, "CallGraph");
201 }
202 
203 void CallGraphNode::print(raw_ostream &os) const {
204   if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(FD))
205       return ND->printName(os);
206   os << "< >";
207 }
208 
209 void CallGraphNode::dump() const {
210   print(llvm::errs());
211 }
212 
213 namespace llvm {
214 
215 template <>
216 struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits {
217 
218   DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
219 
220   static std::string getNodeLabel(const CallGraphNode *Node,
221                                   const CallGraph *CG) {
222     if (CG->getRoot() == Node) {
223       return "< root >";
224     }
225     if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Node->getDecl()))
226       return ND->getNameAsString();
227     else
228       return "< >";
229   }
230 
231 };
232 }
233