contrib/llvm/tools/clang/lib/Analysis/CallGraph.cpp

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