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#include "clang/AST/ASTContext.h" 15#include "clang/AST/Decl.h" 16#include "clang/AST/StmtVisitor.h" 17#include "llvm/ADT/PostOrderIterator.h" 18#include "llvm/ADT/Statistic.h" 19#include "llvm/Support/GraphWriter.h" 20 21using namespace clang; 22 23#define DEBUG_TYPE "CallGraph" 24 25STATISTIC(NumObjCCallEdges, "Number of Objective-C method call edges"); 26STATISTIC(NumBlockCallEdges, "Number of block call edges"); 27 28namespace { 29/// A helper class, which walks the AST and locates all the call sites in the 30/// given function body. 31class CGBuilder : public StmtVisitor<CGBuilder> { 32 CallGraph *G; 33 CallGraphNode *CallerNode; 34 35public: 36 CGBuilder(CallGraph *g, CallGraphNode *N) 37 : G(g), CallerNode(N) {} 38 39 void VisitStmt(Stmt *S) { VisitChildren(S); } 40 41 Decl *getDeclFromCall(CallExpr *CE) { 42 if (FunctionDecl *CalleeDecl = CE->getDirectCallee()) 43 return CalleeDecl; 44 45 // Simple detection of a call through a block. 46 Expr *CEE = CE->getCallee()->IgnoreParenImpCasts(); 47 if (BlockExpr *Block = dyn_cast<BlockExpr>(CEE)) { 48 NumBlockCallEdges++; 49 return Block->getBlockDecl(); 50 } 51 52 return nullptr; 53 } 54 55 void addCalledDecl(Decl *D) { 56 if (G->includeInGraph(D)) { 57 CallGraphNode *CalleeNode = G->getOrInsertNode(D); 58 CallerNode->addCallee(CalleeNode, G); 59 } 60 } 61 62 void VisitCallExpr(CallExpr *CE) { 63 if (Decl *D = getDeclFromCall(CE)) 64 addCalledDecl(D); 65 } 66 67 // Adds may-call edges for the ObjC message sends. 68 void VisitObjCMessageExpr(ObjCMessageExpr *ME) { 69 if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) { 70 Selector Sel = ME->getSelector(); 71 72 // Find the callee definition within the same translation unit. 73 Decl *D = nullptr; 74 if (ME->isInstanceMessage()) 75 D = IDecl->lookupPrivateMethod(Sel); 76 else 77 D = IDecl->lookupPrivateClassMethod(Sel); 78 if (D) { 79 addCalledDecl(D); 80 NumObjCCallEdges++; 81 } 82 } 83 } 84 85 void VisitChildren(Stmt *S) { 86 for (Stmt *SubStmt : S->children()) 87 if (SubStmt) 88 this->Visit(SubStmt); 89 } 90}; 91 92} // end anonymous namespace 93 94void CallGraph::addNodesForBlocks(DeclContext *D) { 95 if (BlockDecl *BD = dyn_cast<BlockDecl>(D)) 96 addNodeForDecl(BD, true); 97 98 for (auto *I : D->decls()) 99 if (auto *DC = dyn_cast<DeclContext>(I)) 100 addNodesForBlocks(DC); 101} 102 103CallGraph::CallGraph() { 104 Root = getOrInsertNode(nullptr); 105} 106 107CallGraph::~CallGraph() { 108 llvm::DeleteContainerSeconds(FunctionMap); 109} 110 111bool CallGraph::includeInGraph(const Decl *D) { 112 assert(D); 113 if (!D->hasBody()) 114 return false; 115 116 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 117 // We skip function template definitions, as their semantics is 118 // only determined when they are instantiated. 119 if (FD->isDependentContext()) 120 return false; 121 122 IdentifierInfo *II = FD->getIdentifier(); 123 if (II && II->getName().startswith("__inline")) 124 return false; 125 } 126 127 return true; 128} 129 130void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) { 131 assert(D); 132 133 // Allocate a new node, mark it as root, and process it's calls. 134 CallGraphNode *Node = getOrInsertNode(D); 135 136 // Process all the calls by this function as well. 137 CGBuilder builder(this, Node); 138 if (Stmt *Body = D->getBody()) 139 builder.Visit(Body); 140} 141 142CallGraphNode *CallGraph::getNode(const Decl *F) const { 143 FunctionMapTy::const_iterator I = FunctionMap.find(F); 144 if (I == FunctionMap.end()) return nullptr; 145 return I->second; 146} 147 148CallGraphNode *CallGraph::getOrInsertNode(Decl *F) { 149 if (F && !isa<ObjCMethodDecl>(F)) 150 F = F->getCanonicalDecl(); 151 152 CallGraphNode *&Node = FunctionMap[F]; 153 if (Node) 154 return Node; 155 156 Node = new CallGraphNode(F); 157 // Make Root node a parent of all functions to make sure all are reachable. 158 if (F) 159 Root->addCallee(Node, this); 160 return Node; 161} 162 163void CallGraph::print(raw_ostream &OS) const { 164 OS << " --- Call graph Dump --- \n"; 165 166 // We are going to print the graph in reverse post order, partially, to make 167 // sure the output is deterministic. 168 llvm::ReversePostOrderTraversal<const clang::CallGraph*> RPOT(this); 169 for (llvm::ReversePostOrderTraversal<const clang::CallGraph*>::rpo_iterator 170 I = RPOT.begin(), E = RPOT.end(); I != E; ++I) { 171 const CallGraphNode *N = *I; 172 173 OS << " Function: "; 174 if (N == Root) 175 OS << "< root >"; 176 else 177 N->print(OS); 178 179 OS << " calls: "; 180 for (CallGraphNode::const_iterator CI = N->begin(), 181 CE = N->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