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:
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 nullptr;
53   }
54 
55   void addCalledDecl(Decl *D) {
56     if (G->includeInGraph(D)) {
57       CallGraphNode *CalleeNode = G->getOrInsertNode(D);
58       CallerNode->addCallee(CalleeNode);
59     }
60   }
61 
62   void VisitCallExpr(CallExpr *CE) {
63     if (Decl *D = getDeclFromCall(CE))
64       addCalledDecl(D);
65     VisitChildren(CE);
66   }
67 
68   // Adds may-call edges for the ObjC message sends.
69   void VisitObjCMessageExpr(ObjCMessageExpr *ME) {
70     if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) {
71       Selector Sel = ME->getSelector();
72 
73       // Find the callee definition within the same translation unit.
74       Decl *D = nullptr;
75       if (ME->isInstanceMessage())
76         D = IDecl->lookupPrivateMethod(Sel);
77       else
78         D = IDecl->lookupPrivateClassMethod(Sel);
79       if (D) {
80         addCalledDecl(D);
81         NumObjCCallEdges++;
82       }
83     }
84   }
85 
86   void VisitChildren(Stmt *S) {
87     for (Stmt *SubStmt : S->children())
88       if (SubStmt)
89         this->Visit(SubStmt);
90   }
91 };
92 
93 } // end anonymous namespace
94 
95 void CallGraph::addNodesForBlocks(DeclContext *D) {
96   if (BlockDecl *BD = dyn_cast<BlockDecl>(D))
97     addNodeForDecl(BD, true);
98 
99   for (auto *I : D->decls())
100     if (auto *DC = dyn_cast<DeclContext>(I))
101       addNodesForBlocks(DC);
102 }
103 
104 CallGraph::CallGraph() {
105   Root = getOrInsertNode(nullptr);
106 }
107 
108 CallGraph::~CallGraph() {}
109 
110 bool CallGraph::includeInGraph(const Decl *D) {
111   assert(D);
112   if (!D->hasBody())
113     return false;
114 
115   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
116     // We skip function template definitions, as their semantics is
117     // only determined when they are instantiated.
118     if (FD->isDependentContext())
119       return false;
120 
121     IdentifierInfo *II = FD->getIdentifier();
122     if (II && II->getName().startswith("__inline"))
123       return false;
124   }
125 
126   return true;
127 }
128 
129 void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) {
130   assert(D);
131 
132   // Allocate a new node, mark it as root, and process it's calls.
133   CallGraphNode *Node = getOrInsertNode(D);
134 
135   // Process all the calls by this function as well.
136   CGBuilder builder(this, Node);
137   if (Stmt *Body = D->getBody())
138     builder.Visit(Body);
139 }
140 
141 CallGraphNode *CallGraph::getNode(const Decl *F) const {
142   FunctionMapTy::const_iterator I = FunctionMap.find(F);
143   if (I == FunctionMap.end()) return nullptr;
144   return I->second.get();
145 }
146 
147 CallGraphNode *CallGraph::getOrInsertNode(Decl *F) {
148   if (F && !isa<ObjCMethodDecl>(F))
149     F = F->getCanonicalDecl();
150 
151   std::unique_ptr<CallGraphNode> &Node = FunctionMap[F];
152   if (Node)
153     return Node.get();
154 
155   Node = llvm::make_unique<CallGraphNode>(F);
156   // Make Root node a parent of all functions to make sure all are reachable.
157   if (F)
158     Root->addCallee(Node.get());
159   return Node.get();
160 }
161 
162 void CallGraph::print(raw_ostream &OS) const {
163   OS << " --- Call graph Dump --- \n";
164 
165   // We are going to print the graph in reverse post order, partially, to make
166   // sure the output is deterministic.
167   llvm::ReversePostOrderTraversal<const clang::CallGraph*> RPOT(this);
168   for (llvm::ReversePostOrderTraversal<const clang::CallGraph*>::rpo_iterator
169          I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
170     const CallGraphNode *N = *I;
171 
172     OS << "  Function: ";
173     if (N == Root)
174       OS << "< root >";
175     else
176       N->print(OS);
177 
178     OS << " calls: ";
179     for (CallGraphNode::const_iterator CI = N->begin(),
180                                        CE = N->end(); CI != CE; ++CI) {
181       assert(*CI != Root && "No one can call the root node.");
182       (*CI)->print(OS);
183       OS << " ";
184     }
185     OS << '\n';
186   }
187   OS.flush();
188 }
189 
190 LLVM_DUMP_METHOD void CallGraph::dump() const {
191   print(llvm::errs());
192 }
193 
194 void CallGraph::viewGraph() const {
195   llvm::ViewGraph(this, "CallGraph");
196 }
197 
198 void CallGraphNode::print(raw_ostream &os) const {
199   if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(FD))
200       return ND->printName(os);
201   os << "< >";
202 }
203 
204 LLVM_DUMP_METHOD void CallGraphNode::dump() const {
205   print(llvm::errs());
206 }
207 
208 namespace llvm {
209 
210 template <>
211 struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits {
212 
213   DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
214 
215   static std::string getNodeLabel(const CallGraphNode *Node,
216                                   const CallGraph *CG) {
217     if (CG->getRoot() == Node) {
218       return "< root >";
219     }
220     if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Node->getDecl()))
221       return ND->getNameAsString();
222     else
223       return "< >";
224   }
225 
226 };
227 }
228