Line data Source code
1 : /* Base class for svalues and regions.
2 : Copyright (C) 2023-2026 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 "selftest.h"
24 :
25 : #include "diagnostics/markup.h"
26 :
27 : #include "analyzer/symbolic-nodes.h"
28 : #include "analyzer/analyzer-logging.h"
29 : #include "analyzer/region-model.h"
30 : #include "analyzer/region-model-manager.h"
31 : #include "analyzer/symbolic-scalars.h"
32 : #include "analyzer/symbolic-bit-vectors.h"
33 : #include "analyzer/analyzer-selftests.h"
34 :
35 : #if ENABLE_ANALYZER
36 :
37 : namespace ana {
38 :
39 : const char *
40 14 : baseline_state_to_str (baseline_state bs)
41 : {
42 14 : switch (bs)
43 : {
44 0 : default:
45 0 : gcc_unreachable ();
46 : case baseline_state::main:
47 : return "main";
48 14 : case baseline_state::after_main:
49 14 : return "after_main";
50 : }
51 : }
52 :
53 : /* Compare N1 and N2 by id. */
54 :
55 : int
56 980381676 : symbolic::node::cmp_ids (const symbolic::node *n1, const symbolic::node *n2)
57 : {
58 980381676 : return (int)n1->get_id () - (int)n2->get_id ();
59 : }
60 :
61 : /* Comparator for use by vec<const symbol *>::qsort. */
62 :
63 : int
64 0 : symbolic::node::cmp_ptr_ptr (const void *p1, const void *p2)
65 : {
66 0 : const symbolic::node *n1 = *(const symbolic::node * const *)p1;
67 0 : const symbolic::node *n2 = *(const symbolic::node * const *)p2;
68 0 : return cmp_ids (n1, n2);
69 : }
70 :
71 : void
72 490 : symbolic::node::dump_to_pp (pretty_printer *pp,
73 : bool show_ids,
74 : bool elide_repeated_nodes) const
75 : {
76 490 : text_art::theme *theme = global_dc->get_diagram_theme ();
77 490 : symbolic::dump_node_tree_to_pp<symbolic::node> (*this, theme, pp,
78 : show_ids,
79 : elide_repeated_nodes);
80 490 : }
81 :
82 : DEBUG_FUNCTION void
83 0 : symbolic::node::dump () const
84 : {
85 0 : symbolic::dump_node_tree_to_stderr<symbolic::node> (*this);
86 0 : }
87 :
88 : void
89 1745 : symbolic::node::dump_to_logger (logger &log) const
90 : {
91 1745 : symbolic::dump_node_tree_to_logger<symbolic::node> (*this, log);
92 1745 : }
93 :
94 : /* Use NDS to create a text_art::widget describing this node in
95 : a tree-like form, using PREFIX as a prefix (e.g. for field names).
96 : We do this via two vfuncs:
97 : (a) print_dump_widget_label, to populate the text of a tree_widget, and
98 : (b) add_dump_widget_children, to add children to the tree_widget. */
99 :
100 : std::unique_ptr<text_art::tree_widget>
101 21262 : symbolic::node::make_dump_widget (node_dump_state &nds,
102 : const char *prefix) const
103 : {
104 21262 : pretty_printer pp;
105 21262 : pp_format_decoder (&pp) = default_tree_printer;
106 21262 : pp_show_color (&pp) = true;
107 :
108 21262 : if (prefix)
109 14627 : pp_printf (&pp, "%s: ", prefix);
110 :
111 21262 : if (nds.m_show_ids)
112 : {
113 20929 : start_any_dump_color (&pp);
114 20929 : pp_printf (&pp, "(%i): ", get_id ());
115 20929 : end_any_dump_color (&pp);
116 : }
117 :
118 21262 : print_dump_widget_label (&pp);
119 :
120 21262 : nds.m_tree_style_id = nds.m_sm.get_or_create_id (get_text_art_tree_style ());
121 21262 : std::unique_ptr<text_art::tree_widget> w
122 21262 : (text_art::tree_widget::make (nds, &pp));
123 :
124 42191 : if (nds.m_elide_repeated_nodes && nds.m_nodes_seen.contains (this))
125 : {
126 2373 : if (get_complexity ().m_num_nodes > 1)
127 : {
128 939 : pretty_printer complexity_pp;
129 939 : pp_printf (&complexity_pp, "{as above; descendents: %u, depth: %u}",
130 939 : get_complexity ().m_num_nodes,
131 939 : get_complexity ().m_max_depth);
132 1878 : w->add_child (text_art::tree_widget::make (nds, &complexity_pp));
133 939 : }
134 : }
135 : else
136 : {
137 18889 : add_dump_widget_children (*w, nds);
138 18889 : if (nds.m_elide_repeated_nodes)
139 18556 : nds.m_nodes_seen.add (this);
140 : }
141 :
142 42524 : return w;
143 21262 : }
144 :
145 : std::unique_ptr<json::object>
146 1694 : symbolic::node::make_json_obj (const char *type_name) const
147 : {
148 1694 : auto obj = std::make_unique<json::object> ();
149 1694 : obj->set_integer ("id", get_id ());
150 1694 : obj->set_string ("kind", type_name);
151 1694 : return obj;
152 : }
153 :
154 : void
155 43738 : symbolic::node::start_any_dump_color (pretty_printer *pp) const
156 : {
157 43738 : if (pp_show_color (pp))
158 43738 : if (const char *dump_color = get_any_dump_color ())
159 43738 : pp_string (pp, colorize_start (true, dump_color));
160 43738 : }
161 :
162 : void
163 43738 : symbolic::node::end_any_dump_color (pretty_printer *pp) const
164 : {
165 43738 : if (pp_show_color (pp))
166 43738 : if (get_any_dump_color ())
167 43738 : pp_string (pp, colorize_stop (true));
168 43738 : }
169 :
170 : text_art::style
171 21262 : symbolic::node::get_text_art_tree_style () const
172 : {
173 21262 : if (const char *dump_color = get_any_dump_color ())
174 21262 : return text_art::get_style_from_color_cap_name (dump_color);
175 : else
176 0 : return text_art::get_style_from_color_cap_name ("note");
177 : }
178 :
179 : /* Return true iff this node is defined in terms of OTHER
180 : (or *is* OTHER). */
181 :
182 : bool
183 785079 : symbolic::node::involves_p (const symbolic::node &other) const
184 : {
185 : /* Subclass of visitor for use in implementing symbolic::node::involves_p. */
186 :
187 1567703 : class involvement_visitor : public symbolic::node_visitor
188 : {
189 : public:
190 782624 : involvement_visitor (const symbolic::node &needle)
191 782624 : : m_needle (needle), m_found (false) {}
192 :
193 : bool
194 4622581 : visit_node (const symbolic::node &candidate) final override
195 : {
196 4622581 : if (&candidate == &m_needle)
197 2054 : m_found = true;
198 4622581 : return true;
199 : }
200 :
201 782624 : bool found_p () const { return m_found; }
202 :
203 : private:
204 : const symbolic::node &m_needle;
205 : bool m_found;
206 : };
207 :
208 785079 : if (&other == this)
209 : return true;
210 :
211 782624 : involvement_visitor v (other);
212 782624 : accept_node_visitor (v);
213 782624 : return v.found_p ();
214 782624 : }
215 :
216 : // class value_node : public node
217 :
218 : /* Base implementation of value_node::implicitly_live_p. */
219 :
220 : bool
221 83721 : symbolic::value_node::implicitly_live_p (symbolic::liveness_context &) const
222 : {
223 83721 : return false;
224 : }
225 :
226 : // class pp_element_for_node : public pp_element
227 :
228 : void
229 12 : symbolic::pp_element_for_node::add_to_phase_2 (pp_markup::context &ctxt)
230 : {
231 12 : markup_context markup_ctxt (nullptr, m_user_facing);
232 12 : auto markup = m_node.make_markup_node (markup_ctxt);
233 12 : diagnostics::markup::lowering_options opts;
234 12 : auto lowered = markup->lower (opts);
235 12 : lowered->print_to_pp (&ctxt.m_pp);
236 12 : }
237 :
238 : // class node_set : public std::set<const NodeClass *>
239 :
240 : template <typename NodeClass>
241 : bool
242 99391499 : symbolic::node_set<NodeClass>::contains (const NodeClass *n) const
243 : {
244 99391499 : return this->find (n) != this->end ();
245 : }
246 :
247 : template
248 : bool
249 : symbolic::node_set<symbolic::value_node>::contains (const symbolic::value_node *n) const;
250 :
251 : template <typename NodeClass>
252 : std::unique_ptr<text_art::tree_widget>
253 0 : symbolic::node_set<NodeClass>::make_dump_widget (node_dump_state &nds,
254 : const char *prefix) const
255 : {
256 0 : pretty_printer pp;
257 0 : pp_format_decoder (&pp) = default_tree_printer;
258 0 : pp_show_color (&pp) = true;
259 :
260 0 : if (prefix)
261 0 : pp_printf (&pp, "%s: ", prefix);
262 :
263 0 : pp_printf (&pp, "%zu element(s)", this->size ());
264 :
265 0 : std::unique_ptr<text_art::tree_widget> w
266 : (text_art::tree_widget::make (nds, &pp));
267 :
268 0 : for (auto iter : *this)
269 0 : w->add_child (iter->make_dump_widget (nds));
270 :
271 0 : return w;
272 0 : }
273 :
274 : template <typename NodeClass>
275 : void
276 0 : symbolic::node_set<NodeClass>::dump_to_pp (pretty_printer *pp,
277 : bool show_ids,
278 : bool elide_repeated_nodes) const
279 : {
280 0 : text_art::theme *theme = global_dc->get_diagram_theme ();
281 : symbolic::dump_node_tree_to_pp<symbolic::node_set<NodeClass>>
282 0 : (*this, theme, pp, show_ids, elide_repeated_nodes);
283 0 : }
284 :
285 : template
286 : void
287 : symbolic::node_set<symbolic::value_node>::dump_to_pp (pretty_printer *pp,
288 : bool show_ids,
289 : bool elide_repeated_nodes) const;
290 :
291 : template <typename NodeClass>
292 : void
293 0 : symbolic::node_set<NodeClass>::dump () const
294 : {
295 0 : symbolic::dump_node_tree_to_stderr<symbolic::node_set<NodeClass>> (*this);
296 0 : }
297 :
298 : template
299 : void
300 : symbolic::node_set<symbolic::value_node>::dump () const;
301 :
302 : // class node_manager
303 :
304 4409 : symbolic::node_manager::node_manager ()
305 4409 : : m_next_node_id (0),
306 4409 : m_scalar_managers (std::make_unique<symbolic::scalar_managers> (*this)),
307 4409 : m_rmm (std::make_unique<region_model_manager> (*this)),
308 4409 : m_bit_contents_manager
309 : (std::make_unique<symbolic::bit_contents_manager> (*this)),
310 4409 : m_bit_vector_manager (std::make_unique<symbolic::bit_vector_manager> (*this))
311 : {
312 4409 : }
313 :
314 4409 : symbolic::node_manager::~node_manager () = default;
315 :
316 : /* Dump the various managers to LOGGER.
317 : If SHOW_OBJS is true, also dump the objects themselves. */
318 :
319 : void
320 5 : symbolic::node_manager::log_stats (logger *logger, bool show_objs) const
321 : {
322 5 : LOG_SCOPE (logger);
323 :
324 5 : m_rmm->log_stats (logger, show_objs);
325 :
326 : // TODO: log other managers
327 5 : }
328 :
329 : // class node_visitor
330 :
331 : bool
332 14485156 : symbolic::node_visitor::visit_bit_contents (const symbolic::bit_contents &n)
333 : {
334 14485156 : return visit_node (n);
335 : }
336 :
337 : bool
338 23576855 : symbolic::node_visitor::visit_bit_vector (const symbolic::bit_vector &n)
339 : {
340 23576855 : return visit_node (n);
341 : }
342 :
343 : bool
344 103151328 : symbolic::node_visitor::visit_region (const region &n)
345 : {
346 103151328 : return visit_node (n);
347 : }
348 :
349 : bool
350 38530 : symbolic::node_visitor::
351 : visit_scalar_unitless (const symbolic::scalar<integer> &n)
352 : {
353 38530 : return visit_node (n);
354 : }
355 :
356 : bool
357 28851488 : symbolic::node_visitor::
358 : visit_scalar_bit (const symbolic::scalar<integer_with_unit<units::bit>> &n)
359 : {
360 28851488 : return visit_node (n);
361 : }
362 :
363 : bool
364 5779689 : symbolic::node_visitor::
365 : visit_scalar_byte (const symbolic::scalar<integer_with_unit<units::byte>> &n)
366 : {
367 5779689 : return visit_node (n);
368 : }
369 :
370 : bool
371 77102241 : symbolic::node_visitor::visit_svalue (const svalue &n)
372 : {
373 77102241 : return visit_node (n);
374 : }
375 :
376 : // class value_node_visitor : public node_visitor
377 :
378 : bool
379 23123418 : symbolic::value_node_visitor::
380 : visit_bit_vector (const symbolic::bit_vector &bv)
381 : {
382 23123418 : if (!symbolic::node_visitor::visit_bit_vector (bv))
383 : return false;
384 23123418 : return (m_cb)(bv, m_user_data);
385 : }
386 :
387 : bool
388 76229318 : symbolic::value_node_visitor::visit_svalue (const svalue &sval)
389 : {
390 76229318 : if (!symbolic::node_visitor::visit_svalue (sval))
391 : return false;
392 76229318 : return (m_cb)(sval, m_user_data);
393 : }
394 :
395 : #if CHECKING_P
396 :
397 : namespace selftest {
398 :
399 : /* Implementation detail of ASSERT_SYMBOLIC_NODE_DUMP_EQ. */
400 :
401 : void
402 150 : assert_symbolic_node_dump_eq (const ::selftest::location &loc,
403 : const symbolic::node &node,
404 : const char *expected_str)
405 : {
406 150 : pretty_printer pp;
407 150 : pp_format_decoder (&pp) = default_tree_printer;
408 :
409 150 : text_art::ascii_theme theme;
410 150 : symbolic::dump_node_tree_to_pp<symbolic::node> (node, &theme, &pp,
411 : false, false);
412 150 : ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected_str);
413 150 : }
414 :
415 : /* Implementation detail of ASSERT_SAME_SYMBOLIC_NODE. */
416 :
417 : void
418 2984 : assert_same_symbolic_node (const ::selftest::location &loc,
419 : const char *desc_lhs,
420 : const char *desc_rhs,
421 : const symbolic::node *lhs,
422 : const symbolic::node *rhs)
423 : {
424 2984 : if (lhs != rhs)
425 : {
426 0 : pretty_printer pp;
427 0 : pp.set_output_stream (stderr);
428 :
429 0 : pp_string (&pp, "lhs:");
430 0 : pp_newline (&pp);
431 0 : if (lhs)
432 0 : lhs->dump_to_pp (&pp, true);
433 : else
434 : {
435 0 : pp_string (&pp, " nullptr");
436 0 : pp_newline (&pp);
437 : }
438 :
439 0 : pp_string (&pp, "rhs:");
440 0 : pp_newline (&pp);
441 0 : if (rhs)
442 0 : rhs->dump_to_pp (&pp, true);
443 : else
444 : {
445 0 : pp_string (&pp, " nullptr");
446 0 : pp_newline (&pp);
447 : }
448 :
449 0 : pp_flush (&pp);
450 :
451 0 : ::selftest::fail_formatted
452 0 : (loc,
453 : "got different symbolic::nodes for:\n"
454 : " lhs: %s\n"
455 : " rhs: %s\n",
456 : desc_lhs, desc_rhs);
457 : }
458 2984 : }
459 :
460 : /* Implementation detail of ASSERT_DIFFERENT_SYMBOLIC_NODE. */
461 :
462 : void
463 52 : assert_different_symbolic_node (const ::selftest::location &loc,
464 : const char *desc_lhs,
465 : const char *desc_rhs,
466 : const symbolic::node *lhs,
467 : const symbolic::node *rhs)
468 : {
469 52 : if (&lhs == &rhs)
470 : {
471 : pretty_printer pp;
472 : pp.set_output_stream (stderr);
473 :
474 : pp_string (&pp, "lhs:");
475 : pp_newline (&pp);
476 : if (lhs)
477 : lhs->dump_to_pp (&pp, true);
478 : else
479 : {
480 : pp_string (&pp, " nullptr");
481 : pp_newline (&pp);
482 : }
483 :
484 : pp_string (&pp, "rhs:");
485 : pp_newline (&pp);
486 : if (rhs)
487 : rhs->dump_to_pp (&pp, true);
488 : else
489 : {
490 : pp_string (&pp, " nullptr");
491 : pp_newline (&pp);
492 : }
493 :
494 : pp_flush (&pp);
495 :
496 : ::selftest::fail_formatted
497 : (loc,
498 : "got same symbolic_node for:\n"
499 : " lhs: %s\n"
500 : " rhs: %s\n",
501 : desc_lhs, desc_rhs);
502 : }
503 52 : }
504 :
505 : /* Implementation detail of ASSERT_SYMBOLIC_NODE_MARKUP_TEXT_EQ. */
506 :
507 : void
508 184 : assert_symbolic_node_markup_text_eq (const ::selftest::location &loc,
509 : const symbolic::node &sym_node,
510 : const diagnostics::markup::lowering_options &opts,
511 : const char *expected_str)
512 : {
513 184 : symbolic::markup_context markup_ctxt (nullptr, true);
514 184 : auto markup = sym_node.make_markup_node (markup_ctxt);
515 184 : ASSERT_MARKUP_TEXT_EQ_AT (loc, *markup, opts, expected_str);
516 184 : }
517 :
518 : static void
519 4 : test_node_visitor ()
520 : {
521 4 : struct recorder : public ana::symbolic::node_visitor
522 : {
523 : bool
524 4 : visit_node (const ana::symbolic::node &n)
525 : {
526 4 : m_nodes_visited.push_back (&n);
527 4 : return true;
528 : }
529 :
530 : std::vector<const ana::symbolic::node *> m_nodes_visited;
531 : };
532 :
533 4 : symbolic::node_manager node_mgr;
534 4 : auto &bv_mgr = node_mgr.get_bit_vector_manager ();
535 4 : auto &unknown_32_bits = bv_mgr.get_unknown_bits (32_bits);
536 :
537 4 : recorder r;
538 4 : unknown_32_bits.accept_node_visitor (r);
539 4 : ASSERT_SAME_SYMBOLIC_NODE (r.m_nodes_visited[0], &unknown_32_bits);
540 : // FIXME: we also ought to visit the size, but we don't currently
541 4 : }
542 :
543 : /* Run all of the selftests within this file. */
544 :
545 : void
546 4 : analyzer_symbolic_nodes_cc_tests ()
547 : {
548 4 : test_node_visitor ();
549 4 : }
550 :
551 : } // namespace selftest
552 :
553 : #endif /* CHECKING_P */
554 :
555 : } // namespace ana
556 :
557 : #endif /* #if ENABLE_ANALYZER */
|