1//===- CallGraph.cpp - AST-based Call graph -------------------------------===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8// 9// This file defines the AST-based CallGraph. 10// 11//===----------------------------------------------------------------------===// 12 13#include "clang/Analysis/CallGraph.h" 14#include "clang/AST/Decl.h" 15#include "clang/AST/DeclBase.h" 16#include "clang/AST/DeclObjC.h" 17#include "clang/AST/Expr.h" 18#include "clang/AST/ExprObjC.h" 19#include "clang/AST/Stmt.h" 20#include "clang/AST/StmtVisitor.h" 21#include "clang/Basic/IdentifierTable.h" 22#include "clang/Basic/LLVM.h" 23#include "llvm/ADT/PostOrderIterator.h" 24#include "llvm/ADT/STLExtras.h" 25#include "llvm/ADT/Statistic.h" 26#include "llvm/Support/Casting.h" 27#include "llvm/Support/Compiler.h" 28#include "llvm/Support/DOTGraphTraits.h" 29#include "llvm/Support/GraphWriter.h" 30#include "llvm/Support/raw_ostream.h" 31#include <cassert> 32#include <memory> 33#include <string> 34 35using namespace clang; 36 37#define DEBUG_TYPE "CallGraph" 38 39STATISTIC(NumObjCCallEdges, "Number of Objective-C method call edges"); 40STATISTIC(NumBlockCallEdges, "Number of block call edges"); 41 42namespace { 43 44/// A helper class, which walks the AST and locates all the call sites in the 45/// given function body. 46class CGBuilder : public StmtVisitor<CGBuilder> { 47 CallGraph *G; 48 CallGraphNode *CallerNode; 49 50public: 51 CGBuilder(CallGraph *g, CallGraphNode *N) : G(g), CallerNode(N) {} 52 53 void VisitStmt(Stmt *S) { VisitChildren(S); } 54 55 Decl *getDeclFromCall(CallExpr *CE) { 56 if (FunctionDecl *CalleeDecl = CE->getDirectCallee()) 57 return CalleeDecl; 58 59 // Simple detection of a call through a block. 60 Expr *CEE = CE->getCallee()->IgnoreParenImpCasts(); 61 if (BlockExpr *Block = dyn_cast<BlockExpr>(CEE)) { 62 NumBlockCallEdges++; 63 return Block->getBlockDecl(); 64 } 65 66 return nullptr; 67 } 68 69 void addCalledDecl(Decl *D, Expr *CallExpr) { 70 if (G->includeCalleeInGraph(D)) { 71 CallGraphNode *CalleeNode = G->getOrInsertNode(D); 72 CallerNode->addCallee({CalleeNode, CallExpr}); 73 } 74 } 75 76 void VisitCallExpr(CallExpr *CE) { 77 if (Decl *D = getDeclFromCall(CE)) 78 addCalledDecl(D, CE); 79 VisitChildren(CE); 80 } 81 82 void VisitLambdaExpr(LambdaExpr *LE) { 83 if (FunctionTemplateDecl *FTD = LE->getDependentCallOperator()) 84 for (FunctionDecl *FD : FTD->specializations()) 85 G->VisitFunctionDecl(FD); 86 else if (CXXMethodDecl *MD = LE->getCallOperator()) 87 G->VisitFunctionDecl(MD); 88 } 89 90 void VisitCXXNewExpr(CXXNewExpr *E) { 91 if (FunctionDecl *FD = E->getOperatorNew()) 92 addCalledDecl(FD, E); 93 VisitChildren(E); 94 } 95 96 void VisitCXXConstructExpr(CXXConstructExpr *E) { 97 CXXConstructorDecl *Ctor = E->getConstructor(); 98 if (FunctionDecl *Def = Ctor->getDefinition()) 99 addCalledDecl(Def, E); 100 VisitChildren(E); 101 } 102 103 // Include the evaluation of the default argument. 104 void VisitCXXDefaultArgExpr(CXXDefaultArgExpr *E) { 105 Visit(E->getExpr()); 106 } 107 108 // Include the evaluation of the default initializers in a class. 109 void VisitCXXDefaultInitExpr(CXXDefaultInitExpr *E) { 110 Visit(E->getExpr()); 111 } 112 113 // Adds may-call edges for the ObjC message sends. 114 void VisitObjCMessageExpr(ObjCMessageExpr *ME) { 115 if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) { 116 Selector Sel = ME->getSelector(); 117 118 // Find the callee definition within the same translation unit. 119 Decl *D = nullptr; 120 if (ME->isInstanceMessage()) 121 D = IDecl->lookupPrivateMethod(Sel); 122 else 123 D = IDecl->lookupPrivateClassMethod(Sel); 124 if (D) { 125 addCalledDecl(D, ME); 126 NumObjCCallEdges++; 127 } 128 } 129 } 130 131 void VisitChildren(Stmt *S) { 132 for (Stmt *SubStmt : S->children()) 133 if (SubStmt) 134 this->Visit(SubStmt); 135 } 136}; 137 138} // namespace 139 140void CallGraph::addNodesForBlocks(DeclContext *D) { 141 if (BlockDecl *BD = dyn_cast<BlockDecl>(D)) 142 addNodeForDecl(BD, true); 143 144 for (auto *I : D->decls()) 145 if (auto *DC = dyn_cast<DeclContext>(I)) 146 addNodesForBlocks(DC); 147} 148 149CallGraph::CallGraph() { 150 Root = getOrInsertNode(nullptr); 151} 152 153CallGraph::~CallGraph() = default; 154 155bool CallGraph::includeInGraph(const Decl *D) { 156 assert(D); 157 if (!D->hasBody()) 158 return false; 159 160 return includeCalleeInGraph(D); 161} 162 163bool CallGraph::includeCalleeInGraph(const Decl *D) { 164 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 165 // We skip function template definitions, as their semantics is 166 // only determined when they are instantiated. 167 if (FD->isDependentContext()) 168 return false; 169 170 IdentifierInfo *II = FD->getIdentifier(); 171 if (II && II->getName().startswith("__inline")) 172 return false; 173 } 174 175 return true; 176} 177 178void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) { 179 assert(D); 180 181 // Allocate a new node, mark it as root, and process its calls. 182 CallGraphNode *Node = getOrInsertNode(D); 183 184 // Process all the calls by this function as well. 185 CGBuilder builder(this, Node); 186 if (Stmt *Body = D->getBody()) 187 builder.Visit(Body); 188 189 // Include C++ constructor member initializers. 190 if (auto constructor = dyn_cast<CXXConstructorDecl>(D)) { 191 for (CXXCtorInitializer *init : constructor->inits()) { 192 builder.Visit(init->getInit()); 193 } 194 } 195} 196 197CallGraphNode *CallGraph::getNode(const Decl *F) const { 198 FunctionMapTy::const_iterator I = FunctionMap.find(F); 199 if (I == FunctionMap.end()) return nullptr; 200 return I->second.get(); 201} 202 203CallGraphNode *CallGraph::getOrInsertNode(Decl *F) { 204 if (F && !isa<ObjCMethodDecl>(F)) 205 F = F->getCanonicalDecl(); 206 207 std::unique_ptr<CallGraphNode> &Node = FunctionMap[F]; 208 if (Node) 209 return Node.get(); 210 211 Node = std::make_unique<CallGraphNode>(F); 212 // Make Root node a parent of all functions to make sure all are reachable. 213 if (F) 214 Root->addCallee({Node.get(), /*Call=*/nullptr}); 215 return Node.get(); 216} 217 218void CallGraph::print(raw_ostream &OS) const { 219 OS << " --- Call graph Dump --- \n"; 220 221 // We are going to print the graph in reverse post order, partially, to make 222 // sure the output is deterministic. 223 llvm::ReversePostOrderTraversal<const CallGraph *> RPOT(this); 224 for (llvm::ReversePostOrderTraversal<const CallGraph *>::rpo_iterator 225 I = RPOT.begin(), E = RPOT.end(); I != E; ++I) { 226 const CallGraphNode *N = *I; 227 228 OS << " Function: "; 229 if (N == Root) 230 OS << "< root >"; 231 else 232 N->print(OS); 233 234 OS << " calls: "; 235 for (CallGraphNode::const_iterator CI = N->begin(), 236 CE = N->end(); CI != CE; ++CI) { 237 assert(CI->Callee != Root && "No one can call the root node."); 238 CI->Callee->print(OS); 239 OS << " "; 240 } 241 OS << '\n'; 242 } 243 OS.flush(); 244} 245 246LLVM_DUMP_METHOD void CallGraph::dump() const { 247 print(llvm::errs()); 248} 249 250void CallGraph::viewGraph() const { 251 llvm::ViewGraph(this, "CallGraph"); 252} 253 254void CallGraphNode::print(raw_ostream &os) const { 255 if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(FD)) 256 return ND->printQualifiedName(os); 257 os << "< >"; 258} 259 260LLVM_DUMP_METHOD void CallGraphNode::dump() const { 261 print(llvm::errs()); 262} 263 264namespace llvm { 265 266template <> 267struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits { 268 DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} 269 270 static std::string getNodeLabel(const CallGraphNode *Node, 271 const CallGraph *CG) { 272 if (CG->getRoot() == Node) { 273 return "< root >"; 274 } 275 if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Node->getDecl())) 276 return ND->getNameAsString(); 277 else 278 return "< >"; 279 } 280}; 281 282} // namespace llvm 283