1 //== CallGraph.cpp - Call graph building ------------------------*- 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 defined the CallGraph and CGBuilder classes.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "clang/Analysis/CallGraph.h"
15 
16 #include "clang/AST/ASTContext.h"
17 #include "clang/AST/StmtVisitor.h"
18 
19 #include "llvm/Support/GraphWriter.h"
20 
21 using namespace clang;
22 using namespace idx;
23 
24 namespace {
25 class CGBuilder : public StmtVisitor<CGBuilder> {
26 
27   CallGraph &G;
28   FunctionDecl *FD;
29 
30   Entity CallerEnt;
31 
32   CallGraphNode *CallerNode;
33 
34 public:
35   CGBuilder(CallGraph &g, FunctionDecl *fd, Entity E, CallGraphNode *N)
36     : G(g), FD(fd), CallerEnt(E), CallerNode(N) {}
37 
38   void VisitStmt(Stmt *S) { VisitChildren(S); }
39 
40   void VisitCallExpr(CallExpr *CE);
41 
42   void VisitChildren(Stmt *S) {
43     for (Stmt::child_iterator I=S->child_begin(), E=S->child_end(); I != E;++I)
44       if (*I)
45         static_cast<CGBuilder*>(this)->Visit(*I);
46   }
47 };
48 }
49 
50 void CGBuilder::VisitCallExpr(CallExpr *CE) {
51   if (FunctionDecl *CalleeDecl = CE->getDirectCallee()) {
52     Entity Ent = Entity::get(CalleeDecl, G.getProgram());
53     CallGraphNode *CalleeNode = G.getOrInsertFunction(Ent);
54 
55     Decl *Parent = ASTLocation::FindImmediateParent(FD, CE);
56 
57     CallerNode->addCallee(ASTLocation(Parent, CE), CalleeNode);
58   }
59 }
60 
61 CallGraph::CallGraph() : Root(0) {
62   ExternalCallingNode = getOrInsertFunction(Entity());
63 }
64 
65 CallGraph::~CallGraph() {
66   if (!FunctionMap.empty()) {
67     for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
68         I != E; ++I)
69       delete I->second;
70     FunctionMap.clear();
71   }
72 }
73 
74 void CallGraph::addTU(ASTUnit &AST) {
75   ASTContext &Ctx = AST.getASTContext();
76   DeclContext *DC = Ctx.getTranslationUnitDecl();
77 
78   for (DeclContext::decl_iterator I = DC->decls_begin(), E = DC->decls_end();
79        I != E; ++I) {
80 
81     if (FunctionDecl *FD = dyn_cast<FunctionDecl>(*I)) {
82       if (FD->isThisDeclarationADefinition()) {
83         // Set caller's ASTContext.
84         Entity Ent = Entity::get(FD, Prog);
85         CallGraphNode *Node = getOrInsertFunction(Ent);
86         CallerCtx[Node] = &Ctx;
87 
88         // If this function has external linkage, anything could call it.
89         if (FD->isGlobal())
90           ExternalCallingNode->addCallee(idx::ASTLocation(), Node);
91 
92         // Set root node to 'main' function.
93         if (FD->getNameAsString() == "main")
94           Root = Node;
95 
96         CGBuilder builder(*this, FD, Ent, Node);
97         builder.Visit(FD->getBody());
98       }
99     }
100   }
101 }
102 
103 CallGraphNode *CallGraph::getOrInsertFunction(Entity F) {
104   CallGraphNode *&Node = FunctionMap[F];
105   if (Node)
106     return Node;
107 
108   return Node = new CallGraphNode(F);
109 }
110 
111 Decl *CallGraph::getDecl(CallGraphNode *Node) {
112   // Get the function's context.
113   ASTContext *Ctx = CallerCtx[Node];
114 
115   return Node->getDecl(*Ctx);
116 }
117 
118 void CallGraph::print(llvm::raw_ostream &os) {
119   for (iterator I = begin(), E = end(); I != E; ++I) {
120     if (I->second->hasCallee()) {
121       os << "function: " << I->first.getPrintableName()
122          << " calls:\n";
123       for (CallGraphNode::iterator CI = I->second->begin(),
124              CE = I->second->end(); CI != CE; ++CI) {
125         os << "    " << CI->second->getName().c_str();
126       }
127       os << '\n';
128     }
129   }
130 }
131 
132 void CallGraph::dump() {
133   print(llvm::errs());
134 }
135 
136 void CallGraph::ViewCallGraph() const {
137   llvm::ViewGraph(*this, "CallGraph");
138 }
139 
140 namespace llvm {
141 
142 template <>
143 struct DOTGraphTraits<CallGraph> : public DefaultDOTGraphTraits {
144 
145   static std::string getNodeLabel(const CallGraphNode *Node,
146                                   const CallGraph &CG, bool ShortNames) {
147     return Node->getName();
148 
149   }
150 
151 };
152 
153 }
154