Line data Source code
1 : /* Unit-safe symbolic scalar values (e.g. "n * 32 bytes")
2 : Copyright (C) 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 : #ifndef GCC_ANALYZER_SYMBOLIC_SCALARS_H
22 : #define GCC_ANALYZER_SYMBOLIC_SCALARS_H
23 :
24 : #include "analyzer/units.h"
25 : #include "analyzer/symbolic-nodes.h"
26 : #include "analyzer/integer-with-unit.h"
27 :
28 : namespace ana {
29 : namespace symbolic {
30 :
31 : template<typename ConcreteValueType>
32 : class scalar_manager;
33 :
34 : template<typename ConcreteValueType>
35 : class concrete_scalar;
36 :
37 : template<typename ConcreteValueType>
38 : class sum;
39 :
40 : template<typename ConcreteValueType>
41 : class product;
42 :
43 : template<typename ConcreteValueType>
44 : class scalar_from_svalue;
45 :
46 : template<typename ConcreteValueType>
47 : class overcomplex_scalar;
48 :
49 : class bits_from_bytes_scalar;
50 :
51 : /* symbolic::scalar
52 :
53 : The class hierarchy looks like this (using indentation to show
54 : inheritance):
55 :
56 : scalar: abstract base class
57 : concrete: a value of ConcreteValueType
58 : sum: the sum of two of more scalars
59 : product: the product of a scalar and a dimensionless scalar
60 : scalar_from_svalue: a scalar derived from an svalue
61 : named_test: a placeholder for use in selftests
62 : bits_from_bytes_scalar: converting a scalar measured in bits
63 : into one measured in bytes. */
64 :
65 : template<typename ConcreteValueType>
66 : class scalar : public symbolic::value_node
67 : {
68 : public:
69 : enum class kind
70 : {
71 : concrete,
72 : sum,
73 : product,
74 : from_svalue,
75 : named_test,
76 : bits_from_bytes
77 : };
78 :
79 : virtual ~scalar () = default;
80 :
81 : scalar_manager<ConcreteValueType> &
82 367480 : get_mgr () const { return m_mgr; }
83 :
84 169614 : enum kind get_kind () const { return m_kind; }
85 :
86 : virtual const concrete_scalar<ConcreteValueType> *
87 403193 : dyn_cast_concrete_scalar () const { return nullptr; }
88 : virtual const sum<ConcreteValueType> *
89 27234 : dyn_cast_sum () const { return nullptr; }
90 : virtual const product<ConcreteValueType> *
91 27924 : dyn_cast_product () const { return nullptr; }
92 : virtual const scalar_from_svalue<ConcreteValueType> *
93 50107 : dyn_cast_scalar_from_svalue () const { return nullptr; }
94 : virtual const bits_from_bytes_scalar *
95 12149 : dyn_cast_bits_from_bytes_scalar () const { return nullptr; }
96 :
97 : virtual void
98 : dump_inline_to_pp (pretty_printer *pp, enum units::role) const = 0;
99 :
100 : iter_result
101 0 : for_each_svalue (iter_result (*) (const svalue &sval,
102 : void *user_data),
103 : void *) const final override
104 : {
105 0 : return iter_result::keep_going;
106 : }
107 :
108 : const char *
109 19795 : get_any_dump_color () const override { return "scalar"; }
110 :
111 : bool
112 : is_zero_p () const;
113 :
114 : bool
115 : is_one_p () const;
116 :
117 : bool
118 : is_unknown_p () const;
119 :
120 : // FIXME: unit test these
121 : static bool
122 : get_total_ordering (const scalar<ConcreteValueType> &a,
123 : enum tree_code op,
124 : const scalar<ConcreteValueType> &b,
125 : const region_model *model);
126 : static tristate
127 : get_partial_ordering (const scalar<ConcreteValueType> &a,
128 : enum tree_code op,
129 : const scalar<ConcreteValueType> &b,
130 : const region_model *model);
131 : // FIXME: unit test these
132 : // FIXME: add notes on the semantics of these comparisons
133 : bool
134 88 : operator== (const scalar<ConcreteValueType> &other) const
135 : {
136 88 : return get_total_ordering (*this, EQ_EXPR, other, nullptr);
137 : }
138 : bool
139 72 : operator!= (const scalar<ConcreteValueType> &other) const
140 : {
141 72 : return get_total_ordering (*this, NE_EXPR, other, nullptr);
142 : }
143 : bool
144 579 : operator< (const scalar<ConcreteValueType> &other) const
145 : {
146 579 : return get_total_ordering (*this, LT_EXPR, other, nullptr);
147 : }
148 : bool
149 1615 : operator<= (const scalar<ConcreteValueType> &other) const
150 : {
151 1615 : return get_total_ordering (*this, LE_EXPR, other, nullptr);
152 : }
153 : bool
154 150 : operator> (const scalar<ConcreteValueType> &other) const
155 : {
156 150 : return get_total_ordering (*this, GT_EXPR, other, nullptr);
157 : }
158 : bool
159 256 : operator>= (const scalar<ConcreteValueType> &other) const
160 : {
161 256 : return get_total_ordering (*this, GE_EXPR, other, nullptr);
162 : }
163 :
164 : protected:
165 108438 : scalar (complexity c, unsigned id, scalar_manager<ConcreteValueType> &mgr,
166 : enum kind kind)
167 : : value_node (c, id),
168 108438 : m_mgr (mgr),
169 108182 : m_kind (kind)
170 : {
171 : }
172 :
173 : std::unique_ptr<json::object>
174 : make_json_obj (const char *type_name) const;
175 :
176 : private:
177 : void
178 : print_dump_widget_label (pretty_printer *pp) const final override;
179 :
180 : virtual void
181 : print_dump_widget_label_for_scalar (pretty_printer *pp) const = 0;
182 :
183 : scalar_manager<ConcreteValueType> &m_mgr;
184 : enum kind m_kind;
185 : };
186 :
187 : } // namespace symbolic
188 :
189 : /* Abbreviations for various useful symbolic::scalar types. */
190 :
191 : using symbolic_integer = symbolic::scalar<integer>;
192 :
193 : using symbolic_bit_offset = symbolic::scalar<integer_with_unit<units::bit>>;
194 : using symbolic_bit_size = symbolic::scalar<integer_with_unit<units::bit>>;
195 :
196 : using symbolic_byte_offset = symbolic::scalar<integer_with_unit<units::byte>>;
197 : using symbolic_byte_size = symbolic::scalar<integer_with_unit<units::byte>>;
198 :
199 : namespace symbolic {
200 :
201 : /* Symbolic value wrapping a concrete scalar. */
202 :
203 : template<typename ConcreteValueType>
204 : class concrete_scalar : public scalar<ConcreteValueType>
205 : {
206 : public:
207 : const concrete_scalar<ConcreteValueType> *
208 33510638 : dyn_cast_concrete_scalar () const final override { return this; }
209 :
210 : concrete_scalar (unsigned id,
211 : scalar_manager<ConcreteValueType> &mgr,
212 : const ConcreteValueType &value);
213 :
214 : const ConcreteValueType &
215 24945376 : get_concrete () const { return m_value; }
216 :
217 : const integer &
218 : get_integer () const;
219 :
220 : void
221 : accept_node_visitor (node_visitor &v) const final override;
222 :
223 : std::unique_ptr<json::object>
224 : to_json () const final override;
225 :
226 : void
227 : dump_inline_to_pp (pretty_printer *pp, enum units::role) const final override;
228 :
229 : std::unique_ptr<diagnostics::markup::node>
230 : make_markup_node (markup_context &markup_ctxt) const final override;
231 :
232 : private:
233 : void
234 : print_dump_widget_label_for_scalar (pretty_printer *pp) const final override;
235 :
236 : void
237 : add_dump_widget_children (text_art::tree_widget &,
238 : node_dump_state &nds) const final override;
239 :
240 : ConcreteValueType m_value;
241 : };
242 :
243 : /* Symbolic value for the sum of two of more scalars.
244 :
245 : Consolidation/canonicalization:
246 : - we never have a sum as an addend of another sum
247 : (we flatten sums of sums)
248 : - a sum is expressed as a sum of one or more non-concrete_scalars,
249 : plus an optional concrete_scalar; the latter is the null pointer iff
250 : the concrete addends sum to zero.
251 : - we must have at least two addends (two or more symbolic, or a concrete
252 : and one or more symbolic). */
253 :
254 : template<typename ConcreteValueType>
255 : class sum : public scalar<ConcreteValueType>
256 : {
257 : public:
258 275193 : struct memoization_key
259 : {
260 : std::vector<const scalar<ConcreteValueType> *> m_addends;
261 :
262 : bool operator< (const memoization_key &other) const;
263 : };
264 :
265 : /* A helper class for canonicalizing sums in the form:
266 : (v1 * f1) + (v2 * f2) + .... (vN * fN) + CST
267 : i.e. as a pair of maps from:
268 : key: v1 ... vN
269 : to
270 : value: f1 ... fN
271 : (one map for where the coefficients have units, and another
272 : for where they are unitless), plus a constant of CVT.
273 :
274 : For example, given
275 : | 3x + 4y + 5 - (2x + 5y + 6)
276 : | => (x * 3) + (y * 4) + 5 - ((x * 2) + (y * 5) + 6)
277 : | => (x * 3) + (y * 4) + 5 + ((x * -2) + (y * -5) + -6)
278 : | => (x * 3) + (y * 4) + 5 + ((x * -2) + (y * -5) + -6)
279 : we canonicalize/fold the addends thus:
280 : | => ({} + 0) + (x * 3) + (y * 4) + 5 + ((x * -2) + (y * -5) + -6)
281 : | => ({x: 3} + 0}) + (y * 4) + 5 + ((x * -2) + (y * -5) + -6)
282 : | => ({x: 3, y: 4} + 0) + 5 + ((x * -2) + (y * -5) + -6)
283 : | => ({x: 3, y: 4} + 5) + ((x * -2) + (y * -5) + -6)
284 : | => ({x: 1, y: 4} + 5) + (y * -5) + -6)
285 : | => ({x: 1, y: -1} + 5) + -6)
286 : | => ({x: 1, y: -1} + -1)
287 : from which we can get this:
288 : | => x + (y * -1) + -1
289 : i.e. sum(x, product(y, -1), -1). */
290 : struct folding_helper
291 : {
292 28118 : folding_helper () : m_sum_of_concrete_values (0) {}
293 :
294 : void
295 : add_addend (const scalar<ConcreteValueType> &addend,
296 : scalar_manager<integer> &unitless_mgr);
297 :
298 : /* Add (FACTOR_WITH_UNIT * UNITLESS_FACTOR) to the sum. */
299 : void
300 : add_to_coefficient_for_addend
301 : (const scalar<ConcreteValueType> *factor_with_unit,
302 : const scalar<integer> *unitless_factor);
303 :
304 : void
305 : dump () const;
306 :
307 : std::unique_ptr<text_art::tree_widget>
308 : make_dump_widget (symbolic::node_dump_state &nds) const;
309 :
310 : /* Maps from unfoldable symbolic addend to symbolic factor for that
311 : addend. This is the "(v1 * f1) + (v2 * f2) + .... (vN * fN)"
312 : from above, i.e "{v1: f1, v2: f2, ..., vN: fN}".
313 : Note that the coefficient can be zero for cases such as "X + (-X)".
314 : We'll discard these when we build the creation_key.
315 :
316 : We have two maps:
317 :
318 : (a) a map in which the terms have units and the
319 : coefficients are unitless, e.g.
320 : (N bytes * 16) + (N bytes * -4), and
321 :
322 : (b) a map in which the coefficents have units and the
323 : terms are unitless, e.g.
324 : (16 bytes * N) + (-4 bytes * N)
325 :
326 : We try to use concrete factors as coefficients, and
327 : purely symbolic factors as "terms". */
328 :
329 : std::map<const scalar<ConcreteValueType> *,
330 : const scalar<integer> *>
331 : m_map_term_with_unit_to_unitless_coefficient;
332 : /* e.g. {'N bytes': 12}. */
333 :
334 : std::map<const scalar<integer> *,
335 : const scalar<ConcreteValueType> *>
336 : m_map_unitless_term_to_coefficient_with_unit;
337 : /* e.g. {'N': 12 bytes}. */
338 :
339 : /* This is the " + CST" from above. */
340 : ConcreteValueType m_sum_of_concrete_values;
341 : };
342 :
343 : /* The second phase of canonicalization: arrange these into a vector
344 : of terms, dropping any terms with a factor == 0. */
345 28118 : struct creation_key
346 : {
347 : struct term
348 : {
349 : const scalar<ConcreteValueType> *m_with_unit;
350 : const scalar<integer> *m_unitless;
351 :
352 : bool operator< (const term &other) const;
353 : bool operator== (const term &other) const;
354 :
355 : complexity
356 : get_complexity () const;
357 :
358 : std::unique_ptr<text_art::tree_widget>
359 : make_dump_widget (symbolic::node_dump_state &nds) const;
360 : };
361 :
362 : creation_key (folding_helper &&fh);
363 :
364 : bool operator< (const creation_key &other) const;
365 :
366 : complexity
367 : get_complexity () const;
368 :
369 : const scalar<ConcreteValueType> *
370 : maybe_fold (scalar_manager<ConcreteValueType> &mgr) const;
371 :
372 : const scalar<ConcreteValueType> *
373 : maybe_fold_for_cvt (scalar_manager<ConcreteValueType> &mgr) const;
374 :
375 : void
376 : dump () const;
377 :
378 : std::unique_ptr<text_art::tree_widget>
379 : make_dump_widget (symbolic::node_dump_state &nds) const;
380 :
381 : std::vector<term> m_symbolic_terms;
382 : ConcreteValueType m_concrete_term;
383 : };
384 :
385 : sum (unsigned id,
386 : scalar_manager<ConcreteValueType> &mgr,
387 : const creation_key &k);
388 :
389 : const sum<ConcreteValueType> *
390 1761 : dyn_cast_sum () const final override { return this; }
391 :
392 : size_t
393 16239 : get_num_symbolic_addends () const
394 : {
395 16239 : return m_symbolic_addends.size ();
396 : }
397 :
398 : const scalar<ConcreteValueType> &
399 8288 : get_symbolic_addend (size_t idx) const { return *m_symbolic_addends[idx]; }
400 :
401 : const concrete_scalar<ConcreteValueType> *
402 8011 : get_any_concrete_addend () const
403 : {
404 8011 : return m_concrete_addend;
405 : }
406 :
407 : const ConcreteValueType *
408 573 : get_any_concrete_addend_value () const
409 : {
410 573 : if (m_concrete_addend)
411 570 : return &m_concrete_addend->get_concrete ();
412 : else
413 : return nullptr;
414 : }
415 :
416 : void
417 : accept_node_visitor (node_visitor &v) const final override;
418 :
419 : std::unique_ptr<json::object>
420 : to_json () const final override;
421 :
422 : void
423 : dump_inline_to_pp (pretty_printer *pp, enum units::role) const final override;
424 :
425 : std::unique_ptr<diagnostics::markup::node>
426 : make_markup_node (markup_context &markup_ctxt) const final override;
427 :
428 : private:
429 : void
430 : print_dump_widget_label_for_scalar (pretty_printer *pp) const final override;
431 :
432 : void
433 : add_dump_widget_children (text_art::tree_widget &,
434 : node_dump_state &nds) const final override;
435 :
436 : std::vector<const scalar<ConcreteValueType> *> m_symbolic_addends;
437 :
438 : // non-null if nonzero; null if zero:
439 : const concrete_scalar<ConcreteValueType> *m_concrete_addend;
440 : };
441 :
442 : /* Symbolic value for a scalar (perhaps with a unit, perhaps dimensionless)
443 : scaled by a dimensionless factor.
444 :
445 : Consolidation/canonicalization:
446 : - X units * 0 --> 0 units
447 : - 0 units * Y --> 0 units
448 : - X units * 1 --> X units
449 : - we never have a product of two concrete_scalar (we fold this). */
450 :
451 : template<typename ConcreteValueType>
452 : class product : public scalar<ConcreteValueType>
453 : {
454 : public:
455 : struct key
456 : {
457 : bool operator< (const key &other) const;
458 :
459 : complexity
460 : get_complexity () const;
461 :
462 : void canonicalize ();
463 :
464 : const scalar<ConcreteValueType> *m_lhs;
465 : const scalar<integer> *m_rhs;
466 : };
467 :
468 : product (unsigned id,
469 : scalar_manager<ConcreteValueType> &mgr,
470 : const key &k);
471 :
472 : const product<ConcreteValueType> *
473 2197 : dyn_cast_product () const final override { return this; }
474 :
475 : const scalar<ConcreteValueType> &
476 5485 : get_lhs () const { return m_lhs; }
477 :
478 : const scalar<integer> &
479 5127 : get_rhs () const { return m_rhs; }
480 :
481 : void
482 : accept_node_visitor (node_visitor &v) const final override;
483 :
484 : std::unique_ptr<json::object>
485 : to_json () const final override;
486 :
487 : void
488 : dump_inline_to_pp (pretty_printer *pp, enum units::role) const final override;
489 :
490 : std::unique_ptr<diagnostics::markup::node>
491 : make_markup_node (markup_context &markup_ctxt) const final override;
492 :
493 : private:
494 : void
495 : print_dump_widget_label_for_scalar (pretty_printer *pp) const final override;
496 :
497 : void
498 : add_dump_widget_children (text_art::tree_widget &,
499 : node_dump_state &nds) const final override;
500 :
501 : const scalar<ConcreteValueType> &m_lhs;
502 : const scalar<integer> &m_rhs;
503 : };
504 :
505 : /* Concrete subclass of symbolic::scalar for a scalar derived from an svalue
506 : for when folding isn't possible.
507 :
508 : Consolidation/canonicalization:
509 : - if the svalue is a constant_svalue, it is not an INTEGER_CST (we
510 : fold such scalars to concrete_scalar). */
511 :
512 : template<typename ConcreteValueType>
513 : class scalar_from_svalue : public scalar<ConcreteValueType>
514 : {
515 : public:
516 : struct key
517 : {
518 : bool operator< (const key &other) const;
519 :
520 : complexity
521 : get_complexity () const;
522 :
523 : const svalue *m_sval;
524 : };
525 :
526 : scalar_from_svalue (unsigned id,
527 : scalar_manager<ConcreteValueType> &mgr,
528 : const key &k);
529 :
530 : const scalar_from_svalue<ConcreteValueType> *
531 18844 : dyn_cast_scalar_from_svalue () const final override { return this; }
532 :
533 : const svalue &
534 44308 : get_svalue () const { return m_sval; }
535 :
536 : void
537 : accept_node_visitor (node_visitor &v) const final override;
538 :
539 : std::unique_ptr<json::object>
540 : to_json () const final override;
541 :
542 : void
543 : dump_inline_to_pp (pretty_printer *pp, enum units::role) const final override;
544 :
545 : std::unique_ptr<diagnostics::markup::node>
546 : make_markup_node (markup_context &markup_ctxt) const final override;
547 :
548 : private:
549 : void
550 : print_dump_widget_label_for_scalar (pretty_printer *pp) const final override;
551 :
552 : void
553 : add_dump_widget_children (text_art::tree_widget &,
554 : node_dump_state &nds) const final override;
555 :
556 : const svalue &m_sval;
557 : };
558 :
559 : /* A named scalar for use in unit tests: cannot be folded. */
560 :
561 : #if CHECKING_P
562 :
563 : template<typename ConcreteValueType>
564 : class named_test_scalar : public scalar<ConcreteValueType>
565 : {
566 : public:
567 256 : named_test_scalar (scalar_manager<ConcreteValueType> &mgr,
568 : std::string name)
569 256 : : scalar<ConcreteValueType> (complexity (1, 1),
570 : mgr.alloc_node_id (),
571 : mgr,
572 : scalar<ConcreteValueType>::kind::named_test),
573 256 : m_name (std::move (name))
574 : {
575 256 : }
576 :
577 : void
578 : accept_node_visitor (node_visitor &v) const final override;
579 :
580 : std::unique_ptr<json::object>
581 : to_json () const final override;
582 :
583 : void
584 : dump_inline_to_pp (pretty_printer *pp, enum units::role) const final override;
585 :
586 : std::unique_ptr<diagnostics::markup::node>
587 : make_markup_node (markup_context &markup_ctxt) const final override;
588 :
589 : private:
590 : void
591 : print_dump_widget_label_for_scalar (pretty_printer *pp) const final override;
592 :
593 : void
594 : add_dump_widget_children (text_art::tree_widget &,
595 : node_dump_state &nds) const final override;
596 :
597 : std::string m_name;
598 : };
599 :
600 : #endif /* #if CHECKING_P */
601 :
602 : /* Concrete subclass of symbolic::scalar for when we can't fold
603 : a conversion from bytes to bits.
604 :
605 : Consolidation/canonicalization:
606 : - m_bytes is not a concrete_scalar.
607 : - m_bytes is not is_unknown_p (). */
608 :
609 : class bits_from_bytes_scalar : public symbolic_bit_size
610 : {
611 : public:
612 : struct key
613 : {
614 : bool operator< (const key &other) const;
615 :
616 : complexity
617 : get_complexity () const;
618 :
619 : const symbolic_byte_size *m_bytes;
620 : };
621 :
622 : bits_from_bytes_scalar (unsigned id,
623 : scalar_manager<concrete_bit_size> &mgr,
624 : const key &k);
625 :
626 : const bits_from_bytes_scalar *
627 28419 : dyn_cast_bits_from_bytes_scalar () const final override { return this; }
628 :
629 : void
630 : accept_node_visitor (node_visitor &v) const final override;
631 :
632 : std::unique_ptr<json::object>
633 : to_json () const final override;
634 :
635 : void
636 : dump_inline_to_pp (pretty_printer *pp, enum units::role) const final override;
637 :
638 : std::unique_ptr<diagnostics::markup::node>
639 : make_markup_node (markup_context &markup_ctxt) const final override;
640 :
641 : const symbolic_byte_size &
642 25757 : get_bytes () const { return m_bytes; }
643 :
644 : private:
645 : void
646 : print_dump_widget_label_for_scalar (pretty_printer *pp) const final override;
647 :
648 : void
649 : add_dump_widget_children (text_art::tree_widget &,
650 : node_dump_state &nds) const final override;
651 :
652 : const symbolic_byte_size &m_bytes;
653 : };
654 :
655 : /* A class with responsibility for allocating/consolidating
656 : scalar<ConcreteValueType> instances. */
657 :
658 : template<typename ConcreteValueType>
659 : class scalar_manager
660 : {
661 : public:
662 13227 : scalar_manager (node_manager &node_mgr)
663 13227 : : m_node_mgr (node_mgr)
664 : {
665 13227 : }
666 :
667 : /* Make sure we don't accidentally copy these. */
668 : scalar_manager (const scalar_manager &) = delete;
669 :
670 : const concrete_scalar<ConcreteValueType> &
671 : get_concrete (const ConcreteValueType &value);
672 :
673 : const scalar<ConcreteValueType> &
674 : get_sum (std::vector<const scalar<ConcreteValueType> *> addends);
675 :
676 : const scalar<ConcreteValueType> &
677 : get_difference (const scalar<ConcreteValueType> &lhs,
678 : const scalar<ConcreteValueType> &rhs);
679 :
680 : const scalar<ConcreteValueType> &
681 : get_negation (const scalar<ConcreteValueType> &s);
682 :
683 : const scalar<ConcreteValueType> &
684 : get_product (const scalar<ConcreteValueType> &lhs,
685 : const scalar<integer> &factor);
686 :
687 : const scalar<ConcreteValueType> &
688 : get_scalar_from_svalue (const svalue &sval);
689 :
690 : const symbolic_bit_size &
691 : get_bits_from_bytes (const symbolic_byte_size &bytes);
692 :
693 : const scalar<ConcreteValueType> &
694 : get_unknown ();
695 :
696 : #if CHECKING_P
697 : const scalar<ConcreteValueType> &
698 : get_named_test_scalar (std::string name);
699 : #endif
700 :
701 : unsigned
702 108438 : alloc_node_id () { return m_node_mgr.alloc_node_id (); }
703 :
704 : node_manager &
705 1094405 : get_node_manager () { return m_node_mgr; }
706 :
707 : scalar_manager<integer> &
708 : get_unitless_manager ();
709 :
710 : private:
711 : /* Explicitly adding units to a unitless value. */
712 : const scalar<ConcreteValueType> *
713 : maybe_from_unitless (const ConcreteValueType &concrete_lhs,
714 : const scalar<integer> &unitless_rhs);
715 :
716 : const scalar<ConcreteValueType> *
717 : maybe_from_unitless_for_unit (const ConcreteValueType &concrete_lhs,
718 : const scalar<integer> &unitless_rhs);
719 :
720 : using sum_memoization_key = typename sum<ConcreteValueType>::memoization_key;
721 : const scalar<ConcreteValueType> &
722 : get_sum_unmemoized (const sum_memoization_key &memo_key);
723 :
724 : const scalar<ConcreteValueType> *
725 : maybe_fold_product (const typename product<ConcreteValueType>::key &k);
726 :
727 : const scalar<ConcreteValueType> *
728 : maybe_fold_scalar_from_svalue (const typename scalar_from_svalue<ConcreteValueType>::key &k);
729 :
730 : const symbolic_bit_size *
731 : maybe_fold_bits_from_bytes (const symbolic_byte_size &bytes);
732 :
733 : node_manager &m_node_mgr;
734 :
735 : std::map<ConcreteValueType,
736 : std::unique_ptr<const concrete_scalar<ConcreteValueType>>> m_concrete_map;
737 :
738 : std::map<typename sum<ConcreteValueType>::memoization_key,
739 : const scalar<ConcreteValueType> *> m_memoized_sums;
740 : std::map<typename sum<ConcreteValueType>::creation_key,
741 : std::unique_ptr<scalar<ConcreteValueType>>> m_sum_map;
742 : std::map<typename product<ConcreteValueType>::key,
743 : std::unique_ptr<const product<ConcreteValueType>>> m_product_map;
744 : std::map<typename scalar_from_svalue<ConcreteValueType>::key,
745 : std::unique_ptr<const scalar_from_svalue<ConcreteValueType>>> m_scalar_from_svalue_map;
746 : std::map<typename bits_from_bytes_scalar::key,
747 : std::unique_ptr<bits_from_bytes_scalar>> m_bits_from_bytes_map;
748 :
749 : #if CHECKING_P
750 : std::vector<std::unique_ptr<named_test_scalar<ConcreteValueType>>>
751 : m_named_test_scalars;
752 : #endif
753 : };
754 :
755 : /* A bundle of scalar_manager<CVT> singletons for each of the various
756 : concrete value types we care about. */
757 :
758 : class scalar_managers
759 : {
760 : public:
761 4409 : scalar_managers (node_manager &node_mgr)
762 4409 : : m_bit_mgr (node_mgr),
763 4409 : m_byte_mgr (node_mgr),
764 4409 : m_unitless_mgr (node_mgr)
765 : {
766 4409 : }
767 :
768 : scalar_manager<integer_with_unit<units::bit>> &
769 12712839 : get_bits ()
770 : {
771 11465331 : return m_bit_mgr;
772 : }
773 :
774 : scalar_manager<integer_with_unit<units::byte>> &
775 1408801 : get_bytes ()
776 : {
777 1408801 : return m_byte_mgr;
778 : }
779 :
780 : scalar_manager<integer> &
781 80841 : get_unitless ()
782 : {
783 70932 : return m_unitless_mgr;
784 : }
785 :
786 : template <typename ConcreteValueType>
787 : scalar_manager<ConcreteValueType> &
788 : get_manager ();
789 :
790 : private:
791 : scalar_manager<integer_with_unit<units::bit>> m_bit_mgr;
792 : scalar_manager<integer_with_unit<units::byte>> m_byte_mgr;
793 : scalar_manager<integer> m_unitless_mgr;
794 : };
795 :
796 : template<>
797 : const symbolic_bit_size &
798 : scalar_manager<concrete_bit_size>::
799 : get_bits_from_bytes (const symbolic_byte_size &bytes);
800 :
801 : } // namespace ana::symbolic
802 :
803 : /* Overloaded operators. */
804 :
805 : /* Addition. */
806 :
807 : /* symbolic + symbolic -> symbolic. */
808 :
809 : template<typename ConcreteValueType>
810 : const symbolic::scalar<ConcreteValueType> &
811 215977 : operator+ (const symbolic::scalar<ConcreteValueType> &lhs,
812 : const symbolic::scalar<ConcreteValueType> &rhs)
813 : {
814 215977 : return lhs.get_mgr ().get_sum ({&lhs, &rhs});
815 : }
816 :
817 : /* symbolic + concrete -> symbolic. */
818 :
819 : template<typename ConcreteValueType>
820 : const symbolic::scalar<ConcreteValueType> &
821 84 : operator+ (const symbolic::scalar<ConcreteValueType> &lhs,
822 : const ConcreteValueType &rhs)
823 : {
824 84 : auto &mgr = lhs.get_mgr ();
825 84 : return mgr.get_sum ({&lhs, &mgr.get_concrete (rhs)});
826 : }
827 :
828 : /* Negation. */
829 :
830 : template<typename ConcreteValueType>
831 : const symbolic::scalar<ConcreteValueType> &
832 429 : operator- (const symbolic::scalar<ConcreteValueType> &i)
833 : {
834 429 : auto &mgr = i.get_mgr ();
835 429 : return mgr.get_negation (i);
836 : }
837 :
838 : /* Subtraction. */
839 :
840 : /* symbolic - symbolic -> symbolic. */
841 :
842 : template<typename ConcreteValueType>
843 : const symbolic::scalar<ConcreteValueType> &
844 21047 : operator- (const symbolic::scalar<ConcreteValueType> &lhs,
845 : const symbolic::scalar<ConcreteValueType> &rhs)
846 : {
847 21047 : return lhs.get_mgr ().get_difference (lhs, rhs);
848 : }
849 :
850 : /* symbolic - concrete -> symbolic. */
851 :
852 : template<typename ConcreteValueType>
853 : const symbolic::scalar<ConcreteValueType> &
854 1419 : operator- (const symbolic::scalar<ConcreteValueType> &lhs,
855 : const ConcreteValueType &rhs)
856 : {
857 1419 : auto &mgr = lhs.get_mgr ();
858 1419 : return mgr.get_difference (lhs, mgr.get_concrete (rhs));
859 : }
860 :
861 : /* symbolic * symbolic_integer -> symbolic. */
862 :
863 : template<typename ConcreteValueType>
864 : const symbolic::scalar<ConcreteValueType> &
865 32299 : operator* (const symbolic::scalar<ConcreteValueType> &lhs,
866 : const symbolic::scalar<integer> &rhs)
867 : {
868 32239 : return lhs.get_mgr ().get_product (lhs, rhs);
869 : }
870 :
871 : inline const symbolic_bit_size &
872 975794 : bits_from_bytes (const symbolic_byte_size &bytes)
873 : {
874 975794 : auto &bit_mgr
875 975794 : = bytes.get_mgr ().get_node_manager ().get_scalars ().get_bits ();
876 975794 : return bit_mgr.get_bits_from_bytes (bytes);
877 : }
878 :
879 : const symbolic_byte_size *
880 : maybe_bytes_from_bits (const symbolic_bit_size &bits);
881 :
882 : template <typename ConcreteValueType>
883 : inline bool
884 4398733 : concrete_from_symbolic (const symbolic::scalar<ConcreteValueType> &in,
885 : ConcreteValueType *out)
886 : {
887 4398733 : if (auto *concrete = in.dyn_cast_concrete_scalar ())
888 : {
889 4342610 : *out = concrete->get_concrete ();
890 4342610 : return true;
891 : }
892 : return false;
893 : }
894 :
895 : template <typename ConcreteValueType>
896 : inline const symbolic::scalar<ConcreteValueType> &
897 4605022 : symbolic_from_concrete (const ConcreteValueType &in,
898 : symbolic::scalar_manager<ConcreteValueType> &mgr)
899 : {
900 2440318 : return mgr.get_concrete (in);
901 : }
902 :
903 : } // namespace ana
904 :
905 : #endif /* GCC_ANALYZER_SYMBOLIC_SCALARS_H */
|