GCC Middle and Back End API Reference
store.h
Go to the documentation of this file.
1/* Classes for modeling the state of memory.
2 Copyright (C) 2020-2025 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it
8under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#ifndef GCC_ANALYZER_STORE_H
22#define GCC_ANALYZER_STORE_H
23
24#include "text-art/tree-widget.h"
25
26/* Implementation of the region-based ternary model described in:
27 "A Memory Model for Static Analysis of C Programs"
28 (Zhongxing Xu, Ted Kremenek, and Jian Zhang)
29 http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf */
30
31/* The store models memory as a collection of "clusters", where regions
32 are partitioned into clusters via their base region.
33
34 For example, given:
35 int a, b, c;
36 struct coord { double x; double y; } verts[3];
37 then "verts[0].y" and "verts[1].x" both have "verts" as their base region.
38 Each of a, b, c, and verts will have their own clusters, so that we
39 know that writes to e.g. "verts[1].x".don't affect e.g. "a".
40
41 Within each cluster we store a map of bindings to values, where the
42 binding keys can be either concrete or symbolic.
43
44 Concrete bindings affect a specific range of bits relative to the start
45 of the base region of the cluster, whereas symbolic bindings affect
46 a specific subregion within the cluster.
47
48 Consider (from the symbolic-1.c testcase):
49
50 char arr[1024];
51 arr[2] = a; (1)
52 arr[3] = b; (2)
53 After (1) and (2), the cluster for "arr" has concrete bindings
54 for bits 16-23 and for bits 24-31, with svalues "INIT_VAL(a)"
55 and "INIT_VAL(b)" respectively:
56 cluster: {bits 16-23: "INIT_VAL(a)",
57 bits 24-31: "INIT_VAL(b)";
58 flags: {}}
59 Attempting to query unbound subregions e.g. arr[4] will
60 return "UNINITIALIZED".
61 "a" and "b" are each in their own clusters, with no explicit
62 bindings, and thus implicitly have value INIT_VAL(a) and INIT_VAL(b).
63
64 arr[3] = c; (3)
65 After (3), the concrete binding for bits 24-31 is replaced with the
66 svalue "INIT_VAL(c)":
67 cluster: {bits 16-23: "INIT_VAL(a)", (from before)
68 bits 24-31: "INIT_VAL(c)"; (updated)
69 flags: {}}
70
71 arr[i] = d; (4)
72 After (4), we lose the concrete bindings and replace them with a
73 symbolic binding for "arr[i]", with svalue "INIT_VAL(d)". We also
74 mark the cluster as having been "symbolically touched": future
75 attempts to query the values of subregions other than "arr[i]",
76 such as "arr[3]" are "UNKNOWN", since we don't know if the write
77 to arr[i] affected them.
78 cluster: {symbolic_key(arr[i]): "INIT_VAL(d)";
79 flags: {TOUCHED}}
80
81 arr[j] = e; (5)
82 After (5), we lose the symbolic binding for "arr[i]" since we could
83 have overwritten it, and add a symbolic binding for "arr[j]".
84 cluster: {symbolic_key(arr[j]): "INIT_VAL(d)"; (different symbolic
85 flags: {TOUCHED}} binding)
86
87 arr[3] = f; (6)
88 After (6), we lose the symbolic binding for "arr[j]" since we could
89 have overwritten it, and gain a concrete binding for bits 24-31
90 again, this time with svalue "INIT_VAL(e)":
91 cluster: {bits 24-31: "INIT_VAL(d)";
92 flags: {TOUCHED}}
93 The cluster is still flagged as touched, so that we know that
94 accesses to other elements are "UNKNOWN" rather than
95 "UNINITIALIZED".
96
97 Handling symbolic regions requires us to handle aliasing.
98
99 In the first example above, each of a, b, c and verts are non-symbolic
100 base regions and so their clusters are "concrete clusters", whereas given:
101 struct coord *p, *q;
102 then "*p" and "*q" are symbolic base regions, and thus "*p" and "*q"
103 have "symbolic clusters".
104
105 In the above, "verts[i].x" will have a symbolic *binding* within a
106 concrete cluster for "verts", whereas "*p" is a symbolic *cluster*.
107
108 Writes to concrete clusters can't affect other concrete clusters,
109 but can affect symbolic clusters; e.g. after:
110 verts[0].x = 42;
111 we bind 42 in the cluster for "verts", but the clusters for "b" and "c"
112 can't be affected. Any symbolic clusters for *p and for *q can be
113 affected, *p and *q could alias verts.
114
115 Writes to a symbolic cluster can affect other clusters, both
116 concrete and symbolic; e.g. after:
117 p->x = 17;
118 we bind 17 within the cluster for "*p". The concrete clusters for a, b,
119 c, and verts could be affected, depending on whether *p aliases them.
120 Similarly, the symbolic cluster to *q could be affected. */
121
122namespace ana {
123
124/* A class for keeping track of aspects of a program_state that we don't
125 know about, to avoid false positives about leaks.
126
127 Consider:
128
129 p->field = malloc (1024);
130 q->field = NULL;
131
132 where we don't know whether or not p and q point to the same memory,
133 and:
134
135 p->field = malloc (1024);
136 unknown_fn (p);
137
138 In both cases, the svalue for the address of the allocated buffer
139 goes from being bound to p->field to not having anything explicitly bound
140 to it.
141
142 Given that we conservatively discard bindings due to possible aliasing or
143 calls to unknown function, the store loses references to svalues,
144 but these svalues could still be live. We don't want to warn about
145 them leaking - they're effectively in a "maybe live" state.
146
147 This "maybe live" information is somewhat transient.
148
149 We don't want to store this "maybe live" information in the program_state,
150 region_model, or store, since we don't want to bloat these objects (and
151 potentially bloat the exploded_graph with more nodes).
152 However, we can't store it in the region_model_context, as these context
153 objects sometimes don't last long enough to be around when comparing the
154 old vs the new state.
155
156 This class is a way to track a set of such svalues, so that we can
157 temporarily capture that they are in a "maybe live" state whilst
158 comparing old and new states. */
159
161{
162public:
164
165 void on_maybe_bound_sval (const svalue *sval)
166 {
167 m_maybe_bound_svals.add (sval);
168 }
170 {
172 }
173
174 bool unknown_sm_state_p (const svalue *sval)
175 {
176 return (m_maybe_bound_svals.contains (sval)
177 || m_mutable_at_unknown_call_svals.contains (sval));
178 }
179
180 void dump_to_pp (pretty_printer *pp, bool simple) const;
181 void dump (bool simple) const;
182
184 {
185 return m_maybe_bound_svals.begin ();
186 }
188 {
189 return m_maybe_bound_svals.end ();
190 }
191
192private:
193
194 /* svalues that might or might not still be bound. */
196
197 /* svalues that have mutable sm-state at unknown calls. */
199};
200
201class byte_range;
202class concrete_binding;
203class symbolic_binding;
204
205/* Abstract base class for describing ranges of bits within a binding_map
206 that can have svalues bound to them. */
207
209{
210public:
211 virtual ~binding_key () {}
212 virtual bool concrete_p () const = 0;
213 bool symbolic_p () const { return !concrete_p (); }
214
215 static const binding_key *make (store_manager *mgr, const region *r);
216
217 virtual void dump_to_pp (pretty_printer *pp, bool simple) const = 0;
218 void dump (bool simple) const;
219 label_text get_desc (bool simple=true) const;
220
221 static int cmp_ptrs (const void *, const void *);
222 static int cmp (const binding_key *, const binding_key *);
223
225 { return nullptr; }
227 { return nullptr; }
228};
229
230/* A concrete range of bits. */
231
233{
234 bit_range (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
235 : m_start_bit_offset (start_bit_offset),
236 m_size_in_bits (size_in_bits)
237 {}
238
239 void dump_to_pp (pretty_printer *pp) const;
240 void dump () const;
241
242 std::unique_ptr<json::object> to_json () const;
243
244 bool empty_p () const
245 {
246 return m_size_in_bits == 0;
247 }
248
250 {
251 return m_start_bit_offset;
252 }
258 {
259 gcc_assert (!empty_p ());
260 return get_next_bit_offset () - 1;
261 }
262
263 bool contains_p (bit_offset_t offset) const
264 {
265 return (offset >= get_start_bit_offset ()
266 && offset < get_next_bit_offset ());
267 }
268
269 bool contains_p (const bit_range &other, bit_range *out) const;
270
271 bool operator== (const bit_range &other) const
272 {
274 && m_size_in_bits == other.m_size_in_bits);
275 }
276
277 bool intersects_p (const bit_range &other) const
278 {
279 return (get_start_bit_offset () < other.get_next_bit_offset ()
281 }
282 bool intersects_p (const bit_range &other,
283 bit_size_t *out_num_overlap_bits) const;
284 bool intersects_p (const bit_range &other,
285 bit_range *out_this,
286 bit_range *out_other) const;
287
288 bool exceeds_p (const bit_range &other,
289 bit_range *out_overhanging_bit_range) const;
290
292 bit_range *out_fall_short_bits) const;
293
294 static int cmp (const bit_range &br1, const bit_range &br2);
295
297
298 static bool from_mask (unsigned HOST_WIDE_INT mask, bit_range *out);
299
300 bool as_byte_range (byte_range *out) const;
301
302 bool
303 operator< (const bit_range &other) const
304 {
306 return true;
308 return false;
309 return (m_size_in_bits < other.m_size_in_bits);
310 }
311
314};
315
316/* A concrete range of bytes. */
317
319{
321 : m_start_byte_offset (start_byte_offset),
323 {}
324
325 void dump_to_pp (pretty_printer *pp) const;
326 void dump () const;
327
328 std::unique_ptr<json::object> to_json () const;
329
330 bool empty_p () const
331 {
332 return m_size_in_bytes == 0;
333 }
334
335 bool contains_p (byte_offset_t offset) const
336 {
337 return (offset >= get_start_byte_offset ()
338 && offset < get_next_byte_offset ());
339 }
340 bool contains_p (const byte_range &other, byte_range *out) const;
341
342 bool operator== (const byte_range &other) const
343 {
345 && m_size_in_bytes == other.m_size_in_bytes);
346 }
347
361
363 {
364 return bit_range (m_start_byte_offset * BITS_PER_UNIT,
365 m_size_in_bytes * BITS_PER_UNIT);
366 }
367
369 {
370 return m_start_byte_offset * BITS_PER_UNIT;
371 }
373 {
374 return get_next_byte_offset () * BITS_PER_UNIT;
375 }
376
377 static int cmp (const byte_range &br1, const byte_range &br2);
378
381};
382
383/* Concrete subclass of binding_key, for describing a non-empty
384 concrete range of bits within the binding_map (e.g. "bits 8-15"). */
385
387{
388public:
389 /* This class is its own key for the purposes of consolidation. */
391
392 concrete_binding (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
393 : m_bit_range (start_bit_offset, size_in_bits)
394 {
395 gcc_assert (m_bit_range.m_size_in_bits > 0);
396 }
397 bool concrete_p () const final override { return true; }
398
399 hashval_t hash () const
400 {
401 inchash::hash hstate;
402 hstate.add_wide_int (m_bit_range.m_start_bit_offset);
403 hstate.add_wide_int (m_bit_range.m_size_in_bits);
404 return hstate.end ();
405 }
406 bool operator== (const concrete_binding &other) const
407 {
408 return m_bit_range == other.m_bit_range;
409 }
410
411 void dump_to_pp (pretty_printer *pp, bool simple) const final override;
412
414 { return this; }
415
416 const bit_range &get_bit_range () const { return m_bit_range; }
417 bool get_byte_range (byte_range *out) const;
418
420 {
421 return m_bit_range.m_start_bit_offset;
422 }
424 {
425 return m_bit_range.m_size_in_bits;
426 }
427 /* Return the next bit offset after the end of this binding. */
429 {
430 return m_bit_range.get_next_bit_offset ();
431 }
432
433 bool overlaps_p (const concrete_binding &other) const;
434
435 static int cmp_ptr_ptr (const void *, const void *);
436
437 void mark_deleted () { m_bit_range.m_size_in_bits = -1; }
438 void mark_empty () { m_bit_range.m_size_in_bits = -2; }
439 bool is_deleted () const { return m_bit_range.m_size_in_bits == -1; }
440 bool is_empty () const { return m_bit_range.m_size_in_bits == -2; }
441
442private:
444};
445
446} // namespace ana
447
448template <>
449template <>
450inline bool
452{
453 return key->concrete_p ();
454}
455
457: public member_function_hash_traits<ana::concrete_binding>
458{
459 static const bool empty_zero_p = false;
460};
461
462namespace ana {
463
464/* Concrete subclass of binding_key, for describing a symbolic set of
465 bits within the binding_map in terms of a region (e.g. "arr[i]"). */
466
468{
469public:
470 /* This class is its own key for the purposes of consolidation. */
472
474 bool concrete_p () const final override { return false; }
475
476 hashval_t hash () const
477 {
478 return (intptr_t)m_region;
479 }
480 bool operator== (const symbolic_binding &other) const
481 {
482 return m_region == other.m_region;
483 }
484
485 void dump_to_pp (pretty_printer *pp, bool simple) const final override;
486
488 { return this; }
489
490 const region *get_region () const { return m_region; }
491
492 static int cmp_ptr_ptr (const void *, const void *);
493
494 void mark_deleted () { m_region = reinterpret_cast<const region *> (1); }
495 void mark_empty () { m_region = nullptr; }
496 bool is_deleted () const
497 { return m_region == reinterpret_cast<const region *> (1); }
498 bool is_empty () const { return m_region == nullptr; }
499
500private:
502};
503
504} // namespace ana
505
507: public member_function_hash_traits<ana::symbolic_binding>
508{
509 static const bool empty_zero_p = true;
510};
511
512namespace ana {
513
514/* A mapping from binding_keys to svalues, for use by binding_cluster
515 and compound_svalue. */
516
518{
519public:
520 typedef hash_map <const binding_key *, const svalue *> map_t;
521 typedef map_t::iterator iterator_t;
522
524 binding_map (const binding_map &other);
526
527 bool operator== (const binding_map &other) const;
528 bool operator!= (const binding_map &other) const
529 {
530 return !(*this == other);
531 }
532
533 hashval_t hash () const;
534
535 const svalue *get (const binding_key *key) const
536 {
537 const svalue **slot = const_cast<map_t &> (m_map).get (key);
538 if (slot)
539 return *slot;
540 else
541 return nullptr;
542 }
543 bool put (const binding_key *k, const svalue *v)
544 {
545 gcc_assert (v);
546 return m_map.put (k, v);
547 }
548
549 void remove (const binding_key *k) { m_map.remove (k); }
550 void empty () { m_map.empty (); }
551
552 iterator_t begin () const { return m_map.begin (); }
553 iterator_t end () const { return m_map.end (); }
554 size_t elements () const { return m_map.elements (); }
555
556 void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
557 void dump (bool simple) const;
558
559 std::unique_ptr<json::object> to_json () const;
560
561 void add_to_tree_widget (text_art::tree_widget &parent_widget,
562 const text_art::dump_widget_info &dwi) const;
563
564 bool apply_ctor_to_region (const region *parent_reg, tree ctor,
566
567 static int cmp (const binding_map &map1, const binding_map &map2);
568
570 const binding_key *drop_key,
571 uncertainty_t *uncertainty,
572 svalue_set *maybe_live_values,
573 bool always_overlap);
574
575private:
578 bool apply_ctor_val_to_range (const region *parent_reg,
580 tree min_index, tree max_index,
581 tree val);
584 tree index, tree val);
585
587};
588
589/* Concept: BindingVisitor, for use by binding_cluster::for_each_binding
590 and store::for_each_binding.
591
592 Should implement:
593 void on_binding (const binding_key *key, const svalue *&sval);
594*/
595
596/* All of the bindings within a store for regions that share the same
597 base region. */
598
600{
601public:
602 friend class store;
603
604 typedef hash_map <const binding_key *, const svalue *> map_t;
605 typedef map_t::iterator iterator_t;
606
607 binding_cluster (const region *base_region);
610
611 bool operator== (const binding_cluster &other) const;
612 bool operator!= (const binding_cluster &other) const
613 {
614 return !(*this == other);
615 }
616
617 hashval_t hash () const;
618
619 bool symbolic_p () const;
620
621 const region *get_base_region () const { return m_base_region; }
622
623 void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
624 void dump (bool simple) const;
625
626 void validate () const;
627
628 std::unique_ptr<json::object> to_json () const;
629
630 std::unique_ptr<text_art::tree_widget>
631 make_dump_widget (const text_art::dump_widget_info &dwi,
632 store_manager *mgr) const;
633
634 void bind (store_manager *mgr, const region *, const svalue *);
635
636 void clobber_region (store_manager *mgr, const region *reg);
637 void purge_region (store_manager *mgr, const region *reg);
638 void fill_region (store_manager *mgr, const region *reg, const svalue *sval);
639 void zero_fill_region (store_manager *mgr, const region *reg);
641 const region *reg_to_bind,
642 const region *reg_for_overlap,
643 uncertainty_t *uncertainty,
644 svalue_set *maybe_live_values);
645 void purge_state_involving (const svalue *sval,
646 region_model_manager *sval_mgr);
647
648 const svalue *get_binding (store_manager *mgr, const region *reg) const;
650 const region *reg) const;
652 const region *reg) const;
654 const region *reg) const;
655
657 uncertainty_t *uncertainty,
658 svalue_set *maybe_live_values);
659
660 template <typename T>
661 void for_each_value (void (*cb) (const svalue *sval, T user_data),
662 T user_data) const
663 {
664 for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
665 cb ((*iter).second, user_data);
666 }
667
668 static bool can_merge_p (const binding_cluster *cluster_a,
669 const binding_cluster *cluster_b,
670 binding_cluster *out_cluster,
671 store *out_store,
672 store_manager *mgr,
673 model_merger *merger);
674 void make_unknown_relative_to (const binding_cluster *other_cluster,
675 store *out_store,
676 store_manager *mgr);
677
679 void on_unknown_fncall (const gcall &call, store_manager *mgr,
680 const conjured_purge &p);
681 void on_asm (const gasm *stmt, store_manager *mgr,
682 const conjured_purge &p);
683
684 bool escaped_p () const;
685 bool touched_p () const { return m_touched; }
686
687 bool redundant_p () const;
688 bool empty_p () const { return m_map.elements () == 0; }
689
692 const region *base_reg,
693 const svalue *sval,
694 logger *logger,
695 auto_vec<path_var> *out_pvs) const;
696
698
699 template <typename BindingVisitor>
700 void for_each_binding (BindingVisitor &v) const
701 {
702 for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
703 {
704 const binding_key *key = (*iter).first;
705 const svalue *&sval = (*iter).second;
706 v.on_binding (key, sval);
707 }
708 }
709
710 iterator_t begin () const { return m_map.begin (); }
711 iterator_t end () const { return m_map.end (); }
712
713 const binding_map &get_map () const { return m_map; }
714
715private:
716 const svalue *get_any_value (const binding_key *key) const;
718 const region *reg,
719 const compound_svalue *compound_sval);
720 void bind_key (const binding_key *key, const svalue *sval);
721
723
725
726 /* Has a pointer to this cluster "escaped" into a part of the program
727 we don't know about (via a call to a function with an unknown body,
728 or by being passed in as a pointer param of a "top-level" function call).
729 Such regions could be overwritten when other such functions are called,
730 even if the region is no longer reachable by pointers that we are
731 tracking. */
733
734 /* Has this cluster been written to via a symbolic binding?
735 If so, then we don't know anything about unbound subregions,
736 so we can't use initial_svalue, treat them as uninitialized, or
737 inherit values from a parent region. */
739};
740
741/* The mapping from regions to svalues.
742 This is actually expressed by subdividing into clusters, to better
743 handle aliasing. */
744
745class store
746{
747public:
748 typedef hash_map <const region *, binding_cluster *> cluster_map_t;
749
751 store (const store &other);
753
754 store &operator= (const store &other);
755
756 bool operator== (const store &other) const;
757 bool operator!= (const store &other) const
758 {
759 return !(*this == other);
760 }
761
762 hashval_t hash () const;
763
764 void dump_to_pp (pretty_printer *pp, bool summarize, bool multiline,
765 store_manager *mgr) const;
766 void dump (bool simple) const;
767 void summarize_to_pp (pretty_printer *pp, bool simple) const;
768
769 void validate () const;
770
771 std::unique_ptr<json::object> to_json () const;
772
773 std::unique_ptr<text_art::tree_widget>
774 make_dump_widget (const text_art::dump_widget_info &dwi,
775 store_manager *mgr) const;
776
777 const svalue *get_any_binding (store_manager *mgr, const region *reg) const;
778
779 bool called_unknown_fn_p () const { return m_called_unknown_fn; }
780
781 void set_value (store_manager *mgr, const region *lhs_reg,
782 const svalue *rhs_sval,
783 uncertainty_t *uncertainty);
784 void clobber_region (store_manager *mgr, const region *reg);
785 void purge_region (store_manager *mgr, const region *reg);
786 void fill_region (store_manager *mgr, const region *reg, const svalue *sval);
787 void zero_fill_region (store_manager *mgr, const region *reg);
789 uncertainty_t *uncertainty,
790 svalue_set *maybe_live_values);
791 void purge_state_involving (const svalue *sval,
792 region_model_manager *sval_mgr);
793
794 const binding_cluster *get_cluster (const region *base_reg) const;
797 void purge_cluster (const region *base_reg);
798
799 template <typename T>
800 void for_each_cluster (void (*cb) (const region *base_reg, T user_data),
801 T user_data) const
802 {
803 for (cluster_map_t::iterator iter = m_cluster_map.begin ();
804 iter != m_cluster_map.end (); ++iter)
805 cb ((*iter).first, user_data);
806 }
807
808 static bool can_merge_p (const store *store_a, const store *store_b,
809 store *out_store, store_manager *mgr,
810 model_merger *merger);
811
812 void mark_as_escaped (const region *base_reg);
813 void on_unknown_fncall (const gcall &call, store_manager *mgr,
814 const conjured_purge &p);
815 bool escaped_p (const region *reg) const;
816
819 const svalue *sval,
820 logger *logger,
821 auto_vec<path_var> *out_pvs) const;
822
823 cluster_map_t::iterator begin () const { return m_cluster_map.begin (); }
824 cluster_map_t::iterator end () const { return m_cluster_map.end (); }
825
826 tristate eval_alias (const region *base_reg_a,
827 const region *base_reg_b) const;
828
829 template <typename BindingVisitor>
830 void for_each_binding (BindingVisitor &v)
831 {
832 for (cluster_map_t::iterator iter = m_cluster_map.begin ();
833 iter != m_cluster_map.end (); ++iter)
834 (*iter).second->for_each_binding (v);
835 }
836
838 void loop_replay_fixup (const store *other_store,
840
842 const store &summary);
844 const store &summary,
845 const region *base_reg);
846 void on_maybe_live_values (const svalue_set &maybe_live_values);
847
848private:
850 uncertainty_t *uncertainty);
851 tristate eval_alias_1 (const region *base_reg_a,
852 const region *base_reg_b) const;
853
855
856 /* If this is true, then unknown code has been called, and so
857 any global variable that isn't currently modelled by the store
858 has unknown state, rather than being in an "initial state".
859 This is to avoid having to mark (and thus explicitly track)
860 every global when an unknown function is called; instead, they
861 can be tracked implicitly. */
863};
864
865/* A class responsible for owning and consolidating binding keys
866 (both concrete and symbolic).
867 Key instances are immutable as far as clients are concerned, so they
868 are provided as "const" ptrs. */
869
871{
872public:
874
876
877 /* binding consolidation. */
878 const concrete_binding *
880 bit_offset_t size_in_bits);
881 const concrete_binding *
883 {
885 bits.m_size_in_bits);
886 }
887 const concrete_binding *
889 {
890 bit_range bits = bytes.as_bit_range ();
891 return get_concrete_binding (bits);
892 }
893 const symbolic_binding *
895
897 {
898 return m_mgr;
899 }
900
901 void log_stats (logger *logger, bool show_objs) const;
902
903private:
907};
908
909} // namespace ana
910
911#endif /* GCC_ANALYZER_STORE_H */
Definition store.h:600
binding_map m_map
Definition store.h:724
void bind(store_manager *mgr, const region *, const svalue *)
void dump(bool simple) const
void get_representative_path_vars(const region_model *model, svalue_set *visited, const region *base_reg, const svalue *sval, logger *logger, auto_vec< path_var > *out_pvs) const
void fill_region(store_manager *mgr, const region *reg, const svalue *sval)
void on_asm(const gasm *stmt, store_manager *mgr, const conjured_purge &p)
const svalue * get_binding_recursive(store_manager *mgr, const region *reg) const
map_t::iterator iterator_t
Definition store.h:605
void for_each_value(void(*cb)(const svalue *sval, T user_data), T user_data) const
Definition store.h:661
void bind_compound_sval(store_manager *mgr, const region *reg, const compound_svalue *compound_sval)
std::unique_ptr< text_art::tree_widget > make_dump_widget(const text_art::dump_widget_info &dwi, store_manager *mgr) const
bool m_escaped
Definition store.h:732
friend class store
Definition store.h:602
void mark_region_as_unknown(store_manager *mgr, const region *reg_to_bind, const region *reg_for_overlap, uncertainty_t *uncertainty, svalue_set *maybe_live_values)
binding_cluster(const binding_cluster &other)
hashval_t hash() const
void validate() const
bool symbolic_p() const
void purge_region(store_manager *mgr, const region *reg)
void clobber_region(store_manager *mgr, const region *reg)
void make_unknown_relative_to(const binding_cluster *other_cluster, store *out_store, store_manager *mgr)
bool operator==(const binding_cluster &other) const
void bind_key(const binding_key *key, const svalue *sval)
bool empty_p() const
Definition store.h:688
const svalue * get_any_binding(store_manager *mgr, const region *reg) const
iterator_t end() const
Definition store.h:711
bool operator!=(const binding_cluster &other) const
Definition store.h:612
hash_map< const binding_key *, const svalue * > map_t
Definition store.h:604
binding_cluster & operator=(const binding_cluster &other)
void purge_state_involving(const svalue *sval, region_model_manager *sval_mgr)
const svalue * get_any_value(const binding_key *key) const
void dump_to_pp(pretty_printer *pp, bool simple, bool multiline) const
const region * get_base_region() const
Definition store.h:621
const region * m_base_region
Definition store.h:722
const svalue * maybe_get_compound_binding(store_manager *mgr, const region *reg) const
bool touched_p() const
Definition store.h:685
const binding_map & get_map() const
Definition store.h:713
void for_each_binding(BindingVisitor &v) const
Definition store.h:700
bool escaped_p() const
iterator_t begin() const
Definition store.h:710
std::unique_ptr< json::object > to_json() const
void remove_overlapping_bindings(store_manager *mgr, const region *reg, uncertainty_t *uncertainty, svalue_set *maybe_live_values)
void zero_fill_region(store_manager *mgr, const region *reg)
const svalue * get_binding(store_manager *mgr, const region *reg) const
static bool can_merge_p(const binding_cluster *cluster_a, const binding_cluster *cluster_b, binding_cluster *out_cluster, store *out_store, store_manager *mgr, model_merger *merger)
void on_unknown_fncall(const gcall &call, store_manager *mgr, const conjured_purge &p)
bool redundant_p() const
bool m_touched
Definition store.h:738
const svalue * maybe_get_simple_value(store_manager *mgr) const
binding_cluster(const region *base_region)
Definition store.h:209
void dump(bool simple) const
static const binding_key * make(store_manager *mgr, const region *r)
static int cmp_ptrs(const void *, const void *)
virtual const symbolic_binding * dyn_cast_symbolic_binding() const
Definition store.h:226
virtual bool concrete_p() const =0
virtual void dump_to_pp(pretty_printer *pp, bool simple) const =0
virtual ~binding_key()
Definition store.h:211
bool symbolic_p() const
Definition store.h:213
static int cmp(const binding_key *, const binding_key *)
label_text get_desc(bool simple=true) const
virtual const concrete_binding * dyn_cast_concrete_binding() const
Definition store.h:224
Definition store.h:518
size_t elements() const
Definition store.h:554
binding_map & operator=(const binding_map &other)
map_t m_map
Definition store.h:586
static int cmp(const binding_map &map1, const binding_map &map2)
iterator_t begin() const
Definition store.h:552
void dump_to_pp(pretty_printer *pp, bool simple, bool multiline) const
void get_overlapping_bindings(const binding_key *key, auto_vec< const binding_key * > *out)
bool operator==(const binding_map &other) const
hash_map< const binding_key *, const svalue * > map_t
Definition store.h:520
bool apply_ctor_pair_to_child_region(const region *parent_reg, region_model_manager *mgr, tree index, tree val)
void dump(bool simple) const
hashval_t hash() const
void empty()
Definition store.h:550
const svalue * get(const binding_key *key) const
Definition store.h:535
std::unique_ptr< json::object > to_json() const
bool apply_ctor_val_to_range(const region *parent_reg, region_model_manager *mgr, tree min_index, tree max_index, tree val)
bool apply_ctor_to_region(const region *parent_reg, tree ctor, region_model_manager *mgr)
void add_to_tree_widget(text_art::tree_widget &parent_widget, const text_art::dump_widget_info &dwi) const
bool operator!=(const binding_map &other) const
Definition store.h:528
void remove_overlapping_bindings(store_manager *mgr, const binding_key *drop_key, uncertainty_t *uncertainty, svalue_set *maybe_live_values, bool always_overlap)
binding_map()
Definition store.h:523
void remove(const binding_key *k)
Definition store.h:549
bool put(const binding_key *k, const svalue *v)
Definition store.h:543
iterator_t end() const
Definition store.h:553
map_t::iterator iterator_t
Definition store.h:521
binding_map(const binding_map &other)
Definition call-summary.h:68
Definition svalue.h:1392
Definition store.h:387
bit_size_t get_size_in_bits() const
Definition store.h:423
bool get_byte_range(byte_range *out) const
void mark_empty()
Definition store.h:438
concrete_binding(bit_offset_t start_bit_offset, bit_size_t size_in_bits)
Definition store.h:392
concrete_binding key_t
Definition store.h:390
const bit_range & get_bit_range() const
Definition store.h:416
void dump_to_pp(pretty_printer *pp, bool simple) const final override
bit_offset_t get_next_bit_offset() const
Definition store.h:428
bool operator==(const concrete_binding &other) const
Definition store.h:406
bool concrete_p() const final override
Definition store.h:397
bit_range m_bit_range
Definition store.h:443
bool is_empty() const
Definition store.h:440
bit_offset_t get_start_bit_offset() const
Definition store.h:419
bool is_deleted() const
Definition store.h:439
void mark_deleted()
Definition store.h:437
bool overlaps_p(const concrete_binding &other) const
hashval_t hash() const
Definition store.h:399
const concrete_binding * dyn_cast_concrete_binding() const final override
Definition store.h:413
static int cmp_ptr_ptr(const void *, const void *)
Definition svalue.h:1493
Definition analyzer-logging.h:34
Definition region-model-manager.h:32
Definition region-model.h:298
Definition region.h:126
Definition store.h:871
consolidation_map< symbolic_binding > m_symbolic_binding_key_mgr
Definition store.h:906
const concrete_binding * get_concrete_binding(const bit_range &bits)
Definition store.h:882
const concrete_binding * get_concrete_binding(bit_offset_t start_bit_offset, bit_offset_t size_in_bits)
const concrete_binding * get_concrete_binding(const byte_range &bytes)
Definition store.h:888
region_model_manager * m_mgr
Definition store.h:904
logger * get_logger() const
region_model_manager * get_svalue_manager() const
Definition store.h:896
store_manager(region_model_manager *mgr)
Definition store.h:873
consolidation_map< concrete_binding > m_concrete_binding_key_mgr
Definition store.h:905
void log_stats(logger *logger, bool show_objs) const
const symbolic_binding * get_symbolic_binding(const region *region)
std::unique_ptr< json::object > to_json() const
void purge_state_involving(const svalue *sval, region_model_manager *sval_mgr)
void dump(bool simple) const
bool escaped_p(const region *reg) const
store(const store &other)
void fill_region(store_manager *mgr, const region *reg, const svalue *sval)
void mark_as_escaped(const region *base_reg)
void purge_region(store_manager *mgr, const region *reg)
tristate eval_alias(const region *base_reg_a, const region *base_reg_b) const
void summarize_to_pp(pretty_printer *pp, bool simple) const
bool operator==(const store &other) const
store & operator=(const store &other)
hash_map< const region *, binding_cluster * > cluster_map_t
Definition store.h:748
void replay_call_summary_cluster(call_summary_replay &r, const store &summary, const region *base_reg)
void for_each_binding(BindingVisitor &v)
Definition store.h:830
cluster_map_t::iterator end() const
Definition store.h:824
std::unique_ptr< text_art::tree_widget > make_dump_widget(const text_art::dump_widget_info &dwi, store_manager *mgr) const
void get_representative_path_vars(const region_model *model, svalue_set *visited, const svalue *sval, logger *logger, auto_vec< path_var > *out_pvs) const
bool m_called_unknown_fn
Definition store.h:862
void loop_replay_fixup(const store *other_store, region_model_manager *mgr)
binding_cluster * get_or_create_cluster(const region *base_reg)
static bool can_merge_p(const store *store_a, const store *store_b, store *out_store, store_manager *mgr, model_merger *merger)
bool operator!=(const store &other) const
Definition store.h:757
bool called_unknown_fn_p() const
Definition store.h:779
void on_maybe_live_values(const svalue_set &maybe_live_values)
void set_value(store_manager *mgr, const region *lhs_reg, const svalue *rhs_sval, uncertainty_t *uncertainty)
cluster_map_t m_cluster_map
Definition store.h:854
const binding_cluster * get_cluster(const region *base_reg) const
void zero_fill_region(store_manager *mgr, const region *reg)
tristate eval_alias_1(const region *base_reg_a, const region *base_reg_b) const
void validate() const
void mark_region_as_unknown(store_manager *mgr, const region *reg, uncertainty_t *uncertainty, svalue_set *maybe_live_values)
void canonicalize(store_manager *mgr)
cluster_map_t::iterator begin() const
Definition store.h:823
const svalue * get_any_binding(store_manager *mgr, const region *reg) const
hashval_t hash() const
binding_cluster * get_cluster(const region *base_reg)
void replay_call_summary(call_summary_replay &r, const store &summary)
void dump_to_pp(pretty_printer *pp, bool summarize, bool multiline, store_manager *mgr) const
void purge_cluster(const region *base_reg)
void for_each_cluster(void(*cb)(const region *base_reg, T user_data), T user_data) const
Definition store.h:800
void remove_overlapping_bindings(store_manager *mgr, const region *reg, uncertainty_t *uncertainty)
void clobber_region(store_manager *mgr, const region *reg)
void on_unknown_fncall(const gcall &call, store_manager *mgr, const conjured_purge &p)
Definition svalue.h:92
Definition store.h:468
void dump_to_pp(pretty_printer *pp, bool simple) const final override
bool is_empty() const
Definition store.h:498
void mark_empty()
Definition store.h:495
bool operator==(const symbolic_binding &other) const
Definition store.h:480
bool concrete_p() const final override
Definition store.h:474
symbolic_binding(const region *region)
Definition store.h:473
symbolic_binding key_t
Definition store.h:471
const symbolic_binding * dyn_cast_symbolic_binding() const final override
Definition store.h:487
const region * get_region() const
Definition store.h:490
bool is_deleted() const
Definition store.h:496
hashval_t hash() const
Definition store.h:476
const region * m_region
Definition store.h:501
static int cmp_ptr_ptr(const void *, const void *)
void mark_deleted()
Definition store.h:494
Definition store.h:161
bool unknown_sm_state_p(const svalue *sval)
Definition store.h:174
void dump(bool simple) const
void dump_to_pp(pretty_printer *pp, bool simple) const
void on_mutable_sval_at_unknown_call(const svalue *sval)
Definition store.h:169
iterator end_maybe_bound_svals() const
Definition store.h:187
hash_set< const svalue * > m_mutable_at_unknown_call_svals
Definition store.h:198
void on_maybe_bound_sval(const svalue *sval)
Definition store.h:165
hash_set< constsvalue * >::iterator iterator
Definition store.h:163
iterator begin_maybe_bound_svals() const
Definition store.h:183
hash_set< const svalue * > m_maybe_bound_svals
Definition store.h:195
Definition vec.h:1667
Definition common.h:554
Definition hash-set.h:110
Definition hash-set.h:37
Definition inchash.h:38
hashval_t end() const
Definition inchash.h:49
void add_wide_int(const generic_wide_int< T > &x)
Definition inchash.h:84
Definition pretty-print.h:241
Definition lra-spills.cc:101
Definition tristate.h:26
union tree_node * tree
Definition coretypes.h:97
void final(rtx_insn *first, FILE *file, int optimize_p)
Definition final.cc:2008
static struct token T
Definition gengtype-parse.cc:45
Definition access-diagram.h:30
offset_int byte_size_t
Definition common.h:199
@ stmt
Definition checker-event.h:37
offset_int bit_offset_t
Definition common.h:196
offset_int byte_offset_t
Definition common.h:198
offset_int bit_size_t
Definition common.h:197
hash_set< const svalue * > svalue_set
Definition common.h:80
poly_int< N, C > r
Definition poly-int.h:774
Definition store.h:233
bit_range operator-(bit_offset_t offset) const
bool operator==(const bit_range &other) const
Definition store.h:271
std::unique_ptr< json::object > to_json() const
bool exceeds_p(const bit_range &other, bit_range *out_overhanging_bit_range) const
bool empty_p() const
Definition store.h:244
bool intersects_p(const bit_range &other) const
Definition store.h:277
static bool from_mask(unsigned HOST_WIDE_INT mask, bit_range *out)
bool falls_short_of_p(bit_offset_t offset, bit_range *out_fall_short_bits) const
bool operator<(const bit_range &other) const
Definition store.h:303
bool intersects_p(const bit_range &other, bit_range *out_this, bit_range *out_other) const
bit_size_t m_size_in_bits
Definition store.h:313
bool contains_p(bit_offset_t offset) const
Definition store.h:263
bit_offset_t get_next_bit_offset() const
Definition store.h:253
bit_offset_t m_start_bit_offset
Definition store.h:312
bool intersects_p(const bit_range &other, bit_size_t *out_num_overlap_bits) const
void dump_to_pp(pretty_printer *pp) const
bit_range(bit_offset_t start_bit_offset, bit_size_t size_in_bits)
Definition store.h:234
bool as_byte_range(byte_range *out) const
void dump() const
static int cmp(const bit_range &br1, const bit_range &br2)
bool contains_p(const bit_range &other, bit_range *out) const
bit_offset_t get_start_bit_offset() const
Definition store.h:249
bit_offset_t get_last_bit_offset() const
Definition store.h:257
Definition store.h:319
bool operator==(const byte_range &other) const
Definition store.h:342
byte_offset_t get_next_byte_offset() const
Definition store.h:352
byte_size_t m_size_in_bytes
Definition store.h:380
byte_offset_t get_last_byte_offset() const
Definition store.h:356
bool contains_p(byte_offset_t offset) const
Definition store.h:335
byte_offset_t get_start_byte_offset() const
Definition store.h:348
void dump_to_pp(pretty_printer *pp) const
void dump() const
byte_range(byte_offset_t start_byte_offset, byte_size_t size_in_bytes)
Definition store.h:320
static int cmp(const byte_range &br1, const byte_range &br2)
bit_offset_t get_start_bit_offset() const
Definition store.h:368
byte_offset_t m_start_byte_offset
Definition store.h:379
bool contains_p(const byte_range &other, byte_range *out) const
bool empty_p() const
Definition store.h:330
bit_offset_t get_next_bit_offset() const
Definition store.h:372
std::unique_ptr< json::object > to_json() const
bit_range as_bit_range() const
Definition store.h:362
Definition region-model.h:1243
static const bool empty_zero_p
Definition store.h:459
static const bool empty_zero_p
Definition store.h:509
Definition hash-traits.h:466
Definition gimple.h:549
Definition gimple.h:352
static bool test(U *p)
Definition common.h:533
#define gcc_assert(EXPR)
Definition system.h:814
static bitmap visited
Definition tree-ssa-dce.cc:640
tree size_in_bytes(const_tree t)
Definition tree.h:5195