1 | /* Call stacks at program points. |
2 | Copyright (C) 2019-2024 Free Software Foundation, Inc. |
3 | Contributed by David Malcolm <dmalcolm@redhat.com>. |
4 | |
5 | This file is part of GCC. |
6 | |
7 | GCC is free software; you can redistribute it and/or modify it |
8 | under the terms of the GNU General Public License as published by |
9 | the Free Software Foundation; either version 3, or (at your option) |
10 | any later version. |
11 | |
12 | GCC is distributed in the hope that it will be useful, but |
13 | WITHOUT ANY WARRANTY; without even the implied warranty of |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
15 | General Public License for more details. |
16 | |
17 | You should have received a copy of the GNU General Public License |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ |
20 | |
21 | #include "config.h" |
22 | #define INCLUDE_MEMORY |
23 | #include "system.h" |
24 | #include "coretypes.h" |
25 | #include "pretty-print.h" |
26 | #include "tree.h" |
27 | #include "options.h" |
28 | #include "ordered-hash-map.h" |
29 | #include "options.h" |
30 | #include "cgraph.h" |
31 | #include "function.h" |
32 | #include "cfg.h" |
33 | #include "basic-block.h" |
34 | #include "gimple.h" |
35 | #include "gimple-iterator.h" |
36 | #include "digraph.h" |
37 | #include "analyzer/analyzer.h" |
38 | #include "analyzer/analyzer-logging.h" |
39 | #include "analyzer/call-string.h" |
40 | #include "analyzer/supergraph.h" |
41 | |
42 | #if ENABLE_ANALYZER |
43 | |
44 | #if __GNUC__ >= 10 |
45 | #pragma GCC diagnostic ignored "-Wformat-diag" |
46 | #endif |
47 | |
48 | /* class call_string. */ |
49 | |
50 | /* struct call_string::element_t. */ |
51 | |
52 | /* call_string::element_t's equality operator. */ |
53 | |
54 | bool |
55 | call_string::element_t::operator== (const call_string::element_t &other) const |
56 | { |
57 | return (m_caller == other.m_caller && m_callee == other.m_callee); |
58 | } |
59 | |
60 | /* call_string::element_t's inequality operator. */ |
61 | bool |
62 | call_string::element_t::operator!= (const call_string::element_t &other) const |
63 | { |
64 | return !(*this == other); |
65 | } |
66 | |
67 | function * |
68 | call_string::element_t::get_caller_function () const |
69 | { |
70 | return m_caller->get_function (); |
71 | } |
72 | |
73 | function * |
74 | call_string::element_t::get_callee_function () const |
75 | { |
76 | return m_callee->get_function (); |
77 | } |
78 | |
79 | /* Print this to PP. */ |
80 | |
81 | void |
82 | call_string::print (pretty_printer *pp) const |
83 | { |
84 | pp_string (pp, "[" ); |
85 | |
86 | call_string::element_t *e; |
87 | int i; |
88 | FOR_EACH_VEC_ELT (m_elements, i, e) |
89 | { |
90 | if (i > 0) |
91 | pp_string (pp, ", " ); |
92 | pp_printf (pp, "(SN: %i -> SN: %i in %s)" , |
93 | e->m_callee->m_index, e->m_caller->m_index, |
94 | function_name (e->m_caller->m_fun)); |
95 | } |
96 | |
97 | pp_string (pp, "]" ); |
98 | } |
99 | |
100 | /* Return a new json::array of the form |
101 | [{"src_snode_idx" : int, |
102 | "dst_snode_idx" : int, |
103 | "funcname" : str}, |
104 | ...for each element in the callstring]. */ |
105 | |
106 | json::value * |
107 | call_string::to_json () const |
108 | { |
109 | json::array *arr = new json::array (); |
110 | |
111 | for (const call_string::element_t &e : m_elements) |
112 | { |
113 | json::object *e_obj = new json::object (); |
114 | e_obj->set (key: "src_snode_idx" , |
115 | v: new json::integer_number (e.m_callee->m_index)); |
116 | e_obj->set (key: "dst_snode_idx" , |
117 | v: new json::integer_number (e.m_caller->m_index)); |
118 | e_obj->set (key: "funcname" , |
119 | v: new json::string (function_name (e.m_caller->m_fun))); |
120 | arr->append (v: e_obj); |
121 | } |
122 | |
123 | return arr; |
124 | } |
125 | |
126 | /* Get or create the call_string resulting from pushing the return |
127 | superedge for CALL_SEDGE onto the end of this call_string. */ |
128 | |
129 | const call_string * |
130 | call_string::push_call (const supergraph &sg, |
131 | const call_superedge *call_sedge) const |
132 | { |
133 | gcc_assert (call_sedge); |
134 | const return_superedge *return_sedge = call_sedge->get_edge_for_return (sg); |
135 | gcc_assert (return_sedge); |
136 | return push_call (src: return_sedge->m_dest, dest: return_sedge->m_src); |
137 | } |
138 | |
139 | /* Get or create the call_string resulting from pushing the call |
140 | (caller, callee) onto the end of this call_string. */ |
141 | |
142 | const call_string * |
143 | call_string::push_call (const supernode *caller, |
144 | const supernode *callee) const |
145 | { |
146 | call_string::element_t e (caller, callee); |
147 | |
148 | if (const call_string **slot = m_children.get (k: e)) |
149 | return *slot; |
150 | |
151 | call_string *result = new call_string (*this, e); |
152 | m_children.put (k: e, v: result); |
153 | return result; |
154 | } |
155 | |
156 | /* Count the number of times the top-most call site appears in the |
157 | stack. */ |
158 | int |
159 | call_string::calc_recursion_depth () const |
160 | { |
161 | if (m_elements.is_empty ()) |
162 | return 0; |
163 | const call_string::element_t top_return_sedge |
164 | = m_elements[m_elements.length () - 1]; |
165 | |
166 | int result = 0; |
167 | for (const call_string::element_t &e : m_elements) |
168 | if (e == top_return_sedge) |
169 | ++result; |
170 | return result; |
171 | } |
172 | |
173 | /* Count the number of times FUN appears in the string. */ |
174 | |
175 | int |
176 | call_string::count_occurrences_of_function (function *fun) const |
177 | { |
178 | int result = 0; |
179 | for (const call_string::element_t &e : m_elements) |
180 | { |
181 | if (e.get_callee_function () == fun) |
182 | result++; |
183 | if (e.get_caller_function () == fun) |
184 | result++; |
185 | } |
186 | return result; |
187 | } |
188 | |
189 | /* Comparator for call strings. |
190 | This implements a version of lexicographical order. |
191 | Return negative if A is before B. |
192 | Return positive if B is after A. |
193 | Return 0 if they are equal. */ |
194 | |
195 | int |
196 | call_string::cmp (const call_string &a, |
197 | const call_string &b) |
198 | { |
199 | unsigned len_a = a.length (); |
200 | unsigned len_b = b.length (); |
201 | |
202 | unsigned i = 0; |
203 | while (1) |
204 | { |
205 | /* Consider index i; the strings have been equal up to it. */ |
206 | |
207 | /* Have both strings run out? */ |
208 | if (i >= len_a && i >= len_b) |
209 | return 0; |
210 | |
211 | /* Otherwise, has just one of the strings run out? */ |
212 | if (i >= len_a) |
213 | return 1; |
214 | if (i >= len_b) |
215 | return -1; |
216 | |
217 | /* Otherwise, compare the node pairs. */ |
218 | const call_string::element_t a_node_pair = a[i]; |
219 | const call_string::element_t b_node_pair = b[i]; |
220 | int src_cmp |
221 | = a_node_pair.m_callee->m_index - b_node_pair.m_callee->m_index; |
222 | if (src_cmp) |
223 | return src_cmp; |
224 | int dest_cmp |
225 | = a_node_pair.m_caller->m_index - b_node_pair.m_caller->m_index; |
226 | if (dest_cmp) |
227 | return dest_cmp; |
228 | i++; |
229 | // TODO: test coverage for this |
230 | } |
231 | } |
232 | |
233 | /* Comparator for use by vec<const call_string *>::qsort. */ |
234 | |
235 | int |
236 | call_string::cmp_ptr_ptr (const void *pa, const void *pb) |
237 | { |
238 | const call_string *cs_a = *static_cast <const call_string * const *> (pa); |
239 | const call_string *cs_b = *static_cast <const call_string * const *> (pb); |
240 | return cmp (a: *cs_a, b: *cs_b); |
241 | } |
242 | |
243 | /* Return the pointer to callee of the topmost call in the stack, |
244 | or NULL if stack is empty. */ |
245 | const supernode * |
246 | call_string::get_callee_node () const |
247 | { |
248 | if(m_elements.is_empty ()) |
249 | return NULL; |
250 | return m_elements[m_elements.length () - 1].m_callee; |
251 | } |
252 | |
253 | /* Return the pointer to caller of the topmost call in the stack, |
254 | or NULL if stack is empty. */ |
255 | const supernode * |
256 | call_string::get_caller_node () const |
257 | { |
258 | if(m_elements.is_empty ()) |
259 | return NULL; |
260 | return m_elements[m_elements.length () - 1].m_caller; |
261 | } |
262 | |
263 | /* Assert that this object is sane. */ |
264 | |
265 | void |
266 | call_string::validate () const |
267 | { |
268 | /* Skip this in a release build. */ |
269 | #if !CHECKING_P |
270 | return; |
271 | #endif |
272 | |
273 | gcc_assert (m_parent || m_elements.length () == 0); |
274 | |
275 | /* Each entry's "caller" should be the "callee" of the previous entry. */ |
276 | call_string::element_t *e; |
277 | int i; |
278 | FOR_EACH_VEC_ELT (m_elements, i, e) |
279 | if (i > 0) |
280 | gcc_assert (e->get_caller_function () == |
281 | m_elements[i - 1].get_callee_function ()); |
282 | } |
283 | |
284 | /* ctor for the root/empty call_string. */ |
285 | |
286 | call_string::call_string () |
287 | : m_parent (NULL), m_elements () |
288 | { |
289 | } |
290 | |
291 | /* ctor for a child call_string. */ |
292 | |
293 | call_string::call_string (const call_string &parent, const element_t &to_push) |
294 | : m_parent (&parent), |
295 | m_elements (parent.m_elements.length () + 1) |
296 | { |
297 | m_elements.splice (src: parent.m_elements); |
298 | m_elements.quick_push (obj: to_push); |
299 | } |
300 | |
301 | /* dtor for call_string: recursively delete children. */ |
302 | |
303 | call_string::~call_string () |
304 | { |
305 | for (auto child_iter : m_children) |
306 | delete child_iter.second; |
307 | } |
308 | |
309 | /* Log this call_string and all its descendents recursively to LOGGER, |
310 | using indentation and elision to highlight the hierarchy. */ |
311 | |
312 | void |
313 | call_string::recursive_log (logger *logger) const |
314 | { |
315 | logger->start_log_line (); |
316 | pretty_printer *pp = logger->get_printer (); |
317 | for (unsigned i = 0; i < length (); i++) |
318 | pp_string (pp, " " ); |
319 | if (length () > 0) |
320 | { |
321 | pp_string (pp, "[" ); |
322 | /* Elide all but the final element, since they are shared with |
323 | the parent call_string. */ |
324 | for (unsigned i = 0; i < length (); i++) |
325 | pp_string (pp, "..., " ); |
326 | /* Log the final element in detail. */ |
327 | const element_t *e = &m_elements[m_elements.length () - 1]; |
328 | pp_printf (pp, "(SN: %i -> SN: %i in %s)]" , |
329 | e->m_callee->m_index, e->m_caller->m_index, |
330 | function_name (e->m_caller->m_fun)); |
331 | } |
332 | else |
333 | pp_string (pp, "[]" ); |
334 | logger->end_log_line (); |
335 | |
336 | /* Recurse into children. */ |
337 | { |
338 | auto_vec<const call_string *> children (m_children.elements ()); |
339 | for (auto iter : m_children) |
340 | children.safe_push (obj: iter.second); |
341 | children.qsort (call_string::cmp_ptr_ptr); |
342 | |
343 | for (auto iter : children) |
344 | iter->recursive_log (logger); |
345 | } |
346 | } |
347 | |
348 | #endif /* #if ENABLE_ANALYZER */ |
349 | |