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 : #include "analyzer/complexity.h"
26 :
27 : /* Implementation of the region-based ternary model described in:
28 : "A Memory Model for Static Analysis of C Programs"
29 : (Zhongxing Xu, Ted Kremenek, and Jian Zhang)
30 : http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf */
31 :
32 : /* The store models memory as a collection of "clusters", where regions
33 : are partitioned into clusters via their base region.
34 :
35 : For example, given:
36 : int a, b, c;
37 : struct coord { double x; double y; } verts[3];
38 : then "verts[0].y" and "verts[1].x" both have "verts" as their base region.
39 : Each of a, b, c, and verts will have their own clusters, so that we
40 : know that writes to e.g. "verts[1].x".don't affect e.g. "a".
41 :
42 : Within each cluster we store a map of bindings to values, where the
43 : binding keys can be either concrete or symbolic.
44 :
45 : Concrete bindings affect a specific range of bits relative to the start
46 : of the base region of the cluster, whereas symbolic bindings affect
47 : a specific subregion within the cluster.
48 :
49 : Consider (from the symbolic-1.c testcase):
50 :
51 : char arr[1024];
52 : arr[2] = a; (1)
53 : arr[3] = b; (2)
54 : After (1) and (2), the cluster for "arr" has concrete bindings
55 : for bits 16-23 and for bits 24-31, with svalues "INIT_VAL(a)"
56 : and "INIT_VAL(b)" respectively:
57 : cluster: {bits 16-23: "INIT_VAL(a)",
58 : bits 24-31: "INIT_VAL(b)";
59 : flags: {}}
60 : Attempting to query unbound subregions e.g. arr[4] will
61 : return "UNINITIALIZED".
62 : "a" and "b" are each in their own clusters, with no explicit
63 : bindings, and thus implicitly have value INIT_VAL(a) and INIT_VAL(b).
64 :
65 : arr[3] = c; (3)
66 : After (3), the concrete binding for bits 24-31 is replaced with the
67 : svalue "INIT_VAL(c)":
68 : cluster: {bits 16-23: "INIT_VAL(a)", (from before)
69 : bits 24-31: "INIT_VAL(c)"; (updated)
70 : flags: {}}
71 :
72 : arr[i] = d; (4)
73 : After (4), we lose the concrete bindings and replace them with a
74 : symbolic binding for "arr[i]", with svalue "INIT_VAL(d)". We also
75 : mark the cluster as having been "symbolically touched": future
76 : attempts to query the values of subregions other than "arr[i]",
77 : such as "arr[3]" are "UNKNOWN", since we don't know if the write
78 : to arr[i] affected them.
79 : cluster: {symbolic_key(arr[i]): "INIT_VAL(d)";
80 : flags: {TOUCHED}}
81 :
82 : arr[j] = e; (5)
83 : After (5), we lose the symbolic binding for "arr[i]" since we could
84 : have overwritten it, and add a symbolic binding for "arr[j]".
85 : cluster: {symbolic_key(arr[j]): "INIT_VAL(d)"; (different symbolic
86 : flags: {TOUCHED}} binding)
87 :
88 : arr[3] = f; (6)
89 : After (6), we lose the symbolic binding for "arr[j]" since we could
90 : have overwritten it, and gain a concrete binding for bits 24-31
91 : again, this time with svalue "INIT_VAL(e)":
92 : cluster: {bits 24-31: "INIT_VAL(d)";
93 : flags: {TOUCHED}}
94 : The cluster is still flagged as touched, so that we know that
95 : accesses to other elements are "UNKNOWN" rather than
96 : "UNINITIALIZED".
97 :
98 : Handling symbolic regions requires us to handle aliasing.
99 :
100 : In the first example above, each of a, b, c and verts are non-symbolic
101 : base regions and so their clusters are "concrete clusters", whereas given:
102 : struct coord *p, *q;
103 : then "*p" and "*q" are symbolic base regions, and thus "*p" and "*q"
104 : have "symbolic clusters".
105 :
106 : In the above, "verts[i].x" will have a symbolic *binding* within a
107 : concrete cluster for "verts", whereas "*p" is a symbolic *cluster*.
108 :
109 : Writes to concrete clusters can't affect other concrete clusters,
110 : but can affect symbolic clusters; e.g. after:
111 : verts[0].x = 42;
112 : we bind 42 in the cluster for "verts", but the clusters for "b" and "c"
113 : can't be affected. Any symbolic clusters for *p and for *q can be
114 : affected, *p and *q could alias verts.
115 :
116 : Writes to a symbolic cluster can affect other clusters, both
117 : concrete and symbolic; e.g. after:
118 : p->x = 17;
119 : we bind 17 within the cluster for "*p". The concrete clusters for a, b,
120 : c, and verts could be affected, depending on whether *p aliases them.
121 : Similarly, the symbolic cluster to *q could be affected. */
122 :
123 : namespace ana {
124 :
125 : /* A class for keeping track of aspects of a program_state that we don't
126 : know about, to avoid false positives about leaks.
127 :
128 : Consider:
129 :
130 : p->field = malloc (1024);
131 : q->field = NULL;
132 :
133 : where we don't know whether or not p and q point to the same memory,
134 : and:
135 :
136 : p->field = malloc (1024);
137 : unknown_fn (p);
138 :
139 : In both cases, the svalue for the address of the allocated buffer
140 : goes from being bound to p->field to not having anything explicitly bound
141 : to it.
142 :
143 : Given that we conservatively discard bindings due to possible aliasing or
144 : calls to unknown function, the store loses references to svalues,
145 : but these svalues could still be live. We don't want to warn about
146 : them leaking - they're effectively in a "maybe live" state.
147 :
148 : This "maybe live" information is somewhat transient.
149 :
150 : We don't want to store this "maybe live" information in the program_state,
151 : region_model, or store, since we don't want to bloat these objects (and
152 : potentially bloat the exploded_graph with more nodes).
153 : However, we can't store it in the region_model_context, as these context
154 : objects sometimes don't last long enough to be around when comparing the
155 : old vs the new state.
156 :
157 : This class is a way to track a set of such svalues, so that we can
158 : temporarily capture that they are in a "maybe live" state whilst
159 : comparing old and new states. */
160 :
161 1031469 : class uncertainty_t
162 : {
163 : public:
164 : typedef hash_set<const svalue *>::iterator iterator;
165 :
166 19945 : void on_maybe_bound_sval (const svalue *sval)
167 : {
168 19945 : m_maybe_bound_svals.add (sval);
169 : }
170 31060 : void on_mutable_sval_at_unknown_call (const svalue *sval)
171 : {
172 31060 : m_mutable_at_unknown_call_svals.add (sval);
173 : }
174 :
175 831027 : bool unknown_sm_state_p (const svalue *sval)
176 : {
177 831027 : return (m_maybe_bound_svals.contains (sval)
178 831027 : || m_mutable_at_unknown_call_svals.contains (sval));
179 : }
180 :
181 : void dump_to_pp (pretty_printer *pp, bool simple) const;
182 : void dump (bool simple) const;
183 :
184 432200 : iterator begin_maybe_bound_svals () const
185 : {
186 432200 : return m_maybe_bound_svals.begin ();
187 : }
188 446500 : iterator end_maybe_bound_svals () const
189 : {
190 446500 : return m_maybe_bound_svals.end ();
191 : }
192 :
193 : private:
194 :
195 : /* svalues that might or might not still be bound. */
196 : hash_set<const svalue *> m_maybe_bound_svals;
197 :
198 : /* svalues that have mutable sm-state at unknown calls. */
199 : hash_set<const svalue *> m_mutable_at_unknown_call_svals;
200 : };
201 :
202 : class byte_range;
203 : class concrete_binding;
204 : class symbolic_binding;
205 :
206 : /* Abstract base class for describing ranges of bits within a binding_map
207 : that can have svalues bound to them. */
208 :
209 431296282 : class binding_key
210 : {
211 : public:
212 417093 : virtual ~binding_key () {}
213 : virtual bool concrete_p () const = 0;
214 9748991 : bool symbolic_p () const { return !concrete_p (); }
215 :
216 : static const binding_key *make (store_manager *mgr, const region *r);
217 :
218 : virtual void dump_to_pp (pretty_printer *pp, bool simple) const = 0;
219 : void dump (bool simple) const;
220 : label_text get_desc (bool simple=true) const;
221 :
222 : static int cmp_ptrs (const void *, const void *);
223 : static int cmp (const binding_key *, const binding_key *);
224 :
225 6956 : virtual const concrete_binding *dyn_cast_concrete_binding () const
226 6956 : { return nullptr; }
227 374944 : virtual const symbolic_binding *dyn_cast_symbolic_binding () const
228 374944 : { return nullptr; }
229 : };
230 :
231 : /* A concrete range of bits. */
232 :
233 : struct bit_range
234 : {
235 2371825 : bit_range (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
236 16089613 : : m_start_bit_offset (start_bit_offset),
237 2573560 : m_size_in_bits (size_in_bits)
238 : {}
239 :
240 : void dump_to_pp (pretty_printer *pp) const;
241 : void dump () const;
242 :
243 : std::unique_ptr<json::object> to_json () const;
244 :
245 5712846 : bool empty_p () const
246 : {
247 1578613 : return m_size_in_bits == 0;
248 : }
249 :
250 26154599 : bit_offset_t get_start_bit_offset () const
251 : {
252 9103315 : return m_start_bit_offset;
253 : }
254 850040 : bit_offset_t get_next_bit_offset () const
255 : {
256 5799078 : return m_start_bit_offset + m_size_in_bits;
257 : }
258 4134233 : bit_offset_t get_last_bit_offset () const
259 : {
260 4134233 : gcc_assert (!empty_p ());
261 4134233 : return get_next_bit_offset () - 1;
262 : }
263 :
264 42537 : bool contains_p (bit_offset_t offset) const
265 : {
266 42537 : return (offset >= get_start_bit_offset ()
267 79850 : && offset < get_next_bit_offset ());
268 : }
269 :
270 : bool contains_p (const bit_range &other, bit_range *out) const;
271 :
272 64518400 : bool operator== (const bit_range &other) const
273 : {
274 64518400 : return (m_start_bit_offset == other.m_start_bit_offset
275 64518400 : && m_size_in_bits == other.m_size_in_bits);
276 : }
277 :
278 814841 : bool intersects_p (const bit_range &other) const
279 : {
280 814841 : return (get_start_bit_offset () < other.get_next_bit_offset ()
281 1620711 : && other.get_start_bit_offset () < get_next_bit_offset ());
282 : }
283 : bool intersects_p (const bit_range &other,
284 : bit_size_t *out_num_overlap_bits) const;
285 : bool intersects_p (const bit_range &other,
286 : bit_range *out_this,
287 : bit_range *out_other) const;
288 :
289 : bool exceeds_p (const bit_range &other,
290 : bit_range *out_overhanging_bit_range) const;
291 :
292 : bool falls_short_of_p (bit_offset_t offset,
293 : bit_range *out_fall_short_bits) const;
294 :
295 : static int cmp (const bit_range &br1, const bit_range &br2);
296 :
297 : bit_range operator- (bit_offset_t offset) const;
298 :
299 : static bool from_mask (unsigned HOST_WIDE_INT mask, bit_range *out);
300 :
301 : bool as_byte_range (byte_range *out) const;
302 :
303 : bool
304 25471644 : operator< (const bit_range &other) const
305 : {
306 25471644 : if (m_start_bit_offset < other.m_start_bit_offset)
307 : return true;
308 15424778 : if (m_start_bit_offset > other.m_start_bit_offset)
309 : return false;
310 9530678 : return (m_size_in_bits < other.m_size_in_bits);
311 : }
312 :
313 87648321 : hashval_t hash () const
314 : {
315 87648321 : inchash::hash hstate;
316 87648321 : hstate.add_wide_int (m_start_bit_offset);
317 87648321 : hstate.add_wide_int (m_size_in_bits);
318 87648321 : return hstate.end ();
319 : }
320 :
321 : bit_offset_t m_start_bit_offset;
322 : bit_size_t m_size_in_bits;
323 : };
324 :
325 : /* A concrete range of bytes. */
326 :
327 : struct byte_range
328 : {
329 35729 : byte_range (byte_offset_t start_byte_offset, byte_size_t size_in_bytes)
330 29611 : : m_start_byte_offset (start_byte_offset),
331 25770 : m_size_in_bytes (size_in_bytes)
332 : {}
333 :
334 : void dump_to_pp (pretty_printer *pp) const;
335 : void dump () const;
336 :
337 : std::unique_ptr<json::object> to_json () const;
338 :
339 2912 : bool empty_p () const
340 : {
341 5824 : return m_size_in_bytes == 0;
342 : }
343 :
344 3530 : bool contains_p (byte_offset_t offset) const
345 : {
346 10590 : return (offset >= get_start_byte_offset ()
347 7054 : && offset < get_next_byte_offset ());
348 : }
349 : bool contains_p (const byte_range &other, byte_range *out) const;
350 :
351 : bool operator== (const byte_range &other) const
352 : {
353 : return (m_start_byte_offset == other.m_start_byte_offset
354 : && m_size_in_bytes == other.m_size_in_bytes);
355 : }
356 :
357 18726 : byte_offset_t get_start_byte_offset () const
358 : {
359 18726 : return m_start_byte_offset;
360 : }
361 4877 : byte_offset_t get_next_byte_offset () const
362 : {
363 4877 : return m_start_byte_offset + m_size_in_bytes;
364 : }
365 2912 : byte_offset_t get_last_byte_offset () const
366 : {
367 2912 : gcc_assert (!empty_p ());
368 2912 : return m_start_byte_offset + m_size_in_bytes - 1;
369 : }
370 :
371 769 : bit_range as_bit_range () const
372 : {
373 2307 : return bit_range (m_start_byte_offset * BITS_PER_UNIT,
374 769 : m_size_in_bytes * BITS_PER_UNIT);
375 : }
376 :
377 0 : bit_offset_t get_start_bit_offset () const
378 : {
379 0 : return m_start_byte_offset * BITS_PER_UNIT;
380 : }
381 0 : bit_offset_t get_next_bit_offset () const
382 : {
383 0 : return get_next_byte_offset () * BITS_PER_UNIT;
384 : }
385 :
386 : static int cmp (const byte_range &br1, const byte_range &br2);
387 :
388 : byte_offset_t m_start_byte_offset;
389 : byte_size_t m_size_in_bytes;
390 : };
391 :
392 : /* Concrete subclass of binding_key, for describing a non-empty
393 : concrete range of bits within the binding_map (e.g. "bits 8-15"). */
394 :
395 360799774 : class concrete_binding : public binding_key
396 : {
397 : public:
398 : /* This class is its own key for the purposes of consolidation. */
399 : typedef concrete_binding key_t;
400 :
401 13513596 : concrete_binding (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
402 13513596 : : m_bit_range (start_bit_offset, size_in_bits)
403 : {
404 13513596 : gcc_assert (m_bit_range.m_size_in_bits > 0);
405 13513596 : }
406 9303806 : bool concrete_p () const final override { return true; }
407 :
408 63087718 : hashval_t hash () const { return m_bit_range.hash (); }
409 60587553 : bool operator== (const concrete_binding &other) const
410 : {
411 60587553 : return m_bit_range == other.m_bit_range;
412 : }
413 :
414 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
415 :
416 775809 : const concrete_binding *dyn_cast_concrete_binding () const final override
417 775809 : { return this; }
418 :
419 7278640 : const bit_range &get_bit_range () const { return m_bit_range; }
420 : bool get_byte_range (byte_range *out) const;
421 :
422 375022 : bit_offset_t get_start_bit_offset () const
423 : {
424 367631 : return m_bit_range.m_start_bit_offset;
425 : }
426 83164 : bit_size_t get_size_in_bits () const
427 : {
428 83164 : return m_bit_range.m_size_in_bits;
429 : }
430 : /* Return the next bit offset after the end of this binding. */
431 0 : bit_offset_t get_next_bit_offset () const
432 : {
433 367631 : return m_bit_range.get_next_bit_offset ();
434 : }
435 :
436 : bool overlaps_p (const concrete_binding &other) const;
437 :
438 : static int cmp_ptr_ptr (const void *, const void *);
439 :
440 : void mark_deleted () { m_bit_range.m_size_in_bits = -1; }
441 60658 : void mark_empty () { m_bit_range.m_size_in_bits = -2; }
442 66107668 : bool is_deleted () const { return m_bit_range.m_size_in_bits == -1; }
443 231575930 : bool is_empty () const { return m_bit_range.m_size_in_bits == -2; }
444 :
445 : private:
446 : bit_range m_bit_range;
447 : };
448 :
449 : } // namespace ana
450 :
451 : template <>
452 : template <>
453 : inline bool
454 424 : is_a_helper <const ana::concrete_binding *>::test (const ana::binding_key *key)
455 : {
456 424 : return key->concrete_p ();
457 : }
458 :
459 : template <> struct default_hash_traits<ana::concrete_binding>
460 : : public member_function_hash_traits<ana::concrete_binding>
461 : {
462 : static const bool empty_zero_p = false;
463 : };
464 :
465 : namespace ana {
466 :
467 : /* Concrete subclass of binding_key, for describing a symbolic set of
468 : bits within the binding_map in terms of a region (e.g. "arr[i]"). */
469 :
470 42421290 : class symbolic_binding : public binding_key
471 : {
472 : public:
473 : /* This class is its own key for the purposes of consolidation. */
474 : typedef symbolic_binding key_t;
475 :
476 1852503 : symbolic_binding (const region *region) : m_region (region) {}
477 446458 : bool concrete_p () const final override { return false; }
478 :
479 10120367 : hashval_t hash () const
480 : {
481 10120367 : return (intptr_t)m_region;
482 : }
483 9875776 : bool operator== (const symbolic_binding &other) const
484 : {
485 9875776 : return m_region == other.m_region;
486 : }
487 :
488 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
489 :
490 32599 : const symbolic_binding *dyn_cast_symbolic_binding () const final override
491 32599 : { return this; }
492 :
493 387451 : const region *get_region () const { return m_region; }
494 :
495 : static int cmp_ptr_ptr (const void *, const void *);
496 :
497 : void mark_deleted () { m_region = reinterpret_cast<const region *> (1); }
498 0 : void mark_empty () { m_region = nullptr; }
499 10796516 : bool is_deleted () const
500 10796516 : { return m_region == reinterpret_cast<const region *> (1); }
501 : bool is_empty () const { return m_region == nullptr; }
502 :
503 : private:
504 : const region *m_region;
505 : };
506 :
507 : } // namespace ana
508 :
509 : template <> struct default_hash_traits<ana::symbolic_binding>
510 : : public member_function_hash_traits<ana::symbolic_binding>
511 : {
512 : static const bool empty_zero_p = true;
513 : };
514 :
515 : namespace ana {
516 :
517 : /* A mapping from concrete bit_ranges to svalues, for use by
518 : binding_cluster and compound_svalue.
519 : The keys are ordered by the start offset, and must not overlap
520 : The bound svalues may not be compound_svalues, so that we don't
521 : nest these (for canonicalization). */
522 :
523 31382675 : class concrete_binding_map
524 : {
525 : public:
526 : using map_t = std::map<bit_range, const svalue *>;
527 : using const_iterator = map_t::const_iterator;
528 : using iterator = map_t::iterator;
529 :
530 48308 : void clear () { m_map.clear (); }
531 179725 : bool empty_p () const { return m_map.empty (); }
532 :
533 : bool
534 14302 : operator== (const concrete_binding_map &other) const
535 : {
536 14302 : return m_map == other.m_map;
537 : }
538 : bool
539 3272192 : operator!= (const concrete_binding_map &other) const
540 : {
541 3272192 : return m_map != other.m_map;
542 : }
543 :
544 22057145 : const_iterator begin () const { return m_map.begin (); }
545 73812381 : const_iterator end () const { return m_map.end (); }
546 3757 : iterator begin () { return m_map.begin (); }
547 2060240 : iterator end () { return m_map.end (); }
548 :
549 13543804 : size_t size () const { return m_map.size (); }
550 :
551 : void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
552 : void dump (bool simple) const;
553 :
554 : void add_to_tree_widget (text_art::tree_widget &parent_widget,
555 : const text_art::dump_widget_info &dwi) const;
556 :
557 : void validate () const;
558 :
559 : static int
560 : cmp (const concrete_binding_map &map1,
561 : const concrete_binding_map &map2);
562 :
563 : void
564 2150493 : insert (const bit_range &bits, const svalue *sval)
565 : {
566 2150493 : m_map.insert ({bits, sval});
567 2150493 : }
568 :
569 : void
570 9 : insert (const byte_range &bytes, const svalue *sval)
571 : {
572 9 : m_map.insert ({bytes.as_bit_range (), sval});
573 9 : }
574 :
575 : void
576 325896 : erase (const bit_range &bits)
577 : {
578 325896 : m_map.erase (bits);
579 287582 : }
580 :
581 : const svalue *
582 : get_any_exact_binding (const bit_range &bits) const;
583 :
584 : const_iterator
585 4821662 : find (const bit_range &bits) const
586 : {
587 4821662 : return m_map.find (bits);
588 : }
589 : iterator
590 2056197 : find (const bit_range &bits)
591 : {
592 2056197 : return m_map.find (bits);
593 : }
594 :
595 : complexity calc_complexity () const;
596 :
597 : bool apply_ctor_to_region (const region *parent_reg, tree ctor,
598 : region_model_manager *mgr);
599 :
600 : void remove_overlapping_binding (store_manager *mgr,
601 : const bit_range &bits_to_drop,
602 : const bit_range &affected_bound_bits,
603 : const svalue &old_sval);
604 :
605 : void remove_overlapping_bindings (store_manager *mgr,
606 : const bit_range &bits);
607 :
608 : private:
609 : std::vector<std::pair<bit_range, const svalue &>>
610 : get_overlapping_bindings (const bit_range &bits);
611 :
612 : bool apply_ctor_val_to_range (const region *parent_reg,
613 : region_model_manager *mgr,
614 : tree min_index, tree max_index,
615 : tree val);
616 : bool apply_ctor_pair_to_child_region (const region *parent_reg,
617 : region_model_manager *mgr,
618 : tree index, tree val);
619 :
620 : map_t m_map;
621 : };
622 :
623 : /* A mapping from binding_keys to svalues, for use by binding_cluster.
624 : We store bindings at concrete bit ranges via a concrete_binding_map,
625 : along with a vector of (symbolic key, svalue) pairs, but for now
626 : this has maximum length of 1. */
627 :
628 : class binding_map
629 : {
630 : public:
631 : struct symbolic_binding
632 : {
633 167237 : bool operator== (const symbolic_binding &other) const
634 : {
635 167237 : return (m_region == other.m_region
636 167237 : && m_sval == other.m_sval);
637 : }
638 :
639 : const region *m_region;
640 : const svalue *m_sval;
641 : };
642 : using concrete_bindings_t = concrete_binding_map;
643 : using symbolic_bindings_t = std::vector<symbolic_binding>;
644 :
645 : struct binding_pair
646 : {
647 11776256 : binding_pair (const binding_key *key,
648 : const svalue *sval)
649 : : m_key (key),
650 : m_sval (sval)
651 : {
652 : }
653 :
654 : const binding_key *m_key;
655 : const svalue *m_sval;
656 : };
657 :
658 : typedef class const_iterator
659 : {
660 : public:
661 33217396 : const_iterator (const binding_map &map,
662 : concrete_bindings_t::const_iterator concrete_iter,
663 : symbolic_bindings_t::const_iterator symbolic_iter)
664 33217396 : : m_map (map),
665 33217396 : m_concrete (concrete_iter),
666 33217396 : m_symbolic (symbolic_iter)
667 : {
668 : }
669 : bool operator== (const const_iterator &other) const;
670 25622939 : bool operator!= (const const_iterator &other) const
671 : {
672 25622939 : return !(*this == other);
673 : }
674 : const_iterator &operator++ ();
675 :
676 : binding_pair operator* ();
677 : const svalue *get_svalue () const;
678 :
679 : private:
680 : const binding_map &m_map;
681 : concrete_bindings_t::const_iterator m_concrete;
682 : symbolic_bindings_t::const_iterator m_symbolic;
683 : } const_iterator_t;
684 :
685 : typedef class iterator
686 : {
687 : public:
688 : friend class binding_map;
689 :
690 20800535 : iterator (const binding_map &map,
691 : concrete_bindings_t::iterator concrete_iter,
692 : symbolic_bindings_t::iterator symbolic_iter)
693 20800535 : : m_map (map),
694 20800535 : m_concrete (concrete_iter),
695 20800535 : m_symbolic (symbolic_iter)
696 : {
697 : }
698 : bool operator== (const iterator &other) const;
699 14853301 : bool operator!= (const iterator &other) const
700 : {
701 14853301 : return !(*this == other);
702 : }
703 : iterator &operator++ ();
704 :
705 : binding_pair operator* ();
706 :
707 : const binding_key *get_key () const;
708 :
709 : private:
710 : const binding_map &m_map;
711 : concrete_bindings_t::iterator m_concrete;
712 : symbolic_bindings_t::iterator m_symbolic;
713 : } iterator_t;
714 :
715 : binding_map (store_manager &store_mgr);
716 : binding_map (const binding_map &other);
717 : binding_map& operator=(const binding_map &other);
718 :
719 : bool operator== (const binding_map &other) const;
720 3272188 : bool operator!= (const binding_map &other) const
721 : {
722 3272188 : return !(*this == other);
723 : }
724 :
725 : hashval_t hash () const;
726 :
727 : const svalue *get (const binding_key *key) const;
728 : void put (const binding_key *k, const svalue *v);
729 : void overwrite (iterator_t &pos, const svalue *v);
730 :
731 : void remove (const binding_key *k);
732 24154 : void clear ()
733 : {
734 24154 : m_concrete.clear ();
735 24154 : m_symbolic.clear ();
736 24154 : }
737 :
738 179725 : bool empty_p () const
739 : {
740 95997 : return m_concrete.empty_p () && m_symbolic.empty ();
741 : }
742 :
743 : const_iterator_t begin () const;
744 : const_iterator_t end () const;
745 : iterator_t begin ();
746 : iterator_t end ();
747 : size_t elements () const;
748 :
749 : void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
750 : void dump (bool simple) const;
751 :
752 : void validate () const;
753 :
754 : std::unique_ptr<json::object> to_json () const;
755 :
756 : void add_to_tree_widget (text_art::tree_widget &parent_widget,
757 : const text_art::dump_widget_info &dwi) const;
758 :
759 : void remove_overlapping_bindings (store_manager *mgr,
760 : const binding_key *drop_key,
761 : uncertainty_t *uncertainty,
762 : svalue_set *maybe_live_values,
763 : bool always_overlap);
764 :
765 : const concrete_bindings_t &
766 800079 : get_concrete_bindings () const { return m_concrete; }
767 :
768 : const symbolic_bindings_t &
769 2163 : get_symbolic_bindings () const { return m_symbolic; }
770 :
771 : private:
772 : void get_overlapping_bindings (const binding_key *key,
773 : auto_vec<const binding_key *> *out);
774 :
775 : store_manager &m_store_mgr;
776 : concrete_bindings_t m_concrete;
777 : symbolic_bindings_t m_symbolic;
778 : };
779 :
780 : /* All of the bindings within a store for regions that share the same
781 : base region. */
782 :
783 32797822 : class binding_cluster
784 : {
785 : public:
786 : friend class store;
787 :
788 : typedef binding_map::const_iterator const_iterator_t;
789 : typedef binding_map::iterator iterator_t;
790 :
791 : binding_cluster (store_manager &store_mgr, const region *base_region);
792 : binding_cluster (const binding_cluster &other);
793 : binding_cluster& operator=(const binding_cluster &other);
794 :
795 : bool operator== (const binding_cluster &other) const;
796 3272188 : bool operator!= (const binding_cluster &other) const
797 : {
798 3272188 : return !(*this == other);
799 : }
800 :
801 : hashval_t hash () const;
802 :
803 : bool symbolic_p () const;
804 :
805 81401 : const region *get_base_region () const { return m_base_region; }
806 :
807 : void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
808 : void dump (bool simple) const;
809 :
810 : void validate () const;
811 :
812 : std::unique_ptr<json::object> to_json () const;
813 :
814 : std::unique_ptr<text_art::tree_widget>
815 : make_dump_widget (const text_art::dump_widget_info &dwi,
816 : store_manager *mgr) const;
817 :
818 : void bind (store_manager *mgr, const region *, const svalue *);
819 :
820 : void clobber_region (store_manager *mgr, const region *reg);
821 : void purge_region (store_manager *mgr, const region *reg);
822 : void fill_region (store_manager *mgr, const region *reg, const svalue *sval);
823 : void zero_fill_region (store_manager *mgr, const region *reg);
824 : void mark_region_as_unknown (store_manager *mgr,
825 : const region *reg_to_bind,
826 : const region *reg_for_overlap,
827 : uncertainty_t *uncertainty,
828 : svalue_set *maybe_live_values);
829 : void purge_state_involving (const svalue *sval,
830 : region_model_manager *sval_mgr);
831 :
832 : const svalue *get_binding (store_manager *mgr, const region *reg) const;
833 : const svalue *get_binding_recursive (store_manager *mgr,
834 : const region *reg) const;
835 : const svalue *get_any_binding (store_manager *mgr,
836 : const region *reg) const;
837 : const svalue *maybe_get_compound_binding (store_manager *mgr,
838 : const region *reg) const;
839 :
840 : void remove_overlapping_bindings (store_manager *mgr, const region *reg,
841 : uncertainty_t *uncertainty,
842 : svalue_set *maybe_live_values);
843 :
844 : template <typename T>
845 8595534 : void for_each_value (void (*cb) (const svalue *sval, T user_data),
846 : T user_data) const
847 : {
848 19604928 : for (auto iter = m_map.begin (); iter != m_map.end (); ++iter)
849 11009394 : cb (iter.get_svalue (), user_data);
850 8595534 : }
851 :
852 : static bool can_merge_p (const binding_cluster *cluster_a,
853 : const binding_cluster *cluster_b,
854 : binding_cluster *out_cluster,
855 : store *out_store,
856 : store_manager *mgr,
857 : model_merger *merger);
858 : void make_unknown_relative_to (const binding_cluster *other_cluster,
859 : store *out_store,
860 : store_manager *mgr);
861 :
862 : void mark_as_escaped ();
863 : void on_unknown_fncall (const gcall &call, store_manager *mgr,
864 : const conjured_purge &p);
865 : void on_asm (const gasm *stmt, store_manager *mgr,
866 : const conjured_purge &p);
867 :
868 : bool escaped_p () const;
869 245454 : bool touched_p () const { return m_touched; }
870 :
871 : bool redundant_p () const;
872 276172 : bool empty_p () const { return m_map.empty_p (); }
873 :
874 : void get_representative_path_vars (const region_model *model,
875 : svalue_set *visited,
876 : const region *base_reg,
877 : const svalue *sval,
878 : logger *logger,
879 : auto_vec<path_var> *out_pvs) const;
880 :
881 : const svalue *maybe_get_simple_value (store_manager *mgr) const;
882 :
883 32331 : const_iterator_t begin () const { return m_map.begin (); }
884 32331 : const_iterator_t end () const { return m_map.end (); }
885 :
886 144974 : iterator_t begin () { return m_map.begin (); }
887 287858 : iterator_t end () { return m_map.end (); }
888 :
889 4326 : const binding_map &get_map () const { return m_map; }
890 : binding_map &get_map () { return m_map; }
891 :
892 : private:
893 : const svalue *get_any_value (const binding_key *key) const;
894 : void bind_compound_sval (store_manager *mgr,
895 : const region *reg,
896 : const compound_svalue *compound_sval);
897 : void bind_key (const binding_key *key, const svalue *sval);
898 :
899 : const region *m_base_region;
900 :
901 : binding_map m_map;
902 :
903 : /* Has a pointer to this cluster "escaped" into a part of the program
904 : we don't know about (via a call to a function with an unknown body,
905 : or by being passed in as a pointer param of a "top-level" function call).
906 : Such regions could be overwritten when other such functions are called,
907 : even if the region is no longer reachable by pointers that we are
908 : tracking. */
909 : bool m_escaped;
910 :
911 : /* Has this cluster been written to via a symbolic binding?
912 : If so, then we don't know anything about unbound subregions,
913 : so we can't use initial_svalue, treat them as uninitialized, or
914 : inherit values from a parent region. */
915 : bool m_touched;
916 : };
917 :
918 : /* The mapping from regions to svalues.
919 : This is actually expressed by subdividing into clusters, to better
920 : handle aliasing. */
921 :
922 : class store
923 : {
924 : public:
925 : typedef hash_map <const region *, binding_cluster *> cluster_map_t;
926 :
927 : store ();
928 : store (const store &other);
929 : ~store ();
930 :
931 : store &operator= (const store &other);
932 :
933 : bool operator== (const store &other) const;
934 505285 : bool operator!= (const store &other) const
935 : {
936 505285 : return !(*this == other);
937 : }
938 :
939 : hashval_t hash () const;
940 :
941 : void dump_to_pp (pretty_printer *pp, bool summarize, bool multiline,
942 : store_manager *mgr) const;
943 : void dump (bool simple) const;
944 : void summarize_to_pp (pretty_printer *pp, bool simple) const;
945 :
946 : void validate () const;
947 :
948 : std::unique_ptr<json::object> to_json () const;
949 :
950 : std::unique_ptr<text_art::tree_widget>
951 : make_dump_widget (const text_art::dump_widget_info &dwi,
952 : store_manager *mgr) const;
953 :
954 : const svalue *get_any_binding (store_manager *mgr, const region *reg) const;
955 :
956 233934 : bool called_unknown_fn_p () const { return m_called_unknown_fn; }
957 :
958 : void set_value (store_manager *mgr, const region *lhs_reg,
959 : const svalue *rhs_sval,
960 : uncertainty_t *uncertainty);
961 : void clobber_region (store_manager *mgr, const region *reg);
962 : void purge_region (store_manager *mgr, const region *reg);
963 : void fill_region (store_manager *mgr, const region *reg, const svalue *sval);
964 : void zero_fill_region (store_manager *mgr, const region *reg);
965 : void mark_region_as_unknown (store_manager *mgr, const region *reg,
966 : uncertainty_t *uncertainty,
967 : svalue_set *maybe_live_values);
968 : void purge_state_involving (const svalue *sval,
969 : region_model_manager *sval_mgr);
970 :
971 : const binding_cluster *get_cluster (const region *base_reg) const;
972 : binding_cluster *get_cluster (const region *base_reg);
973 : binding_cluster *get_or_create_cluster (store_manager &store_mgr,
974 : const region *base_reg);
975 : void purge_cluster (const region *base_reg);
976 :
977 : template <typename T>
978 1406591 : void for_each_cluster (void (*cb) (const region *base_reg, T user_data),
979 : T user_data) const
980 : {
981 13263092 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
982 25119593 : iter != m_cluster_map.end (); ++iter)
983 11856501 : cb ((*iter).first, user_data);
984 1406591 : }
985 :
986 : static bool can_merge_p (const store *store_a, const store *store_b,
987 : store *out_store, store_manager *mgr,
988 : model_merger *merger);
989 :
990 : void mark_as_escaped (store_manager &mgr, const region *base_reg);
991 : void on_unknown_fncall (const gcall &call, store_manager *mgr,
992 : const conjured_purge &p);
993 : bool escaped_p (const region *reg) const;
994 :
995 : void get_representative_path_vars (const region_model *model,
996 : svalue_set *visited,
997 : const svalue *sval,
998 : logger *logger,
999 : auto_vec<path_var> *out_pvs) const;
1000 :
1001 1088613 : cluster_map_t::iterator begin () const { return m_cluster_map.begin (); }
1002 9995871 : cluster_map_t::iterator end () const { return m_cluster_map.end (); }
1003 :
1004 : tristate eval_alias (const region *base_reg_a,
1005 : const region *base_reg_b) const;
1006 :
1007 : void canonicalize (store_manager *mgr);
1008 : void loop_replay_fixup (const store *other_store,
1009 : region_model_manager *mgr);
1010 :
1011 : void replay_call_summary (call_summary_replay &r,
1012 : const store &summary);
1013 : void replay_call_summary_cluster (call_summary_replay &r,
1014 : const store &summary,
1015 : const region *base_reg);
1016 : void on_maybe_live_values (store_manager &mgr,
1017 : const svalue_set &maybe_live_values);
1018 :
1019 : private:
1020 : void remove_overlapping_bindings (store_manager *mgr, const region *reg,
1021 : uncertainty_t *uncertainty);
1022 : tristate eval_alias_1 (const region *base_reg_a,
1023 : const region *base_reg_b) const;
1024 :
1025 : cluster_map_t m_cluster_map;
1026 :
1027 : /* If this is true, then unknown code has been called, and so
1028 : any global variable that isn't currently modelled by the store
1029 : has unknown state, rather than being in an "initial state".
1030 : This is to avoid having to mark (and thus explicitly track)
1031 : every global when an unknown function is called; instead, they
1032 : can be tracked implicitly. */
1033 : bool m_called_unknown_fn;
1034 : };
1035 :
1036 : /* A class responsible for owning and consolidating binding keys
1037 : (both concrete and symbolic).
1038 : Key instances are immutable as far as clients are concerned, so they
1039 : are provided as "const" ptrs. */
1040 :
1041 3991 : class store_manager
1042 : {
1043 : public:
1044 3991 : store_manager (region_model_manager *mgr) : m_mgr (mgr) {}
1045 :
1046 : logger *get_logger () const;
1047 :
1048 : /* binding consolidation. */
1049 : const concrete_binding *
1050 : get_concrete_binding (bit_offset_t start_bit_offset,
1051 : bit_offset_t size_in_bits);
1052 : const concrete_binding *
1053 11271765 : get_concrete_binding (const bit_range &bits)
1054 : {
1055 11271765 : return get_concrete_binding (bits.get_start_bit_offset (),
1056 11271765 : bits.m_size_in_bits);
1057 : }
1058 : const concrete_binding *
1059 : get_concrete_binding (const byte_range &bytes)
1060 : {
1061 : bit_range bits = bytes.as_bit_range ();
1062 : return get_concrete_binding (bits);
1063 : }
1064 : const symbolic_binding *
1065 : get_symbolic_binding (const region *region);
1066 :
1067 6075178 : region_model_manager *get_svalue_manager () const
1068 : {
1069 6075178 : return m_mgr;
1070 : }
1071 :
1072 : void log_stats (logger *logger, bool show_objs) const;
1073 :
1074 : private:
1075 : region_model_manager *m_mgr;
1076 : consolidation_map<concrete_binding> m_concrete_binding_key_mgr;
1077 : consolidation_map<symbolic_binding> m_symbolic_binding_key_mgr;
1078 : };
1079 :
1080 : } // namespace ana
1081 :
1082 : #endif /* GCC_ANALYZER_STORE_H */
|
