CallGraph.cpp revision bb3d20f80c98e7919411bc7e062d69b17462899b
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 22using namespace clang; 23 24/// Determine if a declaration should be included in the graph. 25static 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 46namespace { 47/// A helper class, which walks the AST and locates all the call sites in the 48/// given function body. 49class CGBuilder : public StmtVisitor<CGBuilder> { 50 CallGraph *G; 51 const Decl *FD; 52 CallGraphNode *CallerNode; 53 54public: 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. 80class CGDeclVisitor : public RecursiveASTVisitor<CGDeclVisitor> { 81 CallGraph *CG; 82 83public: 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 106CallGraph::CallGraph() { 107 Root = getOrInsertFunction(0); 108} 109 110CallGraph::~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 119void 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 132void CallGraph::addToCallGraph(TranslationUnitDecl *TU) { 133 CGDeclVisitor(this).TraverseDecl(TU); 134} 135 136CallGraphNode *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 142CallGraphNode *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 154void 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 174void CallGraph::dump() const { 175 print(llvm::errs()); 176} 177 178void CallGraph::viewGraph() const { 179 llvm::ViewGraph(this, "CallGraph"); 180} 181 182StringRef 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 189void CallGraphNode::print(raw_ostream &os) const { 190 os << getName(); 191} 192 193void CallGraphNode::dump() const { 194 print(llvm::errs()); 195} 196 197namespace llvm { 198 199template <> 200struct 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