CallGraph.cpp revision d53e877ddf885da28aa4668148a5f0ce0045ab54
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 builder.Visit(D->getBody()); 129} 130 131void CallGraph::addToCallGraph(TranslationUnitDecl *TU) { 132 CGDeclVisitor(this).TraverseDecl(TU); 133} 134 135CallGraphNode *CallGraph::getNode(const Decl *F) const { 136 FunctionMapTy::const_iterator I = FunctionMap.find(F); 137 if (I == FunctionMap.end()) return 0; 138 return I->second; 139} 140 141CallGraphNode *CallGraph::getOrInsertFunction(Decl *F) { 142 CallGraphNode *&Node = FunctionMap[F]; 143 if (Node) 144 return Node; 145 146 Node = new CallGraphNode(F); 147 // If not root, add to the parentless list. 148 if (F != 0) 149 ParentlessNodes.insert(Node); 150 return Node; 151} 152 153void CallGraph::print(raw_ostream &OS) const { 154 OS << " --- Call graph Dump --- \n"; 155 for (const_iterator I = begin(), E = end(); I != E; ++I) { 156 OS << " Function: "; 157 if (I->second == Root) 158 OS << "< root >"; 159 else 160 I->second->print(OS); 161 OS << " calls: "; 162 for (CallGraphNode::iterator CI = I->second->begin(), 163 CE = I->second->end(); CI != CE; ++CI) { 164 assert(*CI != Root && "No one can call the root node."); 165 (*CI)->print(OS); 166 OS << " "; 167 } 168 OS << '\n'; 169 } 170 OS.flush(); 171} 172 173void CallGraph::dump() const { 174 print(llvm::errs()); 175} 176 177void CallGraph::viewGraph() const { 178 llvm::ViewGraph(this, "CallGraph"); 179} 180 181StringRef CallGraphNode::getName() const { 182 if (const FunctionDecl *D = dyn_cast_or_null<FunctionDecl>(FD)) 183 if (const IdentifierInfo *II = D->getIdentifier()) 184 return II->getName(); 185 return "< >"; 186} 187 188void CallGraphNode::print(raw_ostream &os) const { 189 os << getName(); 190} 191 192void CallGraphNode::dump() const { 193 print(llvm::errs()); 194} 195 196namespace llvm { 197 198template <> 199struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits { 200 201 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 202 203 static std::string getNodeLabel(const CallGraphNode *Node, 204 const CallGraph *CG) { 205 if (CG->getRoot() == Node) { 206 return "< root >"; 207 } 208 return Node->getName(); 209 } 210 211}; 212} 213