CallGraph.cpp revision 55fc873017f10f6f566b182b70f6fc22aefa3464
1d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis//== CallGraph.cpp - AST-based Call graph ----------------------*- C++ -*--==// 277349cb20bfd7069d081f84c91975bfa8ef60a32Ted Kremenek// 377349cb20bfd7069d081f84c91975bfa8ef60a32Ted Kremenek// The LLVM Compiler Infrastructure 477349cb20bfd7069d081f84c91975bfa8ef60a32Ted Kremenek// 577349cb20bfd7069d081f84c91975bfa8ef60a32Ted Kremenek// This file is distributed under the University of Illinois Open Source 677349cb20bfd7069d081f84c91975bfa8ef60a32Ted Kremenek// License. See LICENSE.TXT for details. 777349cb20bfd7069d081f84c91975bfa8ef60a32Ted Kremenek// 877349cb20bfd7069d081f84c91975bfa8ef60a32Ted Kremenek//===----------------------------------------------------------------------===// 977349cb20bfd7069d081f84c91975bfa8ef60a32Ted Kremenek// 10b387a3f23e423d62c053be86294b703da1d1a222Ted Kremenek// This file defines the AST-based CallGraph. 11d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis// 12b387a3f23e423d62c053be86294b703da1d1a222Ted Kremenek//===----------------------------------------------------------------------===// 1377349cb20bfd7069d081f84c91975bfa8ef60a32Ted Kremenek#include "clang/Analysis/CallGraph.h" 1477349cb20bfd7069d081f84c91975bfa8ef60a32Ted Kremenek#include "clang/AST/ASTContext.h" 1577349cb20bfd7069d081f84c91975bfa8ef60a32Ted Kremenek#include "clang/AST/Decl.h" 16d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis#include "clang/AST/StmtVisitor.h" 17d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis#include "llvm/Support/GraphWriter.h" 18d065d6080f0620bb80b933f3f5d52d37bb2ea770Ted Kremenek 1921142581d55918beed544a757e4af3bb865b1812Ted Kremenekusing namespace clang; 2021142581d55918beed544a757e4af3bb865b1812Ted Kremenek 2121142581d55918beed544a757e4af3bb865b1812Ted Kremeneknamespace { 2221142581d55918beed544a757e4af3bb865b1812Ted Kremenek/// A helper class, which walks the AST and locates all the call sites in the 2321142581d55918beed544a757e4af3bb865b1812Ted Kremenek/// given function body. 2421142581d55918beed544a757e4af3bb865b1812Ted Kremenekclass CGBuilder : public StmtVisitor<CGBuilder> { 25c0c3f5dbc9e78aa53a86c7d5e3eeda23ddad93d6Ted Kremenek CallGraph *G; 26f494b579b22f9950f5af021f0bf9879a91bb8b41Steve Naroff CallGraphNode *CallerNode; 27bb141217871e93767aa3f2de1b9946fa6d37066aZhongxing Xu 284beaa9f51b2da57c64740cef2bd1c2fdb0c325d5Ted Kremenekpublic: 2977349cb20bfd7069d081f84c91975bfa8ef60a32Ted Kremenek CGBuilder(CallGraph *g, CallGraphNode *N) 301eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump : G(g), CallerNode(N) {} 315a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 325a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis void VisitStmt(Stmt *S) { VisitChildren(S); } 335a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 349ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenek void VisitCallExpr(CallExpr *CE) { 355a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis // TODO: We need to handle ObjC method calls as well. 365e2d2c2ee3cf410643e0f9a5701708e51409d973Benjamin Kramer if (FunctionDecl *CalleeDecl = CE->getDirectCallee()) 375e2d2c2ee3cf410643e0f9a5701708e51409d973Benjamin Kramer if (G->includeInGraph(CalleeDecl)) { 38f494b579b22f9950f5af021f0bf9879a91bb8b41Steve Naroff CallGraphNode *CalleeNode = G->getOrInsertNode(CalleeDecl); 39d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CallerNode->addCallee(CalleeNode, G); 4025e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu } 4125e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu } 42d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis 431eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump void VisitChildren(Stmt *S) { 44b387a3f23e423d62c053be86294b703da1d1a222Ted Kremenek for (Stmt::child_range I = S->children(); I; ++I) 45031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu if (*I) 461eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump static_cast<CGBuilder*>(this)->Visit(*I); 47d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis } 48b387a3f23e423d62c053be86294b703da1d1a222Ted Kremenek}; 49d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis 501eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump} // end anonymous namespace 51b387a3f23e423d62c053be86294b703da1d1a222Ted Kremenek 524adc81e540b874bafa15715fd2c5cb662463debdTed KremenekCallGraph::CallGraph() { 53cf118d41f7930a18dce97416ef7834a62642f587Ted Kremenek Root = getOrInsertNode(0); 54b387a3f23e423d62c053be86294b703da1d1a222Ted Kremenek} 55b387a3f23e423d62c053be86294b703da1d1a222Ted Kremenek 561eb4433ac451dc16f4133a88af2d002ac26c58efMike StumpCallGraph::~CallGraph() { 57846eabd187be4bfe992e8bca131166b734d86e0dTed Kremenek if (!FunctionMap.empty()) { 58846eabd187be4bfe992e8bca131166b734d86e0dTed Kremenek for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 591eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump I != E; ++I) 60846d4e923bf11bcdc2816758aafa331795f29230Ted Kremenek delete I->second; 61031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu FunctionMap.clear(); 62846d4e923bf11bcdc2816758aafa331795f29230Ted Kremenek } 63846d4e923bf11bcdc2816758aafa331795f29230Ted Kremenek} 640d093d3005dd583675a45a85bd688063572cc8afTed Kremenek 651eb4433ac451dc16f4133a88af2d002ac26c58efMike Stumpbool CallGraph::includeInGraph(const Decl *D) { 661eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 670a3ed3143b00f237decb1288c1ff574ae09eba4eTed Kremenek // We skip function template definitions, as their semantics is 680a3ed3143b00f237decb1288c1ff574ae09eba4eTed Kremenek // only determined when they are instantiated. 691eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump if (!FD->isThisDeclarationADefinition() || 70e448ab4f9dd162802f5d7cfea60f7830cc61c654Ted Kremenek FD->isDependentContext()) 71e448ab4f9dd162802f5d7cfea60f7830cc61c654Ted Kremenek return false; 721eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 73e448ab4f9dd162802f5d7cfea60f7830cc61c654Ted Kremenek IdentifierInfo *II = FD->getIdentifier(); 74e448ab4f9dd162802f5d7cfea60f7830cc61c654Ted Kremenek if (II && II->getName().startswith("__inline")) 75e448ab4f9dd162802f5d7cfea60f7830cc61c654Ted Kremenek return false; 761eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 7772905cfa81cfd126f322c4173f56d332aac5539eJordy Rose 7872905cfa81cfd126f322c4173f56d332aac5539eJordy Rose if (const ObjCMethodDecl *ID = dyn_cast<ObjCMethodDecl>(D)) { 7972905cfa81cfd126f322c4173f56d332aac5539eJordy Rose if (!ID->isThisDeclarationADefinition()) 80c2b7dfaad674587cfd220ff447b3710d252130c3Jordy Rose return false; 81c2b7dfaad674587cfd220ff447b3710d252130c3Jordy Rose } 8272905cfa81cfd126f322c4173f56d332aac5539eJordy Rose 8372905cfa81cfd126f322c4173f56d332aac5539eJordy Rose return true; 8472905cfa81cfd126f322c4173f56d332aac5539eJordy Rose} 8572905cfa81cfd126f322c4173f56d332aac5539eJordy Rose 8672905cfa81cfd126f322c4173f56d332aac5539eJordy Rosevoid CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) { 8772905cfa81cfd126f322c4173f56d332aac5539eJordy Rose assert(D); 8872905cfa81cfd126f322c4173f56d332aac5539eJordy Rose 8972905cfa81cfd126f322c4173f56d332aac5539eJordy Rose // Do nothing if the node already exists. 9072905cfa81cfd126f322c4173f56d332aac5539eJordy Rose if (FunctionMap.find(D) != FunctionMap.end()) 9172905cfa81cfd126f322c4173f56d332aac5539eJordy Rose return; 9272905cfa81cfd126f322c4173f56d332aac5539eJordy Rose 9372905cfa81cfd126f322c4173f56d332aac5539eJordy Rose // Allocate a new node, mark it as root, and process it's calls. 94094bef56a7900f13bb777f9a352704104b1458e7Ted Kremenek CallGraphNode *Node = getOrInsertNode(D); 95b94b81a9ab46c99b00c7ad28c5e1e212c63fc9acZhongxing Xu if (IsGlobal) 9672905cfa81cfd126f322c4173f56d332aac5539eJordy Rose Root->addCallee(Node, this); 979e9595b12e9b55586c4d50d370f429c7a3c92a90Ted Kremenek 989e9595b12e9b55586c4d50d370f429c7a3c92a90Ted Kremenek // Process all the calls by this function as well. 999e9595b12e9b55586c4d50d370f429c7a3c92a90Ted Kremenek CGBuilder builder(this, Node); 1009e9595b12e9b55586c4d50d370f429c7a3c92a90Ted Kremenek if (Stmt *Body = D->getBody()) 1019e9595b12e9b55586c4d50d370f429c7a3c92a90Ted Kremenek builder.Visit(Body); 1029e9595b12e9b55586c4d50d370f429c7a3c92a90Ted Kremenek} 1039e9595b12e9b55586c4d50d370f429c7a3c92a90Ted Kremenek 104094bef56a7900f13bb777f9a352704104b1458e7Ted KremenekCallGraphNode *CallGraph::getNode(const Decl *F) const { 105ff944a8c481d6c0f1ad2633e4be9bf8b1dd2a09fZhongxing Xu FunctionMapTy::const_iterator I = FunctionMap.find(F); 1069e9595b12e9b55586c4d50d370f429c7a3c92a90Ted Kremenek if (I == FunctionMap.end()) return 0; 10772905cfa81cfd126f322c4173f56d332aac5539eJordy Rose return I->second; 1089e9595b12e9b55586c4d50d370f429c7a3c92a90Ted Kremenek} 1099e9595b12e9b55586c4d50d370f429c7a3c92a90Ted Kremenek 1109e9595b12e9b55586c4d50d370f429c7a3c92a90Ted KremenekCallGraphNode *CallGraph::getOrInsertNode(Decl *F) { 1119e9595b12e9b55586c4d50d370f429c7a3c92a90Ted Kremenek CallGraphNode *&Node = FunctionMap[F]; 112d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis if (Node) 113cf118d41f7930a18dce97416ef7834a62642f587Ted Kremenek return Node; 11432a58084a4c53e6938dd81bfce224db25a5976d1Ted Kremenek 115d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis Node = new CallGraphNode(F); 1161eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // If not root, add to the parentless list. 117b22d589e2ccd09cada0bcea136f0966883a8bb11Ted Kremenek if (F != 0) 118d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis ParentlessNodes.insert(Node); 119cf118d41f7930a18dce97416ef7834a62642f587Ted Kremenek return Node; 120d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis} 1211eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 12225e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xuvoid CallGraph::print(raw_ostream &OS) const { 123d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis OS << " --- Call graph Dump --- \n"; 1242ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu for (const_iterator I = begin(), E = end(); I != E; ++I) { 1252ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu OS << " Function: "; 1262ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu if (I->second == Root) 1272ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu OS << "< root >"; 1282ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu else 1292ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu I->second->print(OS); 1302ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu OS << " calls: "; 1312ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu for (CallGraphNode::iterator CI = I->second->begin(), 132d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CE = I->second->end(); CI != CE; ++CI) { 133b387a3f23e423d62c053be86294b703da1d1a222Ted Kremenek assert(*CI != Root && "No one can call the root node."); 1341eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump (*CI)->print(OS); 135b387a3f23e423d62c053be86294b703da1d1a222Ted Kremenek OS << " "; 136c77a55126fcad66fb086f8e100a494caa2496a2dZhongxing Xu } 1375032ffe4259e7d436f2eb19e5a29fdae559e7c12Zhongxing Xu OS << '\n'; 1382ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu } 1391eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump OS.flush(); 140846eabd187be4bfe992e8bca131166b734d86e0dTed Kremenek} 1411eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 142d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisvoid CallGraph::dump() const { 1431eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump print(llvm::errs()); 144cf118d41f7930a18dce97416ef7834a62642f587Ted Kremenek} 1451eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 146d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisvoid CallGraph::viewGraph() const { 147ec9227fea66c3439991fc84b0d33b0a8b4b8875eZhongxing Xu llvm::ViewGraph(this, "CallGraph"); 148d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis} 149d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis 1501eb4433ac451dc16f4133a88af2d002ac26c58efMike StumpStringRef CallGraphNode::getName() const { 151e01c98767dfd7153c3c84637c36659e3bbe16ff7Ted Kremenek if (const FunctionDecl *D = dyn_cast_or_null<FunctionDecl>(FD)) 152e01c98767dfd7153c3c84637c36659e3bbe16ff7Ted Kremenek if (const IdentifierInfo *II = D->getIdentifier()) 153ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek return II->getName(); 1541eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump return "< >"; 155031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu} 1561eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 157b387a3f23e423d62c053be86294b703da1d1a222Ted Kremenekvoid CallGraphNode::print(raw_ostream &os) const { 158b387a3f23e423d62c053be86294b703da1d1a222Ted Kremenek os << getName(); 15917fd8632dcda97022a51effc24060eacdad9dbe0Zhongxing Xu} 1601eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 161031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xuvoid CallGraphNode::dump() const { 162031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu print(llvm::errs()); 16350a6d0ce344c02782e0207574005c3b2aaa5077cTed Kremenek} 164ec9227fea66c3439991fc84b0d33b0a8b4b8875eZhongxing Xu 165094bef56a7900f13bb777f9a352704104b1458e7Ted Kremeneknamespace llvm { 166094bef56a7900f13bb777f9a352704104b1458e7Ted Kremenek 167094bef56a7900f13bb777f9a352704104b1458e7Ted Kremenektemplate <> 168094bef56a7900f13bb777f9a352704104b1458e7Ted Kremenekstruct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits { 169094bef56a7900f13bb777f9a352704104b1458e7Ted Kremenek 170ec9227fea66c3439991fc84b0d33b0a8b4b8875eZhongxing Xu DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 171094bef56a7900f13bb777f9a352704104b1458e7Ted Kremenek 172094bef56a7900f13bb777f9a352704104b1458e7Ted Kremenek static std::string getNodeLabel(const CallGraphNode *Node, 173ec9227fea66c3439991fc84b0d33b0a8b4b8875eZhongxing Xu const CallGraph *CG) { 174ec9227fea66c3439991fc84b0d33b0a8b4b8875eZhongxing Xu if (CG->getRoot() == Node) { 175094bef56a7900f13bb777f9a352704104b1458e7Ted Kremenek return "< root >"; 176094bef56a7900f13bb777f9a352704104b1458e7Ted Kremenek } 1775a5d98bc6962dc2d1aaa5e0e522f1bf84273b9c1Ted Kremenek return Node->getName(); 1781eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 179d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis 1809c6cd67ea416bace666d614c84d5531124287653Zhongxing Xu}; 181d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis} 1829c6cd67ea416bace666d614c84d5531124287653Zhongxing Xu