Branch data Line data Source code
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 : 53286 : call_string::element_t::operator== (const call_string::element_t &other) const
56 : : {
57 : 53286 : return (m_caller == other.m_caller && m_callee == other.m_callee);
58 : : }
59 : :
60 : : /* call_string::element_t's inequality operator. */
61 : : bool
62 : 16157 : call_string::element_t::operator!= (const call_string::element_t &other) const
63 : : {
64 : 16157 : return !(*this == other);
65 : : }
66 : :
67 : : function *
68 : 709850 : call_string::element_t::get_caller_function () const
69 : : {
70 : 709850 : return m_caller->get_function ();
71 : : }
72 : :
73 : : function *
74 : 493733 : call_string::element_t::get_callee_function () const
75 : : {
76 : 493733 : return m_callee->get_function ();
77 : : }
78 : :
79 : : /* Print this to PP. */
80 : :
81 : : void
82 : 3890 : call_string::print (pretty_printer *pp) const
83 : : {
84 : 3890 : pp_string (pp, "[");
85 : :
86 : 3890 : call_string::element_t *e;
87 : 3890 : int i;
88 : 9104 : FOR_EACH_VEC_ELT (m_elements, i, e)
89 : : {
90 : 1324 : if (i > 0)
91 : 328 : pp_string (pp, ", ");
92 : 2648 : pp_printf (pp, "(SN: %i -> SN: %i in %s)",
93 : 1324 : e->m_callee->m_index, e->m_caller->m_index,
94 : 1324 : function_name (e->m_caller->m_fun));
95 : : }
96 : :
97 : 3890 : pp_string (pp, "]");
98 : 3890 : }
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 : 0 : call_string::to_json () const
108 : : {
109 : 0 : json::array *arr = new json::array ();
110 : :
111 : 0 : for (const call_string::element_t &e : m_elements)
112 : : {
113 : 0 : json::object *e_obj = new json::object ();
114 : 0 : e_obj->set ("src_snode_idx",
115 : 0 : new json::integer_number (e.m_callee->m_index));
116 : 0 : e_obj->set ("dst_snode_idx",
117 : 0 : new json::integer_number (e.m_caller->m_index));
118 : 0 : e_obj->set ("funcname",
119 : 0 : new json::string (function_name (e.m_caller->m_fun)));
120 : 0 : arr->append (e_obj);
121 : : }
122 : :
123 : 0 : 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 : 7287 : call_string::push_call (const supergraph &sg,
131 : : const call_superedge *call_sedge) const
132 : : {
133 : 7287 : gcc_assert (call_sedge);
134 : 7287 : const return_superedge *return_sedge = call_sedge->get_edge_for_return (sg);
135 : 7287 : gcc_assert (return_sedge);
136 : 7287 : return push_call (return_sedge->m_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 : 7388 : call_string::push_call (const supernode *caller,
144 : : const supernode *callee) const
145 : : {
146 : 7388 : call_string::element_t e (caller, callee);
147 : :
148 : 7388 : if (const call_string **slot = m_children.get (e))
149 : 1587 : return *slot;
150 : :
151 : 5801 : call_string *result = new call_string (*this, e);
152 : 5801 : m_children.put (e, result);
153 : 5801 : return result;
154 : : }
155 : :
156 : : /* Count the number of times the top-most call site appears in the
157 : : stack. */
158 : : int
159 : 7388 : call_string::calc_recursion_depth () const
160 : : {
161 : 7388 : if (m_elements.is_empty ())
162 : : return 0;
163 : 7388 : const call_string::element_t top_return_sedge
164 : 7388 : = m_elements[m_elements.length () - 1];
165 : :
166 : 7388 : int result = 0;
167 : 22258 : for (const call_string::element_t &e : m_elements)
168 : 14870 : if (e == top_return_sedge)
169 : 9489 : ++result;
170 : : return result;
171 : : }
172 : :
173 : : /* Count the number of times FUN appears in the string. */
174 : :
175 : : int
176 : 6598 : call_string::count_occurrences_of_function (function *fun) const
177 : : {
178 : 6598 : int result = 0;
179 : 31112 : for (const call_string::element_t &e : m_elements)
180 : : {
181 : 11318 : if (e.get_callee_function () == fun)
182 : 7633 : result++;
183 : 11318 : if (e.get_caller_function () == fun)
184 : 2151 : result++;
185 : : }
186 : 6598 : 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 : 1255235 : call_string::cmp (const call_string &a,
197 : : const call_string &b)
198 : : {
199 : 1255235 : unsigned len_a = a.length ();
200 : 1255235 : unsigned len_b = b.length ();
201 : :
202 : 1255235 : unsigned i = 0;
203 : 2796719 : while (1)
204 : : {
205 : : /* Consider index i; the strings have been equal up to it. */
206 : :
207 : : /* Have both strings run out? */
208 : 2025977 : if (i >= len_a && i >= len_b)
209 : : return 0;
210 : :
211 : : /* Otherwise, has just one of the strings run out? */
212 : 1011208 : if (i >= len_a)
213 : : return 1;
214 : 834784 : if (i >= len_b)
215 : : return -1;
216 : :
217 : : /* Otherwise, compare the node pairs. */
218 : 770742 : const call_string::element_t a_node_pair = a[i];
219 : 770742 : const call_string::element_t b_node_pair = b[i];
220 : 770742 : int src_cmp
221 : 770742 : = a_node_pair.m_callee->m_index - b_node_pair.m_callee->m_index;
222 : 770742 : if (src_cmp)
223 : 0 : return src_cmp;
224 : 770742 : int dest_cmp
225 : 770742 : = a_node_pair.m_caller->m_index - b_node_pair.m_caller->m_index;
226 : 770742 : if (dest_cmp)
227 : 0 : return dest_cmp;
228 : 770742 : i++;
229 : : // TODO: test coverage for this
230 : 770742 : }
231 : : }
232 : :
233 : : /* Comparator for use by vec<const call_string *>::qsort. */
234 : :
235 : : int
236 : 0 : call_string::cmp_ptr_ptr (const void *pa, const void *pb)
237 : : {
238 : 0 : const call_string *cs_a = *static_cast <const call_string * const *> (pa);
239 : 0 : const call_string *cs_b = *static_cast <const call_string * const *> (pb);
240 : 0 : return cmp (*cs_a, *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 : 0 : call_string::get_callee_node () const
247 : : {
248 : 0 : if(m_elements.is_empty ())
249 : : return NULL;
250 : 0 : 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 : 84 : call_string::get_caller_node () const
257 : : {
258 : 84 : if(m_elements.is_empty ())
259 : : return NULL;
260 : 84 : return m_elements[m_elements.length () - 1].m_caller;
261 : : }
262 : :
263 : : /* Assert that this object is sane. */
264 : :
265 : : void
266 : 863728 : call_string::validate () const
267 : : {
268 : : /* Skip this in a release build. */
269 : : #if !CHECKING_P
270 : : return;
271 : : #endif
272 : :
273 : 863728 : 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 : 1346143 : FOR_EACH_VEC_ELT (m_elements, i, e)
279 : 482415 : if (i > 0)
280 : 216117 : gcc_assert (e->get_caller_function () ==
281 : : m_elements[i - 1].get_callee_function ());
282 : 863728 : }
283 : :
284 : : /* ctor for the root/empty call_string. */
285 : :
286 : 4309 : call_string::call_string ()
287 : 4309 : : m_parent (NULL), m_elements ()
288 : : {
289 : 4309 : }
290 : :
291 : : /* ctor for a child call_string. */
292 : :
293 : 5801 : call_string::call_string (const call_string &parent, const element_t &to_push)
294 : 5801 : : m_parent (&parent),
295 : 8252 : m_elements (parent.m_elements.length () + 1)
296 : : {
297 : 5801 : m_elements.splice (parent.m_elements);
298 : 5801 : m_elements.quick_push (to_push);
299 : 5801 : }
300 : :
301 : : /* dtor for call_string: recursively delete children. */
302 : :
303 : 10110 : call_string::~call_string ()
304 : : {
305 : 21712 : for (auto child_iter : m_children)
306 : 5801 : delete child_iter.second;
307 : 10110 : }
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 : 2 : call_string::recursive_log (logger *logger) const
314 : : {
315 : 2 : logger->start_log_line ();
316 : 2 : pretty_printer *pp = logger->get_printer ();
317 : 2 : for (unsigned i = 0; i < length (); i++)
318 : 0 : pp_string (pp, " ");
319 : 2 : if (length () > 0)
320 : : {
321 : 0 : pp_string (pp, "[");
322 : : /* Elide all but the final element, since they are shared with
323 : : the parent call_string. */
324 : 0 : for (unsigned i = 0; i < length (); i++)
325 : 0 : pp_string (pp, "..., ");
326 : : /* Log the final element in detail. */
327 : 0 : const element_t *e = &m_elements[m_elements.length () - 1];
328 : 0 : pp_printf (pp, "(SN: %i -> SN: %i in %s)]",
329 : 0 : e->m_callee->m_index, e->m_caller->m_index,
330 : 0 : function_name (e->m_caller->m_fun));
331 : : }
332 : : else
333 : 2 : pp_string (pp, "[]");
334 : 2 : logger->end_log_line ();
335 : :
336 : : /* Recurse into children. */
337 : 2 : {
338 : 2 : auto_vec<const call_string *> children (m_children.elements ());
339 : 2 : for (auto iter : m_children)
340 : 0 : children.safe_push (iter.second);
341 : 2 : children.qsort (call_string::cmp_ptr_ptr);
342 : :
343 : 2 : for (auto iter : children)
344 : 0 : iter->recursive_log (logger);
345 : 2 : }
346 : 2 : }
347 : :
348 : : #endif /* #if ENABLE_ANALYZER */
|
