/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/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 <memory> |
28 | | |
29 | | namespace clang { |
30 | | |
31 | | class CallGraphNode; |
32 | | class Decl; |
33 | | class DeclContext; |
34 | | class 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. |
41 | | class 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 | | |
53 | | public: |
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 | 27.1k | void addToCallGraph(Decl *D) { |
62 | 27.1k | TraverseDecl(D); |
63 | 27.1k | } |
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 | 0 | iterator begin() { return FunctionMap.begin(); } |
81 | 0 | iterator end() { return FunctionMap.end(); } |
82 | 0 | const_iterator begin() const { return FunctionMap.begin(); } |
83 | 0 | const_iterator end() const { return FunctionMap.end(); } |
84 | | |
85 | | /// Get the number of nodes in the graph. |
86 | 0 | 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 | 883 | 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 | 51.5k | bool VisitFunctionDecl(FunctionDecl *FD) { |
107 | 51.5k | // We skip function template definitions, as their semantics is |
108 | 51.5k | // only determined when they are instantiated. |
109 | 51.5k | if (includeInGraph(FD) && FD->isThisDeclarationADefinition()15.4k ) { |
110 | 15.2k | // Add all blocks declared inside this function to the graph. |
111 | 15.2k | addNodesForBlocks(FD); |
112 | 15.2k | // If this function has external linkage, anything could call it. |
113 | 15.2k | // Note, we are not precise here. For example, the function could have |
114 | 15.2k | // its address taken. |
115 | 15.2k | addNodeForDecl(FD, FD->isGlobal()); |
116 | 15.2k | } |
117 | 51.5k | return true; |
118 | 51.5k | } |
119 | | |
120 | | /// Part of recursive declaration visitation. |
121 | 4.16k | bool VisitObjCMethodDecl(ObjCMethodDecl *MD) { |
122 | 4.16k | if (includeInGraph(MD)) { |
123 | 1.11k | addNodesForBlocks(MD); |
124 | 1.11k | addNodeForDecl(MD, true); |
125 | 1.11k | } |
126 | 4.16k | return true; |
127 | 4.16k | } |
128 | | |
129 | | // We are only collecting the declarations, so do not step into the bodies. |
130 | 40.8k | bool TraverseStmt(Stmt *S) { return true; } |
131 | | |
132 | 250k | bool shouldWalkTypesOfTypeLocs() const { return false; } |
133 | 8.90k | bool shouldVisitTemplateInstantiations() const { return true; } |
134 | | |
135 | | private: |
136 | | /// Add the given declaration to the call graph. |
137 | | void addNodeForDecl(Decl *D, bool IsGlobal); |
138 | | |
139 | | /// Allocate a new node in the graph. |
140 | | CallGraphNode *allocateNewNode(Decl *); |
141 | | }; |
142 | | |
143 | | class CallGraphNode { |
144 | | public: |
145 | | using CallRecord = CallGraphNode *; |
146 | | |
147 | | private: |
148 | | /// The function/method declaration. |
149 | | Decl *FD; |
150 | | |
151 | | /// The list of functions called from this node. |
152 | | SmallVector<CallRecord, 5> CalledFunctions; |
153 | | |
154 | | public: |
155 | 17.0k | CallGraphNode(Decl *D) : FD(D) {} |
156 | | |
157 | | using iterator = SmallVectorImpl<CallRecord>::iterator; |
158 | | using const_iterator = SmallVectorImpl<CallRecord>::const_iterator; |
159 | | |
160 | | /// Iterators through all the callees/children of the node. |
161 | 17.0k | iterator begin() { return CalledFunctions.begin(); } |
162 | 39.4k | iterator end() { return CalledFunctions.end(); } |
163 | 36 | const_iterator begin() const { return CalledFunctions.begin(); } |
164 | 66 | const_iterator end() const { return CalledFunctions.end(); } |
165 | | |
166 | 0 | bool empty() const { return CalledFunctions.empty(); } |
167 | 0 | unsigned size() const { return CalledFunctions.size(); } |
168 | | |
169 | 22.3k | void addCallee(CallGraphNode *N) { |
170 | 22.3k | CalledFunctions.push_back(N); |
171 | 22.3k | } |
172 | | |
173 | 17.0k | Decl *getDecl() const { return FD; } |
174 | | |
175 | | void print(raw_ostream &os) const; |
176 | | void dump() const; |
177 | | }; |
178 | | |
179 | | } // namespace clang |
180 | | |
181 | | // Graph traits for iteration, viewing. |
182 | | namespace llvm { |
183 | | |
184 | | template <> struct GraphTraits<clang::CallGraphNode*> { |
185 | | using NodeType = clang::CallGraphNode; |
186 | | using NodeRef = clang::CallGraphNode *; |
187 | | using ChildIteratorType = NodeType::iterator; |
188 | | |
189 | 882 | static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; } |
190 | 17.0k | static ChildIteratorType child_begin(NodeType *N) { return N->begin(); } |
191 | 39.4k | static ChildIteratorType child_end(NodeType *N) { return N->end(); } |
192 | | }; |
193 | | |
194 | | template <> struct GraphTraits<const clang::CallGraphNode*> { |
195 | | using NodeType = const clang::CallGraphNode; |
196 | | using NodeRef = const clang::CallGraphNode *; |
197 | | using ChildIteratorType = NodeType::const_iterator; |
198 | | |
199 | 1 | static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; } |
200 | 18 | static ChildIteratorType child_begin(NodeType *N) { return N->begin();} |
201 | 48 | static ChildIteratorType child_end(NodeType *N) { return N->end(); } |
202 | | }; |
203 | | |
204 | | template <> struct GraphTraits<clang::CallGraph*> |
205 | | : public GraphTraits<clang::CallGraphNode*> { |
206 | 882 | static NodeType *getEntryNode(clang::CallGraph *CGN) { |
207 | 882 | return CGN->getRoot(); // Start at the external node! |
208 | 882 | } |
209 | | |
210 | | static clang::CallGraphNode * |
211 | 0 | CGGetValue(clang::CallGraph::const_iterator::value_type &P) { |
212 | 0 | return P.second.get(); |
213 | 0 | } |
214 | | |
215 | | // nodes_iterator/begin/end - Allow iteration over all nodes in the graph |
216 | | using nodes_iterator = |
217 | | mapped_iterator<clang::CallGraph::iterator, decltype(&CGGetValue)>; |
218 | | |
219 | 0 | static nodes_iterator nodes_begin(clang::CallGraph *CG) { |
220 | 0 | return nodes_iterator(CG->begin(), &CGGetValue); |
221 | 0 | } |
222 | | |
223 | 0 | static nodes_iterator nodes_end (clang::CallGraph *CG) { |
224 | 0 | return nodes_iterator(CG->end(), &CGGetValue); |
225 | 0 | } |
226 | | |
227 | 0 | static unsigned size(clang::CallGraph *CG) { return CG->size(); } |
228 | | }; |
229 | | |
230 | | template <> struct GraphTraits<const clang::CallGraph*> : |
231 | | public GraphTraits<const clang::CallGraphNode*> { |
232 | 1 | static NodeType *getEntryNode(const clang::CallGraph *CGN) { |
233 | 1 | return CGN->getRoot(); |
234 | 1 | } |
235 | | |
236 | | static clang::CallGraphNode * |
237 | 0 | CGGetValue(clang::CallGraph::const_iterator::value_type &P) { |
238 | 0 | return P.second.get(); |
239 | 0 | } |
240 | | |
241 | | // nodes_iterator/begin/end - Allow iteration over all nodes in the graph |
242 | | using nodes_iterator = |
243 | | mapped_iterator<clang::CallGraph::const_iterator, decltype(&CGGetValue)>; |
244 | | |
245 | 0 | static nodes_iterator nodes_begin(const clang::CallGraph *CG) { |
246 | 0 | return nodes_iterator(CG->begin(), &CGGetValue); |
247 | 0 | } |
248 | | |
249 | 0 | static nodes_iterator nodes_end(const clang::CallGraph *CG) { |
250 | 0 | return nodes_iterator(CG->end(), &CGGetValue); |
251 | 0 | } |
252 | | |
253 | 0 | static unsigned size(const clang::CallGraph *CG) { return CG->size(); } |
254 | | }; |
255 | | |
256 | | } // namespace llvm |
257 | | |
258 | | #endif // LLVM_CLANG_ANALYSIS_CALLGRAPH_H |