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