GCC Middle and Back End API Reference
store.h
Go to the documentation of this file.
1/* Classes for modeling the state of memory.
2 Copyright (C) 2020-2026 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it
8under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
25#include "analyzer/complexity.h"
30
31/* Implementation of the region-based ternary model described in:
32 "A Memory Model for Static Analysis of C Programs"
33 (Zhongxing Xu, Ted Kremenek, and Jian Zhang)
34 http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf */
35
36/* Binding clusters
37 ================
38
39 The store models memory as a collection of "clusters", where regions
40 are partitioned into clusters via their base region.
41
42 For example, given:
43 int a, b, c;
44 struct coord { double x; double y; } verts[3];
45 then "verts[0].y" and "verts[1].x" both have "verts" as their base region.
46 Each of a, b, c, and verts will have their own clusters, so that we
47 know that writes to e.g. "verts[1].x".don't affect e.g. "a".
48
49 For each cluster that's been touched by the user's code we track an
50 immutable bit_contents instance, updating it to point to a different
51 bit_contents instance after each change.
52
53 Handling symbolic regions requires us to handle aliasing.
54
55 In the example above, each of a, b, c and verts are non-symbolic
56 base regions and so their clusters are "concrete clusters", whereas given:
57 struct coord *p, *q;
58 then "*p" and "*q" are symbolic base regions, and thus "*p" and "*q"
59 have "symbolic clusters".
60
61 In the above, "verts[i].x" will have a symbolic *binding* within a
62 concrete cluster for "verts", whereas "*p" is a symbolic *cluster*.
63
64 Writes to concrete clusters can't affect other concrete clusters,
65 but can affect symbolic clusters; e.g. after:
66 verts[0].x = 42;
67 we bind 42 in the cluster for "verts", but the clusters for "b" and "c"
68 can't be affected. Any symbolic clusters for *p and for *q can be
69 affected, *p and *q could alias "verts".
70
71 Writes to a symbolic cluster can affect other clusters, both
72 concrete and symbolic; e.g. after:
73 p->x = 17;
74 we bind 17 within the cluster for "*p". The concrete clusters for a, b,
75 c, and verts could be affected, depending on whether *p aliases them.
76 Similarly, the symbolic cluster to *q could be affected.
77
78
79 Tracking the state within a binding cluster
80 ===========================================
81
82 Reads and writes to memory are handled as reading and writing bits to
83 a cluster, where the memory ranges relative to the start of the cluster
84 can be either fully concrete, or be symbolic (with a symbolic start offset
85 and/or size).
86
87 Consider this example (taken from
88 gcc/testsuite/c-c++-common/analyzer/symbolic-1.c, adding calls to
89 __analyzer_dump (); at the pertinent places):
90
91 char arr[1024];
92 arr[2] = a; (1)
93 arr[3] = b; (2)
94 After (1) and (2), we have this state:
95 | program_state
96 | ╰─ Region Model
97 | ├─ Current Frame: frame: ‘test_1’@1
98 | ╰─ Store
99 | ├─ m_called_unknown_fn: false
100 | ╰─ frame: ‘test_1’@1
101 | ╰─ arr:
102 | ╰─ (616): concrete bit overlay
103 | ├─ concrete ranges
104 | │ ├─ [byte 2]: (605): bit_vector_from_svalue[size: 1 byte]
105 | │ │ ╰─ m_sval: (604): ‘char’: initial_svalue
106 | │ │ ├─ value_range: {[irange] char VARYING}
107 | │ │ ╰─ m_reg: (601): ‘char’: decl_region(‘a_48(D)’)
108 | │ │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
109 | │ │ ╰─ parent: (1): stack region
110 | │ │ ╰─ parent: (0): root region
111 | │ ╰─ [byte 3]: (613): bit_vector_from_svalue[size: 1 byte]
112 | │ ╰─ m_sval: (612): ‘char’: initial_svalue
113 | │ ├─ value_range: {[irange] char VARYING}
114 | │ ╰─ m_reg: (611): ‘char’: decl_region(‘b_50(D)’)
115 | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
116 | │ ╰─ {as above; descendents: 3, depth: 3}
117 | ╰─ baseline: (7): uninitialized contents
118 The cluster for "arr" has a concrete_bit_overlay for its contents,
119 with bytes 2 and 3 bound to bit_vectors for the target encoding
120 of svalues for the initial values of "a" and "b" respectively. This
121 is overlaid on top of the baseline "uninitialized" everywhere else, so
122 that attempting to query e.g. arr[4] will return "uninitialized".
123
124 "a" and "b" are each in their own clusters, with no explicit
125 bindings, and thus have their "implicit contents": in this case
126 concrete_bit_overlay instances bound at [0..sizeof(int)) to the bit
127 vectors for the initial_svalue of "a" and "b" respectively.
128
129 arr[3] = c; (3)
130 After (3), the contents of the cluster for "arr" has been replaced by
131 a new concrete_bit_overlay instance, the same as the previous one,
132 but with byte 3 now bound to a bit vector for the
133 initial_svalue for "c":
134 | program_state
135 | ╰─ Region Model
136 | ├─ Current Frame: frame: ‘test_1’@1
137 | ╰─ Store
138 | ├─ m_called_unknown_fn: false
139 | ╰─ frame: ‘test_1’@1
140 | ╰─ arr:
141 | ╰─ (648): concrete bit overlay
142 | ├─ concrete ranges
143 | │ ├─ [byte 2]: (605): bit_vector_from_svalue[size: 1 byte]
144 | │ │ ╰─ m_sval: (604): ‘char’: initial_svalue
145 | │ │ ├─ value_range: {[irange] char VARYING}
146 | │ │ ╰─ m_reg: (601): ‘char’: decl_region(‘a_48(D)’)
147 | │ │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
148 | │ │ ╰─ parent: (1): stack region
149 | │ │ ╰─ parent: (0): root region
150 | │ ╰─ [byte 3]: (645): bit_vector_from_svalue[size: 1 byte]
151 | │ ╰─ m_sval: (644): ‘char’: initial_svalue
152 | │ ├─ value_range: {[irange] char VARYING}
153 | │ ╰─ m_reg: (643): ‘char’: decl_region(‘c_55(D)’)
154 | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
155 | │ ╰─ {as above; descendents: 3, depth: 3}
156 | ╰─ baseline: (7): uninitialized contents
157 Note that the concrete_bit_overlay (and other bit_contents instances)
158 are immutable and pure-functional - when a cluster is written to, we
159 update the cluster's m_contents to point to a different bit_contents.
160
161 arr[i] = d; (4)
162 After the write to the symbolic array index at (4), the cluster for
163 "arr" no longer uses the concrete_bit_overlay and instead points to
164 a symbolic_bit_overlay, where the bytes at element [i] are bound to
165 the bit_vector fot the initial value of "d":
166 | program_state
167 | ╰─ Region Model
168 | ├─ Current Frame: frame: ‘test_1’@1
169 | ╰─ Store
170 | ├─ m_called_unknown_fn: false
171 | ╰─ frame: ‘test_1’@1
172 | ╰─ arr:
173 | ╰─ (670): symbolic bit overlay
174 | ├─ symbolic ranges
175 | │ ├─ symbolic range
176 | │ │ ├─ start offset: (571): bits_from_bytes_scalar
177 | │ │ │ ╰─ (570): scalar_from_svalue<bytes>
178 | │ │ │ ╰─ (565): ‘int’: initial_svalue
179 | │ │ │ ├─ value_range: {[irange] int VARYING}
180 | │ │ │ ╰─ m_reg: (564): ‘int’: decl_region(‘i_61(D)’)
181 | │ │ │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
182 | │ │ │ ╰─ parent: (1): stack region
183 | │ │ │ ╰─ parent: (0): root region
184 | │ │ ╰─ size: (11): concrete_scalar<bits>: 8
185 | │ ╰─ (657): bit_vector_from_svalue[size: 1 byte]
186 | │ ╰─ m_sval: (656): ‘char’: initial_svalue
187 | │ ├─ value_range: {[irange] char VARYING}
188 | │ ╰─ m_reg: (655): ‘char’: decl_region(‘d_62(D)’)
189 | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
190 | │ ╰─ {as above; descendents: 3, depth: 3}
191 | ╰─ baseline: (669): untracked_bit_contents
192 | ╰─ maybe live values
193 | ├─ (605): bit_vector_from_svalue[size: 1 byte]
194 | │ ╰─ m_sval: (604): ‘char’: initial_svalue
195 | │ ├─ value_range: {[irange] char VARYING}
196 | │ ╰─ m_reg: (601): ‘char’: decl_region(‘a_48(D)’)
197 | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
198 | │ ╰─ {as above; descendents: 3, depth: 3}
199 | ╰─ (645): bit_vector_from_svalue[size: 1 byte]
200 | ╰─ m_sval: (644): ‘char’: initial_svalue
201 | ├─ value_range: {[irange] char VARYING}
202 | ╰─ m_reg: (643): ‘char’: decl_region(‘c_55(D)’)
203 | ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
204 | ╰─ {as above; descendents: 3, depth: 3}
205 We also set the baseline for this overlay to an untracked_bit_contents
206 instance. This indicates that we've given up on tracking the contents
207 of "arr" at other locations (reads will return "unknown", rather than
208 "uninitialized"). The untracked_bit_contents has a set of values that
209 are "maybe live", capturing that the initial values of "a" and "c" may
210 still be live within "arr" (to avoid leak false +ves), since we don't
211 know if i == 3 or 4.
212
213 Note how the IDs of the "maybe live values" nodes below match those
214 within the concrete_bit_overlay above: the symbolic::node instances
215 persist through the analysis.
216
217 arr[j] = e; (5)
218 After (5), the user's code has written to a possibly-different
219 symbolic index within "arr", so we have a new symbolic_bit_overlay,
220 binding the byte at [j] to the bit vector for the initial value of "e",
221 and the "maybe live values" has gained the value that was at [i], since
222 we don't know whether j == i (or j == 3, or j == 4):
223 | program_state
224 | ╰─ Region Model
225 | ├─ Current Frame: frame: ‘test_1’@1
226 | ╰─ Store
227 | ├─ m_called_unknown_fn: false
228 | ╰─ frame: ‘test_1’@1
229 | ╰─ arr:
230 | ╰─ (685): symbolic bit overlay
231 | ├─ symbolic ranges
232 | │ ├─ symbolic range
233 | │ │ ├─ start offset: (590): bits_from_bytes_scalar
234 | │ │ │ ╰─ (589): scalar_from_svalue<bytes>
235 | │ │ │ ╰─ (584): ‘int’: initial_svalue
236 | │ │ │ ├─ value_range: {[irange] int VARYING}
237 | │ │ │ ╰─ m_reg: (583): ‘int’: decl_region(‘j_68(D)’)
238 | │ │ │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
239 | │ │ │ ╰─ parent: (1): stack region
240 | │ │ │ ╰─ parent: (0): root region
241 | │ │ ╰─ size: (11): concrete_scalar<bits>: 8
242 | │ ╰─ (676): bit_vector_from_svalue[size: 1 byte]
243 | │ ╰─ m_sval: (675): ‘char’: initial_svalue
244 | │ ├─ value_range: {[irange] char VARYING}
245 | │ ╰─ m_reg: (674): ‘char’: decl_region(‘e_69(D)’)
246 | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
247 | │ ╰─ {as above; descendents: 3, depth: 3}
248 | ╰─ baseline: (684): untracked_bit_contents
249 | ╰─ maybe live values
250 | ├─ (605): bit_vector_from_svalue[size: 1 byte]
251 | │ ╰─ m_sval: (604): ‘char’: initial_svalue
252 | │ ├─ value_range: {[irange] char VARYING}
253 | │ ╰─ m_reg: (601): ‘char’: decl_region(‘a_48(D)’)
254 | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
255 | │ ╰─ {as above; descendents: 3, depth: 3}
256 | ├─ (645): bit_vector_from_svalue[size: 1 byte]
257 | │ ╰─ m_sval: (644): ‘char’: initial_svalue
258 | │ ├─ value_range: {[irange] char VARYING}
259 | │ ╰─ m_reg: (643): ‘char’: decl_region(‘c_55(D)’)
260 | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
261 | │ ╰─ {as above; descendents: 3, depth: 3}
262 | ╰─ (657): bit_vector_from_svalue[size: 1 byte]
263 | ╰─ m_sval: (656): ‘char’: initial_svalue
264 | ├─ value_range: {[irange] char VARYING}
265 | ╰─ m_reg: (655): ‘char’: decl_region(‘d_62(D)’)
266 | ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
267 | ╰─ {as above; descendents: 3, depth: 3}
268
269 arr[3] = f; (6)
270 After (6), we have a concrete_bit_overlay again, this, with a binding
271 at byte [3], where the baseline is an untracked_bit_contents, with all
272 the various other values we're written into "arr" as "maybe live":
273 | program_state
274 | ╰─ Region Model
275 | ├─ Current Frame: frame: ‘test_1’@1
276 | ╰─ Store
277 | ├─ m_called_unknown_fn: false
278 | ╰─ frame: ‘test_1’@1
279 | ╰─ arr:
280 | ╰─ (691): concrete bit overlay
281 | ├─ concrete ranges
282 | │ ╰─ [byte 3]: (688): bit_vector_from_svalue[size: 1 byte]
283 | │ ╰─ m_sval: (687): ‘char’: initial_svalue
284 | │ ├─ value_range: {[irange] char VARYING}
285 | │ ╰─ m_reg: (686): ‘char’: decl_region(‘f_74(D)’)
286 | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
287 | │ ╰─ parent: (1): stack region
288 | │ ╰─ parent: (0): root region
289 | ╰─ baseline: (690): untracked_bit_contents
290 | ╰─ maybe live values
291 | ├─ (605): bit_vector_from_svalue[size: 1 byte]
292 | │ ╰─ m_sval: (604): ‘char’: initial_svalue
293 | │ ├─ value_range: {[irange] char VARYING}
294 | │ ╰─ m_reg: (601): ‘char’: decl_region(‘a_48(D)’)
295 | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
296 | │ ╰─ {as above; descendents: 3, depth: 3}
297 | ├─ (645): bit_vector_from_svalue[size: 1 byte]
298 | │ ╰─ m_sval: (644): ‘char’: initial_svalue
299 | │ ├─ value_range: {[irange] char VARYING}
300 | │ ╰─ m_reg: (643): ‘char’: decl_region(‘c_55(D)’)
301 | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
302 | │ ╰─ {as above; descendents: 3, depth: 3}
303 | ├─ (657): bit_vector_from_svalue[size: 1 byte]
304 | │ ╰─ m_sval: (656): ‘char’: initial_svalue
305 | │ ├─ value_range: {[irange] char VARYING}
306 | │ ╰─ m_reg: (655): ‘char’: decl_region(‘d_62(D)’)
307 | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
308 | │ ╰─ {as above; descendents: 3, depth: 3}
309 | ╰─ (676): bit_vector_from_svalue[size: 1 byte]
310 | ╰─ m_sval: (675): ‘char’: initial_svalue
311 | ├─ value_range: {[irange] char VARYING}
312 | ╰─ m_reg: (674): ‘char’: decl_region(‘e_69(D)’)
313 | ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
314 | ╰─ {as above; descendents: 3, depth: 3}
315*/
316
317
318namespace ana {
319
320/* A class for keeping track of aspects of a program_state that we don't
321 know about, to avoid false positives about leaks.
322
323 Consider:
324
325 p->field = malloc (1024);
326 q->field = NULL;
327
328 where we don't know whether or not p and q point to the same memory,
329 and:
330
331 p->field = malloc (1024);
332 unknown_fn (p);
333
334 In both cases, the svalue for the address of the allocated buffer
335 goes from being bound to p->field to not having anything explicitly bound
336 to it.
337
338 Given that we conservatively discard bindings due to possible aliasing or
339 calls to unknown function, the store loses references to svalues,
340 but these svalues could still be live. We don't want to warn about
341 them leaking - they're effectively in a "maybe live" state.
342
343 This "maybe live" information is somewhat transient.
344
345 We don't want to store this "maybe live" information in the program_state,
346 region_model, or store, since we don't want to bloat these objects (and
347 potentially bloat the exploded_graph with more nodes).
348 However, we can't store it in the region_model_context, as these context
349 objects sometimes don't last long enough to be around when comparing the
350 old vs the new state.
351
352 This class is a way to track a set of such svalues, so that we can
353 temporarily capture that they are in a "maybe live" state whilst
354 comparing old and new states. */
355
357{
358public:
360
363
364 bool unknown_sm_state_p (const svalue *sval);
365
367
368 void dump () const;
369 void dump_to_logger (logger &) const;
370
371 std::unique_ptr<text_art::tree_widget>
373
375 {
376 return m_maybe_bound_vals.begin ();
377 }
379 {
380 return m_maybe_bound_vals.end ();
381 }
382
383private:
384
385 /* Values that might or might not still be bound. */
387
388 /* Values that have mutable sm-state at unknown calls. */
390};
391
392class byte_range;
393
394// TODO: eliminate this in favor of concrete_bit_range:
395/* A concrete range of bits. */
396
398{
399 bit_range (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
400 : m_start_bit_offset (start_bit_offset),
401 m_size_in_bits (size_in_bits)
402 {}
403
404 void dump_to_pp (pretty_printer *pp) const;
405 void dump () const;
406
407 std::unique_ptr<json::object> to_json () const;
408
409 bool empty_p () const
410 {
411 return m_size_in_bits == 0;
412 }
413
415 {
416 return m_start_bit_offset;
417 }
423 {
424 gcc_assert (!empty_p ());
425 return get_next_bit_offset () - 1;
426 }
427
428 bool contains_p (bit_offset_t offset) const
429 {
430 return (offset >= get_start_bit_offset ()
431 && offset < get_next_bit_offset ());
432 }
433
434 bool contains_p (const bit_range &other, bit_range *out) const;
435
436 bool operator== (const bit_range &other) const
437 {
438 return (m_start_bit_offset == other.m_start_bit_offset
439 && m_size_in_bits == other.m_size_in_bits);
440 }
441
442 bool intersects_p (const bit_range &other) const
443 {
444 return (get_start_bit_offset () < other.get_next_bit_offset ()
445 && other.get_start_bit_offset () < get_next_bit_offset ());
446 }
447 bool intersects_p (const bit_range &other,
448 bit_size_t *out_num_overlap_bits) const;
449 bool intersects_p (const bit_range &other,
450 bit_range *out_this,
451 bit_range *out_other) const;
452
453 bool exceeds_p (const bit_range &other,
454 bit_range *out_overhanging_bit_range) const;
455
457 bit_range *out_fall_short_bits) const;
458
459 static int cmp (const bit_range &br1, const bit_range &br2);
460
462
463 bool as_byte_range (byte_range *out) const;
464
465 bool
466 operator< (const bit_range &other) const
467 {
468 if (m_start_bit_offset < other.m_start_bit_offset)
469 return true;
470 if (m_start_bit_offset > other.m_start_bit_offset)
471 return false;
472 return (m_size_in_bits < other.m_size_in_bits);
473 }
474
475 hashval_t hash () const
476 {
477 inchash::hash hstate;
480 return hstate.end ();
481 }
482
485};
486
494
495inline bit_range
497{
498 return bit_range
499 (convert_to_bit_offset_t (new_bits.get_start_offset ()),
500 convert_to_bit_size_t (new_bits.get_size ()));
501}
502
503// TODO: eliminate this in favor of concrete_byte_range:
504/* A concrete range of bytes. */
505
507{
509 : m_start_byte_offset (start_byte_offset),
511 {}
512
513 void dump_to_pp (pretty_printer *pp) const;
514 void dump () const;
515
516 std::unique_ptr<json::object> to_json () const;
517
518 bool empty_p () const
519 {
520 return m_size_in_bytes == 0;
521 }
522
523 bool contains_p (byte_offset_t offset) const
524 {
525 return (offset >= get_start_byte_offset ()
526 && offset < get_next_byte_offset ());
527 }
528 bool contains_p (const byte_range &other, byte_range *out) const;
529
530 bool operator== (const byte_range &other) const
531 {
532 return (m_start_byte_offset == other.m_start_byte_offset
533 && m_size_in_bytes == other.m_size_in_bytes);
534 }
535
549
551 {
552 return bit_range (m_start_byte_offset * BITS_PER_UNIT,
553 m_size_in_bytes * BITS_PER_UNIT);
554 }
555
557 {
558 return m_start_byte_offset * BITS_PER_UNIT;
559 }
561 {
562 return get_next_byte_offset () * BITS_PER_UNIT;
563 }
565 {
566 return m_size_in_bytes * BITS_PER_UNIT;
567 }
568
569 static int cmp (const byte_range &br1, const byte_range &br2);
570
573};
574
575/* All of the bindings within a store for regions that share the same
576 base region.
577
578 Invariants:
579 - the region must be a base region
580 - region->tracked_p () must be true
581 - region->symbolic_for_unknown_ptr_p () must be false (we must not be
582 dereferencing an UNKNOWN ptr). */
583
585{
586public:
587 friend class store;
588
590 const region *base_region,
591 const symbolic::bit_contents &contents);
594
595 bool operator== (const binding_cluster &other) const;
596 bool operator!= (const binding_cluster &other) const
597 {
598 return !(*this == other);
599 }
600
601 hashval_t hash () const;
602
603 bool symbolic_p () const;
604
605 const region *get_base_region () const { return m_base_region; }
606
607 void dump () const;
608
609 void validate () const;
610
611 std::unique_ptr<json::object> to_json () const;
612
613 std::unique_ptr<text_art::tree_widget>
615
618
619 void
621 const symbolic::bit_vector &bits,
622 uncertainty_t *uncertainty);
623
625 get_bit_contents () const { return *m_contents; }
626
627 void
629 {
630 m_contents = &bc;
631 }
632
634 uncertainty_t *uncertainty,
635 value_set *maybe_live_values);
637
640 void *user_data),
641 void *user_data) const;
642
643 static bool can_merge_p (const binding_cluster *cluster_a,
644 const binding_cluster *cluster_b,
645 binding_cluster *out_cluster,
646 store *out_store,
647 model_merger *merger);
648 void make_unknown_relative_to (const binding_cluster *other_cluster,
649 store *out_store,
650 baseline_state bs);
651
653 void on_unknown_fncall (const gcall &call,
654 const conjured_purge &p);
655 void
657 const conjured_purge &p);
658
659 void on_asm (const gasm *stmt,
660 const conjured_purge &p);
661
662 bool escaped_p () const;
663 bool touched_p () const { return m_touched; }
664
665 bool redundant_p (const store &store_,
666 baseline_state bs) const;
667
669 value_set *visited,
670 const region *base_reg,
671 const svalue *sval,
672 logger *logger,
673 auto_vec<path_var> *out_pvs) const;
674
675 void
677 enum poison_kind pkind);
678
679 bool
680 bits_live_p (const symbolic::bit_vector_from_ubc &bv_from_ubc) const;
681
682private:
684
686
688
689 /* Has a pointer to this cluster "escaped" into a part of the program
690 we don't know about (via a call to a function with an unknown body,
691 or by being passed in as a pointer param of a "top-level" function call).
692 Such regions could be overwritten when other such functions are called,
693 even if the region is no longer reachable by pointers that we are
694 tracking. */
696
697 /* Has this cluster been written to via a symbolic binding?
698 If so, then we don't know anything about unbound subregions,
699 so we can't use initial_svalue, treat them as uninitialized, or
700 inherit values from a parent region. */
702};
703
704/* The mapping from regions to svalues.
705 This is actually expressed by subdividing into clusters, to better
706 handle aliasing. */
707
708class store
709{
710public:
711 typedef hash_map <const region *, binding_cluster *> cluster_map_t;
712
714 store (const store &other);
716
717 store &operator= (const store &other);
718
719 bool operator== (const store &other) const;
720 bool operator!= (const store &other) const
721 {
722 return !(*this == other);
723 }
724
725 hashval_t hash () const;
726
727 void dump () const;
728 void summarize_to_pp (pretty_printer *pp, bool simple) const;
729
730 void validate () const;
731
732 std::unique_ptr<json::object> to_json () const;
733
734 std::unique_ptr<text_art::tree_widget>
736
739 baseline_state bs) const;
740
742 get_bit_contents (const region &base_reg,
743 baseline_state bs) const;
744
745 bool called_unknown_fn_p () const { return m_called_unknown_fn; }
746
747 void
748 set_bits (const region *lhs_reg,
749 const symbolic::bit_vector &bv,
750 uncertainty_t *uncertainty,
751 const region_model &model);
752
753 void
755 const symbolic::bit_vector &bv,
756 uncertainty_t *uncertainty,
757 const region_model &model);
758
759 void
760 set_bit_contents_raw (const region &base_reg,
761 const symbolic::bit_contents &bc,
762 const region_model &model);
763
764 void clobber_region (const region *reg,
767 void purge_region (const region *reg);
770 uncertainty_t *uncertainty,
771 const region_model &model);
773
774 const binding_cluster *get_cluster (const region *base_reg) const;
778 baseline_state bs);
779 void purge_cluster (const region *base_reg);
780
781 template <typename T>
782 void for_each_cluster (void (*cb) (const region *base_reg, T user_data),
783 T user_data) const
784 {
785 for (cluster_map_t::iterator iter = m_cluster_map.begin ();
786 iter != m_cluster_map.end (); ++iter)
787 cb ((*iter).first, user_data);
788 }
789
790 static bool can_merge_p (const store *store_a, const store *store_b,
791 store *out_store,
792 model_merger *merger);
793
794 void mark_as_escaped (const region *base_reg,
795 baseline_state bs);
796 void on_unknown_fncall (const gcall &call,
797 const conjured_purge &p);
798 void
801 const gimple &stmt,
802 const conjured_purge &p);
803
804 bool escaped_p (const region *reg) const;
805
807 value_set *visited,
808 const svalue *sval,
809 logger *logger,
810 auto_vec<path_var> *out_pvs) const;
811
812 cluster_map_t::iterator begin () const { return m_cluster_map.begin (); }
813 cluster_map_t::iterator end () const { return m_cluster_map.end (); }
814
815 tristate eval_alias (const region *base_reg_a,
816 const region *base_reg_b,
817 const region_model &model) const;
818
820 void loop_replay_fixup (const store *other_store,
823
825 const store &summary);
827 const store &summary,
828 const region *base_reg);
829 bool
831 const store &summary,
832 const region &summary_base_reg,
833 const region &caller_dest_reg,
834 const symbolic::bit_contents &caller_bc);
835
836 void on_maybe_live_values (const value_set &maybe_live_values,
837 baseline_state bs);
838
839 bool
841 const region_model &model) const;
842
845 baseline_state bs) const;
846
847private:
850 baseline_state bs) const;
851
852 tristate eval_alias_1 (const region *base_reg_a,
853 const region *base_reg_b,
854 const region_model &model) const;
855
857
859
860 /* If this is true, then unknown code has been called since the beginning
861 of some path reaching this point in the analysis. All externally
862 visible non-readonly global variables that aren't currently modelled by
863 the store are affected by this flag: they are implicitly either all in their
864 "initial state" (m_called_unknown_fn==false), or all in unknown state
865 (m_called_unknown_fn==true).
866
867 This is to avoid having to mark (and thus explicitly track)
868 every global when an unknown function is called; instead, they
869 can be tracked implicitly. */
871};
872
873} // namespace ana
874
875#endif /* GCC_ANALYZER_STORE_H */
Definition store.h:585
void mark_region_as_conjured(const gimple &stmt, const conjured_purge &p)
bool bits_live_p(const symbolic::bit_vector_from_ubc &bv_from_ubc) const
static bool can_merge_p(const binding_cluster *cluster_a, const binding_cluster *cluster_b, binding_cluster *out_cluster, store *out_store, model_merger *merger)
void make_unknown_relative_to(const binding_cluster *other_cluster, store *out_store, baseline_state bs)
const symbolic::bit_contents * m_contents
Definition store.h:687
void mark_as_untracked(symbolic::node_manager &node_mgr, uncertainty_t *uncertainty, value_set *maybe_live_values)
std::unique_ptr< text_art::tree_widget > make_dump_widget(symbolic::node_dump_state &nds) const
void set_bits(symbolic_bit_range bit_range, const symbolic::bit_vector &bits, uncertainty_t *uncertainty)
bool m_escaped
Definition store.h:695
friend class store
Definition store.h:587
const symbolic::bit_vector & get_bits(symbolic_bit_range bit_range) const
binding_cluster(const binding_cluster &other)
void purge_state_involving(const symbolic::node &node)
hashval_t hash() const
void validate() const
bool symbolic_p() const
void on_asm(const gasm *stmt, const conjured_purge &p)
void get_representative_path_vars(const region_model *model, value_set *visited, const region *base_reg, const svalue *sval, logger *logger, auto_vec< path_var > *out_pvs) const
bool operator==(const binding_cluster &other) const
const symbolic::bit_contents & get_bit_contents() const
Definition store.h:625
void set_bit_contents(const symbolic::bit_contents &bc)
Definition store.h:628
bool operator!=(const binding_cluster &other) const
Definition store.h:596
bool redundant_p(const store &store_, baseline_state bs) const
binding_cluster & operator=(const binding_cluster &other)
void poison_any_pointers_to_descendents(const region *reg, enum poison_kind pkind)
binding_cluster(symbolic::node_manager &node_mgr, const region *base_region, const symbolic::bit_contents &contents)
const region * get_base_region() const
Definition store.h:605
const region * m_base_region
Definition store.h:685
bool touched_p() const
Definition store.h:663
void on_unknown_fncall(const gcall &call, const conjured_purge &p)
bool escaped_p() const
iter_result for_each_value(iter_result(*cb)(const symbolic::value_node &val, void *user_data), void *user_data) const
std::unique_ptr< json::object > to_json() const
bool m_touched
Definition store.h:701
symbolic::node_manager & m_node_mgr
Definition store.h:683
Definition call-summary.h:68
Definition concrete-ranges.h:33
Definition symbolic-nodes.h:585
Definition integer-with-unit.h:33
Definition analyzer-logging.h:36
Definition region-model-manager.h:36
Definition region-model.h:289
Definition region.h:130
std::unique_ptr< json::object > to_json() const
void on_unknown_fncall(const gcall &call, const conjured_purge &p)
bool escaped_p(const region *reg) const
store(const store &other)
store(symbolic::node_manager &node_mgr)
void summarize_to_pp(pretty_printer *pp, bool simple) const
void dump() const
symbolic::node_manager & m_node_mgr
Definition store.h:856
void canonicalize()
bool operator==(const store &other) const
void mark_region_as_conjured(const region &base_reg, baseline_state bs, const gimple &stmt, const conjured_purge &p)
store & operator=(const store &other)
void clobber_region(const region *reg, baseline_state bs, region_model_manager &rmm)
hash_map< const region *, binding_cluster * > cluster_map_t
Definition store.h:711
void get_representative_path_vars(const region_model *model, value_set *visited, const svalue *sval, logger *logger, auto_vec< path_var > *out_pvs) const
cluster_map_t::iterator end() const
Definition store.h:813
void mark_as_escaped(const region *base_reg, baseline_state bs)
bool m_called_unknown_fn
Definition store.h:870
const symbolic::bit_contents & get_bit_contents(const region &base_reg, baseline_state bs) const
const symbolic::bit_vector & get_bits(const symbolic::memory_range &mem_range, baseline_state bs) const
void on_maybe_live_values(const value_set &maybe_live_values, baseline_state bs)
bool operator!=(const store &other) const
Definition store.h:720
void purge_region(const region *reg)
const symbolic::bit_contents & get_implicit_contents(const region &base_reg, baseline_state bs) const
bool replay_call_summary_cluster(call_summary_replay &r, const store &summary, const region *base_reg)
bool called_unknown_fn_p() const
Definition store.h:745
cluster_map_t m_cluster_map
Definition store.h:858
tristate eval_alias(const region *base_reg_a, const region *base_reg_b, const region_model &model) const
bool bits_live_p(const symbolic::bit_vector_from_ubc &bv_from_ubc, const region_model &model) const
const binding_cluster * get_cluster(const region *base_reg) const
binding_cluster * get_or_create_cluster(const region *base_reg, baseline_state bs)
void loop_replay_fixup(const store *other_store, baseline_state bs, region_model_manager *mgr)
std::unique_ptr< text_art::tree_widget > make_dump_widget(symbolic::node_dump_state &nds) const
static bool can_merge_p(const store *store_a, const store *store_b, store *out_store, model_merger *merger)
void validate() const
void set_bits(const region *lhs_reg, const symbolic::bit_vector &bv, uncertainty_t *uncertainty, const region_model &model)
void set_bits(const symbolic::memory_range &mem_range, const symbolic::bit_vector &bv, uncertainty_t *uncertainty, const region_model &model)
void mark_region_as_unknown(const region *reg, baseline_state bs, uncertainty_t *uncertainty, const region_model &model)
void set_bit_contents_raw(const region &base_reg, const symbolic::bit_contents &bc, const region_model &model)
cluster_map_t::iterator begin() const
Definition store.h:812
hashval_t hash() const
binding_cluster * get_cluster(const region *base_reg)
void purge_state_involving(const symbolic::node &node)
bool replay_call_summary_bit_contents(call_summary_replay &r, const store &summary, const region &summary_base_reg, const region &caller_dest_reg, const symbolic::bit_contents &caller_bc)
bool replay_call_summary(call_summary_replay &r, const store &summary)
void purge_cluster(const region *base_reg)
void for_each_cluster(void(*cb)(const region *base_reg, T user_data), T user_data) const
Definition store.h:782
const symbolic::bit_contents & get_baseline_contents(const region &base_reg, baseline_state bs) const
tristate eval_alias_1(const region *base_reg_a, const region *base_reg_b, const region_model &model) const
Definition svalue.h:82
Definition symbolic-bit-contents.h:68
Definition symbolic-bit-vectors.h:990
Definition symbolic-bit-vectors.h:107
Definition symbolic-memory-ranges.h:34
Definition symbolic-nodes.h:48
Definition symbolic-nodes.h:116
Definition symbolic-nodes.h:468
Definition store.h:357
bool unknown_sm_state_p(const svalue *sval)
void on_maybe_bound_value(const symbolic::value_node &val)
hash_set< const symbolic::value_node * > m_mutable_at_unknown_call_vals
Definition store.h:389
void on_mutable_value_at_unknown_call(const symbolic::value_node &val)
std::unique_ptr< text_art::tree_widget > make_dump_widget(symbolic::node_dump_state &nds) const
hash_set< constsymbolic::value_node * >::iterator iterator
Definition store.h:359
hash_set< const symbolic::value_node * > m_maybe_bound_vals
Definition store.h:386
iterator end_maybe_bound_svals() const
Definition store.h:378
void add_bit_contents(const symbolic::bit_contents &bc)
void dump_to_logger(logger &) const
void dump() const
iterator begin_maybe_bound_svals() const
Definition store.h:374
Definition vec.h:1667
iterator begin() const
Definition hash-map.h:302
iterator end() const
Definition hash-map.h:303
Definition hash-set.h:110
Definition hash-set.h:37
Definition inchash.h:38
hashval_t end() const
Definition inchash.h:49
void add_wide_int(const generic_wide_int< T > &x)
Definition inchash.h:84
Definition pretty-print.h:241
Definition tristate.h:26
Definition access-diagram.h:30
offset_int byte_size_t
Definition common.h:275
offset_int bit_offset_t
Definition common.h:272
concrete_bit_size convert_from_bit_size_t(bit_size_t)
symbolic::range< integer_with_unit< units::bit > > symbolic_bit_range
Definition common.h:124
poison_kind
Definition common.h:520
@ other
Definition common.h:535
offset_int byte_offset_t
Definition common.h:274
iter_result
Definition common.h:563
bit_range convert_to_bit_range(concrete::range< integer_with_unit< units::bit > > new_bits)
Definition store.h:496
bit_size_t convert_to_bit_size_t(concrete_bit_size)
baseline_state
Definition common.h:546
bit_offset_t convert_to_bit_offset_t(concrete_bit_offset)
offset_int bit_size_t
Definition common.h:273
concrete_bit_offset convert_from_bit_offset_t(bit_offset_t)
concrete::range< integer_with_unit< units::bit > > convert_from_bit_range(bit_range old_bits)
Definition store.h:488
symbolic::node_set< symbolic::value_node > value_set
Definition symbolic-nodes.h:461
Definition custom-sarif-properties/state-graphs.h:33
poly_int< N, C > r
Definition poly-int.h:774
Definition store.h:398
bit_range operator-(bit_offset_t offset) const
bool operator==(const bit_range &other) const
Definition store.h:436
std::unique_ptr< json::object > to_json() const
bool exceeds_p(const bit_range &other, bit_range *out_overhanging_bit_range) const
bool empty_p() const
Definition store.h:409
bool intersects_p(const bit_range &other) const
Definition store.h:442
bool falls_short_of_p(bit_offset_t offset, bit_range *out_fall_short_bits) const
bool operator<(const bit_range &other) const
Definition store.h:466
bool intersects_p(const bit_range &other, bit_range *out_this, bit_range *out_other) const
bit_size_t m_size_in_bits
Definition store.h:484
bool contains_p(bit_offset_t offset) const
Definition store.h:428
bit_offset_t get_next_bit_offset() const
Definition store.h:418
bit_offset_t m_start_bit_offset
Definition store.h:483
bool intersects_p(const bit_range &other, bit_size_t *out_num_overlap_bits) const
void dump_to_pp(pretty_printer *pp) const
bit_range(bit_offset_t start_bit_offset, bit_size_t size_in_bits)
Definition store.h:399
hashval_t hash() const
Definition store.h:475
bool as_byte_range(byte_range *out) const
void dump() const
static int cmp(const bit_range &br1, const bit_range &br2)
bool contains_p(const bit_range &other, bit_range *out) const
bit_offset_t get_start_bit_offset() const
Definition store.h:414
bit_offset_t get_last_bit_offset() const
Definition store.h:422
Definition store.h:507
bool operator==(const byte_range &other) const
Definition store.h:530
byte_offset_t get_next_byte_offset() const
Definition store.h:540
byte_size_t m_size_in_bytes
Definition store.h:572
byte_offset_t get_last_byte_offset() const
Definition store.h:544
bool contains_p(byte_offset_t offset) const
Definition store.h:523
bit_size_t get_size_in_bits() const
Definition store.h:564
byte_offset_t get_start_byte_offset() const
Definition store.h:536
void dump_to_pp(pretty_printer *pp) const
void dump() const
byte_range(byte_offset_t start_byte_offset, byte_size_t size_in_bytes)
Definition store.h:508
static int cmp(const byte_range &br1, const byte_range &br2)
bit_offset_t get_start_bit_offset() const
Definition store.h:556
byte_offset_t m_start_byte_offset
Definition store.h:571
bool contains_p(const byte_range &other, byte_range *out) const
bool empty_p() const
Definition store.h:518
bit_offset_t get_next_bit_offset() const
Definition store.h:560
std::unique_ptr< json::object > to_json() const
bit_range as_bit_range() const
Definition store.h:550
Definition region-model.h:1295
Definition symbolic-nodes.h:276
Definition gimple.h:553
Definition gimple.h:356
Definition gimple.h:225
#define gcc_assert(EXPR)
Definition system.h:772
tree size_in_bytes(const_tree t)
Definition tree.h:5560