Line data Source code
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 :
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 : #include "analyzer/common.h"
22 :
23 : #include "ordered-hash-map.h"
24 : #include "cfg.h"
25 : #include "sbitmap.h"
26 : #include "stor-layout.h"
27 :
28 : #include "text-art/tree-widget.h"
29 :
30 : #include "analyzer/analyzer-logging.h"
31 : #include "analyzer/supergraph.h"
32 : #include "analyzer/call-string.h"
33 : #include "analyzer/program-point.h"
34 : #include "analyzer/store.h"
35 : #include "analyzer/region-model.h"
36 : #include "analyzer/call-summary.h"
37 : #include "analyzer/analyzer-selftests.h"
38 :
39 : #if ENABLE_ANALYZER
40 :
41 : namespace ana {
42 :
43 : /* Dump SVALS to PP, sorting them to ensure determinism. */
44 :
45 : static void
46 482 : dump_svalue_set (const hash_set <const svalue *> &svals,
47 : pretty_printer *pp, bool simple)
48 : {
49 482 : auto_vec <const svalue *> v;
50 482 : for (hash_set<const svalue *>::iterator iter = svals.begin ();
51 552 : iter != svals.end (); ++iter)
52 : {
53 35 : v.safe_push (*iter);
54 : }
55 482 : v.qsort (svalue::cmp_ptr_ptr);
56 :
57 482 : pp_character (pp, '{');
58 482 : const svalue *sval;
59 482 : unsigned i;
60 999 : FOR_EACH_VEC_ELT (v, i, sval)
61 : {
62 35 : if (i > 0)
63 20 : pp_string (pp, ", ");
64 35 : sval->dump_to_pp (pp, simple);
65 : }
66 482 : pp_character (pp, '}');
67 482 : }
68 :
69 : /* class uncertainty_t. */
70 :
71 : /* Dump this object to PP. */
72 :
73 : void
74 241 : uncertainty_t::dump_to_pp (pretty_printer *pp, bool simple) const
75 : {
76 241 : pp_string (pp, "{m_maybe_bound_svals: ");
77 241 : dump_svalue_set (m_maybe_bound_svals, pp, simple);
78 :
79 241 : pp_string (pp, ", m_mutable_at_unknown_call_svals: ");
80 241 : dump_svalue_set (m_mutable_at_unknown_call_svals, pp, simple);
81 241 : pp_string (pp, "}");
82 241 : }
83 :
84 : /* Dump this object to stderr. */
85 :
86 : DEBUG_FUNCTION void
87 0 : uncertainty_t::dump (bool simple) const
88 : {
89 0 : tree_dump_pretty_printer pp (stderr);
90 0 : dump_to_pp (&pp, simple);
91 0 : pp_newline (&pp);
92 0 : }
93 :
94 : /* class binding_key. */
95 :
96 : const binding_key *
97 3688425 : binding_key::make (store_manager *mgr, const region *r)
98 : {
99 3688425 : region_offset offset = r->get_offset (mgr->get_svalue_manager ());
100 3688425 : if (offset.symbolic_p ())
101 34902 : return mgr->get_symbolic_binding (r);
102 : else
103 : {
104 3653523 : bit_size_t bit_size;
105 3653523 : if (r->get_bit_size (&bit_size))
106 : {
107 : /* Must be non-empty. */
108 2307823 : gcc_assert (bit_size > 0);
109 2307823 : return mgr->get_concrete_binding (offset.get_bit_offset (),
110 2307823 : bit_size);
111 : }
112 : else
113 1345700 : return mgr->get_symbolic_binding (r);
114 : }
115 : }
116 :
117 : /* Dump this binding_key to stderr. */
118 :
119 : DEBUG_FUNCTION void
120 0 : binding_key::dump (bool simple) const
121 : {
122 0 : tree_dump_pretty_printer pp (stderr);
123 0 : dump_to_pp (&pp, simple);
124 0 : pp_newline (&pp);
125 0 : }
126 :
127 : /* Get a description of this binding_key. */
128 :
129 : label_text
130 0 : binding_key::get_desc (bool simple) const
131 : {
132 0 : pretty_printer pp;
133 0 : pp_format_decoder (&pp) = default_tree_printer;
134 0 : dump_to_pp (&pp, simple);
135 0 : return label_text::take (xstrdup (pp_formatted_text (&pp)));
136 0 : }
137 :
138 : /* qsort callback. */
139 :
140 : int
141 0 : binding_key::cmp_ptrs (const void *p1, const void *p2)
142 : {
143 0 : const binding_key * const *pk1 = (const binding_key * const *)p1;
144 0 : const binding_key * const *pk2 = (const binding_key * const *)p2;
145 0 : return cmp (*pk1, *pk2);
146 : }
147 :
148 : /* Comparator for binding_keys. */
149 :
150 : int
151 0 : binding_key::cmp (const binding_key *k1, const binding_key *k2)
152 : {
153 0 : int concrete1 = k1->concrete_p ();
154 0 : int concrete2 = k2->concrete_p ();
155 0 : if (int concrete_cmp = concrete1 - concrete2)
156 : return concrete_cmp;
157 0 : if (concrete1)
158 : {
159 0 : const concrete_binding *b1 = (const concrete_binding *)k1;
160 0 : const concrete_binding *b2 = (const concrete_binding *)k2;
161 0 : if (int start_cmp = wi::cmp (b1->get_start_bit_offset (),
162 0 : b2->get_start_bit_offset (),
163 : SIGNED))
164 : return start_cmp;
165 0 : return wi::cmp (b1->get_next_bit_offset (), b2->get_next_bit_offset (),
166 : SIGNED);
167 : }
168 : else
169 : {
170 0 : const symbolic_binding *s1 = (const symbolic_binding *)k1;
171 0 : const symbolic_binding *s2 = (const symbolic_binding *)k2;
172 0 : if (s1 > s2)
173 : return 1;
174 0 : if (s1 < s2)
175 : return -1;
176 0 : return 0;
177 : }
178 : }
179 :
180 : /* struct bit_range. */
181 :
182 : void
183 2021 : bit_range::dump_to_pp (pretty_printer *pp) const
184 : {
185 2021 : byte_range bytes (0, 0);
186 2021 : if (as_byte_range (&bytes))
187 2021 : bytes.dump_to_pp (pp);
188 : else
189 : {
190 0 : pp_string (pp, "start: ");
191 0 : pp_wide_int (pp, m_start_bit_offset, SIGNED);
192 0 : pp_string (pp, ", size: ");
193 0 : pp_wide_int (pp, m_size_in_bits, SIGNED);
194 0 : pp_string (pp, ", next: ");
195 0 : pp_wide_int (pp, get_next_bit_offset (), SIGNED);
196 : }
197 2021 : }
198 :
199 : /* Dump this object to stderr. */
200 :
201 : DEBUG_FUNCTION void
202 0 : bit_range::dump () const
203 : {
204 0 : tree_dump_pretty_printer pp (stderr);
205 0 : dump_to_pp (&pp);
206 0 : pp_newline (&pp);
207 0 : }
208 :
209 : /* Generate a JSON value for this bit_range.
210 : This is intended for debugging the analyzer rather
211 : than serialization. */
212 :
213 : std::unique_ptr<json::object>
214 4 : bit_range::to_json () const
215 : {
216 4 : auto obj = std::make_unique<json::object> ();
217 4 : obj->set ("start_bit_offset",
218 4 : bit_offset_to_json (m_start_bit_offset));
219 4 : obj->set ("size_in_bits",
220 4 : bit_offset_to_json (m_size_in_bits));
221 4 : return obj;
222 : }
223 :
224 : /* If OTHER is a subset of this, return true and, if OUT is
225 : non-null, write to *OUT the relative range of OTHER within this.
226 : Otherwise return false. */
227 :
228 : bool
229 23827 : bit_range::contains_p (const bit_range &other, bit_range *out) const
230 : {
231 23827 : if (contains_p (other.get_start_bit_offset ())
232 23827 : && contains_p (other.get_last_bit_offset ()))
233 : {
234 16289 : if (out)
235 : {
236 16289 : out->m_start_bit_offset = other.m_start_bit_offset - m_start_bit_offset;
237 16289 : out->m_size_in_bits = other.m_size_in_bits;
238 : }
239 16289 : return true;
240 : }
241 : else
242 7538 : return false;
243 : }
244 :
245 : /* If OTHER intersects this, return true and write
246 : the relative range of OTHER within THIS to *OUT_THIS,
247 : and the relative range of THIS within OTHER to *OUT_OTHER.
248 : Otherwise return false. */
249 :
250 : bool
251 84 : bit_range::intersects_p (const bit_range &other,
252 : bit_range *out_this,
253 : bit_range *out_other) const
254 : {
255 84 : if (get_start_bit_offset () < other.get_next_bit_offset ()
256 168 : && other.get_start_bit_offset () < get_next_bit_offset ())
257 : {
258 84 : bit_offset_t overlap_start
259 84 : = MAX (get_start_bit_offset (),
260 : other.get_start_bit_offset ());
261 84 : bit_offset_t overlap_next
262 84 : = MIN (get_next_bit_offset (),
263 : other.get_next_bit_offset ());
264 84 : if (overlap_next <= overlap_start)
265 : /* If this has happened, some kind of overflow has happened in
266 : our arithmetic. For now, reject such cases. */
267 : return false;
268 84 : bit_range abs_overlap_bits (overlap_start, overlap_next - overlap_start);
269 84 : *out_this = abs_overlap_bits - get_start_bit_offset ();
270 84 : *out_other = abs_overlap_bits - other.get_start_bit_offset ();
271 84 : return true;
272 : }
273 : else
274 0 : return false;
275 : }
276 :
277 : /* Return true if THIS and OTHER intersect and write the number
278 : of bits both buffers overlap to *OUT_NUM_OVERLAP_BITS.
279 :
280 : Otherwise return false. */
281 :
282 : bool
283 0 : bit_range::intersects_p (const bit_range &other,
284 : bit_size_t *out_num_overlap_bits) const
285 : {
286 0 : if (get_start_bit_offset () < other.get_next_bit_offset ()
287 0 : && other.get_start_bit_offset () < get_next_bit_offset ())
288 : {
289 0 : bit_offset_t overlap_start = MAX (get_start_bit_offset (),
290 : other.get_start_bit_offset ());
291 0 : bit_offset_t overlap_next = MIN (get_next_bit_offset (),
292 : other.get_next_bit_offset ());
293 0 : if (overlap_next <= overlap_start)
294 : /* If this has happened, some kind of overflow has happened in
295 : our arithmetic. For now, reject such cases. */
296 : return false;
297 0 : *out_num_overlap_bits = overlap_next - overlap_start;
298 0 : return true;
299 : }
300 : else
301 0 : return false;
302 : }
303 :
304 : /* Return true if THIS exceeds OTHER and write the overhanging
305 : bit range to OUT_OVERHANGING_BIT_RANGE. */
306 :
307 : bool
308 815303 : bit_range::exceeds_p (const bit_range &other,
309 : bit_range *out_overhanging_bit_range) const
310 : {
311 815303 : gcc_assert (!empty_p ());
312 :
313 815303 : if (other.get_next_bit_offset () < get_next_bit_offset ())
314 : {
315 : /* THIS definitely exceeds OTHER. */
316 460 : bit_offset_t start = MAX (get_start_bit_offset (),
317 : other.get_next_bit_offset ());
318 460 : bit_offset_t size = get_next_bit_offset () - start;
319 460 : if (size <= 0)
320 : /* If this has happened, some kind of overflow has happened in
321 : our arithmetic. For now, reject such cases. */
322 : return false;
323 440 : out_overhanging_bit_range->m_start_bit_offset = start;
324 440 : out_overhanging_bit_range->m_size_in_bits = size;
325 440 : return true;
326 : }
327 : else
328 : return false;
329 : }
330 :
331 : /* Return true if THIS falls short of OFFSET and write the
332 : bit range fallen short to OUT_FALL_SHORT_BITS. */
333 :
334 : bool
335 818993 : bit_range::falls_short_of_p (bit_offset_t offset,
336 : bit_range *out_fall_short_bits) const
337 : {
338 818993 : gcc_assert (!empty_p ());
339 :
340 818993 : if (get_start_bit_offset () < offset)
341 : {
342 : /* THIS falls short of OFFSET. */
343 212 : bit_offset_t start = get_start_bit_offset ();
344 212 : bit_offset_t size = MIN (offset, get_next_bit_offset ()) - start;
345 212 : if (size <= 0)
346 : /* If this has happened, some kind of overflow has happened in
347 : our arithmetic. For now, reject such cases. */
348 : return false;
349 192 : out_fall_short_bits->m_start_bit_offset = start;
350 192 : out_fall_short_bits->m_size_in_bits = size;
351 192 : return true;
352 : }
353 : else
354 : return false;
355 : }
356 :
357 : int
358 442 : bit_range::cmp (const bit_range &br1, const bit_range &br2)
359 : {
360 442 : if (int start_cmp = wi::cmps (br1.m_start_bit_offset,
361 442 : br2.m_start_bit_offset))
362 : return start_cmp;
363 :
364 48 : return wi::cmpu (br1.m_size_in_bits, br2.m_size_in_bits);
365 : }
366 :
367 : /* Offset this range by OFFSET. */
368 :
369 : bit_range
370 168 : bit_range::operator- (bit_offset_t offset) const
371 : {
372 168 : return bit_range (m_start_bit_offset - offset, m_size_in_bits);
373 : }
374 :
375 : /* If MASK is a contiguous range of set bits, write them
376 : to *OUT and return true.
377 : Otherwise return false. */
378 :
379 : bool
380 144 : bit_range::from_mask (unsigned HOST_WIDE_INT mask, bit_range *out)
381 : {
382 144 : unsigned iter_bit_idx = 0;
383 144 : unsigned HOST_WIDE_INT iter_bit_mask = 1;
384 :
385 : /* Find the first contiguous run of set bits in MASK. */
386 :
387 : /* Find first set bit in MASK. */
388 780 : while (iter_bit_idx < HOST_BITS_PER_WIDE_INT)
389 : {
390 776 : if (mask & iter_bit_mask)
391 : break;
392 636 : iter_bit_idx++;
393 636 : iter_bit_mask <<= 1;
394 : }
395 144 : if (iter_bit_idx == HOST_BITS_PER_WIDE_INT)
396 : /* MASK is zero. */
397 : return false;
398 :
399 140 : unsigned first_set_iter_bit_idx = iter_bit_idx;
400 140 : unsigned num_set_bits = 1;
401 140 : iter_bit_idx++;
402 140 : iter_bit_mask <<= 1;
403 :
404 : /* Find next unset bit in MASK. */
405 396 : while (iter_bit_idx < HOST_BITS_PER_WIDE_INT)
406 : {
407 396 : if (!(mask & iter_bit_mask))
408 : break;
409 256 : num_set_bits++;
410 256 : iter_bit_idx++;
411 256 : iter_bit_mask <<= 1;
412 : }
413 140 : if (iter_bit_idx == HOST_BITS_PER_WIDE_INT)
414 : {
415 0 : *out = bit_range (first_set_iter_bit_idx, num_set_bits);
416 0 : return true;
417 : }
418 :
419 : /* We now have the first contiguous run of set bits in MASK.
420 : Fail if any other bits are set. */
421 7892 : while (iter_bit_idx < HOST_BITS_PER_WIDE_INT)
422 : {
423 7760 : if (mask & iter_bit_mask)
424 : return false;
425 7752 : iter_bit_idx++;
426 7752 : iter_bit_mask <<= 1;
427 : }
428 :
429 132 : *out = bit_range (first_set_iter_bit_idx, num_set_bits);
430 132 : return true;
431 : }
432 :
433 : /* Attempt to convert this bit_range to a byte_range.
434 : Return true if it is possible, writing the result to *OUT.
435 : Otherwise return false. */
436 :
437 : bool
438 8199 : bit_range::as_byte_range (byte_range *out) const
439 : {
440 8199 : if (m_start_bit_offset % BITS_PER_UNIT == 0
441 8199 : && m_size_in_bits % BITS_PER_UNIT == 0)
442 : {
443 8186 : out->m_start_byte_offset = m_start_bit_offset / BITS_PER_UNIT;
444 8186 : out->m_size_in_bytes = m_size_in_bits / BITS_PER_UNIT;
445 8186 : return true;
446 : }
447 : return false;
448 : }
449 :
450 : /* Dump this object to PP. */
451 :
452 : void
453 2024 : byte_range::dump_to_pp (pretty_printer *pp) const
454 : {
455 2024 : if (m_size_in_bytes == 0)
456 : {
457 0 : pp_string (pp, "empty");
458 : }
459 2024 : else if (m_size_in_bytes == 1)
460 : {
461 1447 : pp_string (pp, "byte ");
462 1447 : pp_wide_int (pp, m_start_byte_offset, SIGNED);
463 : }
464 : else
465 : {
466 577 : pp_string (pp, "bytes ");
467 577 : pp_wide_int (pp, m_start_byte_offset, SIGNED);
468 577 : pp_string (pp, "-");
469 577 : pp_wide_int (pp, get_last_byte_offset (), SIGNED);
470 : }
471 2024 : }
472 :
473 : /* Dump this object to stderr. */
474 :
475 : DEBUG_FUNCTION void
476 0 : byte_range::dump () const
477 : {
478 0 : tree_dump_pretty_printer pp (stderr);
479 0 : dump_to_pp (&pp);
480 0 : pp_newline (&pp);
481 0 : }
482 :
483 : /* Generate a JSON value for this byte_range.
484 : This is intended for debugging the analyzer rather
485 : than serialization. */
486 :
487 : std::unique_ptr<json::object>
488 4 : byte_range::to_json () const
489 : {
490 4 : auto obj = std::make_unique<json::object> ();
491 4 : obj->set ("start_byte_offset",
492 4 : byte_offset_to_json (m_start_byte_offset));
493 4 : obj->set ("size_in_bytes",
494 4 : byte_offset_to_json (m_size_in_bytes));
495 4 : return obj;
496 : }
497 :
498 : /* If OTHER is a subset of this, return true and write
499 : to *OUT the relative range of OTHER within this.
500 : Otherwise return false. */
501 :
502 : bool
503 948 : byte_range::contains_p (const byte_range &other, byte_range *out) const
504 : {
505 948 : if (contains_p (other.get_start_byte_offset ())
506 948 : && contains_p (other.get_last_byte_offset ()))
507 : {
508 396 : out->m_start_byte_offset = other.m_start_byte_offset - m_start_byte_offset;
509 396 : out->m_size_in_bytes = other.m_size_in_bytes;
510 396 : return true;
511 : }
512 : else
513 552 : return false;
514 : }
515 :
516 : /* qsort comparator for byte ranges. */
517 :
518 : int
519 1977 : byte_range::cmp (const byte_range &br1, const byte_range &br2)
520 : {
521 : /* Order first by offset. */
522 1977 : if (int start_cmp = wi::cmps (br1.m_start_byte_offset,
523 1977 : br2.m_start_byte_offset))
524 : return start_cmp;
525 :
526 : /* ...then by size. */
527 0 : return wi::cmpu (br1.m_size_in_bytes, br2.m_size_in_bytes);
528 : }
529 :
530 : /* class concrete_binding : public binding_key. */
531 :
532 : /* Implementation of binding_key::dump_to_pp vfunc for concrete_binding. */
533 :
534 : void
535 1133 : concrete_binding::dump_to_pp (pretty_printer *pp, bool) const
536 : {
537 1133 : m_bit_range.dump_to_pp (pp);
538 1133 : }
539 :
540 : /* Return true if this binding overlaps with OTHER. */
541 :
542 : bool
543 305487 : concrete_binding::overlaps_p (const concrete_binding &other) const
544 : {
545 305487 : if (get_start_bit_offset () < other.get_next_bit_offset ()
546 305487 : && get_next_bit_offset () > other.get_start_bit_offset ())
547 60332 : return true;
548 : return false;
549 : }
550 :
551 : /* If this is expressible as a concrete byte range, return true
552 : and write it to *OUT. Otherwise return false. */
553 :
554 : bool
555 0 : concrete_binding::get_byte_range (byte_range *out) const
556 : {
557 0 : return m_bit_range.as_byte_range (out);
558 : }
559 :
560 : /* Comparator for use by vec<const concrete_binding *>::qsort. */
561 :
562 : int
563 41 : concrete_binding::cmp_ptr_ptr (const void *p1, const void *p2)
564 : {
565 41 : const concrete_binding *b1 = *(const concrete_binding * const *)p1;
566 41 : const concrete_binding *b2 = *(const concrete_binding * const *)p2;
567 :
568 41 : return bit_range::cmp (b1->m_bit_range, b2->m_bit_range);
569 : }
570 :
571 : /* class symbolic_binding : public binding_key. */
572 :
573 : void
574 16 : symbolic_binding::dump_to_pp (pretty_printer *pp, bool simple) const
575 : {
576 : //binding_key::dump_to_pp (pp, simple);
577 16 : pp_string (pp, "region: ");
578 16 : m_region->dump_to_pp (pp, simple);
579 16 : }
580 :
581 : /* Comparator for use by vec<const symbolic_binding *>::qsort. */
582 :
583 : int
584 19 : symbolic_binding::cmp_ptr_ptr (const void *p1, const void *p2)
585 : {
586 19 : const symbolic_binding *b1 = *(const symbolic_binding * const *)p1;
587 19 : const symbolic_binding *b2 = *(const symbolic_binding * const *)p2;
588 :
589 19 : return region::cmp_ids (b1->get_region (), b2->get_region ());
590 : }
591 :
592 : /* The store is oblivious to the types of the svalues bound within
593 : it: any type can get bound at any location.
594 : Simplify any casts before binding.
595 :
596 : For example, if we have:
597 : struct big { int ia[1024]; };
598 : struct big src, dst;
599 : memcpy (&dst, &src, sizeof (struct big));
600 : this reaches us in gimple form as:
601 : MEM <unsigned char[4096]> [(char * {ref-all})&dst]
602 : = MEM <unsigned char[4096]> [(char * {ref-all})&src];
603 : Using cast_region when handling the MEM_REF would give us:
604 : INIT_VAL(CAST_REG(unsigned char[4096], src))
605 : as rhs_sval, but we can fold that into a cast svalue:
606 : CAST(unsigned char[4096], INIT_VAL(src))
607 : We can discard that cast from the svalue when binding it in
608 : the store for "dst", and simply store:
609 : cluster for: dst
610 : key: {kind: direct, start: 0, size: 32768, next: 32768}
611 : value: ‘struct big’ {INIT_VAL(src)}. */
612 :
613 : static const svalue *
614 425799 : simplify_for_binding (const svalue *sval)
615 : {
616 425799 : if (const svalue *cast_sval = sval->maybe_undo_cast ())
617 0 : sval = cast_sval;
618 46064 : return sval;
619 : }
620 :
621 : /* class concrete_binding_map. */
622 :
623 : /* Dump a representation of this concrete_binding_map to PP.
624 : SIMPLE controls how values and regions are to be printed.
625 : If MULTILINE, then split the dump over multiple lines and
626 : use whitespace for readability, otherwise put all on one line. */
627 :
628 : void
629 2 : concrete_binding_map::dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const
630 : {
631 2 : bool first = true;
632 4 : for (auto iter : *this)
633 : {
634 2 : const bit_range &bits = iter.first;
635 2 : const svalue *value = iter.second;
636 2 : if (multiline)
637 : {
638 0 : pp_string (pp, " bits: {");
639 0 : bits.dump_to_pp (pp);
640 0 : pp_string (pp, "}");
641 0 : pp_newline (pp);
642 0 : pp_string (pp, " value: ");
643 0 : if (tree t = value->get_type ())
644 0 : dump_quoted_tree (pp, t);
645 0 : pp_string (pp, " {");
646 0 : value->dump_to_pp (pp, simple);
647 0 : pp_string (pp, "}");
648 0 : pp_newline (pp);
649 : }
650 : else
651 : {
652 2 : if (first)
653 : first = false;
654 : else
655 0 : pp_string (pp, ", ");
656 2 : pp_string (pp, "bits: {");
657 2 : bits.dump_to_pp (pp);
658 2 : pp_string (pp, "}, value: {");
659 2 : value->dump_to_pp (pp, simple);
660 2 : pp_string (pp, "}");
661 : }
662 : }
663 2 : }
664 :
665 : void
666 0 : concrete_binding_map::dump (bool simple) const
667 : {
668 0 : tree_dump_pretty_printer pp (stderr);
669 0 : dump_to_pp (&pp, simple, true);
670 0 : pp_newline (&pp);
671 0 : }
672 :
673 : void
674 0 : concrete_binding_map::add_to_tree_widget (text_art::tree_widget &parent_widget,
675 : const text_art::dump_widget_info &dwi) const
676 : {
677 0 : for (auto iter : *this)
678 : {
679 0 : const bit_range &bits = iter.first;
680 0 : const svalue *sval = iter.second;
681 :
682 0 : pretty_printer the_pp;
683 0 : pretty_printer * const pp = &the_pp;
684 0 : pp_format_decoder (pp) = default_tree_printer;
685 0 : pp_show_color (pp) = true;
686 0 : const bool simple = true;
687 :
688 0 : bits.dump_to_pp (pp);
689 0 : pp_string (pp, ": ");
690 0 : if (tree t = sval->get_type ())
691 0 : dump_quoted_tree (pp, t);
692 0 : pp_string (pp, " {");
693 0 : sval->dump_to_pp (pp, simple);
694 0 : pp_string (pp, "}");
695 :
696 0 : parent_widget.add_child (text_art::tree_widget::make (dwi, pp));
697 0 : }
698 0 : }
699 :
700 : void
701 13369830 : concrete_binding_map::validate () const
702 : {
703 28454412 : for (auto iter = m_map.begin (); iter != m_map.end (); ++iter)
704 : {
705 : /* Ensure we don't nest compound svalues
706 : within concrete_binding_map instances. */
707 15084582 : const svalue *sval = iter->second;
708 15084582 : gcc_assert (sval->get_kind () != SK_COMPOUND);
709 :
710 : /* Check for overlapping concrete bindings. */
711 15084582 : auto next (iter);
712 15084582 : ++next;
713 15084582 : if (next != m_map.end ())
714 : {
715 : /* Verify they are in order, and do not overlap. */
716 4146497 : const bit_range &iter_bits = iter->first;
717 4146497 : const bit_range &next_bits = next->first;
718 4146497 : gcc_assert (iter_bits.get_start_bit_offset ()
719 : < next_bits.get_start_bit_offset ());
720 4146497 : gcc_assert (iter_bits.get_last_bit_offset ()
721 : < next_bits.get_start_bit_offset ());
722 4146497 : gcc_assert (iter_bits.get_next_bit_offset ()
723 : <= next_bits.get_start_bit_offset ());
724 : }
725 : }
726 13369830 : }
727 :
728 : /* Comparator for imposing an order on concrete_binding_map instances. */
729 :
730 : int
731 28 : concrete_binding_map::cmp (const concrete_binding_map &map1,
732 : const concrete_binding_map &map2)
733 : {
734 28 : if (int size_cmp = map1.size () - map2.size ())
735 : return size_cmp;
736 :
737 28 : auto iter1 = map1.begin ();
738 28 : auto iter2 = map2.begin ();
739 28 : while (iter1 != map1.end ())
740 : {
741 28 : gcc_assert (iter2 != map2.end ());
742 28 : if (int bit_cmp = bit_range::cmp (iter1->first, iter2->first))
743 : return bit_cmp;
744 28 : if (int sval_cmp = svalue::cmp_ptr (iter1->second, iter2->second))
745 : return sval_cmp;
746 0 : ++iter1;
747 0 : ++iter2;
748 : }
749 : return 0;
750 : }
751 :
752 : /* Get the svalue bound precisely to BITS, if any, otherwise
753 : return nullptr. */
754 :
755 : const svalue *
756 56 : concrete_binding_map::get_any_exact_binding (const bit_range &bits) const
757 : {
758 56 : auto iter = m_map.find (bits);
759 56 : if (iter == m_map.end ())
760 : return nullptr;
761 56 : return iter->second;
762 : }
763 :
764 : /* Calculate what the complexity of a compound_svalue instance for this
765 : map will be, based on the bound svalues. */
766 :
767 : complexity
768 661 : concrete_binding_map::calc_complexity () const
769 : {
770 661 : unsigned num_child_nodes = 0;
771 661 : unsigned max_child_depth = 0;
772 2640 : for (auto iter : m_map)
773 : {
774 1979 : const complexity &sval_c = iter.second->get_complexity ();
775 1979 : num_child_nodes += sval_c.m_num_nodes;
776 1979 : max_child_depth = MAX (max_child_depth, sval_c.m_max_depth);
777 : }
778 661 : return complexity (num_child_nodes + 1, max_child_depth + 1);
779 : }
780 :
781 : void
782 39089 : concrete_binding_map::
783 : remove_overlapping_binding (store_manager *mgr,
784 : const bit_range &bits_to_drop,
785 : const bit_range &affected_bound_bits,
786 : const svalue &old_sval)
787 : {
788 39089 : gcc_assert (bits_to_drop.intersects_p (affected_bound_bits));
789 :
790 : /* Remove existing binding. */
791 39089 : erase (affected_bound_bits);
792 :
793 39089 : if (affected_bound_bits.get_start_bit_offset ()
794 39089 : < bits_to_drop.get_start_bit_offset ())
795 : {
796 : /* We have a truncated prefix. */
797 1540 : bit_range prefix_bits (affected_bound_bits.get_start_bit_offset (),
798 3080 : (bits_to_drop.get_start_bit_offset ()
799 1540 : - affected_bound_bits.get_start_bit_offset ()));
800 1540 : bit_range rel_prefix (0, prefix_bits.m_size_in_bits);
801 1540 : const svalue *prefix_sval
802 1540 : = old_sval.extract_bit_range (NULL_TREE,
803 : rel_prefix,
804 : mgr->get_svalue_manager ());
805 1540 : insert (prefix_bits, prefix_sval);
806 : }
807 :
808 78178 : if (affected_bound_bits.get_next_bit_offset ()
809 78178 : > bits_to_drop.get_next_bit_offset ())
810 : {
811 : /* We have a truncated suffix. */
812 10761 : bit_range suffix_bits (bits_to_drop.get_next_bit_offset (),
813 10761 : (affected_bound_bits.get_next_bit_offset ()
814 21522 : - bits_to_drop.get_next_bit_offset ()));
815 10761 : bit_range rel_suffix (bits_to_drop.get_next_bit_offset ()
816 10761 : - affected_bound_bits.get_start_bit_offset (),
817 10761 : suffix_bits.m_size_in_bits);
818 10761 : const svalue *suffix_sval
819 10761 : = old_sval.extract_bit_range (NULL_TREE,
820 : rel_suffix,
821 : mgr->get_svalue_manager ());
822 10761 : insert (suffix_bits, suffix_sval);
823 : }
824 39089 : }
825 :
826 : void
827 8979 : concrete_binding_map::
828 : remove_overlapping_bindings (store_manager *mgr,
829 : const bit_range &bits_to_drop)
830 : {
831 8979 : auto bindings = get_overlapping_bindings (bits_to_drop);
832 17958 : for (auto iter : bindings)
833 8979 : remove_overlapping_binding (mgr, bits_to_drop, iter.first, iter.second);
834 8979 : }
835 :
836 : std::vector<std::pair<bit_range, const svalue &>>
837 8979 : concrete_binding_map::get_overlapping_bindings (const bit_range &bits)
838 : {
839 8979 : std::vector<std::pair<bit_range, const svalue &>> result;
840 18009 : for (auto iter : m_map)
841 9030 : if (iter.first.intersects_p (bits))
842 : {
843 8979 : gcc_assert (iter.second);
844 8979 : result.push_back ({iter.first, *iter.second});
845 : }
846 8979 : return result;
847 : }
848 :
849 : /* class binding_map::const_iterator. */
850 :
851 : bool
852 26056563 : binding_map::const_iterator::operator== (const binding_map::const_iterator &other) const
853 : {
854 26056563 : if (m_concrete != other.m_concrete)
855 : return false;
856 11960239 : if (m_symbolic != other.m_symbolic)
857 521080 : return false;
858 : return true;
859 : }
860 :
861 : binding_map::const_iterator &
862 14610018 : binding_map::const_iterator::operator++ ()
863 : {
864 14610018 : if (m_concrete != m_map.m_concrete.end ())
865 14088938 : ++m_concrete;
866 : else
867 521080 : ++m_symbolic;
868 14610018 : return *this;
869 : }
870 :
871 : binding_map::binding_pair
872 3628584 : binding_map::const_iterator::operator* ()
873 : {
874 3628584 : if (m_concrete != m_map.m_concrete.end ())
875 : {
876 3524595 : const bit_range &bits = m_concrete->first;
877 3524595 : const svalue *sval = m_concrete->second;
878 3524595 : return binding_pair (m_map.m_store_mgr.get_concrete_binding (bits), sval);
879 : }
880 : else
881 : {
882 103989 : gcc_assert (m_symbolic != m_map.m_symbolic.end ());
883 103989 : const region *reg = m_symbolic->m_region;
884 103989 : const svalue *sval = m_symbolic->m_sval;
885 103989 : return binding_pair (m_map.m_store_mgr.get_symbolic_binding (reg), sval);
886 : }
887 : }
888 :
889 : const svalue *
890 10988820 : binding_map::const_iterator::get_svalue () const
891 : {
892 10988820 : if (m_concrete != m_map.m_concrete.end ())
893 10571729 : return m_concrete->second;
894 : else
895 : {
896 417091 : gcc_assert (m_symbolic != m_map.m_symbolic.end ());
897 417091 : return m_symbolic->m_sval;
898 : }
899 : }
900 :
901 : /* class binding_map::iterator. */
902 :
903 : bool
904 15296727 : binding_map::iterator::operator== (const binding_map::iterator &other) const
905 : {
906 15296727 : if (m_concrete != other.m_concrete)
907 : return false;
908 7314520 : if (m_symbolic != other.m_symbolic)
909 402498 : return false;
910 : return true;
911 : }
912 :
913 : binding_map::iterator &
914 8383622 : binding_map::iterator::operator++ ()
915 : {
916 8383622 : if (m_concrete != m_map.m_concrete.end ())
917 7981129 : ++m_concrete;
918 : else
919 402493 : ++m_symbolic;
920 8383622 : return *this;
921 : }
922 :
923 : binding_map::binding_pair
924 8475401 : binding_map::iterator::operator* ()
925 : {
926 8475401 : if (m_concrete != m_map.m_concrete.end ())
927 : {
928 8066737 : const bit_range &bits = m_concrete->first;
929 8066737 : const svalue *&sval = m_concrete->second;
930 8066737 : return binding_pair (m_map.m_store_mgr.get_concrete_binding (bits), sval);
931 : }
932 : else
933 : {
934 408664 : gcc_assert (m_symbolic != m_map.m_symbolic.end ());
935 408664 : const region *reg = m_symbolic->m_region;
936 408664 : const svalue *&sval = m_symbolic->m_sval;
937 408664 : return binding_pair (m_map.m_store_mgr.get_symbolic_binding (reg), sval);
938 : }
939 : }
940 :
941 : /* class binding_map. */
942 :
943 : // Construct an empty binding_map.
944 :
945 1642625 : binding_map::binding_map (store_manager &store_mgr)
946 1642625 : : m_store_mgr (store_mgr),
947 1642625 : m_concrete (),
948 1642625 : m_symbolic ()
949 : {
950 1642625 : }
951 :
952 : /* binding_map's copy ctor. */
953 :
954 32021711 : binding_map::binding_map (const binding_map &other)
955 32021711 : : m_store_mgr (other.m_store_mgr),
956 32021711 : m_concrete (other.m_concrete),
957 32021711 : m_symbolic (other.m_symbolic)
958 : {
959 32021711 : }
960 :
961 : /* binding_map's assignment operator. */
962 :
963 : binding_map&
964 4 : binding_map::operator= (const binding_map &other)
965 : {
966 4 : gcc_assert (&m_store_mgr == &other.m_store_mgr);
967 :
968 : /* For now, assume we only ever copy to an empty cluster. */
969 4 : gcc_assert (m_concrete.size () == 0);
970 4 : gcc_assert (m_symbolic.size () == 0);
971 :
972 4 : m_concrete = other.m_concrete;
973 4 : m_symbolic = other.m_symbolic;
974 :
975 4 : return *this;
976 : }
977 :
978 : /* binding_map's equality operator. */
979 :
980 : bool
981 3376946 : binding_map::operator== (const binding_map &other) const
982 : {
983 3376946 : if (m_concrete != other.m_concrete)
984 : return false;
985 3316335 : if (m_symbolic != other.m_symbolic)
986 : return false;
987 :
988 : return true;
989 : }
990 :
991 : /* Generate a hash value for this binding_map. */
992 :
993 : hashval_t
994 21978531 : binding_map::hash () const
995 : {
996 21978531 : hashval_t result = 0;
997 46817223 : for (auto iter : m_concrete)
998 : {
999 24838692 : result ^= iter.first.hash ();
1000 24838692 : inchash::hash hstate;
1001 24838692 : hstate.add_ptr (iter.second);
1002 24838692 : result ^= hstate.end ();
1003 : }
1004 23140483 : for (auto iter : m_symbolic)
1005 : {
1006 : /* Use a new hasher for each key to avoid depending on the ordering
1007 : of keys when accumulating the result. */
1008 1161952 : inchash::hash hstate;
1009 1161952 : hstate.add_ptr (iter.m_region);
1010 1161952 : hstate.add_ptr (iter.m_sval);
1011 1161952 : result ^= hstate.end ();
1012 : }
1013 21978531 : return result;
1014 : }
1015 :
1016 : const svalue *
1017 5296471 : binding_map::get (const binding_key *key) const
1018 : {
1019 5296471 : if (key->symbolic_p ())
1020 : {
1021 293015 : const ana::symbolic_binding &sym_key
1022 : = *static_cast <const ana::symbolic_binding *> (key);
1023 293015 : const region *reg = sym_key.get_region ();
1024 :
1025 345425 : for (auto iter : m_symbolic)
1026 : {
1027 214559 : if (iter.m_region == reg)
1028 5296471 : return iter.m_sval;
1029 : }
1030 : return nullptr;
1031 : }
1032 : else
1033 : {
1034 5003456 : const concrete_binding &conc_key
1035 : = *static_cast <const concrete_binding *> (key);
1036 5003456 : const bit_range &bits = conc_key.get_bit_range ();
1037 :
1038 5003456 : concrete_bindings_t::const_iterator iter (m_concrete.find (bits));
1039 5003456 : if (iter != m_concrete.end ())
1040 4556245 : return iter->second;
1041 : else
1042 : return nullptr;
1043 : }
1044 : }
1045 :
1046 : void
1047 2203166 : binding_map::put (const binding_key *key, const svalue *sval)
1048 : {
1049 2203166 : if (key->symbolic_p ())
1050 : {
1051 65917 : const ana::symbolic_binding &sym_key
1052 : = *static_cast <const ana::symbolic_binding *> (key);
1053 65917 : const region *reg = sym_key.get_region ();
1054 :
1055 65917 : m_symbolic.clear ();
1056 :
1057 65917 : m_symbolic.push_back ({reg, sval});
1058 : }
1059 : else
1060 : {
1061 2137249 : const concrete_binding &conc_key
1062 : = *static_cast <const concrete_binding *> (key);
1063 2137249 : const bit_range &bits = conc_key.get_bit_range ();
1064 :
1065 2137249 : concrete_bindings_t::iterator iter (m_concrete.find (bits));
1066 2137249 : if (iter != m_concrete.end ())
1067 3558 : (*iter).second = sval;
1068 : else
1069 2133691 : m_concrete.insert (bits, sval);
1070 : }
1071 2203166 : }
1072 :
1073 : void
1074 286 : binding_map::overwrite (iterator_t &pos, const svalue *v)
1075 : {
1076 286 : gcc_assert (&pos.m_map == this);
1077 286 : if (pos.m_symbolic != m_symbolic.end ())
1078 0 : (*(pos.m_symbolic)).m_sval = v;
1079 : else
1080 : {
1081 286 : gcc_assert (pos.m_concrete != m_concrete.end ());
1082 286 : (*(pos.m_concrete)).second = v;
1083 : }
1084 286 : }
1085 :
1086 : void
1087 306386 : binding_map::remove (const binding_key *key)
1088 : {
1089 306386 : if (key->symbolic_p ())
1090 9760 : m_symbolic.clear ();
1091 : else
1092 : {
1093 296626 : const concrete_binding &conc_key
1094 : = *static_cast <const concrete_binding *> (key);
1095 296626 : const bit_range &bits = conc_key.get_bit_range ();
1096 296626 : m_concrete.erase (bits);
1097 : }
1098 306386 : }
1099 :
1100 : binding_map::const_iterator_t
1101 11446545 : binding_map::begin () const
1102 : {
1103 11446545 : return binding_map::const_iterator_t (*this,
1104 : m_concrete.begin (),
1105 11446545 : m_symbolic.begin ());
1106 : }
1107 :
1108 : binding_map::const_iterator_t
1109 22435365 : binding_map::end () const
1110 : {
1111 22435365 : return binding_map::const_iterator_t (*this,
1112 : m_concrete.end (),
1113 22435365 : m_symbolic.end ());
1114 : }
1115 :
1116 : binding_map::iterator_t
1117 6913105 : binding_map::begin ()
1118 : {
1119 6913105 : return binding_map::iterator_t (*this,
1120 : m_concrete.begin (),
1121 6913105 : m_symbolic.begin ());
1122 : }
1123 :
1124 : binding_map::iterator_t
1125 14556374 : binding_map::end ()
1126 : {
1127 14556374 : return binding_map::iterator_t (*this,
1128 : m_concrete.end (),
1129 14556374 : m_symbolic.end ());
1130 : }
1131 :
1132 : size_t
1133 549702 : binding_map::elements () const
1134 : {
1135 549702 : return m_concrete.size () + m_symbolic.size ();
1136 : }
1137 :
1138 : /* Dump a representation of this binding_map to PP.
1139 : SIMPLE controls how values and regions are to be printed.
1140 : If MULTILINE, then split the dump over multiple lines and
1141 : use whitespace for readability, otherwise put all on one line. */
1142 :
1143 : void
1144 1731 : binding_map::dump_to_pp (pretty_printer *pp, bool simple,
1145 : bool multiline) const
1146 : {
1147 1731 : bool first = true;
1148 2862 : for (auto iter : *this)
1149 : {
1150 1131 : const binding_key *key = iter.m_key;
1151 1131 : const svalue *value = iter.m_sval;
1152 1131 : if (multiline)
1153 : {
1154 300 : pp_string (pp, " key: {");
1155 300 : key->dump_to_pp (pp, simple);
1156 300 : pp_string (pp, "}");
1157 300 : pp_newline (pp);
1158 300 : pp_string (pp, " value: ");
1159 300 : if (tree t = value->get_type ())
1160 300 : dump_quoted_tree (pp, t);
1161 300 : pp_string (pp, " {");
1162 300 : value->dump_to_pp (pp, simple);
1163 300 : pp_string (pp, "}");
1164 300 : pp_newline (pp);
1165 : }
1166 : else
1167 : {
1168 831 : if (first)
1169 : first = false;
1170 : else
1171 188 : pp_string (pp, ", ");
1172 831 : pp_string (pp, "binding key: {");
1173 831 : key->dump_to_pp (pp, simple);
1174 831 : pp_string (pp, "}, value: {");
1175 831 : value->dump_to_pp (pp, simple);
1176 831 : pp_string (pp, "}");
1177 : }
1178 : }
1179 1731 : }
1180 :
1181 : /* Dump a multiline representation of this binding_map to stderr. */
1182 :
1183 : DEBUG_FUNCTION void
1184 0 : binding_map::dump (bool simple) const
1185 : {
1186 0 : tree_dump_pretty_printer pp (stderr);
1187 0 : dump_to_pp (&pp, simple, true);
1188 0 : pp_newline (&pp);
1189 0 : }
1190 :
1191 : /* Assert that this object is valid. */
1192 :
1193 : void
1194 13369830 : binding_map::validate () const
1195 : {
1196 13369830 : const size_t num_concrete = m_concrete.size ();
1197 13369830 : const size_t num_symbolic = m_symbolic.size ();
1198 :
1199 : /* We shouldn't have more than one symbolic key per cluster
1200 : (or one would have clobbered the other). */
1201 13369830 : gcc_assert (num_symbolic < 2);
1202 : /* We can't have both concrete and symbolic keys. */
1203 13369830 : gcc_assert (num_concrete == 0 || num_symbolic == 0);
1204 :
1205 13369830 : m_concrete.validate ();
1206 13369830 : }
1207 :
1208 : /* Return a new json::object of the form
1209 : {KEY_DESC : SVALUE_DESC,
1210 : ...for the various key/value pairs in this binding_map}. */
1211 :
1212 : std::unique_ptr<json::object>
1213 0 : binding_map::to_json () const
1214 : {
1215 0 : auto map_obj = std::make_unique<json::object> ();
1216 :
1217 0 : for (auto iter : *this)
1218 : {
1219 0 : const svalue *value = iter.m_sval;
1220 0 : label_text key_desc = iter.m_key->get_desc ();
1221 0 : map_obj->set (key_desc.get (), value->to_json ());
1222 0 : }
1223 :
1224 0 : return map_obj;
1225 : }
1226 :
1227 : /* Add a child to PARENT_WIDGET expressing a binding between
1228 : KEY and SVAL. */
1229 :
1230 : static void
1231 0 : add_binding_to_tree_widget (text_art::tree_widget &parent_widget,
1232 : const text_art::dump_widget_info &dwi,
1233 : const binding_key *key,
1234 : const svalue *sval)
1235 : {
1236 0 : pretty_printer the_pp;
1237 0 : pretty_printer * const pp = &the_pp;
1238 0 : pp_format_decoder (pp) = default_tree_printer;
1239 0 : pp_show_color (pp) = true;
1240 0 : const bool simple = true;
1241 :
1242 0 : key->dump_to_pp (pp, simple);
1243 0 : pp_string (pp, ": ");
1244 0 : if (tree t = sval->get_type ())
1245 0 : dump_quoted_tree (pp, t);
1246 0 : pp_string (pp, " {");
1247 0 : sval->dump_to_pp (pp, simple);
1248 0 : pp_string (pp, "}");
1249 :
1250 0 : parent_widget.add_child (text_art::tree_widget::make (dwi, pp));
1251 0 : }
1252 :
1253 : void
1254 0 : binding_map::add_to_tree_widget (text_art::tree_widget &parent_widget,
1255 : const text_art::dump_widget_info &dwi) const
1256 : {
1257 0 : for (auto iter : *this)
1258 : {
1259 0 : const binding_key *key = iter.m_key;
1260 0 : const svalue *sval = iter.m_sval;
1261 0 : add_binding_to_tree_widget (parent_widget, dwi,
1262 : key, sval);
1263 : }
1264 0 : }
1265 :
1266 : /* Get the child region of PARENT_REG based upon INDEX within a
1267 : CONSTRUCTOR. */
1268 :
1269 : static const region *
1270 467 : get_subregion_within_ctor (const region *parent_reg, tree index,
1271 : region_model_manager *mgr)
1272 : {
1273 467 : switch (TREE_CODE (index))
1274 : {
1275 0 : default:
1276 0 : gcc_unreachable ();
1277 403 : case INTEGER_CST:
1278 403 : {
1279 403 : const svalue *index_sval
1280 403 : = mgr->get_or_create_constant_svalue (index);
1281 403 : return mgr->get_element_region (parent_reg,
1282 403 : TREE_TYPE (parent_reg->get_type ()),
1283 403 : index_sval);
1284 : }
1285 64 : break;
1286 64 : case FIELD_DECL:
1287 64 : return mgr->get_field_region (parent_reg, index);
1288 : }
1289 : }
1290 :
1291 : /* Get the child region of PARENT_REG based upon (INDEX, VALUE) within a
1292 : CONSTRUCTOR. */
1293 :
1294 : static const region *
1295 467 : get_subregion_within_ctor_for_ctor_pair (const region *parent_reg,
1296 : tree index,
1297 : tree value,
1298 : region_model_manager *mgr)
1299 : {
1300 467 : if (TREE_CODE (index) == INTEGER_CST
1301 403 : && TREE_CODE (value) == RAW_DATA_CST)
1302 : {
1303 : /* Special-case; see tree.def's description of CONSTRUCTOR.
1304 : We have RAW_DATA_LENGTH of bytes, starting at INDEX's start. */
1305 14 : const region *start_reg
1306 14 : = get_subregion_within_ctor (parent_reg, index, mgr);
1307 : /* Build a bit range, relative to PARENT_REG. */
1308 14 : region_offset start_offset = start_reg->get_offset (mgr);
1309 :
1310 14 : if (!start_offset.concrete_p ())
1311 : return nullptr;
1312 14 : bit_offset_t start_bit_offset = start_offset.get_bit_offset ();
1313 14 : int length = RAW_DATA_LENGTH (value);
1314 14 : bit_range bits (start_bit_offset, length * BITS_PER_UNIT);
1315 :
1316 14 : return mgr->get_bit_range (parent_reg, NULL_TREE, bits);
1317 : }
1318 :
1319 453 : return get_subregion_within_ctor (parent_reg, index, mgr);
1320 : }
1321 :
1322 : /* Get the svalue for VAL, a non-CONSTRUCTOR value within a CONSTRUCTOR. */
1323 :
1324 : static const svalue *
1325 425 : get_svalue_for_ctor_val (tree val, region_model_manager *mgr)
1326 : {
1327 : /* Reuse the get_rvalue logic from region_model. */
1328 425 : region_model m (mgr);
1329 425 : return m.get_rvalue (path_var (val, 0), nullptr);
1330 425 : }
1331 :
1332 : /* Bind values from CONSTRUCTOR to this map, relative to
1333 : PARENT_REG's relationship to its base region.
1334 : Return true if successful, false if there was a problem (e.g. due
1335 : to hitting a complexity limit). */
1336 :
1337 : bool
1338 164 : concrete_binding_map::apply_ctor_to_region (const region *parent_reg, tree ctor,
1339 : region_model_manager *mgr)
1340 : {
1341 164 : gcc_assert (parent_reg);
1342 164 : gcc_assert (TREE_CODE (ctor) == CONSTRUCTOR);
1343 :
1344 164 : unsigned ix;
1345 164 : tree index;
1346 164 : tree val;
1347 164 : tree parent_type = parent_reg->get_type ();
1348 164 : tree field;
1349 164 : if (TREE_CODE (parent_type) == RECORD_TYPE)
1350 55 : field = TYPE_FIELDS (parent_type);
1351 : else
1352 : field = NULL_TREE;
1353 630 : FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), ix, index, val)
1354 : {
1355 467 : if (!index)
1356 : {
1357 : /* If index is NULL, then iterate through the fields for
1358 : a RECORD_TYPE, or use an INTEGER_CST otherwise.
1359 : Compare with similar logic in output_constructor. */
1360 189 : if (field)
1361 : {
1362 0 : index = field;
1363 0 : field = DECL_CHAIN (field);
1364 : }
1365 : else
1366 189 : index = build_int_cst (integer_type_node, ix);
1367 : }
1368 278 : else if (TREE_CODE (index) == RANGE_EXPR)
1369 : {
1370 0 : tree min_index = TREE_OPERAND (index, 0);
1371 0 : tree max_index = TREE_OPERAND (index, 1);
1372 0 : if (min_index == max_index)
1373 : {
1374 0 : if (!apply_ctor_pair_to_child_region (parent_reg, mgr,
1375 : min_index, val))
1376 : return false;
1377 : }
1378 : else
1379 : {
1380 0 : if (!apply_ctor_val_to_range (parent_reg, mgr,
1381 : min_index, max_index, val))
1382 : return false;
1383 : }
1384 0 : continue;
1385 0 : }
1386 467 : if (!apply_ctor_pair_to_child_region (parent_reg, mgr, index, val))
1387 : return false;
1388 : }
1389 : return true;
1390 : }
1391 :
1392 : /* Bind the value VAL into the range of elements within PARENT_REF
1393 : from MIN_INDEX to MAX_INDEX (including endpoints).
1394 : For use in handling RANGE_EXPR within a CONSTRUCTOR.
1395 : Return true if successful, false if there was a problem (e.g. due
1396 : to hitting a complexity limit). */
1397 :
1398 : bool
1399 0 : concrete_binding_map::apply_ctor_val_to_range (const region *parent_reg,
1400 : region_model_manager *mgr,
1401 : tree min_index, tree max_index,
1402 : tree val)
1403 : {
1404 0 : gcc_assert (TREE_CODE (min_index) == INTEGER_CST);
1405 0 : gcc_assert (TREE_CODE (max_index) == INTEGER_CST);
1406 :
1407 : /* Generate a binding key for the range. */
1408 0 : const region *min_element
1409 0 : = get_subregion_within_ctor (parent_reg, min_index, mgr);
1410 0 : const region *max_element
1411 0 : = get_subregion_within_ctor (parent_reg, max_index, mgr);
1412 0 : region_offset min_offset = min_element->get_offset (mgr);
1413 0 : if (min_offset.symbolic_p ())
1414 : return false;
1415 0 : bit_offset_t start_bit_offset = min_offset.get_bit_offset ();
1416 0 : store_manager *smgr = mgr->get_store_manager ();
1417 0 : if (max_element->empty_p ())
1418 : return false;
1419 0 : const binding_key *max_element_key = binding_key::make (smgr, max_element);
1420 0 : if (max_element_key->symbolic_p ())
1421 : return false;
1422 0 : const concrete_binding *max_element_ckey
1423 0 : = max_element_key->dyn_cast_concrete_binding ();
1424 0 : bit_size_t range_size_in_bits
1425 0 : = max_element_ckey->get_next_bit_offset () - start_bit_offset;
1426 :
1427 : /* Get the value. */
1428 0 : if (TREE_CODE (val) == CONSTRUCTOR)
1429 : return false;
1430 0 : const svalue *sval = get_svalue_for_ctor_val (val, mgr);
1431 :
1432 : /* Bind the value to the range. */
1433 0 : const bit_range affected_bits (start_bit_offset, range_size_in_bits);
1434 0 : insert (affected_bits, sval);
1435 0 : return true;
1436 : }
1437 :
1438 : /* Bind the value VAL into INDEX within PARENT_REF.
1439 : For use in handling a pair of entries within a CONSTRUCTOR.
1440 : Return true if successful, false if there was a problem (e.g. due
1441 : to hitting a complexity limit). */
1442 :
1443 : bool
1444 467 : concrete_binding_map::apply_ctor_pair_to_child_region (const region *parent_reg,
1445 : region_model_manager *mgr,
1446 : tree index, tree val)
1447 : {
1448 467 : const region *child_reg
1449 467 : = get_subregion_within_ctor_for_ctor_pair (parent_reg, index, val, mgr);
1450 467 : if (!child_reg)
1451 : return false;
1452 467 : if (TREE_CODE (val) == CONSTRUCTOR)
1453 42 : return apply_ctor_to_region (child_reg, val, mgr);
1454 : else
1455 : {
1456 425 : const svalue *sval = get_svalue_for_ctor_val (val, mgr);
1457 425 : if (child_reg->empty_p ())
1458 : return false;
1459 425 : const binding_key *k
1460 425 : = binding_key::make (mgr->get_store_manager (), child_reg);
1461 : /* Handle the case where we have an unknown size for child_reg
1462 : (e.g. due to it being a trailing field with incomplete array
1463 : type. */
1464 425 : if (!k->concrete_p ())
1465 : {
1466 : /* Assume that sval has a well-defined size for this case. */
1467 5 : tree sval_type = sval->get_type ();
1468 5 : gcc_assert (sval_type);
1469 5 : HOST_WIDE_INT sval_byte_size = int_size_in_bytes (sval_type);
1470 5 : gcc_assert (sval_byte_size != -1);
1471 5 : bit_size_t sval_bit_size = sval_byte_size * BITS_PER_UNIT;
1472 : /* Get offset of child relative to base region. */
1473 5 : region_offset child_base_offset = child_reg->get_offset (mgr);
1474 5 : if (child_base_offset.symbolic_p ())
1475 1 : return false;
1476 : /* Convert to an offset relative to the parent region. */
1477 4 : region_offset parent_base_offset = parent_reg->get_offset (mgr);
1478 4 : gcc_assert (!parent_base_offset.symbolic_p ());
1479 4 : bit_offset_t child_parent_offset
1480 4 : = (child_base_offset.get_bit_offset ()
1481 4 : - parent_base_offset.get_bit_offset ());
1482 : /* Create a concrete key for the child within the parent. */
1483 4 : k = mgr->get_store_manager ()->get_concrete_binding
1484 4 : (child_parent_offset, sval_bit_size);
1485 : }
1486 424 : gcc_assert (k->concrete_p ());
1487 424 : auto conc_key = as_a <const concrete_binding *> (k);
1488 424 : insert (conc_key->get_bit_range (), sval);
1489 424 : return true;
1490 : }
1491 : }
1492 :
1493 : /* Populate OUT with all bindings within this map that overlap KEY. */
1494 :
1495 : void
1496 35320 : binding_map::get_overlapping_bindings (const binding_key *key,
1497 : auto_vec<const binding_key *> *out)
1498 : {
1499 313655 : for (auto iter : *this)
1500 : {
1501 278335 : const binding_key *iter_key = iter.m_key;
1502 556670 : if (const concrete_binding *ckey
1503 278335 : = key->dyn_cast_concrete_binding ())
1504 : {
1505 551468 : if (const concrete_binding *iter_ckey
1506 275734 : = iter_key->dyn_cast_concrete_binding ())
1507 : {
1508 275225 : if (ckey->overlaps_p (*iter_ckey))
1509 30110 : out->safe_push (iter_key);
1510 : }
1511 : else
1512 : {
1513 : /* Assume overlap. */
1514 509 : out->safe_push (iter_key);
1515 : }
1516 : }
1517 : else
1518 : {
1519 : /* Assume overlap. */
1520 2601 : out->safe_push (iter_key);
1521 : }
1522 : }
1523 35320 : }
1524 :
1525 : /* Remove, truncate, and/or split any bindings within this map that
1526 : overlap DROP_KEY.
1527 :
1528 : For example, if we have:
1529 :
1530 : +------------------------------------+
1531 : | old binding |
1532 : +------------------------------------+
1533 :
1534 : which is to be overwritten with:
1535 :
1536 : .......+----------------------+.......
1537 : .......| new binding |.......
1538 : .......+----------------------+.......
1539 :
1540 : this function "cuts a hole" out of the old binding:
1541 :
1542 : +------+......................+------+
1543 : |prefix| hole for new binding |suffix|
1544 : +------+......................+------+
1545 :
1546 : into which the new binding can be added without
1547 : overlapping the prefix or suffix.
1548 :
1549 : The prefix and suffix (if added) will be bound to the pertinent
1550 : parts of the value of the old binding.
1551 :
1552 : For example, given:
1553 : struct s5
1554 : {
1555 : char arr[8];
1556 : };
1557 : void test_5 (struct s5 *p)
1558 : {
1559 : struct s5 f = *p;
1560 : f.arr[3] = 42;
1561 : }
1562 : then after the "f = *p;" we have:
1563 : cluster for: f: INIT_VAL((*INIT_VAL(p_33(D))))
1564 : and at the "f.arr[3] = 42;" we remove the bindings overlapping
1565 : "f.arr[3]", replacing it with a prefix (bytes 0-2) and suffix (bytes 4-7)
1566 : giving:
1567 : cluster for: f
1568 : key: {bytes 0-2}
1569 : value: {BITS_WITHIN(bytes 0-2, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
1570 : key: {bytes 4-7}
1571 : value: {BITS_WITHIN(bytes 4-7, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
1572 : punching a hole into which the new value can be written at byte 3:
1573 : cluster for: f
1574 : key: {bytes 0-2}
1575 : value: {BITS_WITHIN(bytes 0-2, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
1576 : key: {byte 3}
1577 : value: 'char' {(char)42}
1578 : key: {bytes 4-7}
1579 : value: {BITS_WITHIN(bytes 4-7, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
1580 :
1581 : If UNCERTAINTY is non-NULL, use it to record any svalues that
1582 : were removed, as being maybe-bound.
1583 :
1584 : If MAYBE_LIVE_VALUES is non-NULL, then use it to record any svalues that
1585 : were removed as being maybe-live.
1586 :
1587 : If ALWAYS_OVERLAP, then assume that DROP_KEY can overlap anything
1588 : in the map, due to one or both of the underlying clusters being
1589 : symbolic (but not the same symbolic region). Hence even if DROP_KEY is a
1590 : concrete binding it could actually be referring to the same memory as
1591 : distinct concrete bindings in the map. Remove all bindings, but
1592 : register any svalues with *UNCERTAINTY. */
1593 :
1594 : void
1595 82539 : binding_map::remove_overlapping_bindings (store_manager *mgr,
1596 : const binding_key *drop_key,
1597 : uncertainty_t *uncertainty,
1598 : svalue_set *maybe_live_values,
1599 : bool always_overlap)
1600 : {
1601 : /* Get the bindings of interest within this map. */
1602 82539 : auto_vec<const binding_key *> bindings;
1603 82539 : if (always_overlap)
1604 95066 : for (auto iter : *this)
1605 47847 : bindings.safe_push (iter.m_key); /* Add all bindings. */
1606 : else
1607 : /* Just add overlapping bindings. */
1608 35320 : get_overlapping_bindings (drop_key, &bindings);
1609 :
1610 : unsigned i;
1611 : const binding_key *iter_binding;
1612 228007 : FOR_EACH_VEC_ELT (bindings, i, iter_binding)
1613 : {
1614 : /* Record any svalues that were removed to *UNCERTAINTY as being
1615 : maybe-bound, provided at least some part of the binding is symbolic.
1616 :
1617 : Specifically, if at least one of the bindings is symbolic, or we
1618 : have ALWAYS_OVERLAP for the case where we have possibly aliasing
1619 : regions, then we don't know that the svalue has been overwritten,
1620 : and should record that to *UNCERTAINTY.
1621 :
1622 : However, if we have concrete keys accessing within the same symbolic
1623 : region, then we *know* that the symbolic region has been overwritten,
1624 : so we don't record it to *UNCERTAINTY, as this could be a genuine
1625 : leak. */
1626 81067 : const svalue *old_sval = get (iter_binding);
1627 81067 : if (uncertainty
1628 104196 : && (drop_key->symbolic_p ()
1629 20914 : || iter_binding->symbolic_p ()
1630 18522 : || always_overlap))
1631 19334 : uncertainty->on_maybe_bound_sval (old_sval);
1632 :
1633 : /* Record any svalues that were removed to *MAYBE_LIVE_VALUES as being
1634 : maybe-live. */
1635 81067 : if (maybe_live_values)
1636 47873 : maybe_live_values->add (old_sval);
1637 :
1638 : /* Begin by removing the old binding. */
1639 81067 : remove (iter_binding);
1640 :
1641 : /* Don't attempt to handle prefixes/suffixes for the
1642 : "always_overlap" case; everything's being removed. */
1643 81067 : if (always_overlap)
1644 47847 : continue;
1645 :
1646 : /* Now potentially add the prefix and suffix. */
1647 66440 : if (const concrete_binding *drop_ckey
1648 33220 : = drop_key->dyn_cast_concrete_binding ())
1649 61238 : if (const concrete_binding *iter_ckey
1650 30619 : = iter_binding->dyn_cast_concrete_binding ())
1651 : {
1652 30110 : gcc_assert (drop_ckey->overlaps_p (*iter_ckey));
1653 :
1654 30110 : const bit_range &drop_bits = drop_ckey->get_bit_range ();
1655 30110 : const bit_range &iter_bits = iter_ckey->get_bit_range ();
1656 30110 : gcc_assert (old_sval);
1657 30110 : m_concrete.remove_overlapping_binding (mgr, drop_bits, iter_bits,
1658 : *old_sval);
1659 : }
1660 : }
1661 82539 : }
1662 :
1663 : /* class binding_cluster. */
1664 :
1665 1642617 : binding_cluster::binding_cluster (store_manager &store_mgr,
1666 1642617 : const region *base_region)
1667 1642617 : : m_base_region (base_region), m_map (store_mgr),
1668 1642617 : m_escaped (false), m_touched (false)
1669 : {
1670 1642617 : }
1671 :
1672 : /* binding_cluster's copy ctor. */
1673 :
1674 32021711 : binding_cluster::binding_cluster (const binding_cluster &other)
1675 32021711 : : m_base_region (other.m_base_region), m_map (other.m_map),
1676 32021711 : m_escaped (other.m_escaped), m_touched (other.m_touched)
1677 : {
1678 32021711 : }
1679 :
1680 : /* binding_cluster's assignment operator. */
1681 :
1682 : binding_cluster&
1683 0 : binding_cluster::operator= (const binding_cluster &other)
1684 : {
1685 0 : gcc_assert (m_base_region == other.m_base_region);
1686 0 : m_map = other.m_map;
1687 0 : m_escaped = other.m_escaped;
1688 0 : m_touched = other.m_touched;
1689 0 : return *this;
1690 : }
1691 :
1692 : /* binding_cluster's equality operator. */
1693 :
1694 : bool
1695 3376942 : binding_cluster::operator== (const binding_cluster &other) const
1696 : {
1697 3376942 : if (m_map != other.m_map)
1698 : return false;
1699 :
1700 3314000 : if (m_base_region != other.m_base_region)
1701 : return false;
1702 :
1703 3314000 : if (m_escaped != other.m_escaped)
1704 : return false;
1705 :
1706 3313334 : if (m_touched != other.m_touched)
1707 : return false;
1708 :
1709 3310667 : gcc_checking_assert (hash () == other.hash ());
1710 :
1711 : return true;
1712 : }
1713 :
1714 : /* Generate a hash value for this binding_cluster. */
1715 :
1716 : hashval_t
1717 21978531 : binding_cluster::hash () const
1718 : {
1719 21978531 : return m_map.hash ();
1720 : }
1721 :
1722 : /* Return true if this binding_cluster is symbolic
1723 : i.e. its base region is symbolic. */
1724 :
1725 : bool
1726 9417926 : binding_cluster::symbolic_p () const
1727 : {
1728 9417926 : return m_base_region->get_kind () == RK_SYMBOLIC;
1729 : }
1730 :
1731 : /* Dump a representation of this binding_cluster to PP.
1732 : SIMPLE controls how values and regions are to be printed.
1733 : If MULTILINE, then split the dump over multiple lines and
1734 : use whitespace for readability, otherwise put all on one line. */
1735 :
1736 : void
1737 1731 : binding_cluster::dump_to_pp (pretty_printer *pp, bool simple,
1738 : bool multiline) const
1739 : {
1740 1731 : if (m_escaped)
1741 : {
1742 1092 : if (multiline)
1743 : {
1744 904 : pp_string (pp, " ESCAPED");
1745 904 : pp_newline (pp);
1746 : }
1747 : else
1748 188 : pp_string (pp, "(ESCAPED)");
1749 : }
1750 1731 : if (m_touched)
1751 : {
1752 272 : if (multiline)
1753 : {
1754 84 : pp_string (pp, " TOUCHED");
1755 84 : pp_newline (pp);
1756 : }
1757 : else
1758 188 : pp_string (pp, "(TOUCHED)");
1759 : }
1760 :
1761 1731 : m_map.dump_to_pp (pp, simple, multiline);
1762 1731 : }
1763 :
1764 : /* Dump a multiline representation of this binding_cluster to stderr. */
1765 :
1766 : DEBUG_FUNCTION void
1767 0 : binding_cluster::dump (bool simple) const
1768 : {
1769 0 : tree_dump_pretty_printer pp (stderr);
1770 0 : pp_string (&pp, " cluster for: ");
1771 0 : m_base_region->dump_to_pp (&pp, simple);
1772 0 : pp_string (&pp, ": ");
1773 0 : pp_newline (&pp);
1774 0 : dump_to_pp (&pp, simple, true);
1775 0 : pp_newline (&pp);
1776 0 : }
1777 :
1778 : /* Assert that this object is valid. */
1779 :
1780 : void
1781 13369830 : binding_cluster::validate () const
1782 : {
1783 13369830 : m_map.validate ();
1784 13369830 : }
1785 :
1786 : /* Return a new json::object of the form
1787 : {"escaped": true/false,
1788 : "touched": true/false,
1789 : "map" : object for the binding_map. */
1790 :
1791 : std::unique_ptr<json::object>
1792 0 : binding_cluster::to_json () const
1793 : {
1794 0 : auto cluster_obj = std::make_unique<json::object> ();
1795 :
1796 0 : cluster_obj->set_bool ("escaped", m_escaped);
1797 0 : cluster_obj->set_bool ("touched", m_touched);
1798 0 : cluster_obj->set ("map", m_map.to_json ());
1799 :
1800 0 : return cluster_obj;
1801 : }
1802 :
1803 : std::unique_ptr<text_art::tree_widget>
1804 0 : binding_cluster::make_dump_widget (const text_art::dump_widget_info &dwi,
1805 : store_manager *mgr) const
1806 : {
1807 0 : pretty_printer the_pp;
1808 0 : pretty_printer * const pp = &the_pp;
1809 0 : pp_format_decoder (pp) = default_tree_printer;
1810 0 : pp_show_color (pp) = true;
1811 0 : const bool simple = true;
1812 :
1813 0 : m_base_region->dump_to_pp (pp, simple);
1814 0 : pp_string (pp, ": ");
1815 :
1816 0 : if (const svalue *sval = maybe_get_simple_value (mgr))
1817 : {
1818 : /* Special-case to simplify dumps for the common case where
1819 : we just have one value directly bound to the whole of a
1820 : region. */
1821 0 : sval->dump_to_pp (pp, simple);
1822 0 : if (escaped_p ())
1823 0 : pp_string (pp, " (ESCAPED)");
1824 0 : if (touched_p ())
1825 0 : pp_string (pp, " (TOUCHED)");
1826 :
1827 0 : return text_art::tree_widget::make (dwi, pp);
1828 : }
1829 : else
1830 : {
1831 0 : if (escaped_p ())
1832 0 : pp_string (pp, " (ESCAPED)");
1833 0 : if (touched_p ())
1834 0 : pp_string (pp, " (TOUCHED)");
1835 :
1836 0 : std::unique_ptr<text_art::tree_widget> cluster_widget
1837 0 : (text_art::tree_widget::make (dwi, pp));
1838 :
1839 0 : m_map.add_to_tree_widget (*cluster_widget, dwi);
1840 :
1841 0 : return cluster_widget;
1842 0 : }
1843 0 : }
1844 :
1845 : /* Add a binding of SVAL of kind KIND to REG, unpacking SVAL if it is a
1846 : compound_sval. */
1847 :
1848 : void
1849 461113 : binding_cluster::bind (store_manager *mgr,
1850 : const region *reg, const svalue *sval)
1851 : {
1852 922226 : if (const compound_svalue *compound_sval
1853 461113 : = sval->dyn_cast_compound_svalue ())
1854 : {
1855 941 : bind_compound_sval (mgr, reg, compound_sval);
1856 941 : return;
1857 : }
1858 :
1859 460172 : if (reg->empty_p ())
1860 : return;
1861 460172 : const binding_key *binding = binding_key::make (mgr, reg);
1862 460172 : bind_key (binding, sval);
1863 : }
1864 :
1865 : /* Bind SVAL to KEY.
1866 : Unpacking of compound_svalues should already have been done by the
1867 : time this is called. */
1868 :
1869 : void
1870 463067 : binding_cluster::bind_key (const binding_key *key, const svalue *sval)
1871 : {
1872 463067 : gcc_assert (sval->get_kind () != SK_COMPOUND);
1873 :
1874 463067 : m_map.put (key, sval);
1875 463067 : if (key->symbolic_p ())
1876 25042 : m_touched = true;
1877 463067 : }
1878 :
1879 : /* Subroutine of binding_cluster::bind.
1880 : Unpack compound_svals when binding them, so that we bind them
1881 : element-wise. */
1882 :
1883 : void
1884 941 : binding_cluster::bind_compound_sval (store_manager *mgr,
1885 : const region *reg,
1886 : const compound_svalue *compound_sval)
1887 : {
1888 941 : region_offset reg_offset
1889 941 : = reg->get_offset (mgr->get_svalue_manager ());
1890 941 : if (reg_offset.symbolic_p ())
1891 : {
1892 4 : m_touched = true;
1893 4 : clobber_region (mgr, reg);
1894 4 : return;
1895 : }
1896 :
1897 3432 : for (auto iter : *compound_sval)
1898 : {
1899 2495 : const bit_range &iter_bits = iter.first;
1900 2495 : const svalue *iter_sval = iter.second;
1901 :
1902 2495 : bit_offset_t effective_start
1903 2495 : = (iter_bits.get_start_bit_offset ()
1904 2495 : + reg_offset.get_bit_offset ());
1905 2495 : const bit_range affected_bits (effective_start,
1906 2495 : iter_bits.m_size_in_bits);
1907 2495 : bind_key (mgr->get_concrete_binding (affected_bits), iter_sval);
1908 : }
1909 : }
1910 :
1911 : /* Remove all bindings overlapping REG within this cluster. */
1912 :
1913 : void
1914 6577 : binding_cluster::clobber_region (store_manager *mgr, const region *reg)
1915 : {
1916 6577 : remove_overlapping_bindings (mgr, reg, nullptr, nullptr);
1917 6577 : }
1918 :
1919 : /* Remove any bindings for REG within this cluster. */
1920 :
1921 : void
1922 225319 : binding_cluster::purge_region (store_manager *mgr, const region *reg)
1923 : {
1924 225319 : gcc_assert (reg->get_kind () == RK_DECL);
1925 225319 : if (reg->empty_p ())
1926 : return;
1927 225319 : const binding_key *binding
1928 225319 : = binding_key::make (mgr, const_cast<region *> (reg));
1929 225319 : m_map.remove (binding);
1930 : }
1931 :
1932 : /* Clobber REG and fill it with repeated copies of SVAL. */
1933 :
1934 : void
1935 1598 : binding_cluster::fill_region (store_manager *mgr,
1936 : const region *reg,
1937 : const svalue *sval)
1938 : {
1939 1598 : clobber_region (mgr, reg);
1940 :
1941 1598 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
1942 1598 : const svalue *byte_size_sval = reg->get_byte_size_sval (sval_mgr);
1943 1598 : const svalue *fill_sval
1944 1598 : = sval_mgr->get_or_create_repeated_svalue (reg->get_type (),
1945 : byte_size_sval, sval);
1946 1598 : bind (mgr, reg, fill_sval);
1947 1598 : }
1948 :
1949 : /* Clobber REG within this cluster and fill it with zeroes. */
1950 :
1951 : void
1952 33 : binding_cluster::zero_fill_region (store_manager *mgr, const region *reg)
1953 : {
1954 33 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
1955 33 : const svalue *zero_sval = sval_mgr->get_or_create_int_cst (char_type_node, 0);
1956 33 : fill_region (mgr, reg, zero_sval);
1957 33 : }
1958 :
1959 : /* Mark REG_TO_BIND within this cluster as being unknown.
1960 :
1961 : Remove any bindings overlapping REG_FOR_OVERLAP.
1962 : If UNCERTAINTY is non-NULL, use it to record any svalues that
1963 : had bindings to them removed, as being maybe-bound.
1964 : If MAYBE_LIVE_VALUES is non-NULL, use it to record any svalues that
1965 : had bindings to them removed, as being maybe-live.
1966 :
1967 : REG_TO_BIND and REG_FOR_OVERLAP are the same for
1968 : store::mark_region_as_unknown, but are different in
1969 : store::set_value's alias handling, for handling the case where
1970 : we have a write to a symbolic REG_FOR_OVERLAP. */
1971 :
1972 : void
1973 47528 : binding_cluster::mark_region_as_unknown (store_manager *mgr,
1974 : const region *reg_to_bind,
1975 : const region *reg_for_overlap,
1976 : uncertainty_t *uncertainty,
1977 : svalue_set *maybe_live_values)
1978 : {
1979 47528 : if (reg_to_bind->empty_p ())
1980 : return;
1981 :
1982 47528 : remove_overlapping_bindings (mgr, reg_for_overlap, uncertainty,
1983 : maybe_live_values);
1984 :
1985 : /* Add a default binding to "unknown". */
1986 47528 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
1987 47528 : const svalue *sval
1988 47528 : = sval_mgr->get_or_create_unknown_svalue (reg_to_bind->get_type ());
1989 47528 : bind (mgr, reg_to_bind, sval);
1990 : }
1991 :
1992 : /* Purge state involving SVAL. */
1993 :
1994 : void
1995 405535 : binding_cluster::purge_state_involving (const svalue *sval,
1996 : region_model_manager *sval_mgr)
1997 : {
1998 405535 : auto_vec<const binding_key *> to_remove;
1999 405535 : auto_vec<std::pair<const binding_key *, tree> > to_make_unknown;
2000 813991 : for (auto iter : m_map)
2001 : {
2002 408456 : const binding_key *iter_key = iter.m_key;
2003 816912 : if (const symbolic_binding *symbolic_key
2004 408456 : = iter_key->dyn_cast_symbolic_binding ())
2005 : {
2006 32861 : const region *reg = symbolic_key->get_region ();
2007 32861 : if (reg->involves_p (sval))
2008 0 : to_remove.safe_push (iter_key);
2009 : }
2010 408456 : const svalue *iter_sval = iter.m_sval;
2011 408456 : if (iter_sval->involves_p (sval))
2012 3185 : to_make_unknown.safe_push (std::make_pair(iter_key,
2013 3185 : iter_sval->get_type ()));
2014 : }
2015 405535 : for (auto iter : to_remove)
2016 : {
2017 0 : m_map.remove (iter);
2018 0 : m_touched = true;
2019 : }
2020 415090 : for (auto iter : to_make_unknown)
2021 : {
2022 3185 : const svalue *new_sval
2023 3185 : = sval_mgr->get_or_create_unknown_svalue (iter.second);
2024 3185 : m_map.put (iter.first, new_sval);
2025 : }
2026 405535 : }
2027 :
2028 : /* Get any SVAL bound to REG within this cluster via kind KIND,
2029 : without checking parent regions of REG. */
2030 :
2031 : const svalue *
2032 1473014 : binding_cluster::get_binding (store_manager *mgr,
2033 : const region *reg) const
2034 : {
2035 1473014 : if (reg->empty_p ())
2036 : return nullptr;
2037 1473014 : const binding_key *reg_binding = binding_key::make (mgr, reg);
2038 1473014 : const svalue *sval = m_map.get (reg_binding);
2039 1473014 : if (sval)
2040 : {
2041 : /* If we have a struct with a single field, then the binding of
2042 : the field will equal that of the struct, and looking up e.g.
2043 : PARENT_REG.field within:
2044 : cluster for PARENT_REG: INIT_VAL(OTHER_REG)
2045 : will erroneously return INIT_VAL(OTHER_REG), rather than
2046 : SUB_VALUE(INIT_VAL(OTHER_REG), FIELD) == INIT_VAL(OTHER_REG.FIELD).
2047 : Fix this issue by iterating upwards whilst the bindings are equal,
2048 : expressing the lookups as subvalues.
2049 : We have to gather a list of subregion accesses, then walk it
2050 : in reverse to get the subvalues. */
2051 1197569 : auto_vec<const region *> regions;
2052 1208511 : while (const region *parent_reg = reg->get_parent_region ())
2053 : {
2054 1208511 : const binding_key *parent_reg_binding
2055 1208511 : = binding_key::make (mgr, parent_reg);
2056 1208511 : if (parent_reg_binding == reg_binding
2057 14084 : && sval->get_type ()
2058 13268 : && reg->get_type ()
2059 1221779 : && sval->get_type () != reg->get_type ())
2060 : {
2061 10942 : regions.safe_push (reg);
2062 10942 : reg = parent_reg;
2063 : }
2064 : else
2065 : break;
2066 10942 : }
2067 1197569 : if (sval->get_type ()
2068 1187417 : && reg->get_type ()
2069 2383941 : && sval->get_type () == reg->get_type ())
2070 : {
2071 966736 : unsigned i;
2072 966736 : const region *iter_reg;
2073 1224384 : FOR_EACH_VEC_ELT_REVERSE (regions, i, iter_reg)
2074 : {
2075 9123 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
2076 9123 : sval = rmm_mgr->get_or_create_sub_svalue (iter_reg->get_type (),
2077 : sval, iter_reg);
2078 : }
2079 : }
2080 1197569 : }
2081 : return sval;
2082 : }
2083 :
2084 : /* Get any SVAL bound to REG within this cluster,
2085 : either directly for REG, or recursively checking for bindings within
2086 : parent regions and extracting subvalues if need be. */
2087 :
2088 : const svalue *
2089 1473014 : binding_cluster::get_binding_recursive (store_manager *mgr,
2090 : const region *reg) const
2091 : {
2092 1473014 : if (const svalue *sval = get_binding (mgr, reg))
2093 : return sval;
2094 275445 : if (reg != m_base_region)
2095 169361 : if (const region *parent_reg = reg->get_parent_region ())
2096 338722 : if (const svalue *parent_sval
2097 169361 : = get_binding_recursive (mgr, parent_reg))
2098 : {
2099 : /* Extract child svalue from parent svalue. */
2100 56662 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
2101 56662 : return rmm_mgr->get_or_create_sub_svalue (reg->get_type (),
2102 56662 : parent_sval, reg);
2103 : }
2104 : return nullptr;
2105 : }
2106 :
2107 : /* Get any value bound for REG within this cluster. */
2108 :
2109 : const svalue *
2110 1303653 : binding_cluster::get_any_binding (store_manager *mgr,
2111 : const region *reg) const
2112 : {
2113 : /* Look for a direct binding. */
2114 2607306 : if (const svalue *direct_sval
2115 1303653 : = get_binding_recursive (mgr, reg))
2116 : return direct_sval;
2117 :
2118 : /* If we had a write to a cluster of unknown size, we might
2119 : have a self-binding of the whole base region with an svalue,
2120 : where the base region is symbolic.
2121 : Handle such cases by returning sub_svalue instances. */
2122 106084 : if (const svalue *cluster_sval = maybe_get_simple_value (mgr))
2123 : {
2124 : /* Extract child svalue from parent svalue. */
2125 0 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
2126 0 : return rmm_mgr->get_or_create_sub_svalue (reg->get_type (),
2127 0 : cluster_sval, reg);
2128 : }
2129 :
2130 : /* If this cluster has been touched by a symbolic write, then the content
2131 : of any subregion not currently specifically bound is "UNKNOWN". */
2132 106084 : if (m_touched)
2133 : {
2134 7236 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
2135 7236 : return rmm_mgr->get_or_create_unknown_svalue (reg->get_type ());
2136 : }
2137 :
2138 : /* Alternatively, if this is a symbolic read and the cluster has any bindings,
2139 : then we don't know if we're reading those values or not, so the result
2140 : is also "UNKNOWN". */
2141 98848 : if (reg->get_offset (mgr->get_svalue_manager ()).symbolic_p ()
2142 98848 : && m_map.elements () > 0)
2143 : {
2144 440 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
2145 440 : return rmm_mgr->get_or_create_unknown_svalue (reg->get_type ());
2146 : }
2147 :
2148 98408 : if (const svalue *compound_sval = maybe_get_compound_binding (mgr, reg))
2149 : return compound_sval;
2150 :
2151 : /* Otherwise, the initial value, or uninitialized. */
2152 : return nullptr;
2153 : }
2154 :
2155 : /* Attempt to get a compound_svalue for the bindings within the cluster
2156 : affecting REG (which could be the base region itself).
2157 :
2158 : Create a compound_svalue with the subset of bindings the affect REG,
2159 : offsetting them so that the offsets are relative to the start of REG
2160 : within the cluster.
2161 :
2162 : For example, REG could be one element within an array of structs.
2163 :
2164 : Return the resulting compound_svalue, or nullptr if there's a problem. */
2165 :
2166 : const svalue *
2167 98408 : binding_cluster::maybe_get_compound_binding (store_manager *mgr,
2168 : const region *reg) const
2169 : {
2170 98408 : region_offset cluster_offset
2171 98408 : = m_base_region->get_offset (mgr->get_svalue_manager ());
2172 98408 : if (cluster_offset.symbolic_p ())
2173 : return nullptr;
2174 98408 : region_offset reg_offset = reg->get_offset (mgr->get_svalue_manager ());
2175 98408 : if (reg_offset.symbolic_p ())
2176 : return nullptr;
2177 :
2178 78888 : if (reg->empty_p ())
2179 : return nullptr;
2180 :
2181 78888 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
2182 :
2183 : /* We will a build the result map in two parts:
2184 : (a) result_map, holding the concrete keys from this cluster,
2185 :
2186 : (b) default_map, holding the initial values for the region
2187 : (e.g. uninitialized, initializer values, or zero), unless this
2188 : cluster has been touched.
2189 :
2190 : We will populate (a), and as we do, clobber (b), trimming and
2191 : splitting its bindings as necessary.
2192 : Finally, we will merge (b) into (a), giving a concrete map
2193 : that merges both the initial values and the bound values from
2194 : the binding_cluster.
2195 : Doing it this way reduces N for the O(N^2) intersection-finding,
2196 : perhaps we should have a spatial-organized data structure for
2197 : concrete keys, though. */
2198 :
2199 78888 : concrete_binding_map result_map;
2200 78888 : concrete_binding_map default_map;
2201 :
2202 : /* Set up default values in default_map. */
2203 78888 : const svalue *default_sval;
2204 78888 : if (m_touched)
2205 0 : default_sval = sval_mgr->get_or_create_unknown_svalue (reg->get_type ());
2206 : else
2207 78888 : default_sval = sval_mgr->get_or_create_initial_value (reg);
2208 78888 : const binding_key *default_key = binding_key::make (mgr, reg);
2209 :
2210 : /* Express the bit-range of the default key for REG relative to REG,
2211 : rather than to the base region. */
2212 78888 : const concrete_binding *concrete_default_key
2213 78888 : = default_key->dyn_cast_concrete_binding ();
2214 78888 : if (!concrete_default_key)
2215 : return nullptr;
2216 78011 : const bit_range default_key_relative_to_reg
2217 78011 : (0, concrete_default_key->get_size_in_bits ());
2218 :
2219 78011 : default_map.insert (default_key_relative_to_reg, default_sval);
2220 :
2221 154441 : for (auto iter : m_map)
2222 : {
2223 83816 : const binding_key *key = iter.m_key;
2224 83816 : const svalue *sval = iter.m_sval;
2225 :
2226 167632 : if (const concrete_binding *concrete_key
2227 83816 : = key->dyn_cast_concrete_binding ())
2228 : {
2229 83816 : const bit_range &bound_range = concrete_key->get_bit_range ();
2230 :
2231 83816 : bit_size_t reg_bit_size;
2232 83816 : if (!reg->get_bit_size (®_bit_size))
2233 7386 : return nullptr;
2234 :
2235 83816 : bit_range reg_range (reg_offset.get_bit_offset (),
2236 83816 : reg_bit_size);
2237 :
2238 : /* Skip bindings that are outside the bit range of REG. */
2239 83816 : if (!bound_range.intersects_p (reg_range))
2240 67451 : continue;
2241 :
2242 : /* We shouldn't have an exact match; that should have been
2243 : handled already. */
2244 16365 : gcc_assert (!(reg_range == bound_range));
2245 :
2246 16365 : bit_range subrange (0, 0);
2247 16365 : if (reg_range.contains_p (bound_range, &subrange))
2248 : {
2249 : /* We have a bound range fully within REG.
2250 : Add it to result_map, offsetting accordingly. */
2251 8903 : result_map.insert (subrange, sval);
2252 :
2253 : /* Clobber default_map, removing/trimming/spliting where
2254 : it overlaps with offset_concrete_key. */
2255 8903 : default_map.remove_overlapping_bindings (mgr, subrange);
2256 : }
2257 7462 : else if (bound_range.contains_p (reg_range, &subrange))
2258 : {
2259 : /* REG is fully within the bound range, but
2260 : is not equal to it; we're extracting a subvalue. */
2261 7386 : return sval->extract_bit_range (reg->get_type (),
2262 : subrange,
2263 7386 : mgr->get_svalue_manager ());
2264 : }
2265 : else
2266 : {
2267 : /* REG and the bound range partially overlap. */
2268 76 : bit_range reg_subrange (0, 0);
2269 76 : bit_range bound_subrange (0, 0);
2270 76 : reg_range.intersects_p (bound_range,
2271 : ®_subrange, &bound_subrange);
2272 :
2273 : /* Get the bits from the bound value for the bits at the
2274 : intersection (relative to the bound value). */
2275 76 : const svalue *overlap_sval
2276 76 : = sval->extract_bit_range (NULL_TREE,
2277 : bound_subrange,
2278 : mgr->get_svalue_manager ());
2279 :
2280 76 : result_map.insert (reg_subrange, overlap_sval);
2281 :
2282 : /* Clobber default_map, removing/trimming/spliting where
2283 : it overlaps with overlap_concrete_key. */
2284 76 : default_map.remove_overlapping_bindings (mgr, reg_subrange);
2285 : }
2286 : }
2287 : else
2288 : /* Can't handle symbolic bindings. */
2289 : return nullptr;
2290 : }
2291 :
2292 70625 : if (result_map.size () == 0)
2293 : return nullptr;
2294 :
2295 : /* Merge any bindings from default_map into result_map. */
2296 3659 : for (auto iter : default_map)
2297 : {
2298 323 : const bit_range &key = iter.first;
2299 323 : const svalue *sval = iter.second;
2300 323 : result_map.insert (key, sval);
2301 : }
2302 :
2303 3336 : return sval_mgr->get_or_create_compound_svalue (reg->get_type (),
2304 3336 : std::move (result_map));
2305 78888 : }
2306 :
2307 : /* Remove, truncate, and/or split any bindings within this map that
2308 : could overlap REG.
2309 :
2310 : If REG's base region or this cluster is symbolic and they're different
2311 : base regions, then remove everything in this cluster's map, on the
2312 : grounds that REG could be referring to the same memory as anything
2313 : in the map.
2314 :
2315 : If UNCERTAINTY is non-NULL, use it to record any svalues that
2316 : were removed, as being maybe-bound.
2317 :
2318 : If MAYBE_LIVE_VALUES is non-NULL, use it to record any svalues that
2319 : were removed, as being maybe-live. */
2320 :
2321 : void
2322 82539 : binding_cluster::remove_overlapping_bindings (store_manager *mgr,
2323 : const region *reg,
2324 : uncertainty_t *uncertainty,
2325 : svalue_set *maybe_live_values)
2326 : {
2327 82539 : if (reg->empty_p ())
2328 : return;
2329 82539 : const binding_key *reg_binding = binding_key::make (mgr, reg);
2330 :
2331 82539 : const region *cluster_base_reg = get_base_region ();
2332 82539 : const region *other_base_reg = reg->get_base_region ();
2333 : /* If at least one of the base regions involved is symbolic, and they're
2334 : not the same base region, then consider everything in the map as
2335 : potentially overlapping with reg_binding (even if it's a concrete
2336 : binding and things in the map are concrete - they could be referring
2337 : to the same memory when the symbolic base regions are taken into
2338 : account). */
2339 82539 : bool always_overlap = (cluster_base_reg != other_base_reg
2340 82539 : && (cluster_base_reg->get_kind () == RK_SYMBOLIC
2341 18091 : || other_base_reg->get_kind () == RK_SYMBOLIC));
2342 82539 : m_map.remove_overlapping_bindings (mgr, reg_binding, uncertainty,
2343 : maybe_live_values,
2344 : always_overlap);
2345 : }
2346 :
2347 : /* Attempt to merge CLUSTER_A and CLUSTER_B into OUT_CLUSTER, using
2348 : MGR and MERGER.
2349 : Return true if they can be merged, false otherwise. */
2350 :
2351 : bool
2352 1264244 : binding_cluster::can_merge_p (const binding_cluster *cluster_a,
2353 : const binding_cluster *cluster_b,
2354 : binding_cluster *out_cluster,
2355 : store *out_store,
2356 : store_manager *mgr,
2357 : model_merger *merger)
2358 : {
2359 1264244 : gcc_assert (out_cluster);
2360 :
2361 : /* Merge flags ("ESCAPED" and "TOUCHED") by setting the merged flag to
2362 : true if either of the inputs is true. */
2363 1264244 : if ((cluster_a && cluster_a->m_escaped)
2364 822129 : || (cluster_b && cluster_b->m_escaped))
2365 2708 : out_cluster->m_escaped = true;
2366 1264244 : if ((cluster_a && cluster_a->m_touched)
2367 1066231 : || (cluster_b && cluster_b->m_touched))
2368 7350 : out_cluster->m_touched = true;
2369 :
2370 : /* At least one of CLUSTER_A and CLUSTER_B are non-NULL, but either
2371 : could be NULL. Handle these cases. */
2372 1264244 : if (cluster_a == nullptr)
2373 : {
2374 7624 : gcc_assert (cluster_b != nullptr);
2375 7624 : gcc_assert (cluster_b->m_base_region == out_cluster->m_base_region);
2376 7624 : out_cluster->make_unknown_relative_to (cluster_b, out_store, mgr);
2377 7624 : return true;
2378 : }
2379 1256620 : if (cluster_b == nullptr)
2380 : {
2381 24661 : gcc_assert (cluster_a != nullptr);
2382 24661 : gcc_assert (cluster_a->m_base_region == out_cluster->m_base_region);
2383 24661 : out_cluster->make_unknown_relative_to (cluster_a, out_store, mgr);
2384 24661 : return true;
2385 : }
2386 :
2387 : /* The "both inputs are non-NULL" case. */
2388 1231959 : gcc_assert (cluster_a != nullptr && cluster_b != nullptr);
2389 1231959 : gcc_assert (cluster_a->m_base_region == out_cluster->m_base_region);
2390 1231959 : gcc_assert (cluster_b->m_base_region == out_cluster->m_base_region);
2391 :
2392 1231959 : hash_set<const binding_key *> keys;
2393 3019284 : for (auto iter_a : cluster_a->m_map)
2394 : {
2395 1787325 : const binding_key *key_a = iter_a.m_key;
2396 1787325 : keys.add (key_a);
2397 : }
2398 2913054 : for (auto iter_b : cluster_b->m_map)
2399 : {
2400 1681095 : const binding_key *key_b = iter_b.m_key;
2401 1681095 : keys.add (key_b);
2402 : }
2403 1231959 : int num_symbolic_keys = 0;
2404 1231959 : int num_concrete_keys = 0;
2405 2936539 : for (hash_set<const binding_key *>::iterator iter = keys.begin ();
2406 4641119 : iter != keys.end (); ++iter)
2407 : {
2408 1795044 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
2409 1795044 : const binding_key *key = *iter;
2410 1795044 : const svalue *sval_a = cluster_a->get_any_value (key);
2411 1795044 : const svalue *sval_b = cluster_b->get_any_value (key);
2412 :
2413 1795044 : if (key->symbolic_p ())
2414 52592 : num_symbolic_keys++;
2415 : else
2416 1742452 : num_concrete_keys++;
2417 :
2418 1795044 : if (sval_a == sval_b)
2419 : {
2420 1422182 : gcc_assert (sval_a);
2421 1422182 : out_cluster->m_map.put (key, sval_a);
2422 1422182 : continue;
2423 : }
2424 372862 : else if (sval_a && sval_b)
2425 : {
2426 433683 : if (const svalue *merged_sval
2427 160184 : = sval_a->can_merge_p (sval_b, sval_mgr, merger))
2428 : {
2429 113315 : out_cluster->m_map.put (key, merged_sval);
2430 113315 : continue;
2431 : }
2432 : /* Merger of the svalues failed. Reject merger of the cluster. */
2433 90464 : return false;
2434 : }
2435 :
2436 : /* If we get here, then one cluster binds this key and the other
2437 : doesn't; merge them as "UNKNOWN". */
2438 212678 : gcc_assert (sval_a || sval_b);
2439 :
2440 212678 : const svalue *bound_sval = sval_a ? sval_a : sval_b;
2441 212678 : tree type = bound_sval->get_type ();
2442 212678 : const svalue *unknown_sval
2443 212678 : = mgr->get_svalue_manager ()->get_or_create_unknown_svalue (type);
2444 :
2445 : /* ...but reject the merger if this sval shouldn't be mergeable
2446 : (e.g. reject merging svalues that have non-purgable sm-state,
2447 : to avoid falsely reporting memory leaks by merging them
2448 : with something else). */
2449 212678 : if (!bound_sval->can_merge_p (unknown_sval, sval_mgr, merger))
2450 : return false;
2451 :
2452 169083 : out_cluster->m_map.put (key, unknown_sval);
2453 : }
2454 :
2455 : /* We might now have overlapping concrete clusters in OUT_CLUSTER.
2456 : Reject such cases. */
2457 1141495 : if (num_concrete_keys > 0)
2458 : {
2459 : /* Check for overlapping concrete bindings. */
2460 851258 : const auto &concrete_bindings
2461 851258 : = out_cluster->get_map ().get_concrete_bindings ();
2462 2353934 : for (auto iter = concrete_bindings.begin ();
2463 2353934 : iter != concrete_bindings.end (); ++iter)
2464 : {
2465 1519242 : auto next (iter);
2466 1519242 : ++next;
2467 1519242 : if (next != concrete_bindings.end ())
2468 : {
2469 684550 : const bit_range &iter_bits = iter->first;
2470 684550 : const bit_range &next_bits = next->first;
2471 684550 : if (iter_bits.intersects_p (next_bits))
2472 107030 : return false;
2473 : }
2474 : }
2475 : }
2476 :
2477 : /* We can only have at most one symbolic key per cluster,
2478 : and if we do, we can't have any concrete keys.
2479 : If this happens, mark the cluster as touched, with no keys. */
2480 1124929 : if (num_symbolic_keys >= 2
2481 1124324 : || (num_concrete_keys > 0 && num_symbolic_keys > 0))
2482 : {
2483 2715 : out_cluster->m_touched = true;
2484 2715 : out_cluster->m_map.clear ();
2485 : }
2486 :
2487 : /* We don't handle other kinds of overlaps yet. */
2488 :
2489 : return true;
2490 1231959 : }
2491 :
2492 : /* Update this cluster to reflect an attempt to merge OTHER where there
2493 : is no other cluster to merge with, and so we're notionally merging the
2494 : bound values in OTHER with the initial value of the relevant regions.
2495 :
2496 : Any bound keys in OTHER should be bound to unknown in this. */
2497 :
2498 : void
2499 32285 : binding_cluster::make_unknown_relative_to (const binding_cluster *other,
2500 : store *out_store,
2501 : store_manager *mgr)
2502 : {
2503 64619 : for (auto iter : *other)
2504 : {
2505 32334 : const binding_key *iter_key = iter.m_key;
2506 32334 : const svalue *iter_sval = iter.m_sval;
2507 32334 : const svalue *unknown_sval
2508 : = mgr->get_svalue_manager ()->get_or_create_unknown_svalue
2509 32334 : (iter_sval->get_type ());
2510 32334 : m_map.put (iter_key, unknown_sval);
2511 :
2512 : /* For any pointers in OTHER, the merger means that the
2513 : concrete pointer becomes an unknown value, which could
2514 : show up as a false report of a leak when considering what
2515 : pointers are live before vs after.
2516 : Avoid this by marking the base regions they point to as having
2517 : escaped. */
2518 64668 : if (const region_svalue *region_sval
2519 32334 : = iter_sval->dyn_cast_region_svalue ())
2520 : {
2521 2115 : const region *base_reg
2522 2115 : = region_sval->get_pointee ()->get_base_region ();
2523 2115 : if (base_reg->tracked_p ()
2524 2115 : && !base_reg->symbolic_for_unknown_ptr_p ())
2525 : {
2526 2113 : binding_cluster *c
2527 2113 : = out_store->get_or_create_cluster (*mgr, base_reg);
2528 2113 : c->mark_as_escaped ();
2529 : }
2530 : }
2531 : }
2532 32285 : }
2533 :
2534 : /* Mark this cluster as having escaped. */
2535 :
2536 : void
2537 36862 : binding_cluster::mark_as_escaped ()
2538 : {
2539 36862 : m_escaped = true;
2540 36862 : }
2541 :
2542 : /* If this cluster has escaped (by this call, or by an earlier one, or
2543 : by being an external param), then unbind all values and mark it
2544 : as "touched", so that it has a conjured value, rather than an
2545 : initial_svalue.
2546 : Use P to purge state involving conjured_svalues. */
2547 :
2548 : void
2549 124083 : binding_cluster::on_unknown_fncall (const gcall &call,
2550 : store_manager *mgr,
2551 : const conjured_purge &p)
2552 : {
2553 124083 : if (m_escaped)
2554 : {
2555 21206 : m_map.clear ();
2556 :
2557 21206 : if (!m_base_region->empty_p ())
2558 : {
2559 : /* Bind it to a new "conjured" value using CALL. */
2560 21206 : const svalue *sval
2561 : = mgr->get_svalue_manager ()->get_or_create_conjured_svalue
2562 21206 : (m_base_region->get_type (), &call, m_base_region, p);
2563 21206 : bind (mgr, m_base_region, sval);
2564 : }
2565 :
2566 21206 : m_touched = true;
2567 : }
2568 124083 : }
2569 :
2570 : /* Mark this cluster as having been clobbered by STMT.
2571 : Use P to purge state involving conjured_svalues. */
2572 :
2573 : void
2574 510 : binding_cluster::on_asm (const gasm *stmt,
2575 : store_manager *mgr,
2576 : const conjured_purge &p)
2577 : {
2578 510 : m_map.clear ();
2579 :
2580 : /* Bind it to a new "conjured" value using CALL. */
2581 510 : const svalue *sval
2582 : = mgr->get_svalue_manager ()->get_or_create_conjured_svalue
2583 510 : (m_base_region->get_type (), stmt, m_base_region, p);
2584 510 : bind (mgr, m_base_region, sval);
2585 :
2586 510 : m_touched = true;
2587 510 : }
2588 :
2589 : /* Return true if this cluster has escaped. */
2590 :
2591 : bool
2592 9529280 : binding_cluster::escaped_p () const
2593 : {
2594 : /* Consider the "errno" region to always have escaped. */
2595 9529280 : if (m_base_region->get_kind () == RK_ERRNO)
2596 : return true;
2597 9505729 : return m_escaped;
2598 : }
2599 :
2600 : /* Return true if this binding_cluster has no information
2601 : i.e. if there are no bindings, and it hasn't been marked as having
2602 : escaped, or touched symbolically. */
2603 :
2604 : bool
2605 230294 : binding_cluster::redundant_p () const
2606 : {
2607 230294 : return (m_map.elements () == 0
2608 226385 : && !m_escaped
2609 455506 : && !m_touched);
2610 : }
2611 :
2612 : /* Add PV to OUT_PVS, casting it to TYPE if it is not already of that type. */
2613 :
2614 : static void
2615 7460 : append_pathvar_with_type (path_var pv,
2616 : tree type,
2617 : auto_vec<path_var> *out_pvs)
2618 : {
2619 7460 : gcc_assert (pv.m_tree);
2620 :
2621 7460 : if (TREE_TYPE (pv.m_tree) != type)
2622 879 : pv.m_tree = build1 (NOP_EXPR, type, pv.m_tree);
2623 :
2624 7460 : out_pvs->safe_push (pv);
2625 7460 : }
2626 :
2627 : /* Find representative path_vars for SVAL within this binding of BASE_REG,
2628 : appending the results to OUT_PVS. */
2629 :
2630 : void
2631 46064 : binding_cluster::get_representative_path_vars (const region_model *model,
2632 : svalue_set *visited,
2633 : const region *base_reg,
2634 : const svalue *sval,
2635 : logger *logger,
2636 : auto_vec<path_var> *out_pvs)
2637 : const
2638 : {
2639 46064 : sval = simplify_for_binding (sval);
2640 :
2641 88835 : for (auto iter : m_map)
2642 : {
2643 42771 : const binding_key *key = iter.m_key;
2644 42771 : const svalue *bound_sval = iter.m_sval;
2645 42771 : if (bound_sval == sval)
2646 : {
2647 15702 : if (const concrete_binding *ckey
2648 7851 : = key->dyn_cast_concrete_binding ())
2649 : {
2650 7817 : auto_vec <const region *> subregions;
2651 7817 : base_reg->get_subregions_for_binding
2652 7817 : (model->get_manager (),
2653 : ckey->get_start_bit_offset (),
2654 : ckey->get_size_in_bits (),
2655 : sval->get_type (),
2656 : &subregions);
2657 7817 : unsigned i;
2658 7817 : const region *subregion;
2659 22677 : FOR_EACH_VEC_ELT (subregions, i, subregion)
2660 : {
2661 14860 : if (path_var pv
2662 7430 : = model->get_representative_path_var (subregion,
2663 : visited,
2664 7430 : logger))
2665 7426 : append_pathvar_with_type (pv, sval->get_type (), out_pvs);
2666 : }
2667 7817 : }
2668 : else
2669 : {
2670 34 : const symbolic_binding *skey = (const symbolic_binding *)key;
2671 68 : if (path_var pv
2672 34 : = model->get_representative_path_var (skey->get_region (),
2673 : visited,
2674 34 : logger))
2675 34 : append_pathvar_with_type (pv, sval->get_type (), out_pvs);
2676 : }
2677 : }
2678 : }
2679 46064 : }
2680 :
2681 : /* Get any svalue bound to KEY, or nullptr. */
2682 :
2683 : const svalue *
2684 3742390 : binding_cluster::get_any_value (const binding_key *key) const
2685 : {
2686 3742390 : return m_map.get (key);
2687 : }
2688 :
2689 : /* If this cluster has a single direct binding for the whole of the region,
2690 : return it.
2691 : For use in simplifying dumps. */
2692 :
2693 : const svalue *
2694 299448 : binding_cluster::maybe_get_simple_value (store_manager *mgr) const
2695 : {
2696 : /* Fail gracefully if MGR is nullptr to make it easier to dump store
2697 : instances in the debugger. */
2698 299448 : if (mgr == nullptr)
2699 : return nullptr;
2700 :
2701 299448 : if (m_map.elements () != 1)
2702 : return nullptr;
2703 :
2704 152302 : if (m_base_region->empty_p ())
2705 : return nullptr;
2706 :
2707 152302 : const binding_key *key = binding_key::make (mgr, m_base_region);
2708 152302 : return get_any_value (key);
2709 : }
2710 :
2711 : /* class store_manager. */
2712 :
2713 : logger *
2714 392754 : store_manager::get_logger () const
2715 : {
2716 392754 : return m_mgr->get_logger ();
2717 : }
2718 :
2719 : /* binding consolidation. */
2720 :
2721 : const concrete_binding *
2722 13901686 : store_manager::get_concrete_binding (bit_offset_t start_bit_offset,
2723 : bit_offset_t size_in_bits)
2724 : {
2725 13901686 : concrete_binding b (start_bit_offset, size_in_bits);
2726 27790343 : if (concrete_binding *existing = m_concrete_binding_key_mgr.get (b))
2727 : return existing;
2728 :
2729 13029 : concrete_binding *to_save = new concrete_binding (b);
2730 13029 : m_concrete_binding_key_mgr.put (b, to_save);
2731 13029 : return to_save;
2732 13901686 : }
2733 :
2734 : const symbolic_binding *
2735 1893255 : store_manager::get_symbolic_binding (const region *reg)
2736 : {
2737 1893255 : symbolic_binding b (reg);
2738 3764529 : if (symbolic_binding *existing = m_symbolic_binding_key_mgr.get (b))
2739 : return existing;
2740 :
2741 21981 : symbolic_binding *to_save = new symbolic_binding (b);
2742 21981 : m_symbolic_binding_key_mgr.put (b, to_save);
2743 21981 : return to_save;
2744 1893255 : }
2745 :
2746 : /* class store. */
2747 :
2748 : /* store's default ctor. */
2749 :
2750 419329 : store::store ()
2751 419329 : : m_called_unknown_fn (false)
2752 : {
2753 419329 : }
2754 :
2755 : /* store's copy ctor. */
2756 :
2757 3618409 : store::store (const store &other)
2758 3618409 : : m_cluster_map (other.m_cluster_map.elements ()),
2759 3618409 : m_called_unknown_fn (other.m_called_unknown_fn)
2760 : {
2761 3618409 : for (cluster_map_t::iterator iter = other.m_cluster_map.begin ();
2762 34570014 : iter != other.m_cluster_map.end ();
2763 30951605 : ++iter)
2764 : {
2765 30951605 : const region *reg = (*iter).first;
2766 0 : gcc_assert (reg);
2767 30951605 : binding_cluster *c = (*iter).second;
2768 30951605 : gcc_assert (c);
2769 30951605 : m_cluster_map.put (reg, new binding_cluster (*c));
2770 : }
2771 3618409 : }
2772 :
2773 : /* store's dtor. */
2774 :
2775 4037738 : store::~store ()
2776 : {
2777 36739917 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2778 36739917 : iter != m_cluster_map.end ();
2779 32702179 : ++iter)
2780 32702179 : delete (*iter).second;
2781 4037738 : }
2782 :
2783 : /* store's assignment operator. */
2784 :
2785 : store &
2786 98815 : store::operator= (const store &other)
2787 : {
2788 : /* Delete existing cluster map. */
2789 748646 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2790 748646 : iter != m_cluster_map.end ();
2791 649831 : ++iter)
2792 1299662 : delete (*iter).second;
2793 98815 : m_cluster_map.empty ();
2794 :
2795 98815 : m_called_unknown_fn = other.m_called_unknown_fn;
2796 :
2797 98815 : for (cluster_map_t::iterator iter = other.m_cluster_map.begin ();
2798 1168921 : iter != other.m_cluster_map.end ();
2799 1070106 : ++iter)
2800 : {
2801 1070106 : const region *reg = (*iter).first;
2802 1070106 : gcc_assert (reg);
2803 1070106 : binding_cluster *c = (*iter).second;
2804 1070106 : gcc_assert (c);
2805 1070106 : m_cluster_map.put (reg, new binding_cluster (*c));
2806 : }
2807 98815 : return *this;
2808 : }
2809 :
2810 : /* store's equality operator. */
2811 :
2812 : bool
2813 526641 : store::operator== (const store &other) const
2814 : {
2815 526641 : if (m_called_unknown_fn != other.m_called_unknown_fn)
2816 : return false;
2817 :
2818 522579 : if (m_cluster_map.elements () != other.m_cluster_map.elements ())
2819 : return false;
2820 :
2821 3806832 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2822 3806832 : iter != m_cluster_map.end ();
2823 3310667 : ++iter)
2824 : {
2825 3378992 : const region *reg = (*iter).first;
2826 3378992 : binding_cluster *c = (*iter).second;
2827 3378992 : binding_cluster **other_slot
2828 3378992 : = const_cast <cluster_map_t &> (other.m_cluster_map).get (reg);
2829 3378992 : if (other_slot == nullptr)
2830 68325 : return false;
2831 3376942 : if (*c != **other_slot)
2832 : return false;
2833 : }
2834 :
2835 427840 : gcc_checking_assert (hash () == other.hash ());
2836 :
2837 : return true;
2838 : }
2839 :
2840 : /* Get a hash value for this store. */
2841 :
2842 : hashval_t
2843 2166467 : store::hash () const
2844 : {
2845 2166467 : hashval_t result = 0;
2846 2166467 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2847 17523664 : iter != m_cluster_map.end ();
2848 15357197 : ++iter)
2849 15357197 : result ^= (*iter).second->hash ();
2850 2166467 : return result;
2851 : }
2852 :
2853 : /* Populate OUT with a sorted list of parent regions for the regions in IN,
2854 : removing duplicate parents. */
2855 :
2856 : static void
2857 2134 : get_sorted_parent_regions (auto_vec<const region *> *out,
2858 : auto_vec<const region *> &in)
2859 : {
2860 : /* Get the set of parent regions. */
2861 2134 : hash_set<const region *> parent_regions;
2862 2134 : const region *iter_reg;
2863 2134 : unsigned i;
2864 10887 : FOR_EACH_VEC_ELT (in, i, iter_reg)
2865 : {
2866 8753 : const region *parent_reg = iter_reg->get_parent_region ();
2867 8753 : gcc_assert (parent_reg);
2868 8753 : parent_regions.add (parent_reg);
2869 : }
2870 :
2871 : /* Write to OUT. */
2872 2134 : for (hash_set<const region *>::iterator iter = parent_regions.begin();
2873 11368 : iter != parent_regions.end(); ++iter)
2874 4617 : out->safe_push (*iter);
2875 :
2876 : /* Sort OUT. */
2877 4066 : out->qsort (region::cmp_ptr_ptr);
2878 2134 : }
2879 :
2880 : /* Dump a representation of this store to PP, using SIMPLE to control how
2881 : svalues and regions are printed.
2882 : MGR is used for simplifying dumps if non-NULL, but can also be nullptr
2883 : (to make it easier to use from the debugger). */
2884 :
2885 : void
2886 2126 : store::dump_to_pp (pretty_printer *pp, bool simple, bool multiline,
2887 : store_manager *mgr) const
2888 : {
2889 : /* Sort into some deterministic order. */
2890 2126 : auto_vec<const region *> base_regions;
2891 10879 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2892 19632 : iter != m_cluster_map.end (); ++iter)
2893 : {
2894 8753 : const region *base_reg = (*iter).first;
2895 8753 : base_regions.safe_push (base_reg);
2896 : }
2897 2126 : base_regions.qsort (region::cmp_ptr_ptr);
2898 :
2899 : /* Gather clusters, organize by parent region, so that we can group
2900 : together locals, globals, etc. */
2901 2126 : auto_vec<const region *> parent_regions;
2902 2126 : get_sorted_parent_regions (&parent_regions, base_regions);
2903 :
2904 2126 : const region *parent_reg;
2905 2126 : unsigned i;
2906 6743 : FOR_EACH_VEC_ELT (parent_regions, i, parent_reg)
2907 : {
2908 4617 : gcc_assert (parent_reg);
2909 4617 : pp_string (pp, "clusters within ");
2910 4617 : parent_reg->dump_to_pp (pp, simple);
2911 4617 : if (multiline)
2912 1175 : pp_newline (pp);
2913 : else
2914 3442 : pp_string (pp, " {");
2915 :
2916 : const region *base_reg;
2917 : unsigned j;
2918 27008 : FOR_EACH_VEC_ELT (base_regions, j, base_reg)
2919 : {
2920 : /* This is O(N * M), but N ought to be small. */
2921 22391 : if (base_reg->get_parent_region () != parent_reg)
2922 13638 : continue;
2923 8753 : binding_cluster *cluster
2924 8753 : = *const_cast<cluster_map_t &> (m_cluster_map).get (base_reg);
2925 8753 : if (!multiline)
2926 : {
2927 5854 : if (j > 0)
2928 4435 : pp_string (pp, ", ");
2929 : }
2930 8753 : if (const svalue *sval = cluster->maybe_get_simple_value (mgr))
2931 : {
2932 : /* Special-case to simplify dumps for the common case where
2933 : we just have one value directly bound to the whole of a
2934 : region. */
2935 7022 : if (multiline)
2936 : {
2937 1811 : pp_string (pp, " cluster for: ");
2938 1811 : base_reg->dump_to_pp (pp, simple);
2939 1811 : pp_string (pp, ": ");
2940 1811 : sval->dump_to_pp (pp, simple);
2941 1811 : if (cluster->escaped_p ())
2942 48 : pp_string (pp, " (ESCAPED)");
2943 1811 : if (cluster->touched_p ())
2944 6 : pp_string (pp, " (TOUCHED)");
2945 1811 : pp_newline (pp);
2946 : }
2947 : else
2948 : {
2949 5211 : pp_string (pp, "region: {");
2950 5211 : base_reg->dump_to_pp (pp, simple);
2951 5211 : pp_string (pp, ", value: ");
2952 5211 : sval->dump_to_pp (pp, simple);
2953 5211 : if (cluster->escaped_p ())
2954 1066 : pp_string (pp, " (ESCAPED)");
2955 5211 : if (cluster->touched_p ())
2956 1066 : pp_string (pp, " (TOUCHED)");
2957 5211 : pp_string (pp, "}");
2958 : }
2959 : }
2960 1731 : else if (multiline)
2961 : {
2962 1088 : pp_string (pp, " cluster for: ");
2963 1088 : base_reg->dump_to_pp (pp, simple);
2964 1088 : pp_newline (pp);
2965 1088 : cluster->dump_to_pp (pp, simple, multiline);
2966 : }
2967 : else
2968 : {
2969 643 : pp_string (pp, "base region: {");
2970 643 : base_reg->dump_to_pp (pp, simple);
2971 643 : pp_string (pp, "} has cluster: {");
2972 643 : cluster->dump_to_pp (pp, simple, multiline);
2973 643 : pp_string (pp, "}");
2974 : }
2975 : }
2976 4617 : if (!multiline)
2977 3442 : pp_string (pp, "}");
2978 : }
2979 2126 : pp_printf (pp, "m_called_unknown_fn: %s",
2980 2126 : m_called_unknown_fn ? "TRUE" : "FALSE");
2981 2126 : if (multiline)
2982 545 : pp_newline (pp);
2983 2126 : }
2984 :
2985 : /* Dump a multiline representation of this store to stderr. */
2986 :
2987 : DEBUG_FUNCTION void
2988 0 : store::dump (bool simple) const
2989 : {
2990 0 : tree_dump_pretty_printer pp (stderr);
2991 0 : dump_to_pp (&pp, simple, true, nullptr);
2992 0 : pp_newline (&pp);
2993 0 : }
2994 :
2995 : /* Assert that this object is valid. */
2996 :
2997 : void
2998 1811959 : store::validate () const
2999 : {
3000 15181789 : for (auto iter : m_cluster_map)
3001 13369830 : iter.second->validate ();
3002 1811959 : }
3003 :
3004 : /* Return a new json::object of the form
3005 : {PARENT_REGION_DESC: {BASE_REGION_DESC: object for binding_map,
3006 : ... for each cluster within parent region},
3007 : ...for each parent region,
3008 : "called_unknown_fn": true/false}. */
3009 :
3010 : std::unique_ptr<json::object>
3011 4 : store::to_json () const
3012 : {
3013 4 : auto store_obj = std::make_unique<json::object> ();
3014 :
3015 : /* Sort into some deterministic order. */
3016 4 : auto_vec<const region *> base_regions;
3017 4 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3018 4 : iter != m_cluster_map.end (); ++iter)
3019 : {
3020 0 : const region *base_reg = (*iter).first;
3021 0 : base_regions.safe_push (base_reg);
3022 : }
3023 4 : base_regions.qsort (region::cmp_ptr_ptr);
3024 :
3025 : /* Gather clusters, organize by parent region, so that we can group
3026 : together locals, globals, etc. */
3027 4 : auto_vec<const region *> parent_regions;
3028 4 : get_sorted_parent_regions (&parent_regions, base_regions);
3029 :
3030 4 : const region *parent_reg;
3031 4 : unsigned i;
3032 4 : FOR_EACH_VEC_ELT (parent_regions, i, parent_reg)
3033 : {
3034 0 : gcc_assert (parent_reg);
3035 :
3036 0 : auto clusters_in_parent_reg_obj = std::make_unique<json::object> ();
3037 :
3038 0 : const region *base_reg;
3039 0 : unsigned j;
3040 0 : FOR_EACH_VEC_ELT (base_regions, j, base_reg)
3041 : {
3042 : /* This is O(N * M), but N ought to be small. */
3043 0 : if (base_reg->get_parent_region () != parent_reg)
3044 0 : continue;
3045 0 : binding_cluster *cluster
3046 0 : = *const_cast<cluster_map_t &> (m_cluster_map).get (base_reg);
3047 0 : label_text base_reg_desc = base_reg->get_desc ();
3048 0 : clusters_in_parent_reg_obj->set (base_reg_desc.get (),
3049 0 : cluster->to_json ());
3050 0 : }
3051 0 : label_text parent_reg_desc = parent_reg->get_desc ();
3052 0 : store_obj->set (parent_reg_desc.get (),
3053 : std::move (clusters_in_parent_reg_obj));
3054 0 : }
3055 :
3056 4 : store_obj->set_bool ("called_unknown_fn", m_called_unknown_fn);
3057 :
3058 4 : return store_obj;
3059 4 : }
3060 :
3061 : std::unique_ptr<text_art::tree_widget>
3062 4 : store::make_dump_widget (const text_art::dump_widget_info &dwi,
3063 : store_manager *mgr) const
3064 : {
3065 4 : std::unique_ptr<text_art::tree_widget> store_widget
3066 4 : (text_art::tree_widget::make (dwi, "Store"));
3067 :
3068 4 : store_widget->add_child
3069 8 : (text_art::tree_widget::from_fmt (dwi, nullptr,
3070 : "m_called_unknown_fn: %s",
3071 4 : m_called_unknown_fn ? "true" : "false"));
3072 :
3073 : /* Sort into some deterministic order. */
3074 4 : auto_vec<const region *> base_regions;
3075 4 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3076 4 : iter != m_cluster_map.end (); ++iter)
3077 : {
3078 0 : const region *base_reg = (*iter).first;
3079 0 : base_regions.safe_push (base_reg);
3080 : }
3081 4 : base_regions.qsort (region::cmp_ptr_ptr);
3082 :
3083 : /* Gather clusters, organize by parent region, so that we can group
3084 : together locals, globals, etc. */
3085 4 : auto_vec<const region *> parent_regions;
3086 4 : get_sorted_parent_regions (&parent_regions, base_regions);
3087 :
3088 4 : const region *parent_reg;
3089 4 : unsigned i;
3090 4 : FOR_EACH_VEC_ELT (parent_regions, i, parent_reg)
3091 : {
3092 0 : gcc_assert (parent_reg);
3093 :
3094 0 : pretty_printer the_pp;
3095 0 : pretty_printer * const pp = &the_pp;
3096 0 : pp_format_decoder (pp) = default_tree_printer;
3097 0 : pp_show_color (pp) = true;
3098 0 : const bool simple = true;
3099 :
3100 0 : parent_reg->dump_to_pp (pp, simple);
3101 :
3102 0 : std::unique_ptr<text_art::tree_widget> parent_reg_widget
3103 0 : (text_art::tree_widget::make (dwi, pp));
3104 :
3105 0 : const region *base_reg;
3106 0 : unsigned j;
3107 0 : FOR_EACH_VEC_ELT (base_regions, j, base_reg)
3108 : {
3109 : /* This is O(N * M), but N ought to be small. */
3110 0 : if (base_reg->get_parent_region () != parent_reg)
3111 0 : continue;
3112 0 : binding_cluster *cluster
3113 0 : = *const_cast<cluster_map_t &> (m_cluster_map).get (base_reg);
3114 0 : parent_reg_widget->add_child
3115 0 : (cluster->make_dump_widget (dwi, mgr));
3116 : }
3117 0 : store_widget->add_child (std::move (parent_reg_widget));
3118 0 : }
3119 :
3120 4 : return store_widget;
3121 4 : }
3122 :
3123 : /* Get any svalue bound to REG, or nullptr. */
3124 :
3125 : const svalue *
3126 4261268 : store::get_any_binding (store_manager *mgr, const region *reg) const
3127 : {
3128 4261268 : const region *base_reg = reg->get_base_region ();
3129 4261268 : binding_cluster **cluster_slot
3130 4261268 : = const_cast <cluster_map_t &> (m_cluster_map).get (base_reg);
3131 4261268 : if (!cluster_slot)
3132 : return nullptr;
3133 1303485 : return (*cluster_slot)->get_any_binding (mgr, reg);
3134 : }
3135 :
3136 : /* Set the value of LHS_REG to RHS_SVAL.
3137 : Use MODEL when determining if regions alias each other. */
3138 :
3139 : void
3140 392754 : store::set_value (store_manager *mgr, const region *lhs_reg,
3141 : const svalue *rhs_sval,
3142 : uncertainty_t *uncertainty,
3143 : const region_model &model)
3144 : {
3145 392754 : logger *logger = mgr->get_logger ();
3146 392754 : LOG_SCOPE (logger);
3147 :
3148 392754 : remove_overlapping_bindings (mgr, lhs_reg, uncertainty);
3149 :
3150 392754 : if (lhs_reg->get_type ())
3151 379735 : rhs_sval = simplify_for_binding (rhs_sval);
3152 : /* ...but if we have no type for the region, retain any cast. */
3153 :
3154 392754 : const region *lhs_base_reg = lhs_reg->get_base_region ();
3155 392754 : binding_cluster *lhs_cluster;
3156 392754 : if (lhs_base_reg->symbolic_for_unknown_ptr_p ())
3157 : {
3158 : /* Reject attempting to bind values into a symbolic region
3159 : for an unknown ptr; merely invalidate values below. */
3160 2573 : lhs_cluster = nullptr;
3161 :
3162 : /* The LHS of the write is *UNKNOWN. If the RHS is a pointer,
3163 : then treat the region being pointed to as having escaped. */
3164 2573 : if (const region_svalue *ptr_sval = rhs_sval->dyn_cast_region_svalue ())
3165 : {
3166 83 : const region *ptr_dst = ptr_sval->get_pointee ();
3167 83 : const region *ptr_base_reg = ptr_dst->get_base_region ();
3168 83 : mark_as_escaped (*mgr, ptr_base_reg);
3169 : }
3170 2573 : if (uncertainty)
3171 1151 : uncertainty->on_maybe_bound_sval (rhs_sval);
3172 : }
3173 390181 : else if (lhs_base_reg->tracked_p ())
3174 : {
3175 390103 : lhs_cluster = get_or_create_cluster (*mgr, lhs_base_reg);
3176 390103 : lhs_cluster->bind (mgr, lhs_reg, rhs_sval);
3177 : }
3178 : else
3179 : {
3180 : /* Reject attempting to bind values into an untracked region;
3181 : merely invalidate values below. */
3182 : lhs_cluster = nullptr;
3183 : }
3184 :
3185 : /* Bindings to a cluster can affect other clusters if a symbolic
3186 : base region is involved.
3187 : Writes to concrete clusters can't affect other concrete clusters,
3188 : but can affect symbolic clusters.
3189 : Writes to symbolic clusters can affect both concrete and symbolic
3190 : clusters.
3191 : Invalidate our knowledge of other clusters that might have been
3192 : affected by the write.
3193 : Gather the set of all svalues that might still be live even if
3194 : the store doesn't refer to them. */
3195 392754 : svalue_set maybe_live_values;
3196 5559898 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3197 10727042 : iter != m_cluster_map.end (); ++iter)
3198 : {
3199 5167144 : const region *iter_base_reg = (*iter).first;
3200 5167144 : binding_cluster *iter_cluster = (*iter).second;
3201 5167144 : if (iter_base_reg != lhs_base_reg
3202 5167144 : && (lhs_cluster == nullptr
3203 4737959 : || lhs_cluster->symbolic_p ()
3204 4679967 : || iter_cluster->symbolic_p ()))
3205 : {
3206 690049 : tristate t_alias = eval_alias (lhs_base_reg, iter_base_reg,
3207 : model);
3208 690049 : switch (t_alias.get_value ())
3209 : {
3210 0 : default:
3211 0 : gcc_unreachable ();
3212 :
3213 47219 : case tristate::TS_UNKNOWN:
3214 47219 : if (logger)
3215 : {
3216 0 : pretty_printer *pp = logger->get_printer ();
3217 0 : logger->start_log_line ();
3218 0 : logger->log_partial ("possible aliasing of ");
3219 0 : iter_base_reg->dump_to_pp (pp, true);
3220 0 : logger->log_partial (" when writing SVAL: ");
3221 0 : rhs_sval->dump_to_pp (pp, true);
3222 0 : logger->log_partial (" to LHS_REG: ");
3223 0 : lhs_reg->dump_to_pp (pp, true);
3224 0 : logger->end_log_line ();
3225 : }
3226 : /* Mark all of iter_cluster's iter_base_reg as unknown,
3227 : using LHS_REG when considering overlaps, to handle
3228 : symbolic vs concrete issues. */
3229 47219 : iter_cluster->mark_region_as_unknown
3230 47219 : (mgr,
3231 : iter_base_reg, /* reg_to_bind */
3232 : lhs_reg, /* reg_for_overlap */
3233 : uncertainty,
3234 : &maybe_live_values);
3235 47219 : break;
3236 :
3237 0 : case tristate::TS_TRUE:
3238 0 : gcc_unreachable ();
3239 : break;
3240 :
3241 : case tristate::TS_FALSE:
3242 : /* If they can't be aliases, then don't invalidate this
3243 : cluster. */
3244 : break;
3245 : }
3246 : }
3247 : }
3248 : /* Given the set of svalues that might still be live, process them
3249 : (e.g. marking regions as escaped).
3250 : We do this after the iteration to avoid potentially changing
3251 : m_cluster_map whilst iterating over it. */
3252 392754 : on_maybe_live_values (*mgr, maybe_live_values);
3253 392754 : }
3254 :
3255 : /* Determine if BASE_REG_A could be an alias of BASE_REG_B.
3256 : Use information from MODEL when comparing pointers. */
3257 :
3258 : tristate
3259 691158 : store::eval_alias (const region *base_reg_a,
3260 : const region *base_reg_b,
3261 : const region_model &model) const
3262 : {
3263 691158 : if (base_reg_a == base_reg_b)
3264 383 : return tristate (true);
3265 :
3266 : /* SSA names can't alias. */
3267 690775 : tree decl_a = base_reg_a->maybe_get_decl ();
3268 690775 : if (decl_a && TREE_CODE (decl_a) == SSA_NAME)
3269 497266 : return tristate::TS_FALSE;
3270 193509 : tree decl_b = base_reg_b->maybe_get_decl ();
3271 193509 : if (decl_b && TREE_CODE (decl_b) == SSA_NAME)
3272 43570 : return tristate::TS_FALSE;
3273 :
3274 : /* Different decls don't alias. */
3275 149939 : if (decl_a && decl_b && decl_a != decl_b)
3276 221 : return tristate::TS_FALSE;
3277 :
3278 : /* Try both ways, for symmetry. */
3279 149718 : tristate ts_ab = eval_alias_1 (base_reg_a, base_reg_b, model);
3280 149718 : if (ts_ab.is_false ())
3281 18790 : return tristate::TS_FALSE;
3282 130928 : tristate ts_ba = eval_alias_1 (base_reg_b, base_reg_a, model);
3283 130928 : if (ts_ba.is_false ())
3284 83296 : return tristate::TS_FALSE;
3285 :
3286 47632 : gcc_assert (base_reg_a != base_reg_b);
3287 47632 : enum region_kind kind_a = base_reg_a->get_kind ();
3288 47632 : enum region_kind kind_b = base_reg_b->get_kind ();
3289 47632 : if (kind_a == kind_b)
3290 : {
3291 : /* We have two different base region instances of the same kind.
3292 : For many kinds of region this implies they must have different
3293 : addresses. */
3294 16937 : switch (kind_a)
3295 : {
3296 : /* Invalid cases. */
3297 :
3298 0 : default:
3299 0 : gcc_unreachable ();
3300 :
3301 0 : case RK_CODE:
3302 0 : case RK_ERRNO:
3303 0 : case RK_GLOBALS:
3304 0 : case RK_HEAP:
3305 0 : case RK_ROOT:
3306 0 : case RK_STACK:
3307 0 : case RK_THREAD_LOCAL:
3308 : /* We expect these to be singletons. */
3309 0 : gcc_unreachable ();
3310 :
3311 0 : case RK_BIT_RANGE:
3312 0 : case RK_CAST:
3313 0 : case RK_ELEMENT:
3314 0 : case RK_FIELD:
3315 0 : case RK_OFFSET:
3316 0 : case RK_SIZED:
3317 : /* These aren't base regions. */
3318 0 : gcc_unreachable ();
3319 :
3320 : /* Valid cases. */
3321 :
3322 43 : case RK_ALLOCA:
3323 43 : case RK_DECL:
3324 43 : case RK_FRAME:
3325 43 : case RK_FUNCTION:
3326 43 : case RK_LABEL:
3327 43 : case RK_PRIVATE:
3328 43 : case RK_VAR_ARG:
3329 : /* We expect different regions of these kinds to have
3330 : different addresses. */
3331 43 : return tristate (false);
3332 :
3333 293 : case RK_HEAP_ALLOCATED:
3334 : /* We have results of two different heap allocations.
3335 : If they were non-zero-sized allocations they are different from
3336 : each other, but zero-sized allocations might alias.
3337 : Note that this doesn't handle the case where of a freed pointer
3338 : possibly being reused, but we don't have a way to distinguish
3339 : this case from the "two different allocations case", and it seems
3340 : much more important to keep the latter from aliasing each
3341 : other (for precision when tracking writes). */
3342 293 : {
3343 293 : tristate size_a_gt_zero (tristate::unknown ());
3344 293 : tristate size_b_gt_zero (tristate::unknown ());
3345 293 : const svalue *zero_size
3346 293 : = model.get_manager ()->get_or_create_int_cst (size_type_node, 0);
3347 :
3348 293 : if (auto sval_size_a = model.get_dynamic_extents (base_reg_a))
3349 : {
3350 271 : size_a_gt_zero = model.eval_condition (sval_size_a,
3351 : GT_EXPR,
3352 : zero_size);
3353 : }
3354 293 : if (auto sval_size_b = model.get_dynamic_extents (base_reg_b))
3355 : {
3356 232 : size_b_gt_zero = model.eval_condition (sval_size_b,
3357 : GT_EXPR,
3358 : zero_size);
3359 : }
3360 293 : if (size_a_gt_zero.is_known () && size_b_gt_zero.is_known ())
3361 : {
3362 : /* We have results of two different heap allocations, and for
3363 : each we know if the size was non-zero. */
3364 161 : if (size_a_gt_zero.is_false () && size_b_gt_zero.is_false ())
3365 : {
3366 : /* Different allocations, both zero-sized. We don't
3367 : know if they have the same address. */
3368 0 : return tristate::unknown ();
3369 : }
3370 : else
3371 : {
3372 : /* We either have different allocations of non-zero size,
3373 : or different allocations where one has non-zero size, the
3374 : other is zero-sized. We know these have different
3375 : addresses. */
3376 161 : return tristate (false);
3377 : }
3378 : }
3379 132 : if (size_a_gt_zero.is_true () || size_b_gt_zero.is_true ())
3380 : {
3381 : /* Different allocations, of which at least one > 0 in size.
3382 : They must have different addresses. */
3383 74 : return tristate (false);
3384 : }
3385 : /* At least one size might be zero. */
3386 58 : return tristate::unknown ();
3387 : }
3388 :
3389 16593 : case RK_SYMBOLIC:
3390 16593 : case RK_UNKNOWN:
3391 : /* We don't know that such regions are different from each other. */
3392 16593 : return tristate::unknown ();
3393 :
3394 8 : case RK_STRING:
3395 : /* For now, don't attempt to decide if string literals alias
3396 : each other. */
3397 8 : return tristate::unknown ();
3398 : }
3399 : }
3400 : else
3401 : {
3402 : /* We have two base region instances of different kinds.
3403 : For many kinds of region this implies they must have different
3404 : addresses. */
3405 30695 : if (kind_b == RK_SYMBOLIC || kind_b == RK_UNKNOWN)
3406 12599 : return tristate::unknown ();
3407 :
3408 18096 : switch (kind_a)
3409 : {
3410 : /* Invalid cases. */
3411 :
3412 0 : default:
3413 0 : gcc_unreachable ();
3414 :
3415 0 : case RK_CODE:
3416 0 : case RK_ERRNO:
3417 0 : case RK_GLOBALS:
3418 0 : case RK_HEAP:
3419 0 : case RK_ROOT:
3420 0 : case RK_STACK:
3421 0 : case RK_THREAD_LOCAL:
3422 : /* We expect these to be singletons. */
3423 0 : gcc_unreachable ();
3424 :
3425 0 : case RK_BIT_RANGE:
3426 0 : case RK_CAST:
3427 0 : case RK_ELEMENT:
3428 0 : case RK_FIELD:
3429 0 : case RK_OFFSET:
3430 0 : case RK_SIZED:
3431 : /* These aren't base regions. */
3432 0 : gcc_unreachable ();
3433 :
3434 : /* Valid cases. */
3435 :
3436 5 : case RK_ALLOCA:
3437 5 : case RK_DECL:
3438 5 : case RK_FRAME:
3439 5 : case RK_FUNCTION:
3440 5 : case RK_HEAP_ALLOCATED:
3441 5 : case RK_LABEL:
3442 5 : case RK_PRIVATE:
3443 5 : case RK_STRING:
3444 5 : case RK_VAR_ARG:
3445 : /* We expect regions of these kinds to have different addresses
3446 : from regions of other kinds (apart from symbolic/unknown). */
3447 5 : return tristate (false);
3448 :
3449 18091 : case RK_SYMBOLIC:
3450 18091 : case RK_UNKNOWN:
3451 : /* We don't know anything about such regions. */
3452 18091 : return tristate::unknown ();
3453 : }
3454 : }
3455 : }
3456 :
3457 : /* Half of store::eval_alias; called twice for symmetry. */
3458 :
3459 : tristate
3460 280646 : store::eval_alias_1 (const region *base_reg_a,
3461 : const region *base_reg_b,
3462 : const region_model &model) const
3463 : {
3464 280646 : gcc_assert (base_reg_a != base_reg_b);
3465 :
3466 : /* If they're in different memory spaces, they can't alias. */
3467 280646 : {
3468 280646 : enum memory_space memspace_a = base_reg_a->get_memory_space ();
3469 280646 : if (memspace_a != MEMSPACE_UNKNOWN)
3470 : {
3471 109651 : enum memory_space memspace_b = base_reg_b->get_memory_space ();
3472 109651 : if (memspace_b != MEMSPACE_UNKNOWN
3473 109651 : && memspace_a != memspace_b)
3474 118 : return tristate::TS_FALSE;
3475 : }
3476 : }
3477 :
3478 561056 : if (const symbolic_region *sym_reg_a
3479 280528 : = base_reg_a->dyn_cast_symbolic_region ())
3480 : {
3481 165853 : const svalue *sval_a = sym_reg_a->get_pointer ();
3482 165853 : if (tree decl_b = base_reg_b->maybe_get_decl ())
3483 : {
3484 105979 : if (!may_be_aliased (decl_b))
3485 41035 : return tristate::TS_FALSE;
3486 64944 : if (sval_a->get_kind () == SK_INITIAL)
3487 55388 : if (!is_global_var (decl_b))
3488 : {
3489 : /* The initial value of a pointer can't point to a local. */
3490 49377 : return tristate::TS_FALSE;
3491 : }
3492 : }
3493 75441 : if (sval_a->get_kind () == SK_INITIAL
3494 75441 : && base_reg_b->get_kind () == RK_HEAP_ALLOCATED)
3495 : {
3496 : /* The initial value of a pointer can't point to a
3497 : region that was allocated on the heap after the beginning of the
3498 : path. */
3499 11474 : return tristate::TS_FALSE;
3500 : }
3501 127934 : if (const widening_svalue *widening_sval_a
3502 63967 : = sval_a->dyn_cast_widening_svalue ())
3503 : {
3504 2256 : const svalue *base = widening_sval_a->get_base_svalue ();
3505 4512 : if (const region_svalue *region_sval
3506 2256 : = base->dyn_cast_region_svalue ())
3507 : {
3508 199 : const region *pointee = region_sval->get_pointee ();
3509 : /* If we have sval_a is WIDENING(®ION, OP), and
3510 : B can't alias REGION, then B can't alias A either.
3511 : For example, A might arise from
3512 : for (ptr = ®ION; ...; ptr++)
3513 : where sval_a is ptr in the 2nd iteration of the loop.
3514 : We want to ensure that "*ptr" can only clobber things
3515 : within REGION's base region. */
3516 199 : tristate ts = eval_alias (pointee->get_base_region (),
3517 : base_reg_b,
3518 : model);
3519 199 : if (ts.is_false ())
3520 82 : return tristate::TS_FALSE;
3521 : }
3522 : }
3523 : }
3524 :
3525 178560 : return tristate::TS_UNKNOWN;
3526 : }
3527 :
3528 : /* Record all of the values in MAYBE_LIVE_VALUES as being possibly live. */
3529 :
3530 : void
3531 393063 : store::on_maybe_live_values (store_manager &mgr,
3532 : const svalue_set &maybe_live_values)
3533 : {
3534 460973 : for (auto sval : maybe_live_values)
3535 : {
3536 33955 : if (const region_svalue *ptr_sval = sval->dyn_cast_region_svalue ())
3537 : {
3538 173 : const region *base_reg = ptr_sval->get_pointee ()->get_base_region ();
3539 173 : mark_as_escaped (mgr, base_reg);
3540 : }
3541 : }
3542 393063 : }
3543 :
3544 : /* Remove all bindings overlapping REG within this store. */
3545 :
3546 : void
3547 7240 : store::clobber_region (store_manager *mgr, const region *reg)
3548 : {
3549 7240 : const region *base_reg = reg->get_base_region ();
3550 7240 : binding_cluster **slot = m_cluster_map.get (base_reg);
3551 7240 : if (!slot)
3552 2265 : return;
3553 4975 : binding_cluster *cluster = *slot;
3554 4975 : cluster->clobber_region (mgr, reg);
3555 4975 : if (cluster->redundant_p ())
3556 : {
3557 3438 : delete cluster;
3558 3438 : m_cluster_map.remove (base_reg);
3559 : }
3560 : }
3561 :
3562 : /* Remove any bindings for REG within this store. */
3563 :
3564 : void
3565 225319 : store::purge_region (store_manager *mgr, const region *reg)
3566 : {
3567 225319 : const region *base_reg = reg->get_base_region ();
3568 225319 : binding_cluster **slot = m_cluster_map.get (base_reg);
3569 225319 : if (!slot)
3570 0 : return;
3571 225319 : binding_cluster *cluster = *slot;
3572 225319 : cluster->purge_region (mgr, reg);
3573 225319 : if (cluster->redundant_p ())
3574 : {
3575 221267 : delete cluster;
3576 221267 : m_cluster_map.remove (base_reg);
3577 : }
3578 : }
3579 :
3580 : /* Fill REG with SVAL. */
3581 :
3582 : void
3583 1603 : store::fill_region (store_manager *mgr, const region *reg, const svalue *sval)
3584 : {
3585 : /* Filling an empty region is a no-op. */
3586 1603 : if (reg->empty_p ())
3587 : return;
3588 :
3589 1571 : const region *base_reg = reg->get_base_region ();
3590 1571 : if (base_reg->symbolic_for_unknown_ptr_p ()
3591 1571 : || !base_reg->tracked_p ())
3592 6 : return;
3593 1565 : binding_cluster *cluster = get_or_create_cluster (*mgr, base_reg);
3594 1565 : cluster->fill_region (mgr, reg, sval);
3595 : }
3596 :
3597 : /* Zero-fill REG. */
3598 :
3599 : void
3600 861 : store::zero_fill_region (store_manager *mgr, const region *reg)
3601 : {
3602 861 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
3603 861 : const svalue *zero_sval = sval_mgr->get_or_create_int_cst (char_type_node, 0);
3604 861 : fill_region (mgr, reg, zero_sval);
3605 861 : }
3606 :
3607 : /* Mark REG as having unknown content. */
3608 :
3609 : void
3610 309 : store::mark_region_as_unknown (store_manager *mgr, const region *reg,
3611 : uncertainty_t *uncertainty,
3612 : svalue_set *maybe_live_values)
3613 : {
3614 309 : const region *base_reg = reg->get_base_region ();
3615 309 : if (base_reg->symbolic_for_unknown_ptr_p ()
3616 309 : || !base_reg->tracked_p ())
3617 0 : return;
3618 309 : binding_cluster *cluster = get_or_create_cluster (*mgr, base_reg);
3619 309 : cluster->mark_region_as_unknown (mgr, reg, reg, uncertainty,
3620 : maybe_live_values);
3621 : }
3622 :
3623 : /* Purge state involving SVAL. */
3624 :
3625 : void
3626 30249 : store::purge_state_involving (const svalue *sval,
3627 : region_model_manager *sval_mgr)
3628 : {
3629 30249 : auto_vec <const region *> base_regs_to_purge;
3630 841561 : for (auto iter : m_cluster_map)
3631 : {
3632 405656 : const region *base_reg = iter.first;
3633 405656 : if (base_reg->involves_p (sval))
3634 121 : base_regs_to_purge.safe_push (base_reg);
3635 : else
3636 : {
3637 405535 : binding_cluster *cluster = iter.second;
3638 405535 : cluster->purge_state_involving (sval, sval_mgr);
3639 : }
3640 : }
3641 :
3642 30612 : for (auto iter : base_regs_to_purge)
3643 121 : purge_cluster (iter);
3644 30249 : }
3645 :
3646 : /* Get the cluster for BASE_REG, or nullptr (const version). */
3647 :
3648 : const binding_cluster *
3649 2812912 : store::get_cluster (const region *base_reg) const
3650 : {
3651 2812912 : gcc_assert (base_reg);
3652 2812912 : gcc_assert (base_reg->get_base_region () == base_reg);
3653 5625824 : if (binding_cluster **slot
3654 2812912 : = const_cast <cluster_map_t &> (m_cluster_map).get (base_reg))
3655 2758281 : return *slot;
3656 : else
3657 : return nullptr;
3658 : }
3659 :
3660 : /* Get the cluster for BASE_REG, or nullptr (non-const version). */
3661 :
3662 : binding_cluster *
3663 10815205 : store::get_cluster (const region *base_reg)
3664 : {
3665 10815205 : gcc_assert (base_reg);
3666 10815205 : gcc_assert (base_reg->get_base_region () == base_reg);
3667 10815205 : if (binding_cluster **slot = m_cluster_map.get (base_reg))
3668 8960588 : return *slot;
3669 : else
3670 : return nullptr;
3671 : }
3672 :
3673 : /* Get the cluster for BASE_REG, creating it if doesn't already exist. */
3674 :
3675 : binding_cluster *
3676 1694689 : store::get_or_create_cluster (store_manager &store_mgr,
3677 : const region *base_reg)
3678 : {
3679 1694689 : gcc_assert (base_reg);
3680 1694689 : gcc_assert (base_reg->get_base_region () == base_reg);
3681 :
3682 : /* We shouldn't create clusters for dereferencing an UNKNOWN ptr. */
3683 1694689 : gcc_assert (!base_reg->symbolic_for_unknown_ptr_p ());
3684 :
3685 : /* We shouldn't create clusters for base regions that aren't trackable. */
3686 1694689 : gcc_assert (base_reg->tracked_p ());
3687 :
3688 1694689 : if (binding_cluster **slot = m_cluster_map.get (base_reg))
3689 52273 : return *slot;
3690 :
3691 1642416 : binding_cluster *cluster = new binding_cluster (store_mgr, base_reg);
3692 1642416 : m_cluster_map.put (base_reg, cluster);
3693 :
3694 1642416 : return cluster;
3695 : }
3696 :
3697 : /* Remove any cluster for BASE_REG, for use by
3698 : region_model::unbind_region_and_descendents
3699 : when popping stack frames and handling deleted heap regions. */
3700 :
3701 : void
3702 41342 : store::purge_cluster (const region *base_reg)
3703 : {
3704 41342 : gcc_assert (base_reg->get_base_region () == base_reg);
3705 41342 : binding_cluster **slot = m_cluster_map.get (base_reg);
3706 41342 : if (!slot)
3707 : return;
3708 41342 : binding_cluster *cluster = *slot;
3709 82684 : delete cluster;
3710 41342 : m_cluster_map.remove (base_reg);
3711 : }
3712 :
3713 : /* Attempt to merge STORE_A and STORE_B into OUT_STORE.
3714 : Return true if successful, or false if the stores can't be merged. */
3715 :
3716 : bool
3717 149560 : store::can_merge_p (const store *store_a, const store *store_b,
3718 : store *out_store, store_manager *mgr,
3719 : model_merger *merger)
3720 : {
3721 149560 : if (store_a->m_called_unknown_fn || store_b->m_called_unknown_fn)
3722 46142 : out_store->m_called_unknown_fn = true;
3723 :
3724 : /* Get the union of all base regions for STORE_A and STORE_B. */
3725 149560 : hash_set<const region *> base_regions;
3726 1952915 : for (cluster_map_t::iterator iter_a = store_a->m_cluster_map.begin ();
3727 3756270 : iter_a != store_a->m_cluster_map.end (); ++iter_a)
3728 : {
3729 1803355 : const region *base_reg_a = (*iter_a).first;
3730 1803355 : base_regions.add (base_reg_a);
3731 : }
3732 1930365 : for (cluster_map_t::iterator iter_b = store_b->m_cluster_map.begin ();
3733 3711170 : iter_b != store_b->m_cluster_map.end (); ++iter_b)
3734 : {
3735 1780805 : const region *base_reg_b = (*iter_b).first;
3736 1780805 : base_regions.add (base_reg_b);
3737 : }
3738 :
3739 : /* Sort the base regions before considering them. This ought not to
3740 : affect the results, but can affect which types UNKNOWN_REGIONs are
3741 : created for in a run; sorting them thus avoids minor differences
3742 : in logfiles. */
3743 149560 : auto_vec<const region *> vec_base_regions (base_regions.elements ());
3744 149560 : for (hash_set<const region *>::iterator iter = base_regions.begin ();
3745 3795376 : iter != base_regions.end (); ++iter)
3746 1822908 : vec_base_regions.quick_push (*iter);
3747 149560 : vec_base_regions.qsort (region::cmp_ptr_ptr);
3748 : unsigned i;
3749 : const region *base_reg;
3750 1455466 : FOR_EACH_VEC_ELT (vec_base_regions, i, base_reg)
3751 : {
3752 1264244 : const binding_cluster *cluster_a = store_a->get_cluster (base_reg);
3753 1264244 : const binding_cluster *cluster_b = store_b->get_cluster (base_reg);
3754 : /* At least one of cluster_a and cluster_b must be non-NULL. */
3755 1264244 : binding_cluster *out_cluster
3756 1264244 : = out_store->get_or_create_cluster (*mgr, base_reg);
3757 1264244 : if (!binding_cluster::can_merge_p (cluster_a, cluster_b,
3758 : out_cluster, out_store, mgr, merger))
3759 : return false;
3760 : }
3761 : return true;
3762 149560 : }
3763 :
3764 : /* Mark the cluster for BASE_REG as having escaped.
3765 : For use when handling an unrecognized function call, and
3766 : for params to "top-level" calls.
3767 : Further unknown function calls could touch it, even if the cluster
3768 : isn't reachable from args of those calls. */
3769 :
3770 : void
3771 37504 : store::mark_as_escaped (store_manager &mgr, const region *base_reg)
3772 : {
3773 37504 : gcc_assert (base_reg);
3774 37504 : gcc_assert (base_reg->get_base_region () == base_reg);
3775 :
3776 37504 : if (base_reg->symbolic_for_unknown_ptr_p ()
3777 37504 : || !base_reg->tracked_p ())
3778 5003 : return;
3779 :
3780 32501 : binding_cluster *cluster = get_or_create_cluster (mgr, base_reg);
3781 32501 : cluster->mark_as_escaped ();
3782 : }
3783 :
3784 : /* Handle an unknown fncall by updating any clusters that have escaped
3785 : (either in this fncall, or in a prior one). */
3786 :
3787 : void
3788 18151 : store::on_unknown_fncall (const gcall &call, store_manager *mgr,
3789 : const conjured_purge &p)
3790 : {
3791 18151 : m_called_unknown_fn = true;
3792 :
3793 142234 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3794 266317 : iter != m_cluster_map.end (); ++iter)
3795 124083 : (*iter).second->on_unknown_fncall (call, mgr, p);
3796 18151 : }
3797 :
3798 : /* Return true if a non-const pointer to BASE_REG (or something within it)
3799 : has escaped to code outside of the TU being analyzed. */
3800 :
3801 : bool
3802 9034886 : store::escaped_p (const region *base_reg) const
3803 : {
3804 9034886 : gcc_assert (base_reg);
3805 9034886 : gcc_assert (base_reg->get_base_region () == base_reg);
3806 :
3807 : /* "errno" can always be modified by external code. */
3808 9034886 : if (base_reg->get_kind () == RK_ERRNO)
3809 : return true;
3810 :
3811 17921604 : if (binding_cluster **cluster_slot
3812 8960802 : = const_cast <cluster_map_t &>(m_cluster_map).get (base_reg))
3813 8960802 : return (*cluster_slot)->escaped_p ();
3814 : return false;
3815 : }
3816 :
3817 : /* Populate OUT_PVS with a list of path_vars for describing SVAL based on
3818 : this store, using VISITED to ensure the traversal terminates. */
3819 :
3820 : void
3821 12811 : store::get_representative_path_vars (const region_model *model,
3822 : svalue_set *visited,
3823 : const svalue *sval,
3824 : logger *logger,
3825 : auto_vec<path_var> *out_pvs) const
3826 : {
3827 12811 : gcc_assert (sval);
3828 :
3829 : /* Find all bindings that reference SVAL. */
3830 58875 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3831 104939 : iter != m_cluster_map.end (); ++iter)
3832 : {
3833 46064 : const region *base_reg = (*iter).first;
3834 46064 : binding_cluster *cluster = (*iter).second;
3835 46064 : cluster->get_representative_path_vars (model, visited, base_reg, sval,
3836 : logger,
3837 : out_pvs);
3838 : }
3839 :
3840 12811 : if (const initial_svalue *init_sval = sval->dyn_cast_initial_svalue ())
3841 : {
3842 2305 : const region *reg = init_sval->get_region ();
3843 2305 : if (path_var pv = model->get_representative_path_var (reg,
3844 : visited,
3845 2305 : logger))
3846 2221 : out_pvs->safe_push (pv);
3847 : }
3848 12811 : }
3849 :
3850 : /* Remove all bindings overlapping REG within this store, removing
3851 : any clusters that become redundant.
3852 :
3853 : If UNCERTAINTY is non-NULL, use it to record any svalues that
3854 : were removed, as being maybe-bound. */
3855 :
3856 : void
3857 392754 : store::remove_overlapping_bindings (store_manager *mgr, const region *reg,
3858 : uncertainty_t *uncertainty)
3859 : {
3860 392754 : const region *base_reg = reg->get_base_region ();
3861 392754 : if (binding_cluster **cluster_slot = m_cluster_map.get (base_reg))
3862 : {
3863 74504 : binding_cluster *cluster = *cluster_slot;
3864 74504 : if (reg == base_reg && !escaped_p (base_reg))
3865 : {
3866 : /* Remove whole cluster. */
3867 46070 : m_cluster_map.remove (base_reg);
3868 92140 : delete cluster;
3869 46070 : return;
3870 : }
3871 : /* Pass nullptr for the maybe_live_values here, as we don't want to
3872 : record the old svalues as being maybe-bound. */
3873 28434 : cluster->remove_overlapping_bindings (mgr, reg, uncertainty, nullptr);
3874 : }
3875 : }
3876 :
3877 : /* Subclass of visitor that accumulates a hash_set of the regions that
3878 : were visited. */
3879 :
3880 1739956 : struct region_finder : public visitor
3881 : {
3882 47637618 : void visit_region (const region *reg) final override
3883 : {
3884 47637618 : m_regs.add (reg);
3885 47637618 : }
3886 :
3887 : hash_set<const region *> m_regs;
3888 : };
3889 :
3890 : /* Canonicalize this store, to maximize the chance of equality between
3891 : instances. */
3892 :
3893 : void
3894 869978 : store::canonicalize (store_manager *mgr)
3895 : {
3896 : /* If we have e.g.:
3897 : cluster for: HEAP_ALLOCATED_REGION(543)
3898 : ESCAPED
3899 : TOUCHED
3900 : where the heap region is empty and unreferenced, then purge that
3901 : cluster, to avoid unbounded state chains involving these. */
3902 :
3903 : /* Find regions that are referenced by bound values in the store. */
3904 869978 : region_finder s;
3905 7102938 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3906 13335898 : iter != m_cluster_map.end (); ++iter)
3907 : {
3908 6232960 : binding_cluster *cluster = (*iter).second;
3909 6232960 : for (binding_cluster::iterator_t bind_iter = cluster->m_map.begin ();
3910 13626446 : bind_iter != cluster->m_map.end (); ++bind_iter)
3911 7393486 : (*bind_iter).m_sval->accept (&s);
3912 : }
3913 :
3914 : /* Locate heap-allocated regions that have empty bindings that weren't
3915 : found above. */
3916 869978 : hash_set<const region *> purgeable_regions;
3917 7102938 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3918 13335898 : iter != m_cluster_map.end (); ++iter)
3919 : {
3920 6232960 : const region *base_reg = (*iter).first;
3921 6232960 : binding_cluster *cluster = (*iter).second;
3922 6232960 : if (base_reg->get_kind () == RK_HEAP_ALLOCATED)
3923 : {
3924 : /* Don't purge a heap-allocated region that's been marked as
3925 : escaping, since this could be recording that a ptr to it
3926 : was written to an unknown symbolic region along this
3927 : path, and so we don't know whether it's referenced or
3928 : not, and hence should report it as leaking
3929 : (PR analyzer/106473). */
3930 298600 : if (cluster->escaped_p ())
3931 113989 : continue;
3932 :
3933 184611 : if (cluster->empty_p ())
3934 450 : if (!s.m_regs.contains (base_reg))
3935 0 : purgeable_regions.add (base_reg);
3936 :
3937 : /* Also cover the UNKNOWN case. */
3938 184611 : if (const svalue *sval = cluster->maybe_get_simple_value (mgr))
3939 55326 : if (sval->get_kind () == SK_UNKNOWN)
3940 28783 : if (!s.m_regs.contains (base_reg))
3941 122 : purgeable_regions.add (base_reg);
3942 : }
3943 : }
3944 :
3945 : /* Purge them. */
3946 870100 : for (hash_set<const region *>::iterator iter = purgeable_regions.begin ();
3947 1740200 : iter != purgeable_regions.end (); ++iter)
3948 : {
3949 122 : const region *base_reg = *iter;
3950 122 : purge_cluster (base_reg);
3951 : }
3952 869978 : }
3953 :
3954 : static bool
3955 90696 : needs_loop_replay_fixup_p (const svalue &sval)
3956 : {
3957 90696 : struct my_visitor : public visitor
3958 : {
3959 90696 : my_visitor () : m_found_widening (false) {}
3960 :
3961 : void
3962 400 : visit_widening_svalue (const widening_svalue *) final override
3963 : {
3964 400 : m_found_widening = true;
3965 400 : }
3966 :
3967 : bool m_found_widening;
3968 90696 : } v;
3969 :
3970 90696 : sval.accept (&v);
3971 90696 : return v.m_found_widening;
3972 : }
3973 :
3974 : /* Subroutine for use by exploded_path::feasible_p.
3975 :
3976 : We need to deal with state differences between:
3977 : (a) when the exploded_graph is being initially constructed and
3978 : (b) when replaying the state changes along a specific path in
3979 : in exploded_path::feasible_p.
3980 :
3981 : In (a), state merging happens, so when exploring a loop
3982 : for (i = 0; i < 1024; i++)
3983 : on successive iterations we have i == 0, then i == WIDENING.
3984 :
3985 : In (b), no state merging happens, so naively replaying the path
3986 : that goes twice through the loop then exits it
3987 : would lead to i == 0, then i == 1, and then a (i >= 1024) eedge
3988 : that exits the loop, which would be found to be infeasible as i == 1,
3989 : and the path would be rejected.
3990 :
3991 : We need to fix up state during replay. This subroutine is
3992 : called whenever we enter a supernode that we've already
3993 : visited along this exploded_path, passing in OTHER_STORE
3994 : from the destination enode's state.
3995 :
3996 : Find bindings to widening values in OTHER_STORE.
3997 : For all that are found, update the binding in this store to UNKNOWN. */
3998 :
3999 : void
4000 4656 : store::loop_replay_fixup (const store *other_store,
4001 : region_model_manager *mgr)
4002 : {
4003 4656 : gcc_assert (other_store);
4004 34806 : for (cluster_map_t::iterator iter = other_store->m_cluster_map.begin ();
4005 64956 : iter != other_store->m_cluster_map.end (); ++iter)
4006 : {
4007 30150 : const region *base_reg = (*iter).first;
4008 30150 : binding_cluster *cluster = (*iter).second;
4009 120846 : for (binding_cluster::iterator_t bind_iter = cluster->m_map.begin ();
4010 120846 : bind_iter != cluster->m_map.end (); ++bind_iter)
4011 : {
4012 90696 : const binding_key *key = (*bind_iter).m_key;
4013 90696 : const svalue *sval = (*bind_iter).m_sval;
4014 90696 : if (needs_loop_replay_fixup_p (*sval))
4015 : {
4016 400 : binding_cluster *this_cluster
4017 400 : = get_or_create_cluster (*mgr->get_store_manager (),
4018 : base_reg);
4019 400 : const svalue *unknown
4020 400 : = mgr->get_or_create_unknown_svalue (sval->get_type ());
4021 400 : this_cluster->bind_key (key, unknown);
4022 : }
4023 : }
4024 : }
4025 4656 : }
4026 :
4027 : /* Use R to replay the bindings from SUMMARY into this object. */
4028 :
4029 : void
4030 1662 : store::replay_call_summary (call_summary_replay &r,
4031 : const store &summary)
4032 : {
4033 1662 : if (summary.m_called_unknown_fn)
4034 : {
4035 : /* A call to an external function occurred in the summary.
4036 : Hence we need to invalidate our knownledge of globals,
4037 : escaped regions, etc. */
4038 40 : on_unknown_fncall (r.get_call_stmt (),
4039 : r.get_store_manager (),
4040 40 : conjured_purge (r.get_caller_model (),
4041 40 : r.get_ctxt ()));
4042 : }
4043 :
4044 1662 : auto_vec<const region *> keys (summary.m_cluster_map.elements ());
4045 14135 : for (auto kv : summary.m_cluster_map)
4046 12473 : keys.quick_push (kv.first);
4047 1662 : keys.qsort (region::cmp_ptr_ptr);
4048 17451 : for (auto base_reg : keys)
4049 12473 : replay_call_summary_cluster (r, summary, base_reg);
4050 1662 : }
4051 :
4052 : /* Use R and SUMMARY to replay the bindings in SUMMARY_CLUSTER
4053 : into this object. */
4054 :
4055 : void
4056 12473 : store::replay_call_summary_cluster (call_summary_replay &r,
4057 : const store &summary,
4058 : const region *summary_base_reg)
4059 : {
4060 12473 : const call_details &cd = r.get_call_details ();
4061 12473 : region_model_manager *reg_mgr = r.get_manager ();
4062 12473 : store_manager *mgr = reg_mgr->get_store_manager ();
4063 12473 : const binding_cluster *summary_cluster
4064 12473 : = summary.get_cluster (summary_base_reg);
4065 :
4066 : /* Handle "ESCAPED" and "TOUCHED" flags. */
4067 12473 : if (summary_cluster->escaped_p () || summary_cluster->touched_p ())
4068 7748 : if (const region *caller_reg
4069 3874 : = r.convert_region_from_summary (summary_base_reg))
4070 : {
4071 3871 : const region *caller_base_reg = caller_reg->get_base_region ();
4072 3871 : if (caller_base_reg->tracked_p ()
4073 3871 : && !caller_base_reg->symbolic_for_unknown_ptr_p ())
4074 : {
4075 2944 : binding_cluster *caller_cluster
4076 2944 : = get_or_create_cluster (*mgr, caller_base_reg);
4077 2944 : if (summary_cluster->escaped_p ())
4078 2248 : caller_cluster->mark_as_escaped ();
4079 2944 : if (summary_cluster->touched_p ())
4080 1762 : caller_cluster->m_touched = true;
4081 : }
4082 : }
4083 :
4084 12473 : switch (summary_base_reg->get_kind ())
4085 : {
4086 : /* Top-level regions. */
4087 0 : case RK_FRAME:
4088 0 : case RK_GLOBALS:
4089 0 : case RK_CODE:
4090 0 : case RK_STACK:
4091 0 : case RK_HEAP:
4092 0 : case RK_THREAD_LOCAL:
4093 0 : case RK_ROOT:
4094 : /* Child regions. */
4095 0 : case RK_FIELD:
4096 0 : case RK_ELEMENT:
4097 0 : case RK_OFFSET:
4098 0 : case RK_SIZED:
4099 0 : case RK_CAST:
4100 0 : case RK_BIT_RANGE:
4101 : /* Other regions. */
4102 0 : case RK_VAR_ARG:
4103 0 : case RK_UNKNOWN:
4104 : /* These should never be the base region of a binding cluster. */
4105 0 : gcc_unreachable ();
4106 : break;
4107 :
4108 : case RK_FUNCTION:
4109 : case RK_LABEL:
4110 : case RK_STRING:
4111 : /* These can be marked as escaping. */
4112 : break;
4113 :
4114 2707 : case RK_SYMBOLIC:
4115 2707 : {
4116 2707 : const symbolic_region *summary_symbolic_reg
4117 2707 : = as_a <const symbolic_region *> (summary_base_reg);
4118 2707 : const svalue *summary_ptr_sval = summary_symbolic_reg->get_pointer ();
4119 2707 : const svalue *caller_ptr_sval
4120 2707 : = r.convert_svalue_from_summary (summary_ptr_sval);
4121 2707 : if (!caller_ptr_sval)
4122 : return;
4123 2293 : const region *caller_dest_reg
4124 2293 : = cd.get_model ()->deref_rvalue (caller_ptr_sval,
4125 : NULL_TREE,
4126 : cd.get_ctxt ());
4127 2293 : const svalue *summary_sval
4128 2293 : = summary.get_any_binding (mgr, summary_base_reg);
4129 2293 : if (!summary_sval)
4130 : return;
4131 1979 : const svalue *caller_sval
4132 1979 : = r.convert_svalue_from_summary (summary_sval);
4133 1979 : if (!caller_sval)
4134 2 : caller_sval =
4135 2 : reg_mgr->get_or_create_unknown_svalue (summary_sval->get_type ());
4136 1979 : set_value (mgr, caller_dest_reg,
4137 : caller_sval, nullptr /* uncertainty_t * */,
4138 1979 : *cd.get_model ());
4139 : }
4140 1979 : break;
4141 :
4142 9761 : case RK_HEAP_ALLOCATED:
4143 9761 : case RK_DECL:
4144 9761 : case RK_ERRNO:
4145 9761 : case RK_PRIVATE:
4146 9761 : {
4147 9761 : const region *caller_dest_reg
4148 9761 : = r.convert_region_from_summary (summary_base_reg);
4149 9761 : if (!caller_dest_reg)
4150 : return;
4151 9528 : const svalue *summary_sval
4152 9528 : = summary.get_any_binding (mgr, summary_base_reg);
4153 9528 : if (!summary_sval)
4154 187 : summary_sval = reg_mgr->get_or_create_compound_svalue
4155 187 : (summary_base_reg->get_type (),
4156 187 : summary_cluster->get_map ().get_concrete_bindings ());
4157 9528 : const svalue *caller_sval
4158 9528 : = r.convert_svalue_from_summary (summary_sval);
4159 9528 : if (!caller_sval)
4160 2 : caller_sval =
4161 2 : reg_mgr->get_or_create_unknown_svalue (summary_sval->get_type ());
4162 9528 : set_value (mgr, caller_dest_reg,
4163 : caller_sval, nullptr /* uncertainty_t * */,
4164 9528 : *cd.get_model ());
4165 : }
4166 9528 : break;
4167 :
4168 : case RK_ALLOCA:
4169 : /* Ignore bindings of alloca regions in the summary. */
4170 : break;
4171 : }
4172 : }
4173 :
4174 : #if CHECKING_P
4175 :
4176 : namespace selftest {
4177 :
4178 : /* Verify that bit_range::intersects_p works as expected. */
4179 :
4180 : static void
4181 4 : test_bit_range_intersects_p ()
4182 : {
4183 4 : bit_range b0 (0, 1);
4184 4 : bit_range b1 (1, 1);
4185 4 : bit_range b2 (2, 1);
4186 4 : bit_range b3 (3, 1);
4187 4 : bit_range b4 (4, 1);
4188 4 : bit_range b5 (5, 1);
4189 4 : bit_range b6 (6, 1);
4190 4 : bit_range b7 (7, 1);
4191 4 : bit_range b1_to_6 (1, 6);
4192 4 : bit_range b0_to_7 (0, 8);
4193 4 : bit_range b3_to_5 (3, 3);
4194 4 : bit_range b6_to_7 (6, 2);
4195 :
4196 : /* self-intersection is true. */
4197 4 : ASSERT_TRUE (b0.intersects_p (b0));
4198 4 : ASSERT_TRUE (b7.intersects_p (b7));
4199 4 : ASSERT_TRUE (b1_to_6.intersects_p (b1_to_6));
4200 4 : ASSERT_TRUE (b0_to_7.intersects_p (b0_to_7));
4201 :
4202 4 : ASSERT_FALSE (b0.intersects_p (b1));
4203 4 : ASSERT_FALSE (b1.intersects_p (b0));
4204 4 : ASSERT_FALSE (b0.intersects_p (b7));
4205 4 : ASSERT_FALSE (b7.intersects_p (b0));
4206 :
4207 4 : ASSERT_TRUE (b0_to_7.intersects_p (b0));
4208 4 : ASSERT_TRUE (b0_to_7.intersects_p (b7));
4209 4 : ASSERT_TRUE (b0.intersects_p (b0_to_7));
4210 4 : ASSERT_TRUE (b7.intersects_p (b0_to_7));
4211 :
4212 4 : ASSERT_FALSE (b0.intersects_p (b1_to_6));
4213 4 : ASSERT_FALSE (b1_to_6.intersects_p (b0));
4214 4 : ASSERT_TRUE (b1.intersects_p (b1_to_6));
4215 4 : ASSERT_TRUE (b1_to_6.intersects_p (b1));
4216 4 : ASSERT_TRUE (b1_to_6.intersects_p (b6));
4217 4 : ASSERT_FALSE (b1_to_6.intersects_p (b7));
4218 :
4219 4 : ASSERT_TRUE (b1_to_6.intersects_p (b0_to_7));
4220 4 : ASSERT_TRUE (b0_to_7.intersects_p (b1_to_6));
4221 :
4222 4 : ASSERT_FALSE (b3_to_5.intersects_p (b6_to_7));
4223 4 : ASSERT_FALSE (b6_to_7.intersects_p (b3_to_5));
4224 :
4225 4 : bit_range r1 (0,0);
4226 4 : bit_range r2 (0,0);
4227 4 : ASSERT_TRUE (b1_to_6.intersects_p (b0_to_7, &r1, &r2));
4228 4 : ASSERT_EQ (r1.get_start_bit_offset (), 0);
4229 4 : ASSERT_EQ (r1.m_size_in_bits, 6);
4230 4 : ASSERT_EQ (r2.get_start_bit_offset (), 1);
4231 4 : ASSERT_EQ (r2.m_size_in_bits, 6);
4232 :
4233 4 : ASSERT_TRUE (b0_to_7.intersects_p (b1_to_6, &r1, &r2));
4234 4 : ASSERT_EQ (r1.get_start_bit_offset (), 1);
4235 4 : ASSERT_EQ (r1.m_size_in_bits, 6);
4236 4 : ASSERT_EQ (r2.get_start_bit_offset (), 0);
4237 4 : ASSERT_EQ (r2.m_size_in_bits, 6);
4238 4 : }
4239 :
4240 : /* Implementation detail of ASSERT_BIT_RANGE_FROM_MASK_EQ. */
4241 :
4242 : static void
4243 76 : assert_bit_range_from_mask_eq (const location &loc,
4244 : unsigned HOST_WIDE_INT mask,
4245 : const bit_range &expected)
4246 : {
4247 76 : bit_range actual (0, 0);
4248 76 : bool ok = bit_range::from_mask (mask, &actual);
4249 76 : ASSERT_TRUE_AT (loc, ok);
4250 76 : ASSERT_EQ_AT (loc, actual, expected);
4251 76 : }
4252 :
4253 : /* Assert that bit_range::from_mask (MASK) returns true, and writes
4254 : out EXPECTED_BIT_RANGE. */
4255 :
4256 : #define ASSERT_BIT_RANGE_FROM_MASK_EQ(MASK, EXPECTED_BIT_RANGE) \
4257 : SELFTEST_BEGIN_STMT \
4258 : assert_bit_range_from_mask_eq (SELFTEST_LOCATION, MASK, \
4259 : EXPECTED_BIT_RANGE); \
4260 : SELFTEST_END_STMT
4261 :
4262 : /* Implementation detail of ASSERT_NO_BIT_RANGE_FROM_MASK. */
4263 :
4264 : static void
4265 12 : assert_no_bit_range_from_mask_eq (const location &loc,
4266 : unsigned HOST_WIDE_INT mask)
4267 : {
4268 12 : bit_range actual (0, 0);
4269 12 : bool ok = bit_range::from_mask (mask, &actual);
4270 12 : ASSERT_FALSE_AT (loc, ok);
4271 12 : }
4272 :
4273 : /* Assert that bit_range::from_mask (MASK) returns false. */
4274 :
4275 : #define ASSERT_NO_BIT_RANGE_FROM_MASK(MASK) \
4276 : SELFTEST_BEGIN_STMT \
4277 : assert_no_bit_range_from_mask_eq (SELFTEST_LOCATION, MASK); \
4278 : SELFTEST_END_STMT
4279 :
4280 : /* Verify that bit_range::from_mask works as expected. */
4281 :
4282 : static void
4283 4 : test_bit_range_from_mask ()
4284 : {
4285 : /* Should fail on zero. */
4286 4 : ASSERT_NO_BIT_RANGE_FROM_MASK (0);
4287 :
4288 : /* Verify 1-bit masks. */
4289 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (1, bit_range (0, 1));
4290 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (2, bit_range (1, 1));
4291 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (4, bit_range (2, 1));
4292 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (8, bit_range (3, 1));
4293 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (16, bit_range (4, 1));
4294 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (32, bit_range (5, 1));
4295 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (64, bit_range (6, 1));
4296 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (128, bit_range (7, 1));
4297 :
4298 : /* Verify N-bit masks starting at bit 0. */
4299 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (3, bit_range (0, 2));
4300 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (7, bit_range (0, 3));
4301 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (15, bit_range (0, 4));
4302 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (31, bit_range (0, 5));
4303 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (63, bit_range (0, 6));
4304 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (127, bit_range (0, 7));
4305 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (255, bit_range (0, 8));
4306 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (0xffff, bit_range (0, 16));
4307 :
4308 : /* Various other tests. */
4309 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (0x30, bit_range (4, 2));
4310 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (0x700, bit_range (8, 3));
4311 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (0x600, bit_range (9, 2));
4312 :
4313 : /* Multiple ranges of set bits should fail. */
4314 4 : ASSERT_NO_BIT_RANGE_FROM_MASK (0x101);
4315 4 : ASSERT_NO_BIT_RANGE_FROM_MASK (0xf0f0f0f0);
4316 4 : }
4317 :
4318 : /* Implementation detail of ASSERT_OVERLAP. */
4319 :
4320 : static void
4321 56 : assert_overlap (const location &loc,
4322 : const concrete_binding *b1,
4323 : const concrete_binding *b2)
4324 : {
4325 56 : ASSERT_TRUE_AT (loc, b1->overlaps_p (*b2));
4326 56 : ASSERT_TRUE_AT (loc, b2->overlaps_p (*b1));
4327 56 : }
4328 :
4329 : /* Implementation detail of ASSERT_DISJOINT. */
4330 :
4331 : static void
4332 20 : assert_disjoint (const location &loc,
4333 : const concrete_binding *b1,
4334 : const concrete_binding *b2)
4335 : {
4336 20 : ASSERT_FALSE_AT (loc, b1->overlaps_p (*b2));
4337 20 : ASSERT_FALSE_AT (loc, b2->overlaps_p (*b1));
4338 20 : }
4339 :
4340 : /* Assert that B1 and B2 overlap, checking both ways. */
4341 :
4342 : #define ASSERT_OVERLAP(B1, B2) \
4343 : SELFTEST_BEGIN_STMT \
4344 : assert_overlap (SELFTEST_LOCATION, B1, B2); \
4345 : SELFTEST_END_STMT
4346 :
4347 : /* Assert that B1 and B2 do not overlap, checking both ways. */
4348 :
4349 : #define ASSERT_DISJOINT(B1, B2) \
4350 : SELFTEST_BEGIN_STMT \
4351 : assert_disjoint (SELFTEST_LOCATION, B1, B2); \
4352 : SELFTEST_END_STMT
4353 :
4354 : /* Verify that concrete_binding::overlaps_p works as expected. */
4355 :
4356 : static void
4357 4 : test_binding_key_overlap ()
4358 : {
4359 4 : store_manager mgr (nullptr);
4360 :
4361 : /* Various 8-bit bindings. */
4362 4 : const concrete_binding *cb_0_7 = mgr.get_concrete_binding (0, 8);
4363 4 : const concrete_binding *cb_8_15 = mgr.get_concrete_binding (8, 8);
4364 4 : const concrete_binding *cb_16_23 = mgr.get_concrete_binding (16, 8);
4365 4 : const concrete_binding *cb_24_31 = mgr.get_concrete_binding (24, 8);
4366 :
4367 : /* 16-bit bindings. */
4368 4 : const concrete_binding *cb_0_15 = mgr.get_concrete_binding (0, 16);
4369 4 : const concrete_binding *cb_8_23 = mgr.get_concrete_binding (8, 16);
4370 4 : const concrete_binding *cb_16_31 = mgr.get_concrete_binding (16, 16);
4371 :
4372 : /* 32-bit binding. */
4373 4 : const concrete_binding *cb_0_31 = mgr.get_concrete_binding (0, 32);
4374 :
4375 : /* Everything should self-overlap. */
4376 4 : ASSERT_OVERLAP (cb_0_7, cb_0_7);
4377 4 : ASSERT_OVERLAP (cb_8_15, cb_8_15);
4378 4 : ASSERT_OVERLAP (cb_16_23, cb_16_23);
4379 4 : ASSERT_OVERLAP (cb_24_31, cb_24_31);
4380 4 : ASSERT_OVERLAP (cb_0_15, cb_0_15);
4381 4 : ASSERT_OVERLAP (cb_8_23, cb_8_23);
4382 4 : ASSERT_OVERLAP (cb_16_31, cb_16_31);
4383 4 : ASSERT_OVERLAP (cb_0_31, cb_0_31);
4384 :
4385 : /* Verify the 8-bit bindings that don't overlap each other. */
4386 4 : ASSERT_DISJOINT (cb_0_7, cb_8_15);
4387 4 : ASSERT_DISJOINT (cb_8_15, cb_16_23);
4388 :
4389 : /* Check for overlap of differently-sized bindings. */
4390 4 : ASSERT_OVERLAP (cb_0_7, cb_0_31);
4391 : /* ...and with differing start points. */
4392 4 : ASSERT_OVERLAP (cb_8_15, cb_0_31);
4393 4 : ASSERT_DISJOINT (cb_8_15, cb_16_31);
4394 4 : ASSERT_OVERLAP (cb_16_23, cb_0_31);
4395 4 : ASSERT_OVERLAP (cb_16_31, cb_0_31);
4396 :
4397 4 : ASSERT_DISJOINT (cb_0_7, cb_8_23);
4398 4 : ASSERT_OVERLAP (cb_8_23, cb_16_23);
4399 4 : ASSERT_OVERLAP (cb_8_23, cb_16_31);
4400 4 : ASSERT_DISJOINT (cb_8_23, cb_24_31);
4401 4 : }
4402 :
4403 : static void
4404 4 : test_binding_map_ops ()
4405 : {
4406 4 : region_model_manager region_mgr;
4407 4 : store_manager store_mgr (®ion_mgr);
4408 :
4409 : /* Assignment of empty. */
4410 4 : {
4411 4 : binding_map src (store_mgr);
4412 4 : binding_map dst (store_mgr);
4413 4 : dst = src;
4414 :
4415 4 : ASSERT_EQ (src, dst);
4416 4 : }
4417 4 : }
4418 :
4419 : /* Run all of the selftests within this file. */
4420 :
4421 : void
4422 4 : analyzer_store_cc_tests ()
4423 : {
4424 4 : test_bit_range_intersects_p ();
4425 4 : test_bit_range_from_mask ();
4426 4 : test_binding_key_overlap ();
4427 4 : test_binding_map_ops ();
4428 4 : }
4429 :
4430 : } // namespace selftest
4431 :
4432 : #endif /* CHECKING_P */
4433 :
4434 : } // namespace ana
4435 :
4436 : #endif /* #if ENABLE_ANALYZER */
|
