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 : 806244 : class uncertainty_t
161 : : {
162 : : public:
163 : : typedef hash_set<const svalue *>::iterator iterator;
164 : :
165 : 26356 : void on_maybe_bound_sval (const svalue *sval)
166 : : {
167 : 26356 : m_maybe_bound_svals.add (sval);
168 : : }
169 : 37464 : void on_mutable_sval_at_unknown_call (const svalue *sval)
170 : : {
171 : 37464 : m_mutable_at_unknown_call_svals.add (sval);
172 : : }
173 : :
174 : 582982 : bool unknown_sm_state_p (const svalue *sval)
175 : : {
176 : 582982 : return (m_maybe_bound_svals.contains (sval)
177 : 582982 : || 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 : 589613 : iterator begin_maybe_bound_svals () const
184 : : {
185 : 589613 : return m_maybe_bound_svals.begin ();
186 : : }
187 : 677912 : iterator end_maybe_bound_svals () const
188 : : {
189 : 677912 : 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 : 105674895 : class binding_key
209 : : {
210 : : public:
211 : 401278 : virtual ~binding_key () {}
212 : : virtual bool concrete_p () const = 0;
213 : 10929113 : 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 : 7850 : virtual const concrete_binding *dyn_cast_concrete_binding () const
225 : 7850 : { return nullptr; }
226 : 513830 : virtual const symbolic_binding *dyn_cast_symbolic_binding () const
227 : 513830 : { return nullptr; }
228 : : };
229 : :
230 : : /* A concrete range of bits. */
231 : :
232 : : struct bit_range
233 : : {
234 : 1933850 : bit_range (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
235 : 4371023 : : m_start_bit_offset (start_bit_offset),
236 : 2087122 : 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 : 1313363 : bool empty_p () const
245 : : {
246 : 1287437 : return m_size_in_bits == 0;
247 : : }
248 : :
249 : 1006370 : bit_offset_t get_start_bit_offset () const
250 : : {
251 : 722961 : return m_start_bit_offset;
252 : : }
253 : 678605 : bit_offset_t get_next_bit_offset () const
254 : : {
255 : 815405 : 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 : 10492432 : bool operator== (const bit_range &other) const
272 : : {
273 : 10492432 : return (m_start_bit_offset == other.m_start_bit_offset
274 : 10492432 : && m_size_in_bits == other.m_size_in_bits);
275 : : }
276 : :
277 : 111997 : bool intersects_p (const bit_range &other) const
278 : : {
279 : 111997 : return (get_start_bit_offset () < other.get_next_bit_offset ()
280 : 195658 : && 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 : 550 : operator< (const bit_range &other) const
304 : : {
305 : 550 : if (m_start_bit_offset < other.m_start_bit_offset)
306 : : return true;
307 : 400 : if (m_start_bit_offset > other.m_start_bit_offset)
308 : : return false;
309 : 284 : 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 : 23641 : byte_range (byte_offset_t start_byte_offset, byte_size_t size_in_bytes)
321 : 23127 : : m_start_byte_offset (start_byte_offset),
322 : 19242 : 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 : 3013 : bool empty_p () const
331 : : {
332 : 6026 : return m_size_in_bytes == 0;
333 : : }
334 : :
335 : 2952 : bool contains_p (byte_offset_t offset) const
336 : : {
337 : 8856 : return (offset >= get_start_byte_offset ()
338 : 5902 : && 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 : 17037 : byte_offset_t get_start_byte_offset () const
349 : : {
350 : 17037 : return m_start_byte_offset;
351 : : }
352 : 4102 : byte_offset_t get_next_byte_offset () const
353 : : {
354 : 4102 : return m_start_byte_offset + m_size_in_bytes;
355 : : }
356 : 3013 : byte_offset_t get_last_byte_offset () const
357 : : {
358 : 3013 : gcc_assert (!empty_p ());
359 : 3013 : return m_start_byte_offset + m_size_in_bytes - 1;
360 : : }
361 : :
362 : 736 : bit_range as_bit_range () const
363 : : {
364 : 2208 : return bit_range (m_start_byte_offset * BITS_PER_UNIT,
365 : 736 : 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 : 62598254 : 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 : 2278213 : concrete_binding (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
393 : 2278213 : : m_bit_range (start_bit_offset, size_in_bits)
394 : : {
395 : 2278213 : gcc_assert (m_bit_range.m_size_in_bits > 0);
396 : 2278213 : }
397 : 9936973 : bool concrete_p () const final override { return true; }
398 : :
399 : 11086795 : hashval_t hash () const
400 : : {
401 : 11086795 : inchash::hash hstate;
402 : 11086795 : hstate.add_wide_int (m_bit_range.m_start_bit_offset);
403 : 11086795 : hstate.add_wide_int (m_bit_range.m_size_in_bits);
404 : 11086795 : return hstate.end ();
405 : : }
406 : 10461451 : bool operator== (const concrete_binding &other) const
407 : : {
408 : 10461451 : 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 : 407682 : const concrete_binding *dyn_cast_concrete_binding () const final override
414 : 407682 : { return this; }
415 : :
416 : 138606 : const bit_range &get_bit_range () const { return m_bit_range; }
417 : : bool get_byte_range (byte_range *out) const;
418 : :
419 : 168860 : bit_offset_t get_start_bit_offset () const
420 : : {
421 : 160012 : return m_bit_range.m_start_bit_offset;
422 : : }
423 : 106823 : bit_size_t get_size_in_bits () const
424 : : {
425 : 106823 : return m_bit_range.m_size_in_bits;
426 : : }
427 : : /* Return the next bit offset after the end of this binding. */
428 : 1828 : bit_offset_t get_next_bit_offset () const
429 : : {
430 : 154639 : 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 : 58185 : void mark_empty () { m_bit_range.m_size_in_bits = -2; }
439 : 11653372 : bool is_deleted () const { return m_bit_range.m_size_in_bits == -1; }
440 : 39831239 : 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 : 30371259 : 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 : 1314200 : symbolic_binding (const region *region) : m_region (region) {}
474 : 1004777 : bool concrete_p () const final override { return false; }
475 : :
476 : 7117965 : hashval_t hash () const
477 : : {
478 : 7117965 : return (intptr_t)m_region;
479 : : }
480 : 7130217 : bool operator== (const symbolic_binding &other) const
481 : : {
482 : 7130217 : return m_region == other.m_region;
483 : : }
484 : :
485 : : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
486 : :
487 : 68608 : const symbolic_binding *dyn_cast_symbolic_binding () const final override
488 : 68608 : { return this; }
489 : :
490 : 68680 : 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 : 7741389 : bool is_deleted () const
497 : 7741389 : { 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 : :
517 : 100351 : class binding_map
518 : : {
519 : : public:
520 : : typedef hash_map <const binding_key *, const svalue *> map_t;
521 : : typedef map_t::iterator iterator_t;
522 : :
523 : 1658145 : binding_map () : m_map () {}
524 : : binding_map (const binding_map &other);
525 : : binding_map& operator=(const binding_map &other);
526 : :
527 : : bool operator== (const binding_map &other) const;
528 : 1999413 : bool operator!= (const binding_map &other) const
529 : : {
530 : 1999413 : return !(*this == other);
531 : : }
532 : :
533 : : hashval_t hash () const;
534 : :
535 : 4000928 : const svalue *get (const binding_key *key) const
536 : : {
537 : 4000928 : const svalue **slot = const_cast<map_t &> (m_map).get (key);
538 : 4000928 : if (slot)
539 : 3474838 : return *slot;
540 : : else
541 : : return nullptr;
542 : : }
543 : 1695585 : bool put (const binding_key *k, const svalue *v)
544 : : {
545 : 1695585 : gcc_assert (v);
546 : 1695585 : return m_map.put (k, v);
547 : : }
548 : :
549 : 176589 : void remove (const binding_key *k) { m_map.remove (k); }
550 : 1087640 : void empty () { m_map.empty (); }
551 : :
552 : 17852376 : iterator_t begin () const { return m_map.begin (); }
553 : 26580605 : iterator_t end () const { return m_map.end (); }
554 : 675284 : size_t elements () const { return m_map.elements (); }
555 : :
556 : : void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
557 : : void dump (bool simple) const;
558 : :
559 : : std::unique_ptr<json::object> to_json () const;
560 : :
561 : : void add_to_tree_widget (text_art::tree_widget &parent_widget,
562 : : const text_art::dump_widget_info &dwi) const;
563 : :
564 : : bool apply_ctor_to_region (const region *parent_reg, tree ctor,
565 : : region_model_manager *mgr);
566 : :
567 : : static int cmp (const binding_map &map1, const binding_map &map2);
568 : :
569 : : void remove_overlapping_bindings (store_manager *mgr,
570 : : const binding_key *drop_key,
571 : : uncertainty_t *uncertainty,
572 : : svalue_set *maybe_live_values,
573 : : bool always_overlap);
574 : :
575 : : private:
576 : : void get_overlapping_bindings (const binding_key *key,
577 : : auto_vec<const binding_key *> *out);
578 : : bool apply_ctor_val_to_range (const region *parent_reg,
579 : : region_model_manager *mgr,
580 : : tree min_index, tree max_index,
581 : : tree val);
582 : : bool apply_ctor_pair_to_child_region (const region *parent_reg,
583 : : region_model_manager *mgr,
584 : : tree index, tree val);
585 : :
586 : : map_t m_map;
587 : : };
588 : :
589 : : /* Concept: BindingVisitor, for use by binding_cluster::for_each_binding
590 : : and store::for_each_binding.
591 : :
592 : : Should implement:
593 : : void on_binding (const binding_key *key, const svalue *&sval);
594 : : */
595 : :
596 : : /* All of the bindings within a store for regions that share the same
597 : : base region. */
598 : :
599 : 25353228 : class binding_cluster
600 : : {
601 : : public:
602 : : friend class store;
603 : :
604 : : typedef hash_map <const binding_key *, const svalue *> map_t;
605 : : typedef map_t::iterator iterator_t;
606 : :
607 : : binding_cluster (const region *base_region);
608 : : binding_cluster (const binding_cluster &other);
609 : : binding_cluster& operator=(const binding_cluster &other);
610 : :
611 : : bool operator== (const binding_cluster &other) const;
612 : 1999413 : bool operator!= (const binding_cluster &other) const
613 : : {
614 : 1999413 : return !(*this == other);
615 : : }
616 : :
617 : : hashval_t hash () const;
618 : :
619 : : bool symbolic_p () const;
620 : :
621 : 82382 : const region *get_base_region () const { return m_base_region; }
622 : :
623 : : void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
624 : : void dump (bool simple) const;
625 : :
626 : : void validate () const;
627 : :
628 : : std::unique_ptr<json::object> to_json () const;
629 : :
630 : : std::unique_ptr<text_art::tree_widget>
631 : : make_dump_widget (const text_art::dump_widget_info &dwi,
632 : : store_manager *mgr) const;
633 : :
634 : : void bind (store_manager *mgr, const region *, const svalue *);
635 : :
636 : : void clobber_region (store_manager *mgr, const region *reg);
637 : : void purge_region (store_manager *mgr, const region *reg);
638 : : void fill_region (store_manager *mgr, const region *reg, const svalue *sval);
639 : : void zero_fill_region (store_manager *mgr, const region *reg);
640 : : void mark_region_as_unknown (store_manager *mgr,
641 : : const region *reg_to_bind,
642 : : const region *reg_for_overlap,
643 : : uncertainty_t *uncertainty,
644 : : svalue_set *maybe_live_values);
645 : : void purge_state_involving (const svalue *sval,
646 : : region_model_manager *sval_mgr);
647 : :
648 : : const svalue *get_binding (store_manager *mgr, const region *reg) const;
649 : : const svalue *get_binding_recursive (store_manager *mgr,
650 : : const region *reg) const;
651 : : const svalue *get_any_binding (store_manager *mgr,
652 : : const region *reg) const;
653 : : const svalue *maybe_get_compound_binding (store_manager *mgr,
654 : : const region *reg) const;
655 : :
656 : : void remove_overlapping_bindings (store_manager *mgr, const region *reg,
657 : : uncertainty_t *uncertainty,
658 : : svalue_set *maybe_live_values);
659 : :
660 : : template <typename T>
661 : 7525725 : void for_each_value (void (*cb) (const svalue *sval, T user_data),
662 : : T user_data) const
663 : : {
664 : 23721369 : for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
665 : 8097822 : cb ((*iter).second, user_data);
666 : 7525725 : }
667 : :
668 : : static bool can_merge_p (const binding_cluster *cluster_a,
669 : : const binding_cluster *cluster_b,
670 : : binding_cluster *out_cluster,
671 : : store *out_store,
672 : : store_manager *mgr,
673 : : model_merger *merger);
674 : : void make_unknown_relative_to (const binding_cluster *other_cluster,
675 : : store *out_store,
676 : : store_manager *mgr);
677 : :
678 : : void mark_as_escaped ();
679 : : void on_unknown_fncall (const gcall &call, store_manager *mgr,
680 : : const conjured_purge &p);
681 : : void on_asm (const gasm *stmt, store_manager *mgr,
682 : : const conjured_purge &p);
683 : :
684 : : bool escaped_p () const;
685 : 288842 : bool touched_p () const { return m_touched; }
686 : :
687 : : bool redundant_p () const;
688 : 252544 : bool empty_p () const { return m_map.elements () == 0; }
689 : :
690 : : void get_representative_path_vars (const region_model *model,
691 : : svalue_set *visited,
692 : : const region *base_reg,
693 : : const svalue *sval,
694 : : logger *logger,
695 : : auto_vec<path_var> *out_pvs) const;
696 : :
697 : : const svalue *maybe_get_simple_value (store_manager *mgr) const;
698 : :
699 : : template <typename BindingVisitor>
700 : 139546 : void for_each_binding (BindingVisitor &v) const
701 : : {
702 : 282650 : for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
703 : : {
704 : 143104 : const binding_key *key = (*iter).first;
705 : 143104 : const svalue *&sval = (*iter).second;
706 : 143104 : v.on_binding (key, sval);
707 : : }
708 : 139546 : }
709 : :
710 : 7298 : iterator_t begin () const { return m_map.begin (); }
711 : 7298 : iterator_t end () const { return m_map.end (); }
712 : :
713 : 239 : const binding_map &get_map () const { return m_map; }
714 : :
715 : : private:
716 : : const svalue *get_any_value (const binding_key *key) const;
717 : : void bind_compound_sval (store_manager *mgr,
718 : : const region *reg,
719 : : const compound_svalue *compound_sval);
720 : : void bind_key (const binding_key *key, const svalue *sval);
721 : :
722 : : const region *m_base_region;
723 : :
724 : : binding_map m_map;
725 : :
726 : : /* Has a pointer to this cluster "escaped" into a part of the program
727 : : we don't know about (via a call to a function with an unknown body,
728 : : or by being passed in as a pointer param of a "top-level" function call).
729 : : Such regions could be overwritten when other such functions are called,
730 : : even if the region is no longer reachable by pointers that we are
731 : : tracking. */
732 : : bool m_escaped;
733 : :
734 : : /* Has this cluster been written to via a symbolic binding?
735 : : If so, then we don't know anything about unbound subregions,
736 : : so we can't use initial_svalue, treat them as uninitialized, or
737 : : inherit values from a parent region. */
738 : : bool m_touched;
739 : : };
740 : :
741 : : /* The mapping from regions to svalues.
742 : : This is actually expressed by subdividing into clusters, to better
743 : : handle aliasing. */
744 : :
745 : : class store
746 : : {
747 : : public:
748 : : typedef hash_map <const region *, binding_cluster *> cluster_map_t;
749 : :
750 : : store ();
751 : : store (const store &other);
752 : : ~store ();
753 : :
754 : : store &operator= (const store &other);
755 : :
756 : : bool operator== (const store &other) const;
757 : 454011 : bool operator!= (const store &other) const
758 : : {
759 : 454011 : return !(*this == other);
760 : : }
761 : :
762 : : hashval_t hash () const;
763 : :
764 : : void dump_to_pp (pretty_printer *pp, bool summarize, bool multiline,
765 : : store_manager *mgr) const;
766 : : void dump (bool simple) const;
767 : : void summarize_to_pp (pretty_printer *pp, bool simple) const;
768 : :
769 : : void validate () const;
770 : :
771 : : std::unique_ptr<json::object> to_json () const;
772 : :
773 : : std::unique_ptr<text_art::tree_widget>
774 : : make_dump_widget (const text_art::dump_widget_info &dwi,
775 : : store_manager *mgr) const;
776 : :
777 : : const svalue *get_any_binding (store_manager *mgr, const region *reg) const;
778 : :
779 : 294157 : bool called_unknown_fn_p () const { return m_called_unknown_fn; }
780 : :
781 : : void set_value (store_manager *mgr, const region *lhs_reg,
782 : : const svalue *rhs_sval,
783 : : uncertainty_t *uncertainty);
784 : : void clobber_region (store_manager *mgr, const region *reg);
785 : : void purge_region (store_manager *mgr, const region *reg);
786 : : void fill_region (store_manager *mgr, const region *reg, const svalue *sval);
787 : : void zero_fill_region (store_manager *mgr, const region *reg);
788 : : void mark_region_as_unknown (store_manager *mgr, const region *reg,
789 : : uncertainty_t *uncertainty,
790 : : svalue_set *maybe_live_values);
791 : : void purge_state_involving (const svalue *sval,
792 : : region_model_manager *sval_mgr);
793 : :
794 : : const binding_cluster *get_cluster (const region *base_reg) const;
795 : : binding_cluster *get_cluster (const region *base_reg);
796 : : binding_cluster *get_or_create_cluster (const region *base_reg);
797 : : void purge_cluster (const region *base_reg);
798 : :
799 : : template <typename T>
800 : 1843825 : void for_each_cluster (void (*cb) (const region *base_reg, T user_data),
801 : : T user_data) const
802 : : {
803 : 13241552 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
804 : 24639279 : iter != m_cluster_map.end (); ++iter)
805 : 11397727 : cb ((*iter).first, user_data);
806 : 1843825 : }
807 : :
808 : : static bool can_merge_p (const store *store_a, const store *store_b,
809 : : store *out_store, store_manager *mgr,
810 : : model_merger *merger);
811 : :
812 : : void mark_as_escaped (const region *base_reg);
813 : : void on_unknown_fncall (const gcall &call, store_manager *mgr,
814 : : const conjured_purge &p);
815 : : bool escaped_p (const region *reg) const;
816 : :
817 : : void get_representative_path_vars (const region_model *model,
818 : : svalue_set *visited,
819 : : const svalue *sval,
820 : : logger *logger,
821 : : auto_vec<path_var> *out_pvs) const;
822 : :
823 : 1256594 : cluster_map_t::iterator begin () const { return m_cluster_map.begin (); }
824 : 9134481 : cluster_map_t::iterator end () const { return m_cluster_map.end (); }
825 : :
826 : : tristate eval_alias (const region *base_reg_a,
827 : : const region *base_reg_b) const;
828 : :
829 : : template <typename BindingVisitor>
830 : 36645 : void for_each_binding (BindingVisitor &v)
831 : : {
832 : 176191 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
833 : 176191 : iter != m_cluster_map.end (); ++iter)
834 : 139546 : (*iter).second->for_each_binding (v);
835 : 36645 : }
836 : :
837 : : void canonicalize (store_manager *mgr);
838 : : void loop_replay_fixup (const store *other_store,
839 : : region_model_manager *mgr);
840 : :
841 : : void replay_call_summary (call_summary_replay &r,
842 : : const store &summary);
843 : : void replay_call_summary_cluster (call_summary_replay &r,
844 : : const store &summary,
845 : : const region *base_reg);
846 : : void on_maybe_live_values (const svalue_set &maybe_live_values);
847 : :
848 : : private:
849 : : void remove_overlapping_bindings (store_manager *mgr, const region *reg,
850 : : uncertainty_t *uncertainty);
851 : : tristate eval_alias_1 (const region *base_reg_a,
852 : : const region *base_reg_b) const;
853 : :
854 : : cluster_map_t m_cluster_map;
855 : :
856 : : /* If this is true, then unknown code has been called, and so
857 : : any global variable that isn't currently modelled by the store
858 : : has unknown state, rather than being in an "initial state".
859 : : This is to avoid having to mark (and thus explicitly track)
860 : : every global when an unknown function is called; instead, they
861 : : can be tracked implicitly. */
862 : : bool m_called_unknown_fn;
863 : : };
864 : :
865 : : /* A class responsible for owning and consolidating binding keys
866 : : (both concrete and symbolic).
867 : : Key instances are immutable as far as clients are concerned, so they
868 : : are provided as "const" ptrs. */
869 : :
870 : 3886 : class store_manager
871 : : {
872 : : public:
873 : 3886 : store_manager (region_model_manager *mgr) : m_mgr (mgr) {}
874 : :
875 : : logger *get_logger () const;
876 : :
877 : : /* binding consolidation. */
878 : : const concrete_binding *
879 : : get_concrete_binding (bit_offset_t start_bit_offset,
880 : : bit_offset_t size_in_bits);
881 : : const concrete_binding *
882 : 21025 : get_concrete_binding (const bit_range &bits)
883 : : {
884 : 21025 : return get_concrete_binding (bits.get_start_bit_offset (),
885 : 21025 : bits.m_size_in_bits);
886 : : }
887 : : const concrete_binding *
888 : 8 : get_concrete_binding (const byte_range &bytes)
889 : : {
890 : 8 : bit_range bits = bytes.as_bit_range ();
891 : 8 : return get_concrete_binding (bits);
892 : : }
893 : : const symbolic_binding *
894 : : get_symbolic_binding (const region *region);
895 : :
896 : 5470235 : region_model_manager *get_svalue_manager () const
897 : : {
898 : 5470235 : return m_mgr;
899 : : }
900 : :
901 : : void log_stats (logger *logger, bool show_objs) const;
902 : :
903 : : private:
904 : : region_model_manager *m_mgr;
905 : : consolidation_map<concrete_binding> m_concrete_binding_key_mgr;
906 : : consolidation_map<symbolic_binding> m_symbolic_binding_key_mgr;
907 : : };
908 : :
909 : : } // namespace ana
910 : :
911 : : #endif /* GCC_ANALYZER_STORE_H */
|
