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 : : /* Implementation of the region-based ternary model described in:
25 : : "A Memory Model for Static Analysis of C Programs"
26 : : (Zhongxing Xu, Ted Kremenek, and Jian Zhang)
27 : : http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf */
28 : :
29 : : /* The store models memory as a collection of "clusters", where regions
30 : : are partitioned into clusters via their base region.
31 : :
32 : : For example, given:
33 : : int a, b, c;
34 : : struct coord { double x; double y; } verts[3];
35 : : then "verts[0].y" and "verts[1].x" both have "verts" as their base region.
36 : : Each of a, b, c, and verts will have their own clusters, so that we
37 : : know that writes to e.g. "verts[1].x".don't affect e.g. "a".
38 : :
39 : : Within each cluster we store a map of bindings to values, where the
40 : : binding keys can be either concrete or symbolic.
41 : :
42 : : Concrete bindings affect a specific range of bits relative to the start
43 : : of the base region of the cluster, whereas symbolic bindings affect
44 : : a specific subregion within the cluster.
45 : :
46 : : Consider (from the symbolic-1.c testcase):
47 : :
48 : : char arr[1024];
49 : : arr[2] = a; (1)
50 : : arr[3] = b; (2)
51 : : After (1) and (2), the cluster for "arr" has concrete bindings
52 : : for bits 16-23 and for bits 24-31, with svalues "INIT_VAL(a)"
53 : : and "INIT_VAL(b)" respectively:
54 : : cluster: {bits 16-23: "INIT_VAL(a)",
55 : : bits 24-31: "INIT_VAL(b)";
56 : : flags: {}}
57 : : Attempting to query unbound subregions e.g. arr[4] will
58 : : return "UNINITIALIZED".
59 : : "a" and "b" are each in their own clusters, with no explicit
60 : : bindings, and thus implicitly have value INIT_VAL(a) and INIT_VAL(b).
61 : :
62 : : arr[3] = c; (3)
63 : : After (3), the concrete binding for bits 24-31 is replaced with the
64 : : svalue "INIT_VAL(c)":
65 : : cluster: {bits 16-23: "INIT_VAL(a)", (from before)
66 : : bits 24-31: "INIT_VAL(c)"; (updated)
67 : : flags: {}}
68 : :
69 : : arr[i] = d; (4)
70 : : After (4), we lose the concrete bindings and replace them with a
71 : : symbolic binding for "arr[i]", with svalue "INIT_VAL(d)". We also
72 : : mark the cluster as having been "symbolically touched": future
73 : : attempts to query the values of subregions other than "arr[i]",
74 : : such as "arr[3]" are "UNKNOWN", since we don't know if the write
75 : : to arr[i] affected them.
76 : : cluster: {symbolic_key(arr[i]): "INIT_VAL(d)";
77 : : flags: {TOUCHED}}
78 : :
79 : : arr[j] = e; (5)
80 : : After (5), we lose the symbolic binding for "arr[i]" since we could
81 : : have overwritten it, and add a symbolic binding for "arr[j]".
82 : : cluster: {symbolic_key(arr[j]): "INIT_VAL(d)"; (different symbolic
83 : : flags: {TOUCHED}} binding)
84 : :
85 : : arr[3] = f; (6)
86 : : After (6), we lose the symbolic binding for "arr[j]" since we could
87 : : have overwritten it, and gain a concrete binding for bits 24-31
88 : : again, this time with svalue "INIT_VAL(e)":
89 : : cluster: {bits 24-31: "INIT_VAL(d)";
90 : : flags: {TOUCHED}}
91 : : The cluster is still flagged as touched, so that we know that
92 : : accesses to other elements are "UNKNOWN" rather than
93 : : "UNINITIALIZED".
94 : :
95 : : Handling symbolic regions requires us to handle aliasing.
96 : :
97 : : In the first example above, each of a, b, c and verts are non-symbolic
98 : : base regions and so their clusters are "concrete clusters", whereas given:
99 : : struct coord *p, *q;
100 : : then "*p" and "*q" are symbolic base regions, and thus "*p" and "*q"
101 : : have "symbolic clusters".
102 : :
103 : : In the above, "verts[i].x" will have a symbolic *binding* within a
104 : : concrete cluster for "verts", whereas "*p" is a symbolic *cluster*.
105 : :
106 : : Writes to concrete clusters can't affect other concrete clusters,
107 : : but can affect symbolic clusters; e.g. after:
108 : : verts[0].x = 42;
109 : : we bind 42 in the cluster for "verts", but the clusters for "b" and "c"
110 : : can't be affected. Any symbolic clusters for *p and for *q can be
111 : : affected, *p and *q could alias verts.
112 : :
113 : : Writes to a symbolic cluster can affect other clusters, both
114 : : concrete and symbolic; e.g. after:
115 : : p->x = 17;
116 : : we bind 17 within the cluster for "*p". The concrete clusters for a, b,
117 : : c, and verts could be affected, depending on whether *p aliases them.
118 : : Similarly, the symbolic cluster to *q could be affected. */
119 : :
120 : : namespace ana {
121 : :
122 : : /* A class for keeping track of aspects of a program_state that we don't
123 : : know about, to avoid false positives about leaks.
124 : :
125 : : Consider:
126 : :
127 : : p->field = malloc (1024);
128 : : q->field = NULL;
129 : :
130 : : where we don't know whether or not p and q point to the same memory,
131 : : and:
132 : :
133 : : p->field = malloc (1024);
134 : : unknown_fn (p);
135 : :
136 : : In both cases, the svalue for the address of the allocated buffer
137 : : goes from being bound to p->field to not having anything explicitly bound
138 : : to it.
139 : :
140 : : Given that we conservatively discard bindings due to possible aliasing or
141 : : calls to unknown function, the store loses references to svalues,
142 : : but these svalues could still be live. We don't want to warn about
143 : : them leaking - they're effectively in a "maybe live" state.
144 : :
145 : : This "maybe live" information is somewhat transient.
146 : :
147 : : We don't want to store this "maybe live" information in the program_state,
148 : : region_model, or store, since we don't want to bloat these objects (and
149 : : potentially bloat the exploded_graph with more nodes).
150 : : However, we can't store it in the region_model_context, as these context
151 : : objects sometimes don't last long enough to be around when comparing the
152 : : old vs the new state.
153 : :
154 : : This class is a way to track a set of such svalues, so that we can
155 : : temporarily capture that they are in a "maybe live" state whilst
156 : : comparing old and new states. */
157 : :
158 : 910079 : class uncertainty_t
159 : : {
160 : : public:
161 : : typedef hash_set<const svalue *>::iterator iterator;
162 : :
163 : 33413 : void on_maybe_bound_sval (const svalue *sval)
164 : : {
165 : 33413 : m_maybe_bound_svals.add (sval);
166 : : }
167 : 41772 : void on_mutable_sval_at_unknown_call (const svalue *sval)
168 : : {
169 : 41772 : m_mutable_at_unknown_call_svals.add (sval);
170 : : }
171 : :
172 : 698509 : bool unknown_sm_state_p (const svalue *sval)
173 : : {
174 : 698509 : return (m_maybe_bound_svals.contains (sval)
175 : 698509 : || m_mutable_at_unknown_call_svals.contains (sval));
176 : : }
177 : :
178 : : void dump_to_pp (pretty_printer *pp, bool simple) const;
179 : : void dump (bool simple) const;
180 : :
181 : 687489 : iterator begin_maybe_bound_svals () const
182 : : {
183 : 687489 : return m_maybe_bound_svals.begin ();
184 : : }
185 : 798594 : iterator end_maybe_bound_svals () const
186 : : {
187 : 798594 : return m_maybe_bound_svals.end ();
188 : : }
189 : :
190 : : private:
191 : :
192 : : /* svalues that might or might not still be bound. */
193 : : hash_set<const svalue *> m_maybe_bound_svals;
194 : :
195 : : /* svalues that have mutable sm-state at unknown calls. */
196 : : hash_set<const svalue *> m_mutable_at_unknown_call_svals;
197 : : };
198 : :
199 : : class byte_range;
200 : : class concrete_binding;
201 : : class symbolic_binding;
202 : :
203 : : /* Abstract base class for describing ranges of bits within a binding_map
204 : : that can have svalues bound to them. */
205 : :
206 : 127706442 : class binding_key
207 : : {
208 : : public:
209 : 449895 : virtual ~binding_key () {}
210 : : virtual bool concrete_p () const = 0;
211 : 13036925 : bool symbolic_p () const { return !concrete_p (); }
212 : :
213 : : static const binding_key *make (store_manager *mgr, const region *r);
214 : :
215 : : virtual void dump_to_pp (pretty_printer *pp, bool simple) const = 0;
216 : : void dump (bool simple) const;
217 : : label_text get_desc (bool simple=true) const;
218 : :
219 : : static int cmp_ptrs (const void *, const void *);
220 : : static int cmp (const binding_key *, const binding_key *);
221 : :
222 : 9029 : virtual const concrete_binding *dyn_cast_concrete_binding () const
223 : 9029 : { return NULL; }
224 : 583423 : virtual const symbolic_binding *dyn_cast_symbolic_binding () const
225 : 583423 : { return NULL; }
226 : : };
227 : :
228 : : /* A concrete range of bits. */
229 : :
230 : : struct bit_range
231 : : {
232 : 2265835 : bit_range (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
233 : 5225200 : : m_start_bit_offset (start_bit_offset),
234 : 2466099 : m_size_in_bits (size_in_bits)
235 : : {}
236 : :
237 : : void dump_to_pp (pretty_printer *pp) const;
238 : : void dump () const;
239 : :
240 : : json::object *to_json () const;
241 : :
242 : 1546115 : bool empty_p () const
243 : : {
244 : 1509179 : return m_size_in_bits == 0;
245 : : }
246 : :
247 : 1236828 : bit_offset_t get_start_bit_offset () const
248 : : {
249 : 864156 : return m_start_bit_offset;
250 : : }
251 : 803060 : bit_offset_t get_next_bit_offset () const
252 : : {
253 : 983027 : return m_start_bit_offset + m_size_in_bits;
254 : : }
255 : 37706 : bit_offset_t get_last_bit_offset () const
256 : : {
257 : 37706 : gcc_assert (!empty_p ());
258 : 37706 : return get_next_bit_offset () - 1;
259 : : }
260 : :
261 : 87915 : bool contains_p (bit_offset_t offset) const
262 : : {
263 : 87915 : return (offset >= get_start_bit_offset ()
264 : 163398 : && offset < get_next_bit_offset ());
265 : : }
266 : :
267 : : bool contains_p (const bit_range &other, bit_range *out) const;
268 : :
269 : 12867853 : bool operator== (const bit_range &other) const
270 : : {
271 : 12867853 : return (m_start_bit_offset == other.m_start_bit_offset
272 : 12867853 : && m_size_in_bits == other.m_size_in_bits);
273 : : }
274 : :
275 : 141773 : bool intersects_p (const bit_range &other) const
276 : : {
277 : 141773 : return (get_start_bit_offset () < other.get_next_bit_offset ()
278 : 245918 : && other.get_start_bit_offset () < get_next_bit_offset ());
279 : : }
280 : : bool intersects_p (const bit_range &other,
281 : : bit_size_t *out_num_overlap_bits) const;
282 : : bool intersects_p (const bit_range &other,
283 : : bit_range *out_this,
284 : : bit_range *out_other) const;
285 : :
286 : : bool exceeds_p (const bit_range &other,
287 : : bit_range *out_overhanging_bit_range) const;
288 : :
289 : : bool falls_short_of_p (bit_offset_t offset,
290 : : bit_range *out_fall_short_bits) const;
291 : :
292 : : static int cmp (const bit_range &br1, const bit_range &br2);
293 : :
294 : : bit_range operator- (bit_offset_t offset) const;
295 : :
296 : : static bool from_mask (unsigned HOST_WIDE_INT mask, bit_range *out);
297 : :
298 : : bool as_byte_range (byte_range *out) const;
299 : :
300 : : bit_offset_t m_start_bit_offset;
301 : : bit_size_t m_size_in_bits;
302 : : };
303 : :
304 : : /* A concrete range of bytes. */
305 : :
306 : : struct byte_range
307 : : {
308 : 25287 : byte_range (byte_offset_t start_byte_offset, byte_size_t size_in_bytes)
309 : 25109 : : m_start_byte_offset (start_byte_offset),
310 : 20660 : m_size_in_bytes (size_in_bytes)
311 : : {}
312 : :
313 : : void dump_to_pp (pretty_printer *pp) const;
314 : : void dump () const;
315 : :
316 : : json::object *to_json () const;
317 : :
318 : 2953 : bool empty_p () const
319 : : {
320 : 5906 : return m_size_in_bytes == 0;
321 : : }
322 : :
323 : 3103 : bool contains_p (byte_offset_t offset) const
324 : : {
325 : 9309 : return (offset >= get_start_byte_offset ()
326 : 6204 : && offset < get_next_byte_offset ());
327 : : }
328 : : bool contains_p (const byte_range &other, byte_range *out) const;
329 : :
330 : : bool operator== (const byte_range &other) const
331 : : {
332 : : return (m_start_byte_offset == other.m_start_byte_offset
333 : : && m_size_in_bytes == other.m_size_in_bytes);
334 : : }
335 : :
336 : 19226 : byte_offset_t get_start_byte_offset () const
337 : : {
338 : 19226 : return m_start_byte_offset;
339 : : }
340 : 4431 : byte_offset_t get_next_byte_offset () const
341 : : {
342 : 4431 : return m_start_byte_offset + m_size_in_bytes;
343 : : }
344 : 2953 : byte_offset_t get_last_byte_offset () const
345 : : {
346 : 2953 : gcc_assert (!empty_p ());
347 : 2953 : return m_start_byte_offset + m_size_in_bytes - 1;
348 : : }
349 : :
350 : 828 : bit_range as_bit_range () const
351 : : {
352 : 2484 : return bit_range (m_start_byte_offset * BITS_PER_UNIT,
353 : 828 : m_size_in_bytes * BITS_PER_UNIT);
354 : : }
355 : :
356 : 0 : bit_offset_t get_start_bit_offset () const
357 : : {
358 : 0 : return m_start_byte_offset * BITS_PER_UNIT;
359 : : }
360 : 0 : bit_offset_t get_next_bit_offset () const
361 : : {
362 : 0 : return get_next_byte_offset () * BITS_PER_UNIT;
363 : : }
364 : :
365 : : static int cmp (const byte_range &br1, const byte_range &br2);
366 : :
367 : : byte_offset_t m_start_byte_offset;
368 : : byte_size_t m_size_in_bytes;
369 : : };
370 : :
371 : : /* Concrete subclass of binding_key, for describing a non-empty
372 : : concrete range of bits within the binding_map (e.g. "bits 8-15"). */
373 : :
374 : 76076747 : class concrete_binding : public binding_key
375 : : {
376 : : public:
377 : : /* This class is its own key for the purposes of consolidation. */
378 : : typedef concrete_binding key_t;
379 : :
380 : 2750855 : concrete_binding (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
381 : 2750855 : : m_bit_range (start_bit_offset, size_in_bits)
382 : : {
383 : 2750855 : gcc_assert (m_bit_range.m_size_in_bits > 0);
384 : 2750855 : }
385 : 11840323 : bool concrete_p () const final override { return true; }
386 : :
387 : 13535404 : hashval_t hash () const
388 : : {
389 : 13535404 : inchash::hash hstate;
390 : 13535404 : hstate.add_wide_int (m_bit_range.m_start_bit_offset);
391 : 13535404 : hstate.add_wide_int (m_bit_range.m_size_in_bits);
392 : 13535404 : return hstate.end ();
393 : : }
394 : 12828978 : bool operator== (const concrete_binding &other) const
395 : : {
396 : 12828978 : return m_bit_range == other.m_bit_range;
397 : : }
398 : :
399 : : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
400 : :
401 : 513553 : const concrete_binding *dyn_cast_concrete_binding () const final override
402 : 513553 : { return this; }
403 : :
404 : 180366 : const bit_range &get_bit_range () const { return m_bit_range; }
405 : : bool get_byte_range (byte_range *out) const;
406 : :
407 : 224272 : bit_offset_t get_start_bit_offset () const
408 : : {
409 : 214160 : return m_bit_range.m_start_bit_offset;
410 : : }
411 : 125453 : bit_size_t get_size_in_bits () const
412 : : {
413 : 125453 : return m_bit_range.m_size_in_bits;
414 : : }
415 : : /* Return the next bit offset after the end of this binding. */
416 : 1774 : bit_offset_t get_next_bit_offset () const
417 : : {
418 : 207838 : return m_bit_range.get_next_bit_offset ();
419 : : }
420 : :
421 : : bool overlaps_p (const concrete_binding &other) const;
422 : :
423 : : static int cmp_ptr_ptr (const void *, const void *);
424 : :
425 : : void mark_deleted () { m_bit_range.m_size_in_bits = -1; }
426 : 65262 : void mark_empty () { m_bit_range.m_size_in_bits = -2; }
427 : 14243201 : bool is_deleted () const { return m_bit_range.m_size_in_bits == -1; }
428 : 48267912 : bool is_empty () const { return m_bit_range.m_size_in_bits == -2; }
429 : :
430 : : private:
431 : : bit_range m_bit_range;
432 : : };
433 : :
434 : : } // namespace ana
435 : :
436 : : template <>
437 : : template <>
438 : : inline bool
439 : 0 : is_a_helper <const ana::concrete_binding *>::test (const ana::binding_key *key)
440 : : {
441 : 0 : return key->concrete_p ();
442 : : }
443 : :
444 : : template <> struct default_hash_traits<ana::concrete_binding>
445 : : : public member_function_hash_traits<ana::concrete_binding>
446 : : {
447 : : static const bool empty_zero_p = false;
448 : : };
449 : :
450 : : namespace ana {
451 : :
452 : : /* Concrete subclass of binding_key, for describing a symbolic set of
453 : : bits within the binding_map in terms of a region (e.g. "arr[i]"). */
454 : :
455 : 36344081 : class symbolic_binding : public binding_key
456 : : {
457 : : public:
458 : : /* This class is its own key for the purposes of consolidation. */
459 : : typedef symbolic_binding key_t;
460 : :
461 : 1559885 : symbolic_binding (const region *region) : m_region (region) {}
462 : 1210584 : bool concrete_p () const final override { return false; }
463 : :
464 : 8685877 : hashval_t hash () const
465 : : {
466 : 8685877 : return (intptr_t)m_region;
467 : : }
468 : 8615592 : bool operator== (const symbolic_binding &other) const
469 : : {
470 : 8615592 : return m_region == other.m_region;
471 : : }
472 : :
473 : : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
474 : :
475 : 75987 : const symbolic_binding *dyn_cast_symbolic_binding () const final override
476 : 75987 : { return this; }
477 : :
478 : 76085 : const region *get_region () const { return m_region; }
479 : :
480 : : static int cmp_ptr_ptr (const void *, const void *);
481 : :
482 : : void mark_deleted () { m_region = reinterpret_cast<const region *> (1); }
483 : 0 : void mark_empty () { m_region = NULL; }
484 : 9351075 : bool is_deleted () const
485 : 9351075 : { return m_region == reinterpret_cast<const region *> (1); }
486 : : bool is_empty () const { return m_region == NULL; }
487 : :
488 : : private:
489 : : const region *m_region;
490 : : };
491 : :
492 : : } // namespace ana
493 : :
494 : : template <> struct default_hash_traits<ana::symbolic_binding>
495 : : : public member_function_hash_traits<ana::symbolic_binding>
496 : : {
497 : : static const bool empty_zero_p = true;
498 : : };
499 : :
500 : : namespace ana {
501 : :
502 : : /* A mapping from binding_keys to svalues, for use by binding_cluster
503 : : and compound_svalue. */
504 : :
505 : 118090 : class binding_map
506 : : {
507 : : public:
508 : : typedef hash_map <const binding_key *, const svalue *> map_t;
509 : : typedef map_t::iterator iterator_t;
510 : :
511 : 1960196 : binding_map () : m_map () {}
512 : : binding_map (const binding_map &other);
513 : : binding_map& operator=(const binding_map &other);
514 : :
515 : : bool operator== (const binding_map &other) const;
516 : 2338695 : bool operator!= (const binding_map &other) const
517 : : {
518 : 2338695 : return !(*this == other);
519 : : }
520 : :
521 : : hashval_t hash () const;
522 : :
523 : 4778737 : const svalue *get (const binding_key *key) const
524 : : {
525 : 4778737 : const svalue **slot = const_cast<map_t &> (m_map).get (key);
526 : 4778737 : if (slot)
527 : 4159611 : return *slot;
528 : : else
529 : : return NULL;
530 : : }
531 : 2041195 : bool put (const binding_key *k, const svalue *v)
532 : : {
533 : 2041195 : gcc_assert (v);
534 : 2041195 : return m_map.put (k, v);
535 : : }
536 : :
537 : 214488 : void remove (const binding_key *k) { m_map.remove (k); }
538 : 1290073 : void empty () { m_map.empty (); }
539 : :
540 : 21121012 : iterator_t begin () const { return m_map.begin (); }
541 : 31568000 : iterator_t end () const { return m_map.end (); }
542 : 784961 : size_t elements () const { return m_map.elements (); }
543 : :
544 : : void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
545 : : void dump (bool simple) const;
546 : :
547 : : json::object *to_json () const;
548 : :
549 : : bool apply_ctor_to_region (const region *parent_reg, tree ctor,
550 : : region_model_manager *mgr);
551 : :
552 : : static int cmp (const binding_map &map1, const binding_map &map2);
553 : :
554 : : void remove_overlapping_bindings (store_manager *mgr,
555 : : const binding_key *drop_key,
556 : : uncertainty_t *uncertainty,
557 : : svalue_set *maybe_live_values,
558 : : bool always_overlap);
559 : :
560 : : private:
561 : : void get_overlapping_bindings (const binding_key *key,
562 : : auto_vec<const binding_key *> *out);
563 : : bool apply_ctor_val_to_range (const region *parent_reg,
564 : : region_model_manager *mgr,
565 : : tree min_index, tree max_index,
566 : : tree val);
567 : : bool apply_ctor_pair_to_child_region (const region *parent_reg,
568 : : region_model_manager *mgr,
569 : : tree index, tree val);
570 : :
571 : : map_t m_map;
572 : : };
573 : :
574 : : /* Concept: BindingVisitor, for use by binding_cluster::for_each_binding
575 : : and store::for_each_binding.
576 : :
577 : : Should implement:
578 : : void on_binding (const binding_key *key, const svalue *&sval);
579 : : */
580 : :
581 : : /* All of the bindings within a store for regions that share the same
582 : : base region. */
583 : :
584 : 30176460 : class binding_cluster
585 : : {
586 : : public:
587 : : friend class store;
588 : :
589 : : typedef hash_map <const binding_key *, const svalue *> map_t;
590 : : typedef map_t::iterator iterator_t;
591 : :
592 : : binding_cluster (const region *base_region);
593 : : binding_cluster (const binding_cluster &other);
594 : : binding_cluster& operator=(const binding_cluster &other);
595 : :
596 : : bool operator== (const binding_cluster &other) const;
597 : 2338695 : bool operator!= (const binding_cluster &other) const
598 : : {
599 : 2338695 : return !(*this == other);
600 : : }
601 : :
602 : : hashval_t hash () const;
603 : :
604 : : bool symbolic_p () const;
605 : :
606 : 109527 : const region *get_base_region () const { return m_base_region; }
607 : :
608 : : void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
609 : : void dump (bool simple) const;
610 : :
611 : : void validate () const;
612 : :
613 : : json::object *to_json () const;
614 : :
615 : : void bind (store_manager *mgr, const region *, const svalue *);
616 : :
617 : : void clobber_region (store_manager *mgr, const region *reg);
618 : : void purge_region (store_manager *mgr, const region *reg);
619 : : void fill_region (store_manager *mgr, const region *reg, const svalue *sval);
620 : : void zero_fill_region (store_manager *mgr, const region *reg);
621 : : void mark_region_as_unknown (store_manager *mgr,
622 : : const region *reg_to_bind,
623 : : const region *reg_for_overlap,
624 : : uncertainty_t *uncertainty,
625 : : svalue_set *maybe_live_values);
626 : : void purge_state_involving (const svalue *sval,
627 : : region_model_manager *sval_mgr);
628 : :
629 : : const svalue *get_binding (store_manager *mgr, const region *reg) const;
630 : : const svalue *get_binding_recursive (store_manager *mgr,
631 : : const region *reg) const;
632 : : const svalue *get_any_binding (store_manager *mgr,
633 : : const region *reg) const;
634 : : const svalue *maybe_get_compound_binding (store_manager *mgr,
635 : : const region *reg) const;
636 : :
637 : : void remove_overlapping_bindings (store_manager *mgr, const region *reg,
638 : : uncertainty_t *uncertainty,
639 : : svalue_set *maybe_live_values);
640 : :
641 : : template <typename T>
642 : 8990493 : void for_each_value (void (*cb) (const svalue *sval, T user_data),
643 : : T user_data) const
644 : : {
645 : 28450457 : for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
646 : 9729982 : cb ((*iter).second, user_data);
647 : 8990493 : }
648 : :
649 : : static bool can_merge_p (const binding_cluster *cluster_a,
650 : : const binding_cluster *cluster_b,
651 : : binding_cluster *out_cluster,
652 : : store *out_store,
653 : : store_manager *mgr,
654 : : model_merger *merger);
655 : : void make_unknown_relative_to (const binding_cluster *other_cluster,
656 : : store *out_store,
657 : : store_manager *mgr);
658 : :
659 : : void mark_as_escaped ();
660 : : void on_unknown_fncall (const gcall *call, store_manager *mgr,
661 : : const conjured_purge &p);
662 : : void on_asm (const gasm *stmt, store_manager *mgr,
663 : : const conjured_purge &p);
664 : :
665 : : bool escaped_p () const;
666 : 333088 : bool touched_p () const { return m_touched; }
667 : :
668 : : bool redundant_p () const;
669 : 277077 : bool empty_p () const { return m_map.elements () == 0; }
670 : :
671 : : void get_representative_path_vars (const region_model *model,
672 : : svalue_set *visited,
673 : : const region *base_reg,
674 : : const svalue *sval,
675 : : auto_vec<path_var> *out_pvs) const;
676 : :
677 : : const svalue *maybe_get_simple_value (store_manager *mgr) const;
678 : :
679 : : template <typename BindingVisitor>
680 : 128569 : void for_each_binding (BindingVisitor &v) const
681 : : {
682 : 262802 : for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
683 : : {
684 : 134233 : const binding_key *key = (*iter).first;
685 : 134233 : const svalue *&sval = (*iter).second;
686 : 134233 : v.on_binding (key, sval);
687 : : }
688 : 128569 : }
689 : :
690 : 9479 : iterator_t begin () const { return m_map.begin (); }
691 : 9479 : iterator_t end () const { return m_map.end (); }
692 : :
693 : 303 : const binding_map &get_map () const { return m_map; }
694 : :
695 : : private:
696 : : const svalue *get_any_value (const binding_key *key) const;
697 : : void bind_compound_sval (store_manager *mgr,
698 : : const region *reg,
699 : : const compound_svalue *compound_sval);
700 : : void bind_key (const binding_key *key, const svalue *sval);
701 : :
702 : : const region *m_base_region;
703 : :
704 : : binding_map m_map;
705 : :
706 : : /* Has a pointer to this cluster "escaped" into a part of the program
707 : : we don't know about (via a call to a function with an unknown body,
708 : : or by being passed in as a pointer param of a "top-level" function call).
709 : : Such regions could be overwritten when other such functions are called,
710 : : even if the region is no longer reachable by pointers that we are
711 : : tracking. */
712 : : bool m_escaped;
713 : :
714 : : /* Has this cluster been written to via a symbolic binding?
715 : : If so, then we don't know anything about unbound subregions,
716 : : so we can't use initial_svalue, treat them as uninitialized, or
717 : : inherit values from a parent region. */
718 : : bool m_touched;
719 : : };
720 : :
721 : : /* The mapping from regions to svalues.
722 : : This is actually expressed by subdividing into clusters, to better
723 : : handle aliasing. */
724 : :
725 : : class store
726 : : {
727 : : public:
728 : : typedef hash_map <const region *, binding_cluster *> cluster_map_t;
729 : :
730 : : store ();
731 : : store (const store &other);
732 : : ~store ();
733 : :
734 : : store &operator= (const store &other);
735 : :
736 : : bool operator== (const store &other) const;
737 : 515346 : bool operator!= (const store &other) const
738 : : {
739 : 515346 : return !(*this == other);
740 : : }
741 : :
742 : : hashval_t hash () const;
743 : :
744 : : void dump_to_pp (pretty_printer *pp, bool summarize, bool multiline,
745 : : store_manager *mgr) const;
746 : : void dump (bool simple) const;
747 : : void summarize_to_pp (pretty_printer *pp, bool simple) const;
748 : :
749 : : void validate () const;
750 : :
751 : : json::object *to_json () const;
752 : :
753 : : const svalue *get_any_binding (store_manager *mgr, const region *reg) const;
754 : :
755 : 365050 : bool called_unknown_fn_p () const { return m_called_unknown_fn; }
756 : :
757 : : void set_value (store_manager *mgr, const region *lhs_reg,
758 : : const svalue *rhs_sval,
759 : : uncertainty_t *uncertainty);
760 : : void clobber_region (store_manager *mgr, const region *reg);
761 : : void purge_region (store_manager *mgr, const region *reg);
762 : : void fill_region (store_manager *mgr, const region *reg, const svalue *sval);
763 : : void zero_fill_region (store_manager *mgr, const region *reg);
764 : : void mark_region_as_unknown (store_manager *mgr, const region *reg,
765 : : uncertainty_t *uncertainty,
766 : : svalue_set *maybe_live_values);
767 : : void purge_state_involving (const svalue *sval,
768 : : region_model_manager *sval_mgr);
769 : :
770 : : const binding_cluster *get_cluster (const region *base_reg) const;
771 : : binding_cluster *get_cluster (const region *base_reg);
772 : : binding_cluster *get_or_create_cluster (const region *base_reg);
773 : : void purge_cluster (const region *base_reg);
774 : :
775 : : template <typename T>
776 : 2132506 : void for_each_cluster (void (*cb) (const region *base_reg, T user_data),
777 : : T user_data) const
778 : : {
779 : 15682958 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
780 : 29233410 : iter != m_cluster_map.end (); ++iter)
781 : 13550452 : cb ((*iter).first, user_data);
782 : 2132506 : }
783 : :
784 : : static bool can_merge_p (const store *store_a, const store *store_b,
785 : : store *out_store, store_manager *mgr,
786 : : model_merger *merger);
787 : :
788 : : void mark_as_escaped (const region *base_reg);
789 : : void on_unknown_fncall (const gcall *call, store_manager *mgr,
790 : : const conjured_purge &p);
791 : : bool escaped_p (const region *reg) const;
792 : :
793 : : void get_representative_path_vars (const region_model *model,
794 : : svalue_set *visited,
795 : : const svalue *sval,
796 : : auto_vec<path_var> *out_pvs) const;
797 : :
798 : 1445267 : cluster_map_t::iterator begin () const { return m_cluster_map.begin (); }
799 : 10767750 : cluster_map_t::iterator end () const { return m_cluster_map.end (); }
800 : :
801 : : tristate eval_alias (const region *base_reg_a,
802 : : const region *base_reg_b) const;
803 : :
804 : : template <typename BindingVisitor>
805 : 34923 : void for_each_binding (BindingVisitor &v)
806 : : {
807 : 163492 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
808 : 163492 : iter != m_cluster_map.end (); ++iter)
809 : 128569 : (*iter).second->for_each_binding (v);
810 : 34923 : }
811 : :
812 : : void canonicalize (store_manager *mgr);
813 : : void loop_replay_fixup (const store *other_store,
814 : : region_model_manager *mgr);
815 : :
816 : : void replay_call_summary (call_summary_replay &r,
817 : : const store &summary);
818 : : void replay_call_summary_cluster (call_summary_replay &r,
819 : : const store &summary,
820 : : const region *base_reg);
821 : : void on_maybe_live_values (const svalue_set &maybe_live_values);
822 : :
823 : : private:
824 : : void remove_overlapping_bindings (store_manager *mgr, const region *reg,
825 : : uncertainty_t *uncertainty);
826 : : tristate eval_alias_1 (const region *base_reg_a,
827 : : const region *base_reg_b) const;
828 : :
829 : : cluster_map_t m_cluster_map;
830 : :
831 : : /* If this is true, then unknown code has been called, and so
832 : : any global variable that isn't currently modelled by the store
833 : : has unknown state, rather than being in an "initial state".
834 : : This is to avoid having to mark (and thus explicitly track)
835 : : every global when an unknown function is called; instead, they
836 : : can be tracked implicitly. */
837 : : bool m_called_unknown_fn;
838 : : };
839 : :
840 : : /* A class responsible for owning and consolidating binding keys
841 : : (both concrete and symbolic).
842 : : Key instances are immutable as far as clients are concerned, so they
843 : : are provided as "const" ptrs. */
844 : :
845 : 4359 : class store_manager
846 : : {
847 : : public:
848 : 4359 : store_manager (region_model_manager *mgr) : m_mgr (mgr) {}
849 : :
850 : : logger *get_logger () const;
851 : :
852 : : /* binding consolidation. */
853 : : const concrete_binding *
854 : : get_concrete_binding (bit_offset_t start_bit_offset,
855 : : bit_offset_t size_in_bits);
856 : : const concrete_binding *
857 : 32228 : get_concrete_binding (const bit_range &bits)
858 : : {
859 : 32228 : return get_concrete_binding (bits.get_start_bit_offset (),
860 : 32228 : bits.m_size_in_bits);
861 : : }
862 : : const concrete_binding *
863 : 8 : get_concrete_binding (const byte_range &bytes)
864 : : {
865 : 8 : bit_range bits = bytes.as_bit_range ();
866 : 8 : return get_concrete_binding (bits);
867 : : }
868 : : const symbolic_binding *
869 : : get_symbolic_binding (const region *region);
870 : :
871 : 6542206 : region_model_manager *get_svalue_manager () const
872 : : {
873 : 6542206 : return m_mgr;
874 : : }
875 : :
876 : : void log_stats (logger *logger, bool show_objs) const;
877 : :
878 : : private:
879 : : region_model_manager *m_mgr;
880 : : consolidation_map<concrete_binding> m_concrete_binding_key_mgr;
881 : : consolidation_map<symbolic_binding> m_symbolic_binding_key_mgr;
882 : : };
883 : :
884 : : } // namespace ana
885 : :
886 : : #endif /* GCC_ANALYZER_STORE_H */
|
