/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/Analysis/CallGraph.h
Line | Count | Source (jump to first uncovered line) |
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 | 39.0k | void addToCallGraph(Decl *D) { |
63 | 39.0k | TraverseDecl(D); |
64 | 39.0k | } |
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 | 0 | iterator begin() { return FunctionMap.begin(); } |
87 | 0 | iterator end() { return FunctionMap.end(); } |
88 | 0 | const_iterator begin() const { return FunctionMap.begin(); } |
89 | 0 | const_iterator end() const { return FunctionMap.end(); } |
90 | | |
91 | | /// Get the number of nodes in the graph. |
92 | 0 | 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 | 1.68k | 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 | 94.9k | bool VisitFunctionDecl(FunctionDecl *FD) { |
113 | | // We skip function template definitions, as their semantics is |
114 | | // only determined when they are instantiated. |
115 | 94.9k | if (includeInGraph(FD) && FD->isThisDeclarationADefinition()22.6k ) { |
116 | | // Add all blocks declared inside this function to the graph. |
117 | 22.4k | 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 | 22.4k | addNodeForDecl(FD, FD->isGlobal()); |
122 | 22.4k | } |
123 | 94.9k | return true; |
124 | 94.9k | } |
125 | | |
126 | | /// Part of recursive declaration visitation. |
127 | 5.75k | bool VisitObjCMethodDecl(ObjCMethodDecl *MD) { |
128 | 5.75k | if (includeInGraph(MD)) { |
129 | 1.16k | addNodesForBlocks(MD); |
130 | 1.16k | addNodeForDecl(MD, true); |
131 | 1.16k | } |
132 | 5.75k | return true; |
133 | 5.75k | } |
134 | | |
135 | | // We are only collecting the declarations, so do not step into the bodies. |
136 | 67.1k | bool TraverseStmt(Stmt *S) { return true; } |
137 | | |
138 | 441k | bool shouldWalkTypesOfTypeLocs() const { return false; } |
139 | 20.3k | bool shouldVisitTemplateInstantiations() const { return true; } |
140 | 345k | 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 | 87.9k | : Callee(Callee_), CallExpr(CallExpr_) {} |
157 | | |
158 | | // The call destination is the only important data here, |
159 | | // allow to transparently unwrap into it. |
160 | 87.9k | 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 | 31.5k | 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 | 31.5k | iterator begin() { return CalledFunctions.begin(); } |
178 | 119k | iterator end() { return CalledFunctions.end(); } |
179 | 68 | const_iterator begin() const { return CalledFunctions.begin(); } |
180 | 125 | const_iterator end() const { return CalledFunctions.end(); } |
181 | | |
182 | | /// Iterator access to callees/children of the node. |
183 | 0 | llvm::iterator_range<iterator> callees() { |
184 | 0 | return llvm::make_range(begin(), end()); |
185 | 0 | } |
186 | 0 | llvm::iterator_range<const_iterator> callees() const { |
187 | 0 | return llvm::make_range(begin(), end()); |
188 | 0 | } |
189 | | |
190 | 0 | bool empty() const { return CalledFunctions.empty(); } |
191 | 0 | unsigned size() const { return CalledFunctions.size(); } |
192 | | |
193 | 87.9k | void addCallee(CallRecord Call) { CalledFunctions.push_back(Call); } |
194 | | |
195 | 31.5k | Decl *getDecl() const { return FD; } |
196 | | |
197 | 0 | FunctionDecl *getDefinition() const { |
198 | 0 | return getDecl()->getAsFunction()->getDefinition(); |
199 | 0 | } |
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 | 0 | const CallGraphNode::CallRecord &RHS) { |
209 | 0 | return LHS.Callee == RHS.Callee; |
210 | 0 | } |
211 | | |
212 | | } // namespace clang |
213 | | |
214 | | namespace llvm { |
215 | | |
216 | | // Specialize DenseMapInfo for clang::CallGraphNode::CallRecord. |
217 | | template <> struct DenseMapInfo<clang::CallGraphNode::CallRecord> { |
218 | 0 | static inline clang::CallGraphNode::CallRecord getEmptyKey() { |
219 | 0 | return clang::CallGraphNode::CallRecord( |
220 | 0 | DenseMapInfo<clang::CallGraphNode *>::getEmptyKey(), |
221 | 0 | DenseMapInfo<clang::Expr *>::getEmptyKey()); |
222 | 0 | } |
223 | | |
224 | 0 | static inline clang::CallGraphNode::CallRecord getTombstoneKey() { |
225 | 0 | return clang::CallGraphNode::CallRecord( |
226 | 0 | DenseMapInfo<clang::CallGraphNode *>::getTombstoneKey(), |
227 | 0 | DenseMapInfo<clang::Expr *>::getTombstoneKey()); |
228 | 0 | } |
229 | | |
230 | 0 | static unsigned getHashValue(const clang::CallGraphNode::CallRecord &Val) { |
231 | 0 | // NOTE: we are comparing based on the callee only. |
232 | 0 | // Different call records with the same callee will compare equal! |
233 | 0 | return DenseMapInfo<clang::CallGraphNode *>::getHashValue(Val.Callee); |
234 | 0 | } |
235 | | |
236 | | static bool isEqual(const clang::CallGraphNode::CallRecord &LHS, |
237 | 0 | const clang::CallGraphNode::CallRecord &RHS) { |
238 | 0 | return LHS == RHS; |
239 | 0 | } |
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 | 0 | static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; } |
249 | 31.5k | static ChildIteratorType child_begin(NodeType *N) { return N->begin(); } |
250 | 119k | 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 | 0 | static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; } |
259 | 34 | static ChildIteratorType child_begin(NodeType *N) { return N->begin();} |
260 | 91 | static ChildIteratorType child_end(NodeType *N) { return N->end(); } |
261 | | }; |
262 | | |
263 | | template <> struct GraphTraits<clang::CallGraph*> |
264 | | : public GraphTraits<clang::CallGraphNode*> { |
265 | 1.68k | static NodeType *getEntryNode(clang::CallGraph *CGN) { |
266 | 1.68k | return CGN->getRoot(); // Start at the external node! |
267 | 1.68k | } |
268 | | |
269 | | static clang::CallGraphNode * |
270 | 0 | CGGetValue(clang::CallGraph::const_iterator::value_type &P) { |
271 | 0 | return P.second.get(); |
272 | 0 | } |
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 | 0 | static nodes_iterator nodes_begin(clang::CallGraph *CG) { |
279 | 0 | return nodes_iterator(CG->begin(), &CGGetValue); |
280 | 0 | } |
281 | | |
282 | 0 | static nodes_iterator nodes_end (clang::CallGraph *CG) { |
283 | 0 | return nodes_iterator(CG->end(), &CGGetValue); |
284 | 0 | } |
285 | | |
286 | 0 | 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 | 3 | static NodeType *getEntryNode(const clang::CallGraph *CGN) { |
292 | 3 | return CGN->getRoot(); |
293 | 3 | } |
294 | | |
295 | | static clang::CallGraphNode * |
296 | 0 | CGGetValue(clang::CallGraph::const_iterator::value_type &P) { |
297 | 0 | return P.second.get(); |
298 | 0 | } |
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 | 0 | static nodes_iterator nodes_begin(const clang::CallGraph *CG) { |
305 | 0 | return nodes_iterator(CG->begin(), &CGGetValue); |
306 | 0 | } |
307 | | |
308 | 0 | static nodes_iterator nodes_end(const clang::CallGraph *CG) { |
309 | 0 | return nodes_iterator(CG->end(), &CGGetValue); |
310 | 0 | } |
311 | | |
312 | 0 | static unsigned size(const clang::CallGraph *CG) { return CG->size(); } |
313 | | }; |
314 | | |
315 | | } // namespace llvm |
316 | | |
317 | | #endif // LLVM_CLANG_ANALYSIS_CALLGRAPH_H |