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