Line data Source code
1 : /* Symbolic vectors of bits e.g. "(buf_a[0-10) + buf_b[0-len) + (0b * 8))"
2 :
3 : Copyright (C) 2019-2026 Free Software Foundation, Inc.
4 : Contributed by David Malcolm <dmalcolm@redhat.com>.
5 :
6 : This file is part of GCC.
7 :
8 : GCC is free software; you can redistribute it and/or modify it
9 : under the terms of the GNU General Public License as published by
10 : the Free Software Foundation; either version 3, or (at your option)
11 : any later version.
12 :
13 : GCC is distributed in the hope that it will be useful, but
14 : WITHOUT ANY WARRANTY; without even the implied warranty of
15 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 : General Public License for more details.
17 :
18 : You should have received a copy of the GNU General Public License
19 : along with GCC; see the file COPYING3. If not see
20 : <http://www.gnu.org/licenses/>. */
21 :
22 : #ifndef GCC_ANALYZER_SYMBOLIC_BIT_VECTORS_H
23 : #define GCC_ANALYZER_SYMBOLIC_BIT_VECTORS_H
24 :
25 : #include "analyzer/integer-with-unit.h"
26 : #include "analyzer/concrete-ranges.h"
27 : #include "analyzer/symbolic-nodes.h"
28 : #include "analyzer/store.h"
29 : #include "analyzer/program-point.h"
30 : #include "analyzer/string-scan.h"
31 : #include "text-art/widget.h"
32 :
33 : namespace ana {
34 :
35 : /* A concrete-sized vector of tristate bits. */
36 :
37 : using concrete_tristate_vector = std::vector<tristate>;
38 :
39 : /* A bundle of options for use when printing hexdumps. */
40 :
41 48 : struct hexdump_options
42 : {
43 48 : hexdump_options ()
44 48 : : m_show_headings (false),
45 48 : m_show_binary (false),
46 48 : m_show_hex (true),
47 48 : m_show_ascii (true),
48 48 : m_bytes_per_line (4_bytes)
49 : {
50 : }
51 :
52 : bool m_show_headings;
53 : bool m_show_binary;
54 : bool m_show_hex;
55 : bool m_show_ascii;
56 : concrete_byte_size m_bytes_per_line;
57 : };
58 :
59 : namespace symbolic {
60 :
61 : class bit_vector_manager;
62 :
63 : /* An abstract base class representing the contents of a buffer of memory,
64 : where the size is a symbolic_bit_size.
65 :
66 : Consider:
67 :
68 : | size_t len_a = strlen (a));
69 : | size_t len_b = strlen (b));
70 : |
71 : | memcpy (buf, a, len_a);
72 : | memcpy (buf + len_a, b, len_b);
73 : | buf[len_a + len_b] = '\0';
74 :
75 : and then trying to analyze the contents of "buf". If len_a is known
76 : concretely as 10 bytes, but len_b is only known symbolically, the contents
77 : of buf might be represented as a symbolic::bit_vector as the
78 : concatenation of:
79 :
80 : - [buffer_a's bytes [0-10)],
81 : - [buffer_b's [bytes 0-'len_b')],
82 : - [8 zero bits])
83 :
84 : with size (11 + 'len_b') bytes (see selftest::test_example_strcat for
85 : a worked example similar to the above).
86 :
87 : bit_vectors can be concatenated, cropped, and repeated (with folding of
88 : various identities during these operations).
89 :
90 : The class hierarchy looks like this (using indentation to show
91 : inheritance, and with kinds shown for the concrete subclasses):
92 :
93 : symbolic::bit_vector
94 : concat_bit_vector (kind::concat): the concatenation of a vector of child bit_vectors
95 : conjured_bit_vector (kind::conjured): a bit vector arising from a stmt
96 : cropped_bit_vector (kind::cropped): another bit_vector, cropped and offset
97 : named_test_bit_vector (kind::named_test): an unfoldable bit_vector for use in selftests
98 : repeated_bit_vector (kind::repeated): repeating a bit_vector some number of times
99 : bit_vector_from_svalue (kind::svalue): the bit representation of an svalue on the target
100 : bit_vector_from_ubc (kind::from_ubc): a range of bits within an unfoldable_bit_contents
101 : uniform_bit_vector (abstract): a bit vector that is "the same bit" everywhere
102 : empty_bit_vector (kind::empty): the empty bit vector
103 : poisoned_bit_vector (kind::poisoned): unusable data
104 : tristate_bit_vector (kind::tristate): a range of bits that are all true/false/unknown. */
105 :
106 : class bit_vector : public symbolic::value_node
107 : {
108 : public:
109 : /* An enum for discriminating between the different concrete subclasses
110 : of symbolic bit_vector. */
111 : enum class kind
112 : {
113 : concat,
114 : conjured,
115 : cropped,
116 : empty,
117 : named_test,
118 : poisoned,
119 : repeated,
120 : svalue,
121 : from_ubc,
122 : tristate
123 : };
124 :
125 : bit_vector_manager &
126 21125 : get_bit_vector_manager () const { return m_bv_mgr; }
127 :
128 : const bit_vector *
129 33231568 : dyn_cast_bit_vector () const final override { return this; }
130 :
131 : void
132 : print_dump_widget_label (pretty_printer *pp) const final override;
133 :
134 : virtual void
135 : print_prefix_for_dump_widget_label (pretty_printer *pp) const = 0;
136 :
137 : virtual void
138 2356 : print_any_suffix_for_dump_widget_label (pretty_printer *) const {}
139 :
140 : const char *
141 19027 : get_any_dump_color () const override { return "bit_vector"; }
142 :
143 : virtual bool
144 : maybe_print_for_user (pretty_printer *pp,
145 : const region_model &model,
146 : const symbolic::node *outer_node = nullptr) const;
147 :
148 : virtual ~bit_vector () {}
149 :
150 : virtual enum kind get_kind () const = 0;
151 :
152 : virtual const concat_bit_vector *
153 2737401 : dyn_cast_concat_bit_vector () const { return nullptr; }
154 : virtual const conjured_bit_vector *
155 77 : dyn_cast_conjured_bit_vector () const { return nullptr; }
156 : virtual const cropped_bit_vector *
157 73420 : dyn_cast_cropped_bit_vector () const { return nullptr; }
158 : virtual const empty_bit_vector *
159 0 : dyn_cast_empty_bit_vector () const { return nullptr; }
160 : virtual const uniform_bit_vector *
161 7661 : dyn_cast_uniform_bit_vector () const { return nullptr; }
162 : virtual const poisoned_bit_vector *
163 130851 : dyn_cast_poisoned_bit_vector () const { return nullptr; }
164 : virtual const repeated_bit_vector *
165 133662 : dyn_cast_repeated_bit_vector () const { return nullptr; }
166 : virtual const bit_vector_from_svalue *
167 6758679 : dyn_cast_bit_vector_from_svalue () const { return nullptr; }
168 : virtual const bit_vector_from_ubc *
169 48767 : dyn_cast_bit_vector_from_ubc () const { return nullptr; }
170 : virtual const tristate_bit_vector *
171 608339 : dyn_cast_tristate_bit_vector () const { return nullptr; }
172 :
173 : bool
174 : operator== (const bit_vector &other) const
175 : {
176 : return this == &other;
177 : }
178 :
179 : const symbolic_bit_size &
180 10653054 : get_size () const { return m_size_in_bits; }
181 :
182 : const symbolic_byte_size *
183 : maybe_get_size_in_bytes () const;
184 :
185 : bool
186 : maybe_get_concrete_size_in_bits (concrete_bit_size *out) const;
187 :
188 : bool
189 : maybe_get_concrete_size_in_bytes (concrete_byte_size *out) const;
190 :
191 : virtual tristate
192 : get_tristate_at_offset (const symbolic_bit_offset &bit) const;
193 :
194 : virtual string_scan
195 : scan_for_first_zero_byte (concrete_byte_offset start_byte_offset) const = 0;
196 :
197 : void
198 : hexdump_to_pp (pretty_printer *,
199 : const hexdump_options &hexdump_opts) const;
200 :
201 : void
202 : hexdump (const hexdump_options &hexdump_opts) const;
203 :
204 : void
205 : hexdump () const;
206 :
207 : virtual bool
208 : conjured_p () const;
209 :
210 : /* Convenience member functions (implemented using the bit_vector_manager). */
211 :
212 : tristate
213 : get_tristate_at_offset (const concrete_bit_offset &bit) const;
214 :
215 : const bit_vector &
216 : get_cropped_bits (const symbolic_bit_range &bits_to_use) const;
217 :
218 : const bit_vector &
219 : get_cropped_bits (const concrete_bit_range &bits_to_use) const;
220 :
221 : const bit_vector &
222 : get_cropped_bytes (const symbolic_byte_range &bytes_to_use) const;
223 :
224 : const bit_vector &
225 : get_cropped_bytes (const concrete_byte_range &bytes_to_use) const;
226 :
227 : const bit_vector &
228 : get_prefix (const symbolic_bit_size &size) const;
229 :
230 : const bit_vector &
231 : get_prefix (const concrete_bit_size &size) const;
232 :
233 : const bit_vector &
234 8 : get_prefix (const symbolic_byte_size &size) const
235 : {
236 8 : return get_prefix (bits_from_bytes (size));
237 : }
238 :
239 : const bit_vector &
240 36 : get_prefix (const concrete_byte_size &size) const
241 : {
242 36 : return get_prefix (bits_from_bytes (size));
243 : }
244 :
245 : const bit_vector &
246 : get_suffix (const symbolic_bit_size &size) const;
247 :
248 : const bit_vector &
249 : get_suffix (const concrete_bit_size &size) const;
250 :
251 : const bit_vector &
252 : get_suffix (const symbolic_byte_size &size) const
253 : {
254 : return get_suffix (bits_from_bytes (size));
255 : }
256 :
257 : const bit_vector &
258 28 : get_suffix (const concrete_byte_size &size) const
259 : {
260 28 : return get_suffix (bits_from_bytes (size));
261 : }
262 :
263 : const bit_vector &
264 : get_byte_at_offset (const symbolic_byte_offset &byte_offset) const;
265 :
266 : const bit_vector &
267 : get_byte_at_offset (const concrete_byte_offset &byte_offset) const;
268 :
269 : virtual const bit_vector *
270 : maybe_fold_crop (const symbolic_bit_range &inner_bits_to_use) const;
271 :
272 : bool
273 : maybe_as_uint8 (uint8_t *out) const;
274 :
275 : static const bit_vector *
276 : can_merge_p (const bit_vector &bv_a,
277 : const bit_vector &bv_b,
278 : tree type,
279 : model_merger *merger);
280 :
281 : bool
282 : maybe_get_irange_bitmask (irange_bitmask *out) const;
283 :
284 : bool derived_from_initial_value_p () const;
285 :
286 : protected:
287 : bit_vector (bit_vector_manager &mgr,
288 : complexity c,
289 : const symbolic_bit_size &size_in_bits);
290 :
291 : std::unique_ptr<json::object>
292 : make_json_obj (const char *type_name) const;
293 :
294 : bit_vector_manager &m_bv_mgr;
295 : const symbolic_bit_size &m_size_in_bits;
296 : };
297 :
298 : /* A sequence of bit_vectors concatenated together.
299 :
300 : Consolidation/canonicalization:
301 : - we must have at least two child bit_vectors
302 : - all child bit_vectors must have non-zero size
303 : - no nesting: children must not be concat_bit_vector instances
304 : - consecutive children must not:
305 : - be the same bit_vector
306 : - be uniform_bit_vectors with the same underlying bit
307 : - be repeated_bit_vectors of the same underlying
308 : bit vector
309 : - be a bit_vector and a repeated_bit_vector of that
310 : bit_vector (in either order)
311 : - be bit_vectors taken from the same UBC at
312 : consecutive bit ranges. */
313 :
314 : class concat_bit_vector : public bit_vector
315 : {
316 : public:
317 49191 : struct key
318 : {
319 36864 : key (std::vector<const bit_vector *> bit_vectors)
320 36864 : : m_bit_vectors (std::move (bit_vectors))
321 : {
322 : }
323 :
324 : bool operator< (const key &other) const;
325 :
326 : complexity
327 : get_complexity () const;
328 :
329 : const symbolic_bit_size &
330 : get_size (scalar_manager<concrete_bit_size> &bit_mgr) const;
331 :
332 : std::vector<const bit_vector *> m_bit_vectors;
333 : };
334 :
335 4303 : enum kind get_kind () const final override
336 : {
337 4303 : return kind::concat;
338 : }
339 :
340 : const concat_bit_vector *
341 35852 : dyn_cast_concat_bit_vector () const final override { return this; }
342 :
343 : tristate
344 : get_tristate_at_offset (const symbolic_bit_offset &bit) const final override;
345 :
346 : string_scan
347 : scan_for_first_zero_byte (concrete_byte_offset start_byte_offset)
348 : const final override;
349 :
350 : std::vector<const bit_vector *>::const_iterator
351 3789 : begin () const { return m_bit_vectors.begin (); }
352 : std::vector<const bit_vector *>::const_iterator
353 3789 : end () const { return m_bit_vectors.end (); }
354 :
355 : concat_bit_vector (bit_vector_manager &mgr,
356 : const key &k);
357 :
358 : bool implicitly_live_p (symbolic::liveness_context &) const final override;
359 :
360 : const bit_vector *
361 : maybe_fold_crop (const symbolic_bit_range &inner_bits_to_use)
362 : const final override;
363 :
364 : std::unique_ptr<json::object>
365 : to_json () const final override;
366 :
367 : std::unique_ptr<diagnostics::markup::node>
368 : make_markup_node (markup_context &markup_ctxt) const final override;
369 :
370 : iter_result
371 : for_each_svalue (iter_result (*cb) (const svalue &sval,
372 : void *user_data),
373 : void *user_data) const final override;
374 : private:
375 : void
376 : print_prefix_for_dump_widget_label (pretty_printer *pp) const final override;
377 :
378 : void
379 : add_dump_widget_children (text_art::tree_widget &,
380 : node_dump_state &nds) const final override;
381 :
382 : void
383 : accept_node_visitor (node_visitor &v) const final override;
384 :
385 : std::vector<const bit_vector *> m_bit_vectors;
386 : };
387 :
388 : /* A defined bit_vector arising from a statement, where we want to identify a
389 : particular unknown bundle of bits, so that the value can have sm-state.
390 :
391 : Comparisons of variables that share the same conjured_bit_vector are known
392 : to be equal, even if we don't know what the value is.
393 :
394 : For example, this is used for the values of regions of known size
395 : that may have been touched when calling an unknown function.
396 :
397 : The bit_vector captures a region as well as a stmt in order to avoid falsely
398 : aliasing the various bit vectors that could arise in one statement. For
399 : example, after:
400 : unknown_fn (&a, &b);
401 : we want nodes to clobber a and b with, but we don't want to use the
402 : same node, or it would falsely implicitly assume that a == b. */
403 :
404 : class conjured_bit_vector : public bit_vector
405 : {
406 : public:
407 : struct key
408 : {
409 26132 : key (const gimple *stmt,
410 : const region *id_reg,
411 : unsigned idx)
412 26132 : : m_stmt (stmt), m_id_reg (id_reg), m_idx (idx)
413 : {
414 : }
415 :
416 : bool operator< (const key &other) const;
417 :
418 : complexity
419 : get_complexity () const;
420 :
421 : const symbolic_bit_size &
422 : get_size (scalar_manager<concrete_bit_size> &bit_mgr) const;
423 :
424 : const gimple *m_stmt;
425 : const region *m_id_reg;
426 : unsigned m_idx;
427 : };
428 :
429 1870138 : enum kind get_kind () const final override
430 : {
431 1870138 : return kind::conjured;
432 : }
433 :
434 : const conjured_bit_vector *
435 65 : dyn_cast_conjured_bit_vector () const final override { return this; }
436 :
437 : tristate
438 : get_tristate_at_offset (const symbolic_bit_offset &bit) const final override;
439 :
440 : string_scan
441 : scan_for_first_zero_byte (concrete_byte_offset start_byte_offset)
442 : const final override;
443 :
444 : bool
445 22046 : conjured_p () const final override
446 : {
447 22046 : return true;
448 : }
449 :
450 : conjured_bit_vector (bit_vector_manager &mgr,
451 : const key &k);
452 :
453 : std::unique_ptr<json::object>
454 : to_json () const final override;
455 :
456 : std::unique_ptr<diagnostics::markup::node>
457 : make_markup_node (markup_context &markup_ctxt) const final override;
458 :
459 : iter_result
460 : for_each_svalue (iter_result (*cb) (const svalue &sval,
461 : void *user_data),
462 : void *user_data) const final override;
463 :
464 62 : const gimple *get_stmt () const { return m_stmt; }
465 69 : const region *get_id_reg () const { return m_id_reg; }
466 62 : unsigned get_idx () const { return m_idx; }
467 :
468 : private:
469 : void
470 : print_prefix_for_dump_widget_label (pretty_printer *pp) const final override;
471 :
472 : void
473 : add_dump_widget_children (text_art::tree_widget &,
474 : node_dump_state &nds) const final override;
475 :
476 : void
477 : accept_node_visitor (node_visitor &v) const final override;
478 :
479 : const gimple *m_stmt;
480 : const region *m_id_reg;
481 : unsigned m_idx;
482 : };
483 :
484 : /* A cropping of another bit_vector.
485 : Visually, the cropped bit_vector is within the uncropped bit_vector:
486 : .
487 : . uncropped_bit_vector:
488 : . +--------------------------+
489 : . | |
490 : . +--------------------------+
491 : .
492 : . +----+------------------+--+
493 : . | |cropped_bit_vector| |
494 : . +----+------------------+--+
495 : . ^
496 : . |
497 : . crop_start_bit_offset (relative to uncropped)
498 : .
499 : but in terms of the object hierarchy the uncropped bit_vector is a child
500 : of the cropped bit_vector.
501 :
502 : The bounds can be concrete or symbolic.
503 :
504 : Consolidation/canonicalization:
505 : - no nesting: children must not be concat_bit_vector instances
506 : - we never have a cropped_bit_vector of a uniform_bit_vector, as
507 : these can be expressed simply as a uniform_bit_vector of the appropriate
508 : subclass of smaller size. */
509 :
510 : class cropped_bit_vector : public bit_vector
511 : {
512 : public:
513 : struct key
514 : {
515 87570 : key (const bit_vector *uncropped_bv,
516 : symbolic_bit_range bits_to_use)
517 87570 : : m_uncropped_bv (uncropped_bv),
518 87570 : m_bits_to_use (bits_to_use)
519 : {
520 : }
521 :
522 : bool operator< (const key &other) const;
523 :
524 : const symbolic_bit_size &
525 7367 : get_size () const
526 : {
527 7367 : return m_bits_to_use.get_size ();
528 : }
529 :
530 : const bit_vector *m_uncropped_bv;
531 : symbolic_bit_range m_bits_to_use;
532 : };
533 :
534 53867 : enum kind get_kind () const final override
535 : {
536 53867 : return kind::cropped;
537 : }
538 :
539 : const cropped_bit_vector *
540 463 : dyn_cast_cropped_bit_vector () const final override { return this; }
541 :
542 : tristate
543 : get_tristate_at_offset (const symbolic_bit_offset &bit) const final override;
544 :
545 : string_scan
546 : scan_for_first_zero_byte (concrete_byte_offset start_byte_offset)
547 : const final override;
548 :
549 : cropped_bit_vector (bit_vector_manager &mgr,
550 : const key &k);
551 :
552 : const bit_vector &
553 3730 : get_uncropped_bit_vector () const { return m_uncropped_bv; }
554 :
555 : /* Get bit range of this bit_vector relative to the uncropped_bit_vector. */
556 : symbolic_bit_range
557 2456 : get_uncropped_bits_to_use () const
558 : {
559 2439 : return symbolic_bit_range (m_crop_start_bit_offset, get_size ());
560 : }
561 :
562 : /* Try to get byte range of this bit_vector relative to the
563 : uncropped_bit_vector. */
564 : bool
565 : get_uncropped_bytes_to_use (symbolic_byte_range *out) const
566 : {
567 : return maybe_bytes_from_bits (get_uncropped_bits_to_use (), out);
568 : }
569 :
570 : bool
571 : implicitly_live_p (symbolic::liveness_context &) const final override;
572 :
573 : const bit_vector *
574 : maybe_fold_crop (const symbolic_bit_range &inner_bits_to_use)
575 : const final override;
576 :
577 : std::unique_ptr<json::object>
578 : to_json () const final override;
579 :
580 : std::unique_ptr<diagnostics::markup::node>
581 : make_markup_node (markup_context &markup_ctxt) const final override;
582 :
583 : iter_result
584 : for_each_svalue (iter_result (*cb) (const svalue &sval,
585 : void *user_data),
586 : void *user_data) const final override;
587 :
588 : private:
589 : void
590 : print_prefix_for_dump_widget_label (pretty_printer *pp) const final override;
591 :
592 : void
593 : print_any_suffix_for_dump_widget_label (pretty_printer *pp)
594 : const final override;
595 :
596 : void
597 : add_dump_widget_children (text_art::tree_widget &,
598 : node_dump_state &nds) const final override;
599 :
600 : void
601 : accept_node_visitor (node_visitor &v) const final override;
602 :
603 : const bit_vector &m_uncropped_bv;
604 : const symbolic_bit_offset &m_crop_start_bit_offset;
605 : // relative to the uncropped bit vector
606 : };
607 :
608 : /* An unfoldable bit_vector with a name, for use in selftests. */
609 :
610 : #if CHECKING_P
611 :
612 : class named_test_bit_vector : public bit_vector
613 : {
614 : public:
615 80 : enum kind get_kind () const final override
616 : {
617 80 : return kind::named_test;
618 : }
619 :
620 : tristate
621 : get_tristate_at_offset (const symbolic_bit_offset &bit) const override;
622 :
623 : string_scan
624 : scan_for_first_zero_byte (concrete_byte_offset start_byte_offset)
625 : const override;
626 :
627 : named_test_bit_vector (bit_vector_manager &mgr,
628 : const symbolic_bit_size &size_in_bits,
629 : std::string label);
630 :
631 : std::unique_ptr<json::object>
632 : to_json () const final override;
633 :
634 : std::unique_ptr<diagnostics::markup::node>
635 : make_markup_node (markup_context &markup_ctxt) const final override;
636 :
637 : iter_result
638 : for_each_svalue (iter_result (*cb) (const svalue &sval,
639 : void *user_data),
640 : void *user_data) const final override;
641 : private:
642 : void
643 : print_prefix_for_dump_widget_label (pretty_printer *pp) const final override;
644 :
645 : void
646 : print_any_suffix_for_dump_widget_label (pretty_printer *pp)
647 : const final override;
648 :
649 : void
650 : add_dump_widget_children (text_art::tree_widget &,
651 : node_dump_state &nds) const final override;
652 :
653 : void
654 : accept_node_visitor (node_visitor &v) const final override;
655 :
656 : std::string m_label;
657 : };
658 :
659 : #endif /* #if CHECKING_P */
660 :
661 : /* An abstract subclass for bit_vector subclasses that are the same
662 : at every bit offset (and for which we can thus simplify away "crop",
663 : "concatentate", and "repeat" operations by using a like-kinded
664 : instance of the appropriate size). */
665 :
666 : class uniform_bit_vector : public bit_vector
667 : {
668 : protected:
669 36286 : uniform_bit_vector (bit_vector_manager &mgr,
670 : complexity c,
671 : const symbolic_bit_size &size_in_bits)
672 36286 : : bit_vector (mgr, c, size_in_bits)
673 : {
674 : }
675 : };
676 :
677 : /* The empty bit vector.
678 :
679 : This is a uniform_bit_vector because, having no elements, all its
680 : elements are trivially equal. This allows more canonicalization
681 : rules to be expresed purely in terms of uniform_bit_vector.
682 :
683 : Consolidation/canonicalization:
684 : - The only bit_vector with zero size should be the singleton
685 : empty_bit_vector; instances of all other subclasses should have
686 : non-zero size. */
687 :
688 : class empty_bit_vector : public uniform_bit_vector
689 : {
690 : public:
691 0 : enum kind get_kind () const final override
692 : {
693 0 : return kind::empty;
694 : }
695 :
696 : const empty_bit_vector *
697 0 : dyn_cast_empty_bit_vector () const final override { return this; }
698 :
699 : tristate
700 : get_tristate_at_offset (const symbolic_bit_offset &bit) const final override;
701 :
702 : string_scan
703 : scan_for_first_zero_byte (concrete_byte_offset start_byte_offset)
704 : const final override;
705 :
706 : empty_bit_vector (bit_vector_manager &mgr);
707 :
708 : std::unique_ptr<json::object>
709 : to_json () const final override;
710 :
711 : std::unique_ptr<diagnostics::markup::node>
712 : make_markup_node (markup_context &markup_ctxt) const final override;
713 :
714 : iter_result
715 : for_each_svalue (iter_result (*cb) (const svalue &sval,
716 : void *user_data),
717 : void *user_data) const final override;
718 : private:
719 : void
720 : print_prefix_for_dump_widget_label (pretty_printer *pp) const final override;
721 :
722 : void
723 : add_dump_widget_children (text_art::tree_widget &,
724 : node_dump_state &nds) const final override;
725 :
726 : void
727 : accept_node_visitor (node_visitor &v) const final override;
728 : };
729 :
730 : /* A run of bits that are unusable (e.g. uninitialized data). */
731 :
732 : class poisoned_bit_vector : public uniform_bit_vector
733 : {
734 : public:
735 : struct key
736 : {
737 1664101 : key (const symbolic_bit_size &size_in_bits,
738 : enum poison_kind kind)
739 1664101 : : m_size_in_bits (size_in_bits),
740 1664101 : m_poison_kind (kind)
741 : {
742 : }
743 :
744 : bool operator< (const key &other) const;
745 :
746 : const symbolic_bit_size &m_size_in_bits;
747 : enum poison_kind m_poison_kind;
748 : };
749 :
750 20231 : enum kind get_kind () const final override
751 : {
752 20231 : return kind::poisoned;
753 : }
754 :
755 : const poisoned_bit_vector *
756 6680 : dyn_cast_poisoned_bit_vector () const final override { return this; }
757 :
758 : tristate
759 : get_tristate_at_offset (const symbolic_bit_offset &bit) const final override;
760 :
761 : string_scan
762 : scan_for_first_zero_byte (concrete_byte_offset start_byte_offset)
763 : const final override;
764 :
765 : poisoned_bit_vector (bit_vector_manager &mgr,
766 : const key &k);
767 :
768 56915 : enum poison_kind get_poison_kind () const { return m_poison_kind; }
769 :
770 : const bit_vector *
771 : maybe_fold_crop (const symbolic_bit_range &inner_bits_to_use)
772 : const final override;
773 :
774 : std::unique_ptr<json::object>
775 : to_json () const final override;
776 :
777 : std::unique_ptr<diagnostics::markup::node>
778 : make_markup_node (markup_context &markup_ctxt) const final override;
779 :
780 : iter_result
781 : for_each_svalue (iter_result (*cb) (const svalue &sval,
782 : void *user_data),
783 : void *user_data) const final override;
784 : private:
785 : void
786 : print_prefix_for_dump_widget_label (pretty_printer *pp) const final override;
787 :
788 : void
789 : print_any_suffix_for_dump_widget_label (pretty_printer *pp)
790 : const final override;
791 :
792 : void
793 : add_dump_widget_children (text_art::tree_widget &,
794 : node_dump_state &nds) const final override;
795 :
796 : void
797 : accept_node_visitor (node_visitor &v) const final override;
798 :
799 : enum poison_kind m_poison_kind;
800 : };
801 :
802 : /* Concrete bit_vector subclass: N repeated copies of an underlying
803 : bit vector, where N could be symbolic.
804 :
805 : Consolidation/canonicalization:
806 : - we never have a concrete repeat count of zero or one, as these are
807 : trivially foldable to empty/inner_bv
808 : - no nesting: we never have a repeated_bit_vector of a inner_bv
809 : - we never have a repeated_bit_vector of a uniform_bit_vector, as
810 : these can be expressed simply as a uniform_bit_vector (of the appropriate
811 : subclass) of larger size. */
812 :
813 : class repeated_bit_vector : public bit_vector
814 : {
815 : public:
816 : struct key
817 : {
818 637 : key (const bit_vector *inner_bv,
819 : const symbolic_integer *repeat_count)
820 637 : : m_inner_bv (inner_bv),
821 637 : m_repeat_count (repeat_count)
822 : {
823 : }
824 :
825 : bool operator< (const key &other) const;
826 :
827 : const symbolic_bit_size &
828 294 : get_size () const
829 : {
830 294 : return m_inner_bv->get_size () * (*m_repeat_count);
831 : }
832 :
833 : const bit_vector *m_inner_bv;
834 : const symbolic_integer *m_repeat_count;
835 : };
836 :
837 115833 : enum kind get_kind () const final override
838 : {
839 115833 : return kind::repeated;
840 : }
841 :
842 : const repeated_bit_vector *
843 2771 : dyn_cast_repeated_bit_vector () const final override { return this; }
844 :
845 : string_scan
846 : scan_for_first_zero_byte (concrete_byte_offset start_byte_offset)
847 : const final override;
848 :
849 : repeated_bit_vector (bit_vector_manager &mgr,
850 : const key &k);
851 :
852 : const bit_vector &
853 2645 : get_inner_bit_vector () const { return m_inner_bv; }
854 :
855 : const symbolic_integer &
856 36 : get_repeat_count () const { return m_repeat_count; }
857 :
858 : const bit_vector *
859 : maybe_fold_crop (const symbolic_bit_range &inner_bits_to_use)
860 : const final override;
861 :
862 : std::unique_ptr<json::object>
863 : to_json () const final override;
864 :
865 : std::unique_ptr<diagnostics::markup::node>
866 : make_markup_node (markup_context &markup_ctxt) const final override;
867 :
868 : iter_result
869 : for_each_svalue (iter_result (*cb) (const svalue &sval,
870 : void *user_data),
871 : void *user_data) const final override;
872 : private:
873 : void
874 : print_prefix_for_dump_widget_label (pretty_printer *pp) const final override;
875 :
876 : void
877 : add_dump_widget_children (text_art::tree_widget &,
878 : node_dump_state &nds) const final override;
879 :
880 : void
881 : accept_node_visitor (node_visitor &v) const final override;
882 :
883 : const bit_vector &m_inner_bv;
884 : const symbolic_integer &m_repeat_count;
885 : };
886 :
887 : /* Concrete bit_vector subclass: the bit representation of an svalue
888 : on the target.
889 :
890 : Consolidation/canonicalization:
891 : - no nesting: inner svalue can't be a svalue_from_bit_vector
892 : - the inner svalue must not have zero size (or we'd have an empty_bit_vector)
893 : - no all zeros or all ones (we fold to tristate_bit_vector for this)
894 : - all other concrete 8-bit vectors are canonicalized to m_cached_bytes,
895 : each of which is the bit_vector_from_svalue of an unsigned char of the
896 : relevant value. */
897 :
898 : class bit_vector_from_svalue : public bit_vector
899 : {
900 : public:
901 : struct key
902 : {
903 1466879 : key (const svalue *sval)
904 1466879 : : m_sval (sval)
905 : {
906 : }
907 :
908 : bool operator< (const key &other) const;
909 :
910 : const symbolic_bit_size &
911 : get_size (scalar_manager<concrete_bit_size> &bit_mgr) const;
912 :
913 : const svalue *m_sval;
914 : };
915 :
916 5128049 : enum kind get_kind () const final override
917 : {
918 5128049 : return kind::svalue;
919 : }
920 :
921 : const bit_vector_from_svalue *
922 6949938 : dyn_cast_bit_vector_from_svalue () const final override { return this; }
923 :
924 : bool
925 : maybe_print_for_user (pretty_printer *pp,
926 : const region_model &model,
927 : const symbolic::node *outer_node = nullptr)
928 : const final override;
929 :
930 : tristate
931 : get_tristate_at_offset (const symbolic_bit_offset &bit) const final override;
932 :
933 : string_scan
934 : scan_for_first_zero_byte (concrete_byte_offset start_byte_offset)
935 : const final override;
936 :
937 : bit_vector_from_svalue (bit_vector_manager &mgr,
938 : const key &k);
939 :
940 6988870 : const svalue &get_svalue () const { return m_sval; }
941 :
942 : const bit_vector *
943 : maybe_fold_crop (const symbolic_bit_range &inner_bits_to_use)
944 : const final override;
945 :
946 : bool implicitly_live_p (symbolic::liveness_context &) const final override;
947 :
948 : std::unique_ptr<json::object>
949 : to_json () const final override;
950 :
951 : std::unique_ptr<diagnostics::markup::node>
952 : make_markup_node (markup_context &markup_ctxt) const final override;
953 :
954 : iter_result
955 : for_each_svalue (iter_result (*cb) (const svalue &sval,
956 : void *user_data),
957 : void *user_data) const final override;
958 : private:
959 : void
960 : print_prefix_for_dump_widget_label (pretty_printer *pp) const final override;
961 :
962 : void
963 : add_dump_widget_children (text_art::tree_widget &,
964 : node_dump_state &nds) const final override;
965 :
966 : void
967 : accept_node_visitor (node_visitor &v) const final override;
968 :
969 : const bit_vector *
970 : maybe_fold_crop_from_cst (const concrete_bit_range &inner_bits_to_use) const;
971 :
972 : const bit_vector *
973 : maybe_fold_crop_from_bitmask (const concrete_bit_range &inner_bits_to_use)
974 : const;
975 :
976 : const bit_vector *
977 : maybe_fold_crop_from_initial_bits (const concrete_bit_range &inner_bits_to_use)
978 : const;
979 :
980 : const svalue &m_sval;
981 : };
982 :
983 : /* Concrete bit_vector subclass: a range of bits from an unfoldable_bit_contents
984 : instance. These are managed by their unfoldable_bit_contents instance.
985 :
986 : Consolidation/canonicalization:
987 : - TODO. */
988 :
989 : class bit_vector_from_ubc : public bit_vector
990 : {
991 : public:
992 14413466 : enum kind get_kind () const final override
993 : {
994 14413466 : return kind::from_ubc;
995 : }
996 :
997 : const bit_vector_from_ubc *
998 1610 : dyn_cast_bit_vector_from_ubc () const final override { return this; }
999 :
1000 : tristate
1001 : get_tristate_at_offset (const symbolic_bit_offset &bit) const final override;
1002 :
1003 : string_scan
1004 : scan_for_first_zero_byte (concrete_byte_offset start_byte_offset)
1005 : const final override;
1006 :
1007 : bit_vector_from_ubc (const unfoldable_bit_contents &bc,
1008 : symbolic_bit_range bit_range);
1009 :
1010 : const unfoldable_bit_contents &
1011 438976 : get_bit_contents () const { return m_unfoldable_bit_contents; }
1012 :
1013 : const symbolic_bit_range &
1014 460 : get_bit_range () const { return m_bit_range; }
1015 :
1016 : const bit_vector *
1017 : maybe_fold_crop (const symbolic_bit_range &inner_bits_to_use)
1018 : const final override;
1019 :
1020 : std::unique_ptr<json::object>
1021 : to_json () const final override;
1022 :
1023 : std::unique_ptr<diagnostics::markup::node>
1024 : make_markup_node (markup_context &markup_ctxt) const final override;
1025 :
1026 : iter_result
1027 : for_each_svalue (iter_result (*cb) (const svalue &sval,
1028 : void *user_data),
1029 : void *user_data) const final override;
1030 :
1031 : bool implicitly_live_p (symbolic::liveness_context &) const final override;
1032 :
1033 : bool
1034 : conjured_p () const final override;
1035 :
1036 : private:
1037 : void
1038 : print_prefix_for_dump_widget_label (pretty_printer *pp) const final override;
1039 :
1040 : void
1041 : add_dump_widget_children (text_art::tree_widget &,
1042 : node_dump_state &nds) const final override;
1043 :
1044 : void
1045 : accept_node_visitor (node_visitor &v) const final override;
1046 :
1047 : const unfoldable_bit_contents &m_unfoldable_bit_contents;
1048 : symbolic_bit_range m_bit_range;
1049 : };
1050 :
1051 : /* A run of bits that are all 0, all 1, or all unknown. */
1052 :
1053 : class tristate_bit_vector : public uniform_bit_vector
1054 : {
1055 : public:
1056 : struct key
1057 : {
1058 634387 : key (const symbolic_bit_size &size_in_bits,
1059 : tristate bit_value)
1060 634387 : : m_size_in_bits (size_in_bits),
1061 634387 : m_bit_value (bit_value)
1062 : {
1063 : }
1064 :
1065 : bool operator< (const key &other) const;
1066 :
1067 : const symbolic_bit_size &m_size_in_bits;
1068 : tristate m_bit_value;
1069 : };
1070 :
1071 1885647 : enum kind get_kind () const final override
1072 : {
1073 1885647 : return kind::tristate;
1074 : }
1075 :
1076 : const tristate_bit_vector *
1077 565017 : dyn_cast_tristate_bit_vector () const final override { return this; }
1078 :
1079 : tristate
1080 : get_tristate_at_offset (const symbolic_bit_offset &bit) const final override;
1081 :
1082 : string_scan
1083 : scan_for_first_zero_byte (concrete_byte_offset start_byte_offset)
1084 : const final override;
1085 :
1086 : tristate_bit_vector (bit_vector_manager &mgr,
1087 : const key &k);
1088 :
1089 : tristate
1090 264753 : get_bit_value () const { return m_bit_value; }
1091 :
1092 : const bit_vector *
1093 : maybe_fold_crop (const symbolic_bit_range &inner_bits_to_use)
1094 : const final override;
1095 :
1096 : std::unique_ptr<json::object>
1097 : to_json () const final override;
1098 :
1099 : std::unique_ptr<diagnostics::markup::node>
1100 : make_markup_node (markup_context &markup_ctxt) const final override;
1101 :
1102 : iter_result
1103 : for_each_svalue (iter_result (*cb) (const svalue &sval,
1104 : void *user_data),
1105 : void *user_data) const final override;
1106 :
1107 : private:
1108 : void
1109 : print_prefix_for_dump_widget_label (pretty_printer *pp) const final override;
1110 :
1111 : void
1112 : print_any_suffix_for_dump_widget_label (pretty_printer *pp)
1113 : const final override;
1114 :
1115 : void
1116 : add_dump_widget_children (text_art::tree_widget &,
1117 : node_dump_state &nds) const final override;
1118 : void
1119 : accept_node_visitor (node_visitor &v) const final override;
1120 :
1121 : tristate m_bit_value;
1122 : };
1123 :
1124 : /* A class with responsibility for allocating/consolidating
1125 : bit_vector instances. A singleton relative to a node_manager. */
1126 :
1127 : class bit_vector_manager
1128 : {
1129 : public:
1130 : bit_vector_manager (node_manager &node_mgr);
1131 :
1132 : bit_vector_manager (const bit_vector_manager &) = delete;
1133 :
1134 : /* bit_vector consolidation. */
1135 :
1136 : const bit_vector &
1137 : get_tristate_bits (const symbolic_bit_size &num_bits, tristate bit_val);
1138 :
1139 : const bit_vector &
1140 : get_tristate_bits (const concrete_bit_size &num_bits, tristate bit_val);
1141 :
1142 : const bit_vector &
1143 4528 : get_all_zeros (const symbolic_bit_size &num_bits)
1144 : {
1145 4528 : return get_tristate_bits (num_bits, tristate (false));
1146 : }
1147 :
1148 : const bit_vector &
1149 115756 : get_all_zeros (const concrete_bit_size &num_bits)
1150 : {
1151 115752 : return get_tristate_bits (num_bits, tristate (false));
1152 : }
1153 :
1154 : const bit_vector &
1155 : get_all_zeros (const symbolic_byte_size &num_bytes)
1156 : {
1157 : return get_tristate_bits (bits_from_bytes (num_bytes), tristate (false));
1158 : }
1159 :
1160 : const bit_vector &
1161 4492 : get_all_zeros (const concrete_byte_size &num_bytes)
1162 : {
1163 4492 : return get_tristate_bits (bits_from_bytes (num_bytes), tristate (false));
1164 : }
1165 :
1166 : const bit_vector &
1167 : get_all_ones (const symbolic_bit_size &num_bits)
1168 : {
1169 : return get_tristate_bits (num_bits, tristate (true));
1170 : }
1171 :
1172 : const bit_vector &
1173 10492 : get_all_ones (const concrete_bit_size &num_bits)
1174 : {
1175 10492 : return get_tristate_bits (num_bits, tristate (true));
1176 : }
1177 :
1178 : const bit_vector &
1179 : get_all_ones (const symbolic_byte_size &num_bytes)
1180 : {
1181 : return get_tristate_bits (bits_from_bytes (num_bytes), tristate (true));
1182 : }
1183 :
1184 : const bit_vector &
1185 4421 : get_all_ones (const concrete_byte_size &num_bytes)
1186 : {
1187 4421 : return get_tristate_bits (bits_from_bytes (num_bytes), tristate (true));
1188 : }
1189 :
1190 : const bit_vector &
1191 : get_concat_bits (std::vector<const bit_vector *> vec_of_bit_vectors);
1192 :
1193 : const bit_vector &
1194 : get_conjured_bits (const gimple *stmt,
1195 : const region *id_reg,
1196 : const conjured_purge &p,
1197 : unsigned idx);
1198 :
1199 : const bit_vector &
1200 : get_bits_for_constant (tree tree_cst);
1201 :
1202 : const bit_vector &
1203 34 : get_empty () const { return m_empty_bv; }
1204 :
1205 : const bit_vector &
1206 105546 : get_unknown_bits (const symbolic_bit_size &num_bits)
1207 : {
1208 105546 : return get_tristate_bits (num_bits, tristate::unknown ());
1209 : }
1210 :
1211 : const bit_vector &
1212 289 : get_unknown_bytes (const symbolic_byte_size &num_bytes)
1213 : {
1214 289 : return get_tristate_bits (bits_from_bytes (num_bytes),
1215 289 : tristate::unknown ());
1216 : }
1217 :
1218 : const bit_vector &
1219 123862 : get_unknown_bits (const concrete_bit_size &num_bits)
1220 : {
1221 123862 : return get_tristate_bits (num_bits, tristate::unknown ());
1222 : }
1223 :
1224 : const bit_vector &
1225 8 : get_unknown_bytes (const concrete_byte_size &num_bytes)
1226 : {
1227 8 : return get_tristate_bits (bits_from_bytes (num_bytes), tristate::unknown ());
1228 : }
1229 :
1230 : // Unknown bits of unknown length
1231 : const bit_vector &
1232 : get_unknown_bits ();
1233 :
1234 : const bit_vector &
1235 : get_poisoned_bits (const symbolic_bit_size &num_bits,
1236 : enum poison_kind kind);
1237 :
1238 : const bit_vector &
1239 : get_poisoned_bits (const concrete_bit_size &num_bits,
1240 : enum poison_kind kind);
1241 :
1242 : const bit_vector &
1243 : get_poisoned_bytes (const symbolic_byte_size &num_bytes,
1244 : enum poison_kind kind)
1245 : {
1246 : return get_poisoned_bits (bits_from_bytes (num_bytes), kind);
1247 : }
1248 :
1249 : const bit_vector &
1250 1610670 : get_uninitialized_bits (const symbolic_bit_size &num_bits)
1251 : {
1252 1610670 : return get_poisoned_bits (num_bits, poison_kind::uninit);
1253 : }
1254 :
1255 : const bit_vector &
1256 : get_uninitialized_bytes (const symbolic_byte_size &num_bytes)
1257 : {
1258 : return get_poisoned_bits (bits_from_bytes (num_bytes),
1259 : poison_kind::uninit);
1260 : }
1261 :
1262 : const bit_vector &
1263 12 : get_uninitialized_bytes (const concrete_byte_size &num_bytes)
1264 : {
1265 12 : return get_poisoned_bits (bits_from_bytes (num_bytes),
1266 12 : poison_kind::uninit);
1267 : }
1268 :
1269 : const bit_vector &
1270 : get_cropped_bits (const bit_vector &uncropped_bv,
1271 : const symbolic_bit_range &bits_to_use);
1272 :
1273 : const bit_vector &
1274 : get_cropped_bytes (const bit_vector &uncropped_bv,
1275 : const symbolic_byte_range &bytes_to_use);
1276 :
1277 : const bit_vector &
1278 : get_repeated_bits (const bit_vector &inner_bv,
1279 : const symbolic_integer &repeat_count);
1280 :
1281 : const bit_vector &
1282 : get_repeated_bits (const bit_vector &inner_bv,
1283 : const concrete_integer &repeat_count);
1284 :
1285 : const bit_vector &
1286 : get_bit_vector_from_svalue (const svalue &sval);
1287 :
1288 : const bit_vector *
1289 : maybe_get_bit_vector_from_svalue (const svalue &sval);
1290 :
1291 : const bit_vector &
1292 26576 : get_uint8 (uint8_t value)
1293 : {
1294 26556 : gcc_assert (m_cached_bytes[value]);
1295 240 : return *m_cached_bytes[value];
1296 : }
1297 :
1298 : #if CHECKING_P
1299 : const bit_vector &
1300 : get_named_test_bit_vector (const symbolic_bit_size &size_in_bits,
1301 : std::string label);
1302 :
1303 : const bit_vector &
1304 : get_named_test_bit_vector (const symbolic_byte_size &size_in_bytes,
1305 : std::string label);
1306 :
1307 : const bit_vector &
1308 : get_named_test_bit_vector (const concrete_bit_size &size_in_bits,
1309 : std::string label);
1310 :
1311 : const bit_vector &
1312 : get_named_test_bit_vector (const concrete_byte_size &size_in_bytes,
1313 : std::string label);
1314 : #endif /* #if CHECKING_P */
1315 :
1316 : node_manager &
1317 3745150 : get_node_manager () const { return m_node_mgr; }
1318 :
1319 : scalar_manager<concrete_bit_size> &
1320 4022513 : get_bit_manager () const
1321 : {
1322 4022513 : return m_node_mgr.get_scalars ().get_bits ();
1323 : }
1324 :
1325 : region_model_manager &
1326 48 : get_svalue_manager () const { return m_node_mgr.get_svalue_manager (); }
1327 :
1328 : const bit_vector &
1329 : get_baseline_bit_vector (const region &base_reg,
1330 : baseline_state bs);
1331 :
1332 : const bit_vector *
1333 : maybe_fold_bytes_within_constant (tree tree_cst,
1334 : concrete_byte_range conc_bytes);
1335 : const bit_vector *
1336 : maybe_fold_bits_for_svalue (const svalue &sval);
1337 :
1338 : private:
1339 : const bit_vector *
1340 : maybe_fold_concat_bits (const std::vector<const bit_vector *> &vec);
1341 :
1342 : std::vector<const bit_vector *>
1343 : canonicalize_concat_bits (const std::vector<const bit_vector *> &vec);
1344 :
1345 : const bit_vector *
1346 : maybe_fold_bits_for_constant (tree tree_cst);
1347 :
1348 : const bit_vector *
1349 : maybe_fold_bytes_within_string_cst (tree string_cst,
1350 : concrete_byte_range conc_bytes);
1351 : const bit_vector *
1352 : maybe_fold_bytes_within_raw_data_cst (tree raw_data_cst,
1353 : concrete_byte_range conc_bytes);
1354 :
1355 : const bit_vector *
1356 : maybe_fold_cropped_bits (const bit_vector &inner_bits,
1357 : const symbolic_bit_range &inner_bits_to_use);
1358 :
1359 : const bit_vector &
1360 : make_baseline_bit_vector (baseline_key k);
1361 :
1362 : const bit_vector *
1363 : maybe_fold_repeated_bits (const bit_vector &inner_bits,
1364 : const symbolic_integer &repeat_count);
1365 :
1366 : node_manager &m_node_mgr;
1367 :
1368 : std::map<concat_bit_vector::key,
1369 : std::unique_ptr<concat_bit_vector>> m_concat_map;
1370 : std::map<conjured_bit_vector::key,
1371 : std::unique_ptr<conjured_bit_vector>> m_conjured_map;
1372 : std::map<cropped_bit_vector::key,
1373 : std::unique_ptr<cropped_bit_vector>> m_cropped_map;
1374 : empty_bit_vector m_empty_bv;
1375 : std::map<poisoned_bit_vector::key,
1376 : std::unique_ptr<poisoned_bit_vector>> m_poisoned_map;
1377 : std::map<repeated_bit_vector::key,
1378 : std::unique_ptr<repeated_bit_vector>> m_repeated_map;
1379 : std::map<bit_vector_from_svalue::key,
1380 : std::unique_ptr<bit_vector_from_svalue>> m_svalue_to_bv_map;
1381 : std::map<tristate_bit_vector::key,
1382 : std::unique_ptr<tristate_bit_vector>> m_tristate_map;
1383 :
1384 : std::map<baseline_key, const bit_vector &> m_baseline_map;
1385 :
1386 : #if CHECKING_P
1387 : std::vector<std::unique_ptr<named_test_bit_vector>> m_named_test_bvs;
1388 : #endif
1389 :
1390 : const bit_vector *m_cached_bytes[256];
1391 : };
1392 :
1393 : } // namespace ana::symbolic
1394 : } // namespace ana
1395 :
1396 : #endif /* GCC_ANALYZER_SYMBOLIC_BIT_VECTORS_H */
|