1/* Call stacks at program points.
2 Copyright (C) 2019-2024 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it
8under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
54bool
55call_string::element_t::operator== (const call_string::element_t &other) const
56{
57 return (m_caller == other.m_caller && m_callee == other.m_callee);
58}
59
60/* call_string::element_t's inequality operator. */
61bool
62call_string::element_t::operator!= (const call_string::element_t &other) const
63{
64 return !(*this == other);
65}
66
67function *
68call_string::element_t::get_caller_function () const
69{
70 return m_caller->get_function ();
71}
72
73function *
74call_string::element_t::get_callee_function () const
75{
76 return m_callee->get_function ();
77}
78
79/* Print this to PP. */
80
81void
82call_string::print (pretty_printer *pp) const
83{
84 pp_string (pp, "[");
85
86 call_string::element_t *e;
87 int i;
88 FOR_EACH_VEC_ELT (m_elements, i, e)
89 {
90 if (i > 0)
91 pp_string (pp, ", ");
92 pp_printf (pp, "(SN: %i -> SN: %i in %s)",
93 e->m_callee->m_index, e->m_caller->m_index,
94 function_name (e->m_caller->m_fun));
95 }
96
97 pp_string (pp, "]");
98}
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
106json::value *
107call_string::to_json () const
108{
109 json::array *arr = new json::array ();
110
111 for (const call_string::element_t &e : m_elements)
112 {
113 json::object *e_obj = new json::object ();
114 e_obj->set (key: "src_snode_idx",
115 v: new json::integer_number (e.m_callee->m_index));
116 e_obj->set (key: "dst_snode_idx",
117 v: new json::integer_number (e.m_caller->m_index));
118 e_obj->set (key: "funcname",
119 v: new json::string (function_name (e.m_caller->m_fun)));
120 arr->append (v: e_obj);
121 }
122
123 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
129const call_string *
130call_string::push_call (const supergraph &sg,
131 const call_superedge *call_sedge) const
132{
133 gcc_assert (call_sedge);
134 const return_superedge *return_sedge = call_sedge->get_edge_for_return (sg);
135 gcc_assert (return_sedge);
136 return push_call (src: return_sedge->m_dest, 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
142const call_string *
143call_string::push_call (const supernode *caller,
144 const supernode *callee) const
145{
146 call_string::element_t e (caller, callee);
147
148 if (const call_string **slot = m_children.get (k: e))
149 return *slot;
150
151 call_string *result = new call_string (*this, e);
152 m_children.put (k: e, v: result);
153 return result;
154}
155
156/* Count the number of times the top-most call site appears in the
157 stack. */
158int
159call_string::calc_recursion_depth () const
160{
161 if (m_elements.is_empty ())
162 return 0;
163 const call_string::element_t top_return_sedge
164 = m_elements[m_elements.length () - 1];
165
166 int result = 0;
167 for (const call_string::element_t &e : m_elements)
168 if (e == top_return_sedge)
169 ++result;
170 return result;
171}
172
173/* Count the number of times FUN appears in the string. */
174
175int
176call_string::count_occurrences_of_function (function *fun) const
177{
178 int result = 0;
179 for (const call_string::element_t &e : m_elements)
180 {
181 if (e.get_callee_function () == fun)
182 result++;
183 if (e.get_caller_function () == fun)
184 result++;
185 }
186 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
195int
196call_string::cmp (const call_string &a,
197 const call_string &b)
198{
199 unsigned len_a = a.length ();
200 unsigned len_b = b.length ();
201
202 unsigned i = 0;
203 while (1)
204 {
205 /* Consider index i; the strings have been equal up to it. */
206
207 /* Have both strings run out? */
208 if (i >= len_a && i >= len_b)
209 return 0;
210
211 /* Otherwise, has just one of the strings run out? */
212 if (i >= len_a)
213 return 1;
214 if (i >= len_b)
215 return -1;
216
217 /* Otherwise, compare the node pairs. */
218 const call_string::element_t a_node_pair = a[i];
219 const call_string::element_t b_node_pair = b[i];
220 int src_cmp
221 = a_node_pair.m_callee->m_index - b_node_pair.m_callee->m_index;
222 if (src_cmp)
223 return src_cmp;
224 int dest_cmp
225 = a_node_pair.m_caller->m_index - b_node_pair.m_caller->m_index;
226 if (dest_cmp)
227 return dest_cmp;
228 i++;
229 // TODO: test coverage for this
230 }
231}
232
233/* Comparator for use by vec<const call_string *>::qsort. */
234
235int
236call_string::cmp_ptr_ptr (const void *pa, const void *pb)
237{
238 const call_string *cs_a = *static_cast <const call_string * const *> (pa);
239 const call_string *cs_b = *static_cast <const call_string * const *> (pb);
240 return cmp (a: *cs_a, b: *cs_b);
241}
242
243/* Return the pointer to callee of the topmost call in the stack,
244 or NULL if stack is empty. */
245const supernode *
246call_string::get_callee_node () const
247{
248 if(m_elements.is_empty ())
249 return NULL;
250 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. */
255const supernode *
256call_string::get_caller_node () const
257{
258 if(m_elements.is_empty ())
259 return NULL;
260 return m_elements[m_elements.length () - 1].m_caller;
261}
262
263/* Assert that this object is sane. */
264
265void
266call_string::validate () const
267{
268 /* Skip this in a release build. */
269#if !CHECKING_P
270 return;
271#endif
272
273 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 FOR_EACH_VEC_ELT (m_elements, i, e)
279 if (i > 0)
280 gcc_assert (e->get_caller_function () ==
281 m_elements[i - 1].get_callee_function ());
282}
283
284/* ctor for the root/empty call_string. */
285
286call_string::call_string ()
287: m_parent (NULL), m_elements ()
288{
289}
290
291/* ctor for a child call_string. */
292
293call_string::call_string (const call_string &parent, const element_t &to_push)
294: m_parent (&parent),
295 m_elements (parent.m_elements.length () + 1)
296{
297 m_elements.splice (src: parent.m_elements);
298 m_elements.quick_push (obj: to_push);
299}
300
301/* dtor for call_string: recursively delete children. */
302
303call_string::~call_string ()
304{
305 for (auto child_iter : m_children)
306 delete child_iter.second;
307}
308
309/* Log this call_string and all its descendents recursively to LOGGER,
310 using indentation and elision to highlight the hierarchy. */
311
312void
313call_string::recursive_log (logger *logger) const
314{
315 logger->start_log_line ();
316 pretty_printer *pp = logger->get_printer ();
317 for (unsigned i = 0; i < length (); i++)
318 pp_string (pp, " ");
319 if (length () > 0)
320 {
321 pp_string (pp, "[");
322 /* Elide all but the final element, since they are shared with
323 the parent call_string. */
324 for (unsigned i = 0; i < length (); i++)
325 pp_string (pp, "..., ");
326 /* Log the final element in detail. */
327 const element_t *e = &m_elements[m_elements.length () - 1];
328 pp_printf (pp, "(SN: %i -> SN: %i in %s)]",
329 e->m_callee->m_index, e->m_caller->m_index,
330 function_name (e->m_caller->m_fun));
331 }
332 else
333 pp_string (pp, "[]");
334 logger->end_log_line ();
335
336 /* Recurse into children. */
337 {
338 auto_vec<const call_string *> children (m_children.elements ());
339 for (auto iter : m_children)
340 children.safe_push (obj: iter.second);
341 children.qsort (call_string::cmp_ptr_ptr);
342
343 for (auto iter : children)
344 iter->recursive_log (logger);
345 }
346}
347
348#endif /* #if ENABLE_ANALYZER */
349

source code of gcc/analyzer/call-string.cc