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 136