CallGraph.cpp revision d2776613703a516f107decc06b38a0b60a10542c
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 23/// Determine if a declaration should be included in the graph. 24static bool includeInGraph(const Decl *D) { 25 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 26 // We skip function template definitions, as their semantics is 27 // only determined when they are instantiated. 28 if (!FD->isThisDeclarationADefinition() || 29 FD->isDependentContext()) 30 return false; 31 32 IdentifierInfo *II = FD->getIdentifier(); 33 if (II && II->getName().startswith("__inline")) 34 return false; 35 } 36 37 if (const ObjCMethodDecl *ID = dyn_cast<ObjCMethodDecl>(D)) { 38 if (!ID->isThisDeclarationADefinition()) 39 return false; 40 } 41 42 return true; 43} 44 45namespace { 46/// A helper class, which walks the AST and locates all the call sites in the 47/// given function body. 48class CGBuilder : public StmtVisitor<CGBuilder> { 49 CallGraph *G; 50 const Decl *FD; 51 CallGraphNode *CallerNode; 52 53public: 54 CGBuilder(CallGraph *g, const Decl *D, CallGraphNode *N) 55 : G(g), FD(D), CallerNode(N) {} 56 57 void VisitStmt(Stmt *S) { VisitChildren(S); } 58 59 void VisitCallExpr(CallExpr *CE) { 60 // TODO: We need to handle ObjC method calls as well. 61 if (FunctionDecl *CalleeDecl = CE->getDirectCallee()) 62 if (includeInGraph(CalleeDecl)) { 63 CallGraphNode *CalleeNode = G->getOrInsertFunction(CalleeDecl); 64 CallerNode->addCallee(CalleeNode, G); 65 } 66 } 67 68 void VisitChildren(Stmt *S) { 69 for (Stmt::child_range I = S->children(); I; ++I) 70 if (*I) 71 static_cast<CGBuilder*>(this)->Visit(*I); 72 } 73}; 74} // end anonymous namespace 75 76CallGraph::CallGraph() { 77 Root = getOrInsertFunction(0); 78} 79 80CallGraph::~CallGraph() { 81 if (!FunctionMap.empty()) { 82 for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 83 I != E; ++I) 84 delete I->second; 85 FunctionMap.clear(); 86 } 87} 88 89void CallGraph::addToCallGraph(Decl* D, bool IsGlobal) { 90 assert(D); 91 CallGraphNode *Node = getOrInsertFunction(D); 92 93 if (IsGlobal) 94 Root->addCallee(Node, this); 95 96 // Process all the calls by this function as well. 97 CGBuilder builder(this, D, Node); 98 builder.Visit(D->getBody()); 99} 100 101void CallGraph::addToCallGraph(DeclContext *DC) { 102 for (DeclContext::decl_iterator I = DC->decls_begin(), E = DC->decls_end(); 103 I != E; ++I) { 104 Decl *D = *I; 105 switch (D->getKind()) { 106 case Decl::CXXConstructor: 107 case Decl::CXXDestructor: 108 case Decl::CXXConversion: 109 case Decl::CXXMethod: 110 case Decl::Function: { 111 FunctionDecl *FD = cast<FunctionDecl>(D); 112 // We skip function template definitions, as their semantics is 113 // only determined when they are instantiated. 114 if (includeInGraph(FD)) 115 // If this function has external linkage, anything could call it. 116 // Note, we are not precise here. For example, the function could have 117 // its address taken. 118 addToCallGraph(FD, FD->isGlobal()); 119 break; 120 } 121 122 case Decl::ObjCCategoryImpl: 123 case Decl::ObjCImplementation: { 124 ObjCImplDecl *ID = cast<ObjCImplDecl>(D); 125 for (ObjCContainerDecl::method_iterator MI = ID->meth_begin(), 126 ME = ID->meth_end(); MI != ME; ++MI) { 127 if (includeInGraph(*MI)) 128 addToCallGraph(*MI, true); 129 } 130 break; 131 } 132 133 default: 134 break; 135 } 136 } 137} 138 139CallGraphNode *CallGraph::getOrInsertFunction(Decl *F) { 140 CallGraphNode *&Node = FunctionMap[F]; 141 if (Node) 142 return Node; 143 144 Node = new CallGraphNode(F); 145 // If not root, add to the parentless list. 146 if (F != 0) 147 ParentlessNodes.insert(Node); 148 return Node; 149} 150 151void CallGraph::print(raw_ostream &OS) const { 152 OS << " --- Call graph Dump --- \n"; 153 for (const_iterator I = begin(), E = end(); I != E; ++I) { 154 OS << " Function: "; 155 if (I->second == Root) 156 OS << "< root >"; 157 else 158 I->second->print(OS); 159 OS << " calls: "; 160 for (CallGraphNode::iterator CI = I->second->begin(), 161 CE = I->second->end(); CI != CE; ++CI) { 162 assert(*CI != Root && "No one can call the root node."); 163 (*CI)->print(OS); 164 OS << " "; 165 } 166 OS << '\n'; 167 } 168 OS.flush(); 169} 170 171void CallGraph::dump() const { 172 print(llvm::errs()); 173} 174 175void CallGraph::viewGraph() const { 176 llvm::ViewGraph(this, "CallGraph"); 177} 178 179StringRef CallGraphNode::getName() const { 180 if (const FunctionDecl *D = dyn_cast_or_null<FunctionDecl>(FD)) 181 if (const IdentifierInfo *II = D->getIdentifier()) 182 return II->getName(); 183 return "< >"; 184} 185 186void CallGraphNode::print(raw_ostream &os) const { 187 os << getName(); 188} 189 190void CallGraphNode::dump() const { 191 print(llvm::errs()); 192} 193 194namespace llvm { 195 196template <> 197struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits { 198 199 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 200 201 static std::string getNodeLabel(const CallGraphNode *Node, 202 const CallGraph *CG) { 203 if (CG->getRoot() == Node) { 204 return "< root >"; 205 } 206 return Node->getName(); 207 } 208 209}; 210} 211