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/PostOrderIterator.h" 20 #include "llvm/ADT/Statistic.h" 21 #include "llvm/Support/GraphWriter.h" 22 23 using namespace clang; 24 25 STATISTIC(NumObjCCallEdges, "Number of Objective-C method call edges"); 26 STATISTIC(NumBlockCallEdges, "Number of block call edges"); 27 28 namespace { 29 /// A helper class, which walks the AST and locates all the call sites in the 30 /// given function body. 31 class CGBuilder : public StmtVisitor<CGBuilder> { 32 CallGraph *G; 33 CallGraphNode *CallerNode; 34 35 public: 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 0; 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 = 0; 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::child_range I = S->children(); I; ++I) 87 if (*I) 88 static_cast<CGBuilder*>(this)->Visit(*I); 89 } 90 }; 91 92 } // end anonymous namespace 93 94 void CallGraph::addNodesForBlocks(DeclContext *D) { 95 if (BlockDecl *BD = dyn_cast<BlockDecl>(D)) 96 addNodeForDecl(BD, true); 97 98 for (DeclContext::decl_iterator I = D->decls_begin(), E = D->decls_end(); 99 I!=E; ++I) 100 if (DeclContext *DC = dyn_cast<DeclContext>(*I)) 101 addNodesForBlocks(DC); 102 } 103 104 CallGraph::CallGraph() { 105 Root = getOrInsertNode(0); 106 } 107 108 CallGraph::~CallGraph() { 109 if (!FunctionMap.empty()) { 110 for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 111 I != E; ++I) 112 delete I->second; 113 FunctionMap.clear(); 114 } 115 } 116 117 bool CallGraph::includeInGraph(const Decl *D) { 118 assert(D); 119 if (!D->getBody()) 120 return false; 121 122 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 123 // We skip function template definitions, as their semantics is 124 // only determined when they are instantiated. 125 if (!FD->isThisDeclarationADefinition() || 126 FD->isDependentContext()) 127 return false; 128 129 IdentifierInfo *II = FD->getIdentifier(); 130 if (II && II->getName().startswith("__inline")) 131 return false; 132 } 133 134 if (const ObjCMethodDecl *ID = dyn_cast<ObjCMethodDecl>(D)) { 135 if (!ID->isThisDeclarationADefinition()) 136 return false; 137 } 138 139 return true; 140 } 141 142 void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) { 143 assert(D); 144 145 // Allocate a new node, mark it as root, and process it's calls. 146 CallGraphNode *Node = getOrInsertNode(D); 147 148 // Process all the calls by this function as well. 149 CGBuilder builder(this, Node); 150 if (Stmt *Body = D->getBody()) 151 builder.Visit(Body); 152 } 153 154 CallGraphNode *CallGraph::getNode(const Decl *F) const { 155 FunctionMapTy::const_iterator I = FunctionMap.find(F); 156 if (I == FunctionMap.end()) return 0; 157 return I->second; 158 } 159 160 CallGraphNode *CallGraph::getOrInsertNode(Decl *F) { 161 CallGraphNode *&Node = FunctionMap[F]; 162 if (Node) 163 return Node; 164 165 Node = new CallGraphNode(F); 166 // Make Root node a parent of all functions to make sure all are reachable. 167 if (F != 0) 168 Root->addCallee(Node, this); 169 return Node; 170 } 171 172 void CallGraph::print(raw_ostream &OS) const { 173 OS << " --- Call graph Dump --- \n"; 174 175 // We are going to print the graph in reverse post order, partially, to make 176 // sure the output is deterministic. 177 llvm::ReversePostOrderTraversal<const clang::CallGraph*> RPOT(this); 178 for (llvm::ReversePostOrderTraversal<const clang::CallGraph*>::rpo_iterator 179 I = RPOT.begin(), E = RPOT.end(); I != E; ++I) { 180 const CallGraphNode *N = *I; 181 182 OS << " Function: "; 183 if (N == Root) 184 OS << "< root >"; 185 else 186 N->print(OS); 187 188 OS << " calls: "; 189 for (CallGraphNode::const_iterator CI = N->begin(), 190 CE = N->end(); CI != CE; ++CI) { 191 assert(*CI != Root && "No one can call the root node."); 192 (*CI)->print(OS); 193 OS << " "; 194 } 195 OS << '\n'; 196 } 197 OS.flush(); 198 } 199 200 void CallGraph::dump() const { 201 print(llvm::errs()); 202 } 203 204 void CallGraph::viewGraph() const { 205 llvm::ViewGraph(this, "CallGraph"); 206 } 207 208 void CallGraphNode::print(raw_ostream &os) const { 209 if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(FD)) 210 return ND->printName(os); 211 os << "< >"; 212 } 213 214 void CallGraphNode::dump() const { 215 print(llvm::errs()); 216 } 217 218 namespace llvm { 219 220 template <> 221 struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits { 222 223 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 224 225 static std::string getNodeLabel(const CallGraphNode *Node, 226 const CallGraph *CG) { 227 if (CG->getRoot() == Node) { 228 return "< root >"; 229 } 230 if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Node->getDecl())) 231 return ND->getNameAsString(); 232 else 233 return "< >"; 234 } 235 236 }; 237 } 238