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   ShouldWalkTypesOfTypeLocs = false;
 151   ShouldVisitTemplateInstantiations = true;
 152   ShouldVisitImplicitCode = true;
 153   Root = getOrInsertNode(nullptr);
 154 }
 155
 156 CallGraph::~CallGraph() = default;
 157
 158 bool CallGraph::includeInGraph(const Decl *D) {
 159   assert(D);
 160   if (!D->hasBody())
 161     return false;
 162
 163   return includeCalleeInGraph(D);
 164 }
 165
 166 bool CallGraph::includeCalleeInGraph(const Decl *D) {
 167   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
 168     // We skip function template definitions, as their semantics is
 169     // only determined when they are instantiated.
 170     if (FD->isDependentContext())
 171       return false;
 172
 173     IdentifierInfo *II = FD->getIdentifier();
 174     if (II && II->getName().starts_with("__inline"))
 175       return false;
 176   }
 177
 178   return true;
 179 }
 180
 181 void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) {
 182   assert(D);
 183
 184   // Allocate a new node, mark it as root, and process its calls.
 185   CallGraphNode *Node = getOrInsertNode(D);
 186
 187   // Process all the calls by this function as well.
 188   CGBuilder builder(this, Node);
 189   if (Stmt *Body = D->getBody())
 190     builder.Visit(Body);
 191
 192   // Include C++ constructor member initializers.
 193   if (auto constructor = dyn_cast<CXXConstructorDecl>(D)) {
 194     for (CXXCtorInitializer *init : constructor->inits()) {
 195       builder.Visit(init->getInit());
 196     }
 197   }
 198 }
 199
 200 CallGraphNode *CallGraph::getNode(const Decl *F) const {
 201   FunctionMapTy::const_iterator I = FunctionMap.find(F);
 202   if (I == FunctionMap.end()) return nullptr;
 203   return I->second.get();
 204 }
 205
 206 CallGraphNode *CallGraph::getOrInsertNode(Decl *F) {
 207   if (F && !isa<ObjCMethodDecl>(F))
 208     F = F->getCanonicalDecl();
 209
 210   std::unique_ptr<CallGraphNode> &Node = FunctionMap[F];
 211   if (Node)
 212     return Node.get();
 213
 214   Node = std::make_unique<CallGraphNode>(F);
 215   // Make Root node a parent of all functions to make sure all are reachable.
 216   if (F)
 217     Root->addCallee({Node.get(), /*Call=*/nullptr});
 218   return Node.get();
 219 }
 220
 221 void CallGraph::print(raw_ostream &OS) const {
 222   OS << " --- Call graph Dump --- \n";
 223
 224   // We are going to print the graph in reverse post order, partially, to make
 225   // sure the output is deterministic.
 226   llvm::ReversePostOrderTraversal<const CallGraph *> RPOT(this);
 227   for (llvm::ReversePostOrderTraversal<const CallGraph *>::rpo_iterator
 228          I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
 229     const CallGraphNode *N = *I;
 230
 231     OS << "  Function: ";
 232     if (N == Root)
 233       OS << "< root >";
 234     else
 235       N->print(OS);
 236
 237     OS << " calls: ";
 238     for (CallGraphNode::const_iterator CI = N->begin(),
 239                                        CE = N->end(); CI != CE; ++CI) {
 240       assert(CI->Callee != Root && "No one can call the root node.");
 241       CI->Callee->print(OS);
 242       OS << " ";
 243     }
 244     OS << '\n';
 245   }
 246   OS.flush();
 247 }
 248
 249 LLVM_DUMP_METHOD void CallGraph::dump() const {
 250   print(llvm::errs());
 251 }
 252
 253 void CallGraph::viewGraph() const {
 254   llvm::ViewGraph(this, "CallGraph");
 255 }
 256
 257 void CallGraphNode::print(raw_ostream &os) const {
 258   if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(FD))
 259       return ND->printQualifiedName(os);
 260   os << "< >";
 261 }
 262
 263 LLVM_DUMP_METHOD void CallGraphNode::dump() const {
 264   print(llvm::errs());
 265 }
 266
 267 namespace llvm {
 268
 269 template <>
 270 struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits {
 271   DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
 272
 273   static std::string getNodeLabel(const CallGraphNode *Node,
 274                                   const CallGraph *CG) {
 275     if (CG->getRoot() == Node) {
 276       return "< root >";
 277     }
 278     if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Node->getDecl()))
 279       return ND->getNameAsString();
 280     else
 281       return "< >";
 282   }
 283 };
 284
 285 } // namespace llvm