Line data Source code
1 : /* Unit-safe symbolic scalar values (e.g. "n * 32 bytes")
2 : Copyright (C) 2019-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/region-model-manager.h"
28 : #include "analyzer/symbolic-scalars.h"
29 : #include "analyzer/region-model.h"
30 :
31 : #if ENABLE_ANALYZER
32 :
33 : namespace ana {
34 : namespace symbolic {
35 :
36 : // template<typename ConcreteValueType> class scalar : public symbolic::node
37 :
38 : template<typename ConcreteValueType>
39 : bool
40 18352885 : scalar<ConcreteValueType>::is_zero_p () const
41 : {
42 18352885 : if (auto concrete = dyn_cast_concrete_scalar ())
43 18134318 : return concrete->get_concrete ().is_zero_p ();
44 : return false;
45 : }
46 :
47 : template
48 : bool
49 : scalar<integer_with_unit<units::bit>>::is_zero_p () const;
50 :
51 : template
52 : bool
53 : scalar<integer_with_unit<units::byte>>::is_zero_p () const;
54 :
55 : template
56 : bool
57 : scalar<integer>::is_zero_p () const;
58 :
59 : template<typename ConcreteValueType>
60 : bool
61 11145 : scalar<ConcreteValueType>::is_one_p () const
62 : {
63 11145 : if (auto concrete = dyn_cast_concrete_scalar ())
64 8677 : return concrete->get_concrete ().is_one_p ();
65 : return false;
66 : }
67 :
68 : template
69 : bool
70 : scalar<integer_with_unit<units::bit>>::is_one_p () const;
71 :
72 : template
73 : bool
74 : scalar<integer_with_unit<units::byte>>::is_one_p () const;
75 :
76 : template
77 : bool
78 : scalar<integer>::is_one_p () const;
79 :
80 : template<typename ConcreteValueType>
81 : bool
82 57539 : scalar<ConcreteValueType>::is_unknown_p () const
83 : {
84 57539 : if (auto *from_sval = dyn_cast_scalar_from_svalue ())
85 14227 : return from_sval->get_svalue ().get_kind () == SK_UNKNOWN;
86 : return false;
87 : }
88 :
89 : template<typename ConcreteValueType>
90 : void
91 2928 : scalar<ConcreteValueType>::print_dump_widget_label (pretty_printer *pp) const
92 : {
93 2928 : start_any_dump_color (pp);
94 2928 : print_dump_widget_label_for_scalar (pp);
95 2928 : end_any_dump_color (pp);
96 2928 : }
97 :
98 : template<>
99 : std::unique_ptr<json::object>
100 20 : scalar<integer>::make_json_obj (const char *type_name) const
101 : {
102 20 : return value_node::make_json_obj (type_name);
103 : }
104 :
105 : template<>
106 : std::unique_ptr<json::object>
107 232 : scalar<integer_with_unit<units::bit>>::make_json_obj (const char *type_name) const
108 : {
109 232 : auto obj = value_node::make_json_obj (type_name);
110 232 : obj->set_string ("unit", "bit");
111 232 : return obj;
112 : }
113 :
114 : template<>
115 : std::unique_ptr<json::object>
116 129 : scalar<integer_with_unit<units::byte>>::make_json_obj (const char *type_name) const
117 : {
118 129 : auto obj = value_node::make_json_obj (type_name);
119 129 : obj->set_string ("unit", "byte");
120 129 : return obj;
121 : }
122 :
123 : /* A total ordering on scalars, which attempts to do the right
124 : thing where the scalars are directly comparable (using
125 : get_partial_ordering), with fallbacks for other cases. */
126 :
127 : template<typename ConcreteValueType>
128 : bool
129 2760 : scalar<ConcreteValueType>::
130 : get_total_ordering (const scalar<ConcreteValueType> &a,
131 : enum tree_code op,
132 : const scalar<ConcreteValueType> &b,
133 : const region_model *model)
134 : {
135 2760 : tristate partial = get_partial_ordering (a, op, b, model);
136 2760 : if (partial.is_known ())
137 2324 : return partial.is_true ();
138 :
139 436 : ConcreteValueType conc_a;
140 436 : if (concrete_from_symbolic (a, &conc_a))
141 : {
142 109 : ConcreteValueType conc_b;
143 109 : if (concrete_from_symbolic (b, &conc_b))
144 : {
145 : /* Concrete vs concrete: should have already been handled
146 : by get_partial_ordering. */
147 0 : gcc_unreachable ();
148 : }
149 : else
150 : {
151 : /* Concrete vs symbolic: put all concrete before all symbolic. */
152 109 : switch (op)
153 : {
154 0 : default:
155 0 : gcc_unreachable ();
156 : case NE_EXPR:
157 : case LT_EXPR:
158 : case LE_EXPR:
159 : return true;
160 36 : case EQ_EXPR:
161 : case GT_EXPR:
162 : case GE_EXPR:
163 36 : return false;
164 : }
165 : }
166 109 : }
167 : else
168 : {
169 327 : ConcreteValueType conc_b;
170 327 : if (concrete_from_symbolic (b, &conc_b))
171 : {
172 : /* Symbolic vs concrete: put all symbolic after all concrete. */
173 117 : switch (op)
174 : {
175 0 : default:
176 0 : gcc_unreachable ();
177 : case EQ_EXPR:
178 : case LT_EXPR:
179 : case LE_EXPR:
180 : return false;
181 66 : case NE_EXPR:
182 : case GT_EXPR:
183 : case GE_EXPR:
184 66 : return true;
185 : }
186 : }
187 : else
188 : {
189 : /* Symbolic vs symbolic with unknown ordering.
190 : Fall back to ID order. */
191 210 : int cmp_ids = symbolic::node::cmp_ids (&a, &b);
192 210 : switch (op)
193 : {
194 0 : default:
195 0 : gcc_unreachable ();
196 12 : case EQ_EXPR:
197 12 : return cmp_ids == 0;
198 12 : case NE_EXPR:
199 12 : return cmp_ids != 0;
200 90 : case LT_EXPR:
201 90 : return cmp_ids < 0;
202 48 : case LE_EXPR:
203 48 : return cmp_ids <= 0;
204 24 : case GT_EXPR:
205 24 : return cmp_ids > 0;
206 24 : case GE_EXPR:
207 24 : return cmp_ids >= 0;
208 : }
209 : }
210 327 : }
211 436 : }
212 :
213 : template<typename ConcreteValueType>
214 : tristate
215 4025 : scalar<ConcreteValueType>::
216 : get_partial_ordering (const scalar<ConcreteValueType> &a,
217 : enum tree_code op,
218 : const scalar<ConcreteValueType> &b,
219 : const region_model *model)
220 : {
221 4025 : ConcreteValueType conc_a;
222 4025 : if (concrete_from_symbolic (a, &conc_a))
223 : {
224 2725 : ConcreteValueType conc_b;
225 2725 : if (concrete_from_symbolic (b, &conc_b))
226 : {
227 : /* Concrete vs concrete. */
228 2588 : switch (op)
229 : {
230 0 : default:
231 0 : gcc_unreachable ();
232 821 : case EQ_EXPR:
233 1069 : return conc_a == conc_b;
234 24 : case NE_EXPR:
235 36 : return conc_a != conc_b;
236 145 : case LT_EXPR:
237 201 : return conc_a < conc_b;
238 1354 : case LE_EXPR:
239 1699 : return conc_a <= conc_b;
240 86 : case GT_EXPR:
241 144 : return conc_a > conc_b;
242 158 : case GE_EXPR:
243 220 : return conc_a >= conc_b;
244 : }
245 : }
246 : else
247 : {
248 : /* Concrete vs symbolic: can't compare. */
249 137 : return tristate::unknown ();
250 : }
251 2725 : }
252 : else
253 : {
254 1300 : ConcreteValueType conc_b;
255 1300 : if (concrete_from_symbolic (b, &conc_b))
256 : {
257 : /* Concrete vs symbolic: can't compare. */
258 162 : return tristate::unknown ();
259 : }
260 : else
261 : {
262 : /* Symbolic vs symbolic. */
263 :
264 : /* Check for identity. */
265 1138 : if (&a == &b)
266 140 : switch (op)
267 : {
268 0 : default:
269 0 : gcc_unreachable ();
270 54 : case NE_EXPR:
271 : case LT_EXPR:
272 : case GT_EXPR:
273 54 : return false;
274 :
275 86 : case EQ_EXPR:
276 : case LE_EXPR:
277 : case GE_EXPR:
278 86 : return true;
279 : }
280 :
281 : /* Try taking their difference to see if it simplifies
282 : to a concrete value. */;
283 998 : auto &diff = a - b;
284 998 : ConcreteValueType conc_diff;
285 998 : if (concrete_from_symbolic (diff, &conc_diff))
286 : {
287 486 : switch (op)
288 : {
289 0 : default:
290 0 : gcc_unreachable ();
291 8 : case EQ_EXPR:
292 12 : return conc_diff.get_integer () == 0;
293 8 : case NE_EXPR:
294 24 : return conc_diff.get_integer () != 0;
295 319 : case LT_EXPR:
296 327 : return conc_diff.get_integer () < 0;
297 87 : case LE_EXPR:
298 154 : return conc_diff.get_integer () <= 0;
299 24 : case GT_EXPR:
300 36 : return conc_diff.get_integer () > 0;
301 24 : case GE_EXPR:
302 36 : return conc_diff.get_integer () >= 0;
303 : }
304 : }
305 :
306 512 : if (auto *bits_from_bytes_a = a.dyn_cast_bits_from_bytes_scalar ())
307 90 : if (auto *bits_from_bytes_b = b.dyn_cast_bits_from_bytes_scalar ())
308 : return symbolic_byte_size::get_partial_ordering
309 90 : (bits_from_bytes_a->get_bytes (),
310 : op,
311 90 : bits_from_bytes_b->get_bytes (),
312 90 : model);
313 :
314 422 : if (auto *scalar_from_sval_a = a.dyn_cast_scalar_from_svalue ())
315 218 : if (auto *scalar_from_sval_b = b.dyn_cast_scalar_from_svalue ())
316 : {
317 : // TODO: would be nice not to need a region_model here
318 212 : auto &node_mgr = a.get_mgr ().get_node_manager ();
319 212 : const region_model placeholder_model (node_mgr);
320 212 : const region_model *tmp_model = model;
321 212 : if (!tmp_model)
322 0 : tmp_model = &placeholder_model;
323 212 : auto ts_sval = tmp_model->eval_condition
324 212 : (&scalar_from_sval_a->get_svalue (),
325 : op,
326 212 : &scalar_from_sval_b->get_svalue ());
327 212 : if (ts_sval.is_known ())
328 80 : return ts_sval;
329 212 : }
330 :
331 342 : return tristate::unknown ();
332 998 : }
333 1300 : }
334 4025 : }
335 :
336 : template
337 : bool
338 : symbolic_bit_size::get_total_ordering (const symbolic_bit_size &a,
339 : enum tree_code op,
340 : const symbolic_bit_size &b,
341 : const region_model *model);
342 :
343 : template
344 : bool
345 : symbolic_byte_size::get_total_ordering (const symbolic_byte_size &a,
346 : enum tree_code op,
347 : const symbolic_byte_size &b,
348 : const region_model *model);
349 :
350 : // template<typename ConcreteValueType> class concrete_scalar : public scalar<ConcreteValueType>
351 :
352 : template<typename ConcreteValueType>
353 91190 : concrete_scalar<ConcreteValueType>::
354 : concrete_scalar (unsigned id,
355 : scalar_manager<ConcreteValueType> &mgr,
356 : const ConcreteValueType &value)
357 91190 : : scalar<ConcreteValueType> (complexity (1, 1), id, mgr,
358 : scalar<ConcreteValueType>::kind::concrete),
359 91190 : m_value (value)
360 : {
361 : }
362 :
363 : template<>
364 : const integer &
365 2412 : concrete_scalar<concrete_bit_size>::get_integer () const
366 : {
367 2412 : return m_value.get_integer ();
368 : }
369 :
370 : template<>
371 : const integer &
372 117687 : concrete_scalar<concrete_byte_size>::get_integer () const
373 : {
374 117687 : return m_value.get_integer ();
375 : }
376 :
377 : template<>
378 : const integer &
379 2429 : concrete_scalar<integer>::get_integer () const
380 : {
381 2429 : return m_value;
382 : }
383 :
384 : template<typename ConcreteValueType>
385 : void
386 1466 : concrete_scalar<ConcreteValueType>::
387 : print_dump_widget_label_for_scalar (pretty_printer *pp) const
388 : {
389 1466 : pp_printf (pp, "concrete_scalar<%s>: ", ConcreteValueType::dump_type_name);
390 1466 : m_value.dump_to_pp (pp);
391 1466 : }
392 :
393 : template<typename ConcreteValueType>
394 : void
395 1305 : concrete_scalar<ConcreteValueType>::
396 : add_dump_widget_children (text_art::tree_widget &,
397 : node_dump_state &) const
398 : {
399 : // no-op
400 1305 : }
401 :
402 : template<>
403 : void
404 0 : concrete_scalar<integer>::accept_node_visitor (symbolic::node_visitor &v) const
405 : {
406 0 : v.visit_scalar_unitless (*this);
407 0 : }
408 :
409 : template<>
410 : void
411 27324349 : concrete_scalar<integer_with_unit<units::bit>>::accept_node_visitor (symbolic::node_visitor &v) const
412 : {
413 27324349 : v.visit_scalar_bit (*this);
414 27324349 : }
415 :
416 : template<>
417 : void
418 3892522 : concrete_scalar<integer_with_unit<units::byte>>::
419 : accept_node_visitor (symbolic::node_visitor &v) const
420 : {
421 3892522 : v.visit_scalar_byte (*this);
422 3892522 : }
423 :
424 : template<typename ConcreteValueType>
425 : std::unique_ptr<json::object>
426 325 : concrete_scalar<ConcreteValueType>::to_json () const
427 : {
428 325 : auto obj = scalar<ConcreteValueType>::make_json_obj ("concrete_scalar");
429 325 : obj->set ("value", m_value.to_json ());
430 325 : return obj;
431 : }
432 :
433 : template<typename ConcreteValueType>
434 : void
435 2774 : concrete_scalar<ConcreteValueType>::
436 : dump_inline_to_pp (pretty_printer *pp, enum units::role role) const
437 : {
438 2774 : m_value.dump_to_pp (pp, role);
439 2766 : }
440 :
441 : template<>
442 : void
443 0 : concrete_scalar<integer>::
444 : dump_inline_to_pp (pretty_printer *pp, enum units::role) const
445 : {
446 0 : m_value.dump_to_pp (pp);
447 0 : }
448 :
449 : template<typename ConcreteValueType>
450 : std::unique_ptr<diagnostics::markup::node>
451 74 : concrete_scalar<ConcreteValueType>::make_markup_node (markup_context &) const
452 : {
453 74 : pretty_printer pp;
454 74 : m_value.dump_to_pp (&pp);
455 74 : return diagnostics::markup::make_text_node (pp_formatted_text (&pp));
456 74 : }
457 :
458 : // template<typename ConcreteValueType> class sum : public scalar<ConcreteValueType>
459 :
460 : template<typename ConcreteValueType>
461 : bool
462 1299094 : sum<ConcreteValueType>::memoization_key::
463 : operator< (const memoization_key &other) const
464 : {
465 1299094 : if (m_addends.size () != other.m_addends.size ())
466 3426 : return m_addends.size () < other.m_addends.size ();
467 2392071 : for (size_t i = 0 ; i < m_addends.size (); ++i)
468 2010393 : if (int c = symbolic::node::cmp (*m_addends[i],
469 2010393 : *other.m_addends[i]))
470 913990 : return c < 0;
471 : return false;
472 : }
473 :
474 : template<typename ConcreteValueType>
475 : void
476 57547 : sum<ConcreteValueType>::folding_helper::
477 : add_addend (const scalar<ConcreteValueType> &addend,
478 : scalar_manager<integer> &unitless_mgr)
479 : {
480 : /* Accumulate the sum of any concrete terms. */
481 57547 : if (auto concrete = addend.dyn_cast_concrete_scalar ())
482 45150 : m_sum_of_concrete_values += concrete->get_concrete ();
483 12397 : else if (auto sum = addend.dyn_cast_sum ())
484 : {
485 : /* Flatten sums of sums. */
486 1950 : for (auto symbolic : sum->m_symbolic_addends)
487 1059 : add_addend (*symbolic, unitless_mgr);
488 891 : if (auto concrete = sum->m_concrete_addend)
489 785 : m_sum_of_concrete_values += concrete->get_concrete ();
490 : }
491 11506 : else if (auto product = addend.dyn_cast_product ())
492 1765 : add_to_coefficient_for_addend (&product->get_lhs (),
493 1765 : &product->get_rhs ());
494 : else
495 9741 : add_to_coefficient_for_addend (&addend,
496 19482 : &unitless_mgr.get_concrete (1));
497 57547 : }
498 :
499 : /* Update MAP by adding COEFFICIENT_CHANGE to the coefficient for TERM
500 : (if any). */
501 :
502 : template <typename Term, typename Coefficient>
503 : static void
504 11506 : add_coefficient_to_term (std::map<const Term *, const Coefficient *> &map,
505 : const Term *term,
506 : const Coefficient *coefficient_change)
507 : {
508 11506 : auto iter = map.find (term);
509 11506 : if (iter == map.end ())
510 11140 : map.insert ({term, coefficient_change});
511 : else
512 : {
513 366 : auto &coefficient = map[term];
514 366 : coefficient = &(*coefficient + *coefficient_change);
515 : }
516 11506 : }
517 :
518 : /* Add (VAL_WITH_UNIT * UNITLESS_VAL) to this in-construction sum.
519 :
520 : Try to use concrete values as coefficients, and purely symbolic terms
521 : as "terms". */
522 :
523 : template<typename ConcreteValueType>
524 : void
525 11506 : sum<ConcreteValueType>::folding_helper::
526 : add_to_coefficient_for_addend (const scalar<ConcreteValueType> *val_with_unit,
527 : const scalar<integer> *unitless_val)
528 : {
529 11506 : if (val_with_unit->dyn_cast_concrete_scalar ())
530 : {
531 1159 : gcc_assert (!unitless_val->dyn_cast_concrete_scalar ());
532 :
533 1159 : auto *term = unitless_val;
534 1159 : auto *coefficient_change = val_with_unit;
535 1159 : add_coefficient_to_term (m_map_unitless_term_to_coefficient_with_unit,
536 : term,
537 : coefficient_change);
538 : }
539 : else
540 : {
541 10347 : auto *term = val_with_unit;
542 10347 : auto *coefficient_change = unitless_val;
543 10347 : add_coefficient_to_term (m_map_term_with_unit_to_unitless_coefficient,
544 : term,
545 : coefficient_change);
546 : }
547 11506 : }
548 :
549 : template<typename ConcreteValueType>
550 : DEBUG_FUNCTION void
551 0 : sum<ConcreteValueType>::folding_helper::dump () const
552 : {
553 0 : symbolic::dump_node_tree_to_stderr<sum<ConcreteValueType>::folding_helper> (*this);
554 0 : }
555 :
556 : template<typename ConcreteValueType>
557 : std::unique_ptr<text_art::tree_widget>
558 0 : sum<ConcreteValueType>::folding_helper::
559 : make_dump_widget (symbolic::node_dump_state &nds) const
560 : {
561 : using text_art::tree_widget;
562 0 : std::unique_ptr<tree_widget> fh_widget
563 : (tree_widget::from_fmt (nds, nullptr, "folding_helper"));
564 :
565 : {
566 0 : std::unique_ptr<tree_widget> map_widget
567 : (tree_widget::from_fmt (nds, nullptr, "terms with units"));
568 0 : for (auto iter : m_map_term_with_unit_to_unitless_coefficient)
569 : {
570 0 : auto &addend = iter.first;
571 0 : auto &factor = iter.second;
572 0 : std::unique_ptr<tree_widget> iter_widget
573 : (tree_widget::from_fmt (nds, nullptr, "symbolic addend"));
574 0 : iter_widget->add_child (addend->make_dump_widget (nds));
575 0 : iter_widget->add_child (factor->make_dump_widget (nds));
576 0 : map_widget->add_child (std::move (iter_widget));
577 : }
578 0 : fh_widget->add_child (std::move (map_widget));
579 0 : }
580 : {
581 0 : std::unique_ptr<tree_widget> map_widget
582 : (tree_widget::from_fmt (nds, nullptr, "unitless terms"));
583 0 : for (auto iter : m_map_unitless_term_to_coefficient_with_unit)
584 : {
585 0 : auto &addend = iter.first;
586 0 : auto &factor = iter.second;
587 0 : std::unique_ptr<tree_widget> iter_widget
588 : (tree_widget::from_fmt (nds, nullptr, "symbolic addend"));
589 0 : iter_widget->add_child (addend->make_dump_widget (nds));
590 0 : iter_widget->add_child (factor->make_dump_widget (nds));
591 0 : map_widget->add_child (std::move (iter_widget));
592 : }
593 0 : fh_widget->add_child (std::move (map_widget));
594 0 : }
595 : {
596 0 : pretty_printer the_pp;
597 0 : pretty_printer * const pp = &the_pp;
598 0 : pp_format_decoder (pp) = default_tree_printer;
599 0 : m_sum_of_concrete_values.dump_to_pp (pp);
600 0 : fh_widget->add_child (tree_widget::make (nds, pp));
601 0 : }
602 :
603 0 : return fh_widget;
604 : }
605 :
606 : template<typename ConcreteValueType>
607 : bool
608 9399 : sum<ConcreteValueType>::creation_key::term::
609 : operator< (const sum<ConcreteValueType>::creation_key::term &other) const
610 : {
611 9399 : if (int c = symbolic::node::cmp (*m_with_unit, *other.m_with_unit))
612 7400 : return c < 0;
613 1999 : return symbolic::node::cmp (*m_unitless, *other.m_unitless) < 0;
614 : }
615 :
616 : template<typename ConcreteValueType>
617 : bool
618 9274 : sum<ConcreteValueType>::creation_key::term::
619 : operator== (const sum<ConcreteValueType>::creation_key::term &other) const
620 : {
621 9274 : return (m_with_unit == other.m_with_unit
622 9274 : && m_unitless == other.m_unitless);
623 : }
624 :
625 : template<typename ConcreteValueType>
626 : complexity
627 3047 : sum<ConcreteValueType>::creation_key::term::get_complexity () const
628 : {
629 3047 : gcc_assert (!m_unitless->is_zero_p ());
630 3047 : gcc_assert (!m_with_unit->is_zero_p ());
631 :
632 3047 : if (m_unitless->is_one_p ())
633 1956 : return m_with_unit->get_complexity ();
634 1091 : else if (m_with_unit->is_one_p ())
635 0 : return m_unitless->get_complexity ();
636 : else
637 1091 : return complexity::from_pair (m_with_unit->get_complexity (),
638 1091 : m_unitless->get_complexity ());
639 : }
640 :
641 : template<typename ConcreteValueType>
642 : std::unique_ptr<text_art::tree_widget>
643 0 : sum<ConcreteValueType>::creation_key::term::
644 : make_dump_widget (symbolic::node_dump_state &nds) const
645 : {
646 : using text_art::tree_widget;
647 0 : std::unique_ptr<tree_widget> term_widget
648 : (tree_widget::from_fmt (nds, nullptr, "term"));
649 0 : term_widget->add_child (m_with_unit->make_dump_widget (nds));
650 0 : term_widget->add_child (m_unitless->make_dump_widget (nds));
651 0 : return term_widget;
652 : }
653 :
654 : template<typename ConcreteValueType>
655 : complexity
656 2636 : sum<ConcreteValueType>::creation_key::get_complexity () const
657 : {
658 : /* If we just have a constant we should have been folded away already. */
659 2636 : gcc_assert (!m_symbolic_terms.empty ());
660 :
661 2636 : unsigned num_nodes = 0;
662 2636 : unsigned max_depth = 0;
663 5683 : for (auto term : m_symbolic_terms)
664 : {
665 3047 : const complexity iter_c = term.get_complexity ();
666 3047 : num_nodes += iter_c.m_num_nodes;
667 3047 : max_depth = std::max (max_depth, iter_c.m_max_depth);
668 : }
669 2636 : if (!m_concrete_term.is_zero_p ())
670 : {
671 2357 : num_nodes += 1;
672 2357 : max_depth = std::max (max_depth, (unsigned)1);
673 : }
674 2636 : return complexity (num_nodes + 1, max_depth + 1);
675 : }
676 :
677 : template<typename ConcreteValueType>
678 28118 : sum<ConcreteValueType>::creation_key::
679 : creation_key (sum<ConcreteValueType>::folding_helper &&fh)
680 28118 : : m_concrete_term (std::move (fh.m_sum_of_concrete_values))
681 : {
682 38186 : for (auto iter : fh.m_map_term_with_unit_to_unitless_coefficient)
683 : {
684 10068 : gcc_assert (!iter.first->is_zero_p ());
685 10068 : if (!iter.second->is_zero_p ())
686 9978 : m_symbolic_terms.push_back ({iter.first, iter.second});
687 : }
688 29190 : for (auto iter : fh.m_map_unitless_term_to_coefficient_with_unit)
689 : {
690 1072 : gcc_assert (!iter.first->is_zero_p ());
691 1072 : if (!iter.second->is_zero_p ())
692 1022 : m_symbolic_terms.push_back ({iter.second, iter.first});
693 : }
694 :
695 : /* Make the ordering of the terms deterministic based on var node id. */
696 28118 : std::sort (m_symbolic_terms.begin (), m_symbolic_terms.end ());
697 28118 : }
698 :
699 : template<typename ConcreteValueType>
700 : bool
701 16715 : sum<ConcreteValueType>::creation_key::
702 : operator< (const sum<ConcreteValueType>::creation_key &other) const
703 : {
704 16715 : if (int c = ConcreteValueType::cmp (m_concrete_term,
705 16059 : other.m_concrete_term))
706 7257 : return c < 0;
707 :
708 9458 : if (m_symbolic_terms.size ()
709 9458 : != other.m_symbolic_terms.size ())
710 550 : return (m_symbolic_terms.size () < other.m_symbolic_terms.size ());
711 :
712 9902 : for (size_t i = 0; i < m_symbolic_terms.size (); ++i)
713 10268 : if (!(m_symbolic_terms[i] == other.m_symbolic_terms[i]))
714 8280 : return m_symbolic_terms[i] < other.m_symbolic_terms[i];
715 :
716 : return false;
717 : }
718 :
719 : template<typename ConcreteValueType>
720 : const scalar<ConcreteValueType> *
721 28118 : sum<ConcreteValueType>::creation_key::
722 : maybe_fold (scalar_manager<ConcreteValueType> &mgr) const
723 : {
724 28118 : if (m_symbolic_terms.empty ())
725 : {
726 : // We have a purely concrete value:
727 17841 : return &mgr.get_concrete (m_concrete_term);
728 : }
729 :
730 10277 : if (m_symbolic_terms.size () == 1
731 10277 : && m_concrete_term.is_zero_p ())
732 : {
733 : /* ((X * F) + 0) --> (X * F). */
734 4442 : auto &term = m_symbolic_terms[0];
735 4442 : return &mgr.get_product (*term.m_with_unit, *term.m_unitless);
736 : }
737 :
738 : /* If any part of any of the symbolic terms is unknown, the
739 : whole sum is unknown. */
740 12018 : for (auto iter : m_symbolic_terms)
741 : {
742 6544 : if (iter.m_with_unit->is_unknown_p ())
743 361 : return &mgr.get_unknown ();
744 6183 : if (iter.m_unitless->is_unknown_p ())
745 0 : return &mgr.get_unknown ();
746 : }
747 :
748 2678 : if (auto *folded = maybe_fold_for_cvt (mgr))
749 : return folded;
750 :
751 : return nullptr;
752 : }
753 :
754 : template<typename ConcreteValueType>
755 : const scalar<ConcreteValueType> *
756 : sum<ConcreteValueType>::creation_key::
757 : maybe_fold_for_cvt (scalar_manager<ConcreteValueType> &) const
758 : {
759 : return nullptr;
760 : }
761 :
762 : /* If all the symbolic terms are bits_from_bytes_scalar
763 : and any concrete term is a multiple of 8, then we can move the
764 : bits_from_bytes outside the sum. This is a simplification if the
765 : number of terms (symbolic or concrete) > 1, which should be the case
766 : for a creation_key that has survived this far. */
767 :
768 : template<>
769 : const symbolic_bit_size *
770 2678 : sum<concrete_bit_size>::creation_key::
771 : maybe_fold_for_cvt (scalar_manager<concrete_bit_size> &mgr) const
772 : {
773 2678 : concrete_byte_size conc_bytes;
774 2678 : if (!maybe_bytes_from_bits (m_concrete_term, &conc_bytes))
775 : return nullptr;
776 :
777 2608 : auto &byte_mgr = mgr.get_node_manager ().get_scalars ().get_bytes ();
778 2608 : std::vector<const symbolic_byte_size *> addends_as_bytes;
779 2608 : addends_as_bytes.push_back (&symbolic_from_concrete (conc_bytes, byte_mgr));
780 :
781 5284 : for (auto sym_term : m_symbolic_terms)
782 : {
783 2760 : auto *bits_from_bytes
784 2760 : = sym_term.m_with_unit->dyn_cast_bits_from_bytes_scalar ();
785 2760 : if (!bits_from_bytes)
786 2608 : return nullptr;
787 2676 : auto &addend_as_bytes
788 2676 : = bits_from_bytes->get_bytes () * (*sym_term.m_unitless);
789 2676 : addends_as_bytes.push_back (&addend_as_bytes);
790 : }
791 :
792 2524 : auto &byte_sum = byte_mgr.get_sum (addends_as_bytes);
793 2524 : return &mgr.get_bits_from_bytes (byte_sum);
794 2608 : }
795 :
796 : template<typename ConcreteValueType>
797 : DEBUG_FUNCTION void
798 0 : sum<ConcreteValueType>::creation_key::dump () const
799 : {
800 0 : symbolic::dump_node_tree_to_stderr<sum<ConcreteValueType>::creation_key> (*this);
801 0 : }
802 :
803 : template<typename ConcreteValueType>
804 : std::unique_ptr<text_art::tree_widget>
805 0 : sum<ConcreteValueType>::creation_key::
806 : make_dump_widget (symbolic::node_dump_state &nds) const
807 : {
808 : using text_art::tree_widget;
809 0 : std::unique_ptr<tree_widget> ck_widget
810 : (tree_widget::from_fmt (nds, nullptr, "creation_key"));
811 :
812 0 : for (auto sym_term : m_symbolic_terms)
813 0 : ck_widget->add_child (sym_term.make_dump_widget (nds));
814 : {
815 0 : pretty_printer the_pp;
816 0 : pretty_printer * const pp = &the_pp;
817 0 : pp_format_decoder (pp) = default_tree_printer;
818 0 : m_concrete_term.dump_to_pp (pp);
819 0 : ck_widget->add_child (tree_widget::make (nds, pp));
820 0 : }
821 :
822 0 : return ck_widget;
823 : }
824 :
825 : template<typename ConcreteValueType>
826 2636 : sum<ConcreteValueType>::sum (unsigned id,
827 : scalar_manager<ConcreteValueType> &mgr,
828 : const creation_key &ck)
829 : : scalar<ConcreteValueType> (ck.get_complexity (), id, mgr,
830 : scalar<ConcreteValueType>::kind::sum),
831 2636 : m_concrete_addend (nullptr)
832 : {
833 5683 : for (auto term : ck.m_symbolic_terms)
834 : {
835 3047 : gcc_assert (!term.m_with_unit->is_zero_p ());
836 3047 : gcc_assert (!term.m_unitless->is_zero_p ());
837 3047 : auto &symbolic_addend = (*term.m_with_unit) * (*term.m_unitless);
838 3047 : gcc_assert (!symbolic_addend.dyn_cast_concrete_scalar ());
839 3047 : gcc_assert (!symbolic_addend.dyn_cast_sum ());
840 3047 : m_symbolic_addends.push_back (&symbolic_addend);
841 : }
842 :
843 2636 : if (ck.m_concrete_term.is_zero_p ())
844 : {
845 279 : gcc_assert (m_symbolic_addends.size () >= 2);
846 : }
847 : else
848 : {
849 2357 : gcc_assert (m_symbolic_addends.size () >= 1);
850 2357 : m_concrete_addend = &mgr.get_concrete (ck.m_concrete_term);
851 : }
852 2636 : }
853 :
854 : template<typename ConcreteValueType>
855 : void
856 82 : sum<ConcreteValueType>::
857 : print_dump_widget_label_for_scalar (pretty_printer *pp) const
858 : {
859 82 : pp_printf (pp, "sum<%s>", ConcreteValueType::dump_type_name);
860 82 : }
861 :
862 : template<typename ConcreteValueType>
863 : void
864 82 : sum<ConcreteValueType>::
865 : add_dump_widget_children (text_art::tree_widget &w,
866 : node_dump_state &nds) const
867 : {
868 200 : for (auto iter : m_symbolic_addends)
869 236 : w.add_child (iter->make_dump_widget (nds));
870 82 : if (m_concrete_addend)
871 124 : w.add_child (m_concrete_addend->make_dump_widget (nds));
872 82 : }
873 :
874 : template<>
875 : void
876 0 : sum<integer>::accept_node_visitor (symbolic::node_visitor &v) const
877 : {
878 0 : if (v.visit_scalar_unitless (*this))
879 : {
880 0 : for (auto iter : m_symbolic_addends)
881 0 : iter->accept_node_visitor (v);
882 0 : if (m_concrete_addend)
883 0 : m_concrete_addend->accept_node_visitor (v);
884 : }
885 0 : }
886 :
887 : template<>
888 : void
889 0 : sum<integer_with_unit<units::bit>>::
890 : accept_node_visitor (symbolic::node_visitor &v) const
891 : {
892 0 : if (v.visit_scalar_bit (*this))
893 : {
894 0 : for (auto iter : m_symbolic_addends)
895 0 : iter->accept_node_visitor (v);
896 0 : if (m_concrete_addend)
897 0 : m_concrete_addend->accept_node_visitor (v);
898 : }
899 0 : }
900 :
901 : template<>
902 : void
903 46052 : sum<integer_with_unit<units::byte>>::
904 : accept_node_visitor (symbolic::node_visitor &v) const
905 : {
906 46052 : if (v.visit_scalar_byte (*this))
907 : {
908 98777 : for (auto iter : m_symbolic_addends)
909 52725 : iter->accept_node_visitor (v);
910 46052 : if (m_concrete_addend)
911 42051 : m_concrete_addend->accept_node_visitor (v);
912 : }
913 46052 : }
914 :
915 : template<typename ConcreteValueType>
916 : std::unique_ptr<json::object>
917 4 : sum<ConcreteValueType>::to_json () const
918 : {
919 4 : auto obj = scalar<ConcreteValueType>::make_json_obj ("sum");
920 4 : auto arr = std::make_unique<json::array> ();
921 16 : for (auto iter : m_symbolic_addends)
922 12 : arr->append (iter->to_json ());
923 4 : obj->set ("symbolic_addends", std::move (arr));
924 4 : if (m_concrete_addend)
925 0 : obj->set ("concrete_addend", m_concrete_addend->to_json ());
926 4 : return obj;
927 4 : }
928 :
929 : template<typename ConcreteValueType>
930 : void
931 20 : sum<ConcreteValueType>::
932 : dump_inline_to_pp (pretty_printer *pp, enum units::role role) const
933 : {
934 20 : bool first = true;
935 68 : for (auto iter : m_symbolic_addends)
936 : {
937 48 : if (first)
938 : first = false;
939 : else
940 28 : pp_string (pp, " + ");
941 48 : iter->dump_inline_to_pp (pp, role);
942 : }
943 20 : if (m_concrete_addend)
944 : {
945 8 : if (first)
946 8 : first = false;
947 : else
948 8 : pp_string (pp, " + ");
949 8 : m_concrete_addend->dump_inline_to_pp (pp, role);
950 : }
951 20 : }
952 :
953 : template<typename ConcreteValueType>
954 : std::unique_ptr<diagnostics::markup::node>
955 106 : sum<ConcreteValueType>::make_markup_node (markup_context &markup_ctxt) const
956 : {
957 106 : std::vector<std::unique_ptr<diagnostics::markup::node>> children;
958 306 : for (auto iter : m_symbolic_addends)
959 200 : children.push_back (iter->make_markup_node (markup_ctxt));
960 106 : if (m_concrete_addend)
961 32 : children.push_back (m_concrete_addend->make_markup_node (markup_ctxt));
962 :
963 106 : gcc_assert (children.size () >= 2);
964 :
965 106 : if (markup_ctxt.m_user_facing)
966 106 : if (children.size () == 2)
967 : {
968 : /* Lower "(-A) + B" to "B - A". */
969 86 : if (auto *a_as_negation = children[0]->dyn_cast_math_negation ())
970 : return std::make_unique<diagnostics::markup::math::subtraction>
971 0 : (std::move (children[1]), // "B"
972 0 : a_as_negation->take_operand ()); // "A"
973 :
974 : /* Lower "A + (-B)" to "A - B". */
975 86 : if (auto *b_as_negation = children[1]->dyn_cast_math_negation ())
976 : return std::make_unique<diagnostics::markup::math::subtraction>
977 36 : (std::move (children[0]), // "A"
978 36 : b_as_negation->take_operand ()); // "B"
979 : }
980 :
981 : return std::make_unique<diagnostics::markup::math::sum>
982 70 : (std::move (children));
983 106 : }
984 :
985 : // template<typename ConcreteValueType> class product : public scalar<ConcreteValueType>
986 :
987 : template<typename ConcreteValueType>
988 : bool
989 15068 : product<ConcreteValueType>::key::operator< (const key &other) const
990 : {
991 15068 : if (int c = symbolic::node::cmp (*m_lhs, *other.m_lhs))
992 3811 : return c < 0;
993 11257 : return symbolic::node::cmp (*m_rhs, *other.m_rhs) < 0;
994 : }
995 :
996 : template<typename ConcreteValueType>
997 : complexity
998 1161 : product<ConcreteValueType>::key::get_complexity () const
999 : {
1000 1161 : return complexity::from_pair (m_lhs->get_complexity (),
1001 1161 : m_rhs->get_complexity ());
1002 : }
1003 :
1004 : template<typename ConcreteValueType>
1005 : void
1006 : product<ConcreteValueType>::key::canonicalize ()
1007 : {
1008 : // No-op in general...
1009 : }
1010 :
1011 : template<>
1012 : void
1013 566 : product<integer>::key::canonicalize ()
1014 : {
1015 : /* For integer * integer, make sure any
1016 : concrete value is on the right. */
1017 566 : if (m_lhs->dyn_cast_concrete_scalar ())
1018 40 : std::swap (m_lhs, m_rhs);
1019 566 : }
1020 :
1021 : template<typename ConcreteValueType>
1022 1161 : product<ConcreteValueType>::product (unsigned id,
1023 : scalar_manager<ConcreteValueType> &mgr,
1024 : const key &k)
1025 : : scalar<ConcreteValueType> (k.get_complexity (), id, mgr,
1026 : scalar<ConcreteValueType>::kind::product),
1027 1161 : m_lhs (*k.m_lhs),
1028 1161 : m_rhs (*k.m_rhs)
1029 : {
1030 : if (CHECKING_P)
1031 : {
1032 : /* Multiplication by 0 or 1 should have been folded away by now. */
1033 1161 : gcc_assert (!m_lhs.is_zero_p ());
1034 1161 : gcc_assert (!m_rhs.is_zero_p ());
1035 1161 : gcc_assert (!m_lhs.is_one_p ());
1036 1161 : gcc_assert (!m_rhs.is_one_p ());
1037 :
1038 : /* Concrete * concrete should have been folded by now. */
1039 1161 : gcc_assert (!(m_lhs.dyn_cast_concrete_scalar ()
1040 : && m_rhs.dyn_cast_concrete_scalar ()));
1041 : }
1042 1161 : }
1043 :
1044 : template<typename ConcreteValueType>
1045 : void
1046 24 : product<ConcreteValueType>::
1047 : print_dump_widget_label_for_scalar (pretty_printer *pp) const
1048 : {
1049 24 : pp_printf (pp, "product<%s>", ConcreteValueType::dump_type_name);
1050 24 : }
1051 :
1052 : template<typename ConcreteValueType>
1053 : void
1054 24 : product<ConcreteValueType>::
1055 : add_dump_widget_children (text_art::tree_widget &w,
1056 : node_dump_state &nds) const
1057 : {
1058 48 : w.add_child (m_lhs.make_dump_widget (nds));
1059 48 : w.add_child (m_rhs.make_dump_widget (nds));
1060 24 : }
1061 :
1062 : template<>
1063 : void
1064 0 : product<integer>::accept_node_visitor (symbolic::node_visitor &v) const
1065 : {
1066 0 : if (v.visit_scalar_unitless (*this))
1067 : {
1068 0 : m_lhs.accept_node_visitor (v);
1069 0 : m_rhs.accept_node_visitor (v);
1070 : }
1071 0 : }
1072 :
1073 : template<>
1074 : void
1075 0 : product<integer_with_unit<units::bit>>::
1076 : accept_node_visitor (symbolic::node_visitor &v) const
1077 : {
1078 0 : if (v.visit_scalar_bit (*this))
1079 : {
1080 0 : m_lhs.accept_node_visitor (v);
1081 0 : m_rhs.accept_node_visitor (v);
1082 : }
1083 0 : }
1084 :
1085 : template<>
1086 : void
1087 38530 : product<integer_with_unit<units::byte>>::
1088 : accept_node_visitor (symbolic::node_visitor &v) const
1089 : {
1090 38530 : if (v.visit_scalar_byte (*this))
1091 : {
1092 38530 : m_lhs.accept_node_visitor (v);
1093 38530 : m_rhs.accept_node_visitor (v);
1094 : }
1095 38530 : }
1096 :
1097 : template<typename ConcreteValueType>
1098 : std::unique_ptr<json::object>
1099 16 : product<ConcreteValueType>::to_json () const
1100 : {
1101 16 : auto obj = scalar<ConcreteValueType>::make_json_obj ("product");
1102 16 : obj->set ("lhs", m_lhs.to_json ());
1103 16 : obj->set ("rhs", m_rhs.to_json ());
1104 16 : return obj;
1105 : }
1106 :
1107 : template<typename ConcreteValueType>
1108 : void
1109 16 : product<ConcreteValueType>::
1110 : dump_inline_to_pp (pretty_printer *pp, enum units::role role) const
1111 : {
1112 16 : m_lhs.dump_inline_to_pp (pp, role);
1113 16 : pp_string (pp, " * ");
1114 16 : m_rhs.dump_inline_to_pp (pp, role);
1115 16 : }
1116 :
1117 : template<typename ConcreteValueType>
1118 : std::unique_ptr<diagnostics::markup::node>
1119 94 : product<ConcreteValueType>::make_markup_node (markup_context &markup_ctxt) const
1120 : {
1121 : /* "A * -1" -> "-A". */
1122 94 : if (markup_ctxt.m_user_facing)
1123 94 : if (auto *conc = m_rhs.dyn_cast_concrete_scalar ())
1124 60 : if (conc->get_concrete ().get_integer () == -1)
1125 : return std::make_unique<diagnostics::markup::math::negation>
1126 60 : (m_lhs.make_markup_node (markup_ctxt));
1127 :
1128 34 : auto markup
1129 : = std::make_unique<diagnostics::markup::math::product> ();
1130 : /* Put any concrete value on the RHS. */
1131 34 : if (m_lhs.dyn_cast_concrete_scalar ())
1132 : {
1133 18 : markup->add_child (m_rhs.make_markup_node (markup_ctxt));
1134 18 : markup->add_child (m_lhs.make_markup_node (markup_ctxt));
1135 : }
1136 : else
1137 : {
1138 16 : markup->add_child (m_lhs.make_markup_node (markup_ctxt));
1139 16 : markup->add_child (m_rhs.make_markup_node (markup_ctxt));
1140 : }
1141 34 : return markup;
1142 34 : }
1143 :
1144 : // class scalar_from_svalue : public scalar<ConcreteValueType>
1145 :
1146 : template<typename ConcreteValueType>
1147 : bool
1148 241235 : scalar_from_svalue<ConcreteValueType>::key::operator< (const key &other) const
1149 : {
1150 241235 : if (int c = symbolic::node::cmp (*m_sval, *other.m_sval))
1151 21077 : return c < 0;
1152 : return false;
1153 : }
1154 :
1155 : template<typename ConcreteValueType>
1156 : complexity
1157 8062 : scalar_from_svalue<ConcreteValueType>::key::get_complexity () const
1158 : {
1159 : // For now, return the complexity of m_sval directly
1160 8062 : return m_sval->get_complexity ();
1161 : }
1162 :
1163 : template<typename ConcreteValueType>
1164 8062 : scalar_from_svalue<ConcreteValueType>::
1165 : scalar_from_svalue (unsigned id,
1166 : scalar_manager<ConcreteValueType> &mgr,
1167 : const key &k)
1168 : : scalar<ConcreteValueType> (k.get_complexity (), id, mgr,
1169 : scalar<ConcreteValueType>::kind::from_svalue),
1170 8062 : m_sval (*k.m_sval)
1171 : {
1172 : if (CHECKING_P)
1173 : {
1174 8062 : if (auto cst = m_sval.maybe_get_constant ())
1175 0 : gcc_assert (TREE_CODE (cst) != INTEGER_CST);
1176 : }
1177 8062 : }
1178 :
1179 : template<typename ConcreteValueType>
1180 : void
1181 1003 : scalar_from_svalue<ConcreteValueType>::
1182 : print_dump_widget_label_for_scalar (pretty_printer *pp) const
1183 : {
1184 1003 : pp_printf (pp, "scalar_from_svalue<%s>", ConcreteValueType::dump_type_name);
1185 1003 : }
1186 :
1187 : template<typename ConcreteValueType>
1188 : void
1189 865 : scalar_from_svalue<ConcreteValueType>::
1190 : add_dump_widget_children (text_art::tree_widget &w,
1191 : node_dump_state &nds) const
1192 : {
1193 1730 : w.add_child (m_sval.make_dump_widget (nds));
1194 865 : }
1195 :
1196 : template<>
1197 : void
1198 38530 : scalar_from_svalue<integer>::
1199 : accept_node_visitor (symbolic::node_visitor &v) const
1200 : {
1201 38530 : if (v.visit_scalar_unitless (*this))
1202 38530 : m_sval.accept_node_visitor (v);
1203 38530 : }
1204 :
1205 : template<>
1206 : void
1207 3666 : scalar_from_svalue<integer_with_unit<units::bit>>::
1208 : accept_node_visitor (symbolic::node_visitor &v) const
1209 : {
1210 3666 : if (v.visit_scalar_bit (*this))
1211 3666 : m_sval.accept_node_visitor (v);
1212 3666 : }
1213 :
1214 : template<>
1215 : void
1216 1802585 : scalar_from_svalue<integer_with_unit<units::byte>>::
1217 : accept_node_visitor (symbolic::node_visitor &v) const
1218 : {
1219 1802585 : if (v.visit_scalar_byte (*this))
1220 1802585 : m_sval.accept_node_visitor (v);
1221 1802585 : }
1222 :
1223 : template<typename ConcreteValueType>
1224 : std::unique_ptr<json::object>
1225 0 : scalar_from_svalue<ConcreteValueType>::to_json () const
1226 : {
1227 0 : auto obj = scalar<ConcreteValueType>::make_json_obj ("scalar_from_svalue");
1228 0 : obj->set ("svalue", m_sval.to_json ());
1229 0 : return obj;
1230 : }
1231 :
1232 : template<typename ConcreteValueType>
1233 : void
1234 0 : scalar_from_svalue<ConcreteValueType>::
1235 : dump_inline_to_pp (pretty_printer *pp, enum units::role) const
1236 : {
1237 0 : m_sval.dump_to_pp (pp, true);
1238 0 : }
1239 :
1240 : template<typename ConcreteValueType>
1241 : std::unique_ptr<diagnostics::markup::node>
1242 39 : scalar_from_svalue<ConcreteValueType>::
1243 : make_markup_node (markup_context &markup_ctxt) const
1244 : {
1245 39 : return m_sval.make_markup_node (markup_ctxt);
1246 : }
1247 :
1248 : #if CHECKING_P
1249 :
1250 : // template<typename ConcreteValueType> class named_test_scalar : public scalar<ConcreteValueType>
1251 :
1252 : template<typename ConcreteValueType>
1253 : void
1254 100 : named_test_scalar<ConcreteValueType>::
1255 : print_dump_widget_label_for_scalar (pretty_printer *pp) const
1256 : {
1257 100 : pp_printf (pp, "named_test_scalar<%s>: %qs",
1258 : ConcreteValueType::dump_type_name, m_name.c_str ());
1259 100 : }
1260 :
1261 : template<typename ConcreteValueType>
1262 : void
1263 100 : named_test_scalar<ConcreteValueType>::
1264 : add_dump_widget_children (text_art::tree_widget &,
1265 : node_dump_state &) const
1266 : {
1267 : // no-op
1268 100 : }
1269 :
1270 : template<>
1271 : void
1272 0 : named_test_scalar<integer>::accept_node_visitor (symbolic::node_visitor &v) const
1273 : {
1274 0 : v.visit_scalar_unitless (*this);
1275 0 : }
1276 :
1277 : template<>
1278 : void
1279 0 : named_test_scalar<integer_with_unit<units::bit>>::
1280 : accept_node_visitor (symbolic::node_visitor &v) const
1281 : {
1282 0 : v.visit_scalar_bit (*this);
1283 0 : }
1284 :
1285 : template<>
1286 : void
1287 0 : named_test_scalar<integer_with_unit<units::byte>>::
1288 : accept_node_visitor (symbolic::node_visitor &v) const
1289 : {
1290 0 : v.visit_scalar_byte (*this);
1291 0 : }
1292 :
1293 : template<typename ConcreteValueType>
1294 : std::unique_ptr<json::object>
1295 32 : named_test_scalar<ConcreteValueType>::to_json () const
1296 : {
1297 32 : auto obj = scalar<ConcreteValueType>::make_json_obj ("named_test_scalar");
1298 64 : obj->set_string ("name", m_name);
1299 32 : return obj;
1300 : }
1301 :
1302 : template<>
1303 : void
1304 28 : named_test_scalar<integer_with_unit<units::bit>>::
1305 : dump_inline_to_pp (pretty_printer *pp, enum units::role role) const
1306 : {
1307 28 : switch (role)
1308 : {
1309 0 : default:
1310 0 : gcc_unreachable ();
1311 16 : case units::role::generic:
1312 16 : case units::role::size:
1313 16 : pp_printf (pp, "%s bits", m_name.c_str ());
1314 16 : break;
1315 12 : case units::role::offset:
1316 12 : pp_printf (pp, "bit %s", m_name.c_str ());
1317 12 : break;
1318 : }
1319 28 : }
1320 :
1321 : template<>
1322 : void
1323 24 : named_test_scalar<integer_with_unit<units::byte>>::
1324 : dump_inline_to_pp (pretty_printer *pp, enum units::role role) const
1325 : {
1326 24 : switch (role)
1327 : {
1328 0 : default:
1329 0 : gcc_unreachable ();
1330 16 : case units::role::generic:
1331 16 : case units::role::size:
1332 16 : pp_printf (pp, "%s bytes", m_name.c_str ());
1333 16 : break;
1334 8 : case units::role::offset:
1335 8 : pp_printf (pp, "byte %s", m_name.c_str ());
1336 8 : break;
1337 : }
1338 24 : }
1339 :
1340 : template<>
1341 : void
1342 16 : named_test_scalar<integer>::
1343 : dump_inline_to_pp (pretty_printer *pp, enum units::role) const
1344 : {
1345 16 : pp_string (pp, m_name.c_str ());
1346 16 : }
1347 :
1348 : template<typename ConcreteValueType>
1349 : std::unique_ptr<diagnostics::markup::node>
1350 232 : named_test_scalar<ConcreteValueType>::make_markup_node (markup_context &) const
1351 : {
1352 464 : return diagnostics::markup::make_text_node (m_name);
1353 : }
1354 :
1355 : #endif /* #if CHECKING_P */
1356 :
1357 : // class bits_from_bytes_scalar : public symbolic_bit_size
1358 :
1359 : bool
1360 80261 : bits_from_bytes_scalar::key::operator< (const key &other) const
1361 : {
1362 80261 : return symbolic::node::cmp (*m_bytes, *other.m_bytes) < 0;
1363 : }
1364 :
1365 : complexity
1366 5133 : bits_from_bytes_scalar::key::get_complexity () const
1367 : {
1368 5133 : return complexity (*m_bytes);
1369 : }
1370 :
1371 5133 : bits_from_bytes_scalar::
1372 : bits_from_bytes_scalar (unsigned id,
1373 : scalar_manager<concrete_bit_size> &mgr,
1374 : const key &k)
1375 : : symbolic_bit_size (k.get_complexity (), id, mgr,
1376 : symbolic_bit_size::kind::bits_from_bytes),
1377 5133 : m_bytes (*k.m_bytes)
1378 : {
1379 5133 : if (CHECKING_P)
1380 : {
1381 5133 : gcc_assert (!m_bytes.dyn_cast_concrete_scalar ());
1382 5133 : gcc_assert (!m_bytes.is_unknown_p ());
1383 : }
1384 5133 : }
1385 :
1386 : void
1387 253 : bits_from_bytes_scalar::print_dump_widget_label_for_scalar (pretty_printer *pp) const
1388 : {
1389 253 : pp_string (pp, "bits_from_bytes_scalar");
1390 253 : }
1391 :
1392 : void
1393 253 : bits_from_bytes_scalar::add_dump_widget_children (text_art::tree_widget &w,
1394 : node_dump_state &nds) const
1395 : {
1396 506 : w.add_child (m_bytes.make_dump_widget (nds));
1397 253 : }
1398 :
1399 : void
1400 1523473 : bits_from_bytes_scalar::accept_node_visitor (symbolic::node_visitor &v) const
1401 : {
1402 1523473 : if (v.visit_scalar_bit (*this))
1403 1523473 : m_bytes.accept_node_visitor (v);
1404 1523473 : }
1405 :
1406 : std::unique_ptr<json::object>
1407 4 : bits_from_bytes_scalar::to_json () const
1408 : {
1409 4 : auto obj = scalar<integer_with_unit<units::bit>>::make_json_obj
1410 4 : ("bits_from_bytes_scalar");
1411 4 : obj->set ("bytes", m_bytes.to_json ());
1412 4 : return obj;
1413 : }
1414 :
1415 : void
1416 4 : bits_from_bytes_scalar::
1417 : dump_inline_to_pp (pretty_printer *pp, enum units::role role) const
1418 : {
1419 4 : pp_string (pp, "bits_from_bytes_scalar(");
1420 4 : m_bytes.dump_inline_to_pp (pp, role);
1421 4 : pp_string (pp, ")");
1422 4 : }
1423 :
1424 : std::unique_ptr<diagnostics::markup::node>
1425 0 : bits_from_bytes_scalar::make_markup_node (markup_context &) const
1426 : {
1427 0 : return diagnostics::markup::make_text_node ("bits_from_bytes_scalar");
1428 : }
1429 :
1430 : // template<typename ConcreteValueType> class scalar_manager;
1431 :
1432 : template<typename ConcreteValueType>
1433 : const concrete_scalar<ConcreteValueType> &
1434 15740982 : scalar_manager<ConcreteValueType>::get_concrete (const ConcreteValueType &value)
1435 : {
1436 15740982 : auto iter = m_concrete_map.find (value);
1437 15740982 : if (iter != m_concrete_map.end ())
1438 15649792 : return *(iter->second);
1439 :
1440 91190 : auto s = std::make_unique<concrete_scalar<ConcreteValueType>>
1441 91190 : (alloc_node_id (),
1442 : *this,
1443 : value);
1444 91190 : auto &result = *s.get ();
1445 91190 : m_concrete_map.insert ({value, std::move (s)});
1446 : return result;
1447 91190 : }
1448 :
1449 : /* Helper for implementing (concrete unit) * scalar.
1450 : See if we can unpack scalar to move terms it to the
1451 : per-unit scalar. */
1452 :
1453 : template<typename ConcreteValueType>
1454 : const scalar<ConcreteValueType> *
1455 26709 : scalar_manager<ConcreteValueType>::
1456 : maybe_from_unitless (const ConcreteValueType &concrete_lhs,
1457 : const scalar<integer> &unitless_rhs)
1458 : {
1459 26709 : if (concrete_lhs.is_one_p ())
1460 : {
1461 : // (1 unit) * CST --> (CST units)
1462 7046 : if (auto s = unitless_rhs.dyn_cast_concrete_scalar ())
1463 5276 : return &get_concrete (ConcreteValueType (s->get_concrete ()));
1464 :
1465 : /* (1 unit) * (A * B) --> to_unit(A) * B
1466 : if A can be converted; otherwise try --> to_unit(B) * A). */
1467 1770 : if (auto s = unitless_rhs.dyn_cast_product ())
1468 : {
1469 16 : if (auto *lhs_with_units
1470 16 : = maybe_from_unitless (concrete_lhs, s->get_lhs ()))
1471 0 : return &((*lhs_with_units) * s->get_rhs ());
1472 16 : if (auto *rhs_with_units
1473 16 : = maybe_from_unitless (concrete_lhs, s->get_rhs ()))
1474 16 : return &((*rhs_with_units) * s->get_lhs ());
1475 : }
1476 :
1477 : /* (1 unit) * unitless_from_sval(SVAL) --> with_unit_from_sval(SVAL). */
1478 1754 : if (auto *from_sval = unitless_rhs.dyn_cast_scalar_from_svalue ())
1479 1738 : return &get_scalar_from_svalue (from_sval->get_svalue ());
1480 : }
1481 :
1482 19679 : if (auto *bits = maybe_from_unitless_for_unit (concrete_lhs, unitless_rhs))
1483 : return bits;
1484 :
1485 : return nullptr;
1486 : }
1487 :
1488 : template<>
1489 : const symbolic_bit_offset *
1490 12332 : scalar_manager<concrete_bit_offset>::
1491 : maybe_from_unitless_for_unit (const concrete_bit_offset &concrete_lhs,
1492 : const scalar<integer> &unitless_rhs)
1493 : {
1494 12332 : auto &byte_mgr = get_node_manager ().get_scalars ().get_bytes ();
1495 :
1496 : /* ((8 * C) bits * unitless_rhs)
1497 : --> bits_from_bytes (C_bytes * unitless_rhs). */
1498 24664 : if (concrete_lhs.get_integer ().floor_mod (BITS_PER_UNIT) == 0)
1499 12236 : return &(get_bits_from_bytes
1500 12236 : (byte_mgr.get_concrete
1501 24472 : (concrete_byte_offset (concrete_lhs.get_integer ()
1502 24472 : .floor_div (integer (BITS_PER_UNIT))))
1503 12236 : * unitless_rhs));
1504 :
1505 : return nullptr;
1506 : }
1507 :
1508 : template<>
1509 : const symbolic_byte_offset *
1510 7347 : scalar_manager<concrete_byte_offset>::
1511 : maybe_from_unitless_for_unit (const concrete_byte_offset &,
1512 : const scalar<integer> &)
1513 : {
1514 : // No-op
1515 7347 : return nullptr;
1516 : }
1517 :
1518 : /* No-op specializing for "converting" plain integer to integer. */
1519 :
1520 : template<>
1521 : const scalar<integer> *
1522 163 : scalar_manager<integer>::
1523 : maybe_from_unitless (const integer &concrete_lhs,
1524 : const scalar<integer> &unitless_rhs)
1525 : {
1526 163 : if (concrete_lhs.is_one_p ())
1527 20 : return &unitless_rhs;
1528 : return nullptr;
1529 : }
1530 :
1531 : template<typename ConcreteValueType>
1532 : const scalar<ConcreteValueType> &
1533 28118 : scalar_manager<ConcreteValueType>::
1534 : get_sum_unmemoized (const typename sum<ConcreteValueType>::memoization_key &memo_key)
1535 : {
1536 : /* Gather and unwrap the addends. */
1537 : using folding_helper = typename sum<ConcreteValueType>::folding_helper;
1538 28118 : folding_helper fh;
1539 84606 : for (auto iter : memo_key.m_addends)
1540 56488 : fh.add_addend (*iter, get_unitless_manager ());
1541 :
1542 : /* Convert from map to a vector in a canonical order. */
1543 : using creation_key = typename sum<ConcreteValueType>::creation_key;
1544 28118 : creation_key ck (std::move (fh));
1545 :
1546 28118 : if (auto *folded = ck.maybe_fold (*this))
1547 : return *folded;
1548 :
1549 : /* Cache based on creation_key. */
1550 2950 : auto iter = m_sum_map.find (ck);
1551 2950 : if (iter != m_sum_map.end ())
1552 314 : return *(iter->second.get ());
1553 :
1554 2636 : auto s = std::make_unique<sum<ConcreteValueType>> (alloc_node_id (),
1555 : *this,
1556 : ck);
1557 2636 : auto &result = *s.get ();
1558 2636 : m_sum_map.insert ({std::move (ck), std::move (s)});
1559 2636 : return result;
1560 30754 : }
1561 :
1562 :
1563 : template<typename ConcreteValueType>
1564 : const scalar<ConcreteValueType> &
1565 218957 : scalar_manager<ConcreteValueType>::
1566 : get_sum (std::vector<const scalar<ConcreteValueType> *> addends)
1567 : {
1568 : typename sum<ConcreteValueType>::memoization_key
1569 218957 : memo_key {std::move (addends) };
1570 :
1571 218957 : auto iter = m_memoized_sums.find (memo_key);
1572 218957 : if (iter != m_memoized_sums.end ())
1573 190839 : return *(iter->second);
1574 :
1575 28118 : auto &s = get_sum_unmemoized (memo_key);
1576 28118 : m_memoized_sums.insert ({std::move (memo_key), &s});
1577 28118 : return s;
1578 218957 : }
1579 :
1580 : template<typename ConcreteValueType>
1581 : const scalar<ConcreteValueType> &
1582 22466 : scalar_manager<ConcreteValueType>::
1583 : get_difference (const scalar<ConcreteValueType> &lhs,
1584 : const scalar<ConcreteValueType> &rhs)
1585 : {
1586 22466 : return lhs + get_negation (rhs);
1587 : }
1588 :
1589 : template
1590 : const scalar<concrete_bit_offset> &
1591 : scalar_manager<concrete_bit_offset>::
1592 : get_difference (const scalar<concrete_bit_offset> &lhs,
1593 : const scalar<concrete_bit_offset> &rhs);
1594 :
1595 : template
1596 : const scalar<concrete_byte_offset> &
1597 : scalar_manager<concrete_byte_offset>::
1598 : get_difference (const scalar<concrete_byte_offset> &lhs,
1599 : const scalar<concrete_byte_offset> &rhs);
1600 :
1601 : template<typename ConcreteValueType>
1602 : const scalar<ConcreteValueType> &
1603 22895 : scalar_manager<ConcreteValueType>::
1604 : get_negation (const scalar<ConcreteValueType> &s)
1605 : {
1606 22895 : if (auto concrete = s.dyn_cast_concrete_scalar ())
1607 : {
1608 21599 : auto &i = concrete->get_concrete ();
1609 :
1610 : // -0 --> 0
1611 21599 : if (i.is_zero_p ())
1612 : return s;
1613 20174 : return get_concrete (-i);
1614 : }
1615 :
1616 1296 : auto &unitless_mgr = get_unitless_manager ();
1617 1296 : auto &minus_one = unitless_mgr.get_concrete (integer (-1));
1618 1296 : return get_product (s, minus_one);
1619 : }
1620 :
1621 : template<typename ConcreteValueType>
1622 : const integer &
1623 : as_integer (const integer &i) { return i; }
1624 :
1625 : template<typename Unit>
1626 : const integer &
1627 : as_integer (const integer_with_unit<Unit> &i) { return i.get_integer (); }
1628 :
1629 : template<typename ConcreteValueType>
1630 : const scalar<ConcreteValueType> *
1631 38148 : scalar_manager<ConcreteValueType>::
1632 : maybe_fold_product (const typename product<ConcreteValueType>::key &k)
1633 : {
1634 38148 : if (auto concrete_lhs = k.m_lhs->dyn_cast_concrete_scalar ())
1635 : {
1636 26864 : auto &i = concrete_lhs->get_concrete ();
1637 :
1638 : // 0 units * A --> 0 units
1639 26864 : if (i.is_zero_p ())
1640 24 : return &get_concrete (ConcreteValueType (0));
1641 :
1642 : // concrete unit * A --> A units
1643 26840 : if (auto s = maybe_from_unitless (concrete_lhs->get_concrete (),
1644 26840 : *k.m_rhs))
1645 : return s;
1646 :
1647 : // concrete units * concrete rhs --> concrete units
1648 7570 : if (auto concrete_rhs = k.m_rhs->dyn_cast_concrete_scalar ())
1649 4982 : return &get_concrete (i * concrete_rhs->get_concrete ());
1650 :
1651 2691 : if (auto rhs_prod = k.m_rhs->dyn_cast_product ())
1652 : {
1653 : /* (C1 units) * (F * C2) where C1 and C2 are constant
1654 : --> (C1 * C2) units * F units. */
1655 146 : if (auto conc = rhs_prod->get_rhs ().dyn_cast_concrete_scalar ())
1656 146 : return &(get_concrete (concrete_lhs->get_concrete ()
1657 292 : * conc->get_concrete ())
1658 292 : * rhs_prod->get_lhs ());
1659 : }
1660 : }
1661 13829 : if (auto concrete_rhs = k.m_rhs->dyn_cast_concrete_scalar ())
1662 : {
1663 11140 : auto &i = concrete_rhs->get_concrete ();
1664 :
1665 : // X units * 0 --> 0 units
1666 11140 : if (i.is_zero_p ())
1667 24 : return &get_concrete (ConcreteValueType (0));
1668 :
1669 : // X units * 1 --> X units
1670 11116 : if (i.is_one_p ())
1671 8690 : return k.m_lhs;
1672 :
1673 : /* (X units * F1) units * concrete factor F2
1674 : --> (X * (F1 * F2)) units. */
1675 2426 : if (auto lhs_prod = k.m_lhs->dyn_cast_product ())
1676 : return &(lhs_prod->get_lhs ()
1677 202 : * (lhs_prod->get_rhs () * *concrete_rhs));
1678 : }
1679 :
1680 : /* Distributive property. */
1681 : {
1682 4913 : if (auto sum_lhs = k.m_lhs->dyn_cast_sum ())
1683 : {
1684 : /* product(sum(s1 + ... sN), RHS)
1685 : --> sum((s1 * RHS), ... (sN * RHS)). */
1686 160 : std::vector<const scalar<ConcreteValueType> *> products;
1687 347 : for (size_t i = 0; i < sum_lhs->get_num_symbolic_addends (); ++i)
1688 187 : products.push_back (&(sum_lhs->get_symbolic_addend (i)
1689 187 : * (*k.m_rhs)));
1690 160 : if (auto conc = sum_lhs->get_any_concrete_addend ())
1691 149 : products.push_back (&((*conc) * (*k.m_rhs)));
1692 160 : return &get_sum (products);
1693 160 : }
1694 : }
1695 :
1696 : /* Product of product. */
1697 4753 : if (auto lhs_prod = k.m_lhs->dyn_cast_product ())
1698 : {
1699 : /* Product of product: (LHS units * A) * B --> (LHS units) * (A * B) */
1700 12 : auto &unitless_mgr = get_unitless_manager ();
1701 12 : return &get_product (lhs_prod->get_lhs (),
1702 : unitless_mgr.get_product (lhs_prod->get_rhs (),
1703 24 : *k.m_rhs));
1704 : }
1705 :
1706 4741 : if (k.m_lhs->is_unknown_p ())
1707 101 : return &get_unknown ();
1708 4640 : if (k.m_rhs->is_unknown_p ())
1709 211 : return &get_unknown ();
1710 :
1711 : return nullptr;
1712 : }
1713 :
1714 : template<typename ConcreteValueType>
1715 : const scalar<ConcreteValueType> &
1716 38148 : scalar_manager<ConcreteValueType>::
1717 : get_product (const scalar<ConcreteValueType> &lhs,
1718 : const scalar<integer> &rhs)
1719 : {
1720 38148 : typename product<ConcreteValueType>::key k {&lhs, &rhs};
1721 :
1722 38148 : if (auto *s = maybe_fold_product (k))
1723 : return *s;
1724 :
1725 : // Canonicalize order when lhs is also integer
1726 566 : k.canonicalize ();
1727 :
1728 4429 : auto iter = m_product_map.find (k);
1729 4429 : if (iter != m_product_map.end ())
1730 3268 : return *(iter->second);
1731 :
1732 1161 : auto s
1733 1161 : = std::make_unique<product<ConcreteValueType>> (alloc_node_id (),
1734 : *this,
1735 : k);
1736 1161 : auto &result = *s.get ();
1737 1161 : m_product_map.insert ({std::move (k), std::move (s)});
1738 1161 : return result;
1739 1161 : }
1740 :
1741 : template<typename ConcreteValueType>
1742 : const scalar<ConcreteValueType> *
1743 737147 : scalar_manager<ConcreteValueType>::
1744 : maybe_fold_scalar_from_svalue (const typename scalar_from_svalue<ConcreteValueType>::key &k)
1745 : {
1746 737147 : switch (k.m_sval->get_kind ())
1747 : {
1748 : default:
1749 : break;
1750 :
1751 669875 : case SK_CONSTANT:
1752 : {
1753 669875 : tree cst = as_a<const constant_svalue *> (k.m_sval)->get_constant ();
1754 669875 : switch (TREE_CODE (cst))
1755 : {
1756 : default:
1757 : break;
1758 :
1759 669875 : case INTEGER_CST:
1760 : return &get_concrete
1761 669875 : (ConcreteValueType (convert_from_integer_cst (cst)));
1762 : }
1763 : }
1764 : break;
1765 : }
1766 :
1767 : return nullptr;
1768 : }
1769 :
1770 : template<typename ConcreteValueType>
1771 : const scalar<ConcreteValueType> &
1772 737147 : scalar_manager<ConcreteValueType>::get_scalar_from_svalue (const svalue &sval)
1773 : {
1774 737147 : typename scalar_from_svalue<ConcreteValueType>::key k {&sval};
1775 :
1776 737147 : if (auto *s = maybe_fold_scalar_from_svalue (k))
1777 : return *s;
1778 :
1779 67272 : auto iter = m_scalar_from_svalue_map.find (k);
1780 67272 : if (iter != m_scalar_from_svalue_map.end ())
1781 59210 : return *(iter->second);
1782 :
1783 8062 : auto s = std::make_unique<scalar_from_svalue<ConcreteValueType>>
1784 8062 : (alloc_node_id (),
1785 : *this,
1786 : k);
1787 8062 : auto &result = *s.get ();
1788 8062 : m_scalar_from_svalue_map.insert ({std::move (k), std::move (s)});
1789 8062 : return result;
1790 8062 : }
1791 :
1792 : template
1793 : const scalar<integer> &
1794 : scalar_manager<integer>::get_scalar_from_svalue (const svalue &sval);
1795 :
1796 : template
1797 : const scalar<integer_with_unit<units::byte>> &
1798 : scalar_manager<integer_with_unit<units::byte>>::get_scalar_from_svalue (const svalue &sval);
1799 :
1800 : // class scalar_managers
1801 :
1802 : template <>
1803 : scalar_manager<integer_with_unit<units::bit>> &
1804 24 : scalar_managers::get_manager<integer_with_unit<units::bit>> ()
1805 : {
1806 24 : return m_bit_mgr;
1807 : }
1808 :
1809 : template <>
1810 : scalar_manager<integer_with_unit<units::byte>> &
1811 24 : scalar_managers::get_manager<integer_with_unit<units::byte>> ()
1812 : {
1813 24 : return m_byte_mgr;
1814 : }
1815 :
1816 : template <>
1817 : scalar_manager<integer> &
1818 24 : scalar_managers::get_manager<integer> ()
1819 : {
1820 24 : return m_unitless_mgr;
1821 : }
1822 :
1823 : template<typename ConcreteValueType>
1824 : scalar_manager<integer> &
1825 66363 : scalar_manager<ConcreteValueType>::get_unitless_manager ()
1826 : {
1827 66363 : return m_node_mgr.get_scalars ().get_unitless ();
1828 : }
1829 :
1830 : template
1831 : scalar_manager<integer> &
1832 : scalar_manager<concrete_bit_offset>::get_unitless_manager ();
1833 :
1834 : template
1835 : scalar_manager<integer> &
1836 : scalar_manager<concrete_byte_offset>::get_unitless_manager ();
1837 :
1838 : template<>
1839 : scalar_manager<integer> &
1840 1342 : scalar_manager<integer>::get_unitless_manager ()
1841 : {
1842 1342 : return *this;
1843 : }
1844 :
1845 : template <>
1846 : const scalar<concrete_bit_size> &
1847 11032 : scalar_manager<concrete_bit_size>::get_unknown ()
1848 : {
1849 11032 : auto &mgr = m_node_mgr.get_svalue_manager ();
1850 11032 : auto *sval = mgr.get_or_create_unknown_svalue (NULL_TREE);
1851 11032 : return get_scalar_from_svalue (*sval);
1852 : }
1853 :
1854 : template <>
1855 : const scalar<concrete_byte_size> &
1856 411 : scalar_manager<concrete_byte_size>::get_unknown ()
1857 : {
1858 411 : auto &mgr = m_node_mgr.get_svalue_manager ();
1859 411 : auto *sval = mgr.get_or_create_unknown_svalue (size_type_node);
1860 411 : return get_scalar_from_svalue (*sval);
1861 : }
1862 :
1863 : template <>
1864 : const scalar<integer> &
1865 136 : scalar_manager<integer>::get_unknown ()
1866 : {
1867 136 : auto &mgr = m_node_mgr.get_svalue_manager ();
1868 136 : auto *sval = mgr.get_or_create_unknown_svalue (size_type_node);
1869 136 : return get_scalar_from_svalue (*sval);
1870 : }
1871 :
1872 : #if CHECKING_P
1873 :
1874 : template <typename ConcreteValueType>
1875 : const scalar<ConcreteValueType> &
1876 256 : scalar_manager<ConcreteValueType>::get_named_test_scalar (std::string name)
1877 : {
1878 256 : auto obj
1879 : = std::make_unique<named_test_scalar<ConcreteValueType>> (*this,
1880 : std::move (name));
1881 256 : auto &result = *obj.get ();
1882 256 : m_named_test_scalars.push_back (std::move (obj));
1883 512 : return result;
1884 256 : }
1885 :
1886 : #endif /* #if CHECKING_P */
1887 :
1888 : template<>
1889 : const symbolic_bit_size *
1890 993609 : scalar_manager<concrete_bit_size>::
1891 : maybe_fold_bits_from_bytes (const symbolic_byte_size &bytes)
1892 : {
1893 993609 : if (auto *conc = bytes.dyn_cast_concrete_scalar ())
1894 984083 : return &get_concrete
1895 984083 : (concrete_bit_size (conc->get_concrete ().get_integer ()
1896 2952249 : * BITS_PER_UNIT));
1897 :
1898 9526 : if (bytes.is_unknown_p ())
1899 801 : return &get_unknown ();
1900 :
1901 : return nullptr;
1902 : }
1903 :
1904 : template<>
1905 : const symbolic_bit_size &
1906 993609 : scalar_manager<concrete_bit_size>::
1907 : get_bits_from_bytes (const symbolic_byte_size &bytes)
1908 : {
1909 993609 : if (auto *folded = maybe_fold_bits_from_bytes (bytes))
1910 : return *folded;
1911 :
1912 8725 : bits_from_bytes_scalar::key k {&bytes};
1913 8725 : auto iter = m_bits_from_bytes_map.find (k);
1914 8725 : if (iter != m_bits_from_bytes_map.end ())
1915 3592 : return *(iter->second);
1916 :
1917 5133 : auto s = std::make_unique<bits_from_bytes_scalar>
1918 10266 : (alloc_node_id (),
1919 : *this,
1920 5133 : k);
1921 5133 : auto &result = *s.get ();
1922 5133 : m_bits_from_bytes_map.insert ({std::move (k), std::move (s)});
1923 5133 : return result;
1924 5133 : }
1925 :
1926 : } // namespace ana::symbolic
1927 :
1928 : /* Fold
1929 : bytes_from_bits (A + ... + Z) to
1930 : to:
1931 : bytes_from_bits (A) + ... bytes_from_bits (Z)
1932 : if all of the terms themselves fold. */
1933 :
1934 : static const symbolic_byte_size *
1935 5 : maybe_fold_bytes_from_bits_sum (const symbolic::sum<concrete_bit_size> &bit_sum)
1936 : {
1937 5 : std::vector<const symbolic_byte_size *> byte_addends;
1938 :
1939 10 : for (size_t i = 0; i < bit_sum.get_num_symbolic_addends (); ++i)
1940 : {
1941 5 : auto &sym_addend_as_bits = bit_sum.get_symbolic_addend (i);
1942 5 : auto *sym_addend_as_bytes = maybe_bytes_from_bits (sym_addend_as_bits);
1943 5 : if (!sym_addend_as_bytes)
1944 0 : return nullptr;
1945 5 : byte_addends.push_back (sym_addend_as_bytes);
1946 : }
1947 :
1948 5 : if (auto *conc_addend_as_bits = bit_sum.get_any_concrete_addend ())
1949 : {
1950 5 : auto *conc_addend_as_bytes = maybe_bytes_from_bits (*conc_addend_as_bits);
1951 5 : if (!conc_addend_as_bytes)
1952 5 : return nullptr;
1953 0 : byte_addends.push_back (conc_addend_as_bytes);
1954 : }
1955 :
1956 0 : auto &bytes_mgr
1957 0 : = bit_sum.get_mgr ().get_node_manager ().get_scalars ().get_bytes ();
1958 0 : return &bytes_mgr.get_sum (std::move (byte_addends));
1959 5 : }
1960 :
1961 : const symbolic_byte_size *
1962 132089 : maybe_bytes_from_bits (const symbolic_bit_size &bits)
1963 : {
1964 132089 : if (auto *concrete_bits = bits.dyn_cast_concrete_scalar ())
1965 : {
1966 103742 : auto val = concrete_bits->get_concrete ();
1967 103742 : integer_with_unit<units::byte> concrete_bytes;
1968 103742 : if (maybe_bytes_from_bits (val, &concrete_bytes))
1969 : {
1970 103550 : auto &bytes_mgr
1971 103550 : = bits.get_mgr ().get_node_manager ().get_scalars ().get_bytes ();
1972 103550 : return &bytes_mgr.get_concrete (concrete_bytes);
1973 : }
1974 : else
1975 : return nullptr;
1976 103742 : }
1977 28347 : if (auto *b_from_b = bits.dyn_cast_bits_from_bytes_scalar ())
1978 21420 : return &b_from_b->get_bytes ();
1979 :
1980 6927 : if (auto *sum = bits.dyn_cast_sum ())
1981 5 : if (auto *folded = maybe_fold_bytes_from_bits_sum (*sum))
1982 : return folded;
1983 :
1984 6927 : if (auto *product = bits.dyn_cast_product ())
1985 8 : if (auto *lhs_as_bytes = maybe_bytes_from_bits (product->get_lhs ()))
1986 8 : return &((*lhs_as_bytes) * product->get_rhs ());
1987 :
1988 : return nullptr;
1989 : }
1990 :
1991 : #if CHECKING_P
1992 :
1993 : namespace selftest {
1994 :
1995 : using symbolic_bit_manager
1996 : = symbolic::scalar_manager<integer_with_unit<units::bit>>;
1997 : using symbolic_byte_manager
1998 : = symbolic::scalar_manager<integer_with_unit<units::byte>>;
1999 :
2000 : template <typename ConcreteValueType>
2001 : void
2002 28 : assert_scalar_dump_inline_eq (const ::selftest::location &loc,
2003 : const symbolic::scalar<ConcreteValueType> &s,
2004 : enum units::role role,
2005 : const char *expected_str)
2006 : {
2007 28 : pretty_printer pp;
2008 28 : pp_format_decoder (&pp) = default_tree_printer;
2009 28 : s.dump_inline_to_pp (&pp, role);
2010 28 : ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected_str);
2011 28 : }
2012 :
2013 : #define ASSERT_SCALAR_DUMP_INLINE_EQ(SCALAR, ROLE, EXPECTED_STR) \
2014 : SELFTEST_BEGIN_STMT \
2015 : assert_scalar_dump_inline_eq (SELFTEST_LOCATION, (SCALAR), (ROLE), \
2016 : (EXPECTED_STR)); \
2017 : SELFTEST_END_STMT
2018 :
2019 : template<typename ConcreteValueType>
2020 : static void
2021 12 : test_basics ()
2022 : {
2023 12 : symbolic::node_manager node_mgr;
2024 12 : auto &mgr = node_mgr.get_scalars ().get_manager<ConcreteValueType> ();
2025 :
2026 12 : auto &zero = mgr.get_concrete (ConcreteValueType (0));
2027 12 : ASSERT_EQ (zero.get_complexity ().m_num_nodes, 1);
2028 12 : ASSERT_EQ (zero.get_complexity ().m_max_depth, 1);
2029 :
2030 12 : ASSERT_TRUE (zero.is_zero_p ());
2031 12 : ASSERT_FALSE (zero.is_one_p ());
2032 12 : ASSERT_FALSE (zero.is_unknown_p ());
2033 :
2034 12 : auto &one = mgr.get_concrete (ConcreteValueType (1));
2035 12 : ASSERT_EQ (zero.get_complexity ().m_num_nodes, 1);
2036 12 : ASSERT_EQ (zero.get_complexity ().m_max_depth, 1);
2037 :
2038 12 : ASSERT_FALSE (one.is_zero_p ());
2039 12 : ASSERT_TRUE (one.is_one_p ());
2040 12 : ASSERT_FALSE (one.is_unknown_p ());
2041 :
2042 12 : auto &x = mgr.get_named_test_scalar ("x");
2043 12 : ASSERT_EQ (x.get_complexity ().m_num_nodes, 1);
2044 12 : ASSERT_EQ (x.get_complexity ().m_max_depth, 1);
2045 12 : ASSERT_FALSE (x.is_zero_p ());
2046 12 : ASSERT_FALSE (x.is_one_p ());
2047 12 : ASSERT_FALSE (x.is_unknown_p ());
2048 :
2049 12 : auto &unknown = mgr.get_unknown ();
2050 12 : ASSERT_FALSE (unknown.is_zero_p ());
2051 12 : ASSERT_FALSE (unknown.is_one_p ());
2052 12 : ASSERT_TRUE (unknown.is_unknown_p ());
2053 :
2054 12 : diagnostics::markup::lowering_options opts;
2055 12 : ASSERT_SYMBOLIC_NODE_MARKUP_TEXT_EQ (zero, opts, "0");
2056 12 : ASSERT_SYMBOLIC_NODE_MARKUP_TEXT_EQ (one, opts, "1");
2057 12 : ASSERT_SYMBOLIC_NODE_MARKUP_TEXT_EQ (x, opts, "x");
2058 :
2059 : // Verify that consolidation works
2060 12 : ASSERT_SAME_SYMBOLIC_NODE (mgr.get_concrete (ConcreteValueType (0)),
2061 : zero);
2062 12 : ASSERT_SAME_SYMBOLIC_NODE (mgr.get_concrete (ConcreteValueType (1)),
2063 : one);
2064 12 : ASSERT_DIFFERENT_SYMBOLIC_NODE (one, zero);
2065 12 : }
2066 :
2067 : /* Test addition, for scalars of the given unit. */
2068 :
2069 : template<typename ConcreteValueType>
2070 : static void
2071 12 : test_sums ()
2072 : {
2073 12 : symbolic::node_manager node_mgr;
2074 12 : auto &mgr = node_mgr.get_scalars ().get_manager<ConcreteValueType> ();
2075 12 : auto &unitless_mgr = node_mgr.get_scalars ().get_unitless ();
2076 :
2077 12 : auto &x = mgr.get_named_test_scalar ("x");
2078 12 : auto &y = mgr.get_named_test_scalar ("y");
2079 12 : auto &z = mgr.get_named_test_scalar ("z");
2080 :
2081 12 : auto &zero = mgr.get_concrete (ConcreteValueType (0));
2082 :
2083 : /* concrete + concrete. */
2084 : {
2085 24 : auto &sum = (mgr.get_concrete (ConcreteValueType (42))
2086 24 : + mgr.get_concrete (ConcreteValueType (1)));
2087 12 : ASSERT_EQ (sum.dyn_cast_concrete_scalar ()->get_concrete (),
2088 : ConcreteValueType (43));
2089 12 : ASSERT_EQ (sum.get_complexity ().m_num_nodes, 1);
2090 12 : ASSERT_EQ (sum.get_complexity ().m_max_depth, 1);
2091 : }
2092 :
2093 : {
2094 : /* symbolic + concrete. */
2095 12 : auto three = ConcreteValueType (3);
2096 12 : auto &x_plus_3 = (x + three);
2097 12 : ASSERT_EQ (x_plus_3.dyn_cast_sum ()->get_num_symbolic_addends (), 1);
2098 12 : ASSERT_SAME_SYMBOLIC_NODE
2099 : (x_plus_3.dyn_cast_sum ()->get_symbolic_addend (0),
2100 : x);
2101 24 : ASSERT_EQ (*x_plus_3.dyn_cast_sum ()->get_any_concrete_addend_value (),
2102 : three);
2103 12 : ASSERT_EQ (x_plus_3.get_complexity ().m_num_nodes, 3);
2104 12 : ASSERT_EQ (x_plus_3.get_complexity ().m_max_depth, 2);
2105 :
2106 12 : diagnostics::markup::lowering_options opts;
2107 12 : ASSERT_SYMBOLIC_NODE_MARKUP_TEXT_EQ (x_plus_3, opts, "x + 3");
2108 :
2109 : /* concrete + symbolic == symbolic + concrete. */
2110 12 : auto &three_plus_x = (mgr.get_concrete (three) + x);
2111 12 : ASSERT_SAME_SYMBOLIC_NODE (three_plus_x, x_plus_3);
2112 12 : ASSERT_SYMBOLIC_NODE_MARKUP_TEXT_EQ (three_plus_x, opts, "x + 3");
2113 12 : }
2114 :
2115 : /* Additive identity. */
2116 : {
2117 : /* X + 0 -> X. */
2118 12 : ASSERT_SAME_SYMBOLIC_NODE ((x + zero), x);
2119 :
2120 : /* 0 + X -> X. */
2121 12 : ASSERT_SAME_SYMBOLIC_NODE ((zero + x), x);
2122 : }
2123 :
2124 : /* symbolic + symbolic. */
2125 : {
2126 12 : auto &x_plus_y = x + y;
2127 12 : ASSERT_EQ (x_plus_y.dyn_cast_sum ()->get_num_symbolic_addends (), 2);
2128 12 : ASSERT_SAME_SYMBOLIC_NODE
2129 : (x_plus_y.dyn_cast_sum ()->get_symbolic_addend (0),
2130 : x);
2131 12 : ASSERT_SAME_SYMBOLIC_NODE
2132 : (x_plus_y.dyn_cast_sum ()->get_symbolic_addend (1),
2133 : y);
2134 12 : ASSERT_EQ (x_plus_y.dyn_cast_sum ()->get_any_concrete_addend (), nullptr);
2135 12 : ASSERT_EQ (x_plus_y.get_complexity ().m_num_nodes, 3);
2136 12 : ASSERT_EQ (x_plus_y.get_complexity ().m_max_depth, 2);
2137 :
2138 : // Canonicalization of addition:
2139 12 : ASSERT_SAME_SYMBOLIC_NODE ((x + y), x_plus_y);
2140 :
2141 : /* X + Y == Y + X. */
2142 12 : ASSERT_SAME_SYMBOLIC_NODE ((y + x), x_plus_y);
2143 :
2144 12 : diagnostics::markup::lowering_options opts;
2145 12 : ASSERT_SYMBOLIC_NODE_MARKUP_TEXT_EQ (x_plus_y, opts, "x + y");
2146 : }
2147 :
2148 : /* X + Y + Z. */
2149 : {
2150 12 : auto &s = mgr.get_sum ({&x, &y, &z});
2151 12 : ASSERT_EQ (s.dyn_cast_sum ()->get_num_symbolic_addends (), 3);
2152 12 : ASSERT_SAME_SYMBOLIC_NODE (s.dyn_cast_sum ()->get_symbolic_addend (0),
2153 : x);
2154 12 : ASSERT_SAME_SYMBOLIC_NODE (s.dyn_cast_sum ()->get_symbolic_addend (1),
2155 : y);
2156 12 : ASSERT_SAME_SYMBOLIC_NODE (s.dyn_cast_sum ()->get_symbolic_addend (2),
2157 : z);
2158 12 : ASSERT_EQ (s.dyn_cast_sum ()->get_any_concrete_addend (), nullptr);
2159 :
2160 12 : diagnostics::markup::lowering_options opts;
2161 12 : ASSERT_SYMBOLIC_NODE_MARKUP_TEXT_EQ (s, opts, "x + y + z");
2162 : }
2163 :
2164 : /* X + Y + Z == Z + 0 + Y + 0 + X. */
2165 12 : ASSERT_SAME_SYMBOLIC_NODE (mgr.get_sum ({&x, &y, &z}),
2166 : mgr.get_sum ({&z, &zero, &y, &zero, &x}));
2167 :
2168 : /* (X + 3) + 2 --> (X + 5). */
2169 12 : ASSERT_SAME_SYMBOLIC_NODE (((x + ConcreteValueType (3))
2170 : + ConcreteValueType (2)),
2171 : (x + ConcreteValueType (5)));
2172 :
2173 : /* No addends: sum() --> 0. */
2174 12 : ASSERT_SAME_SYMBOLIC_NODE (mgr.get_sum ({}),
2175 : (mgr.get_concrete (ConcreteValueType(0))));
2176 :
2177 : /* One addend: sum(X) --> X. */
2178 12 : ASSERT_SAME_SYMBOLIC_NODE (mgr.get_sum ({&x}),
2179 : x);
2180 :
2181 : /* Unknown + anything --> unknown. */
2182 12 : ASSERT_SAME_SYMBOLIC_NODE (mgr.get_sum ({&mgr.get_unknown (), &x}),
2183 : mgr.get_unknown ());
2184 12 : ASSERT_SAME_SYMBOLIC_NODE (mgr.get_sum ({&x, &mgr.get_unknown ()}),
2185 : mgr.get_unknown ());
2186 12 : ASSERT_SAME_SYMBOLIC_NODE
2187 : (mgr.get_sum ({&mgr.get_unknown (), &mgr.get_unknown ()}),
2188 : mgr.get_unknown ());
2189 :
2190 : /* X + X --> (X * 2). */
2191 : {
2192 12 : auto &s = mgr.get_sum ({&x, &x});
2193 12 : ASSERT_SAME_SYMBOLIC_NODE (s,
2194 : (x * unitless_mgr.get_concrete (2)));
2195 12 : ASSERT_SAME_SYMBOLIC_NODE (s.dyn_cast_product ()->get_lhs (),
2196 : x);
2197 12 : ASSERT_SAME_SYMBOLIC_NODE (s.dyn_cast_product ()->get_rhs (),
2198 : unitless_mgr.get_concrete (2));
2199 : }
2200 :
2201 : /* X + X + X --> (X * 3). */
2202 : {
2203 12 : auto &s = mgr.get_sum ({&x, &x, &x});
2204 12 : ASSERT_SAME_SYMBOLIC_NODE (s,
2205 : (x * unitless_mgr.get_concrete (3)));
2206 12 : ASSERT_SAME_SYMBOLIC_NODE (s.dyn_cast_product ()->get_lhs (),
2207 : x);
2208 12 : ASSERT_SAME_SYMBOLIC_NODE (s.dyn_cast_product ()->get_rhs (),
2209 : unitless_mgr.get_concrete (3));
2210 : }
2211 :
2212 : /* X + Y + X + Y --> (X * 2) + (Y * 2). */
2213 12 : ASSERT_SAME_SYMBOLIC_NODE (mgr.get_sum ({&x, &y, &x, &y}),
2214 : (x * unitless_mgr.get_concrete (2)
2215 : + y * unitless_mgr.get_concrete (2)));
2216 :
2217 : /* X + Y + X + X + Y --> (X * 3) + (Y * 2). */
2218 12 : ASSERT_SAME_SYMBOLIC_NODE (mgr.get_sum ({&x, &y, &x, &x, &y}),
2219 : (x * unitless_mgr.get_concrete (3)
2220 : + y * unitless_mgr.get_concrete (2)));
2221 :
2222 : /* The example from the comment in the header:
2223 : 3x + 4y + 5 - (2x + 5y + 6). */
2224 12 : ASSERT_SAME_SYMBOLIC_NODE
2225 : ((((x * unitless_mgr.get_concrete (3))
2226 : + (y * unitless_mgr.get_concrete (4))
2227 : + mgr.get_concrete (ConcreteValueType(5)))
2228 : - ((x * unitless_mgr.get_concrete (2))
2229 : + (y * unitless_mgr.get_concrete (5))
2230 : + mgr.get_concrete (ConcreteValueType(6)))),
2231 : x - (y + mgr.get_concrete (ConcreteValueType(1))));
2232 12 : }
2233 :
2234 : /* Test multiplication, for scalars of the given type. */
2235 :
2236 : template<typename ConcreteValueType>
2237 : static void
2238 12 : test_products ()
2239 : {
2240 12 : symbolic::node_manager node_mgr;
2241 12 : auto &unitless_mgr = node_mgr.get_scalars ().get_unitless ();
2242 12 : auto &unit_mgr = node_mgr.get_scalars ().get_manager<ConcreteValueType> ();
2243 :
2244 12 : auto &x = unit_mgr.get_named_test_scalar ("x");
2245 :
2246 12 : auto &a = unitless_mgr.get_named_test_scalar ("a");
2247 12 : auto &b = unitless_mgr.get_named_test_scalar ("b");
2248 :
2249 : /* Multiplication by zero: X * 0 --> 0. */
2250 : {
2251 : // e.g. "x bytes * 0 --> 0 bytes":
2252 12 : ASSERT_SAME_SYMBOLIC_NODE ((x * unitless_mgr.get_concrete (0)),
2253 : unit_mgr.get_concrete (ConcreteValueType (0)));
2254 :
2255 : // e.g. "0 bytes * a --> 0 bytes":
2256 12 : ASSERT_SAME_SYMBOLIC_NODE
2257 : ((unit_mgr.get_concrete (ConcreteValueType (0)) * a),
2258 : unit_mgr.get_concrete (ConcreteValueType (0)));
2259 :
2260 : // 0 * unknown --> 0:
2261 12 : ASSERT_SAME_SYMBOLIC_NODE
2262 : (unit_mgr.get_concrete (ConcreteValueType (0))
2263 : * unitless_mgr.get_unknown (),
2264 : unit_mgr.get_concrete (ConcreteValueType (0)));
2265 12 : ASSERT_SAME_SYMBOLIC_NODE
2266 : (unit_mgr.get_unknown () * unitless_mgr.get_concrete (0),
2267 : unit_mgr.get_concrete (ConcreteValueType (0)));
2268 : }
2269 :
2270 : /* Multiplicative identity. */
2271 : {
2272 : /* X * 1 --> X. */
2273 : // e.g. "x bytes * 1 --> x bytes":
2274 12 : ASSERT_SAME_SYMBOLIC_NODE ((x * unitless_mgr.get_concrete (1)),
2275 : x);
2276 :
2277 : /* 1 unit * X for various X. */
2278 : {
2279 : // The constant case e.g. 1 byte * 5 --> 5 bytes
2280 12 : ASSERT_SAME_SYMBOLIC_NODE
2281 : ((unit_mgr.get_concrete (ConcreteValueType (1))
2282 : * unitless_mgr.get_concrete (5)),
2283 : unit_mgr.get_concrete (ConcreteValueType (5)));
2284 :
2285 : // The product cases e.g. 1 byte * (a * 3) --> 3 bytes * a
2286 12 : ASSERT_SAME_SYMBOLIC_NODE
2287 : ((unit_mgr.get_concrete (ConcreteValueType (1))
2288 : * (a * unitless_mgr.get_concrete (3))),
2289 : (unit_mgr.get_concrete (ConcreteValueType (3))
2290 : * a));
2291 12 : ASSERT_SAME_SYMBOLIC_NODE
2292 : ((unit_mgr.get_concrete (ConcreteValueType (1))
2293 : * (unitless_mgr.get_concrete (3) * a)),
2294 : (unit_mgr.get_concrete (ConcreteValueType (3))
2295 : * a));
2296 : }
2297 : }
2298 :
2299 : /* concrete * concrete --> concrete */
2300 : {
2301 : // e.g. "4 bytes * 3 --> 12 bytes":
2302 24 : auto &product = (unit_mgr.get_concrete (ConcreteValueType (4))
2303 24 : * unitless_mgr.get_concrete (3));
2304 12 : ASSERT_EQ (product.dyn_cast_concrete_scalar ()->get_concrete (),
2305 : ConcreteValueType (12));
2306 : }
2307 :
2308 : /* Distributive property: (X + 8) units * 2 --> (X * 2) units + 16 units. */
2309 12 : ASSERT_SAME_SYMBOLIC_NODE
2310 : (((x + unit_mgr.get_concrete (ConcreteValueType (8)))
2311 : * unitless_mgr.get_concrete (2)),
2312 : ((x * unitless_mgr.get_concrete (2))
2313 : + unit_mgr.get_concrete (ConcreteValueType (16))));
2314 :
2315 : /* Chained multiplication: (X * 3) units * 2 --> (X * 6) units. */
2316 12 : ASSERT_SAME_SYMBOLIC_NODE ((x * unitless_mgr.get_concrete (3))
2317 : * unitless_mgr.get_concrete (2),
2318 : (x * unitless_mgr.get_concrete (6)));
2319 :
2320 : /* Chained multiplication: (X units * A) * B --> (X units) * (A * B). */
2321 12 : ASSERT_SAME_SYMBOLIC_NODE ((x * a) * b,
2322 : x * (a * b));
2323 :
2324 : // unknown * a --> unknown:
2325 12 : ASSERT_SAME_SYMBOLIC_NODE (unit_mgr.get_unknown () * a,
2326 : unit_mgr.get_unknown ());
2327 12 : ASSERT_SAME_SYMBOLIC_NODE (x * unitless_mgr.get_unknown (),
2328 : unit_mgr.get_unknown ());
2329 :
2330 : /* (1 unit) * unitless_from_sval(SVAL) --> with_unit_from_sval(SVAL). */
2331 12 : placeholder_svalue sval (node_mgr.alloc_node_id (), size_type_node, "sval");
2332 12 : ASSERT_SAME_SYMBOLIC_NODE
2333 : (unit_mgr.get_concrete (ConcreteValueType (1))
2334 : * unitless_mgr.get_scalar_from_svalue (sval),
2335 : unit_mgr.get_scalar_from_svalue (sval));
2336 12 : }
2337 :
2338 : /* Test negation, for scalars of the given type. */
2339 :
2340 : template<typename ConcreteValueType>
2341 : static void
2342 12 : test_negation ()
2343 : {
2344 12 : symbolic::node_manager node_mgr;
2345 12 : auto &unit_mgr = node_mgr.get_scalars ().get_manager<ConcreteValueType> ();
2346 12 : auto &unitless_mgr = node_mgr.get_scalars ().get_unitless ();
2347 :
2348 12 : auto &concrete = unit_mgr.get_concrete (ConcreteValueType (42));
2349 12 : ASSERT_SAME_SYMBOLIC_NODE (-concrete,
2350 : unit_mgr.get_concrete (ConcreteValueType (-42)));
2351 :
2352 12 : auto &x = unit_mgr.get_named_test_scalar ("x");
2353 12 : ASSERT_SAME_SYMBOLIC_NODE (-x, x * unitless_mgr.get_concrete (-1));
2354 :
2355 12 : ASSERT_SAME_SYMBOLIC_NODE (-unit_mgr.get_unknown (), unit_mgr.get_unknown ());
2356 :
2357 12 : auto &a = unitless_mgr.get_named_test_scalar ("a");
2358 12 : ASSERT_SAME_SYMBOLIC_NODE
2359 : (-(unit_mgr.get_concrete (ConcreteValueType (3)) * a),
2360 : unit_mgr.get_concrete (ConcreteValueType (-3)) * a);
2361 :
2362 12 : ASSERT_SYMBOLIC_NODE_MARKUP_TEXT_EQ
2363 : (-x,
2364 : diagnostics::selftest::get_ascii_markup_opts (),
2365 : "-x");
2366 12 : ASSERT_SYMBOLIC_NODE_MARKUP_TEXT_EQ
2367 : (-x,
2368 : diagnostics::selftest::get_unicode_markup_opts (),
2369 : MARKUP_UNICODE_SYMBOL_UNARY_NEGATION "x");
2370 12 : }
2371 :
2372 : /* Test subtraction, for scalars of the given type. */
2373 :
2374 : template<typename ConcreteValueType>
2375 : static void
2376 12 : test_differences ()
2377 : {
2378 12 : symbolic::node_manager node_mgr;
2379 12 : auto &unitless_mgr = node_mgr.get_scalars ().get_unitless ();
2380 12 : auto &unit_mgr = node_mgr.get_scalars ().get_manager<ConcreteValueType> ();
2381 :
2382 12 : auto &x = unit_mgr.get_named_test_scalar ("x");
2383 12 : auto &y = unit_mgr.get_named_test_scalar ("y");
2384 :
2385 12 : auto &zero = unit_mgr.get_concrete (ConcreteValueType (0));
2386 :
2387 12 : auto &a = unitless_mgr.get_named_test_scalar ("a");
2388 :
2389 : // concrete - concrete
2390 12 : ASSERT_SAME_SYMBOLIC_NODE
2391 : ((unit_mgr.get_concrete (ConcreteValueType (5))
2392 : - unit_mgr.get_concrete (ConcreteValueType (3))),
2393 : unit_mgr.get_concrete (ConcreteValueType (2)));
2394 :
2395 : // concrete - symbolic
2396 12 : ASSERT_SAME_SYMBOLIC_NODE
2397 : (unit_mgr.get_concrete (ConcreteValueType (5)) - x,
2398 : (-x) + unit_mgr.get_concrete (ConcreteValueType (5)));
2399 :
2400 : // symbolic - concrete
2401 12 : ASSERT_SAME_SYMBOLIC_NODE
2402 : (x - unit_mgr.get_concrete (ConcreteValueType (3)),
2403 : x + unit_mgr.get_concrete (ConcreteValueType (-3)));
2404 :
2405 : // symbolic - symbolic
2406 12 : ASSERT_SAME_SYMBOLIC_NODE (x - y, x + (-y));
2407 12 : ASSERT_SYMBOLIC_NODE_MARKUP_TEXT_EQ
2408 : (x - y,
2409 : diagnostics::selftest::get_ascii_markup_opts (),
2410 : "x - y");
2411 12 : ASSERT_SYMBOLIC_NODE_MARKUP_TEXT_EQ
2412 : (x - y,
2413 : diagnostics::selftest::get_unicode_markup_opts (),
2414 : "x " MARKUP_UNICODE_SYMBOL_SUBTRACTION " y");
2415 :
2416 : {
2417 12 : pretty_printer pp;
2418 12 : symbolic::pp_element_for_node e (x - y, true);
2419 12 : pp_printf (&pp, "before{%e}after", &e);
2420 12 : ASSERT_STREQ (pp_formatted_text (&pp), "before{x - y}after");
2421 12 : }
2422 :
2423 : // (X - X) --> 0
2424 12 : ASSERT_SAME_SYMBOLIC_NODE ((x - x),
2425 : zero);
2426 :
2427 : // (unknown - 1) --> unknown
2428 12 : ASSERT_SAME_SYMBOLIC_NODE
2429 : (unit_mgr.get_unknown () - unit_mgr.get_concrete (ConcreteValueType (1)),
2430 : unit_mgr.get_unknown ());
2431 : // (unknown - unknown) --> unknown
2432 12 : ASSERT_SAME_SYMBOLIC_NODE
2433 : ((unit_mgr.get_unknown () - unit_mgr.get_unknown ()),
2434 : unit_mgr.get_unknown ());
2435 :
2436 : // (X - Y) + Y --> X
2437 12 : ASSERT_SAME_SYMBOLIC_NODE ((x - y) + y, x);
2438 :
2439 : // (X units * 5) - (X units * 3) --> (X units * 2)
2440 12 : ASSERT_SAME_SYMBOLIC_NODE
2441 : ((x * unitless_mgr.get_concrete (5)
2442 : - (x * unitless_mgr.get_concrete (3))),
2443 : x * unitless_mgr.get_concrete (2));
2444 :
2445 : // (5 units * a) - (3 units * a) --> (2 * a) units
2446 12 : ASSERT_SAME_SYMBOLIC_NODE
2447 : ((unit_mgr.get_concrete (ConcreteValueType (5)) * a)
2448 : - (unit_mgr.get_concrete (ConcreteValueType (3)) * a),
2449 : unit_mgr.get_concrete (ConcreteValueType (2)) * a);
2450 12 : }
2451 :
2452 : template<typename ConcreteValueType>
2453 : static void
2454 12 : test_comparisons ()
2455 : {
2456 12 : symbolic::node_manager node_mgr;
2457 12 : auto &scalar_mgr = node_mgr.get_scalars ().get_manager<ConcreteValueType> ();
2458 :
2459 : /* Tests of get_total_ordering. */
2460 :
2461 12 : auto &three = scalar_mgr.get_concrete (ConcreteValueType (3));
2462 12 : auto &four = scalar_mgr.get_concrete (ConcreteValueType (4));
2463 12 : auto &x = scalar_mgr.get_named_test_scalar ("x");
2464 12 : auto &y = scalar_mgr.get_named_test_scalar ("y");
2465 :
2466 : /* Concrete vs concrete. */
2467 : {
2468 12 : ASSERT_TRUE (three == three);
2469 12 : ASSERT_FALSE (three == four);
2470 :
2471 12 : ASSERT_TRUE (three != four);
2472 12 : ASSERT_FALSE (three != three);
2473 :
2474 12 : ASSERT_TRUE (three < four);
2475 12 : ASSERT_FALSE (three < three);
2476 12 : ASSERT_FALSE (four < three);
2477 :
2478 12 : ASSERT_TRUE (three <= four);
2479 12 : ASSERT_TRUE (three <= three);
2480 12 : ASSERT_FALSE (four <= three);
2481 :
2482 12 : ASSERT_FALSE (three > four);
2483 12 : ASSERT_FALSE (three > three);
2484 12 : ASSERT_TRUE (four > three);
2485 :
2486 12 : ASSERT_FALSE (three >= four);
2487 12 : ASSERT_TRUE (three >= three);
2488 12 : ASSERT_TRUE (four >= three);
2489 : }
2490 :
2491 : /* Symbolic vs concrete and vice versa:
2492 : all concrete should be before all symbolic. */
2493 : {
2494 12 : ASSERT_FALSE (three == x);
2495 :
2496 12 : ASSERT_TRUE (three != x);
2497 :
2498 12 : ASSERT_TRUE (three < x);
2499 12 : ASSERT_FALSE (x < three);
2500 :
2501 12 : ASSERT_TRUE (three <= x);
2502 12 : ASSERT_FALSE (x <= three);
2503 :
2504 12 : ASSERT_FALSE (three > x);
2505 12 : ASSERT_TRUE (x > three);
2506 :
2507 12 : ASSERT_FALSE (three >= x);
2508 12 : ASSERT_TRUE (x >= three);
2509 : }
2510 :
2511 : /* Symbolic vs symbolic. */
2512 : {
2513 : /* Unfoldable: order by creation order. */
2514 : {
2515 12 : ASSERT_TRUE (x == x);
2516 12 : ASSERT_FALSE (x == y);
2517 :
2518 12 : ASSERT_TRUE (x != y);
2519 12 : ASSERT_FALSE (x != x);
2520 :
2521 12 : ASSERT_TRUE (x < y);
2522 12 : ASSERT_FALSE (x < x);
2523 12 : ASSERT_FALSE (y < x);
2524 :
2525 12 : ASSERT_TRUE (x <= y);
2526 12 : ASSERT_TRUE (x <= x);
2527 12 : ASSERT_FALSE (y <= x);
2528 :
2529 12 : ASSERT_FALSE (x > y);
2530 12 : ASSERT_FALSE (x > x);
2531 12 : ASSERT_TRUE (y > x);
2532 :
2533 12 : ASSERT_FALSE (x >= y);
2534 12 : ASSERT_TRUE (x >= x);
2535 12 : ASSERT_TRUE (y >= x);
2536 : }
2537 :
2538 : /* Cases that have a constant difference and thus can be compared. */
2539 : {
2540 12 : ASSERT_FALSE (x == x + three);
2541 :
2542 12 : ASSERT_TRUE (x != x + three);
2543 :
2544 12 : ASSERT_TRUE (x < x + three);
2545 12 : ASSERT_FALSE (x + three < x);
2546 :
2547 12 : ASSERT_TRUE (x <= x + three);
2548 12 : ASSERT_FALSE (x + three <= x);
2549 :
2550 12 : ASSERT_FALSE (x > x + three);
2551 12 : ASSERT_TRUE (x + three > x);
2552 :
2553 12 : ASSERT_FALSE (x >= x + three);
2554 12 : ASSERT_TRUE (x + three >= x);
2555 : }
2556 : }
2557 12 : }
2558 :
2559 : template<typename ConcreteValueType>
2560 : static void
2561 12 : per_concrete_value_type_scalar_tests ()
2562 : {
2563 12 : test_basics<ConcreteValueType> ();
2564 12 : test_sums<ConcreteValueType> ();
2565 12 : test_products<ConcreteValueType> ();
2566 12 : test_negation<ConcreteValueType> ();
2567 12 : test_differences<ConcreteValueType> ();
2568 12 : test_comparisons<ConcreteValueType> ();
2569 12 : }
2570 :
2571 : /* Verify that symbolic::scalar subclasses are dumped correctly.
2572 : These can't be type-independent, as the strings mention the unit. */
2573 :
2574 : static void
2575 4 : test_dumping_scalars ()
2576 : {
2577 4 : symbolic::node_manager node_mgr;
2578 4 : auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
2579 4 : auto &byte_mgr = node_mgr.get_scalars ().get_bytes ();
2580 4 : auto &unitless_mgr = node_mgr.get_scalars ().get_unitless ();
2581 :
2582 4 : auto &x = bit_mgr.get_named_test_scalar ("x");
2583 4 : auto &y = bit_mgr.get_named_test_scalar ("y");
2584 4 : auto &z = bit_mgr.get_named_test_scalar ("z");
2585 :
2586 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ (x, "named_test_scalar<bits>: 'x'\n");
2587 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ (bit_mgr.get_concrete (8_bits),
2588 : "concrete_scalar<bits>: 8\n");
2589 :
2590 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2591 : (x + y + z,
2592 : ("sum<bits>\n"
2593 : "+- named_test_scalar<bits>: 'x'\n"
2594 : "+- named_test_scalar<bits>: 'y'\n"
2595 : "`- named_test_scalar<bits>: 'z'\n"));
2596 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2597 : (x + y + z + 42_bits,
2598 : ("sum<bits>\n"
2599 : "+- named_test_scalar<bits>: 'x'\n"
2600 : "+- named_test_scalar<bits>: 'y'\n"
2601 : "+- named_test_scalar<bits>: 'z'\n"
2602 : "`- concrete_scalar<bits>: 42\n"));
2603 4 : ASSERT_SCALAR_DUMP_INLINE_EQ (x + y + z + 42_bits, units::role::offset,
2604 : "bit x + bit y + bit z + bit 42");
2605 4 : ASSERT_SCALAR_DUMP_INLINE_EQ (x + y + z + 42_bits, units::role::size,
2606 : "x bits + y bits + z bits + 42 bits");
2607 :
2608 4 : auto &m = byte_mgr.get_named_test_scalar ("m");
2609 4 : auto &n = byte_mgr.get_named_test_scalar ("n");
2610 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ (m, "named_test_scalar<bytes>: 'm'\n");
2611 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ (byte_mgr.get_concrete (10_bytes),
2612 : "concrete_scalar<bytes>: 10\n");
2613 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2614 : (m + n,
2615 : ("sum<bytes>\n"
2616 : "+- named_test_scalar<bytes>: 'm'\n"
2617 : "`- named_test_scalar<bytes>: 'n'\n"));
2618 4 : ASSERT_SCALAR_DUMP_INLINE_EQ (m + n, units::role::offset,
2619 : "byte m + byte n");
2620 4 : ASSERT_SCALAR_DUMP_INLINE_EQ (m + n, units::role::size,
2621 : "m bytes + n bytes");
2622 :
2623 4 : auto &a = unitless_mgr.get_named_test_scalar ("a");
2624 4 : auto &b = unitless_mgr.get_named_test_scalar ("b");
2625 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ (a, "named_test_scalar<integer>: 'a'\n");
2626 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ (b, "named_test_scalar<integer>: 'b'\n");
2627 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2628 : (a + b,
2629 : ("sum<integer>\n"
2630 : "+- named_test_scalar<integer>: 'a'\n"
2631 : "`- named_test_scalar<integer>: 'b'\n"));
2632 :
2633 : // Dump a complex example, showing a product
2634 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2635 : ((m * a) + (n * b),
2636 : ("sum<bytes>\n"
2637 : "+- product<bytes>\n"
2638 : "| +- named_test_scalar<bytes>: 'm'\n"
2639 : "| `- named_test_scalar<integer>: 'a'\n"
2640 : "`- product<bytes>\n"
2641 : " +- named_test_scalar<bytes>: 'n'\n"
2642 : " `- named_test_scalar<integer>: 'b'\n"));
2643 :
2644 4 : ASSERT_SCALAR_DUMP_INLINE_EQ
2645 : ((m * a) + (n * b),
2646 : units::role::size,
2647 : "m bytes * a + n bytes * b");
2648 4 : }
2649 :
2650 : /* Test an example showing multiple levels of nesting,
2651 : combining addition and multiplication. */
2652 :
2653 : static void
2654 4 : test_example_1 ()
2655 : {
2656 4 : symbolic::node_manager node_mgr;
2657 4 : auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
2658 4 : auto &unitless_mgr = node_mgr.get_scalars ().get_unitless ();
2659 :
2660 4 : auto &x = bit_mgr.get_named_test_scalar ("x");
2661 4 : auto &y = bit_mgr.get_named_test_scalar ("y");
2662 4 : auto &z = bit_mgr.get_named_test_scalar ("z");
2663 :
2664 4 : auto &a = unitless_mgr.get_named_test_scalar ("a");
2665 4 : auto &b = unitless_mgr.get_named_test_scalar ("b");
2666 :
2667 4 : auto &s = (x * a) + (y * b) + z;
2668 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2669 : (s,
2670 : ("sum<bits>\n"
2671 : "+- product<bits>\n"
2672 : "| +- named_test_scalar<bits>: 'x'\n"
2673 : "| `- named_test_scalar<integer>: 'a'\n"
2674 : "+- product<bits>\n"
2675 : "| +- named_test_scalar<bits>: 'y'\n"
2676 : "| `- named_test_scalar<integer>: 'b'\n"
2677 : "`- named_test_scalar<bits>: 'z'\n"));
2678 4 : s.to_json ();
2679 :
2680 4 : ASSERT_SYMBOLIC_NODE_MARKUP_TEXT_EQ
2681 : (s,
2682 : diagnostics::selftest::get_ascii_markup_opts (),
2683 : "(x * a) + (y * b) + z");
2684 :
2685 4 : ASSERT_SYMBOLIC_NODE_MARKUP_TEXT_EQ
2686 : (s,
2687 : diagnostics::selftest::get_unicode_markup_opts (),
2688 : ("(x " MARKUP_UNICODE_SYMBOL_MULTIPLICATION " a)"
2689 : " + (y " MARKUP_UNICODE_SYMBOL_MULTIPLICATION " b)"
2690 : " + z"));
2691 :
2692 4 : ASSERT_EQ (s.get_complexity ().m_num_nodes, 8);
2693 4 : ASSERT_EQ (s.get_complexity ().m_max_depth, 3);
2694 4 : }
2695 :
2696 : static void
2697 4 : test_example_2 ()
2698 : {
2699 : /* Consider:
2700 : |
2701 : | struct coord { uint32_t x; uint32_t y; };
2702 : | struct triangle { coord m_vertices[3]; };
2703 : |
2704 : | ptr = malloc (sizeof (triangle) * n);
2705 : |
2706 : and tracking the size of the allocated buffer. */
2707 :
2708 4 : symbolic::node_manager node_mgr;
2709 4 : auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
2710 4 : auto &byte_mgr = node_mgr.get_scalars ().get_bytes ();
2711 4 : auto &unitless_mgr = node_mgr.get_scalars ().get_unitless ();
2712 :
2713 4 : auto &n = unitless_mgr.get_named_test_scalar ("n");
2714 :
2715 : /* In bytes. */
2716 4 : {
2717 4 : auto &sizeof_x = byte_mgr.get_concrete (4_bytes);
2718 4 : auto &sizeof_y = byte_mgr.get_concrete (4_bytes);
2719 :
2720 4 : auto &sizeof_coord = sizeof_x + sizeof_y;
2721 4 : ASSERT_EQ (sizeof_coord.dyn_cast_concrete_scalar ()->get_concrete (),
2722 : 8_bytes);
2723 :
2724 4 : auto &sizeof_triangle = sizeof_coord * unitless_mgr.get_concrete (3);
2725 4 : ASSERT_EQ (sizeof_triangle.dyn_cast_concrete_scalar ()->get_concrete (),
2726 : 24_bytes);
2727 :
2728 4 : auto &sizeof_buffer = sizeof_triangle * n;
2729 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2730 : (sizeof_buffer,
2731 : ("product<bytes>\n"
2732 : "+- concrete_scalar<bytes>: 24\n"
2733 : "`- named_test_scalar<integer>: 'n'\n"));
2734 :
2735 4 : ASSERT_SCALAR_DUMP_INLINE_EQ
2736 : (sizeof_buffer,
2737 : units::role::size,
2738 : "24 bytes * n");
2739 :
2740 4 : sizeof_buffer.to_json ();
2741 : }
2742 :
2743 : /* In bits. */
2744 4 : {
2745 4 : auto &sizeof_x = bit_mgr.get_concrete (32_bits);
2746 4 : auto &sizeof_y = bit_mgr.get_concrete (32_bits);
2747 :
2748 4 : auto &sizeof_coord = sizeof_x + sizeof_y;
2749 4 : ASSERT_EQ (sizeof_coord.dyn_cast_concrete_scalar ()->get_concrete (),
2750 : 64_bits);
2751 :
2752 4 : auto &sizeof_triangle = sizeof_coord * unitless_mgr.get_concrete (3);
2753 4 : ASSERT_EQ (sizeof_triangle.dyn_cast_concrete_scalar ()->get_concrete (),
2754 : 192_bits);
2755 :
2756 4 : auto &sizeof_buffer = sizeof_triangle * n;
2757 4 : ASSERT_SYMBOLIC_NODE_DUMP_EQ
2758 : (sizeof_buffer,
2759 : ("bits_from_bytes_scalar\n"
2760 : "`- product<bytes>\n"
2761 : " +- concrete_scalar<bytes>: 24\n"
2762 : " `- named_test_scalar<integer>: 'n'\n"));
2763 :
2764 4 : ASSERT_SCALAR_DUMP_INLINE_EQ
2765 : (sizeof_buffer,
2766 : units::role::size,
2767 : "bits_from_bytes_scalar(24 bytes * n)");
2768 :
2769 4 : sizeof_buffer.to_json ();
2770 : }
2771 4 : }
2772 :
2773 : static void
2774 4 : test_bits_from_bytes ()
2775 : {
2776 4 : symbolic::node_manager node_mgr;
2777 4 : auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
2778 4 : auto &byte_mgr = node_mgr.get_scalars ().get_bytes ();
2779 4 : auto &unitless_mgr = node_mgr.get_scalars ().get_unitless ();
2780 :
2781 4 : auto &num_bytes_a = byte_mgr.get_named_test_scalar ("num_bytes_a");
2782 4 : auto &num_bytes_b = byte_mgr.get_named_test_scalar ("num_bytes_b");
2783 :
2784 4 : ASSERT_SAME_SYMBOLIC_NODE
2785 : (bits_from_bytes (num_bytes_a) + bits_from_bytes (num_bytes_b),
2786 : bits_from_bytes (num_bytes_a + num_bytes_b));
2787 :
2788 4 : ASSERT_SAME_SYMBOLIC_NODE
2789 : (bits_from_bytes (num_bytes_a)
2790 : + bits_from_bytes (num_bytes_b)
2791 : + bits_from_bytes (1_byte),
2792 : bits_from_bytes (num_bytes_a + num_bytes_b + 1_byte));
2793 :
2794 4 : ASSERT_SAME_SYMBOLIC_NODE
2795 : (bits_from_bytes (byte_mgr.get_unknown ()),
2796 : bit_mgr.get_unknown ());
2797 :
2798 4 : placeholder_svalue sval (node_mgr.alloc_node_id (), size_type_node, "sval");
2799 4 : auto &bytes_from_sval = byte_mgr.get_scalar_from_svalue (sval);
2800 4 : auto &unitless_from_sval = unitless_mgr.get_scalar_from_svalue (sval);
2801 4 : ASSERT_EQ (bits_from_bytes (bytes_from_sval).get_kind (),
2802 : symbolic::scalar<concrete_bit_offset>::kind::bits_from_bytes);
2803 4 : ASSERT_SAME_SYMBOLIC_NODE (bit_mgr.get_concrete (8_bits) * unitless_from_sval,
2804 : bits_from_bytes (bytes_from_sval));
2805 4 : }
2806 :
2807 : static void
2808 4 : test_maybe_bytes_from_bits ()
2809 : {
2810 4 : symbolic::node_manager node_mgr;
2811 4 : auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
2812 4 : auto &byte_mgr = node_mgr.get_scalars ().get_bytes ();
2813 4 : auto &unitless_mgr = node_mgr.get_scalars ().get_unitless ();
2814 :
2815 4 : ASSERT_SAME_SYMBOLIC_NODE
2816 : (*maybe_bytes_from_bits (bit_mgr.get_concrete (8_bits)),
2817 : byte_mgr.get_concrete (1_byte));
2818 4 : ASSERT_EQ (maybe_bytes_from_bits (bit_mgr.get_concrete (3_bits)),
2819 : nullptr);
2820 :
2821 4 : placeholder_svalue sval (node_mgr.alloc_node_id (), size_type_node, "sval");
2822 4 : ASSERT_SAME_SYMBOLIC_NODE
2823 : (maybe_bytes_from_bits (bit_mgr.get_concrete (8_bits)
2824 : * unitless_mgr.get_scalar_from_svalue (sval)),
2825 : &byte_mgr.get_scalar_from_svalue (sval));
2826 4 : }
2827 :
2828 : /* Run all of the selftests within this file. */
2829 :
2830 : void
2831 4 : analyzer_symbolic_scalars_cc_tests ()
2832 : {
2833 4 : per_concrete_value_type_scalar_tests<integer> ();
2834 4 : per_concrete_value_type_scalar_tests<integer_with_unit<units::bit>> ();
2835 4 : per_concrete_value_type_scalar_tests<integer_with_unit<units::byte>> ();
2836 :
2837 4 : test_dumping_scalars ();
2838 4 : test_example_1 ();
2839 4 : test_example_2 ();
2840 :
2841 4 : test_bits_from_bytes ();
2842 4 : test_maybe_bytes_from_bits ();
2843 4 : }
2844 :
2845 : } // namespace selftest
2846 :
2847 : #endif /* CHECKING_P */
2848 :
2849 : } // namespace ana
2850 :
2851 : #endif /* #if ENABLE_ANALYZER */
|