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-2024 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 {
168 }
173
174 bool unknown_sm_state_p (const svalue *sval)
175 {
176 return (m_maybe_bound_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 NULL; }
227 { return NULL; }
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
264 {
265 return (offset >= get_start_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
304};
305
306/* A concrete range of bytes. */
307
309{
311 : m_start_byte_offset (start_byte_offset),
313 {}
314
315 void dump_to_pp (pretty_printer *pp) const;
316 void dump () const;
317
318 std::unique_ptr<json::object> to_json () const;
319
320 bool empty_p () const
321 {
322 return m_size_in_bytes == 0;
323 }
324
326 {
327 return (offset >= get_start_byte_offset ()
329 }
330 bool contains_p (const byte_range &other, byte_range *out) const;
331
332 bool operator== (const byte_range &other) const
333 {
335 && m_size_in_bytes == other.m_size_in_bytes);
336 }
337
351
353 {
354 return bit_range (m_start_byte_offset * BITS_PER_UNIT,
355 m_size_in_bytes * BITS_PER_UNIT);
356 }
357
359 {
360 return m_start_byte_offset * BITS_PER_UNIT;
361 }
363 {
364 return get_next_byte_offset () * BITS_PER_UNIT;
365 }
366
367 static int cmp (const byte_range &br1, const byte_range &br2);
368
371};
372
373/* Concrete subclass of binding_key, for describing a non-empty
374 concrete range of bits within the binding_map (e.g. "bits 8-15"). */
375
377{
378public:
379 /* This class is its own key for the purposes of consolidation. */
381
382 concrete_binding (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
383 : m_bit_range (start_bit_offset, size_in_bits)
384 {
386 }
387 bool concrete_p () const final override { return true; }
388
389 hashval_t hash () const
390 {
391 inchash::hash hstate;
394 return hstate.end ();
395 }
396 bool operator== (const concrete_binding &other) const
397 {
398 return m_bit_range == other.m_bit_range;
399 }
400
401 void dump_to_pp (pretty_printer *pp, bool simple) const final override;
402
404 { return this; }
405
406 const bit_range &get_bit_range () const { return m_bit_range; }
407 bool get_byte_range (byte_range *out) const;
408
414 {
416 }
417 /* Return the next bit offset after the end of this binding. */
422
423 bool overlaps_p (const concrete_binding &other) const;
424
425 static int cmp_ptr_ptr (const void *, const void *);
426
429 bool is_deleted () const { return m_bit_range.m_size_in_bits == -1; }
430 bool is_empty () const { return m_bit_range.m_size_in_bits == -2; }
431
432private:
434};
435
436} // namespace ana
437
438template <>
439template <>
440inline bool
442{
443 return key->concrete_p ();
444}
445
446template <> struct default_hash_traits<ana::concrete_binding>
447: public member_function_hash_traits<ana::concrete_binding>
448{
449 static const bool empty_zero_p = false;
450};
451
452namespace ana {
453
454/* Concrete subclass of binding_key, for describing a symbolic set of
455 bits within the binding_map in terms of a region (e.g. "arr[i]"). */
456
458{
459public:
460 /* This class is its own key for the purposes of consolidation. */
462
464 bool concrete_p () const final override { return false; }
465
466 hashval_t hash () const
467 {
468 return (intptr_t)m_region;
469 }
470 bool operator== (const symbolic_binding &other) const
471 {
472 return m_region == other.m_region;
473 }
474
475 void dump_to_pp (pretty_printer *pp, bool simple) const final override;
476
478 { return this; }
479
480 const region *get_region () const { return m_region; }
481
482 static int cmp_ptr_ptr (const void *, const void *);
483
484 void mark_deleted () { m_region = reinterpret_cast<const region *> (1); }
485 void mark_empty () { m_region = NULL; }
486 bool is_deleted () const
487 { return m_region == reinterpret_cast<const region *> (1); }
488 bool is_empty () const { return m_region == NULL; }
489
490private:
492};
493
494} // namespace ana
495
496template <> struct default_hash_traits<ana::symbolic_binding>
497: public member_function_hash_traits<ana::symbolic_binding>
498{
499 static const bool empty_zero_p = true;
500};
501
502namespace ana {
503
504/* A mapping from binding_keys to svalues, for use by binding_cluster
505 and compound_svalue. */
506
508{
509public:
510 typedef hash_map <const binding_key *, const svalue *> map_t;
511 typedef map_t::iterator iterator_t;
512
514 binding_map (const binding_map &other);
516
517 bool operator== (const binding_map &other) const;
518 bool operator!= (const binding_map &other) const
519 {
520 return !(*this == other);
521 }
522
523 hashval_t hash () const;
524
525 const svalue *get (const binding_key *key) const
526 {
527 const svalue **slot = const_cast<map_t &> (m_map).get (key);
528 if (slot)
529 return *slot;
530 else
531 return NULL;
532 }
533 bool put (const binding_key *k, const svalue *v)
534 {
535 gcc_assert (v);
536 return m_map.put (k, v);
537 }
538
539 void remove (const binding_key *k) { m_map.remove (k); }
540 void empty () { m_map.empty (); }
541
542 iterator_t begin () const { return m_map.begin (); }
543 iterator_t end () const { return m_map.end (); }
544 size_t elements () const { return m_map.elements (); }
545
546 void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
547 void dump (bool simple) const;
548
549 std::unique_ptr<json::object> to_json () const;
550
551 void add_to_tree_widget (text_art::tree_widget &parent_widget,
552 const text_art::dump_widget_info &dwi) const;
553
554 bool apply_ctor_to_region (const region *parent_reg, tree ctor,
556
557 static int cmp (const binding_map &map1, const binding_map &map2);
558
560 const binding_key *drop_key,
561 uncertainty_t *uncertainty,
562 svalue_set *maybe_live_values,
563 bool always_overlap);
564
565private:
568 bool apply_ctor_val_to_range (const region *parent_reg,
570 tree min_index, tree max_index,
571 tree val);
574 tree index, tree val);
575
577};
578
579/* Concept: BindingVisitor, for use by binding_cluster::for_each_binding
580 and store::for_each_binding.
581
582 Should implement:
583 void on_binding (const binding_key *key, const svalue *&sval);
584*/
585
586/* All of the bindings within a store for regions that share the same
587 base region. */
588
590{
591public:
592 friend class store;
593
594 typedef hash_map <const binding_key *, const svalue *> map_t;
595 typedef map_t::iterator iterator_t;
596
597 binding_cluster (const region *base_region);
600
601 bool operator== (const binding_cluster &other) const;
602 bool operator!= (const binding_cluster &other) const
603 {
604 return !(*this == other);
605 }
606
607 hashval_t hash () const;
608
609 bool symbolic_p () const;
610
611 const region *get_base_region () const { return m_base_region; }
612
613 void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
614 void dump (bool simple) const;
615
616 void validate () const;
617
618 std::unique_ptr<json::object> to_json () const;
619
620 std::unique_ptr<text_art::tree_widget>
621 make_dump_widget (const text_art::dump_widget_info &dwi,
622 store_manager *mgr) const;
623
624 void bind (store_manager *mgr, const region *, const svalue *);
625
626 void clobber_region (store_manager *mgr, const region *reg);
627 void purge_region (store_manager *mgr, const region *reg);
628 void fill_region (store_manager *mgr, const region *reg, const svalue *sval);
629 void zero_fill_region (store_manager *mgr, const region *reg);
631 const region *reg_to_bind,
632 const region *reg_for_overlap,
633 uncertainty_t *uncertainty,
634 svalue_set *maybe_live_values);
635 void purge_state_involving (const svalue *sval,
636 region_model_manager *sval_mgr);
637
638 const svalue *get_binding (store_manager *mgr, const region *reg) const;
640 const region *reg) const;
642 const region *reg) const;
644 const region *reg) const;
645
647 uncertainty_t *uncertainty,
648 svalue_set *maybe_live_values);
649
650 template <typename T>
651 void for_each_value (void (*cb) (const svalue *sval, T user_data),
652 T user_data) const
653 {
654 for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
655 cb ((*iter).second, user_data);
656 }
657
658 static bool can_merge_p (const binding_cluster *cluster_a,
659 const binding_cluster *cluster_b,
660 binding_cluster *out_cluster,
661 store *out_store,
662 store_manager *mgr,
663 model_merger *merger);
664 void make_unknown_relative_to (const binding_cluster *other_cluster,
665 store *out_store,
666 store_manager *mgr);
667
669 void on_unknown_fncall (const gcall *call, store_manager *mgr,
670 const conjured_purge &p);
671 void on_asm (const gasm *stmt, store_manager *mgr,
672 const conjured_purge &p);
673
674 bool escaped_p () const;
675 bool touched_p () const { return m_touched; }
676
677 bool redundant_p () const;
678 bool empty_p () const { return m_map.elements () == 0; }
679
682 const region *base_reg,
683 const svalue *sval,
684 logger *logger,
685 auto_vec<path_var> *out_pvs) const;
686
688
689 template <typename BindingVisitor>
690 void for_each_binding (BindingVisitor &v) const
691 {
692 for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
693 {
694 const binding_key *key = (*iter).first;
695 const svalue *&sval = (*iter).second;
696 v.on_binding (key, sval);
697 }
698 }
699
700 iterator_t begin () const { return m_map.begin (); }
701 iterator_t end () const { return m_map.end (); }
702
703 const binding_map &get_map () const { return m_map; }
704
705private:
706 const svalue *get_any_value (const binding_key *key) const;
708 const region *reg,
709 const compound_svalue *compound_sval);
710 void bind_key (const binding_key *key, const svalue *sval);
711
713
715
716 /* Has a pointer to this cluster "escaped" into a part of the program
717 we don't know about (via a call to a function with an unknown body,
718 or by being passed in as a pointer param of a "top-level" function call).
719 Such regions could be overwritten when other such functions are called,
720 even if the region is no longer reachable by pointers that we are
721 tracking. */
723
724 /* Has this cluster been written to via a symbolic binding?
725 If so, then we don't know anything about unbound subregions,
726 so we can't use initial_svalue, treat them as uninitialized, or
727 inherit values from a parent region. */
729};
730
731/* The mapping from regions to svalues.
732 This is actually expressed by subdividing into clusters, to better
733 handle aliasing. */
734
735class store
736{
737public:
738 typedef hash_map <const region *, binding_cluster *> cluster_map_t;
739
741 store (const store &other);
743
744 store &operator= (const store &other);
745
746 bool operator== (const store &other) const;
747 bool operator!= (const store &other) const
748 {
749 return !(*this == other);
750 }
751
752 hashval_t hash () const;
753
754 void dump_to_pp (pretty_printer *pp, bool summarize, bool multiline,
755 store_manager *mgr) const;
756 void dump (bool simple) const;
757 void summarize_to_pp (pretty_printer *pp, bool simple) const;
758
759 void validate () const;
760
761 std::unique_ptr<json::object> to_json () const;
762
763 std::unique_ptr<text_art::tree_widget>
764 make_dump_widget (const text_art::dump_widget_info &dwi,
765 store_manager *mgr) const;
766
767 const svalue *get_any_binding (store_manager *mgr, const region *reg) const;
768
769 bool called_unknown_fn_p () const { return m_called_unknown_fn; }
770
771 void set_value (store_manager *mgr, const region *lhs_reg,
772 const svalue *rhs_sval,
773 uncertainty_t *uncertainty);
774 void clobber_region (store_manager *mgr, const region *reg);
775 void purge_region (store_manager *mgr, const region *reg);
776 void fill_region (store_manager *mgr, const region *reg, const svalue *sval);
777 void zero_fill_region (store_manager *mgr, const region *reg);
779 uncertainty_t *uncertainty,
780 svalue_set *maybe_live_values);
781 void purge_state_involving (const svalue *sval,
782 region_model_manager *sval_mgr);
783
784 const binding_cluster *get_cluster (const region *base_reg) const;
787 void purge_cluster (const region *base_reg);
788
789 template <typename T>
790 void for_each_cluster (void (*cb) (const region *base_reg, T user_data),
791 T user_data) const
792 {
793 for (cluster_map_t::iterator iter = m_cluster_map.begin ();
794 iter != m_cluster_map.end (); ++iter)
795 cb ((*iter).first, user_data);
796 }
797
798 static bool can_merge_p (const store *store_a, const store *store_b,
799 store *out_store, store_manager *mgr,
800 model_merger *merger);
801
802 void mark_as_escaped (const region *base_reg);
803 void on_unknown_fncall (const gcall *call, store_manager *mgr,
804 const conjured_purge &p);
805 bool escaped_p (const region *reg) const;
806
809 const svalue *sval,
810 logger *logger,
811 auto_vec<path_var> *out_pvs) const;
812
813 cluster_map_t::iterator begin () const { return m_cluster_map.begin (); }
814 cluster_map_t::iterator end () const { return m_cluster_map.end (); }
815
816 tristate eval_alias (const region *base_reg_a,
817 const region *base_reg_b) const;
818
819 template <typename BindingVisitor>
820 void for_each_binding (BindingVisitor &v)
821 {
822 for (cluster_map_t::iterator iter = m_cluster_map.begin ();
823 iter != m_cluster_map.end (); ++iter)
824 (*iter).second->for_each_binding (v);
825 }
826
828 void loop_replay_fixup (const store *other_store,
830
832 const store &summary);
834 const store &summary,
835 const region *base_reg);
836 void on_maybe_live_values (const svalue_set &maybe_live_values);
837
838private:
840 uncertainty_t *uncertainty);
841 tristate eval_alias_1 (const region *base_reg_a,
842 const region *base_reg_b) const;
843
845
846 /* If this is true, then unknown code has been called, and so
847 any global variable that isn't currently modelled by the store
848 has unknown state, rather than being in an "initial state".
849 This is to avoid having to mark (and thus explicitly track)
850 every global when an unknown function is called; instead, they
851 can be tracked implicitly. */
853};
854
855/* A class responsible for owning and consolidating binding keys
856 (both concrete and symbolic).
857 Key instances are immutable as far as clients are concerned, so they
858 are provided as "const" ptrs. */
859
861{
862public:
864
866
867 /* binding consolidation. */
868 const concrete_binding *
870 bit_offset_t size_in_bits);
871 const concrete_binding *
873 {
875 bits.m_size_in_bits);
876 }
877 const concrete_binding *
879 {
880 bit_range bits = bytes.as_bit_range ();
881 return get_concrete_binding (bits);
882 }
883 const symbolic_binding *
885
887 {
888 return m_mgr;
889 }
890
891 void log_stats (logger *logger, bool show_objs) const;
892
893private:
897};
898
899} // namespace ana
900
901#endif /* GCC_ANALYZER_STORE_H */
Definition store.h:590
binding_map m_map
Definition store.h:714
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
void for_each_value(void(*cb)(const svalue *sval, T user_data), T user_data) const
Definition store.h:651
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:722
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)
void on_unknown_fncall(const gcall *call, store_manager *mgr, const conjured_purge &p)
bool operator==(const binding_cluster &other) const
hash_map< const binding_key *, const svalue * > map_t
Definition store.h:594
void bind_key(const binding_key *key, const svalue *sval)
bool empty_p() const
Definition store.h:678
const svalue * get_any_binding(store_manager *mgr, const region *reg) const
iterator_t end() const
Definition store.h:701
bool operator!=(const binding_cluster &other) const
Definition store.h:602
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
map_t::iterator iterator_t
Definition store.h:595
const region * get_base_region() const
Definition store.h:611
const region * m_base_region
Definition store.h:712
const svalue * maybe_get_compound_binding(store_manager *mgr, const region *reg) const
bool touched_p() const
Definition store.h:675
const binding_map & get_map() const
Definition store.h:703
void for_each_binding(BindingVisitor &v) const
Definition store.h:690
bool escaped_p() const
iterator_t begin() const
Definition store.h:700
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)
bool redundant_p() const
bool m_touched
Definition store.h:728
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:508
size_t elements() const
Definition store.h:544
binding_map & operator=(const binding_map &other)
map_t m_map
Definition store.h:576
static int cmp(const binding_map &map1, const binding_map &map2)
iterator_t begin() const
Definition store.h:542
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
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:540
const svalue * get(const binding_key *key) const
Definition store.h:525
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
map_t::iterator iterator_t
Definition store.h:511
hash_map< const binding_key *, const svalue * > map_t
Definition store.h:510
bool operator!=(const binding_map &other) const
Definition store.h:518
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:513
void remove(const binding_key *k)
Definition store.h:539
bool put(const binding_key *k, const svalue *v)
Definition store.h:533
iterator_t end() const
Definition store.h:543
binding_map(const binding_map &other)
Definition call-summary.h:68
Definition svalue.h:1389
Definition store.h:377
bit_size_t get_size_in_bits() const
Definition store.h:413
bool get_byte_range(byte_range *out) const
void mark_empty()
Definition store.h:428
concrete_binding(bit_offset_t start_bit_offset, bit_size_t size_in_bits)
Definition store.h:382
const bit_range & get_bit_range() const
Definition store.h:406
void dump_to_pp(pretty_printer *pp, bool simple) const final override
concrete_binding key_t
Definition store.h:380
bit_offset_t get_next_bit_offset() const
Definition store.h:418
bool operator==(const concrete_binding &other) const
Definition store.h:396
bool concrete_p() const final override
Definition store.h:387
bit_range m_bit_range
Definition store.h:433
bool is_empty() const
Definition store.h:430
bit_offset_t get_start_bit_offset() const
Definition store.h:409
bool is_deleted() const
Definition store.h:429
void mark_deleted()
Definition store.h:427
bool overlaps_p(const concrete_binding &other) const
hashval_t hash() const
Definition store.h:389
const concrete_binding * dyn_cast_concrete_binding() const final override
Definition store.h:403
static int cmp_ptr_ptr(const void *, const void *)
Definition svalue.h:1490
Definition analyzer-logging.h:34
Definition region-model-manager.h:32
Definition region-model.h:263
Definition region.h:126
Definition store.h:861
consolidation_map< symbolic_binding > m_symbolic_binding_key_mgr
Definition store.h:896
const concrete_binding * get_concrete_binding(const bit_range &bits)
Definition store.h:872
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:878
region_model_manager * m_mgr
Definition store.h:894
logger * get_logger() const
region_model_manager * get_svalue_manager() const
Definition store.h:886
store_manager(region_model_manager *mgr)
Definition store.h:863
consolidation_map< concrete_binding > m_concrete_binding_key_mgr
Definition store.h:895
void log_stats(logger *logger, bool show_objs) const
const symbolic_binding * get_symbolic_binding(const region *region)
Definition store.h:736
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
hash_map< const region *, binding_cluster * > cluster_map_t
Definition store.h:738
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)
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:820
cluster_map_t::iterator end() const
Definition store.h:814
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:852
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:747
bool called_unknown_fn_p() const
Definition store.h:769
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:844
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:813
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 on_unknown_fncall(const gcall *call, store_manager *mgr, const conjured_purge &p)
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:790
void remove_overlapping_bindings(store_manager *mgr, const region *reg, uncertainty_t *uncertainty)
void clobber_region(store_manager *mgr, const region *reg)
Definition svalue.h:92
Definition store.h:458
symbolic_binding key_t
Definition store.h:461
void dump_to_pp(pretty_printer *pp, bool simple) const final override
bool is_empty() const
Definition store.h:488
void mark_empty()
Definition store.h:485
bool operator==(const symbolic_binding &other) const
Definition store.h:470
bool concrete_p() const final override
Definition store.h:464
symbolic_binding(const region *region)
Definition store.h:463
const symbolic_binding * dyn_cast_symbolic_binding() const final override
Definition store.h:477
const region * get_region() const
Definition store.h:480
bool is_deleted() const
Definition store.h:486
hashval_t hash() const
Definition store.h:466
const region * m_region
Definition store.h:491
static int cmp_ptr_ptr(const void *, const void *)
void mark_deleted()
Definition store.h:484
Definition store.h:161
bool unknown_sm_state_p(const svalue *sval)
Definition store.h:174
hash_set< constsvalue * >::iterator iterator
Definition store.h:163
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
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:1656
Definition analyzer.h:529
iterator begin() const
Definition hash-map.h:302
void empty()
Definition hash-map.h:249
size_t elements() const
Definition hash-map.h:247
void remove(const Key &k)
Definition hash-map.h:218
iterator end() const
Definition hash-map.h:303
bool put(const Key &k, const Value &v)
Definition hash-map.h:168
Definition hash-set.h:110
Definition hash-set.h:37
iterator begin() const
Definition hash-set.h:140
iterator end() const
Definition hash-set.h:141
bool contains(const Key &k)
Definition hash-set.h:73
bool add(const Key &k)
Definition hash-set.h:56
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:2004
Definition access-diagram.h:30
offset_int byte_size_t
Definition analyzer.h:182
offset_int bit_offset_t
Definition analyzer.h:179
offset_int byte_offset_t
Definition analyzer.h:181
offset_int bit_size_t
Definition analyzer.h:180
poly_int< N, C > r
Definition poly-int.h:774
rtx offset
Definition postreload.cc:691
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 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:303
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:302
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:309
bool operator==(const byte_range &other) const
Definition store.h:332
byte_offset_t get_next_byte_offset() const
Definition store.h:342
byte_size_t m_size_in_bytes
Definition store.h:370
byte_offset_t get_last_byte_offset() const
Definition store.h:346
bool contains_p(byte_offset_t offset) const
Definition store.h:325
byte_offset_t get_start_byte_offset() const
Definition store.h:338
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:310
static int cmp(const byte_range &br1, const byte_range &br2)
bit_offset_t get_start_bit_offset() const
Definition store.h:358
byte_offset_t m_start_byte_offset
Definition store.h:369
bool contains_p(const byte_range &other, byte_range *out) const
bool empty_p() const
Definition store.h:320
bit_offset_t get_next_bit_offset() const
Definition store.h:362
std::unique_ptr< json::object > to_json() const
bit_range as_bit_range() const
Definition store.h:352
Definition region-model.h:1132
Definition hash-traits.h:466
Definition gimple.h:549
Definition gimple.h:352
static bool test(U *p)
Definition analyzer.h:508
#define NULL
Definition system.h:50
#define gcc_assert(EXPR)
Definition system.h:814
static bitmap visited
Definition tree-ssa-dce.cc:577
tree size_in_bytes(const_tree t)
Definition tree.h:5131