CallGraph.h revision 360784
1//===- CallGraph.h - AST-based Call graph -----------------------*- C++ -*-===// 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 declares the AST-based CallGraph. 10// 11// A call graph for functions whose definitions/bodies are available in the 12// current translation unit. The graph has a "virtual" root node that contains 13// edges to all externally available functions. 14// 15//===----------------------------------------------------------------------===// 16 17#ifndef LLVM_CLANG_ANALYSIS_CALLGRAPH_H 18#define LLVM_CLANG_ANALYSIS_CALLGRAPH_H 19 20#include "clang/AST/Decl.h" 21#include "clang/AST/RecursiveASTVisitor.h" 22#include "llvm/ADT/DenseMap.h" 23#include "llvm/ADT/GraphTraits.h" 24#include "llvm/ADT/STLExtras.h" 25#include "llvm/ADT/SetVector.h" 26#include "llvm/ADT/SmallVector.h" 27#include <memory> 28 29namespace clang { 30 31class CallGraphNode; 32class Decl; 33class DeclContext; 34class Stmt; 35 36/// The AST-based call graph. 37/// 38/// The call graph extends itself with the given declarations by implementing 39/// the recursive AST visitor, which constructs the graph by visiting the given 40/// declarations. 41class CallGraph : public RecursiveASTVisitor<CallGraph> { 42 friend class CallGraphNode; 43 44 using FunctionMapTy = 45 llvm::DenseMap<const Decl *, std::unique_ptr<CallGraphNode>>; 46 47 /// FunctionMap owns all CallGraphNodes. 48 FunctionMapTy FunctionMap; 49 50 /// This is a virtual root node that has edges to all the functions. 51 CallGraphNode *Root; 52 53public: 54 CallGraph(); 55 ~CallGraph(); 56 57 /// Populate the call graph with the functions in the given 58 /// declaration. 59 /// 60 /// Recursively walks the declaration to find all the dependent Decls as well. 61 void addToCallGraph(Decl *D) { 62 TraverseDecl(D); 63 } 64 65 /// Determine if a declaration should be included in the graph. 66 static bool includeInGraph(const Decl *D); 67 68 /// Lookup the node for the given declaration. 69 CallGraphNode *getNode(const Decl *) const; 70 71 /// Lookup the node for the given declaration. If none found, insert 72 /// one into the graph. 73 CallGraphNode *getOrInsertNode(Decl *); 74 75 using iterator = FunctionMapTy::iterator; 76 using const_iterator = FunctionMapTy::const_iterator; 77 78 /// Iterators through all the elements in the graph. Note, this gives 79 /// non-deterministic order. 80 iterator begin() { return FunctionMap.begin(); } 81 iterator end() { return FunctionMap.end(); } 82 const_iterator begin() const { return FunctionMap.begin(); } 83 const_iterator end() const { return FunctionMap.end(); } 84 85 /// Get the number of nodes in the graph. 86 unsigned size() const { return FunctionMap.size(); } 87 88 /// \ brief Get the virtual root of the graph, all the functions available 89 /// externally are represented as callees of the node. 90 CallGraphNode *getRoot() const { return Root; } 91 92 /// Iterators through all the nodes of the graph that have no parent. These 93 /// are the unreachable nodes, which are either unused or are due to us 94 /// failing to add a call edge due to the analysis imprecision. 95 using nodes_iterator = llvm::SetVector<CallGraphNode *>::iterator; 96 using const_nodes_iterator = llvm::SetVector<CallGraphNode *>::const_iterator; 97 98 void print(raw_ostream &os) const; 99 void dump() const; 100 void viewGraph() const; 101 102 void addNodesForBlocks(DeclContext *D); 103 104 /// Part of recursive declaration visitation. We recursively visit all the 105 /// declarations to collect the root functions. 106 bool VisitFunctionDecl(FunctionDecl *FD) { 107 // We skip function template definitions, as their semantics is 108 // only determined when they are instantiated. 109 if (includeInGraph(FD) && FD->isThisDeclarationADefinition()) { 110 // Add all blocks declared inside this function to the graph. 111 addNodesForBlocks(FD); 112 // If this function has external linkage, anything could call it. 113 // Note, we are not precise here. For example, the function could have 114 // its address taken. 115 addNodeForDecl(FD, FD->isGlobal()); 116 } 117 return true; 118 } 119 120 /// Part of recursive declaration visitation. 121 bool VisitObjCMethodDecl(ObjCMethodDecl *MD) { 122 if (includeInGraph(MD)) { 123 addNodesForBlocks(MD); 124 addNodeForDecl(MD, true); 125 } 126 return true; 127 } 128 129 // We are only collecting the declarations, so do not step into the bodies. 130 bool TraverseStmt(Stmt *S) { return true; } 131 132 bool shouldWalkTypesOfTypeLocs() const { return false; } 133 bool shouldVisitTemplateInstantiations() const { return true; } 134 bool shouldVisitImplicitCode() const { return true; } 135 136private: 137 /// Add the given declaration to the call graph. 138 void addNodeForDecl(Decl *D, bool IsGlobal); 139 140 /// Allocate a new node in the graph. 141 CallGraphNode *allocateNewNode(Decl *); 142}; 143 144class CallGraphNode { 145public: 146 using CallRecord = CallGraphNode *; 147 148private: 149 /// The function/method declaration. 150 Decl *FD; 151 152 /// The list of functions called from this node. 153 SmallVector<CallRecord, 5> CalledFunctions; 154 155public: 156 CallGraphNode(Decl *D) : FD(D) {} 157 158 using iterator = SmallVectorImpl<CallRecord>::iterator; 159 using const_iterator = SmallVectorImpl<CallRecord>::const_iterator; 160 161 /// Iterators through all the callees/children of the node. 162 iterator begin() { return CalledFunctions.begin(); } 163 iterator end() { return CalledFunctions.end(); } 164 const_iterator begin() const { return CalledFunctions.begin(); } 165 const_iterator end() const { return CalledFunctions.end(); } 166 167 bool empty() const { return CalledFunctions.empty(); } 168 unsigned size() const { return CalledFunctions.size(); } 169 170 void addCallee(CallGraphNode *N) { 171 CalledFunctions.push_back(N); 172 } 173 174 Decl *getDecl() const { return FD; } 175 176 void print(raw_ostream &os) const; 177 void dump() const; 178}; 179 180} // namespace clang 181 182// Graph traits for iteration, viewing. 183namespace llvm { 184 185template <> struct GraphTraits<clang::CallGraphNode*> { 186 using NodeType = clang::CallGraphNode; 187 using NodeRef = clang::CallGraphNode *; 188 using ChildIteratorType = NodeType::iterator; 189 190 static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; } 191 static ChildIteratorType child_begin(NodeType *N) { return N->begin(); } 192 static ChildIteratorType child_end(NodeType *N) { return N->end(); } 193}; 194 195template <> struct GraphTraits<const clang::CallGraphNode*> { 196 using NodeType = const clang::CallGraphNode; 197 using NodeRef = const clang::CallGraphNode *; 198 using ChildIteratorType = NodeType::const_iterator; 199 200 static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; } 201 static ChildIteratorType child_begin(NodeType *N) { return N->begin();} 202 static ChildIteratorType child_end(NodeType *N) { return N->end(); } 203}; 204 205template <> struct GraphTraits<clang::CallGraph*> 206 : public GraphTraits<clang::CallGraphNode*> { 207 static NodeType *getEntryNode(clang::CallGraph *CGN) { 208 return CGN->getRoot(); // Start at the external node! 209 } 210 211 static clang::CallGraphNode * 212 CGGetValue(clang::CallGraph::const_iterator::value_type &P) { 213 return P.second.get(); 214 } 215 216 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 217 using nodes_iterator = 218 mapped_iterator<clang::CallGraph::iterator, decltype(&CGGetValue)>; 219 220 static nodes_iterator nodes_begin(clang::CallGraph *CG) { 221 return nodes_iterator(CG->begin(), &CGGetValue); 222 } 223 224 static nodes_iterator nodes_end (clang::CallGraph *CG) { 225 return nodes_iterator(CG->end(), &CGGetValue); 226 } 227 228 static unsigned size(clang::CallGraph *CG) { return CG->size(); } 229}; 230 231template <> struct GraphTraits<const clang::CallGraph*> : 232 public GraphTraits<const clang::CallGraphNode*> { 233 static NodeType *getEntryNode(const clang::CallGraph *CGN) { 234 return CGN->getRoot(); 235 } 236 237 static clang::CallGraphNode * 238 CGGetValue(clang::CallGraph::const_iterator::value_type &P) { 239 return P.second.get(); 240 } 241 242 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 243 using nodes_iterator = 244 mapped_iterator<clang::CallGraph::const_iterator, decltype(&CGGetValue)>; 245 246 static nodes_iterator nodes_begin(const clang::CallGraph *CG) { 247 return nodes_iterator(CG->begin(), &CGGetValue); 248 } 249 250 static nodes_iterator nodes_end(const clang::CallGraph *CG) { 251 return nodes_iterator(CG->end(), &CGGetValue); 252 } 253 254 static unsigned size(const clang::CallGraph *CG) { return CG->size(); } 255}; 256 257} // namespace llvm 258 259#endif // LLVM_CLANG_ANALYSIS_CALLGRAPH_H 260