clang-tools-extra/clang-move/HelperDeclRefGraph.cpp

   1 //===-- HelperDeclRefGraph.cpp - AST-based call graph for helper decls ----===//
   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 #include "HelperDeclRefGraph.h"
  10 #include "Move.h"
  11 #include "clang/AST/Decl.h"
  12 #include "llvm/Support/Debug.h"
  13 #include <vector>
  14
  15 #define DEBUG_TYPE "clang-move"
  16
  17 namespace clang {
  18 namespace move {
  19
  20 void HelperDeclRefGraph::print(raw_ostream &OS) const {
  21   OS << " --- Call graph Dump --- \n";
  22   for (auto I = DeclMap.begin(); I != DeclMap.end(); ++I) {
  23     const CallGraphNode *N = (I->second).get();
  24
  25     OS << "  Declarations: ";
  26     N->print(OS);
  27     OS << " (" << N << ") ";
  28     OS << " calls: ";
  29     for (auto CI = N->begin(), CE = N->end(); CI != CE; ++CI) {
  30       CI->Callee->print(OS);
  31       OS << " (" << CI << ") ";
  32     }
  33     OS << '\n';
  34   }
  35   OS.flush();
  36 }
  37
  38 void HelperDeclRefGraph::addEdge(const Decl *Caller, const Decl *Callee) {
  39   assert(Caller);
  40   assert(Callee);
  41
  42   // Ignore the case where Caller equals Callee. This happens in the static
  43   // class member definitions in global namespace like "int CLASS::static_var =
  44   // 1;", its DC is a VarDel whose outmost enclosing declaration is the "CLASS"
  45   // CXXRecordDecl.
  46   if (Caller == Callee) return;
  47
  48   // Allocate a new node, mark it as root, and process it's calls.
  49   CallGraphNode *CallerNode = getOrInsertNode(const_cast<Decl *>(Caller));
  50   CallGraphNode *CalleeNode = getOrInsertNode(const_cast<Decl *>(Callee));
  51   CallerNode->addCallee({CalleeNode, /*CallExpr=*/nullptr});
  52 }
  53
  54 void HelperDeclRefGraph::dump() const { print(llvm::errs()); }
  55
  56 CallGraphNode *HelperDeclRefGraph::getOrInsertNode(Decl *F) {
  57   F = F->getCanonicalDecl();
  58   std::unique_ptr<CallGraphNode> &Node = DeclMap[F];
  59   if (Node)
  60     return Node.get();
  61
  62   Node = std::make_unique<CallGraphNode>(F);
  63   return Node.get();
  64 }
  65
  66 CallGraphNode *HelperDeclRefGraph::getNode(const Decl *D) const {
  67   auto I = DeclMap.find(D->getCanonicalDecl());
  68   return I == DeclMap.end() ? nullptr : I->second.get();
  69 }
  70
  71 llvm::DenseSet<const CallGraphNode *>
  72 HelperDeclRefGraph::getReachableNodes(const Decl *Root) const {
  73   const auto *RootNode = getNode(Root);
  74   if (!RootNode)
  75     return {};
  76   llvm::DenseSet<const CallGraphNode *> ConnectedNodes;
  77   std::function<void(const CallGraphNode *)> VisitNode =
  78       [&](const CallGraphNode *Node) {
  79         if (!ConnectedNodes.insert(Node).second)
  80           return;
  81         for (const CallGraphNode::CallRecord &Callee : *Node)
  82           VisitNode(Callee);
  83       };
  84
  85   VisitNode(RootNode);
  86   return ConnectedNodes;
  87 }
  88
  89 const Decl *HelperDeclRGBuilder::getOutmostClassOrFunDecl(const Decl *D) {
  90   const auto *DC = D->getDeclContext();
  91   const auto *Result = D;
  92   while (DC) {
  93     if (const auto *RD = dyn_cast<CXXRecordDecl>(DC))
  94       Result = RD;
  95     else if (const auto *FD = dyn_cast<FunctionDecl>(DC))
  96       Result = FD;
  97     DC = DC->getParent();
  98   }
  99   return Result;
 100 }
 101
 102 void HelperDeclRGBuilder::run(
 103     const ast_matchers::MatchFinder::MatchResult &Result) {
 104   // Construct the graph by adding a directed edge from caller to callee.
 105   //
 106   // "dc" is the closest ancestor declaration of "func_ref" or "used_class", it
 107   // might be not the targetted Caller Decl, we always use the outmost enclosing
 108   // FunctionDecl/CXXRecordDecl of "dc". For example,
 109   //
 110   //   int MoveClass::F() { int a = helper(); return a; }
 111   //
 112   // The matched "dc" of "helper" DeclRefExpr is a VarDecl, we traverse up AST
 113   // to find the outmost "MoveClass" CXXRecordDecl and use it as Caller.
 114   if (const auto *FuncRef = Result.Nodes.getNodeAs<DeclRefExpr>("func_ref")) {
 115     const auto *DC = Result.Nodes.getNodeAs<Decl>("dc");
 116     assert(DC);
 117     LLVM_DEBUG(llvm::dbgs() << "Find helper function usage: "
 118                             << FuncRef->getDecl()->getDeclName() << " ("
 119                             << FuncRef->getDecl() << ")\n");
 120     RG->addEdge(
 121         getOutmostClassOrFunDecl(DC->getCanonicalDecl()),
 122         getOutmostClassOrFunDecl(FuncRef->getDecl()->getCanonicalDecl()));
 123   } else if (const auto *UsedClass =
 124                  Result.Nodes.getNodeAs<CXXRecordDecl>("used_class")) {
 125     const auto *DC = Result.Nodes.getNodeAs<Decl>("dc");
 126     assert(DC);
 127     LLVM_DEBUG(llvm::dbgs()
 128                << "Find helper class usage: " << UsedClass->getDeclName()
 129                << " (" << UsedClass << ")\n");
 130     RG->addEdge(getOutmostClassOrFunDecl(DC->getCanonicalDecl()), UsedClass);
 131   }
 132 }
 133
 134 } // namespace move
 135 } // namespace clang