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.
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.
86   iterator begin() { return FunctionMap.begin(); }
87   iterator end()   { return FunctionMap.end();   }
88   const_iterator begin() const { return FunctionMap.begin(); }
89   const_iterator end()   const { return FunctionMap.end();   }
90 
91   /// Get the number of nodes in the graph.
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.
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.
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.
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.
136   bool TraverseStmt(Stmt *S) { return true; }
137 
138   bool shouldWalkTypesOfTypeLocs() const { return false; }
139   bool shouldVisitTemplateInstantiations() const { return true; }
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 
155     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:
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.
177   iterator begin() { return CalledFunctions.begin(); }
178   iterator end() { return CalledFunctions.end(); }
179   const_iterator begin() const { return CalledFunctions.begin(); }
180   const_iterator end() const { return CalledFunctions.end(); }
181 
182   /// Iterator access to callees/children of the node.
183   llvm::iterator_range<iterator> callees() {
184     return llvm::make_range(begin(), end());
185   }
186   llvm::iterator_range<const_iterator> callees() const {
187     return llvm::make_range(begin(), end());
188   }
189 
190   bool empty() const { return CalledFunctions.empty(); }
191   unsigned size() const { return CalledFunctions.size(); }
192 
193   void addCallee(CallRecord Call) { CalledFunctions.push_back(Call); }
194 
195   Decl *getDecl() const { return FD; }
196 
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