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 "llvm/ADT/iterator_range.h" 28 #include <memory> 29 30 namespace clang { 31 32 class CallGraphNode; 33 class Decl; 34 class DeclContext; 35 class Stmt; 36 37 /// The AST-based call graph. 38 /// 39 /// The call graph extends itself with the given declarations by implementing 40 /// the recursive AST visitor, which constructs the graph by visiting the given 41 /// declarations. 42 class CallGraph : public RecursiveASTVisitor<CallGraph> { 43 friend class CallGraphNode; 44 45 using FunctionMapTy = 46 llvm::DenseMap<const Decl *, std::unique_ptr<CallGraphNode>>; 47 48 /// FunctionMap owns all CallGraphNodes. 49 FunctionMapTy FunctionMap; 50 51 /// This is a virtual root node that has edges to all the functions. 52 CallGraphNode *Root; 53 54 public: 55 CallGraph(); 56 ~CallGraph(); 57 58 /// Populate the call graph with the functions in the given 59 /// declaration. 60 /// 61 /// Recursively walks the declaration to find all the dependent Decls as well. addToCallGraph(Decl * D)62 void addToCallGraph(Decl *D) { 63 TraverseDecl(D); 64 } 65 66 /// Determine if a declaration should be included in the graph. 67 static bool includeInGraph(const Decl *D); 68 69 /// Determine if a declaration should be included in the graph for the 70 /// purposes of being a callee. This is similar to includeInGraph except 71 /// it permits declarations, not just definitions. 72 static bool includeCalleeInGraph(const Decl *D); 73 74 /// Lookup the node for the given declaration. 75 CallGraphNode *getNode(const Decl *) const; 76 77 /// Lookup the node for the given declaration. If none found, insert 78 /// one into the graph. 79 CallGraphNode *getOrInsertNode(Decl *); 80 81 using iterator = FunctionMapTy::iterator; 82 using const_iterator = FunctionMapTy::const_iterator; 83 84 /// Iterators through all the elements in the graph. Note, this gives 85 /// non-deterministic order. begin()86 iterator begin() { return FunctionMap.begin(); } end()87 iterator end() { return FunctionMap.end(); } begin()88 const_iterator begin() const { return FunctionMap.begin(); } end()89 const_iterator end() const { return FunctionMap.end(); } 90 91 /// Get the number of nodes in the graph. size()92 unsigned size() const { return FunctionMap.size(); } 93 94 /// Get the virtual root of the graph, all the functions available externally 95 /// are represented as callees of the node. getRoot()96 CallGraphNode *getRoot() const { return Root; } 97 98 /// Iterators through all the nodes of the graph that have no parent. These 99 /// are the unreachable nodes, which are either unused or are due to us 100 /// failing to add a call edge due to the analysis imprecision. 101 using nodes_iterator = llvm::SetVector<CallGraphNode *>::iterator; 102 using const_nodes_iterator = llvm::SetVector<CallGraphNode *>::const_iterator; 103 104 void print(raw_ostream &os) const; 105 void dump() const; 106 void viewGraph() const; 107 108 void addNodesForBlocks(DeclContext *D); 109 110 /// Part of recursive declaration visitation. We recursively visit all the 111 /// declarations to collect the root functions. VisitFunctionDecl(FunctionDecl * FD)112 bool VisitFunctionDecl(FunctionDecl *FD) { 113 // We skip function template definitions, as their semantics is 114 // only determined when they are instantiated. 115 if (includeInGraph(FD) && FD->isThisDeclarationADefinition()) { 116 // Add all blocks declared inside this function to the graph. 117 addNodesForBlocks(FD); 118 // If this function has external linkage, anything could call it. 119 // Note, we are not precise here. For example, the function could have 120 // its address taken. 121 addNodeForDecl(FD, FD->isGlobal()); 122 } 123 return true; 124 } 125 126 /// Part of recursive declaration visitation. VisitObjCMethodDecl(ObjCMethodDecl * MD)127 bool VisitObjCMethodDecl(ObjCMethodDecl *MD) { 128 if (includeInGraph(MD)) { 129 addNodesForBlocks(MD); 130 addNodeForDecl(MD, true); 131 } 132 return true; 133 } 134 135 // We are only collecting the declarations, so do not step into the bodies. TraverseStmt(Stmt * S)136 bool TraverseStmt(Stmt *S) { return true; } 137 shouldWalkTypesOfTypeLocs()138 bool shouldWalkTypesOfTypeLocs() const { return false; } shouldVisitTemplateInstantiations()139 bool shouldVisitTemplateInstantiations() const { return true; } shouldVisitImplicitCode()140 bool shouldVisitImplicitCode() const { return true; } 141 142 private: 143 /// Add the given declaration to the call graph. 144 void addNodeForDecl(Decl *D, bool IsGlobal); 145 }; 146 147 class CallGraphNode { 148 public: 149 struct CallRecord { 150 CallGraphNode *Callee; 151 Expr *CallExpr; 152 153 CallRecord() = default; 154 CallRecordCallRecord155 CallRecord(CallGraphNode *Callee_, Expr *CallExpr_) 156 : Callee(Callee_), CallExpr(CallExpr_) {} 157 158 // The call destination is the only important data here, 159 // allow to transparently unwrap into it. 160 operator CallGraphNode *() const { return Callee; } 161 }; 162 163 private: 164 /// The function/method declaration. 165 Decl *FD; 166 167 /// The list of functions called from this node. 168 SmallVector<CallRecord, 5> CalledFunctions; 169 170 public: CallGraphNode(Decl * D)171 CallGraphNode(Decl *D) : FD(D) {} 172 173 using iterator = SmallVectorImpl<CallRecord>::iterator; 174 using const_iterator = SmallVectorImpl<CallRecord>::const_iterator; 175 176 /// Iterators through all the callees/children of the node. begin()177 iterator begin() { return CalledFunctions.begin(); } end()178 iterator end() { return CalledFunctions.end(); } begin()179 const_iterator begin() const { return CalledFunctions.begin(); } end()180 const_iterator end() const { return CalledFunctions.end(); } 181 182 /// Iterator access to callees/children of the node. callees()183 llvm::iterator_range<iterator> callees() { 184 return llvm::make_range(begin(), end()); 185 } callees()186 llvm::iterator_range<const_iterator> callees() const { 187 return llvm::make_range(begin(), end()); 188 } 189 empty()190 bool empty() const { return CalledFunctions.empty(); } size()191 unsigned size() const { return CalledFunctions.size(); } 192 addCallee(CallRecord Call)193 void addCallee(CallRecord Call) { CalledFunctions.push_back(Call); } 194 getDecl()195 Decl *getDecl() const { return FD; } 196 getDefinition()197 FunctionDecl *getDefinition() const { 198 return getDecl()->getAsFunction()->getDefinition(); 199 } 200 201 void print(raw_ostream &os) const; 202 void dump() const; 203 }; 204 205 // NOTE: we are comparing based on the callee only. So different call records 206 // (with different call expressions) to the same callee will compare equal! 207 inline bool operator==(const CallGraphNode::CallRecord &LHS, 208 const CallGraphNode::CallRecord &RHS) { 209 return LHS.Callee == RHS.Callee; 210 } 211 212 } // namespace clang 213 214 namespace llvm { 215 216 // Specialize DenseMapInfo for clang::CallGraphNode::CallRecord. 217 template <> struct DenseMapInfo<clang::CallGraphNode::CallRecord> { 218 static inline clang::CallGraphNode::CallRecord getEmptyKey() { 219 return clang::CallGraphNode::CallRecord( 220 DenseMapInfo<clang::CallGraphNode *>::getEmptyKey(), 221 DenseMapInfo<clang::Expr *>::getEmptyKey()); 222 } 223 224 static inline clang::CallGraphNode::CallRecord getTombstoneKey() { 225 return clang::CallGraphNode::CallRecord( 226 DenseMapInfo<clang::CallGraphNode *>::getTombstoneKey(), 227 DenseMapInfo<clang::Expr *>::getTombstoneKey()); 228 } 229 230 static unsigned getHashValue(const clang::CallGraphNode::CallRecord &Val) { 231 // NOTE: we are comparing based on the callee only. 232 // Different call records with the same callee will compare equal! 233 return DenseMapInfo<clang::CallGraphNode *>::getHashValue(Val.Callee); 234 } 235 236 static bool isEqual(const clang::CallGraphNode::CallRecord &LHS, 237 const clang::CallGraphNode::CallRecord &RHS) { 238 return LHS == RHS; 239 } 240 }; 241 242 // Graph traits for iteration, viewing. 243 template <> struct GraphTraits<clang::CallGraphNode*> { 244 using NodeType = clang::CallGraphNode; 245 using NodeRef = clang::CallGraphNode *; 246 using ChildIteratorType = NodeType::iterator; 247 248 static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; } 249 static ChildIteratorType child_begin(NodeType *N) { return N->begin(); } 250 static ChildIteratorType child_end(NodeType *N) { return N->end(); } 251 }; 252 253 template <> struct GraphTraits<const clang::CallGraphNode*> { 254 using NodeType = const clang::CallGraphNode; 255 using NodeRef = const clang::CallGraphNode *; 256 using ChildIteratorType = NodeType::const_iterator; 257 258 static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; } 259 static ChildIteratorType child_begin(NodeType *N) { return N->begin();} 260 static ChildIteratorType child_end(NodeType *N) { return N->end(); } 261 }; 262 263 template <> struct GraphTraits<clang::CallGraph*> 264 : public GraphTraits<clang::CallGraphNode*> { 265 static NodeType *getEntryNode(clang::CallGraph *CGN) { 266 return CGN->getRoot(); // Start at the external node! 267 } 268 269 static clang::CallGraphNode * 270 CGGetValue(clang::CallGraph::const_iterator::value_type &P) { 271 return P.second.get(); 272 } 273 274 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 275 using nodes_iterator = 276 mapped_iterator<clang::CallGraph::iterator, decltype(&CGGetValue)>; 277 278 static nodes_iterator nodes_begin(clang::CallGraph *CG) { 279 return nodes_iterator(CG->begin(), &CGGetValue); 280 } 281 282 static nodes_iterator nodes_end (clang::CallGraph *CG) { 283 return nodes_iterator(CG->end(), &CGGetValue); 284 } 285 286 static unsigned size(clang::CallGraph *CG) { return CG->size(); } 287 }; 288 289 template <> struct GraphTraits<const clang::CallGraph*> : 290 public GraphTraits<const clang::CallGraphNode*> { 291 static NodeType *getEntryNode(const clang::CallGraph *CGN) { 292 return CGN->getRoot(); 293 } 294 295 static clang::CallGraphNode * 296 CGGetValue(clang::CallGraph::const_iterator::value_type &P) { 297 return P.second.get(); 298 } 299 300 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 301 using nodes_iterator = 302 mapped_iterator<clang::CallGraph::const_iterator, decltype(&CGGetValue)>; 303 304 static nodes_iterator nodes_begin(const clang::CallGraph *CG) { 305 return nodes_iterator(CG->begin(), &CGGetValue); 306 } 307 308 static nodes_iterator nodes_end(const clang::CallGraph *CG) { 309 return nodes_iterator(CG->end(), &CGGetValue); 310 } 311 312 static unsigned size(const clang::CallGraph *CG) { return CG->size(); } 313 }; 314 315 } // namespace llvm 316 317 #endif // LLVM_CLANG_ANALYSIS_CALLGRAPH_H 318