clang/lib/Analysis/CallGraph.cpp

   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
  35 using namespace clang;
  36
  37 #define DEBUG_TYPE "CallGraph"
  38
  39 STATISTIC(NumObjCCallEdges, "Number of Objective-C method call edges");
  40 STATISTIC(NumBlockCallEdges, "Number of block call edges");
  41
  42 namespace {
  43
  44 /// A helper class, which walks the AST and locates all the call sites in the
  45 /// given function body.
  46 class CGBuilder : public StmtVisitor<CGBuilder> {
  47   CallGraph *G;
  48   CallGraphNode *CallerNode;
  49
  50 public:
  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
 140 void 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
 149 CallGraph::CallGraph() {
 150   Root = getOrInsertNode(nullptr);
 151 }
 152
 153 CallGraph::~CallGraph() = default;
 154
 155 bool CallGraph::includeInGraph(const Decl *D) {
 156   assert(D);
 157   if (!D->hasBody())
 158     return false;
 159
 160   return includeCalleeInGraph(D);
 161 }
 162
 163 bool 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
 178 void 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
 197 CallGraphNode *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
 203 CallGraphNode *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
 218 void 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
 246 LLVM_DUMP_METHOD void CallGraph::dump() const {
 247   print(llvm::errs());
 248 }
 249
 250 void CallGraph::viewGraph() const {
 251   llvm::ViewGraph(this, "CallGraph");
 252 }
 253
 254 void 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
 260 LLVM_DUMP_METHOD void CallGraphNode::dump() const {
 261   print(llvm::errs());
 262 }
 263
 264 namespace llvm {
 265
 266 template <>
 267 struct 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