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