1234287Sdim//== CallGraph.cpp - AST-based Call graph ----------------------*- C++ -*--==// 2234287Sdim// 3234287Sdim// The LLVM Compiler Infrastructure 4234287Sdim// 5234287Sdim// This file is distributed under the University of Illinois Open Source 6234287Sdim// License. See LICENSE.TXT for details. 7234287Sdim// 8234287Sdim//===----------------------------------------------------------------------===// 9234287Sdim// 10234287Sdim// This file defines the AST-based CallGraph. 11234287Sdim// 12234287Sdim//===----------------------------------------------------------------------===// 13249423Sdim#define DEBUG_TYPE "CallGraph" 14249423Sdim 15234287Sdim#include "clang/Analysis/CallGraph.h" 16234287Sdim#include "clang/AST/ASTContext.h" 17234287Sdim#include "clang/AST/Decl.h" 18234287Sdim#include "clang/AST/StmtVisitor.h" 19249423Sdim#include "llvm/ADT/PostOrderIterator.h" 20249423Sdim#include "llvm/ADT/Statistic.h" 21234287Sdim#include "llvm/Support/GraphWriter.h" 22234287Sdim 23234287Sdimusing namespace clang; 24234287Sdim 25249423SdimSTATISTIC(NumObjCCallEdges, "Number of Objective-C method call edges"); 26249423SdimSTATISTIC(NumBlockCallEdges, "Number of block call edges"); 27249423Sdim 28234287Sdimnamespace { 29234287Sdim/// A helper class, which walks the AST and locates all the call sites in the 30234287Sdim/// given function body. 31234287Sdimclass CGBuilder : public StmtVisitor<CGBuilder> { 32234287Sdim CallGraph *G; 33234287Sdim CallGraphNode *CallerNode; 34234287Sdim 35234287Sdimpublic: 36239462Sdim CGBuilder(CallGraph *g, CallGraphNode *N) 37239462Sdim : G(g), CallerNode(N) {} 38234287Sdim 39234287Sdim void VisitStmt(Stmt *S) { VisitChildren(S); } 40234287Sdim 41249423Sdim Decl *getDeclFromCall(CallExpr *CE) { 42249423Sdim if (FunctionDecl *CalleeDecl = CE->getDirectCallee()) 43249423Sdim return CalleeDecl; 44249423Sdim 45249423Sdim // Simple detection of a call through a block. 46249423Sdim Expr *CEE = CE->getCallee()->IgnoreParenImpCasts(); 47249423Sdim if (BlockExpr *Block = dyn_cast<BlockExpr>(CEE)) { 48249423Sdim NumBlockCallEdges++; 49249423Sdim return Block->getBlockDecl(); 50249423Sdim } 51249423Sdim 52249423Sdim return 0; 53249423Sdim } 54249423Sdim 55249423Sdim void addCalledDecl(Decl *D) { 56249423Sdim if (G->includeInGraph(D)) { 57249423Sdim CallGraphNode *CalleeNode = G->getOrInsertNode(D); 58249423Sdim CallerNode->addCallee(CalleeNode, G); 59249423Sdim } 60249423Sdim } 61249423Sdim 62234287Sdim void VisitCallExpr(CallExpr *CE) { 63249423Sdim if (Decl *D = getDeclFromCall(CE)) 64249423Sdim addCalledDecl(D); 65249423Sdim } 66249423Sdim 67249423Sdim // Adds may-call edges for the ObjC message sends. 68249423Sdim void VisitObjCMessageExpr(ObjCMessageExpr *ME) { 69249423Sdim if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) { 70249423Sdim Selector Sel = ME->getSelector(); 71249423Sdim 72249423Sdim // Find the callee definition within the same translation unit. 73249423Sdim Decl *D = 0; 74249423Sdim if (ME->isInstanceMessage()) 75249423Sdim D = IDecl->lookupPrivateMethod(Sel); 76249423Sdim else 77249423Sdim D = IDecl->lookupPrivateClassMethod(Sel); 78249423Sdim if (D) { 79249423Sdim addCalledDecl(D); 80249423Sdim NumObjCCallEdges++; 81234287Sdim } 82249423Sdim } 83234287Sdim } 84234287Sdim 85234287Sdim void VisitChildren(Stmt *S) { 86234287Sdim for (Stmt::child_range I = S->children(); I; ++I) 87234287Sdim if (*I) 88234287Sdim static_cast<CGBuilder*>(this)->Visit(*I); 89234287Sdim } 90234287Sdim}; 91234287Sdim 92234287Sdim} // end anonymous namespace 93234287Sdim 94249423Sdimvoid CallGraph::addNodesForBlocks(DeclContext *D) { 95249423Sdim if (BlockDecl *BD = dyn_cast<BlockDecl>(D)) 96249423Sdim addNodeForDecl(BD, true); 97249423Sdim 98249423Sdim for (DeclContext::decl_iterator I = D->decls_begin(), E = D->decls_end(); 99249423Sdim I!=E; ++I) 100249423Sdim if (DeclContext *DC = dyn_cast<DeclContext>(*I)) 101249423Sdim addNodesForBlocks(DC); 102249423Sdim} 103249423Sdim 104234287SdimCallGraph::CallGraph() { 105234287Sdim Root = getOrInsertNode(0); 106234287Sdim} 107234287Sdim 108234287SdimCallGraph::~CallGraph() { 109234287Sdim if (!FunctionMap.empty()) { 110234287Sdim for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 111234287Sdim I != E; ++I) 112234287Sdim delete I->second; 113234287Sdim FunctionMap.clear(); 114234287Sdim } 115234287Sdim} 116234287Sdim 117234287Sdimbool CallGraph::includeInGraph(const Decl *D) { 118249423Sdim assert(D); 119249423Sdim if (!D->getBody()) 120249423Sdim return false; 121249423Sdim 122234287Sdim if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 123234287Sdim // We skip function template definitions, as their semantics is 124234287Sdim // only determined when they are instantiated. 125234287Sdim if (!FD->isThisDeclarationADefinition() || 126234287Sdim FD->isDependentContext()) 127234287Sdim return false; 128234287Sdim 129234287Sdim IdentifierInfo *II = FD->getIdentifier(); 130234287Sdim if (II && II->getName().startswith("__inline")) 131234287Sdim return false; 132234287Sdim } 133234287Sdim 134234287Sdim if (const ObjCMethodDecl *ID = dyn_cast<ObjCMethodDecl>(D)) { 135234287Sdim if (!ID->isThisDeclarationADefinition()) 136234287Sdim return false; 137234287Sdim } 138234287Sdim 139234287Sdim return true; 140234287Sdim} 141234287Sdim 142234287Sdimvoid CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) { 143234287Sdim assert(D); 144234287Sdim 145234287Sdim // Allocate a new node, mark it as root, and process it's calls. 146234287Sdim CallGraphNode *Node = getOrInsertNode(D); 147234287Sdim 148234287Sdim // Process all the calls by this function as well. 149239462Sdim CGBuilder builder(this, Node); 150234287Sdim if (Stmt *Body = D->getBody()) 151234287Sdim builder.Visit(Body); 152234287Sdim} 153234287Sdim 154234287SdimCallGraphNode *CallGraph::getNode(const Decl *F) const { 155234287Sdim FunctionMapTy::const_iterator I = FunctionMap.find(F); 156234287Sdim if (I == FunctionMap.end()) return 0; 157234287Sdim return I->second; 158234287Sdim} 159234287Sdim 160234287SdimCallGraphNode *CallGraph::getOrInsertNode(Decl *F) { 161234287Sdim CallGraphNode *&Node = FunctionMap[F]; 162234287Sdim if (Node) 163234287Sdim return Node; 164234287Sdim 165234287Sdim Node = new CallGraphNode(F); 166249423Sdim // Make Root node a parent of all functions to make sure all are reachable. 167234287Sdim if (F != 0) 168249423Sdim Root->addCallee(Node, this); 169234287Sdim return Node; 170234287Sdim} 171234287Sdim 172234287Sdimvoid CallGraph::print(raw_ostream &OS) const { 173234287Sdim OS << " --- Call graph Dump --- \n"; 174249423Sdim 175249423Sdim // We are going to print the graph in reverse post order, partially, to make 176249423Sdim // sure the output is deterministic. 177249423Sdim llvm::ReversePostOrderTraversal<const clang::CallGraph*> RPOT(this); 178249423Sdim for (llvm::ReversePostOrderTraversal<const clang::CallGraph*>::rpo_iterator 179249423Sdim I = RPOT.begin(), E = RPOT.end(); I != E; ++I) { 180249423Sdim const CallGraphNode *N = *I; 181249423Sdim 182234287Sdim OS << " Function: "; 183249423Sdim if (N == Root) 184234287Sdim OS << "< root >"; 185234287Sdim else 186249423Sdim N->print(OS); 187249423Sdim 188234287Sdim OS << " calls: "; 189249423Sdim for (CallGraphNode::const_iterator CI = N->begin(), 190249423Sdim CE = N->end(); CI != CE; ++CI) { 191234287Sdim assert(*CI != Root && "No one can call the root node."); 192234287Sdim (*CI)->print(OS); 193234287Sdim OS << " "; 194234287Sdim } 195234287Sdim OS << '\n'; 196234287Sdim } 197234287Sdim OS.flush(); 198234287Sdim} 199234287Sdim 200234287Sdimvoid CallGraph::dump() const { 201234287Sdim print(llvm::errs()); 202234287Sdim} 203234287Sdim 204234287Sdimvoid CallGraph::viewGraph() const { 205234287Sdim llvm::ViewGraph(this, "CallGraph"); 206234287Sdim} 207234287Sdim 208234287Sdimvoid CallGraphNode::print(raw_ostream &os) const { 209249423Sdim if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(FD)) 210249423Sdim return ND->printName(os); 211249423Sdim os << "< >"; 212234287Sdim} 213234287Sdim 214234287Sdimvoid CallGraphNode::dump() const { 215234287Sdim print(llvm::errs()); 216234287Sdim} 217234287Sdim 218234287Sdimnamespace llvm { 219234287Sdim 220234287Sdimtemplate <> 221234287Sdimstruct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits { 222234287Sdim 223234287Sdim DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 224234287Sdim 225234287Sdim static std::string getNodeLabel(const CallGraphNode *Node, 226234287Sdim const CallGraph *CG) { 227234287Sdim if (CG->getRoot() == Node) { 228234287Sdim return "< root >"; 229234287Sdim } 230249423Sdim if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Node->getDecl())) 231249423Sdim return ND->getNameAsString(); 232249423Sdim else 233249423Sdim return "< >"; 234234287Sdim } 235234287Sdim 236234287Sdim}; 237234287Sdim} 238