Line data Source code
1 : /* Call stacks at program points.
2 : Copyright (C) 2019-2026 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 "analyzer/common.h"
22 :
23 : #include "analyzer/symbolic-nodes.h"
24 : #include "analyzer/analyzer-logging.h"
25 : #include "analyzer/call-string.h"
26 : #include "analyzer/supergraph.h"
27 :
28 : #if ENABLE_ANALYZER
29 :
30 : #if __GNUC__ >= 10
31 : #pragma GCC diagnostic ignored "-Wformat-diag"
32 : #endif
33 :
34 : /* class call_string. */
35 :
36 : /* struct call_string::element_t. */
37 :
38 : /* call_string::element_t's equality operator. */
39 :
40 : bool
41 263487 : call_string::element_t::operator== (const call_string::element_t &other) const
42 : {
43 263487 : return (m_call_sedge == other.m_call_sedge
44 263487 : && m_called_fun == other.m_called_fun);
45 : }
46 :
47 : /* call_string::element_t's inequality operator. */
48 : bool
49 65 : call_string::element_t::operator!= (const call_string::element_t &other) const
50 : {
51 65 : return !(*this == other);
52 : }
53 :
54 : int
55 466394 : call_string::element_t::cmp (const element_t &a, const element_t &b)
56 : {
57 466394 : if (int src_id_cmp = (a.m_call_sedge->m_src->m_id
58 466394 : - b.m_call_sedge->m_src->m_id))
59 : return src_id_cmp;
60 :
61 : /* We don't expect multiple call sedges with the same src. */
62 466394 : gcc_assert (a.m_call_sedge->m_dest == b.m_call_sedge->m_dest);
63 :
64 466394 : return a.m_called_fun->funcdef_no - b.m_called_fun->funcdef_no;
65 : }
66 :
67 : function *
68 690178 : call_string::element_t::get_caller_function () const
69 : {
70 690178 : return m_call_sedge->m_src->get_function ();
71 : }
72 :
73 : const supernode *
74 2796 : call_string::element_t::get_call_snode_in_caller () const
75 : {
76 2796 : return m_call_sedge->m_src;
77 : }
78 :
79 : const supernode *
80 12666 : call_string::element_t::get_return_snode_in_caller () const
81 : {
82 12666 : return m_call_sedge->m_dest;
83 : }
84 :
85 : const gcall &
86 8674 : call_string::element_t::get_call_stmt () const
87 : {
88 8674 : return m_call_op->get_gcall ();
89 : }
90 :
91 : std::unique_ptr<text_art::tree_widget>
92 0 : call_string::element_t::make_dump_widget (symbolic::node_dump_state &nds) const
93 : {
94 0 : using text_art::tree_widget;
95 :
96 0 : pretty_printer pp;
97 0 : pp_printf (&pp, "SN: %i -> SN: %i in %qs",
98 0 : get_call_snode_in_caller ()->m_id,
99 0 : get_return_snode_in_caller ()->m_id,
100 0 : function_name (get_caller_function ()));
101 0 : return tree_widget::make (nds, &pp);
102 0 : }
103 :
104 : std::unique_ptr<text_art::tree_widget>
105 0 : call_string::make_dump_widget (symbolic::node_dump_state &nds) const
106 : {
107 0 : using text_art::tree_widget;
108 :
109 0 : auto w = tree_widget::make (nds, "call_string");
110 :
111 0 : call_string::element_t *e;
112 0 : int i;
113 0 : FOR_EACH_VEC_ELT (m_elements, i, e)
114 0 : w->add_child (e->make_dump_widget (nds));
115 :
116 0 : return w;
117 : }
118 :
119 : /* Print this to PP. */
120 :
121 : void
122 2655 : call_string::print (pretty_printer *pp) const
123 : {
124 2655 : pp_string (pp, "[");
125 :
126 2655 : call_string::element_t *e;
127 2655 : int i;
128 8106 : FOR_EACH_VEC_ELT (m_elements, i, e)
129 : {
130 2796 : if (i > 0)
131 2107 : pp_string (pp, ", ");
132 2796 : pp_printf (pp, "(SN: %i -> SN: %i in %s)",
133 2796 : e->get_call_snode_in_caller ()->m_id,
134 2796 : e->get_return_snode_in_caller ()->m_id,
135 2796 : function_name (e->get_caller_function ()));
136 : }
137 :
138 2655 : pp_string (pp, "]");
139 2655 : }
140 :
141 : /* Return a new json::array of the form
142 : [{"call_sedge_src" : int,
143 : "call_sedge_dest" : int,
144 : "called_fun" : str},
145 : ...for each element in the callstring]. */
146 :
147 : std::unique_ptr<json::value>
148 0 : call_string::to_json () const
149 : {
150 0 : auto arr = std::make_unique<json::array> ();
151 :
152 0 : for (const call_string::element_t &e : m_elements)
153 : {
154 0 : auto e_obj = std::make_unique<json::object> ();
155 0 : e_obj->set_integer ("call_sedge_src", e.m_call_sedge->m_src->m_id);
156 0 : e_obj->set_integer ("call_sedge_dest", e.m_call_sedge->m_dest->m_id);
157 0 : e_obj->set_string ("called_fun", function_name (e.m_called_fun));
158 0 : arr->append (std::move (e_obj));
159 0 : }
160 :
161 0 : return arr;
162 0 : }
163 :
164 :
165 : /* Get or create the call_string resulting from pushing the call
166 : (caller, callee) onto the end of this call_string. */
167 :
168 : const call_string *
169 9577 : call_string::push_call (const superedge &call_sedge,
170 : const call_and_return_op &call_op,
171 : function &called_fun) const
172 : {
173 9577 : call_string::element_t e (&call_sedge, &call_op, &called_fun);
174 :
175 9577 : if (const call_string **slot = m_children.get (e))
176 1054 : return *slot;
177 :
178 8523 : call_string *result = new call_string (*this, e);
179 8523 : m_children.put (e, result);
180 8523 : return result;
181 : }
182 :
183 : /* Count the number of times the top-most call site appears in the
184 : stack. */
185 : int
186 376761 : call_string::calc_recursion_depth () const
187 : {
188 376761 : if (m_elements.is_empty ())
189 : return 0;
190 119118 : const call_string::element_t top_return_sedge
191 119118 : = m_elements[m_elements.length () - 1];
192 :
193 119118 : int result = 0;
194 350489 : for (const call_string::element_t &e : m_elements)
195 231371 : if (e == top_return_sedge)
196 127826 : ++result;
197 : return result;
198 : }
199 :
200 : /* Count the number of times FUN appears in the string. */
201 :
202 : int
203 8987 : call_string::count_occurrences_of_function (function *fun) const
204 : {
205 8987 : int result = 0;
206 44345 : for (const call_string::element_t &e : m_elements)
207 : {
208 17384 : if (e.get_caller_function () == fun)
209 1993 : result++;
210 17384 : if (e.get_callee_function () == fun)
211 10007 : result++;
212 : }
213 8987 : return result;
214 : }
215 :
216 : /* Comparator for call strings.
217 : This implements a version of lexicographical order.
218 : Return negative if A is before B.
219 : Return positive if B is after A.
220 : Return 0 if they are equal. */
221 :
222 : int
223 1270755 : call_string::cmp (const call_string &a,
224 : const call_string &b)
225 : {
226 1270755 : unsigned len_a = a.length ();
227 1270755 : unsigned len_b = b.length ();
228 :
229 1270755 : unsigned i = 0;
230 2203543 : while (1)
231 : {
232 : /* Consider index i; the strings have been equal up to it. */
233 :
234 : /* Have both strings run out? */
235 1737149 : if (i >= len_a && i >= len_b)
236 : return 0;
237 :
238 : /* Otherwise, has just one of the strings run out? */
239 666730 : if (i >= len_a)
240 : return 1;
241 540661 : if (i >= len_b)
242 : return -1;
243 :
244 : /* Otherwise, compare the elements. */
245 466394 : if (int element_cmp = call_string::element_t::cmp (a[i], b[i]))
246 : return element_cmp;
247 466394 : i++;
248 : // TODO: test coverage for this
249 466394 : }
250 : }
251 :
252 : /* Comparator for use by vec<const call_string *>::qsort. */
253 :
254 : int
255 0 : call_string::cmp_ptr_ptr (const void *pa, const void *pb)
256 : {
257 0 : const call_string *cs_a = *static_cast <const call_string * const *> (pa);
258 0 : const call_string *cs_b = *static_cast <const call_string * const *> (pb);
259 0 : return cmp (*cs_a, *cs_b);
260 : }
261 :
262 : /* Return the pointer to caller of the topmost call in the stack,
263 : or nullptr if stack is empty. */
264 : const supernode *
265 1677 : call_string::get_return_node_in_caller () const
266 : {
267 1677 : if(m_elements.is_empty ())
268 : return nullptr;
269 1677 : return m_elements[m_elements.length () - 1].get_return_snode_in_caller ();
270 : }
271 :
272 : /* Assert that this object is sane. */
273 :
274 : void
275 747360 : call_string::validate () const
276 : {
277 : /* Skip this in a release build. */
278 : #if !CHECKING_P
279 : return;
280 : #endif
281 :
282 982800 : gcc_assert ((m_parent != nullptr)
283 : ^ (m_elements.length () == 0));
284 :
285 : call_string::element_t *e;
286 : int i;
287 1200079 : FOR_EACH_VEC_ELT (m_elements, i, e)
288 : {
289 452719 : gcc_assert (e->m_call_op == e->m_call_sedge->get_op ());
290 : /* Each entry's "caller" should be the "callee" of the
291 : previous entry. */
292 452719 : if (i > 0)
293 217279 : gcc_assert (e->get_caller_function () ==
294 : m_elements[i - 1].get_callee_function ());
295 : }
296 747360 : }
297 :
298 : /* ctor for the root/empty call_string. */
299 :
300 4409 : call_string::call_string ()
301 4409 : : m_parent (nullptr), m_elements ()
302 : {
303 4409 : }
304 :
305 : /* ctor for a child call_string. */
306 :
307 8523 : call_string::call_string (const call_string &parent, const element_t &to_push)
308 8523 : : m_parent (&parent),
309 12731 : m_elements (parent.m_elements.length () + 1)
310 : {
311 8523 : m_elements.splice (parent.m_elements);
312 8523 : m_elements.quick_push (to_push);
313 8523 : }
314 :
315 : /* dtor for call_string: recursively delete children. */
316 :
317 12932 : call_string::~call_string ()
318 : {
319 21455 : for (auto child_iter : m_children)
320 8523 : delete child_iter.second;
321 12932 : }
322 :
323 : /* Log this call_string and all its descendents recursively to LOGGER,
324 : using indentation and elision to highlight the hierarchy. */
325 :
326 : void
327 5 : call_string::recursive_log (logger *logger) const
328 : {
329 5 : logger->start_log_line ();
330 5 : pretty_printer *pp = logger->get_printer ();
331 5 : for (unsigned i = 0; i < length (); i++)
332 0 : pp_string (pp, " ");
333 5 : if (length () > 0)
334 : {
335 0 : pp_string (pp, "[");
336 : /* Elide all but the final element, since they are shared with
337 : the parent call_string. */
338 0 : for (unsigned i = 0; i < length (); i++)
339 0 : pp_string (pp, "..., ");
340 : /* Log the final element in detail. */
341 0 : const element_t *e = &m_elements[m_elements.length () - 1];
342 0 : pp_printf (pp, "(SN: %i -> SN: %i in %s)]",
343 0 : e->m_call_sedge->m_src->m_id,
344 0 : e->m_call_sedge->m_dest->m_id,
345 0 : function_name (e->get_caller_function ()));
346 : }
347 : else
348 5 : pp_string (pp, "[]");
349 5 : logger->end_log_line ();
350 :
351 : /* Recurse into children. */
352 5 : {
353 5 : auto_vec<const call_string *> children (m_children.elements ());
354 5 : for (auto iter : m_children)
355 0 : children.safe_push (iter.second);
356 5 : children.qsort (call_string::cmp_ptr_ptr);
357 :
358 5 : for (auto iter : children)
359 0 : iter->recursive_log (logger);
360 5 : }
361 5 : }
362 :
363 : #endif /* #if ENABLE_ANALYZER */
|