Line data Source code
1 : /* Classes for modeling the state of memory.
2 : Copyright (C) 2020-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_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 :
122 : namespace 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 :
160 1025339 : class uncertainty_t
161 : {
162 : public:
163 : typedef hash_set<const svalue *>::iterator iterator;
164 :
165 19948 : void on_maybe_bound_sval (const svalue *sval)
166 : {
167 19948 : m_maybe_bound_svals.add (sval);
168 : }
169 31017 : void on_mutable_sval_at_unknown_call (const svalue *sval)
170 : {
171 31017 : m_mutable_at_unknown_call_svals.add (sval);
172 : }
173 :
174 830824 : bool unknown_sm_state_p (const svalue *sval)
175 : {
176 830824 : return (m_maybe_bound_svals.contains (sval)
177 830824 : || 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 :
183 430514 : iterator begin_maybe_bound_svals () const
184 : {
185 430514 : return m_maybe_bound_svals.begin ();
186 : }
187 444817 : iterator end_maybe_bound_svals () const
188 : {
189 444817 : return m_maybe_bound_svals.end ();
190 : }
191 :
192 : private:
193 :
194 : /* svalues that might or might not still be bound. */
195 : hash_set<const svalue *> m_maybe_bound_svals;
196 :
197 : /* svalues that have mutable sm-state at unknown calls. */
198 : hash_set<const svalue *> m_mutable_at_unknown_call_svals;
199 : };
200 :
201 : class byte_range;
202 : class concrete_binding;
203 : class 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 :
208 432251077 : class binding_key
209 : {
210 : public:
211 412152 : virtual ~binding_key () {}
212 : virtual bool concrete_p () const = 0;
213 10026244 : 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 :
224 6497 : virtual const concrete_binding *dyn_cast_concrete_binding () const
225 6497 : { return nullptr; }
226 345504 : virtual const symbolic_binding *dyn_cast_symbolic_binding () const
227 345504 : { return nullptr; }
228 : };
229 :
230 : /* A concrete range of bits. */
231 :
232 : struct bit_range
233 : {
234 2363693 : bit_range (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
235 16087298 : : m_start_bit_offset (start_bit_offset),
236 2486540 : 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 5705691 : bool empty_p () const
245 : {
246 1573243 : return m_size_in_bits == 0;
247 : }
248 :
249 26115061 : bit_offset_t get_start_bit_offset () const
250 : {
251 9093808 : return m_start_bit_offset;
252 : }
253 836551 : bit_offset_t get_next_bit_offset () const
254 : {
255 5746386 : return m_start_bit_offset + m_size_in_bits;
256 : }
257 4132448 : bit_offset_t get_last_bit_offset () const
258 : {
259 4132448 : gcc_assert (!empty_p ());
260 4132448 : return get_next_bit_offset () - 1;
261 : }
262 :
263 42270 : bool contains_p (bit_offset_t offset) const
264 : {
265 42270 : return (offset >= get_start_bit_offset ()
266 79361 : && offset < get_next_bit_offset ());
267 : }
268 :
269 : bool contains_p (const bit_range &other, bit_range *out) const;
270 :
271 64643261 : bool operator== (const bit_range &other) const
272 : {
273 64643261 : return (m_start_bit_offset == other.m_start_bit_offset
274 64643261 : && m_size_in_bits == other.m_size_in_bits);
275 : }
276 :
277 767595 : bool intersects_p (const bit_range &other) const
278 : {
279 767595 : return (get_start_bit_offset () < other.get_next_bit_offset ()
280 1526235 : && other.get_start_bit_offset () < 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 :
291 : bool falls_short_of_p (bit_offset_t offset,
292 : bit_range *out_fall_short_bits) const;
293 :
294 : static int cmp (const bit_range &br1, const bit_range &br2);
295 :
296 : bit_range operator- (bit_offset_t offset) const;
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 25620603 : operator< (const bit_range &other) const
304 : {
305 25620603 : if (m_start_bit_offset < other.m_start_bit_offset)
306 : return true;
307 15642488 : if (m_start_bit_offset > other.m_start_bit_offset)
308 : return false;
309 9743670 : return (m_size_in_bits < other.m_size_in_bits);
310 : }
311 :
312 87900548 : hashval_t hash () const
313 : {
314 87900548 : inchash::hash hstate;
315 87900548 : hstate.add_wide_int (m_start_bit_offset);
316 87900548 : hstate.add_wide_int (m_size_in_bits);
317 87900548 : return hstate.end ();
318 : }
319 :
320 : bit_offset_t m_start_bit_offset;
321 : bit_size_t m_size_in_bits;
322 : };
323 :
324 : /* A concrete range of bytes. */
325 :
326 : struct byte_range
327 : {
328 33338 : byte_range (byte_offset_t start_byte_offset, byte_size_t size_in_bytes)
329 27292 : : m_start_byte_offset (start_byte_offset),
330 24086 : m_size_in_bytes (size_in_bytes)
331 : {}
332 :
333 : void dump_to_pp (pretty_printer *pp) const;
334 : void dump () const;
335 :
336 : std::unique_ptr<json::object> to_json () const;
337 :
338 2855 : bool empty_p () const
339 : {
340 5710 : return m_size_in_bytes == 0;
341 : }
342 :
343 3070 : bool contains_p (byte_offset_t offset) const
344 : {
345 9210 : return (offset >= get_start_byte_offset ()
346 6134 : && offset < get_next_byte_offset ());
347 : }
348 : bool contains_p (const byte_range &other, byte_range *out) const;
349 :
350 : bool operator== (const byte_range &other) const
351 : {
352 : return (m_start_byte_offset == other.m_start_byte_offset
353 : && m_size_in_bytes == other.m_size_in_bytes);
354 : }
355 :
356 16574 : byte_offset_t get_start_byte_offset () const
357 : {
358 16574 : return m_start_byte_offset;
359 : }
360 4194 : byte_offset_t get_next_byte_offset () const
361 : {
362 4194 : return m_start_byte_offset + m_size_in_bytes;
363 : }
364 2855 : byte_offset_t get_last_byte_offset () const
365 : {
366 2855 : gcc_assert (!empty_p ());
367 2855 : return m_start_byte_offset + m_size_in_bytes - 1;
368 : }
369 :
370 770 : bit_range as_bit_range () const
371 : {
372 2310 : return bit_range (m_start_byte_offset * BITS_PER_UNIT,
373 770 : m_size_in_bytes * BITS_PER_UNIT);
374 : }
375 :
376 0 : bit_offset_t get_start_bit_offset () const
377 : {
378 0 : return m_start_byte_offset * BITS_PER_UNIT;
379 : }
380 0 : bit_offset_t get_next_bit_offset () const
381 : {
382 0 : return get_next_byte_offset () * BITS_PER_UNIT;
383 : }
384 :
385 : static int cmp (const byte_range &br1, const byte_range &br2);
386 :
387 : byte_offset_t m_start_byte_offset;
388 : byte_size_t m_size_in_bytes;
389 : };
390 :
391 : /* Concrete subclass of binding_key, for describing a non-empty
392 : concrete range of bits within the binding_map (e.g. "bits 8-15"). */
393 :
394 362378334 : class concrete_binding : public binding_key
395 : {
396 : public:
397 : /* This class is its own key for the purposes of consolidation. */
398 : typedef concrete_binding key_t;
399 :
400 13598436 : concrete_binding (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
401 13598436 : : m_bit_range (start_bit_offset, size_in_bits)
402 : {
403 13598436 : gcc_assert (m_bit_range.m_size_in_bits > 0);
404 13598436 : }
405 9591560 : bool concrete_p () const final override { return true; }
406 :
407 63349562 : hashval_t hash () const { return m_bit_range.hash (); }
408 60715917 : bool operator== (const concrete_binding &other) const
409 : {
410 60715917 : return m_bit_range == other.m_bit_range;
411 : }
412 :
413 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
414 :
415 804280 : const concrete_binding *dyn_cast_concrete_binding () const final override
416 804280 : { return this; }
417 :
418 7531228 : const bit_range &get_bit_range () const { return m_bit_range; }
419 : bool get_byte_range (byte_range *out) const;
420 :
421 407915 : bit_offset_t get_start_bit_offset () const
422 : {
423 400608 : return m_bit_range.m_start_bit_offset;
424 : }
425 84652 : bit_size_t get_size_in_bits () const
426 : {
427 84652 : return m_bit_range.m_size_in_bits;
428 : }
429 : /* Return the next bit offset after the end of this binding. */
430 244 : bit_offset_t get_next_bit_offset () const
431 : {
432 396966 : return m_bit_range.get_next_bit_offset ();
433 : }
434 :
435 : bool overlaps_p (const concrete_binding &other) const;
436 :
437 : static int cmp_ptr_ptr (const void *, const void *);
438 :
439 : void mark_deleted () { m_bit_range.m_size_in_bits = -1; }
440 60586 : void mark_empty () { m_bit_range.m_size_in_bits = -2; }
441 66294542 : bool is_deleted () const { return m_bit_range.m_size_in_bits == -1; }
442 232705614 : bool is_empty () const { return m_bit_range.m_size_in_bits == -2; }
443 :
444 : private:
445 : bit_range m_bit_range;
446 : };
447 :
448 : } // namespace ana
449 :
450 : template <>
451 : template <>
452 : inline bool
453 0 : is_a_helper <const ana::concrete_binding *>::test (const ana::binding_key *key)
454 : {
455 0 : return key->concrete_p ();
456 : }
457 :
458 : template <> struct default_hash_traits<ana::concrete_binding>
459 : : public member_function_hash_traits<ana::concrete_binding>
460 : {
461 : static const bool empty_zero_p = false;
462 : };
463 :
464 : namespace ana {
465 :
466 : /* Concrete subclass of binding_key, for describing a symbolic set of
467 : bits within the binding_map in terms of a region (e.g. "arr[i]"). */
468 :
469 41871785 : class symbolic_binding : public binding_key
470 : {
471 : public:
472 : /* This class is its own key for the purposes of consolidation. */
473 : typedef symbolic_binding key_t;
474 :
475 1820249 : symbolic_binding (const region *region) : m_region (region) {}
476 441084 : bool concrete_p () const final override { return false; }
477 :
478 9982688 : hashval_t hash () const
479 : {
480 9982688 : return (intptr_t)m_region;
481 : }
482 9805034 : bool operator== (const symbolic_binding &other) const
483 : {
484 9805034 : return m_region == other.m_region;
485 : }
486 :
487 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
488 :
489 29831 : const symbolic_binding *dyn_cast_symbolic_binding () const final override
490 29831 : { return this; }
491 :
492 381023 : const region *get_region () const { return m_region; }
493 :
494 : static int cmp_ptr_ptr (const void *, const void *);
495 :
496 : void mark_deleted () { m_region = reinterpret_cast<const region *> (1); }
497 0 : void mark_empty () { m_region = nullptr; }
498 10703465 : bool is_deleted () const
499 10703465 : { return m_region == reinterpret_cast<const region *> (1); }
500 : bool is_empty () const { return m_region == nullptr; }
501 :
502 : private:
503 : const region *m_region;
504 : };
505 :
506 : } // namespace ana
507 :
508 : template <> struct default_hash_traits<ana::symbolic_binding>
509 : : public member_function_hash_traits<ana::symbolic_binding>
510 : {
511 : static const bool empty_zero_p = true;
512 : };
513 :
514 : namespace ana {
515 :
516 : /* A mapping from binding_keys to svalues, for use by binding_cluster
517 : and compound_svalue.
518 : We store a map from concrete keys to svalues, which is ordered by
519 : the start offset.
520 : We also store a vector of (symbolic key, svalue) pairs, but for now
521 : this has maximum length of 1. */
522 :
523 : class binding_map
524 : {
525 : public:
526 : struct symbolic_binding
527 : {
528 167273 : bool operator== (const symbolic_binding &other) const
529 : {
530 167273 : return (m_region == other.m_region
531 167273 : && m_sval == other.m_sval);
532 : }
533 :
534 : const region *m_region;
535 : const svalue *m_sval;
536 : };
537 : using concrete_bindings_t = std::map<bit_range, const svalue *>;
538 : using symbolic_bindings_t = std::vector<symbolic_binding>;
539 :
540 : struct binding_pair
541 : {
542 11820916 : binding_pair (const binding_key *key,
543 : const svalue *sval)
544 : : m_key (key),
545 : m_sval (sval)
546 : {
547 : }
548 :
549 : const binding_key *m_key;
550 : const svalue *m_sval;
551 : };
552 :
553 : typedef class const_iterator
554 : {
555 : public:
556 33220354 : const_iterator (const binding_map &map,
557 : concrete_bindings_t::const_iterator concrete_iter,
558 : symbolic_bindings_t::const_iterator symbolic_iter)
559 33220354 : : m_map (map),
560 33220354 : m_concrete (concrete_iter),
561 33220354 : m_symbolic (symbolic_iter)
562 : {
563 : }
564 : bool operator== (const const_iterator &other) const;
565 25639939 : bool operator!= (const const_iterator &other) const
566 : {
567 6200703 : return !(*this == other);
568 : }
569 : const_iterator &operator++ ();
570 :
571 : binding_pair operator* ();
572 : const svalue *get_svalue () const;
573 :
574 : private:
575 : const binding_map &m_map;
576 : concrete_bindings_t::const_iterator m_concrete;
577 : symbolic_bindings_t::const_iterator m_symbolic;
578 : } const_iterator_t;
579 :
580 : typedef class iterator
581 : {
582 : public:
583 : friend class binding_map;
584 :
585 20704283 : iterator (const binding_map &map,
586 : concrete_bindings_t::iterator concrete_iter,
587 : symbolic_bindings_t::iterator symbolic_iter)
588 20704283 : : m_map (map),
589 20704283 : m_concrete (concrete_iter),
590 20704283 : m_symbolic (symbolic_iter)
591 : {
592 : }
593 : bool operator== (const iterator &other) const;
594 14772026 : bool operator!= (const iterator &other) const
595 : {
596 14772026 : return !(*this == other);
597 : }
598 : iterator &operator++ ();
599 :
600 : binding_pair operator* ();
601 :
602 : const binding_key *get_key () const;
603 :
604 : private:
605 : const binding_map &m_map;
606 : concrete_bindings_t::iterator m_concrete;
607 : symbolic_bindings_t::iterator m_symbolic;
608 : } iterator_t;
609 :
610 : binding_map (store_manager &store_mgr);
611 : binding_map (const binding_map &other);
612 : binding_map& operator=(const binding_map &other);
613 :
614 : bool operator== (const binding_map &other) const;
615 3306235 : bool operator!= (const binding_map &other) const
616 : {
617 3306235 : return !(*this == other);
618 : }
619 :
620 : hashval_t hash () const;
621 :
622 : const svalue *get (const binding_key *key) const;
623 : void put (const binding_key *k, const svalue *v);
624 : void overwrite (iterator_t &pos, const svalue *v);
625 :
626 : void remove (const binding_key *k);
627 22930 : void clear ()
628 : {
629 22930 : m_concrete.clear ();
630 22930 : m_symbolic.clear ();
631 22930 : }
632 :
633 179473 : bool empty_p () const
634 : {
635 95736 : return m_concrete.empty () && m_symbolic.empty ();
636 : }
637 :
638 : const_iterator_t begin () const;
639 : const_iterator_t end () const;
640 : iterator_t begin ();
641 : iterator_t end ();
642 : size_t elements () const;
643 :
644 : void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
645 : void dump (bool simple) const;
646 :
647 : void validate () const;
648 :
649 : std::unique_ptr<json::object> to_json () const;
650 :
651 : void add_to_tree_widget (text_art::tree_widget &parent_widget,
652 : const text_art::dump_widget_info &dwi) const;
653 :
654 : bool apply_ctor_to_region (const region *parent_reg, tree ctor,
655 : region_model_manager *mgr);
656 :
657 : static int cmp (const binding_map &map1, const binding_map &map2);
658 :
659 : void remove_overlapping_bindings (store_manager *mgr,
660 : const binding_key *drop_key,
661 : uncertainty_t *uncertainty,
662 : svalue_set *maybe_live_values,
663 : bool always_overlap);
664 :
665 : const concrete_bindings_t &
666 839470 : get_concrete_bindings () const { return m_concrete; }
667 :
668 : const symbolic_bindings_t &
669 1696 : get_symbolic_bindings () const { return m_symbolic; }
670 :
671 : private:
672 : void get_overlapping_bindings (const binding_key *key,
673 : auto_vec<const binding_key *> *out);
674 : bool apply_ctor_val_to_range (const region *parent_reg,
675 : region_model_manager *mgr,
676 : tree min_index, tree max_index,
677 : tree val);
678 : bool apply_ctor_pair_to_child_region (const region *parent_reg,
679 : region_model_manager *mgr,
680 : tree index, tree val);
681 :
682 : store_manager &m_store_mgr;
683 : concrete_bindings_t m_concrete;
684 : symbolic_bindings_t m_symbolic;
685 : };
686 :
687 : /* All of the bindings within a store for regions that share the same
688 : base region. */
689 :
690 30194456 : class binding_cluster
691 : {
692 : public:
693 : friend class store;
694 :
695 : typedef binding_map::const_iterator const_iterator_t;
696 : typedef binding_map::iterator iterator_t;
697 :
698 : binding_cluster (store_manager &store_mgr, const region *base_region);
699 : binding_cluster (const binding_cluster &other);
700 : binding_cluster& operator=(const binding_cluster &other);
701 :
702 : bool operator== (const binding_cluster &other) const;
703 3306235 : bool operator!= (const binding_cluster &other) const
704 : {
705 3306235 : return !(*this == other);
706 : }
707 :
708 : hashval_t hash () const;
709 :
710 : bool symbolic_p () const;
711 :
712 79169 : const region *get_base_region () const { return m_base_region; }
713 :
714 : void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
715 : void dump (bool simple) const;
716 :
717 : void validate () const;
718 :
719 : std::unique_ptr<json::object> to_json () const;
720 :
721 : std::unique_ptr<text_art::tree_widget>
722 : make_dump_widget (const text_art::dump_widget_info &dwi,
723 : store_manager *mgr) const;
724 :
725 : void bind (store_manager *mgr, const region *, const svalue *);
726 :
727 : void clobber_region (store_manager *mgr, const region *reg);
728 : void purge_region (store_manager *mgr, const region *reg);
729 : void fill_region (store_manager *mgr, const region *reg, const svalue *sval);
730 : void zero_fill_region (store_manager *mgr, const region *reg);
731 : void mark_region_as_unknown (store_manager *mgr,
732 : const region *reg_to_bind,
733 : const region *reg_for_overlap,
734 : uncertainty_t *uncertainty,
735 : svalue_set *maybe_live_values);
736 : void purge_state_involving (const svalue *sval,
737 : region_model_manager *sval_mgr);
738 :
739 : const svalue *get_binding (store_manager *mgr, const region *reg) const;
740 : const svalue *get_binding_recursive (store_manager *mgr,
741 : const region *reg) const;
742 : const svalue *get_any_binding (store_manager *mgr,
743 : const region *reg) const;
744 : const svalue *maybe_get_compound_binding (store_manager *mgr,
745 : const region *reg) const;
746 :
747 : void remove_overlapping_bindings (store_manager *mgr, const region *reg,
748 : uncertainty_t *uncertainty,
749 : svalue_set *maybe_live_values);
750 :
751 : template <typename T>
752 8580851 : void for_each_value (void (*cb) (const svalue *sval, T user_data),
753 : T user_data) const
754 : {
755 19439236 : for (auto iter = m_map.begin (); iter != m_map.end (); ++iter)
756 10858385 : cb (iter.get_svalue (), user_data);
757 8580851 : }
758 :
759 : static bool can_merge_p (const binding_cluster *cluster_a,
760 : const binding_cluster *cluster_b,
761 : binding_cluster *out_cluster,
762 : store *out_store,
763 : store_manager *mgr,
764 : model_merger *merger);
765 : void make_unknown_relative_to (const binding_cluster *other_cluster,
766 : store *out_store,
767 : store_manager *mgr);
768 :
769 : void mark_as_escaped ();
770 : void on_unknown_fncall (const gcall &call, store_manager *mgr,
771 : const conjured_purge &p);
772 : void on_asm (const gasm *stmt, store_manager *mgr,
773 : const conjured_purge &p);
774 :
775 : bool escaped_p () const;
776 238694 : bool touched_p () const { return m_touched; }
777 :
778 : bool redundant_p () const;
779 275659 : bool empty_p () const { return m_map.empty_p (); }
780 :
781 : void get_representative_path_vars (const region_model *model,
782 : svalue_set *visited,
783 : const region *base_reg,
784 : const svalue *sval,
785 : logger *logger,
786 : auto_vec<path_var> *out_pvs) const;
787 :
788 : const svalue *maybe_get_simple_value (store_manager *mgr) const;
789 :
790 32120 : const_iterator_t begin () const { return m_map.begin (); }
791 32120 : const_iterator_t end () const { return m_map.end (); }
792 :
793 137655 : iterator_t begin () { return m_map.begin (); }
794 273159 : iterator_t end () { return m_map.end (); }
795 :
796 3565 : const binding_map &get_map () const { return m_map; }
797 33 : binding_map &get_map () { return m_map; }
798 :
799 : private:
800 : const svalue *get_any_value (const binding_key *key) const;
801 : void bind_compound_sval (store_manager *mgr,
802 : const region *reg,
803 : const compound_svalue *compound_sval);
804 : void bind_key (const binding_key *key, const svalue *sval);
805 :
806 : const region *m_base_region;
807 :
808 : binding_map m_map;
809 :
810 : /* Has a pointer to this cluster "escaped" into a part of the program
811 : we don't know about (via a call to a function with an unknown body,
812 : or by being passed in as a pointer param of a "top-level" function call).
813 : Such regions could be overwritten when other such functions are called,
814 : even if the region is no longer reachable by pointers that we are
815 : tracking. */
816 : bool m_escaped;
817 :
818 : /* Has this cluster been written to via a symbolic binding?
819 : If so, then we don't know anything about unbound subregions,
820 : so we can't use initial_svalue, treat them as uninitialized, or
821 : inherit values from a parent region. */
822 : bool m_touched;
823 : };
824 :
825 : /* The mapping from regions to svalues.
826 : This is actually expressed by subdividing into clusters, to better
827 : handle aliasing. */
828 :
829 : class store
830 : {
831 : public:
832 : typedef hash_map <const region *, binding_cluster *> cluster_map_t;
833 :
834 : store ();
835 : store (const store &other);
836 : ~store ();
837 :
838 : store &operator= (const store &other);
839 :
840 : bool operator== (const store &other) const;
841 502470 : bool operator!= (const store &other) const
842 : {
843 502470 : return !(*this == other);
844 : }
845 :
846 : hashval_t hash () const;
847 :
848 : void dump_to_pp (pretty_printer *pp, bool summarize, bool multiline,
849 : store_manager *mgr) const;
850 : void dump (bool simple) const;
851 : void summarize_to_pp (pretty_printer *pp, bool simple) const;
852 :
853 : void validate () const;
854 :
855 : std::unique_ptr<json::object> to_json () const;
856 :
857 : std::unique_ptr<text_art::tree_widget>
858 : make_dump_widget (const text_art::dump_widget_info &dwi,
859 : store_manager *mgr) const;
860 :
861 : const svalue *get_any_binding (store_manager *mgr, const region *reg) const;
862 :
863 233289 : bool called_unknown_fn_p () const { return m_called_unknown_fn; }
864 :
865 : void set_value (store_manager *mgr, const region *lhs_reg,
866 : const svalue *rhs_sval,
867 : uncertainty_t *uncertainty);
868 : void clobber_region (store_manager *mgr, const region *reg);
869 : void purge_region (store_manager *mgr, const region *reg);
870 : void fill_region (store_manager *mgr, const region *reg, const svalue *sval);
871 : void zero_fill_region (store_manager *mgr, const region *reg);
872 : void mark_region_as_unknown (store_manager *mgr, const region *reg,
873 : uncertainty_t *uncertainty,
874 : svalue_set *maybe_live_values);
875 : void purge_state_involving (const svalue *sval,
876 : region_model_manager *sval_mgr);
877 :
878 : const binding_cluster *get_cluster (const region *base_reg) const;
879 : binding_cluster *get_cluster (const region *base_reg);
880 : binding_cluster *get_or_create_cluster (store_manager &store_mgr,
881 : const region *base_reg);
882 : void purge_cluster (const region *base_reg);
883 :
884 : template <typename T>
885 1397722 : void for_each_cluster (void (*cb) (const region *base_reg, T user_data),
886 : T user_data) const
887 : {
888 13228283 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
889 25058844 : iter != m_cluster_map.end (); ++iter)
890 11830561 : cb ((*iter).first, user_data);
891 1397722 : }
892 :
893 : static bool can_merge_p (const store *store_a, const store *store_b,
894 : store *out_store, store_manager *mgr,
895 : model_merger *merger);
896 :
897 : void mark_as_escaped (store_manager &mgr, const region *base_reg);
898 : void on_unknown_fncall (const gcall &call, store_manager *mgr,
899 : const conjured_purge &p);
900 : bool escaped_p (const region *reg) const;
901 :
902 : void get_representative_path_vars (const region_model *model,
903 : svalue_set *visited,
904 : const svalue *sval,
905 : logger *logger,
906 : auto_vec<path_var> *out_pvs) const;
907 :
908 1079407 : cluster_map_t::iterator begin () const { return m_cluster_map.begin (); }
909 9955220 : cluster_map_t::iterator end () const { return m_cluster_map.end (); }
910 :
911 : tristate eval_alias (const region *base_reg_a,
912 : const region *base_reg_b) const;
913 :
914 : void canonicalize (store_manager *mgr);
915 : void loop_replay_fixup (const store *other_store,
916 : region_model_manager *mgr);
917 :
918 : void replay_call_summary (call_summary_replay &r,
919 : const store &summary);
920 : void replay_call_summary_cluster (call_summary_replay &r,
921 : const store &summary,
922 : const region *base_reg);
923 : void on_maybe_live_values (store_manager &mgr,
924 : const svalue_set &maybe_live_values);
925 :
926 : private:
927 : void remove_overlapping_bindings (store_manager *mgr, const region *reg,
928 : uncertainty_t *uncertainty);
929 : tristate eval_alias_1 (const region *base_reg_a,
930 : const region *base_reg_b) const;
931 :
932 : cluster_map_t m_cluster_map;
933 :
934 : /* If this is true, then unknown code has been called, and so
935 : any global variable that isn't currently modelled by the store
936 : has unknown state, rather than being in an "initial state".
937 : This is to avoid having to mark (and thus explicitly track)
938 : every global when an unknown function is called; instead, they
939 : can be tracked implicitly. */
940 : bool m_called_unknown_fn;
941 : };
942 :
943 : /* A class responsible for owning and consolidating binding keys
944 : (both concrete and symbolic).
945 : Key instances are immutable as far as clients are concerned, so they
946 : are provided as "const" ptrs. */
947 :
948 3945 : class store_manager
949 : {
950 : public:
951 3945 : store_manager (region_model_manager *mgr) : m_mgr (mgr) {}
952 :
953 : logger *get_logger () const;
954 :
955 : /* binding consolidation. */
956 : const concrete_binding *
957 : get_concrete_binding (bit_offset_t start_bit_offset,
958 : bit_offset_t size_in_bits);
959 : const concrete_binding *
960 11338283 : get_concrete_binding (const bit_range &bits)
961 : {
962 11338283 : return get_concrete_binding (bits.get_start_bit_offset (),
963 11338283 : bits.m_size_in_bits);
964 : }
965 : const concrete_binding *
966 9 : get_concrete_binding (const byte_range &bytes)
967 : {
968 9 : bit_range bits = bytes.as_bit_range ();
969 9 : return get_concrete_binding (bits);
970 : }
971 : const symbolic_binding *
972 : get_symbolic_binding (const region *region);
973 :
974 6048018 : region_model_manager *get_svalue_manager () const
975 : {
976 6048018 : return m_mgr;
977 : }
978 :
979 : void log_stats (logger *logger, bool show_objs) const;
980 :
981 : private:
982 : region_model_manager *m_mgr;
983 : consolidation_map<concrete_binding> m_concrete_binding_key_mgr;
984 : consolidation_map<symbolic_binding> m_symbolic_binding_key_mgr;
985 : };
986 :
987 : } // namespace ana
988 :
989 : #endif /* GCC_ANALYZER_STORE_H */
|
