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 : : #include "system.h"
23 : : #include "coretypes.h"
24 : : #include "pretty-print.h"
25 : : #include "tree.h"
26 : : #include "options.h"
27 : : #include "ordered-hash-map.h"
28 : : #include "options.h"
29 : : #include "cgraph.h"
30 : : #include "function.h"
31 : : #include "cfg.h"
32 : : #include "basic-block.h"
33 : : #include "gimple.h"
34 : : #include "gimple-iterator.h"
35 : : #include "digraph.h"
36 : : #include "analyzer/analyzer.h"
37 : : #include "analyzer/analyzer-logging.h"
38 : : #include "analyzer/call-string.h"
39 : : #include "analyzer/supergraph.h"
40 : : #include "make-unique.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 : 44179 : call_string::element_t::operator== (const call_string::element_t &other) const
56 : : {
57 : 44179 : return (m_caller == other.m_caller && m_callee == other.m_callee);
58 : : }
59 : :
60 : : /* call_string::element_t's inequality operator. */
61 : : bool
62 : 13734 : call_string::element_t::operator!= (const call_string::element_t &other) const
63 : : {
64 : 13734 : return !(*this == other);
65 : : }
66 : :
67 : : function *
68 : 573729 : call_string::element_t::get_caller_function () const
69 : : {
70 : 573729 : return m_caller->get_function ();
71 : : }
72 : :
73 : : function *
74 : 401386 : call_string::element_t::get_callee_function () const
75 : : {
76 : 401386 : return m_callee->get_function ();
77 : : }
78 : :
79 : : /* Print this to PP. */
80 : :
81 : : void
82 : 3247 : call_string::print (pretty_printer *pp) const
83 : : {
84 : 3247 : pp_string (pp, "[");
85 : :
86 : 3247 : call_string::element_t *e;
87 : 3247 : int i;
88 : 7556 : FOR_EACH_VEC_ELT (m_elements, i, e)
89 : : {
90 : 1062 : if (i > 0)
91 : 257 : pp_string (pp, ", ");
92 : 2124 : pp_printf (pp, "(SN: %i -> SN: %i in %s)",
93 : 1062 : e->m_callee->m_index, e->m_caller->m_index,
94 : 1062 : function_name (e->m_caller->m_fun));
95 : : }
96 : :
97 : 3247 : pp_string (pp, "]");
98 : 3247 : }
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 : : std::unique_ptr<json::value>
107 : 0 : call_string::to_json () const
108 : : {
109 : 0 : auto arr = ::make_unique<json::array> ();
110 : :
111 : 0 : for (const call_string::element_t &e : m_elements)
112 : : {
113 : 0 : auto e_obj = ::make_unique<json::object> ();
114 : 0 : e_obj->set_integer ("src_snode_idx", e.m_callee->m_index);
115 : 0 : e_obj->set_integer ("dst_snode_idx", e.m_caller->m_index);
116 : 0 : e_obj->set_string ("funcname", function_name (e.m_caller->m_fun));
117 : 0 : arr->append (std::move (e_obj));
118 : 0 : }
119 : :
120 : 0 : return arr;
121 : 0 : }
122 : :
123 : : /* Get or create the call_string resulting from pushing the return
124 : : superedge for CALL_SEDGE onto the end of this call_string. */
125 : :
126 : : const call_string *
127 : 6023 : call_string::push_call (const supergraph &sg,
128 : : const call_superedge *call_sedge) const
129 : : {
130 : 6023 : gcc_assert (call_sedge);
131 : 6023 : const return_superedge *return_sedge = call_sedge->get_edge_for_return (sg);
132 : 6023 : gcc_assert (return_sedge);
133 : 6023 : return push_call (return_sedge->m_dest, return_sedge->m_src);
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 : 6103 : call_string::push_call (const supernode *caller,
141 : : const supernode *callee) const
142 : : {
143 : 6103 : call_string::element_t e (caller, callee);
144 : :
145 : 6103 : if (const call_string **slot = m_children.get (e))
146 : 1297 : return *slot;
147 : :
148 : 4806 : call_string *result = new call_string (*this, e);
149 : 4806 : m_children.put (e, result);
150 : 4806 : return result;
151 : : }
152 : :
153 : : /* Count the number of times the top-most call site appears in the
154 : : stack. */
155 : : int
156 : 6103 : call_string::calc_recursion_depth () const
157 : : {
158 : 6103 : if (m_elements.is_empty ())
159 : : return 0;
160 : 6103 : const call_string::element_t top_return_sedge
161 : 6103 : = m_elements[m_elements.length () - 1];
162 : :
163 : 6103 : int result = 0;
164 : 18269 : for (const call_string::element_t &e : m_elements)
165 : 12166 : if (e == top_return_sedge)
166 : 7815 : ++result;
167 : : return result;
168 : : }
169 : :
170 : : /* Count the number of times FUN appears in the string. */
171 : :
172 : : int
173 : 5460 : call_string::count_occurrences_of_function (function *fun) const
174 : : {
175 : 5460 : int result = 0;
176 : 25661 : for (const call_string::element_t &e : m_elements)
177 : : {
178 : 9281 : if (e.get_callee_function () == fun)
179 : 6309 : result++;
180 : 9281 : if (e.get_caller_function () == fun)
181 : 1751 : result++;
182 : : }
183 : 5460 : return result;
184 : : }
185 : :
186 : : /* Comparator for call strings.
187 : : This implements a version of lexicographical order.
188 : : Return negative if A is before B.
189 : : Return positive if B is after A.
190 : : Return 0 if they are equal. */
191 : :
192 : : int
193 : 1027616 : call_string::cmp (const call_string &a,
194 : : const call_string &b)
195 : : {
196 : 1027616 : unsigned len_a = a.length ();
197 : 1027616 : unsigned len_b = b.length ();
198 : :
199 : 1027616 : unsigned i = 0;
200 : 2265262 : while (1)
201 : : {
202 : : /* Consider index i; the strings have been equal up to it. */
203 : :
204 : : /* Have both strings run out? */
205 : 1646439 : if (i >= len_a && i >= len_b)
206 : : return 0;
207 : :
208 : : /* Otherwise, has just one of the strings run out? */
209 : 813825 : if (i >= len_a)
210 : : return 1;
211 : 671908 : if (i >= len_b)
212 : : return -1;
213 : :
214 : : /* Otherwise, compare the node pairs. */
215 : 618823 : const call_string::element_t a_node_pair = a[i];
216 : 618823 : const call_string::element_t b_node_pair = b[i];
217 : 618823 : int src_cmp
218 : 618823 : = a_node_pair.m_callee->m_index - b_node_pair.m_callee->m_index;
219 : 618823 : if (src_cmp)
220 : : return src_cmp;
221 : 618823 : int dest_cmp
222 : 618823 : = a_node_pair.m_caller->m_index - b_node_pair.m_caller->m_index;
223 : 618823 : if (dest_cmp)
224 : : return dest_cmp;
225 : 618823 : i++;
226 : : // TODO: test coverage for this
227 : 618823 : }
228 : : }
229 : :
230 : : /* Comparator for use by vec<const call_string *>::qsort. */
231 : :
232 : : int
233 : 0 : call_string::cmp_ptr_ptr (const void *pa, const void *pb)
234 : : {
235 : 0 : const call_string *cs_a = *static_cast <const call_string * const *> (pa);
236 : 0 : const call_string *cs_b = *static_cast <const call_string * const *> (pb);
237 : 0 : return cmp (*cs_a, *cs_b);
238 : : }
239 : :
240 : : /* Return the pointer to callee of the topmost call in the stack,
241 : : or NULL if stack is empty. */
242 : : const supernode *
243 : 0 : call_string::get_callee_node () const
244 : : {
245 : 0 : if(m_elements.is_empty ())
246 : : return NULL;
247 : 0 : return m_elements[m_elements.length () - 1].m_callee;
248 : : }
249 : :
250 : : /* Return the pointer to caller of the topmost call in the stack,
251 : : or NULL if stack is empty. */
252 : : const supernode *
253 : 67 : call_string::get_caller_node () const
254 : : {
255 : 67 : if(m_elements.is_empty ())
256 : : return NULL;
257 : 67 : return m_elements[m_elements.length () - 1].m_caller;
258 : : }
259 : :
260 : : /* Assert that this object is sane. */
261 : :
262 : : void
263 : 721988 : call_string::validate () const
264 : : {
265 : : /* Skip this in a release build. */
266 : : #if !CHECKING_P
267 : : return;
268 : : #endif
269 : :
270 : 721988 : gcc_assert (m_parent || m_elements.length () == 0);
271 : :
272 : : /* Each entry's "caller" should be the "callee" of the previous entry. */
273 : : call_string::element_t *e;
274 : : int i;
275 : 1114093 : FOR_EACH_VEC_ELT (m_elements, i, e)
276 : 392105 : if (i > 0)
277 : 172343 : gcc_assert (e->get_caller_function () ==
278 : : m_elements[i - 1].get_callee_function ());
279 : 721988 : }
280 : :
281 : : /* ctor for the root/empty call_string. */
282 : :
283 : 3769 : call_string::call_string ()
284 : 3769 : : m_parent (NULL), m_elements ()
285 : : {
286 : 3769 : }
287 : :
288 : : /* ctor for a child call_string. */
289 : :
290 : 4806 : call_string::call_string (const call_string &parent, const element_t &to_push)
291 : 4806 : : m_parent (&parent),
292 : 6801 : m_elements (parent.m_elements.length () + 1)
293 : : {
294 : 4806 : m_elements.splice (parent.m_elements);
295 : 4806 : m_elements.quick_push (to_push);
296 : 4806 : }
297 : :
298 : : /* dtor for call_string: recursively delete children. */
299 : :
300 : 8575 : call_string::~call_string ()
301 : : {
302 : 18187 : for (auto child_iter : m_children)
303 : 4806 : delete child_iter.second;
304 : 8575 : }
305 : :
306 : : /* Log this call_string and all its descendents recursively to LOGGER,
307 : : using indentation and elision to highlight the hierarchy. */
308 : :
309 : : void
310 : 2 : call_string::recursive_log (logger *logger) const
311 : : {
312 : 2 : logger->start_log_line ();
313 : 2 : pretty_printer *pp = logger->get_printer ();
314 : 2 : for (unsigned i = 0; i < length (); i++)
315 : 0 : pp_string (pp, " ");
316 : 2 : if (length () > 0)
317 : : {
318 : 0 : pp_string (pp, "[");
319 : : /* Elide all but the final element, since they are shared with
320 : : the parent call_string. */
321 : 0 : for (unsigned i = 0; i < length (); i++)
322 : 0 : pp_string (pp, "..., ");
323 : : /* Log the final element in detail. */
324 : 0 : const element_t *e = &m_elements[m_elements.length () - 1];
325 : 0 : pp_printf (pp, "(SN: %i -> SN: %i in %s)]",
326 : 0 : e->m_callee->m_index, e->m_caller->m_index,
327 : 0 : function_name (e->m_caller->m_fun));
328 : : }
329 : : else
330 : 2 : pp_string (pp, "[]");
331 : 2 : logger->end_log_line ();
332 : :
333 : : /* Recurse into children. */
334 : 2 : {
335 : 2 : auto_vec<const call_string *> children (m_children.elements ());
336 : 2 : for (auto iter : m_children)
337 : 0 : children.safe_push (iter.second);
338 : 2 : children.qsort (call_string::cmp_ptr_ptr);
339 : :
340 : 2 : for (auto iter : children)
341 : 0 : iter->recursive_log (logger);
342 : 2 : }
343 : 2 : }
344 : :
345 : : #endif /* #if ENABLE_ANALYZER */
|
