]>
Commit | Line | Data |
---|---|---|
757bf1df | 1 | /* Call stacks at program points. |
a945c346 | 2 | Copyright (C) 2019-2024 Free Software Foundation, Inc. |
757bf1df DM |
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" | |
accece8c | 22 | #define INCLUDE_MEMORY |
757bf1df DM |
23 | #include "system.h" |
24 | #include "coretypes.h" | |
25 | #include "pretty-print.h" | |
26 | #include "tree.h" | |
27 | #include "options.h" | |
757bf1df DM |
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" | |
bb8e93eb DM |
37 | #include "analyzer/analyzer.h" |
38 | #include "analyzer/analyzer-logging.h" | |
39 | #include "analyzer/call-string.h" | |
757bf1df DM |
40 | #include "analyzer/supergraph.h" |
41 | ||
42 | #if ENABLE_ANALYZER | |
43 | ||
5253b3e6 | 44 | #if __GNUC__ >= 10 |
808f4dfe | 45 | #pragma GCC diagnostic ignored "-Wformat-diag" |
5253b3e6 | 46 | #endif |
808f4dfe | 47 | |
757bf1df DM |
48 | /* class call_string. */ |
49 | ||
e8de5bad AS |
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 | ||
757bf1df DM |
79 | /* Print this to PP. */ |
80 | ||
81 | void | |
82 | call_string::print (pretty_printer *pp) const | |
83 | { | |
84 | pp_string (pp, "["); | |
85 | ||
e8de5bad | 86 | call_string::element_t *e; |
757bf1df | 87 | int i; |
e8de5bad | 88 | FOR_EACH_VEC_ELT (m_elements, i, e) |
757bf1df DM |
89 | { |
90 | if (i > 0) | |
91 | pp_string (pp, ", "); | |
92 | pp_printf (pp, "(SN: %i -> SN: %i in %s)", | |
e8de5bad AS |
93 | e->m_callee->m_index, e->m_caller->m_index, |
94 | function_name (e->m_caller->m_fun)); | |
757bf1df DM |
95 | } |
96 | ||
97 | pp_string (pp, "]"); | |
98 | } | |
99 | ||
809192e7 DM |
100 | /* Return a new json::array of the form |
101 | [{"src_snode_idx" : int, | |
102 | "dst_snode_idx" : int, | |
103 | "funcname" : str}, | |
e8de5bad | 104 | ...for each element in the callstring]. */ |
809192e7 DM |
105 | |
106 | json::value * | |
107 | call_string::to_json () const | |
108 | { | |
109 | json::array *arr = new json::array (); | |
110 | ||
e8de5bad | 111 | for (const call_string::element_t &e : m_elements) |
809192e7 DM |
112 | { |
113 | json::object *e_obj = new json::object (); | |
114 | e_obj->set ("src_snode_idx", | |
e8de5bad | 115 | new json::integer_number (e.m_callee->m_index)); |
809192e7 | 116 | e_obj->set ("dst_snode_idx", |
e8de5bad | 117 | new json::integer_number (e.m_caller->m_index)); |
809192e7 | 118 | e_obj->set ("funcname", |
e8de5bad | 119 | new json::string (function_name (e.m_caller->m_fun))); |
809192e7 DM |
120 | arr->append (e_obj); |
121 | } | |
122 | ||
123 | return arr; | |
124 | } | |
125 | ||
bb8e93eb DM |
126 | /* Get or create the call_string resulting from pushing the return |
127 | superedge for CALL_SEDGE onto the end of this call_string. */ | |
757bf1df | 128 | |
bb8e93eb | 129 | const call_string * |
757bf1df | 130 | call_string::push_call (const supergraph &sg, |
bb8e93eb | 131 | const call_superedge *call_sedge) const |
757bf1df DM |
132 | { |
133 | gcc_assert (call_sedge); | |
134 | const return_superedge *return_sedge = call_sedge->get_edge_for_return (sg); | |
135 | gcc_assert (return_sedge); | |
bb8e93eb | 136 | return push_call (return_sedge->m_dest, return_sedge->m_src); |
e8de5bad AS |
137 | } |
138 | ||
bb8e93eb DM |
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 * | |
e8de5bad | 143 | call_string::push_call (const supernode *caller, |
bb8e93eb | 144 | const supernode *callee) const |
e8de5bad AS |
145 | { |
146 | call_string::element_t e (caller, callee); | |
e8de5bad | 147 | |
bb8e93eb DM |
148 | if (const call_string **slot = m_children.get (e)) |
149 | return *slot; | |
150 | ||
151 | call_string *result = new call_string (*this, e); | |
152 | m_children.put (e, result); | |
153 | return result; | |
757bf1df DM |
154 | } |
155 | ||
156 | /* Count the number of times the top-most call site appears in the | |
157 | stack. */ | |
757bf1df DM |
158 | int |
159 | call_string::calc_recursion_depth () const | |
160 | { | |
e8de5bad | 161 | if (m_elements.is_empty ()) |
757bf1df | 162 | return 0; |
3752e21d | 163 | const call_string::element_t top_return_sedge |
e8de5bad | 164 | = m_elements[m_elements.length () - 1]; |
757bf1df DM |
165 | |
166 | int result = 0; | |
e8de5bad | 167 | for (const call_string::element_t &e : m_elements) |
757bf1df DM |
168 | if (e == top_return_sedge) |
169 | ++result; | |
170 | return result; | |
171 | } | |
172 | ||
12c583a2 DM |
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 | ||
757bf1df | 189 | /* Comparator for call strings. |
6a81cabc | 190 | This implements a version of lexicographical order. |
757bf1df DM |
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) | |
757bf1df DM |
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 | ||
e8de5bad AS |
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]; | |
3752e21d DM |
220 | int src_cmp |
221 | = a_node_pair.m_callee->m_index - b_node_pair.m_callee->m_index; | |
757bf1df DM |
222 | if (src_cmp) |
223 | return src_cmp; | |
3752e21d DM |
224 | int dest_cmp |
225 | = a_node_pair.m_caller->m_index - b_node_pair.m_caller->m_index; | |
757bf1df DM |
226 | if (dest_cmp) |
227 | return dest_cmp; | |
228 | i++; | |
229 | // TODO: test coverage for this | |
230 | } | |
231 | } | |
232 | ||
bb8e93eb DM |
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 (*cs_a, *cs_b); | |
241 | } | |
242 | ||
e8de5bad AS |
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. */ | |
3752e21d | 255 | const supernode * |
e8de5bad AS |
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 | ||
757bf1df DM |
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 | ||
bb8e93eb DM |
273 | gcc_assert (m_parent || m_elements.length () == 0); |
274 | ||
757bf1df | 275 | /* Each entry's "caller" should be the "callee" of the previous entry. */ |
e8de5bad | 276 | call_string::element_t *e; |
757bf1df | 277 | int i; |
e8de5bad | 278 | FOR_EACH_VEC_ELT (m_elements, i, e) |
757bf1df | 279 | if (i > 0) |
3752e21d DM |
280 | gcc_assert (e->get_caller_function () == |
281 | m_elements[i - 1].get_callee_function ()); | |
757bf1df DM |
282 | } |
283 | ||
bb8e93eb DM |
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 (parent.m_elements); | |
298 | m_elements.quick_push (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 (iter.second); | |
341 | children.qsort (call_string::cmp_ptr_ptr); | |
342 | ||
343 | for (auto iter : children) | |
344 | iter->recursive_log (logger); | |
345 | } | |
346 | } | |
347 | ||
757bf1df | 348 | #endif /* #if ENABLE_ANALYZER */ |