1 /* Call stacks at program points.
2 Copyright (C) 2019-2021 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 "json.h"
28 #include "analyzer/call-string.h"
29 #include "ordered-hash-map.h"
30 #include "options.h"
31 #include "cgraph.h"
32 #include "function.h"
33 #include "cfg.h"
34 #include "basic-block.h"
35 #include "gimple.h"
36 #include "gimple-iterator.h"
37 #include "digraph.h"
38 #include "analyzer/supergraph.h"
39
40 #if ENABLE_ANALYZER
41
42 #if __GNUC__ >= 10
43 #pragma GCC diagnostic ignored "-Wformat-diag"
44 #endif
45
46 /* class call_string. */
47
48 /* struct call_string::element_t. */
49
50 /* call_string::element_t's equality operator. */
51
52 bool
operator ==(const call_string::element_t & other) const53 call_string::element_t::operator== (const call_string::element_t &other) const
54 {
55 return (m_caller == other.m_caller && m_callee == other.m_callee);
56 }
57
58 /* call_string::element_t's inequality operator. */
59 bool
operator !=(const call_string::element_t & other) const60 call_string::element_t::operator!= (const call_string::element_t &other) const
61 {
62 return !(*this == other);
63 }
64
65 function *
get_caller_function() const66 call_string::element_t::get_caller_function () const
67 {
68 return m_caller->get_function ();
69 }
70
71 function *
get_callee_function() const72 call_string::element_t::get_callee_function () const
73 {
74 return m_callee->get_function ();
75 }
76
77 /* call_string's copy ctor. */
78
call_string(const call_string & other)79 call_string::call_string (const call_string &other)
80 : m_elements (other.m_elements.length ())
81 {
82 for (const call_string::element_t &e : other.m_elements)
83 m_elements.quick_push (e);
84 }
85
86 /* call_string's assignment operator. */
87
88 call_string&
operator =(const call_string & other)89 call_string::operator= (const call_string &other)
90 {
91 // would be much simpler if we could rely on vec<> assignment op
92 m_elements.truncate (0);
93 m_elements.reserve (other.m_elements.length (), true);
94 call_string::element_t *e;
95 int i;
96 FOR_EACH_VEC_ELT (other.m_elements, i, e)
97 m_elements.quick_push (*e);
98 return *this;
99 }
100
101 /* call_string's equality operator. */
102
103 bool
operator ==(const call_string & other) const104 call_string::operator== (const call_string &other) const
105 {
106 if (m_elements.length () != other.m_elements.length ())
107 return false;
108 call_string::element_t *e;
109 int i;
110 FOR_EACH_VEC_ELT (m_elements, i, e)
111 if (*e != other.m_elements[i])
112 return false;
113 return true;
114 }
115
116 /* Print this to PP. */
117
118 void
print(pretty_printer * pp) const119 call_string::print (pretty_printer *pp) const
120 {
121 pp_string (pp, "[");
122
123 call_string::element_t *e;
124 int i;
125 FOR_EACH_VEC_ELT (m_elements, i, e)
126 {
127 if (i > 0)
128 pp_string (pp, ", ");
129 pp_printf (pp, "(SN: %i -> SN: %i in %s)",
130 e->m_callee->m_index, e->m_caller->m_index,
131 function_name (e->m_caller->m_fun));
132 }
133
134 pp_string (pp, "]");
135 }
136
137 /* Return a new json::array of the form
138 [{"src_snode_idx" : int,
139 "dst_snode_idx" : int,
140 "funcname" : str},
141 ...for each element in the callstring]. */
142
143 json::value *
to_json() const144 call_string::to_json () const
145 {
146 json::array *arr = new json::array ();
147
148 for (const call_string::element_t &e : m_elements)
149 {
150 json::object *e_obj = new json::object ();
151 e_obj->set ("src_snode_idx",
152 new json::integer_number (e.m_callee->m_index));
153 e_obj->set ("dst_snode_idx",
154 new json::integer_number (e.m_caller->m_index));
155 e_obj->set ("funcname",
156 new json::string (function_name (e.m_caller->m_fun)));
157 arr->append (e_obj);
158 }
159
160 return arr;
161 }
162
163 /* Generate a hash value for this call_string. */
164
165 hashval_t
hash() const166 call_string::hash () const
167 {
168 inchash::hash hstate;
169 for (const call_string::element_t &e : m_elements)
170 hstate.add_ptr (e.m_caller);
171 return hstate.end ();
172 }
173
174 /* Push the return superedge for CALL_SEDGE onto the end of this
175 call_string. */
176
177 void
push_call(const supergraph & sg,const call_superedge * call_sedge)178 call_string::push_call (const supergraph &sg,
179 const call_superedge *call_sedge)
180 {
181 gcc_assert (call_sedge);
182 const return_superedge *return_sedge = call_sedge->get_edge_for_return (sg);
183 gcc_assert (return_sedge);
184 call_string::element_t e (return_sedge->m_dest, return_sedge->m_src);
185 m_elements.safe_push (e);
186 }
187
188 void
push_call(const supernode * caller,const supernode * callee)189 call_string::push_call (const supernode *caller,
190 const supernode *callee)
191 {
192 call_string::element_t e (caller, callee);
193 m_elements.safe_push (e);
194 }
195
196 call_string::element_t
pop()197 call_string::pop ()
198 {
199 return m_elements.pop();
200 }
201
202 /* Count the number of times the top-most call site appears in the
203 stack. */
204 int
calc_recursion_depth() const205 call_string::calc_recursion_depth () const
206 {
207 if (m_elements.is_empty ())
208 return 0;
209 const call_string::element_t top_return_sedge
210 = m_elements[m_elements.length () - 1];
211
212 int result = 0;
213 for (const call_string::element_t &e : m_elements)
214 if (e == top_return_sedge)
215 ++result;
216 return result;
217 }
218
219 /* Comparator for call strings.
220 This implements a version of lexicographical order.
221 Return negative if A is before B.
222 Return positive if B is after A.
223 Return 0 if they are equal. */
224
225 int
cmp(const call_string & a,const call_string & b)226 call_string::cmp (const call_string &a,
227 const call_string &b)
228 {
229 unsigned len_a = a.length ();
230 unsigned len_b = b.length ();
231
232 unsigned i = 0;
233 while (1)
234 {
235 /* Consider index i; the strings have been equal up to it. */
236
237 /* Have both strings run out? */
238 if (i >= len_a && i >= len_b)
239 return 0;
240
241 /* Otherwise, has just one of the strings run out? */
242 if (i >= len_a)
243 return 1;
244 if (i >= len_b)
245 return -1;
246
247 /* Otherwise, compare the node pairs. */
248 const call_string::element_t a_node_pair = a[i];
249 const call_string::element_t b_node_pair = b[i];
250 int src_cmp
251 = a_node_pair.m_callee->m_index - b_node_pair.m_callee->m_index;
252 if (src_cmp)
253 return src_cmp;
254 int dest_cmp
255 = a_node_pair.m_caller->m_index - b_node_pair.m_caller->m_index;
256 if (dest_cmp)
257 return dest_cmp;
258 i++;
259 // TODO: test coverage for this
260 }
261 }
262
263 /* Return the pointer to callee of the topmost call in the stack,
264 or NULL if stack is empty. */
265 const supernode *
get_callee_node() const266 call_string::get_callee_node () const
267 {
268 if(m_elements.is_empty ())
269 return NULL;
270 return m_elements[m_elements.length () - 1].m_callee;
271 }
272
273 /* Return the pointer to caller of the topmost call in the stack,
274 or NULL if stack is empty. */
275 const supernode *
get_caller_node() const276 call_string::get_caller_node () const
277 {
278 if(m_elements.is_empty ())
279 return NULL;
280 return m_elements[m_elements.length () - 1].m_caller;
281 }
282
283 /* Assert that this object is sane. */
284
285 void
validate() const286 call_string::validate () const
287 {
288 /* Skip this in a release build. */
289 #if !CHECKING_P
290 return;
291 #endif
292
293 /* Each entry's "caller" should be the "callee" of the previous entry. */
294 call_string::element_t *e;
295 int i;
296 FOR_EACH_VEC_ELT (m_elements, i, e)
297 if (i > 0)
298 {
299 gcc_assert (e->get_caller_function () ==
300 m_elements[i - 1].get_callee_function ());
301 }
302 }
303
304 #endif /* #if ENABLE_ANALYZER */
305