Branch data Line data Source code
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 : :
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 : 760201 : class uncertainty_t
161 : : {
162 : : public:
163 : : typedef hash_set<const svalue *>::iterator iterator;
164 : :
165 : 27130 : void on_maybe_bound_sval (const svalue *sval)
166 : : {
167 : 27130 : m_maybe_bound_svals.add (sval);
168 : : }
169 : 35498 : void on_mutable_sval_at_unknown_call (const svalue *sval)
170 : : {
171 : 35498 : m_mutable_at_unknown_call_svals.add (sval);
172 : : }
173 : :
174 : 585552 : bool unknown_sm_state_p (const svalue *sval)
175 : : {
176 : 585552 : return (m_maybe_bound_svals.contains (sval)
177 : 585552 : || 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 : 573739 : iterator begin_maybe_bound_svals () const
184 : : {
185 : 573739 : return m_maybe_bound_svals.begin ();
186 : : }
187 : 663256 : iterator end_maybe_bound_svals () const
188 : : {
189 : 663256 : 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 : 106102593 : class binding_key
209 : : {
210 : : public:
211 : 382066 : virtual ~binding_key () {}
212 : : virtual bool concrete_p () const = 0;
213 : 10809381 : 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 : 7869 : virtual const concrete_binding *dyn_cast_concrete_binding () const
225 : 7869 : { return NULL; }
226 : 497958 : virtual const symbolic_binding *dyn_cast_symbolic_binding () const
227 : 497958 : { return NULL; }
228 : : };
229 : :
230 : : /* A concrete range of bits. */
231 : :
232 : : struct bit_range
233 : : {
234 : 1902912 : bit_range (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
235 : 4360958 : : m_start_bit_offset (start_bit_offset),
236 : 2059337 : 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 : 1297532 : bool empty_p () const
245 : : {
246 : 1267334 : return m_size_in_bits == 0;
247 : : }
248 : :
249 : 1024532 : bit_offset_t get_start_bit_offset () const
250 : : {
251 : 724655 : return m_start_bit_offset;
252 : : }
253 : 675430 : bit_offset_t get_next_bit_offset () const
254 : : {
255 : 825801 : return m_start_bit_offset + m_size_in_bits;
256 : : }
257 : 30814 : bit_offset_t get_last_bit_offset () const
258 : : {
259 : 30814 : gcc_assert (!empty_p ());
260 : 30814 : return get_next_bit_offset () - 1;
261 : : }
262 : :
263 : 71424 : bool contains_p (bit_offset_t offset) const
264 : : {
265 : 71424 : return (offset >= get_start_bit_offset ()
266 : 133277 : && offset < get_next_bit_offset ());
267 : : }
268 : :
269 : : bool contains_p (const bit_range &other, bit_range *out) const;
270 : :
271 : 10654672 : bool operator== (const bit_range &other) const
272 : : {
273 : 10654672 : return (m_start_bit_offset == other.m_start_bit_offset
274 : 10654672 : && m_size_in_bits == other.m_size_in_bits);
275 : : }
276 : :
277 : 107296 : bool intersects_p (const bit_range &other) const
278 : : {
279 : 107296 : return (get_start_bit_offset () < other.get_next_bit_offset ()
280 : 195761 : && 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 : : bit_offset_t m_start_bit_offset;
303 : : bit_size_t m_size_in_bits;
304 : : };
305 : :
306 : : /* A concrete range of bytes. */
307 : :
308 : : struct byte_range
309 : : {
310 : 21836 : byte_range (byte_offset_t start_byte_offset, byte_size_t size_in_bytes)
311 : 21682 : : m_start_byte_offset (start_byte_offset),
312 : 17815 : m_size_in_bytes (size_in_bytes)
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 : 2530 : bool empty_p () const
321 : : {
322 : 5060 : return m_size_in_bytes == 0;
323 : : }
324 : :
325 : 2580 : bool contains_p (byte_offset_t offset) const
326 : : {
327 : 7740 : return (offset >= get_start_byte_offset ()
328 : 5158 : && offset < get_next_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 : : {
334 : : return (m_start_byte_offset == other.m_start_byte_offset
335 : : && m_size_in_bytes == other.m_size_in_bytes);
336 : : }
337 : :
338 : 16471 : byte_offset_t get_start_byte_offset () const
339 : : {
340 : 16471 : return m_start_byte_offset;
341 : : }
342 : 3730 : byte_offset_t get_next_byte_offset () const
343 : : {
344 : 3730 : return m_start_byte_offset + m_size_in_bytes;
345 : : }
346 : 2530 : byte_offset_t get_last_byte_offset () const
347 : : {
348 : 2530 : gcc_assert (!empty_p ());
349 : 2530 : return m_start_byte_offset + m_size_in_bytes - 1;
350 : : }
351 : :
352 : 737 : bit_range as_bit_range () const
353 : : {
354 : 2211 : return bit_range (m_start_byte_offset * BITS_PER_UNIT,
355 : 737 : m_size_in_bytes * BITS_PER_UNIT);
356 : : }
357 : :
358 : 0 : bit_offset_t get_start_bit_offset () const
359 : : {
360 : 0 : return m_start_byte_offset * BITS_PER_UNIT;
361 : : }
362 : 0 : bit_offset_t get_next_bit_offset () const
363 : : {
364 : 0 : return get_next_byte_offset () * BITS_PER_UNIT;
365 : : }
366 : :
367 : : static int cmp (const byte_range &br1, const byte_range &br2);
368 : :
369 : : byte_offset_t m_start_byte_offset;
370 : : byte_size_t m_size_in_bytes;
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 : :
376 : 63247850 : class concrete_binding : public binding_key
377 : : {
378 : : public:
379 : : /* This class is its own key for the purposes of consolidation. */
380 : : typedef concrete_binding key_t;
381 : :
382 : 2294926 : concrete_binding (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
383 : 2294926 : : m_bit_range (start_bit_offset, size_in_bits)
384 : : {
385 : 2294926 : gcc_assert (m_bit_range.m_size_in_bits > 0);
386 : 2294926 : }
387 : 9825703 : bool concrete_p () const final override { return true; }
388 : :
389 : 11231888 : hashval_t hash () const
390 : : {
391 : 11231888 : inchash::hash hstate;
392 : 11231888 : hstate.add_wide_int (m_bit_range.m_start_bit_offset);
393 : 11231888 : hstate.add_wide_int (m_bit_range.m_size_in_bits);
394 : 11231888 : return hstate.end ();
395 : : }
396 : 10622357 : bool operator== (const concrete_binding &other) const
397 : : {
398 : 10622357 : return m_bit_range == other.m_bit_range;
399 : : }
400 : :
401 : : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
402 : :
403 : 428211 : const concrete_binding *dyn_cast_concrete_binding () const final override
404 : 428211 : { return this; }
405 : :
406 : 139858 : const bit_range &get_bit_range () const { return m_bit_range; }
407 : : bool get_byte_range (byte_range *out) const;
408 : :
409 : 193045 : bit_offset_t get_start_bit_offset () const
410 : : {
411 : 184345 : return m_bit_range.m_start_bit_offset;
412 : : }
413 : 107200 : bit_size_t get_size_in_bits () const
414 : : {
415 : 107200 : return m_bit_range.m_size_in_bits;
416 : : }
417 : : /* Return the next bit offset after the end of this binding. */
418 : 1776 : bit_offset_t get_next_bit_offset () const
419 : : {
420 : 178985 : return m_bit_range.get_next_bit_offset ();
421 : : }
422 : :
423 : : bool overlaps_p (const concrete_binding &other) const;
424 : :
425 : : static int cmp_ptr_ptr (const void *, const void *);
426 : :
427 : : void mark_deleted () { m_bit_range.m_size_in_bits = -1; }
428 : 56408 : void mark_empty () { m_bit_range.m_size_in_bits = -2; }
429 : 11807047 : bool is_deleted () const { return m_bit_range.m_size_in_bits == -1; }
430 : 40183289 : bool is_empty () const { return m_bit_range.m_size_in_bits == -2; }
431 : :
432 : : private:
433 : : bit_range m_bit_range;
434 : : };
435 : :
436 : : } // namespace ana
437 : :
438 : : template <>
439 : : template <>
440 : : inline bool
441 : 0 : is_a_helper <const ana::concrete_binding *>::test (const ana::binding_key *key)
442 : : {
443 : 0 : return key->concrete_p ();
444 : : }
445 : :
446 : : template <> 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 : :
452 : : namespace 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 : :
457 : 30145103 : class symbolic_binding : public binding_key
458 : : {
459 : : public:
460 : : /* This class is its own key for the purposes of consolidation. */
461 : : typedef symbolic_binding key_t;
462 : :
463 : 1288164 : symbolic_binding (const region *region) : m_region (region) {}
464 : 996002 : bool concrete_p () const final override { return false; }
465 : :
466 : 7225724 : hashval_t hash () const
467 : : {
468 : 7225724 : return (intptr_t)m_region;
469 : : }
470 : 7203387 : bool operator== (const symbolic_binding &other) const
471 : : {
472 : 7203387 : return m_region == other.m_region;
473 : : }
474 : :
475 : : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
476 : :
477 : 65581 : const symbolic_binding *dyn_cast_symbolic_binding () const final override
478 : 65581 : { return this; }
479 : :
480 : 65653 : 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 : 0 : void mark_empty () { m_region = NULL; }
486 : 7785840 : bool is_deleted () const
487 : 7785840 : { return m_region == reinterpret_cast<const region *> (1); }
488 : : bool is_empty () const { return m_region == NULL; }
489 : :
490 : : private:
491 : : const region *m_region;
492 : : };
493 : :
494 : : } // namespace ana
495 : :
496 : : template <> 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 : :
502 : : namespace ana {
503 : :
504 : : /* A mapping from binding_keys to svalues, for use by binding_cluster
505 : : and compound_svalue. */
506 : :
507 : 100859 : class binding_map
508 : : {
509 : : public:
510 : : typedef hash_map <const binding_key *, const svalue *> map_t;
511 : : typedef map_t::iterator iterator_t;
512 : :
513 : 1656156 : binding_map () : m_map () {}
514 : : binding_map (const binding_map &other);
515 : : binding_map& operator=(const binding_map &other);
516 : :
517 : : bool operator== (const binding_map &other) const;
518 : 1941424 : bool operator!= (const binding_map &other) const
519 : : {
520 : 1941424 : return !(*this == other);
521 : : }
522 : :
523 : : hashval_t hash () const;
524 : :
525 : 3988767 : const svalue *get (const binding_key *key) const
526 : : {
527 : 3988767 : const svalue **slot = const_cast<map_t &> (m_map).get (key);
528 : 3988767 : if (slot)
529 : 3484525 : return *slot;
530 : : else
531 : : return NULL;
532 : : }
533 : 1711798 : bool put (const binding_key *k, const svalue *v)
534 : : {
535 : 1711798 : gcc_assert (v);
536 : 1711798 : return m_map.put (k, v);
537 : : }
538 : :
539 : 178736 : void remove (const binding_key *k) { m_map.remove (k); }
540 : 1092774 : void empty () { m_map.empty (); }
541 : :
542 : 17624468 : iterator_t begin () const { return m_map.begin (); }
543 : 26317033 : iterator_t end () const { return m_map.end (); }
544 : 652689 : 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,
555 : : region_model_manager *mgr);
556 : :
557 : : static int cmp (const binding_map &map1, const binding_map &map2);
558 : :
559 : : void remove_overlapping_bindings (store_manager *mgr,
560 : : const binding_key *drop_key,
561 : : uncertainty_t *uncertainty,
562 : : svalue_set *maybe_live_values,
563 : : bool always_overlap);
564 : :
565 : : private:
566 : : void get_overlapping_bindings (const binding_key *key,
567 : : auto_vec<const binding_key *> *out);
568 : : bool apply_ctor_val_to_range (const region *parent_reg,
569 : : region_model_manager *mgr,
570 : : tree min_index, tree max_index,
571 : : tree val);
572 : : bool apply_ctor_pair_to_child_region (const region *parent_reg,
573 : : region_model_manager *mgr,
574 : : tree index, tree val);
575 : :
576 : : map_t m_map;
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 : :
589 : 25318781 : class binding_cluster
590 : : {
591 : : public:
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);
598 : : binding_cluster (const binding_cluster &other);
599 : : binding_cluster& operator=(const binding_cluster &other);
600 : :
601 : : bool operator== (const binding_cluster &other) const;
602 : 1941424 : bool operator!= (const binding_cluster &other) const
603 : : {
604 : 1941424 : return !(*this == other);
605 : : }
606 : :
607 : : hashval_t hash () const;
608 : :
609 : : bool symbolic_p () const;
610 : :
611 : 89058 : 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);
630 : : void mark_region_as_unknown (store_manager *mgr,
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;
639 : : const svalue *get_binding_recursive (store_manager *mgr,
640 : : const region *reg) const;
641 : : const svalue *get_any_binding (store_manager *mgr,
642 : : const region *reg) const;
643 : : const svalue *maybe_get_compound_binding (store_manager *mgr,
644 : : const region *reg) const;
645 : :
646 : : void remove_overlapping_bindings (store_manager *mgr, const region *reg,
647 : : uncertainty_t *uncertainty,
648 : : svalue_set *maybe_live_values);
649 : :
650 : : template <typename T>
651 : 7506752 : void for_each_value (void (*cb) (const svalue *sval, T user_data),
652 : : T user_data) const
653 : : {
654 : 23659702 : for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
655 : 8076475 : cb ((*iter).second, user_data);
656 : 7506752 : }
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 : :
668 : : void mark_as_escaped ();
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 : 278025 : bool touched_p () const { return m_touched; }
676 : :
677 : : bool redundant_p () const;
678 : 226592 : bool empty_p () const { return m_map.elements () == 0; }
679 : :
680 : : void get_representative_path_vars (const region_model *model,
681 : : svalue_set *visited,
682 : : const region *base_reg,
683 : : const svalue *sval,
684 : : logger *logger,
685 : : auto_vec<path_var> *out_pvs) const;
686 : :
687 : : const svalue *maybe_get_simple_value (store_manager *mgr) const;
688 : :
689 : : template <typename BindingVisitor>
690 : 108723 : void for_each_binding (BindingVisitor &v) const
691 : : {
692 : 221773 : for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
693 : : {
694 : 113050 : const binding_key *key = (*iter).first;
695 : 113050 : const svalue *&sval = (*iter).second;
696 : 113050 : v.on_binding (key, sval);
697 : : }
698 : 108723 : }
699 : :
700 : 8050 : iterator_t begin () const { return m_map.begin (); }
701 : 8050 : iterator_t end () const { return m_map.end (); }
702 : :
703 : 239 : const binding_map &get_map () const { return m_map; }
704 : :
705 : : private:
706 : : const svalue *get_any_value (const binding_key *key) const;
707 : : void bind_compound_sval (store_manager *mgr,
708 : : const region *reg,
709 : : const compound_svalue *compound_sval);
710 : : void bind_key (const binding_key *key, const svalue *sval);
711 : :
712 : : const region *m_base_region;
713 : :
714 : : binding_map m_map;
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. */
722 : : bool m_escaped;
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. */
728 : : bool m_touched;
729 : : };
730 : :
731 : : /* The mapping from regions to svalues.
732 : : This is actually expressed by subdividing into clusters, to better
733 : : handle aliasing. */
734 : :
735 : : class store
736 : : {
737 : : public:
738 : : typedef hash_map <const region *, binding_cluster *> cluster_map_t;
739 : :
740 : : store ();
741 : : store (const store &other);
742 : : ~store ();
743 : :
744 : : store &operator= (const store &other);
745 : :
746 : : bool operator== (const store &other) const;
747 : 431154 : bool operator!= (const store &other) const
748 : : {
749 : 431154 : 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 : 296296 : 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);
778 : : void mark_region_as_unknown (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;
785 : : binding_cluster *get_cluster (const region *base_reg);
786 : : binding_cluster *get_or_create_cluster (const region *base_reg);
787 : : void purge_cluster (const region *base_reg);
788 : :
789 : : template <typename T>
790 : 1779916 : void for_each_cluster (void (*cb) (const region *base_reg, T user_data),
791 : : T user_data) const
792 : : {
793 : 13087290 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
794 : 24394664 : iter != m_cluster_map.end (); ++iter)
795 : 11307374 : cb ((*iter).first, user_data);
796 : 1779916 : }
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 : :
807 : : void get_representative_path_vars (const region_model *model,
808 : : svalue_set *visited,
809 : : const svalue *sval,
810 : : logger *logger,
811 : : auto_vec<path_var> *out_pvs) const;
812 : :
813 : 1206047 : cluster_map_t::iterator begin () const { return m_cluster_map.begin (); }
814 : 8992278 : 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 : 29064 : void for_each_binding (BindingVisitor &v)
821 : : {
822 : 137787 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
823 : 137787 : iter != m_cluster_map.end (); ++iter)
824 : 108723 : (*iter).second->for_each_binding (v);
825 : 29064 : }
826 : :
827 : : void canonicalize (store_manager *mgr);
828 : : void loop_replay_fixup (const store *other_store,
829 : : region_model_manager *mgr);
830 : :
831 : : void replay_call_summary (call_summary_replay &r,
832 : : const store &summary);
833 : : void replay_call_summary_cluster (call_summary_replay &r,
834 : : const store &summary,
835 : : const region *base_reg);
836 : : void on_maybe_live_values (const svalue_set &maybe_live_values);
837 : :
838 : : private:
839 : : void remove_overlapping_bindings (store_manager *mgr, const region *reg,
840 : : uncertainty_t *uncertainty);
841 : : tristate eval_alias_1 (const region *base_reg_a,
842 : : const region *base_reg_b) const;
843 : :
844 : : cluster_map_t m_cluster_map;
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. */
852 : : bool m_called_unknown_fn;
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 : :
860 : 3773 : class store_manager
861 : : {
862 : : public:
863 : 3773 : store_manager (region_model_manager *mgr) : m_mgr (mgr) {}
864 : :
865 : : logger *get_logger () const;
866 : :
867 : : /* binding consolidation. */
868 : : const concrete_binding *
869 : : get_concrete_binding (bit_offset_t start_bit_offset,
870 : : bit_offset_t size_in_bits);
871 : : const concrete_binding *
872 : 27523 : get_concrete_binding (const bit_range &bits)
873 : : {
874 : 27523 : return get_concrete_binding (bits.get_start_bit_offset (),
875 : 27523 : bits.m_size_in_bits);
876 : : }
877 : : const concrete_binding *
878 : 8 : get_concrete_binding (const byte_range &bytes)
879 : : {
880 : 8 : bit_range bits = bytes.as_bit_range ();
881 : 8 : return get_concrete_binding (bits);
882 : : }
883 : : const symbolic_binding *
884 : : get_symbolic_binding (const region *region);
885 : :
886 : 5445478 : region_model_manager *get_svalue_manager () const
887 : : {
888 : 5445478 : return m_mgr;
889 : : }
890 : :
891 : : void log_stats (logger *logger, bool show_objs) const;
892 : :
893 : : private:
894 : : region_model_manager *m_mgr;
895 : : consolidation_map<concrete_binding> m_concrete_binding_key_mgr;
896 : : consolidation_map<symbolic_binding> m_symbolic_binding_key_mgr;
897 : : };
898 : :
899 : : } // namespace ana
900 : :
901 : : #endif /* GCC_ANALYZER_STORE_H */
|
