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 
15 #include "clang/AST/ASTContext.h"
16 #include "clang/AST/Decl.h"
17 #include "clang/AST/RecursiveASTVisitor.h"
18 #include "clang/AST/StmtVisitor.h"
19 
20 #include "llvm/Support/GraphWriter.h"
21 
22 using namespace clang;
23 
24 /// Determine if a declaration should be included in the graph.
25 static bool includeInGraph(const Decl *D) {
26   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
27     // We skip function template definitions, as their semantics is
28     // only determined when they are instantiated.
29     if (!FD->isThisDeclarationADefinition() ||
30         FD->isDependentContext())
31       return false;
32 
33     IdentifierInfo *II = FD->getIdentifier();
34     if (II && II->getName().startswith("__inline"))
35       return false;
36   }
37 
38   if (const ObjCMethodDecl *ID = dyn_cast<ObjCMethodDecl>(D)) {
39     if (!ID->isThisDeclarationADefinition())
40       return false;
41   }
42 
43   return true;
44 }
45 
46 namespace {
47 /// A helper class, which walks the AST and locates all the call sites in the
48 /// given function body.
49 class CGBuilder : public StmtVisitor<CGBuilder> {
50   CallGraph *G;
51   const Decl *FD;
52   CallGraphNode *CallerNode;
53 
54 public:
55   CGBuilder(CallGraph *g, const Decl *D, CallGraphNode *N)
56     : G(g), FD(D), CallerNode(N) {}
57 
58   void VisitStmt(Stmt *S) { VisitChildren(S); }
59 
60   void VisitCallExpr(CallExpr *CE) {
61     // TODO: We need to handle ObjC method calls as well.
62     if (FunctionDecl *CalleeDecl = CE->getDirectCallee())
63       if (includeInGraph(CalleeDecl)) {
64         CallGraphNode *CalleeNode = G->getOrInsertFunction(CalleeDecl);
65         CallerNode->addCallee(CalleeNode, G);
66       }
67   }
68 
69   void VisitChildren(Stmt *S) {
70     for (Stmt::child_range I = S->children(); I; ++I)
71       if (*I)
72         static_cast<CGBuilder*>(this)->Visit(*I);
73   }
74 };
75 
76 /// A helper class which walks the AST declarations.
77 // TODO: We might want to specialize the visitor to shrink the call graph.
78 // For example, we might not want to include the inline methods from header
79 // files.
80 class CGDeclVisitor : public RecursiveASTVisitor<CGDeclVisitor> {
81   CallGraph *CG;
82 
83 public:
84   CGDeclVisitor(CallGraph * InCG) : CG(InCG) {}
85 
86   bool VisitFunctionDecl(FunctionDecl *FD) {
87     // We skip function template definitions, as their semantics is
88     // only determined when they are instantiated.
89     if (includeInGraph(FD))
90       // If this function has external linkage, anything could call it.
91       // Note, we are not precise here. For example, the function could have
92       // its address taken.
93       CG->addToCallGraph(FD, FD->isGlobal());
94     return true;
95   }
96 
97   bool VisitObjCMethodDecl(ObjCMethodDecl *MD) {
98     if (includeInGraph(MD))
99       CG->addToCallGraph(MD, true);
100     return true;
101   }
102 };
103 
104 } // end anonymous namespace
105 
106 CallGraph::CallGraph() {
107   Root = getOrInsertFunction(0);
108 }
109 
110 CallGraph::~CallGraph() {
111   if (!FunctionMap.empty()) {
112     for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
113         I != E; ++I)
114       delete I->second;
115     FunctionMap.clear();
116   }
117 }
118 
119 void CallGraph::addToCallGraph(Decl* D, bool IsGlobal) {
120   assert(D);
121   CallGraphNode *Node = getOrInsertFunction(D);
122 
123   if (IsGlobal)
124     Root->addCallee(Node, this);
125 
126   // Process all the calls by this function as well.
127   CGBuilder builder(this, D, Node);
128   if (Stmt *Body = D->getBody())
129     builder.Visit(Body);
130 }
131 
132 void CallGraph::addToCallGraph(TranslationUnitDecl *TU) {
133   CGDeclVisitor(this).TraverseDecl(TU);
134 }
135 
136 CallGraphNode *CallGraph::getNode(const Decl *F) const {
137   FunctionMapTy::const_iterator I = FunctionMap.find(F);
138   if (I == FunctionMap.end()) return 0;
139   return I->second;
140 }
141 
142 CallGraphNode *CallGraph::getOrInsertFunction(Decl *F) {
143   CallGraphNode *&Node = FunctionMap[F];
144   if (Node)
145     return Node;
146 
147   Node = new CallGraphNode(F);
148   // If not root, add to the parentless list.
149   if (F != 0)
150     ParentlessNodes.insert(Node);
151   return Node;
152 }
153 
154 void CallGraph::print(raw_ostream &OS) const {
155   OS << " --- Call graph Dump --- \n";
156   for (const_iterator I = begin(), E = end(); I != E; ++I) {
157     OS << "  Function: ";
158     if (I->second == Root)
159       OS << "< root >";
160     else
161       I->second->print(OS);
162     OS << " calls: ";
163     for (CallGraphNode::iterator CI = I->second->begin(),
164         CE = I->second->end(); CI != CE; ++CI) {
165       assert(*CI != Root && "No one can call the root node.");
166       (*CI)->print(OS);
167       OS << " ";
168     }
169     OS << '\n';
170   }
171   OS.flush();
172 }
173 
174 void CallGraph::dump() const {
175   print(llvm::errs());
176 }
177 
178 void CallGraph::viewGraph() const {
179   llvm::ViewGraph(this, "CallGraph");
180 }
181 
182 StringRef CallGraphNode::getName() const {
183   if (const FunctionDecl *D = dyn_cast_or_null<FunctionDecl>(FD))
184     if (const IdentifierInfo *II = D->getIdentifier())
185       return II->getName();
186     return "< >";
187 }
188 
189 void CallGraphNode::print(raw_ostream &os) const {
190   os << getName();
191 }
192 
193 void CallGraphNode::dump() const {
194   print(llvm::errs());
195 }
196 
197 namespace llvm {
198 
199 template <>
200 struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits {
201 
202   DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
203 
204   static std::string getNodeLabel(const CallGraphNode *Node,
205                                   const CallGraph *CG) {
206     if (CG->getRoot() == Node) {
207       return "< root >";
208     }
209     return Node->getName();
210   }
211 
212 };
213 }
214