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