CallGraph.cpp revision bd80231672a7418aa1a99d3dbbe1774205c88f74 
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
23using namespace clang;
24
25STATISTIC(NumObjCCallEdges, "Number of objective C call edges");
26STATISTIC(NumBlockCallEdges, "Number of block call edges");
27
28namespace {
29/// A helper class, which walks the AST and locates all the call sites in the
30/// given function body.
31class CGBuilder : public StmtVisitor<CGBuilder> {
32  CallGraph *G;
33  CallGraphNode *CallerNode;
34
35public:
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      // Fild 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
94void 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
104CallGraph::CallGraph() {
105  Root = getOrInsertNode(0);
106}
107
108CallGraph::~CallGraph() {
109  if (!FunctionMap.empty()) {
110    for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
111        I != E; ++I)
112      delete I->second;
113    FunctionMap.clear();
114  }
115}
116
117bool CallGraph::includeInGraph(const Decl *D) {
118  assert(D);
119  if (!D->getBody())
120    return false;
121
122  if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
123    // We skip function template definitions, as their semantics is
124    // only determined when they are instantiated.
125    if (!FD->isThisDeclarationADefinition() ||
126        FD->isDependentContext())
127      return false;
128
129    IdentifierInfo *II = FD->getIdentifier();
130    if (II && II->getName().startswith("__inline"))
131      return false;
132  }
133
134  if (const ObjCMethodDecl *ID = dyn_cast<ObjCMethodDecl>(D)) {
135    if (!ID->isThisDeclarationADefinition())
136      return false;
137  }
138
139  return true;
140}
141
142void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) {
143  assert(D);
144
145  // Allocate a new node, mark it as root, and process it's calls.
146  CallGraphNode *Node = getOrInsertNode(D);
147
148  // Process all the calls by this function as well.
149  CGBuilder builder(this, Node);
150  if (Stmt *Body = D->getBody())
151    builder.Visit(Body);
152}
153
154CallGraphNode *CallGraph::getNode(const Decl *F) const {
155  FunctionMapTy::const_iterator I = FunctionMap.find(F);
156  if (I == FunctionMap.end()) return 0;
157  return I->second;
158}
159
160CallGraphNode *CallGraph::getOrInsertNode(Decl *F) {
161  CallGraphNode *&Node = FunctionMap[F];
162  if (Node)
163    return Node;
164
165  Node = new CallGraphNode(F);
166  // Make Root node a parent of all functions to make sure all are reachable.
167  if (F != 0)
168    Root->addCallee(Node, this);
169  return Node;
170}
171
172void CallGraph::print(raw_ostream &OS) const {
173  OS << " --- Call graph Dump --- \n";
174
175  // We are going to print the graph in reverse post order, partially, to make
176  // sure the output is deterministic.
177  llvm::ReversePostOrderTraversal<const clang::CallGraph*> RPOT(this);
178  for (llvm::ReversePostOrderTraversal<const clang::CallGraph*>::rpo_iterator
179         I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
180    const CallGraphNode *N = *I;
181
182    OS << "  Function: ";
183    if (N == Root)
184      OS << "< root >";
185    else
186      N->print(OS);
187
188    OS << " calls: ";
189    for (CallGraphNode::const_iterator CI = N->begin(),
190                                       CE = N->end(); CI != CE; ++CI) {
191      assert(*CI != Root && "No one can call the root node.");
192      (*CI)->print(OS);
193      OS << " ";
194    }
195    OS << '\n';
196  }
197  OS.flush();
198}
199
200void CallGraph::dump() const {
201  print(llvm::errs());
202}
203
204void CallGraph::viewGraph() const {
205  llvm::ViewGraph(this, "CallGraph");
206}
207
208void CallGraphNode::print(raw_ostream &os) const {
209  if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(FD))
210      return ND->printName(os);
211  os << "< >";
212}
213
214void CallGraphNode::dump() const {
215  print(llvm::errs());
216}
217
218namespace llvm {
219
220template <>
221struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits {
222
223  DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
224
225  static std::string getNodeLabel(const CallGraphNode *Node,
226                                  const CallGraph *CG) {
227    if (CG->getRoot() == Node) {
228      return "< root >";
229    }
230    if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Node->getDecl()))
231      return ND->getNameAsString();
232    else
233      return "< >";
234  }
235
236};
237}
238