Line data Source code
1 : /* Symbolic maps of bits e.g. "bytes [0-4): <bitvec>, bytes[16-20): <bitvec>"
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 : #ifndef GCC_ANALYZER_SYMBOLIC_BIT_MAP_H
22 : #define GCC_ANALYZER_SYMBOLIC_BIT_MAP_H
23 :
24 : #include "analyzer/concrete-ranges.h"
25 : #include "analyzer/symbolic-ranges.h"
26 : #include "analyzer/string-scan.h"
27 : #include "analyzer/symbolic-bit-vectors.h"
28 :
29 : namespace ana {
30 :
31 : namespace symbolic {
32 :
33 : /* Abstract base class for representing a total function from
34 : symbolic bit ranges to symbolic bit vectors i.e. the contents
35 : of a region of memory.
36 :
37 : e.g. - "what is the value of bytes [8..16)?"
38 : - "what is the value of bit[100000]?"
39 : - "what is the value of byte[x]?" (for symbolic x)
40 :
41 : It's permissable to get/set things at negative offsets e.g. for the
42 : case of negative offsets from a symbolic pointer.
43 :
44 : Any range checking happens at a higher level.
45 :
46 : This is purely-functional: setters return a reference to a bit_contents
47 : instance holding the update.
48 :
49 : The class hierarchy looks like this (using indentation to show
50 : inheritance):
51 :
52 : symbolic::bit_contents (abstract)
53 : symbolic::uniform_bit_contents (abstract): something that ignores the input range
54 : symbolic::uninit_contents (concrete singleton): uninitialized everywhere
55 : symbolic::untracked_bit_contents (concrete): unknown everywhere, has a set of possibly-live values
56 : symbolic::zero_contents (concrete singleton): zero everywhere
57 : symbolic::unfoldable_bit_contents (abstract): unfoldable; hands out bit_vector_from_ubc instances
58 : symbolic::baseline_bit_contents (concrete): the initial contents of regions without known sizes
59 : symbolic::conjured_bit_contents (concrete): a bit_contents arising from a stmt
60 : symbolic::named_test_bit_contents (concrete): for use in selftests
61 : symbolic::bit_overlay (abstract): a baseline overridden at some places
62 : symbolic::concrete_bit_overlay (concrete)
63 : symbolic::symbolic_bit_overlay (concrete)
64 : symbolic::offset_bit_contents (concrete): offsets the coordinates of another bit_contents
65 : */
66 :
67 : class bit_contents : public symbolic::node
68 : {
69 : public:
70 : enum class kind
71 : {
72 : uninit,
73 : untracked,
74 : zero,
75 : baseline,
76 : conjured,
77 : named_test,
78 : concrete_overlay,
79 : symbolic_overlay,
80 : offset
81 : };
82 :
83 : virtual enum kind get_kind () const = 0;
84 :
85 95261 : node_manager &get_node_mgr () const { return m_node_mgr; }
86 :
87 : bit_contents_manager &
88 874823 : get_bit_contents_manager () const
89 : {
90 874823 : return m_node_mgr.get_bit_contents_manager ();
91 : }
92 :
93 : bit_vector_manager &
94 4260177 : get_bit_vector_manager () const
95 : {
96 2091015 : return m_node_mgr.get_bit_vector_manager ();
97 : }
98 :
99 : virtual const uniform_bit_contents *
100 9 : dyn_cast_uniform_bit_contents () const { return nullptr; }
101 :
102 : virtual const baseline_bit_contents *
103 62336 : dyn_cast_baseline_bit_contents () const { return nullptr; }
104 :
105 : virtual const conjured_bit_contents *
106 56033 : dyn_cast_conjured_bit_contents () const { return nullptr; }
107 :
108 : virtual const concrete_bit_overlay *
109 331005 : dyn_cast_concrete_bit_overlay () const { return nullptr; }
110 :
111 : virtual const symbolic_bit_overlay *
112 0 : dyn_cast_symbolic_bit_overlay () const { return nullptr; }
113 :
114 : virtual const offset_bit_contents *
115 9 : dyn_cast_offset_bit_contents () const { return nullptr; }
116 :
117 : const char *
118 11896 : get_any_dump_color () const override { return "bit_contents"; }
119 :
120 : // Getters
121 :
122 : virtual const bit_vector &
123 : get_bits (const symbolic_bit_range &bit_range) const = 0;
124 :
125 : const bit_vector &
126 : get_bits (const concrete_bit_range &bit_range) const;
127 :
128 : const bit_vector &
129 : get_bytes (const concrete_byte_range &byte_range) const;
130 :
131 : const bit_vector &
132 : get_bytes (const symbolic_byte_range &byte_range) const;
133 :
134 : const bit_vector &
135 328 : get_byte (integer_with_unit<units::byte> byte_offset) const
136 : {
137 984 : return get_bytes (concrete_byte_range (byte_offset, 1_byte));
138 : }
139 :
140 : // Setters
141 :
142 : const bit_contents &
143 : set_bits (const symbolic_bit_range &bit_range,
144 : const bit_vector &bv,
145 : uncertainty_t *uncertainty) const;
146 :
147 : const bit_contents &
148 : set_bits (const concrete_bit_range &bit_range,
149 : const bit_vector &bv,
150 : uncertainty_t *uncertainty) const;
151 :
152 : const bit_contents &
153 : set_bytes (const symbolic_byte_range &byte_range,
154 : const bit_vector &bv,
155 : uncertainty_t *uncertainty) const;
156 :
157 : const bit_contents &
158 : set_bytes (const concrete_byte_range &byte_range,
159 : const bit_vector &bv,
160 : uncertainty_t *uncertainty) const;
161 :
162 : const bit_contents &
163 : set_byte (integer_with_unit<units::byte> byte_offset,
164 : uint8_t value,
165 : uncertainty_t *uncertainty) const;
166 :
167 : virtual string_scan
168 : scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset)
169 : const = 0;
170 :
171 : virtual void
172 : get_representative_path_vars (const region_model *model,
173 : value_set *visited,
174 : const region *base_reg,
175 : const svalue *sval,
176 : tree desired_type,
177 : logger *logger,
178 : auto_vec<path_var> *out_pvs) const = 0;
179 :
180 : virtual const bit_contents &
181 : poison_any_pointers_to_descendents (const region *reg,
182 : enum poison_kind pkind) const = 0;
183 :
184 : virtual const bit_contents &
185 : purge_state_involving (const symbolic::node &node) const = 0;
186 :
187 : virtual bool
188 : bits_live_p (const bit_vector_from_ubc &bv_from_ubc) const = 0;
189 :
190 :
191 : /* vfunc for use by bit_contents_manager::get_offset_bit_contents. */
192 : virtual const bit_contents *
193 13 : maybe_fold_offset (const symbolic_bit_offset &) const
194 : {
195 13 : return nullptr;
196 : }
197 :
198 : static const bit_contents *
199 : can_merge_p (const bit_contents &bit_contents_a,
200 : const bit_contents &bit_contents_b,
201 : tree type,
202 : model_merger *merger);
203 :
204 : virtual bool
205 110496 : conjured_p () const { return false; }
206 :
207 : virtual iter_result
208 : for_each_value (iter_result (*cb) (const symbolic::value_node &val,
209 : void *user_data),
210 : void *user_data) const = 0;
211 :
212 : value_set
213 : get_maybe_live_values () const;
214 :
215 : protected:
216 112748 : bit_contents (complexity c, node_manager &node_mgr)
217 : : node (c, node_mgr.alloc_node_id ()),
218 9 : m_node_mgr (node_mgr)
219 : {
220 : }
221 :
222 : private:
223 : node_manager &m_node_mgr;
224 : };
225 :
226 : /* Abstract subclass of bit_contents for those classes that have
227 : the same bit content everywhere, and thus ignore the input bit_range. */
228 :
229 : class uniform_bit_contents : public bit_contents
230 : {
231 : public:
232 : const uniform_bit_contents *
233 0 : dyn_cast_uniform_bit_contents () const final override { return this; }
234 :
235 : const bit_contents *
236 : maybe_fold_offset (const symbolic_bit_offset &bit_offset)
237 : const final override;
238 :
239 : iter_result
240 : for_each_value (iter_result (*cb) (const symbolic::value_node &val,
241 : void *user_data),
242 : void *user_data) const override;
243 :
244 : protected:
245 12238 : uniform_bit_contents (complexity c, node_manager &node_mgr)
246 3420 : : bit_contents (c, node_mgr)
247 : {
248 : }
249 : };
250 :
251 : /* Concrete subclass that's always uninitialized. */
252 :
253 : class uninit_contents : public uniform_bit_contents
254 : {
255 : public:
256 : uninit_contents (node_manager &node_mgr);
257 :
258 : enum kind
259 1509876 : get_kind () const final override
260 : {
261 1509876 : return bit_contents::kind::uninit;
262 : }
263 :
264 : const bit_vector &
265 : get_bits (const symbolic_bit_range &bit_range) const final override;
266 :
267 : void
268 : print_dump_widget_label (pretty_printer *pp) const final override;
269 :
270 : void
271 : add_dump_widget_children (text_art::tree_widget &,
272 : node_dump_state &nds) const final override;
273 :
274 : void
275 : accept_node_visitor (node_visitor &v) const final override;
276 :
277 : std::unique_ptr<json::object>
278 : to_json () const final override;
279 :
280 : std::unique_ptr<diagnostics::markup::node>
281 : make_markup_node (markup_context &markup_ctxt) const final override;
282 :
283 : string_scan
284 : scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset)
285 : const final override;
286 :
287 : void
288 : get_representative_path_vars (const region_model *model,
289 : value_set *visited,
290 : const region *base_reg,
291 : const svalue *sval,
292 : tree desired_type,
293 : logger *logger,
294 : auto_vec<path_var> *out_pvs)
295 : const final override;
296 :
297 : const bit_contents &
298 : poison_any_pointers_to_descendents (const region *reg,
299 : enum poison_kind pkind)
300 : const final override;
301 :
302 : const bit_contents &
303 : purge_state_involving (const symbolic::node &node) const final override;
304 :
305 : bool
306 211 : bits_live_p (const bit_vector_from_ubc &) const final override
307 : {
308 211 : return false;
309 : }
310 : };
311 :
312 : /* Concrete subclass where the bits are unknown everywhere,
313 : with a set of possibly-live values.
314 :
315 : Consolidation/canonicalization:
316 : - every value stored in the set must have true for
317 : untracked_bit_contents::track_value_liveness_p (val); other
318 : value nodes are redundant to liveness and are never added
319 : to untracked_bit_contents::m_maybe_live. */
320 :
321 : class untracked_bit_contents : public uniform_bit_contents
322 : {
323 : public:
324 134760 : struct key
325 : {
326 127920 : key (value_set &&maybe_live) : m_maybe_live (maybe_live) {}
327 :
328 : value_set m_maybe_live;
329 :
330 : bool
331 : operator< (const key &other) const;
332 :
333 : complexity
334 : get_complexity () const;
335 : };
336 :
337 : untracked_bit_contents (node_manager &node_mgr, const key &k);
338 :
339 : enum kind
340 16402 : get_kind () const final override
341 : {
342 16402 : return bit_contents::kind::untracked;
343 : }
344 :
345 : const bit_vector &
346 : get_bits (const symbolic_bit_range &bit_range) const final override;
347 :
348 : void
349 : print_dump_widget_label (pretty_printer *pp) const final override;
350 :
351 : void
352 : add_dump_widget_children (text_art::tree_widget &,
353 : node_dump_state &nds) const final override;
354 :
355 : void
356 : accept_node_visitor (node_visitor &v) const final override;
357 :
358 : std::unique_ptr<json::object>
359 : to_json () const final override;
360 :
361 : std::unique_ptr<diagnostics::markup::node>
362 : make_markup_node (markup_context &markup_ctxt) const final override;
363 :
364 : string_scan
365 : scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset)
366 : const final override;
367 :
368 : void
369 : get_representative_path_vars (const region_model *model,
370 : value_set *visited,
371 : const region *base_reg,
372 : const svalue *sval,
373 : tree desired_type,
374 : logger *logger,
375 : auto_vec<path_var> *out_pvs)
376 : const final override;
377 :
378 : const bit_contents &
379 : poison_any_pointers_to_descendents (const region *reg,
380 : enum poison_kind pkind)
381 : const final override;
382 :
383 : const bit_contents &
384 : purge_state_involving (const symbolic::node &node) const final override;
385 :
386 : bool
387 : bits_live_p (const bit_vector_from_ubc &) const final override;
388 :
389 : iter_result
390 : for_each_value (iter_result (*cb) (const symbolic::value_node &val,
391 : void *user_data),
392 : void *user_data) const final override;
393 :
394 : const value_set &
395 : get_maybe_live () const { return m_maybe_live; }
396 :
397 : static bool
398 : track_value_liveness_p (const symbolic::value_node &val);
399 :
400 : static bool
401 : track_bit_vector_liveness_p (const symbolic::bit_vector &bv);
402 :
403 : static bool
404 : track_svalue_liveness_p (const svalue &val);
405 :
406 : private:
407 : value_set m_maybe_live;
408 : };
409 :
410 : /* Concrete subclass that's a zero bit everywhere. */
411 :
412 : class zero_contents : public uniform_bit_contents
413 : {
414 : public:
415 : zero_contents (node_manager &node_mgr);
416 :
417 : enum kind
418 1236 : get_kind () const final override
419 : {
420 1236 : return bit_contents::kind::zero;
421 : }
422 :
423 : const bit_vector &
424 : get_bits (const symbolic_bit_range &bit_range) const final override;
425 :
426 : void
427 : print_dump_widget_label (pretty_printer *pp) const final override;
428 :
429 : void
430 : add_dump_widget_children (text_art::tree_widget &,
431 : node_dump_state &nds) const final override;
432 :
433 : void
434 : accept_node_visitor (node_visitor &v) const final override;
435 :
436 : std::unique_ptr<json::object>
437 : to_json () const final override;
438 :
439 : std::unique_ptr<diagnostics::markup::node>
440 : make_markup_node (markup_context &markup_ctxt) const final override;
441 :
442 : string_scan
443 : scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset)
444 : const final override;
445 :
446 : void
447 : get_representative_path_vars (const region_model *model,
448 : value_set *visited,
449 : const region *base_reg,
450 : const svalue *sval,
451 : tree desired_type,
452 : logger *logger,
453 : auto_vec<path_var> *out_pvs)
454 : const final override;
455 :
456 : const bit_contents &
457 : poison_any_pointers_to_descendents (const region *reg,
458 : enum poison_kind pkind)
459 : const final override;
460 :
461 : const bit_contents &
462 : purge_state_involving (const symbolic::node &node) const final override;
463 :
464 : bool
465 0 : bits_live_p (const bit_vector_from_ubc &) const final override
466 : {
467 0 : return false;
468 : }
469 : };
470 :
471 : /* Abstract bit_contents subclass that can't be folded.
472 : Hands out bit_vector_from_ubc instances when its bits
473 : are queried. */
474 :
475 : class unfoldable_bit_contents : public bit_contents
476 : {
477 : public:
478 : const symbolic::bit_vector &
479 : get_bits (const symbolic_bit_range &bit_range) const override;
480 :
481 : string_scan
482 : scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset)
483 : const final override;
484 :
485 : bool
486 : bits_live_p (const bit_vector_from_ubc &bv_from_ubc) const final override;
487 :
488 : void
489 : get_representative_path_vars (const region_model *model,
490 : value_set *visited,
491 : const region *base_reg,
492 : const svalue *sval,
493 : tree desired_type,
494 : logger *logger,
495 : auto_vec<path_var> *out_pvs)
496 : const final override;
497 :
498 : protected:
499 20253 : unfoldable_bit_contents (complexity c, node_manager &node_mgr)
500 8042 : : bit_contents (c, node_mgr)
501 : {}
502 :
503 : private:
504 : using map_type = std::map<symbolic_bit_range,
505 : std::unique_ptr<bit_vector_from_ubc>>;
506 : mutable map_type m_range_to_bv_map;
507 : };
508 :
509 : /* A bit_contents representing the initial content of a base region that
510 : doesn't have a meaningful size.
511 :
512 : Consolidation/canonicalization:
513 : - the base region must not have meaningful size (otherwise we can build
514 : an concrete_bit_overlay for its initial contents using initial_svalue). */
515 :
516 : class baseline_bit_contents : public unfoldable_bit_contents
517 : {
518 : public:
519 : baseline_bit_contents (node_manager &node_mgr, const baseline_key &k);
520 :
521 : enum kind
522 25019 : get_kind () const final override
523 : {
524 25019 : return bit_contents::kind::baseline;
525 : }
526 :
527 : const baseline_bit_contents *
528 283658 : dyn_cast_baseline_bit_contents () const final override { return this; }
529 :
530 : void
531 : print_dump_widget_label (pretty_printer *pp) const final override;
532 :
533 : void
534 : add_dump_widget_children (text_art::tree_widget &,
535 : node_dump_state &) const final override;
536 :
537 : void
538 : accept_node_visitor (node_visitor &v) const final override;
539 :
540 : std::unique_ptr<json::object>
541 : to_json () const final override;
542 :
543 : std::unique_ptr<diagnostics::markup::node>
544 : make_markup_node (markup_context &markup_ctxt) const final override;
545 :
546 : const bit_contents &
547 : poison_any_pointers_to_descendents (const region *reg,
548 : enum poison_kind pkind)
549 : const final override;
550 :
551 : const bit_contents &
552 : purge_state_involving (const symbolic::node &node) const final override;
553 :
554 : iter_result
555 : for_each_value (iter_result (*cb) (const symbolic::value_node &val,
556 : void *user_data),
557 : void *user_data) const final override;
558 :
559 : const baseline_key &
560 : get_baseline_key () const { return m_baseline_key; }
561 :
562 : private:
563 : baseline_key m_baseline_key;
564 : };
565 :
566 : /* A defined bit_contents arising from a statement.
567 :
568 : For example, this is used for the values of regions of unknown size
569 : that may have been touched when calling an unknown function.
570 :
571 : The bit_contents captures a region as well as a stmt in order to avoid
572 : falsely aliasing the various values that could arise in one statement.
573 : For example, after:
574 : unknown_fn (&a, &b);
575 : we want nodes to clobber a and b with, but we don't want to use the
576 : same node, or it would falsely implicitly assume that a == b. */
577 :
578 : class conjured_bit_contents : public unfoldable_bit_contents
579 : {
580 : public:
581 : struct key
582 : {
583 25532 : key (const gimple *stmt,
584 : const region *id_reg,
585 : unsigned idx)
586 25532 : : m_stmt (stmt), m_id_reg (id_reg), m_idx (idx)
587 : {
588 : }
589 :
590 : bool operator< (const key &other) const;
591 :
592 : complexity
593 : get_complexity () const;
594 :
595 : const gimple *m_stmt;
596 : const region *m_id_reg;
597 : unsigned m_idx;
598 : };
599 :
600 : conjured_bit_contents (node_manager &node_mgr, const key &k);
601 :
602 : enum kind
603 10564 : get_kind () const final override
604 : {
605 10564 : return bit_contents::kind::conjured;
606 : }
607 :
608 : const conjured_bit_contents *
609 11005 : dyn_cast_conjured_bit_contents () const final override { return this; }
610 :
611 : void
612 : print_dump_widget_label (pretty_printer *pp) const final override;
613 :
614 : void
615 : add_dump_widget_children (text_art::tree_widget &,
616 : node_dump_state &) const final override;
617 :
618 : void
619 : accept_node_visitor (node_visitor &v) const final override;
620 :
621 : std::unique_ptr<json::object>
622 : to_json () const final override;
623 :
624 : std::unique_ptr<diagnostics::markup::node>
625 : make_markup_node (markup_context &markup_ctxt) const final override;
626 :
627 : const bit_contents &
628 : poison_any_pointers_to_descendents (const region *reg,
629 : enum poison_kind pkind)
630 : const final override;
631 :
632 : const bit_contents &
633 : purge_state_involving (const symbolic::node &node) const final override;
634 :
635 : bool
636 15847 : conjured_p () const final override { return true; }
637 :
638 : iter_result
639 : for_each_value (iter_result (*cb) (const symbolic::value_node &val,
640 : void *user_data),
641 : void *user_data) const final override;
642 :
643 : const gimple *get_stmt () const { return m_stmt; }
644 11005 : const region *get_id_region () const { return m_id_reg; }
645 : unsigned get_index () const { return m_idx; }
646 :
647 : private:
648 : const gimple *m_stmt;
649 : const region *m_id_reg;
650 : unsigned m_idx;
651 : };
652 :
653 : /* Concrete subclass of unfoldable_bit_contents for use in selftests. */
654 :
655 : #if CHECKING_P
656 :
657 : class named_test_bit_contents : public unfoldable_bit_contents
658 : {
659 : public:
660 : named_test_bit_contents (node_manager &node_mgr, std::string name);
661 :
662 : enum kind
663 656 : get_kind () const final override
664 : {
665 656 : return bit_contents::kind::named_test;
666 : }
667 :
668 : void
669 : print_dump_widget_label (pretty_printer *pp) const final override;
670 :
671 : void
672 : add_dump_widget_children (text_art::tree_widget &,
673 : node_dump_state &) const final override;
674 :
675 : void
676 : accept_node_visitor (node_visitor &v) const final override;
677 :
678 : std::unique_ptr<json::object>
679 : to_json () const final override;
680 :
681 : std::unique_ptr<diagnostics::markup::node>
682 : make_markup_node (markup_context &markup_ctxt) const final override;
683 :
684 : const bit_contents &
685 : poison_any_pointers_to_descendents (const region *reg,
686 : enum poison_kind pkind)
687 : const final override;
688 :
689 : const bit_contents &
690 : purge_state_involving (const symbolic::node &node) const final override;
691 :
692 : iter_result
693 : for_each_value (iter_result (*cb) (const symbolic::value_node &val,
694 : void *user_data),
695 : void *user_data) const final override;
696 :
697 : const char *
698 : get_name () const { return m_name.c_str (); }
699 :
700 : private:
701 : std::string m_name;
702 : };
703 :
704 : #endif /* #if CHECKING_P */
705 :
706 : /* Abstract bit_contents subclasses that uses a baseline
707 : bit_contents in most of the domain, but overrides it at
708 : one or more places; subclasses provide the concrete implementation.
709 :
710 : Consolidation/canonicalization:
711 : - no nesting of overlays: the baseline must not itself be a bit_overlay. */
712 :
713 : class bit_overlay : public bit_contents
714 : {
715 : public:
716 : const bit_contents &
717 6456232 : get_baseline () const { return m_baseline; }
718 :
719 : protected:
720 80248 : bit_overlay (complexity c, const bit_contents &baseline)
721 : : bit_contents (c, baseline.get_node_mgr ()),
722 80248 : m_baseline (baseline)
723 : {
724 : }
725 :
726 : private:
727 : const bit_contents &m_baseline;
728 : };
729 :
730 : /* A sparse mapping from concrete bit ranges to symbolic bit maps,
731 : overlaid on an underlying baseline bit_contents.
732 :
733 : Has no size; bounds-checking must happen at a higher level.
734 :
735 : Consolidation/canonicalization:
736 : - must have at least one entry in the map
737 : - no nesting of overlays: the baseline must not itself be a bit_overlay.
738 : - bit ranges in the map are ordered by start offset
739 : - no overlapping of bit ranges
740 : - no redundant bindings: the bit_vector bound to RANGE must not equal
741 : BASELINE.get_bits(RANGE)
742 : - the size of each bit_vector must be concrete and match that of the bit
743 : range it is bound to
744 : - no leading concrete-sized child elements of a concat_bit_vector: these
745 : are canonicalized by splitting out into separate mappings from range
746 : to component bit_vector. */
747 :
748 : class concrete_bit_overlay : public bit_overlay
749 : {
750 : public:
751 855908 : struct key
752 : {
753 : const bit_contents *m_baseline;
754 : std::map<concrete_bit_range, const bit_vector &> m_concrete_range_map;
755 :
756 : bool
757 : operator< (const key &other) const;
758 :
759 : complexity
760 : get_complexity () const;
761 :
762 : void
763 : remove_redundant_bindings ();
764 : };
765 :
766 : const concrete_bit_overlay *
767 184708 : dyn_cast_concrete_bit_overlay () const final override { return this; }
768 :
769 : concrete_bit_overlay (const key &k);
770 :
771 : enum kind
772 7708 : get_kind () const final override
773 : {
774 7708 : return bit_contents::kind::concrete_overlay;
775 : }
776 :
777 8 : size_t size () const { return m_concrete_range_map.size (); }
778 :
779 : const bit_vector &
780 : get_bits (const symbolic_bit_range &bit_range) const final override;
781 :
782 : void
783 : print_dump_widget_label (pretty_printer *pp) const final override;
784 :
785 : void
786 : add_dump_widget_children (text_art::tree_widget &,
787 : node_dump_state &nds) const final override;
788 :
789 : void
790 : accept_node_visitor (node_visitor &v) const final override;
791 :
792 : std::unique_ptr<json::object>
793 : to_json () const final override;
794 :
795 : std::unique_ptr<diagnostics::markup::node>
796 : make_markup_node (markup_context &markup_ctxt) const final override;
797 :
798 : string_scan
799 : scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset)
800 : const final override;
801 :
802 : void
803 : get_representative_path_vars (const region_model *model,
804 : value_set *visited,
805 : const region *base_reg,
806 : const svalue *sval,
807 : tree desired_type,
808 : logger *logger,
809 : auto_vec<path_var> *out_pvs)
810 : const final override;
811 :
812 : const bit_contents &
813 : poison_any_pointers_to_descendents (const region *reg,
814 : enum poison_kind pkind)
815 : const final override;
816 :
817 : const bit_contents &
818 : purge_state_involving (const symbolic::node &node) const final override;
819 :
820 : bool
821 : bits_live_p (const bit_vector_from_ubc &bv_from_ubc) const final override;
822 :
823 : iter_result
824 : for_each_value (iter_result (*cb) (const symbolic::value_node &val,
825 : void *user_data),
826 : void *user_data) const final override;
827 :
828 : const bit_vector &
829 : get_concrete_bits (const concrete_bit_range &bit_range) const;
830 :
831 : const bit_contents &
832 : set_concrete_bits (const concrete_bit_range &bit_range,
833 : const bit_vector &bv) const;
834 :
835 : const svalue *
836 : maybe_get_var_arg_svalue () const;
837 :
838 : static const bit_contents *
839 : can_merge_p (const bit_contents &bit_contents_a,
840 : const bit_contents &bit_contents_b,
841 : const bit_contents &shared_baseline,
842 : const concrete_bit_overlay *conc_bit_overlay_a,
843 : const concrete_bit_overlay *conc_bit_overlay_b,
844 : tree type,
845 : model_merger *merger);
846 :
847 : static std::map<concrete_bit_range, const bit_vector &>
848 : canonicalize_new_bit_vec (const concrete_bit_range &new_bit_range,
849 : const bit_vector &bv);
850 :
851 : static std::map<concrete_bit_range, const bit_vector &>
852 : consolidate_adjacent (std::map<concrete_bit_range, const bit_vector &> map,
853 : bit_vector_manager &bv_mgr);
854 :
855 : bool
856 : bit_offset_is_bound_p (concrete_bit_offset) const;
857 :
858 : /* Map from concrete ranges of bits to symbolic bit vectors.
859 : The sizes must match.
860 : By construction, the bit ranges do not overlap. */
861 : std::map<concrete_bit_range, const bit_vector &> m_concrete_range_map;
862 : };
863 :
864 : /* A sparse mapping from symbolic bit ranges to symbolic bit vectors,
865 : overlaid on an underlying baseline bit_contents.
866 :
867 : Has no size; bounds-checking must happen at a higher level.
868 :
869 : Consolidation/canonicalization:
870 : - must have exactly one entry in the map (attempts to create more than
871 : one symbolic key ought to be folded into the baseline)
872 : TODO(can probably use this to greatly simplify this implementation,
873 : and possibly merge it with concrete_bit_overlay).
874 : - no nesting of overlays: the baseline must not itself be a bit_overlay.
875 : - bit ranges in the map are not allowed to have "unknown" start offset
876 : TODO(design): are they allowed to have "unknown" size?
877 : - bit ranges in the map are not allowed to be fully concrete
878 : - no redundant bindings: the bit_vector bound to RANGE must not equal
879 : BASELINE.get_bits(RANGE).
880 : - the size of each bit_vector must match that of the bit
881 : range it is bound to (this size may be either concrete or symbolic). */
882 :
883 : class symbolic_bit_overlay : public bit_overlay
884 : {
885 : public:
886 23791 : struct key
887 : {
888 : const bit_contents *m_baseline;
889 : std::map<symbolic_bit_range, const bit_vector &> m_symbolic_range_map;
890 :
891 : bool
892 : operator< (const key &other) const;
893 :
894 : complexity
895 : get_complexity () const;
896 :
897 : void
898 : remove_redundant_bindings ();
899 : };
900 :
901 : const symbolic_bit_overlay *
902 0 : dyn_cast_symbolic_bit_overlay () const final override { return this; }
903 :
904 : symbolic_bit_overlay (const key &k);
905 :
906 : enum kind
907 770 : get_kind () const final override
908 : {
909 770 : return bit_contents::kind::symbolic_overlay;
910 : }
911 :
912 : size_t size () const { return m_symbolic_range_map.size (); }
913 :
914 : const bit_vector &
915 : get_bits (const symbolic_bit_range &bit_range) const final override;
916 :
917 : void
918 : print_dump_widget_label (pretty_printer *pp) const final override;
919 :
920 : void
921 : add_dump_widget_children (text_art::tree_widget &,
922 : node_dump_state &nds) const final override;
923 :
924 : void
925 : accept_node_visitor (node_visitor &v) const final override;
926 :
927 : std::unique_ptr<json::object>
928 : to_json () const final override;
929 :
930 : std::unique_ptr<diagnostics::markup::node>
931 : make_markup_node (markup_context &markup_ctxt) const final override;
932 :
933 : string_scan
934 : scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset)
935 : const final override;
936 :
937 : void
938 : get_representative_path_vars (const region_model *model,
939 : value_set *visited,
940 : const region *base_reg,
941 : const svalue *sval,
942 : tree desired_type,
943 : logger *logger,
944 : auto_vec<path_var> *out_pvs)
945 : const final override;
946 :
947 : const bit_contents &
948 : poison_any_pointers_to_descendents (const region *reg,
949 : enum poison_kind pkind)
950 : const final override;
951 :
952 : const bit_contents &
953 : purge_state_involving (const symbolic::node &node) const final override;
954 :
955 : bool
956 : bits_live_p (const bit_vector_from_ubc &bv_from_ubc) const final override;
957 :
958 : iter_result
959 : for_each_value (iter_result (*cb) (const symbolic::value_node &val,
960 : void *user_data),
961 : void *user_data) const final override;
962 :
963 : /* Map from symbolic ranges of bits to symbolic bit vectors.
964 : Note that in the current implementation the map has at most one
965 : entry, suggsesting future simplification possibilities. */
966 : std::map<symbolic_bit_range, const bit_vector &> m_symbolic_range_map;
967 : };
968 :
969 : /* A bit_contents instance that offsets the coordinates of another
970 : bit_contents instance.
971 :
972 : Consolidation/canonicalization:
973 : - the offset cannot be zero
974 : - the inner bit_contents cannot be uniform
975 : - no nesting: the inner bit_contents cannot be an offset_bit_contents
976 : (we can simply fold by adding the offsets). */
977 :
978 : class offset_bit_contents : public bit_contents
979 : {
980 : public:
981 : struct key
982 : {
983 : const bit_contents *m_inner_bc;
984 : const symbolic_bit_offset *m_bit_offset;
985 :
986 : bool
987 : operator< (const key &other) const;
988 :
989 : complexity
990 : get_complexity () const;
991 : };
992 :
993 : const offset_bit_contents *
994 4 : dyn_cast_offset_bit_contents () const final override { return this; }
995 :
996 : offset_bit_contents (node_manager &node_mgr, const key &k);
997 :
998 : enum kind
999 5 : get_kind () const final override
1000 : {
1001 5 : return bit_contents::kind::offset;
1002 : }
1003 :
1004 : const bit_vector &
1005 : get_bits (const symbolic_bit_range &bit_range) const final override;
1006 :
1007 : void
1008 : print_dump_widget_label (pretty_printer *pp) const final override;
1009 :
1010 : void
1011 : add_dump_widget_children (text_art::tree_widget &,
1012 : node_dump_state &nds) const final override;
1013 :
1014 : void
1015 : accept_node_visitor (node_visitor &v) const final override;
1016 :
1017 : std::unique_ptr<json::object>
1018 : to_json () const final override;
1019 :
1020 : std::unique_ptr<diagnostics::markup::node>
1021 : make_markup_node (markup_context &markup_ctxt) const final override;
1022 :
1023 : string_scan
1024 : scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset)
1025 : const final override;
1026 :
1027 : void
1028 : get_representative_path_vars (const region_model *model,
1029 : value_set *visited,
1030 : const region *base_reg,
1031 : const svalue *sval,
1032 : tree desired_type,
1033 : logger *logger,
1034 : auto_vec<path_var> *out_pvs)
1035 : const final override;
1036 :
1037 : const bit_contents &
1038 : poison_any_pointers_to_descendents (const region *reg,
1039 : enum poison_kind pkind)
1040 : const final override;
1041 :
1042 : const bit_contents &
1043 : purge_state_involving (const symbolic::node &node) const final override;
1044 :
1045 : bool
1046 : bits_live_p (const bit_vector_from_ubc &bv_from_ubc) const final override;
1047 :
1048 : iter_result
1049 : for_each_value (iter_result (*cb) (const symbolic::value_node &val,
1050 : void *user_data),
1051 : void *user_data) const final override;
1052 :
1053 : const bit_contents *
1054 : maybe_fold_offset (const symbolic_bit_offset &bit_offset)
1055 : const final override;
1056 :
1057 : const bit_contents &
1058 4 : get_inner_bit_contents () const { return m_inner_bc; }
1059 :
1060 : const symbolic_bit_offset &
1061 4 : get_bit_offset () const { return m_bit_offset; }
1062 :
1063 : private:
1064 : const bit_contents &m_inner_bc;
1065 : const symbolic_bit_offset &m_bit_offset;
1066 : };
1067 :
1068 : /* A class with responsibility for allocating/consolidating
1069 : bit_contents instances. A singleton relative to a node_manager. */
1070 :
1071 : class bit_contents_manager
1072 : {
1073 : public:
1074 : bit_contents_manager (node_manager &node_mgr);
1075 :
1076 : bit_contents_manager (const bit_contents_manager &) = delete;
1077 :
1078 : const uninit_contents &
1079 4 : get_uninitialized () const { return m_uninit_contents; }
1080 :
1081 : const bit_contents &
1082 : get_untracked (value_set maybe_live);
1083 :
1084 : const zero_contents &
1085 206 : get_all_zeros () const { return m_zero_contents; }
1086 :
1087 : const bit_contents &
1088 : set_bits (const bit_contents &original,
1089 : const symbolic_bit_range &bit_range,
1090 : const bit_vector &bv,
1091 : uncertainty_t *uncertainty);
1092 :
1093 : const bit_contents &
1094 : set_bits (const bit_contents &original,
1095 : const concrete_bit_range &bit_range,
1096 : const bit_vector &bv,
1097 : uncertainty_t *uncertainty);
1098 :
1099 : const bit_contents &
1100 : get_concrete_bit_overlay (concrete_bit_overlay::key k,
1101 : uncertainty_t *uncertainty);
1102 :
1103 : const bit_contents &
1104 : get_symbolic_bit_overlay (symbolic_bit_overlay::key k,
1105 : uncertainty_t *uncertainty);
1106 :
1107 : const bit_contents &
1108 : get_bit_contents_for_constant (tree tree_cst);
1109 :
1110 : const bit_contents &
1111 : get_baseline_contents (const region &base_reg,
1112 : baseline_state bs);
1113 :
1114 : const bit_contents &
1115 : get_conjured_bit_contents (const region &base_reg,
1116 : const gimple *stmt,
1117 : const conjured_purge &p,
1118 : unsigned idx = 0);
1119 :
1120 : #if CHECKING_P
1121 : const bit_contents &
1122 : get_named_test_bit_contents (std::string name);
1123 : #endif
1124 :
1125 : const bit_contents &
1126 : get_offset_bit_contents (const bit_contents &inner_bc,
1127 : const symbolic_bit_offset &bit_offset);
1128 :
1129 : private:
1130 : const bit_contents &
1131 : make_bit_contents_for_constant (tree tree_cst);
1132 :
1133 : const bit_contents &
1134 : make_baseline_contents (baseline_key k);
1135 :
1136 : node_manager &m_node_mgr;
1137 :
1138 : uninit_contents m_uninit_contents;
1139 : zero_contents m_zero_contents;
1140 :
1141 : std::map<untracked_bit_contents::key,
1142 : std::unique_ptr<untracked_bit_contents>> m_untracked_bit_contents;
1143 :
1144 : std::map<concrete_bit_overlay::key,
1145 : std::unique_ptr<concrete_bit_overlay>> m_concrete_bit_overlays;
1146 :
1147 : std::map<symbolic_bit_overlay::key,
1148 : std::unique_ptr<symbolic_bit_overlay>> m_symbolic_bit_overlays;
1149 :
1150 : std::map<conjured_bit_contents::key,
1151 : std::unique_ptr<conjured_bit_contents>> m_conjured_map;
1152 : std::vector<std::unique_ptr<unfoldable_bit_contents>> m_unfoldable_bit_contents;
1153 :
1154 : std::map<offset_bit_contents::key,
1155 : std::unique_ptr<offset_bit_contents>> m_offset_map;
1156 :
1157 : // Cached lookups
1158 : std::map<tree, const bit_contents &> m_bit_contents_for_constants;
1159 : std::map<baseline_key, const bit_contents &> m_baseline_contents;
1160 : };
1161 :
1162 : } // namespace ana::symbolic
1163 : } // namespace ana
1164 :
1165 : #endif /* GCC_ANALYZER_SYMBOLIC_BIT_MAP_H */
|