Branch data Line data Source code
1 : : /* Call stacks at program points.
2 : : Copyright (C) 2019-2025 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 : 48282 : call_string::element_t::operator== (const call_string::element_t &other) const
41 : : {
42 : 48282 : return (m_caller == other.m_caller && m_callee == other.m_callee);
43 : : }
44 : :
45 : : /* call_string::element_t's inequality operator. */
46 : : bool
47 : 14679 : call_string::element_t::operator!= (const call_string::element_t &other) const
48 : : {
49 : 14679 : return !(*this == other);
50 : : }
51 : :
52 : : function *
53 : 655725 : call_string::element_t::get_caller_function () const
54 : : {
55 : 655725 : return m_caller->get_function ();
56 : : }
57 : :
58 : : function *
59 : 455049 : call_string::element_t::get_callee_function () const
60 : : {
61 : 455049 : return m_callee->get_function ();
62 : : }
63 : :
64 : : /* Print this to PP. */
65 : :
66 : : void
67 : 3817 : call_string::print (pretty_printer *pp) const
68 : : {
69 : 3817 : pp_string (pp, "[");
70 : :
71 : 3817 : call_string::element_t *e;
72 : 3817 : int i;
73 : 10638 : FOR_EACH_VEC_ELT (m_elements, i, e)
74 : : {
75 : 3004 : if (i > 0)
76 : 1797 : pp_string (pp, ", ");
77 : 6008 : pp_printf (pp, "(SN: %i -> SN: %i in %s)",
78 : 3004 : e->m_callee->m_index, e->m_caller->m_index,
79 : 3004 : function_name (e->m_caller->m_fun));
80 : : }
81 : :
82 : 3817 : pp_string (pp, "]");
83 : 3817 : }
84 : :
85 : : /* Return a new json::array of the form
86 : : [{"src_snode_idx" : int,
87 : : "dst_snode_idx" : int,
88 : : "funcname" : str},
89 : : ...for each element in the callstring]. */
90 : :
91 : : std::unique_ptr<json::value>
92 : 0 : call_string::to_json () const
93 : : {
94 : 0 : auto arr = std::make_unique<json::array> ();
95 : :
96 : 0 : for (const call_string::element_t &e : m_elements)
97 : : {
98 : 0 : auto e_obj = std::make_unique<json::object> ();
99 : 0 : e_obj->set_integer ("src_snode_idx", e.m_callee->m_index);
100 : 0 : e_obj->set_integer ("dst_snode_idx", e.m_caller->m_index);
101 : 0 : e_obj->set_string ("funcname", function_name (e.m_caller->m_fun));
102 : 0 : arr->append (std::move (e_obj));
103 : 0 : }
104 : :
105 : 0 : return arr;
106 : 0 : }
107 : :
108 : : /* Get or create the call_string resulting from pushing the return
109 : : superedge for CALL_SEDGE onto the end of this call_string. */
110 : :
111 : : const call_string *
112 : 6733 : call_string::push_call (const supergraph &sg,
113 : : const call_superedge *call_sedge) const
114 : : {
115 : 6733 : gcc_assert (call_sedge);
116 : 6733 : const return_superedge *return_sedge = call_sedge->get_edge_for_return (sg);
117 : 6733 : gcc_assert (return_sedge);
118 : 6733 : return push_call (return_sedge->m_dest, return_sedge->m_src);
119 : : }
120 : :
121 : : /* Get or create the call_string resulting from pushing the call
122 : : (caller, callee) onto the end of this call_string. */
123 : :
124 : : const call_string *
125 : 6813 : call_string::push_call (const supernode *caller,
126 : : const supernode *callee) const
127 : : {
128 : 6813 : call_string::element_t e (caller, callee);
129 : :
130 : 6813 : if (const call_string **slot = m_children.get (e))
131 : 1256 : return *slot;
132 : :
133 : 5557 : call_string *result = new call_string (*this, e);
134 : 5557 : m_children.put (e, result);
135 : 5557 : return result;
136 : : }
137 : :
138 : : /* Count the number of times the top-most call site appears in the
139 : : stack. */
140 : : int
141 : 6813 : call_string::calc_recursion_depth () const
142 : : {
143 : 6813 : if (m_elements.is_empty ())
144 : : return 0;
145 : 6813 : const call_string::element_t top_return_sedge
146 : 6813 : = m_elements[m_elements.length () - 1];
147 : :
148 : 6813 : int result = 0;
149 : 20666 : for (const call_string::element_t &e : m_elements)
150 : 13853 : if (e == top_return_sedge)
151 : 8408 : ++result;
152 : : return result;
153 : : }
154 : :
155 : : /* Count the number of times FUN appears in the string. */
156 : :
157 : : int
158 : 6218 : call_string::count_occurrences_of_function (function *fun) const
159 : : {
160 : 6218 : int result = 0;
161 : 30024 : for (const call_string::element_t &e : m_elements)
162 : : {
163 : 11370 : if (e.get_callee_function () == fun)
164 : 7001 : result++;
165 : 11370 : if (e.get_caller_function () == fun)
166 : 1649 : result++;
167 : : }
168 : 6218 : return result;
169 : : }
170 : :
171 : : /* Comparator for call strings.
172 : : This implements a version of lexicographical order.
173 : : Return negative if A is before B.
174 : : Return positive if B is after A.
175 : : Return 0 if they are equal. */
176 : :
177 : : int
178 : 1000613 : call_string::cmp (const call_string &a,
179 : : const call_string &b)
180 : : {
181 : 1000613 : unsigned len_a = a.length ();
182 : 1000613 : unsigned len_b = b.length ();
183 : :
184 : 1000613 : unsigned i = 0;
185 : 2095115 : while (1)
186 : : {
187 : : /* Consider index i; the strings have been equal up to it. */
188 : :
189 : : /* Have both strings run out? */
190 : 1547864 : if (i >= len_a && i >= len_b)
191 : : return 0;
192 : :
193 : : /* Otherwise, has just one of the strings run out? */
194 : 744988 : if (i >= len_a)
195 : : return 1;
196 : 608638 : if (i >= len_b)
197 : : return -1;
198 : :
199 : : /* Otherwise, compare the node pairs. */
200 : 547251 : const call_string::element_t a_node_pair = a[i];
201 : 547251 : const call_string::element_t b_node_pair = b[i];
202 : 547251 : int src_cmp
203 : 547251 : = a_node_pair.m_callee->m_index - b_node_pair.m_callee->m_index;
204 : 547251 : if (src_cmp)
205 : : return src_cmp;
206 : 547251 : int dest_cmp
207 : 547251 : = a_node_pair.m_caller->m_index - b_node_pair.m_caller->m_index;
208 : 547251 : if (dest_cmp)
209 : : return dest_cmp;
210 : 547251 : i++;
211 : : // TODO: test coverage for this
212 : 547251 : }
213 : : }
214 : :
215 : : /* Comparator for use by vec<const call_string *>::qsort. */
216 : :
217 : : int
218 : 0 : call_string::cmp_ptr_ptr (const void *pa, const void *pb)
219 : : {
220 : 0 : const call_string *cs_a = *static_cast <const call_string * const *> (pa);
221 : 0 : const call_string *cs_b = *static_cast <const call_string * const *> (pb);
222 : 0 : return cmp (*cs_a, *cs_b);
223 : : }
224 : :
225 : : /* Return the pointer to callee of the topmost call in the stack,
226 : : or nullptr if stack is empty. */
227 : : const supernode *
228 : 0 : call_string::get_callee_node () const
229 : : {
230 : 0 : if(m_elements.is_empty ())
231 : : return nullptr;
232 : 0 : return m_elements[m_elements.length () - 1].m_callee;
233 : : }
234 : :
235 : : /* Return the pointer to caller of the topmost call in the stack,
236 : : or nullptr if stack is empty. */
237 : : const supernode *
238 : 1672 : call_string::get_caller_node () const
239 : : {
240 : 1672 : if(m_elements.is_empty ())
241 : : return nullptr;
242 : 1672 : return m_elements[m_elements.length () - 1].m_caller;
243 : : }
244 : :
245 : : /* Assert that this object is sane. */
246 : :
247 : : void
248 : 765429 : call_string::validate () const
249 : : {
250 : : /* Skip this in a release build. */
251 : : #if !CHECKING_P
252 : : return;
253 : : #endif
254 : :
255 : 765429 : gcc_assert (m_parent || m_elements.length () == 0);
256 : :
257 : : /* Each entry's "caller" should be the "callee" of the previous entry. */
258 : : call_string::element_t *e;
259 : : int i;
260 : 1209108 : FOR_EACH_VEC_ELT (m_elements, i, e)
261 : 443679 : if (i > 0)
262 : 200676 : gcc_assert (e->get_caller_function () ==
263 : : m_elements[i - 1].get_callee_function ());
264 : 765429 : }
265 : :
266 : : /* ctor for the root/empty call_string. */
267 : :
268 : 3880 : call_string::call_string ()
269 : 3880 : : m_parent (nullptr), m_elements ()
270 : : {
271 : 3880 : }
272 : :
273 : : /* ctor for a child call_string. */
274 : :
275 : 5557 : call_string::call_string (const call_string &parent, const element_t &to_push)
276 : 5557 : : m_parent (&parent),
277 : 8083 : m_elements (parent.m_elements.length () + 1)
278 : : {
279 : 5557 : m_elements.splice (parent.m_elements);
280 : 5557 : m_elements.quick_push (to_push);
281 : 5557 : }
282 : :
283 : : /* dtor for call_string: recursively delete children. */
284 : :
285 : 9437 : call_string::~call_string ()
286 : : {
287 : 20551 : for (auto child_iter : m_children)
288 : 5557 : delete child_iter.second;
289 : 9437 : }
290 : :
291 : : /* Log this call_string and all its descendents recursively to LOGGER,
292 : : using indentation and elision to highlight the hierarchy. */
293 : :
294 : : void
295 : 2 : call_string::recursive_log (logger *logger) const
296 : : {
297 : 2 : logger->start_log_line ();
298 : 2 : pretty_printer *pp = logger->get_printer ();
299 : 2 : for (unsigned i = 0; i < length (); i++)
300 : 0 : pp_string (pp, " ");
301 : 2 : if (length () > 0)
302 : : {
303 : 0 : pp_string (pp, "[");
304 : : /* Elide all but the final element, since they are shared with
305 : : the parent call_string. */
306 : 0 : for (unsigned i = 0; i < length (); i++)
307 : 0 : pp_string (pp, "..., ");
308 : : /* Log the final element in detail. */
309 : 0 : const element_t *e = &m_elements[m_elements.length () - 1];
310 : 0 : pp_printf (pp, "(SN: %i -> SN: %i in %s)]",
311 : 0 : e->m_callee->m_index, e->m_caller->m_index,
312 : 0 : function_name (e->m_caller->m_fun));
313 : : }
314 : : else
315 : 2 : pp_string (pp, "[]");
316 : 2 : logger->end_log_line ();
317 : :
318 : : /* Recurse into children. */
319 : 2 : {
320 : 2 : auto_vec<const call_string *> children (m_children.elements ());
321 : 2 : for (auto iter : m_children)
322 : 0 : children.safe_push (iter.second);
323 : 2 : children.qsort (call_string::cmp_ptr_ptr);
324 : :
325 : 2 : for (auto iter : children)
326 : 0 : iter->recursive_log (logger);
327 : 2 : }
328 : 2 : }
329 : :
330 : : #endif /* #if ENABLE_ANALYZER */
|