CallGraph.cpp revision e34e1939ad67576293b2b205b2169488cc6b3b14
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#define DEBUG_TYPE "CallGraph" 14 15#include "clang/Analysis/CallGraph.h" 16#include "clang/AST/ASTContext.h" 17#include "clang/AST/Decl.h" 18#include "clang/AST/StmtVisitor.h" 19#include "llvm/ADT/Statistic.h" 20#include "llvm/Support/GraphWriter.h" 21 22using namespace clang; 23 24STATISTIC(NumObjCCallEdges, "Number of objective C call edges"); 25STATISTIC(NumBlockCallEdges, "Number of block call edges"); 26 27namespace { 28/// A helper class, which walks the AST and locates all the call sites in the 29/// given function body. 30class CGBuilder : public StmtVisitor<CGBuilder> { 31 CallGraph *G; 32 CallGraphNode *CallerNode; 33 34public: 35 CGBuilder(CallGraph *g, CallGraphNode *N) 36 : G(g), CallerNode(N) {} 37 38 void VisitStmt(Stmt *S) { VisitChildren(S); } 39 40 Decl *getDeclFromCall(CallExpr *CE) { 41 if (FunctionDecl *CalleeDecl = CE->getDirectCallee()) 42 return CalleeDecl; 43 44 // Simple detection of a call through a block. 45 Expr *CEE = CE->getCallee()->IgnoreParenImpCasts(); 46 if (BlockExpr *Block = dyn_cast<BlockExpr>(CEE)) { 47 NumBlockCallEdges++; 48 return Block->getBlockDecl(); 49 } 50 51 return 0; 52 } 53 54 void addCalledDecl(Decl *D) { 55 if (G->includeInGraph(D)) { 56 CallGraphNode *CalleeNode = G->getOrInsertNode(D); 57 CallerNode->addCallee(CalleeNode, G); 58 } 59 } 60 61 void VisitCallExpr(CallExpr *CE) { 62 if (Decl *D = getDeclFromCall(CE)) 63 addCalledDecl(D); 64 } 65 66 // Adds may-call edges for the ObjC message sends. 67 void VisitObjCMessageExpr(ObjCMessageExpr *ME) { 68 if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) { 69 Selector Sel = ME->getSelector(); 70 71 // Fild the callee definition within the same translation unit. 72 Decl *D = 0; 73 if (ME->isInstanceMessage()) 74 D = IDecl->lookupPrivateMethod(Sel); 75 else 76 D = IDecl->lookupPrivateClassMethod(Sel); 77 if (D) { 78 addCalledDecl(D); 79 NumObjCCallEdges++; 80 } 81 } 82 } 83 84 void VisitChildren(Stmt *S) { 85 for (Stmt::child_range I = S->children(); I; ++I) 86 if (*I) 87 static_cast<CGBuilder*>(this)->Visit(*I); 88 } 89}; 90 91} // end anonymous namespace 92 93void CallGraph::addNodesForBlocks(DeclContext *D) { 94 if (BlockDecl *BD = dyn_cast<BlockDecl>(D)) 95 addNodeForDecl(BD, true); 96 97 for (DeclContext::decl_iterator I = D->decls_begin(), E = D->decls_end(); 98 I!=E; ++I) 99 if (DeclContext *DC = dyn_cast<DeclContext>(*I)) 100 addNodesForBlocks(DC); 101} 102 103CallGraph::CallGraph() { 104 Root = getOrInsertNode(0); 105} 106 107CallGraph::~CallGraph() { 108 if (!FunctionMap.empty()) { 109 for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 110 I != E; ++I) 111 delete I->second; 112 FunctionMap.clear(); 113 } 114} 115 116bool CallGraph::includeInGraph(const Decl *D) { 117 assert(D); 118 if (!D->getBody()) 119 return false; 120 121 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 122 // We skip function template definitions, as their semantics is 123 // only determined when they are instantiated. 124 if (!FD->isThisDeclarationADefinition() || 125 FD->isDependentContext()) 126 return false; 127 128 IdentifierInfo *II = FD->getIdentifier(); 129 if (II && II->getName().startswith("__inline")) 130 return false; 131 } 132 133 if (const ObjCMethodDecl *ID = dyn_cast<ObjCMethodDecl>(D)) { 134 if (!ID->isThisDeclarationADefinition()) 135 return false; 136 } 137 138 return true; 139} 140 141void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) { 142 assert(D); 143 144 // Allocate a new node, mark it as root, and process it's calls. 145 CallGraphNode *Node = getOrInsertNode(D); 146 147 // Process all the calls by this function as well. 148 CGBuilder builder(this, Node); 149 if (Stmt *Body = D->getBody()) 150 builder.Visit(Body); 151} 152 153CallGraphNode *CallGraph::getNode(const Decl *F) const { 154 FunctionMapTy::const_iterator I = FunctionMap.find(F); 155 if (I == FunctionMap.end()) return 0; 156 return I->second; 157} 158 159CallGraphNode *CallGraph::getOrInsertNode(Decl *F) { 160 CallGraphNode *&Node = FunctionMap[F]; 161 if (Node) 162 return Node; 163 164 Node = new CallGraphNode(F); 165 // Make Root node a parent of all functions to make sure all are reachable. 166 if (F != 0) 167 Root->addCallee(Node, this); 168 return Node; 169} 170 171void CallGraph::print(raw_ostream &OS) const { 172 OS << " --- Call graph Dump --- \n"; 173 for (const_iterator I = begin(), E = end(); I != E; ++I) { 174 OS << " Function: "; 175 if (I->second == Root) 176 OS << "< root >"; 177 else 178 I->second->print(OS); 179 OS << " calls: "; 180 for (CallGraphNode::iterator CI = I->second->begin(), 181 CE = I->second->end(); CI != CE; ++CI) { 182 assert(*CI != Root && "No one can call the root node."); 183 (*CI)->print(OS); 184 OS << " "; 185 } 186 OS << '\n'; 187 } 188 OS.flush(); 189} 190 191void CallGraph::dump() const { 192 print(llvm::errs()); 193} 194 195void CallGraph::viewGraph() const { 196 llvm::ViewGraph(this, "CallGraph"); 197} 198 199void CallGraphNode::print(raw_ostream &os) const { 200 if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(FD)) 201 return ND->printName(os); 202 os << "< >"; 203} 204 205void CallGraphNode::dump() const { 206 print(llvm::errs()); 207} 208 209namespace llvm { 210 211template <> 212struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits { 213 214 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 215 216 static std::string getNodeLabel(const CallGraphNode *Node, 217 const CallGraph *CG) { 218 if (CG->getRoot() == Node) { 219 return "< root >"; 220 } 221 if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Node->getDecl())) 222 return ND->getNameAsString(); 223 else 224 return "< >"; 225 } 226 227}; 228} 229