Branch data Line data Source code
1 : : /* Classes for modeling the state of memory.
2 : : Copyright (C) 2020-2025 Free Software Foundation, Inc.
3 : : Contributed by David Malcolm <dmalcolm@redhat.com>.
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify it
8 : : under the terms of the GNU General Public License as published by
9 : : the Free Software Foundation; either version 3, or (at your option)
10 : : any later version.
11 : :
12 : : GCC is distributed in the hope that it will be useful, but
13 : : WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : : General Public License for more details.
16 : :
17 : : You should have received a copy of the GNU General Public License
18 : : along with GCC; see the file COPYING3. If not see
19 : : <http://www.gnu.org/licenses/>. */
20 : :
21 : : #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 : 496 : dump_svalue_set (const hash_set <const svalue *> &svals,
47 : : pretty_printer *pp, bool simple)
48 : : {
49 : 496 : auto_vec <const svalue *> v;
50 : 496 : for (hash_set<const svalue *>::iterator iter = svals.begin ();
51 : 560 : iter != svals.end (); ++iter)
52 : : {
53 : 32 : v.safe_push (*iter);
54 : : }
55 : 496 : v.qsort (svalue::cmp_ptr_ptr);
56 : :
57 : 496 : pp_character (pp, '{');
58 : 496 : const svalue *sval;
59 : 496 : unsigned i;
60 : 1024 : FOR_EACH_VEC_ELT (v, i, sval)
61 : : {
62 : 32 : if (i > 0)
63 : 19 : pp_string (pp, ", ");
64 : 32 : sval->dump_to_pp (pp, simple);
65 : : }
66 : 496 : pp_character (pp, '}');
67 : 496 : }
68 : :
69 : : /* class uncertainty_t. */
70 : :
71 : : /* Dump this object to PP. */
72 : :
73 : : void
74 : 248 : uncertainty_t::dump_to_pp (pretty_printer *pp, bool simple) const
75 : : {
76 : 248 : pp_string (pp, "{m_maybe_bound_svals: ");
77 : 248 : dump_svalue_set (m_maybe_bound_svals, pp, simple);
78 : :
79 : 248 : pp_string (pp, ", m_mutable_at_unknown_call_svals: ");
80 : 248 : dump_svalue_set (m_mutable_at_unknown_call_svals, pp, simple);
81 : 248 : pp_string (pp, "}");
82 : 248 : }
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 : 3515955 : binding_key::make (store_manager *mgr, const region *r)
98 : : {
99 : 3515955 : region_offset offset = r->get_offset (mgr->get_svalue_manager ());
100 : 3515955 : if (offset.symbolic_p ())
101 : 36504 : return mgr->get_symbolic_binding (r);
102 : : else
103 : : {
104 : 3479451 : bit_size_t bit_size;
105 : 3479451 : if (r->get_bit_size (&bit_size))
106 : : {
107 : : /* Must be non-empty. */
108 : 2188267 : gcc_assert (bit_size > 0);
109 : 2188267 : return mgr->get_concrete_binding (offset.get_bit_offset (),
110 : 2188267 : bit_size);
111 : : }
112 : : else
113 : 1291184 : 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 : 1668 : binding_key::cmp_ptrs (const void *p1, const void *p2)
142 : : {
143 : 1668 : const binding_key * const *pk1 = (const binding_key * const *)p1;
144 : 1668 : const binding_key * const *pk2 = (const binding_key * const *)p2;
145 : 1668 : return cmp (*pk1, *pk2);
146 : : }
147 : :
148 : : /* Comparator for binding_keys. */
149 : :
150 : : int
151 : 1720 : binding_key::cmp (const binding_key *k1, const binding_key *k2)
152 : : {
153 : 1720 : int concrete1 = k1->concrete_p ();
154 : 1720 : int concrete2 = k2->concrete_p ();
155 : 1720 : if (int concrete_cmp = concrete1 - concrete2)
156 : : return concrete_cmp;
157 : 1720 : if (concrete1)
158 : : {
159 : 1720 : const concrete_binding *b1 = (const concrete_binding *)k1;
160 : 1720 : const concrete_binding *b2 = (const concrete_binding *)k2;
161 : 1720 : if (int start_cmp = wi::cmp (b1->get_start_bit_offset (),
162 : 1720 : b2->get_start_bit_offset (),
163 : : SIGNED))
164 : : return start_cmp;
165 : 52 : 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 : 2611 : bit_range::dump_to_pp (pretty_printer *pp) const
184 : : {
185 : 2611 : byte_range bytes (0, 0);
186 : 2611 : if (as_byte_range (&bytes))
187 : 2611 : 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 : 2611 : }
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 : 35801 : bit_range::contains_p (const bit_range &other, bit_range *out) const
230 : : {
231 : 35801 : if (contains_p (other.get_start_bit_offset ())
232 : 35801 : && contains_p (other.get_last_bit_offset ()))
233 : : {
234 : 22763 : if (out)
235 : : {
236 : 22763 : out->m_start_bit_offset = other.m_start_bit_offset - m_start_bit_offset;
237 : 22763 : out->m_size_in_bits = other.m_size_in_bits;
238 : : }
239 : 22763 : return true;
240 : : }
241 : : else
242 : 13038 : 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 : 644790 : bit_range::exceeds_p (const bit_range &other,
309 : : bit_range *out_overhanging_bit_range) const
310 : : {
311 : 644790 : gcc_assert (!empty_p ());
312 : :
313 : 644790 : if (other.get_next_bit_offset () < get_next_bit_offset ())
314 : : {
315 : : /* THIS definitely exceeds OTHER. */
316 : 487 : bit_offset_t start = MAX (get_start_bit_offset (),
317 : : other.get_next_bit_offset ());
318 : 487 : bit_offset_t size = get_next_bit_offset () - start;
319 : 487 : 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 : 467 : out_overhanging_bit_range->m_start_bit_offset = start;
324 : 467 : out_overhanging_bit_range->m_size_in_bits = size;
325 : 467 : 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 : 648354 : bit_range::falls_short_of_p (bit_offset_t offset,
336 : : bit_range *out_fall_short_bits) const
337 : : {
338 : 648354 : gcc_assert (!empty_p ());
339 : :
340 : 648354 : if (get_start_bit_offset () < offset)
341 : : {
342 : : /* THIS falls short of OFFSET. */
343 : 192 : bit_offset_t start = get_start_bit_offset ();
344 : 192 : bit_offset_t size = MIN (offset, get_next_bit_offset ()) - start;
345 : 192 : 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 : 172 : out_fall_short_bits->m_start_bit_offset = start;
350 : 172 : out_fall_short_bits->m_size_in_bits = size;
351 : 172 : return true;
352 : : }
353 : : else
354 : : return false;
355 : : }
356 : :
357 : : int
358 : 1198 : bit_range::cmp (const bit_range &br1, const bit_range &br2)
359 : : {
360 : 1198 : if (int start_cmp = wi::cmps (br1.m_start_bit_offset,
361 : 1198 : br2.m_start_bit_offset))
362 : : return start_cmp;
363 : :
364 : 12 : 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 : 8228 : bit_range::as_byte_range (byte_range *out) const
439 : : {
440 : 8228 : if (m_start_bit_offset % BITS_PER_UNIT == 0
441 : 8228 : && m_size_in_bits % BITS_PER_UNIT == 0)
442 : : {
443 : 8207 : out->m_start_byte_offset = m_start_bit_offset / BITS_PER_UNIT;
444 : 8207 : out->m_size_in_bytes = m_size_in_bits / BITS_PER_UNIT;
445 : 8207 : return true;
446 : : }
447 : : return false;
448 : : }
449 : :
450 : : /* Dump this object to PP. */
451 : :
452 : : void
453 : 2611 : byte_range::dump_to_pp (pretty_printer *pp) const
454 : : {
455 : 2611 : if (m_size_in_bytes == 0)
456 : : {
457 : 0 : pp_string (pp, "empty");
458 : : }
459 : 2611 : else if (m_size_in_bytes == 1)
460 : : {
461 : 1595 : pp_string (pp, "byte ");
462 : 1595 : pp_wide_int (pp, m_start_byte_offset, SIGNED);
463 : : }
464 : : else
465 : : {
466 : 1016 : pp_string (pp, "bytes ");
467 : 1016 : pp_wide_int (pp, m_start_byte_offset, SIGNED);
468 : 1016 : pp_string (pp, "-");
469 : 1016 : pp_wide_int (pp, get_last_byte_offset (), SIGNED);
470 : : }
471 : 2611 : }
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 : 803 : byte_range::contains_p (const byte_range &other, byte_range *out) const
504 : : {
505 : 803 : if (contains_p (other.get_start_byte_offset ())
506 : 803 : && contains_p (other.get_last_byte_offset ()))
507 : : {
508 : 330 : out->m_start_byte_offset = other.m_start_byte_offset - m_start_byte_offset;
509 : 330 : out->m_size_in_bytes = other.m_size_in_bytes;
510 : 330 : return true;
511 : : }
512 : : else
513 : 473 : return false;
514 : : }
515 : :
516 : : /* qsort comparator for byte ranges. */
517 : :
518 : : int
519 : 571 : byte_range::cmp (const byte_range &br1, const byte_range &br2)
520 : : {
521 : : /* Order first by offset. */
522 : 571 : if (int start_cmp = wi::cmps (br1.m_start_byte_offset,
523 : 571 : 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 : 1648 : concrete_binding::dump_to_pp (pretty_printer *pp, bool) const
536 : : {
537 : 1648 : m_bit_range.dump_to_pp (pp);
538 : 1648 : }
539 : :
540 : : /* Return true if this binding overlaps with OTHER. */
541 : :
542 : : bool
543 : 91470 : concrete_binding::overlaps_p (const concrete_binding &other) const
544 : : {
545 : 91470 : if (get_start_bit_offset () < other.get_next_bit_offset ()
546 : 91470 : && get_next_bit_offset () > other.get_start_bit_offset ())
547 : 53628 : 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 : 683 : concrete_binding::get_byte_range (byte_range *out) const
556 : : {
557 : 683 : return m_bit_range.as_byte_range (out);
558 : : }
559 : :
560 : : /* Comparator for use by vec<const concrete_binding *>::qsort. */
561 : :
562 : : int
563 : 48 : concrete_binding::cmp_ptr_ptr (const void *p1, const void *p2)
564 : : {
565 : 48 : const concrete_binding *b1 = *(const concrete_binding * const *)p1;
566 : 48 : const concrete_binding *b2 = *(const concrete_binding * const *)p2;
567 : :
568 : 48 : 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 : 2 : symbolic_binding::dump_to_pp (pretty_printer *pp, bool simple) const
575 : : {
576 : : //binding_key::dump_to_pp (pp, simple);
577 : 2 : pp_string (pp, "region: ");
578 : 2 : m_region->dump_to_pp (pp, simple);
579 : 2 : }
580 : :
581 : : /* Comparator for use by vec<const symbolic_binding *>::qsort. */
582 : :
583 : : int
584 : 4 : symbolic_binding::cmp_ptr_ptr (const void *p1, const void *p2)
585 : : {
586 : 4 : const symbolic_binding *b1 = *(const symbolic_binding * const *)p1;
587 : 4 : const symbolic_binding *b2 = *(const symbolic_binding * const *)p2;
588 : :
589 : 4 : 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 : 383707 : simplify_for_binding (const svalue *sval)
615 : : {
616 : 383707 : if (const svalue *cast_sval = sval->maybe_undo_cast ())
617 : 0 : sval = cast_sval;
618 : 58920 : return sval;
619 : : }
620 : :
621 : : /* class binding_map::const_iterator. */
622 : :
623 : : bool
624 : 67836568 : binding_map::const_iterator::operator== (const binding_map::const_iterator &other) const
625 : : {
626 : 67836568 : if (m_concrete != other.m_concrete)
627 : : return false;
628 : 36149045 : if (m_symbolic != other.m_symbolic)
629 : 3013217 : return false;
630 : : return true;
631 : : }
632 : :
633 : : binding_map::const_iterator &
634 : 34687794 : binding_map::const_iterator::operator++ ()
635 : : {
636 : 34687794 : if (m_concrete != m_map.m_concrete.end ())
637 : 31674577 : ++m_concrete;
638 : : else
639 : 3013217 : ++m_symbolic;
640 : 34687794 : return *this;
641 : : }
642 : :
643 : : binding_map::binding_pair
644 : 34700740 : binding_map::const_iterator::operator* ()
645 : : {
646 : 34700740 : if (m_concrete != m_map.m_concrete.end ())
647 : : {
648 : 31687523 : const bit_range &bits = m_concrete->first;
649 : 31687523 : const svalue *sval = m_concrete->second;
650 : 31687523 : return binding_pair (m_map.m_store_mgr.get_concrete_binding (bits), sval);
651 : : }
652 : : else
653 : : {
654 : 3013217 : gcc_assert (m_symbolic != m_map.m_symbolic.end ());
655 : 3013217 : const region *reg = m_symbolic->m_region;
656 : 3013217 : const svalue *sval = m_symbolic->m_sval;
657 : 3013217 : return binding_pair (m_map.m_store_mgr.get_symbolic_binding (reg), sval);
658 : : }
659 : : }
660 : :
661 : : /* class binding_map::iterator. */
662 : :
663 : : bool
664 : 13741330 : binding_map::iterator::operator== (const binding_map::iterator &other) const
665 : : {
666 : 13741330 : if (m_concrete != other.m_concrete)
667 : : return false;
668 : 7353995 : if (m_symbolic != other.m_symbolic)
669 : 641020 : return false;
670 : : return true;
671 : : }
672 : :
673 : : binding_map::iterator &
674 : 7026973 : binding_map::iterator::operator++ ()
675 : : {
676 : 7026973 : if (m_concrete != m_map.m_concrete.end ())
677 : 6385962 : ++m_concrete;
678 : : else
679 : 641011 : ++m_symbolic;
680 : 7026973 : return *this;
681 : : }
682 : :
683 : : binding_map::binding_pair
684 : 7106573 : binding_map::iterator::operator* ()
685 : : {
686 : 7106573 : if (m_concrete != m_map.m_concrete.end ())
687 : : {
688 : 6453831 : const bit_range &bits = m_concrete->first;
689 : 6453831 : const svalue *&sval = m_concrete->second;
690 : 6453831 : return binding_pair (m_map.m_store_mgr.get_concrete_binding (bits), sval);
691 : : }
692 : : else
693 : : {
694 : 652742 : gcc_assert (m_symbolic != m_map.m_symbolic.end ());
695 : 652742 : const region *reg = m_symbolic->m_region;
696 : 652742 : const svalue *&sval = m_symbolic->m_sval;
697 : 652742 : return binding_pair (m_map.m_store_mgr.get_symbolic_binding (reg), sval);
698 : : }
699 : : }
700 : :
701 : : /* class binding_map. */
702 : :
703 : : // Construct an empty binding_map.
704 : :
705 : 1684906 : binding_map::binding_map (store_manager &store_mgr)
706 : 1684906 : : m_store_mgr (store_mgr),
707 : 1684906 : m_concrete (),
708 : 1684906 : m_symbolic ()
709 : : {
710 : 1684906 : }
711 : :
712 : : /* binding_map's copy ctor. */
713 : :
714 : 24199947 : binding_map::binding_map (const binding_map &other)
715 : 24199947 : : m_store_mgr (other.m_store_mgr),
716 : 24199947 : m_concrete (other.m_concrete),
717 : 24199947 : m_symbolic (other.m_symbolic)
718 : : {
719 : 24199947 : }
720 : :
721 : : /* binding_map's assignment operator. */
722 : :
723 : : binding_map&
724 : 4 : binding_map::operator= (const binding_map &other)
725 : : {
726 : 4 : gcc_assert (&m_store_mgr == &other.m_store_mgr);
727 : :
728 : : /* For now, assume we only ever copy to an empty cluster. */
729 : 4 : gcc_assert (m_concrete.size () == 0);
730 : 4 : gcc_assert (m_symbolic.size () == 0);
731 : :
732 : 4 : m_concrete = other.m_concrete;
733 : 4 : m_symbolic = other.m_symbolic;
734 : :
735 : 4 : return *this;
736 : : }
737 : :
738 : : /* binding_map's equality operator. */
739 : :
740 : : bool
741 : 2036396 : binding_map::operator== (const binding_map &other) const
742 : : {
743 : 2036396 : if (m_concrete != other.m_concrete)
744 : : return false;
745 : 1993282 : if (m_symbolic != other.m_symbolic)
746 : : return false;
747 : :
748 : : return true;
749 : : }
750 : :
751 : : /* Generate a hash value for this binding_map. */
752 : :
753 : : hashval_t
754 : 14097422 : binding_map::hash () const
755 : : {
756 : 14097422 : hashval_t result = 0;
757 : 28591026 : for (auto iter : *this)
758 : : {
759 : : /* Use a new hasher for each key to avoid depending on the ordering
760 : : of keys when accumulating the result. */
761 : 14493604 : inchash::hash hstate;
762 : 14493604 : hstate.add_ptr (iter.m_key);
763 : 14493604 : hstate.add_ptr (iter.m_sval);
764 : 14493604 : result ^= hstate.end ();
765 : : }
766 : 14097422 : return result;
767 : : }
768 : :
769 : : const svalue *
770 : 4071360 : binding_map::get (const binding_key *key) const
771 : : {
772 : 4071360 : if (key->symbolic_p ())
773 : : {
774 : 470908 : const ana::symbolic_binding &sym_key
775 : : = *static_cast <const ana::symbolic_binding *> (key);
776 : 470908 : const region *reg = sym_key.get_region ();
777 : :
778 : 539013 : for (auto iter : m_symbolic)
779 : : {
780 : 366045 : if (iter.m_region == reg)
781 : 4071360 : return iter.m_sval;
782 : : }
783 : : return nullptr;
784 : : }
785 : : else
786 : : {
787 : 3600452 : const concrete_binding &conc_key
788 : : = *static_cast <const concrete_binding *> (key);
789 : 3600452 : const bit_range &bits = conc_key.get_bit_range ();
790 : :
791 : 3600452 : concrete_bindings_t::const_iterator iter (m_concrete.find (bits));
792 : 3600452 : if (iter != m_concrete.end ())
793 : 3235041 : return iter->second;
794 : : else
795 : : return nullptr;
796 : : }
797 : : }
798 : :
799 : : void
800 : 1729593 : binding_map::put (const binding_key *key, const svalue *sval)
801 : : {
802 : 1729593 : if (key->symbolic_p ())
803 : : {
804 : 147665 : const ana::symbolic_binding &sym_key
805 : : = *static_cast <const ana::symbolic_binding *> (key);
806 : 147665 : const region *reg = sym_key.get_region ();
807 : :
808 : 147665 : m_symbolic.clear ();
809 : :
810 : 147665 : m_symbolic.push_back ({reg, sval});
811 : : }
812 : : else
813 : : {
814 : 1581928 : const concrete_binding &conc_key
815 : : = *static_cast <const concrete_binding *> (key);
816 : 1581928 : const bit_range &bits = conc_key.get_bit_range ();
817 : :
818 : 1581928 : concrete_bindings_t::iterator iter (m_concrete.find (bits));
819 : 1581928 : if (iter != m_concrete.end ())
820 : 5813 : (*iter).second = sval;
821 : : else
822 : 1576115 : m_concrete.insert ({bits, sval});
823 : : }
824 : 1729593 : }
825 : :
826 : : void
827 : 142 : binding_map::overwrite (iterator_t &pos, const svalue *v)
828 : : {
829 : 142 : gcc_assert (&pos.m_map == this);
830 : 142 : if (pos.m_symbolic != m_symbolic.end ())
831 : 0 : (*(pos.m_symbolic)).m_sval = v;
832 : : else
833 : : {
834 : 142 : gcc_assert (pos.m_concrete != m_concrete.end ());
835 : 142 : (*(pos.m_concrete)).second = v;
836 : : }
837 : 142 : }
838 : :
839 : : void
840 : 264910 : binding_map::remove (const binding_key *key)
841 : : {
842 : 264910 : if (key->symbolic_p ())
843 : 14676 : m_symbolic.clear ();
844 : : else
845 : : {
846 : 250234 : const concrete_binding &conc_key
847 : : = *static_cast <const concrete_binding *> (key);
848 : 250234 : const bit_range &bits = conc_key.get_bit_range ();
849 : 250234 : m_concrete.erase (bits);
850 : : }
851 : 264910 : }
852 : :
853 : : binding_map::const_iterator_t
854 : 33148774 : binding_map::begin () const
855 : : {
856 : 33148774 : return binding_map::const_iterator_t (*this,
857 : : m_concrete.begin (),
858 : 33148774 : m_symbolic.begin ());
859 : : }
860 : :
861 : : binding_map::const_iterator_t
862 : 33163694 : binding_map::end () const
863 : : {
864 : 33163694 : return binding_map::const_iterator_t (*this,
865 : : m_concrete.end (),
866 : 33163694 : m_symbolic.end ());
867 : : }
868 : :
869 : : binding_map::iterator_t
870 : 6714357 : binding_map::begin ()
871 : : {
872 : 6714357 : return binding_map::iterator_t (*this,
873 : : m_concrete.begin (),
874 : 6714357 : m_symbolic.begin ());
875 : : }
876 : :
877 : : binding_map::iterator_t
878 : 13020579 : binding_map::end ()
879 : : {
880 : 13020579 : return binding_map::iterator_t (*this,
881 : : m_concrete.end (),
882 : 13020579 : m_symbolic.end ());
883 : : }
884 : :
885 : : size_t
886 : 679521 : binding_map::elements () const
887 : : {
888 : 679521 : return m_concrete.size () + m_symbolic.size ();
889 : : }
890 : :
891 : : /* Dump a representation of this binding_map to PP.
892 : : SIMPLE controls how values and regions are to be printed.
893 : : If MULTILINE, then split the dump over multiple lines and
894 : : use whitespace for readability, otherwise put all on one line. */
895 : :
896 : : void
897 : 2257 : binding_map::dump_to_pp (pretty_printer *pp, bool simple,
898 : : bool multiline) const
899 : : {
900 : 2257 : bool first = true;
901 : 3900 : for (auto iter : *this)
902 : : {
903 : 1643 : const binding_key *key = iter.m_key;
904 : 1643 : const svalue *value = iter.m_sval;
905 : 1643 : if (multiline)
906 : : {
907 : 328 : pp_string (pp, " key: {");
908 : 328 : key->dump_to_pp (pp, simple);
909 : 328 : pp_string (pp, "}");
910 : 328 : pp_newline (pp);
911 : 328 : pp_string (pp, " value: ");
912 : 328 : if (tree t = value->get_type ())
913 : 328 : dump_quoted_tree (pp, t);
914 : 328 : pp_string (pp, " {");
915 : 328 : value->dump_to_pp (pp, simple);
916 : 328 : pp_string (pp, "}");
917 : 328 : pp_newline (pp);
918 : : }
919 : : else
920 : : {
921 : 1315 : if (first)
922 : : first = false;
923 : : else
924 : 566 : pp_string (pp, ", ");
925 : 1315 : pp_string (pp, "binding key: {");
926 : 1315 : key->dump_to_pp (pp, simple);
927 : 1315 : pp_string (pp, "}, value: {");
928 : 1315 : value->dump_to_pp (pp, simple);
929 : 1315 : pp_string (pp, "}");
930 : : }
931 : : }
932 : 2257 : }
933 : :
934 : : /* Dump a multiline representation of this binding_map to stderr. */
935 : :
936 : : DEBUG_FUNCTION void
937 : 0 : binding_map::dump (bool simple) const
938 : : {
939 : 0 : tree_dump_pretty_printer pp (stderr);
940 : 0 : dump_to_pp (&pp, simple, true);
941 : 0 : pp_newline (&pp);
942 : 0 : }
943 : :
944 : : /* Return a new json::object of the form
945 : : {KEY_DESC : SVALUE_DESC,
946 : : ...for the various key/value pairs in this binding_map}. */
947 : :
948 : : std::unique_ptr<json::object>
949 : 0 : binding_map::to_json () const
950 : : {
951 : 0 : auto map_obj = std::make_unique<json::object> ();
952 : :
953 : 0 : for (auto iter : *this)
954 : : {
955 : 0 : const svalue *value = iter.m_sval;
956 : 0 : label_text key_desc = iter.m_key->get_desc ();
957 : 0 : map_obj->set (key_desc.get (), value->to_json ());
958 : 0 : }
959 : :
960 : 0 : return map_obj;
961 : : }
962 : :
963 : : /* Add a child to PARENT_WIDGET expressing a binding between
964 : : KEY and SVAL. */
965 : :
966 : : static void
967 : 0 : add_binding_to_tree_widget (text_art::tree_widget &parent_widget,
968 : : const text_art::dump_widget_info &dwi,
969 : : const binding_key *key,
970 : : const svalue *sval)
971 : : {
972 : 0 : pretty_printer the_pp;
973 : 0 : pretty_printer * const pp = &the_pp;
974 : 0 : pp_format_decoder (pp) = default_tree_printer;
975 : 0 : pp_show_color (pp) = true;
976 : 0 : const bool simple = true;
977 : :
978 : 0 : key->dump_to_pp (pp, simple);
979 : 0 : pp_string (pp, ": ");
980 : 0 : if (tree t = sval->get_type ())
981 : 0 : dump_quoted_tree (pp, t);
982 : 0 : pp_string (pp, " {");
983 : 0 : sval->dump_to_pp (pp, simple);
984 : 0 : pp_string (pp, "}");
985 : :
986 : 0 : parent_widget.add_child (text_art::tree_widget::make (dwi, pp));
987 : 0 : }
988 : :
989 : : void
990 : 0 : binding_map::add_to_tree_widget (text_art::tree_widget &parent_widget,
991 : : const text_art::dump_widget_info &dwi) const
992 : : {
993 : 0 : for (auto iter : *this)
994 : : {
995 : 0 : const binding_key *key = iter.m_key;
996 : 0 : const svalue *sval = iter.m_sval;
997 : 0 : add_binding_to_tree_widget (parent_widget, dwi,
998 : : key, sval);
999 : : }
1000 : 0 : }
1001 : :
1002 : :
1003 : : /* Comparator for imposing an order on binding_maps. */
1004 : :
1005 : : int
1006 : 52 : binding_map::cmp (const binding_map &map1, const binding_map &map2)
1007 : : {
1008 : 52 : if (int count_cmp = map1.elements () - map2.elements ())
1009 : : return count_cmp;
1010 : :
1011 : 52 : auto_vec <const binding_key *> keys1 (map1.elements ());
1012 : 104 : for (auto iter : map1)
1013 : 52 : keys1.quick_push (iter.m_key);
1014 : 52 : keys1.qsort (binding_key::cmp_ptrs);
1015 : :
1016 : 52 : auto_vec <const binding_key *> keys2 (map2.elements ());
1017 : 104 : for (auto iter : map2)
1018 : 52 : keys2.quick_push (iter.m_key);
1019 : 52 : keys2.qsort (binding_key::cmp_ptrs);
1020 : :
1021 : 104 : for (size_t i = 0; i < keys1.length (); i++)
1022 : : {
1023 : 52 : const binding_key *k1 = keys1[i];
1024 : 52 : const binding_key *k2 = keys2[i];
1025 : 52 : if (int key_cmp = binding_key::cmp (k1, k2))
1026 : : return key_cmp;
1027 : 52 : gcc_assert (k1 == k2);
1028 : 52 : if (int sval_cmp = svalue::cmp_ptr (map1.get (k1), map2.get (k2)))
1029 : : return sval_cmp;
1030 : : }
1031 : :
1032 : : return 0;
1033 : 52 : }
1034 : :
1035 : : /* Get the child region of PARENT_REG based upon INDEX within a
1036 : : CONSTRUCTOR. */
1037 : :
1038 : : static const region *
1039 : 548 : get_subregion_within_ctor (const region *parent_reg, tree index,
1040 : : region_model_manager *mgr)
1041 : : {
1042 : 548 : switch (TREE_CODE (index))
1043 : : {
1044 : 0 : default:
1045 : 0 : gcc_unreachable ();
1046 : 412 : case INTEGER_CST:
1047 : 412 : {
1048 : 412 : const svalue *index_sval
1049 : 412 : = mgr->get_or_create_constant_svalue (index);
1050 : 412 : return mgr->get_element_region (parent_reg,
1051 : 412 : TREE_TYPE (parent_reg->get_type ()),
1052 : 412 : index_sval);
1053 : : }
1054 : 136 : break;
1055 : 136 : case FIELD_DECL:
1056 : 136 : return mgr->get_field_region (parent_reg, index);
1057 : : }
1058 : : }
1059 : :
1060 : : /* Get the child region of PARENT_REG based upon (INDEX, VALUE) within a
1061 : : CONSTRUCTOR. */
1062 : :
1063 : : static const region *
1064 : 548 : get_subregion_within_ctor_for_ctor_pair (const region *parent_reg,
1065 : : tree index,
1066 : : tree value,
1067 : : region_model_manager *mgr)
1068 : : {
1069 : 548 : if (TREE_CODE (index) == INTEGER_CST
1070 : 412 : && TREE_CODE (value) == RAW_DATA_CST)
1071 : : {
1072 : : /* Special-case; see tree.def's description of CONSTRUCTOR.
1073 : : We have RAW_DATA_LENGTH of bytes, starting at INDEX's start. */
1074 : 14 : const region *start_reg
1075 : 14 : = get_subregion_within_ctor (parent_reg, index, mgr);
1076 : : /* Build a bit range, relative to PARENT_REG. */
1077 : 14 : region_offset start_offset = start_reg->get_offset (mgr);
1078 : :
1079 : 14 : if (!start_offset.concrete_p ())
1080 : : return nullptr;
1081 : 14 : bit_offset_t start_bit_offset = start_offset.get_bit_offset ();
1082 : 14 : int length = RAW_DATA_LENGTH (value);
1083 : 14 : bit_range bits (start_bit_offset, length * BITS_PER_UNIT);
1084 : :
1085 : 14 : return mgr->get_bit_range (parent_reg, NULL_TREE, bits);
1086 : : }
1087 : :
1088 : 534 : return get_subregion_within_ctor (parent_reg, index, mgr);
1089 : : }
1090 : :
1091 : : /* Get the svalue for VAL, a non-CONSTRUCTOR value within a CONSTRUCTOR. */
1092 : :
1093 : : static const svalue *
1094 : 482 : get_svalue_for_ctor_val (tree val, region_model_manager *mgr)
1095 : : {
1096 : : /* Reuse the get_rvalue logic from region_model. */
1097 : 482 : region_model m (mgr);
1098 : 482 : return m.get_rvalue (path_var (val, 0), nullptr);
1099 : 482 : }
1100 : :
1101 : : /* Bind values from CONSTRUCTOR to this map, relative to
1102 : : PARENT_REG's relationship to its base region.
1103 : : Return true if successful, false if there was a problem (e.g. due
1104 : : to hitting a complexity limit). */
1105 : :
1106 : : bool
1107 : 214 : binding_map::apply_ctor_to_region (const region *parent_reg, tree ctor,
1108 : : region_model_manager *mgr)
1109 : : {
1110 : 214 : gcc_assert (parent_reg);
1111 : 214 : gcc_assert (TREE_CODE (ctor) == CONSTRUCTOR);
1112 : :
1113 : 214 : unsigned ix;
1114 : 214 : tree index;
1115 : 214 : tree val;
1116 : 214 : tree parent_type = parent_reg->get_type ();
1117 : 214 : tree field;
1118 : 214 : if (TREE_CODE (parent_type) == RECORD_TYPE)
1119 : 102 : field = TYPE_FIELDS (parent_type);
1120 : : else
1121 : : field = NULL_TREE;
1122 : 761 : FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), ix, index, val)
1123 : : {
1124 : 548 : if (!index)
1125 : : {
1126 : : /* If index is NULL, then iterate through the fields for
1127 : : a RECORD_TYPE, or use an INTEGER_CST otherwise.
1128 : : Compare with similar logic in output_constructor. */
1129 : 198 : if (field)
1130 : : {
1131 : 0 : index = field;
1132 : 0 : field = DECL_CHAIN (field);
1133 : : }
1134 : : else
1135 : 198 : index = build_int_cst (integer_type_node, ix);
1136 : : }
1137 : 350 : else if (TREE_CODE (index) == RANGE_EXPR)
1138 : : {
1139 : 0 : tree min_index = TREE_OPERAND (index, 0);
1140 : 0 : tree max_index = TREE_OPERAND (index, 1);
1141 : 0 : if (min_index == max_index)
1142 : : {
1143 : 0 : if (!apply_ctor_pair_to_child_region (parent_reg, mgr,
1144 : : min_index, val))
1145 : : return false;
1146 : : }
1147 : : else
1148 : : {
1149 : 0 : if (!apply_ctor_val_to_range (parent_reg, mgr,
1150 : : min_index, max_index, val))
1151 : : return false;
1152 : : }
1153 : 0 : continue;
1154 : 0 : }
1155 : 548 : if (!apply_ctor_pair_to_child_region (parent_reg, mgr, index, val))
1156 : : return false;
1157 : : }
1158 : : return true;
1159 : : }
1160 : :
1161 : : /* Bind the value VAL into the range of elements within PARENT_REF
1162 : : from MIN_INDEX to MAX_INDEX (including endpoints).
1163 : : For use in handling RANGE_EXPR within a CONSTRUCTOR.
1164 : : Return true if successful, false if there was a problem (e.g. due
1165 : : to hitting a complexity limit). */
1166 : :
1167 : : bool
1168 : 0 : binding_map::apply_ctor_val_to_range (const region *parent_reg,
1169 : : region_model_manager *mgr,
1170 : : tree min_index, tree max_index,
1171 : : tree val)
1172 : : {
1173 : 0 : gcc_assert (TREE_CODE (min_index) == INTEGER_CST);
1174 : 0 : gcc_assert (TREE_CODE (max_index) == INTEGER_CST);
1175 : :
1176 : : /* Generate a binding key for the range. */
1177 : 0 : const region *min_element
1178 : 0 : = get_subregion_within_ctor (parent_reg, min_index, mgr);
1179 : 0 : const region *max_element
1180 : 0 : = get_subregion_within_ctor (parent_reg, max_index, mgr);
1181 : 0 : region_offset min_offset = min_element->get_offset (mgr);
1182 : 0 : if (min_offset.symbolic_p ())
1183 : : return false;
1184 : 0 : bit_offset_t start_bit_offset = min_offset.get_bit_offset ();
1185 : 0 : store_manager *smgr = mgr->get_store_manager ();
1186 : 0 : if (max_element->empty_p ())
1187 : : return false;
1188 : 0 : const binding_key *max_element_key = binding_key::make (smgr, max_element);
1189 : 0 : if (max_element_key->symbolic_p ())
1190 : : return false;
1191 : 0 : const concrete_binding *max_element_ckey
1192 : 0 : = max_element_key->dyn_cast_concrete_binding ();
1193 : 0 : bit_size_t range_size_in_bits
1194 : 0 : = max_element_ckey->get_next_bit_offset () - start_bit_offset;
1195 : 0 : const concrete_binding *range_key
1196 : 0 : = smgr->get_concrete_binding (start_bit_offset, range_size_in_bits);
1197 : 0 : if (range_key->symbolic_p ())
1198 : : return false;
1199 : :
1200 : : /* Get the value. */
1201 : 0 : if (TREE_CODE (val) == CONSTRUCTOR)
1202 : : return false;
1203 : 0 : const svalue *sval = get_svalue_for_ctor_val (val, mgr);
1204 : :
1205 : : /* Bind the value to the range. */
1206 : 0 : put (range_key, sval);
1207 : 0 : return true;
1208 : : }
1209 : :
1210 : : /* Bind the value VAL into INDEX within PARENT_REF.
1211 : : For use in handling a pair of entries within a CONSTRUCTOR.
1212 : : Return true if successful, false if there was a problem (e.g. due
1213 : : to hitting a complexity limit). */
1214 : :
1215 : : bool
1216 : 548 : binding_map::apply_ctor_pair_to_child_region (const region *parent_reg,
1217 : : region_model_manager *mgr,
1218 : : tree index, tree val)
1219 : : {
1220 : 548 : const region *child_reg
1221 : 548 : = get_subregion_within_ctor_for_ctor_pair (parent_reg, index, val, mgr);
1222 : 548 : if (!child_reg)
1223 : : return false;
1224 : 548 : if (TREE_CODE (val) == CONSTRUCTOR)
1225 : 66 : return apply_ctor_to_region (child_reg, val, mgr);
1226 : : else
1227 : : {
1228 : 482 : const svalue *sval = get_svalue_for_ctor_val (val, mgr);
1229 : 482 : if (child_reg->empty_p ())
1230 : : return false;
1231 : 482 : const binding_key *k
1232 : 482 : = binding_key::make (mgr->get_store_manager (), child_reg);
1233 : : /* Handle the case where we have an unknown size for child_reg
1234 : : (e.g. due to it being a trailing field with incomplete array
1235 : : type. */
1236 : 482 : if (!k->concrete_p ())
1237 : : {
1238 : : /* Assume that sval has a well-defined size for this case. */
1239 : 5 : tree sval_type = sval->get_type ();
1240 : 5 : gcc_assert (sval_type);
1241 : 5 : HOST_WIDE_INT sval_byte_size = int_size_in_bytes (sval_type);
1242 : 5 : gcc_assert (sval_byte_size != -1);
1243 : 5 : bit_size_t sval_bit_size = sval_byte_size * BITS_PER_UNIT;
1244 : : /* Get offset of child relative to base region. */
1245 : 5 : region_offset child_base_offset = child_reg->get_offset (mgr);
1246 : 5 : if (child_base_offset.symbolic_p ())
1247 : 1 : return false;
1248 : : /* Convert to an offset relative to the parent region. */
1249 : 4 : region_offset parent_base_offset = parent_reg->get_offset (mgr);
1250 : 4 : gcc_assert (!parent_base_offset.symbolic_p ());
1251 : 4 : bit_offset_t child_parent_offset
1252 : 4 : = (child_base_offset.get_bit_offset ()
1253 : 4 : - parent_base_offset.get_bit_offset ());
1254 : : /* Create a concrete key for the child within the parent. */
1255 : 4 : k = mgr->get_store_manager ()->get_concrete_binding
1256 : 4 : (child_parent_offset, sval_bit_size);
1257 : : }
1258 : 481 : gcc_assert (k->concrete_p ());
1259 : 481 : put (k, sval);
1260 : 481 : return true;
1261 : : }
1262 : : }
1263 : :
1264 : : /* Populate OUT with all bindings within this map that overlap KEY. */
1265 : :
1266 : : void
1267 : 35881 : binding_map::get_overlapping_bindings (const binding_key *key,
1268 : : auto_vec<const binding_key *> *out)
1269 : : {
1270 : 103797 : for (auto iter : *this)
1271 : : {
1272 : 67916 : const binding_key *iter_key = iter.m_key;
1273 : 135832 : if (const concrete_binding *ckey
1274 : 67916 : = key->dyn_cast_concrete_binding ())
1275 : : {
1276 : 130598 : if (const concrete_binding *iter_ckey
1277 : 65299 : = iter_key->dyn_cast_concrete_binding ())
1278 : : {
1279 : 64560 : if (ckey->overlaps_p (*iter_ckey))
1280 : 26758 : out->safe_push (iter_key);
1281 : : }
1282 : : else
1283 : : {
1284 : : /* Assume overlap. */
1285 : 739 : out->safe_push (iter_key);
1286 : : }
1287 : : }
1288 : : else
1289 : : {
1290 : : /* Assume overlap. */
1291 : 2617 : out->safe_push (iter_key);
1292 : : }
1293 : : }
1294 : 35881 : }
1295 : :
1296 : : /* Remove, truncate, and/or split any bindings within this map that
1297 : : overlap DROP_KEY.
1298 : :
1299 : : For example, if we have:
1300 : :
1301 : : +------------------------------------+
1302 : : | old binding |
1303 : : +------------------------------------+
1304 : :
1305 : : which is to be overwritten with:
1306 : :
1307 : : .......+----------------------+.......
1308 : : .......| new binding |.......
1309 : : .......+----------------------+.......
1310 : :
1311 : : this function "cuts a hole" out of the old binding:
1312 : :
1313 : : +------+......................+------+
1314 : : |prefix| hole for new binding |suffix|
1315 : : +------+......................+------+
1316 : :
1317 : : into which the new binding can be added without
1318 : : overlapping the prefix or suffix.
1319 : :
1320 : : The prefix and suffix (if added) will be bound to the pertinent
1321 : : parts of the value of the old binding.
1322 : :
1323 : : For example, given:
1324 : : struct s5
1325 : : {
1326 : : char arr[8];
1327 : : };
1328 : : void test_5 (struct s5 *p)
1329 : : {
1330 : : struct s5 f = *p;
1331 : : f.arr[3] = 42;
1332 : : }
1333 : : then after the "f = *p;" we have:
1334 : : cluster for: f: INIT_VAL((*INIT_VAL(p_33(D))))
1335 : : and at the "f.arr[3] = 42;" we remove the bindings overlapping
1336 : : "f.arr[3]", replacing it with a prefix (bytes 0-2) and suffix (bytes 4-7)
1337 : : giving:
1338 : : cluster for: f
1339 : : key: {bytes 0-2}
1340 : : value: {BITS_WITHIN(bytes 0-2, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
1341 : : key: {bytes 4-7}
1342 : : value: {BITS_WITHIN(bytes 4-7, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
1343 : : punching a hole into which the new value can be written at byte 3:
1344 : : cluster for: f
1345 : : key: {bytes 0-2}
1346 : : value: {BITS_WITHIN(bytes 0-2, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
1347 : : key: {byte 3}
1348 : : value: 'char' {(char)42}
1349 : : key: {bytes 4-7}
1350 : : value: {BITS_WITHIN(bytes 4-7, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
1351 : :
1352 : : If UNCERTAINTY is non-NULL, use it to record any svalues that
1353 : : were removed, as being maybe-bound.
1354 : :
1355 : : If MAYBE_LIVE_VALUES is non-NULL, then use it to record any svalues that
1356 : : were removed as being maybe-live.
1357 : :
1358 : : If ALWAYS_OVERLAP, then assume that DROP_KEY can overlap anything
1359 : : in the map, due to one or both of the underlying clusters being
1360 : : symbolic (but not the same symbolic region). Hence even if DROP_KEY is a
1361 : : concrete binding it could actually be referring to the same memory as
1362 : : distinct concrete bindings in the map. Remove all bindings, but
1363 : : register any svalues with *UNCERTAINTY. */
1364 : :
1365 : : void
1366 : 92076 : binding_map::remove_overlapping_bindings (store_manager *mgr,
1367 : : const binding_key *drop_key,
1368 : : uncertainty_t *uncertainty,
1369 : : svalue_set *maybe_live_values,
1370 : : bool always_overlap)
1371 : : {
1372 : : /* Get the bindings of interest within this map. */
1373 : 92076 : auto_vec<const binding_key *> bindings;
1374 : 92076 : if (always_overlap)
1375 : 113324 : for (auto iter : *this)
1376 : 57129 : bindings.safe_push (iter.m_key); /* Add all bindings. */
1377 : : else
1378 : : /* Just add overlapping bindings. */
1379 : 35881 : get_overlapping_bindings (drop_key, &bindings);
1380 : :
1381 : : unsigned i;
1382 : : const binding_key *iter_binding;
1383 : 259701 : FOR_EACH_VEC_ELT (bindings, i, iter_binding)
1384 : : {
1385 : : /* Record any svalues that were removed to *UNCERTAINTY as being
1386 : : maybe-bound, provided at least some part of the binding is symbolic.
1387 : :
1388 : : Specifically, if at least one of the bindings is symbolic, or we
1389 : : have ALWAYS_OVERLAP for the case where we have possibly aliasing
1390 : : regions, then we don't know that the svalue has been overwritten,
1391 : : and should record that to *UNCERTAINTY.
1392 : :
1393 : : However, if we have concrete keys accessing within the same symbolic
1394 : : region, then we *know* that the symbolic region has been overwritten,
1395 : : so we don't record it to *UNCERTAINTY, as this could be a genuine
1396 : : leak. */
1397 : 87243 : const svalue *old_sval = get (iter_binding);
1398 : 87243 : if (uncertainty
1399 : 116074 : && (drop_key->symbolic_p ()
1400 : 26609 : || iter_binding->symbolic_p ()
1401 : 22958 : || always_overlap))
1402 : 24889 : uncertainty->on_maybe_bound_sval (old_sval);
1403 : :
1404 : : /* Record any svalues that were removed to *MAYBE_LIVE_VALUES as being
1405 : : maybe-live. */
1406 : 87243 : if (maybe_live_values)
1407 : 57129 : maybe_live_values->add (old_sval);
1408 : :
1409 : : /* Begin by removing the old binding. */
1410 : 87243 : remove (iter_binding);
1411 : :
1412 : : /* Don't attempt to handle prefixes/suffixes for the
1413 : : "always_overlap" case; everything's being removed. */
1414 : 87243 : if (always_overlap)
1415 : 57129 : continue;
1416 : :
1417 : : /* Now potentially add the prefix and suffix. */
1418 : 60228 : if (const concrete_binding *drop_ckey
1419 : 30114 : = drop_key->dyn_cast_concrete_binding ())
1420 : 54994 : if (const concrete_binding *iter_ckey
1421 : 27497 : = iter_binding->dyn_cast_concrete_binding ())
1422 : : {
1423 : 26758 : gcc_assert (drop_ckey->overlaps_p (*iter_ckey));
1424 : :
1425 : 26758 : const bit_range &drop_bits = drop_ckey->get_bit_range ();
1426 : 26758 : const bit_range &iter_bits = iter_ckey->get_bit_range ();
1427 : :
1428 : 26758 : if (iter_bits.get_start_bit_offset ()
1429 : 26758 : < drop_bits.get_start_bit_offset ())
1430 : : {
1431 : : /* We have a truncated prefix. */
1432 : 1704 : bit_range prefix_bits (iter_bits.get_start_bit_offset (),
1433 : 3408 : (drop_bits.get_start_bit_offset ()
1434 : 1704 : - iter_bits.get_start_bit_offset ()));
1435 : 1704 : const concrete_binding *prefix_key
1436 : 1704 : = mgr->get_concrete_binding (prefix_bits);
1437 : 1704 : bit_range rel_prefix (0, prefix_bits.m_size_in_bits);
1438 : 1704 : const svalue *prefix_sval
1439 : 1704 : = old_sval->extract_bit_range (NULL_TREE,
1440 : : rel_prefix,
1441 : : mgr->get_svalue_manager ());
1442 : 1704 : put (prefix_key, prefix_sval);
1443 : : }
1444 : :
1445 : 53516 : if (iter_bits.get_next_bit_offset ()
1446 : 53516 : > drop_bits.get_next_bit_offset ())
1447 : : {
1448 : : /* We have a truncated suffix. */
1449 : 9169 : bit_range suffix_bits (drop_bits.get_next_bit_offset (),
1450 : 9169 : (iter_bits.get_next_bit_offset ()
1451 : 18338 : - drop_bits.get_next_bit_offset ()));
1452 : 9169 : const concrete_binding *suffix_key
1453 : 9169 : = mgr->get_concrete_binding (suffix_bits);
1454 : 9169 : bit_range rel_suffix (drop_bits.get_next_bit_offset ()
1455 : 9169 : - iter_bits.get_start_bit_offset (),
1456 : 9169 : suffix_bits.m_size_in_bits);
1457 : 9169 : const svalue *suffix_sval
1458 : 9169 : = old_sval->extract_bit_range (NULL_TREE,
1459 : : rel_suffix,
1460 : : mgr->get_svalue_manager ());
1461 : 9169 : put (suffix_key, suffix_sval);
1462 : : }
1463 : : }
1464 : : }
1465 : 92076 : }
1466 : :
1467 : : /* class binding_cluster. */
1468 : :
1469 : 1487192 : binding_cluster::binding_cluster (store_manager &store_mgr,
1470 : 1487192 : const region *base_region)
1471 : 1487192 : : m_base_region (base_region), m_map (store_mgr),
1472 : 1487192 : m_escaped (false), m_touched (false)
1473 : : {
1474 : 1487192 : }
1475 : :
1476 : : /* binding_cluster's copy ctor. */
1477 : :
1478 : 24199290 : binding_cluster::binding_cluster (const binding_cluster &other)
1479 : 24199290 : : m_base_region (other.m_base_region), m_map (other.m_map),
1480 : 24199290 : m_escaped (other.m_escaped), m_touched (other.m_touched)
1481 : : {
1482 : 24199290 : }
1483 : :
1484 : : /* binding_cluster's assignment operator. */
1485 : :
1486 : : binding_cluster&
1487 : 0 : binding_cluster::operator= (const binding_cluster &other)
1488 : : {
1489 : 0 : gcc_assert (m_base_region == other.m_base_region);
1490 : 0 : m_map = other.m_map;
1491 : 0 : m_escaped = other.m_escaped;
1492 : 0 : m_touched = other.m_touched;
1493 : 0 : return *this;
1494 : : }
1495 : :
1496 : : /* binding_cluster's equality operator. */
1497 : :
1498 : : bool
1499 : 2019515 : binding_cluster::operator== (const binding_cluster &other) const
1500 : : {
1501 : 2019515 : if (m_map != other.m_map)
1502 : : return false;
1503 : :
1504 : 1988254 : if (m_base_region != other.m_base_region)
1505 : : return false;
1506 : :
1507 : 1988254 : if (m_escaped != other.m_escaped)
1508 : : return false;
1509 : :
1510 : 1987537 : if (m_touched != other.m_touched)
1511 : : return false;
1512 : :
1513 : 1986099 : gcc_checking_assert (hash () == other.hash ());
1514 : :
1515 : : return true;
1516 : : }
1517 : :
1518 : : /* Generate a hash value for this binding_cluster. */
1519 : :
1520 : : hashval_t
1521 : 14097422 : binding_cluster::hash () const
1522 : : {
1523 : 14097422 : return m_map.hash ();
1524 : : }
1525 : :
1526 : : /* Return true if this binding_cluster is symbolic
1527 : : i.e. its base region is symbolic. */
1528 : :
1529 : : bool
1530 : 7360047 : binding_cluster::symbolic_p () const
1531 : : {
1532 : 7360047 : return m_base_region->get_kind () == RK_SYMBOLIC;
1533 : : }
1534 : :
1535 : : /* Dump a representation of this binding_cluster to PP.
1536 : : SIMPLE controls how values and regions are to be printed.
1537 : : If MULTILINE, then split the dump over multiple lines and
1538 : : use whitespace for readability, otherwise put all on one line. */
1539 : :
1540 : : void
1541 : 2257 : binding_cluster::dump_to_pp (pretty_printer *pp, bool simple,
1542 : : bool multiline) const
1543 : : {
1544 : 2257 : if (m_escaped)
1545 : : {
1546 : 1506 : if (multiline)
1547 : : {
1548 : 1324 : pp_string (pp, " ESCAPED");
1549 : 1324 : pp_newline (pp);
1550 : : }
1551 : : else
1552 : 182 : pp_string (pp, "(ESCAPED)");
1553 : : }
1554 : 2257 : if (m_touched)
1555 : : {
1556 : 306 : if (multiline)
1557 : : {
1558 : 124 : pp_string (pp, " TOUCHED");
1559 : 124 : pp_newline (pp);
1560 : : }
1561 : : else
1562 : 182 : pp_string (pp, "(TOUCHED)");
1563 : : }
1564 : :
1565 : 2257 : m_map.dump_to_pp (pp, simple, multiline);
1566 : 2257 : }
1567 : :
1568 : : /* Dump a multiline representation of this binding_cluster to stderr. */
1569 : :
1570 : : DEBUG_FUNCTION void
1571 : 0 : binding_cluster::dump (bool simple) const
1572 : : {
1573 : 0 : tree_dump_pretty_printer pp (stderr);
1574 : 0 : pp_string (&pp, " cluster for: ");
1575 : 0 : m_base_region->dump_to_pp (&pp, simple);
1576 : 0 : pp_string (&pp, ": ");
1577 : 0 : pp_newline (&pp);
1578 : 0 : dump_to_pp (&pp, simple, true);
1579 : 0 : pp_newline (&pp);
1580 : 0 : }
1581 : :
1582 : : /* Assert that this object is valid. */
1583 : :
1584 : : void
1585 : 9097161 : binding_cluster::validate () const
1586 : : {
1587 : 9097161 : int num_symbolic = 0;
1588 : 9097161 : int num_concrete = 0;
1589 : 18485520 : for (auto iter : m_map)
1590 : : {
1591 : 9388359 : if (iter.m_key->symbolic_p ())
1592 : 848822 : num_symbolic++;
1593 : : else
1594 : 8539537 : num_concrete++;
1595 : : }
1596 : : /* We shouldn't have more than one symbolic key per cluster
1597 : : (or one would have clobbered the other). */
1598 : 9097161 : gcc_assert (num_symbolic < 2);
1599 : : /* We can't have both concrete and symbolic keys. */
1600 : 9097161 : gcc_assert (num_concrete == 0 || num_symbolic == 0);
1601 : 9097161 : }
1602 : :
1603 : : /* Return a new json::object of the form
1604 : : {"escaped": true/false,
1605 : : "touched": true/false,
1606 : : "map" : object for the binding_map. */
1607 : :
1608 : : std::unique_ptr<json::object>
1609 : 0 : binding_cluster::to_json () const
1610 : : {
1611 : 0 : auto cluster_obj = std::make_unique<json::object> ();
1612 : :
1613 : 0 : cluster_obj->set_bool ("escaped", m_escaped);
1614 : 0 : cluster_obj->set_bool ("touched", m_touched);
1615 : 0 : cluster_obj->set ("map", m_map.to_json ());
1616 : :
1617 : 0 : return cluster_obj;
1618 : : }
1619 : :
1620 : : std::unique_ptr<text_art::tree_widget>
1621 : 0 : binding_cluster::make_dump_widget (const text_art::dump_widget_info &dwi,
1622 : : store_manager *mgr) const
1623 : : {
1624 : 0 : pretty_printer the_pp;
1625 : 0 : pretty_printer * const pp = &the_pp;
1626 : 0 : pp_format_decoder (pp) = default_tree_printer;
1627 : 0 : pp_show_color (pp) = true;
1628 : 0 : const bool simple = true;
1629 : :
1630 : 0 : m_base_region->dump_to_pp (pp, simple);
1631 : 0 : pp_string (pp, ": ");
1632 : :
1633 : 0 : if (const svalue *sval = maybe_get_simple_value (mgr))
1634 : : {
1635 : : /* Special-case to simplify dumps for the common case where
1636 : : we just have one value directly bound to the whole of a
1637 : : region. */
1638 : 0 : sval->dump_to_pp (pp, simple);
1639 : 0 : if (escaped_p ())
1640 : 0 : pp_string (pp, " (ESCAPED)");
1641 : 0 : if (touched_p ())
1642 : 0 : pp_string (pp, " (TOUCHED)");
1643 : :
1644 : 0 : return text_art::tree_widget::make (dwi, pp);
1645 : : }
1646 : : else
1647 : : {
1648 : 0 : if (escaped_p ())
1649 : 0 : pp_string (pp, " (ESCAPED)");
1650 : 0 : if (touched_p ())
1651 : 0 : pp_string (pp, " (TOUCHED)");
1652 : :
1653 : 0 : std::unique_ptr<text_art::tree_widget> cluster_widget
1654 : 0 : (text_art::tree_widget::make (dwi, pp));
1655 : :
1656 : 0 : m_map.add_to_tree_widget (*cluster_widget, dwi);
1657 : :
1658 : 0 : return cluster_widget;
1659 : 0 : }
1660 : 0 : }
1661 : :
1662 : : /* Add a binding of SVAL of kind KIND to REG, unpacking SVAL if it is a
1663 : : compound_sval. */
1664 : :
1665 : : void
1666 : 420955 : binding_cluster::bind (store_manager *mgr,
1667 : : const region *reg, const svalue *sval)
1668 : : {
1669 : 841910 : if (const compound_svalue *compound_sval
1670 : 420955 : = sval->dyn_cast_compound_svalue ())
1671 : : {
1672 : 868 : bind_compound_sval (mgr, reg, compound_sval);
1673 : 868 : return;
1674 : : }
1675 : :
1676 : 420087 : if (reg->empty_p ())
1677 : : return;
1678 : 420087 : const binding_key *binding = binding_key::make (mgr, reg);
1679 : 420087 : bind_key (binding, sval);
1680 : : }
1681 : :
1682 : : /* Bind SVAL to KEY.
1683 : : Unpacking of compound_svalues should already have been done by the
1684 : : time this is called. */
1685 : :
1686 : : void
1687 : 424231 : binding_cluster::bind_key (const binding_key *key, const svalue *sval)
1688 : : {
1689 : 424231 : gcc_assert (sval->get_kind () != SK_COMPOUND);
1690 : :
1691 : 424231 : m_map.put (key, sval);
1692 : 424231 : if (key->symbolic_p ())
1693 : 32704 : m_touched = true;
1694 : 424231 : }
1695 : :
1696 : : /* Subroutine of binding_cluster::bind.
1697 : : Unpack compound_svals when binding them, so that we bind them
1698 : : element-wise. */
1699 : :
1700 : : void
1701 : 868 : binding_cluster::bind_compound_sval (store_manager *mgr,
1702 : : const region *reg,
1703 : : const compound_svalue *compound_sval)
1704 : : {
1705 : 868 : region_offset reg_offset
1706 : 868 : = reg->get_offset (mgr->get_svalue_manager ());
1707 : 868 : if (reg_offset.symbolic_p ())
1708 : : {
1709 : 4 : m_touched = true;
1710 : 4 : clobber_region (mgr, reg);
1711 : 4 : return;
1712 : : }
1713 : :
1714 : 3293 : for (auto iter : *compound_sval)
1715 : : {
1716 : 2429 : const binding_key *iter_key = iter.m_key;
1717 : 2429 : const svalue *iter_sval = iter.m_sval;
1718 : :
1719 : 4858 : if (const concrete_binding *concrete_key
1720 : 2429 : = iter_key->dyn_cast_concrete_binding ())
1721 : : {
1722 : 2429 : bit_offset_t effective_start
1723 : 2429 : = (concrete_key->get_start_bit_offset ()
1724 : 2429 : + reg_offset.get_bit_offset ());
1725 : 2429 : const concrete_binding *effective_concrete_key
1726 : 2429 : = mgr->get_concrete_binding (effective_start,
1727 : : concrete_key->get_size_in_bits ());
1728 : 2429 : bind_key (effective_concrete_key, iter_sval);
1729 : : }
1730 : : else
1731 : 0 : gcc_unreachable ();
1732 : : }
1733 : : }
1734 : :
1735 : : /* Remove all bindings overlapping REG within this cluster. */
1736 : :
1737 : : void
1738 : 5950 : binding_cluster::clobber_region (store_manager *mgr, const region *reg)
1739 : : {
1740 : 5950 : remove_overlapping_bindings (mgr, reg, nullptr, nullptr);
1741 : 5950 : }
1742 : :
1743 : : /* Remove any bindings for REG within this cluster. */
1744 : :
1745 : : void
1746 : 177667 : binding_cluster::purge_region (store_manager *mgr, const region *reg)
1747 : : {
1748 : 177667 : gcc_assert (reg->get_kind () == RK_DECL);
1749 : 177667 : if (reg->empty_p ())
1750 : : return;
1751 : 177667 : const binding_key *binding
1752 : 177667 : = binding_key::make (mgr, const_cast<region *> (reg));
1753 : 177667 : m_map.remove (binding);
1754 : : }
1755 : :
1756 : : /* Clobber REG and fill it with repeated copies of SVAL. */
1757 : :
1758 : : void
1759 : 1425 : binding_cluster::fill_region (store_manager *mgr,
1760 : : const region *reg,
1761 : : const svalue *sval)
1762 : : {
1763 : 1425 : clobber_region (mgr, reg);
1764 : :
1765 : 1425 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
1766 : 1425 : const svalue *byte_size_sval = reg->get_byte_size_sval (sval_mgr);
1767 : 1425 : const svalue *fill_sval
1768 : 1425 : = sval_mgr->get_or_create_repeated_svalue (reg->get_type (),
1769 : : byte_size_sval, sval);
1770 : 1425 : bind (mgr, reg, fill_sval);
1771 : 1425 : }
1772 : :
1773 : : /* Clobber REG within this cluster and fill it with zeroes. */
1774 : :
1775 : : void
1776 : 33 : binding_cluster::zero_fill_region (store_manager *mgr, const region *reg)
1777 : : {
1778 : 33 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
1779 : 33 : const svalue *zero_sval = sval_mgr->get_or_create_int_cst (char_type_node, 0);
1780 : 33 : fill_region (mgr, reg, zero_sval);
1781 : 33 : }
1782 : :
1783 : : /* Mark REG_TO_BIND within this cluster as being unknown.
1784 : :
1785 : : Remove any bindings overlapping REG_FOR_OVERLAP.
1786 : : If UNCERTAINTY is non-NULL, use it to record any svalues that
1787 : : had bindings to them removed, as being maybe-bound.
1788 : : If MAYBE_LIVE_VALUES is non-NULL, use it to record any svalues that
1789 : : had bindings to them removed, as being maybe-live.
1790 : :
1791 : : REG_TO_BIND and REG_FOR_OVERLAP are the same for
1792 : : store::mark_region_as_unknown, but are different in
1793 : : store::set_value's alias handling, for handling the case where
1794 : : we have a write to a symbolic REG_FOR_OVERLAP. */
1795 : :
1796 : : void
1797 : 56484 : binding_cluster::mark_region_as_unknown (store_manager *mgr,
1798 : : const region *reg_to_bind,
1799 : : const region *reg_for_overlap,
1800 : : uncertainty_t *uncertainty,
1801 : : svalue_set *maybe_live_values)
1802 : : {
1803 : 56484 : if (reg_to_bind->empty_p ())
1804 : : return;
1805 : :
1806 : 56484 : remove_overlapping_bindings (mgr, reg_for_overlap, uncertainty,
1807 : : maybe_live_values);
1808 : :
1809 : : /* Add a default binding to "unknown". */
1810 : 56484 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
1811 : 56484 : const svalue *sval
1812 : 56484 : = sval_mgr->get_or_create_unknown_svalue (reg_to_bind->get_type ());
1813 : 56484 : bind (mgr, reg_to_bind, sval);
1814 : : }
1815 : :
1816 : : /* Purge state involving SVAL. */
1817 : :
1818 : : void
1819 : 584011 : binding_cluster::purge_state_involving (const svalue *sval,
1820 : : region_model_manager *sval_mgr)
1821 : : {
1822 : 584011 : auto_vec<const binding_key *> to_remove;
1823 : 584011 : auto_vec<std::pair<const binding_key *, tree> > to_make_unknown;
1824 : 1169878 : for (auto iter : m_map)
1825 : : {
1826 : 585867 : const binding_key *iter_key = iter.m_key;
1827 : 1171734 : if (const symbolic_binding *symbolic_key
1828 : 585867 : = iter_key->dyn_cast_symbolic_binding ())
1829 : : {
1830 : 68981 : const region *reg = symbolic_key->get_region ();
1831 : 68981 : if (reg->involves_p (sval))
1832 : 0 : to_remove.safe_push (iter_key);
1833 : : }
1834 : 585867 : const svalue *iter_sval = iter.m_sval;
1835 : 585867 : if (iter_sval->involves_p (sval))
1836 : 4109 : to_make_unknown.safe_push (std::make_pair(iter_key,
1837 : 4109 : iter_sval->get_type ()));
1838 : : }
1839 : 584011 : for (auto iter : to_remove)
1840 : : {
1841 : 0 : m_map.remove (iter);
1842 : 0 : m_touched = true;
1843 : : }
1844 : 596338 : for (auto iter : to_make_unknown)
1845 : : {
1846 : 4109 : const svalue *new_sval
1847 : 4109 : = sval_mgr->get_or_create_unknown_svalue (iter.second);
1848 : 4109 : m_map.put (iter.first, new_sval);
1849 : : }
1850 : 584011 : }
1851 : :
1852 : : /* Get any SVAL bound to REG within this cluster via kind KIND,
1853 : : without checking parent regions of REG. */
1854 : :
1855 : : const svalue *
1856 : 1420256 : binding_cluster::get_binding (store_manager *mgr,
1857 : : const region *reg) const
1858 : : {
1859 : 1420256 : if (reg->empty_p ())
1860 : : return nullptr;
1861 : 1420256 : const binding_key *reg_binding = binding_key::make (mgr, reg);
1862 : 1420256 : const svalue *sval = m_map.get (reg_binding);
1863 : 1420256 : if (sval)
1864 : : {
1865 : : /* If we have a struct with a single field, then the binding of
1866 : : the field will equal that of the struct, and looking up e.g.
1867 : : PARENT_REG.field within:
1868 : : cluster for PARENT_REG: INIT_VAL(OTHER_REG)
1869 : : will erroneously return INIT_VAL(OTHER_REG), rather than
1870 : : SUB_VALUE(INIT_VAL(OTHER_REG), FIELD) == INIT_VAL(OTHER_REG.FIELD).
1871 : : Fix this issue by iterating upwards whilst the bindings are equal,
1872 : : expressing the lookups as subvalues.
1873 : : We have to gather a list of subregion accesses, then walk it
1874 : : in reverse to get the subvalues. */
1875 : 1103917 : auto_vec<const region *> regions;
1876 : 1115833 : while (const region *parent_reg = reg->get_parent_region ())
1877 : : {
1878 : 1115833 : const binding_key *parent_reg_binding
1879 : 1115833 : = binding_key::make (mgr, parent_reg);
1880 : 1115833 : if (parent_reg_binding == reg_binding
1881 : 14615 : && sval->get_type ()
1882 : 14603 : && reg->get_type ()
1883 : 1130436 : && sval->get_type () != reg->get_type ())
1884 : : {
1885 : 11916 : regions.safe_push (reg);
1886 : 11916 : reg = parent_reg;
1887 : : }
1888 : : else
1889 : : break;
1890 : 11916 : }
1891 : 1103917 : if (sval->get_type ()
1892 : 1095111 : && reg->get_type ()
1893 : 2198215 : && sval->get_type () == reg->get_type ())
1894 : : {
1895 : 905112 : unsigned i;
1896 : 905112 : const region *iter_reg;
1897 : 1137112 : FOR_EACH_VEC_ELT_REVERSE (regions, i, iter_reg)
1898 : : {
1899 : 11207 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
1900 : 11207 : sval = rmm_mgr->get_or_create_sub_svalue (iter_reg->get_type (),
1901 : : sval, iter_reg);
1902 : : }
1903 : : }
1904 : 1103917 : }
1905 : : return sval;
1906 : : }
1907 : :
1908 : : /* Get any SVAL bound to REG within this cluster,
1909 : : either directly for REG, or recursively checking for bindings within
1910 : : parent regions and extracting subvalues if need be. */
1911 : :
1912 : : const svalue *
1913 : 1420256 : binding_cluster::get_binding_recursive (store_manager *mgr,
1914 : : const region *reg) const
1915 : : {
1916 : 1420256 : if (const svalue *sval = get_binding (mgr, reg))
1917 : : return sval;
1918 : 316339 : if (reg != m_base_region)
1919 : 189080 : if (const region *parent_reg = reg->get_parent_region ())
1920 : 378160 : if (const svalue *parent_sval
1921 : 189080 : = get_binding_recursive (mgr, parent_reg))
1922 : : {
1923 : : /* Extract child svalue from parent svalue. */
1924 : 58057 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
1925 : 58057 : return rmm_mgr->get_or_create_sub_svalue (reg->get_type (),
1926 : 58057 : parent_sval, reg);
1927 : : }
1928 : : return nullptr;
1929 : : }
1930 : :
1931 : : /* Get any value bound for REG within this cluster. */
1932 : :
1933 : : const svalue *
1934 : 1231176 : binding_cluster::get_any_binding (store_manager *mgr,
1935 : : const region *reg) const
1936 : : {
1937 : : /* Look for a direct binding. */
1938 : 2462352 : if (const svalue *direct_sval
1939 : 1231176 : = get_binding_recursive (mgr, reg))
1940 : : return direct_sval;
1941 : :
1942 : : /* If we had a write to a cluster of unknown size, we might
1943 : : have a self-binding of the whole base region with an svalue,
1944 : : where the base region is symbolic.
1945 : : Handle such cases by returning sub_svalue instances. */
1946 : 127259 : if (const svalue *cluster_sval = maybe_get_simple_value (mgr))
1947 : : {
1948 : : /* Extract child svalue from parent svalue. */
1949 : 0 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
1950 : 0 : return rmm_mgr->get_or_create_sub_svalue (reg->get_type (),
1951 : 0 : cluster_sval, reg);
1952 : : }
1953 : :
1954 : : /* If this cluster has been touched by a symbolic write, then the content
1955 : : of any subregion not currently specifically bound is "UNKNOWN". */
1956 : 127259 : if (m_touched)
1957 : : {
1958 : 5319 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
1959 : 5319 : return rmm_mgr->get_or_create_unknown_svalue (reg->get_type ());
1960 : : }
1961 : :
1962 : : /* Alternatively, if this is a symbolic read and the cluster has any bindings,
1963 : : then we don't know if we're reading those values or not, so the result
1964 : : is also "UNKNOWN". */
1965 : 121940 : if (reg->get_offset (mgr->get_svalue_manager ()).symbolic_p ()
1966 : 121940 : && m_map.elements () > 0)
1967 : : {
1968 : 571 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
1969 : 571 : return rmm_mgr->get_or_create_unknown_svalue (reg->get_type ());
1970 : : }
1971 : :
1972 : 121369 : if (const svalue *compound_sval = maybe_get_compound_binding (mgr, reg))
1973 : : return compound_sval;
1974 : :
1975 : : /* Otherwise, the initial value, or uninitialized. */
1976 : : return nullptr;
1977 : : }
1978 : :
1979 : : /* Attempt to get a compound_svalue for the bindings within the cluster
1980 : : affecting REG (which could be the base region itself).
1981 : :
1982 : : Create a compound_svalue with the subset of bindings the affect REG,
1983 : : offsetting them so that the offsets are relative to the start of REG
1984 : : within the cluster.
1985 : :
1986 : : For example, REG could be one element within an array of structs.
1987 : :
1988 : : Return the resulting compound_svalue, or nullptr if there's a problem. */
1989 : :
1990 : : const svalue *
1991 : 121369 : binding_cluster::maybe_get_compound_binding (store_manager *mgr,
1992 : : const region *reg) const
1993 : : {
1994 : 121369 : region_offset cluster_offset
1995 : 121369 : = m_base_region->get_offset (mgr->get_svalue_manager ());
1996 : 121369 : if (cluster_offset.symbolic_p ())
1997 : : return nullptr;
1998 : 121369 : region_offset reg_offset = reg->get_offset (mgr->get_svalue_manager ());
1999 : 121369 : if (reg_offset.symbolic_p ())
2000 : : return nullptr;
2001 : :
2002 : 96791 : if (reg->empty_p ())
2003 : : return nullptr;
2004 : :
2005 : 96791 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
2006 : :
2007 : : /* We will a build the result map in two parts:
2008 : : (a) result_map, holding the concrete keys from this cluster,
2009 : :
2010 : : (b) default_map, holding the initial values for the region
2011 : : (e.g. uninitialized, initializer values, or zero), unless this
2012 : : cluster has been touched.
2013 : :
2014 : : We will populate (a), and as we do, clobber (b), trimming and
2015 : : splitting its bindings as necessary.
2016 : : Finally, we will merge (b) into (a), giving a concrete map
2017 : : that merges both the initial values and the bound values from
2018 : : the binding_cluster.
2019 : : Doing it this way reduces N for the O(N^2) intersection-finding,
2020 : : perhaps we should have a spatial-organized data structure for
2021 : : concrete keys, though. */
2022 : :
2023 : 96791 : binding_map result_map (*mgr);
2024 : 96791 : binding_map default_map (*mgr);
2025 : :
2026 : : /* Set up default values in default_map. */
2027 : 96791 : const svalue *default_sval;
2028 : 96791 : if (m_touched)
2029 : 0 : default_sval = sval_mgr->get_or_create_unknown_svalue (reg->get_type ());
2030 : : else
2031 : 96791 : default_sval = sval_mgr->get_or_create_initial_value (reg);
2032 : 96791 : const binding_key *default_key = binding_key::make (mgr, reg);
2033 : :
2034 : : /* Express the bit-range of the default key for REG relative to REG,
2035 : : rather than to the base region. */
2036 : 96791 : const concrete_binding *concrete_default_key
2037 : 96791 : = default_key->dyn_cast_concrete_binding ();
2038 : 96791 : if (!concrete_default_key)
2039 : : return nullptr;
2040 : 95908 : const concrete_binding *default_key_relative_to_reg
2041 : 95908 : = mgr->get_concrete_binding (0, concrete_default_key->get_size_in_bits ());
2042 : :
2043 : 95908 : default_map.put (default_key_relative_to_reg, default_sval);
2044 : :
2045 : 178038 : for (auto iter : m_map)
2046 : : {
2047 : 95016 : const binding_key *key = iter.m_key;
2048 : 95016 : const svalue *sval = iter.m_sval;
2049 : :
2050 : 190032 : if (const concrete_binding *concrete_key
2051 : 95016 : = key->dyn_cast_concrete_binding ())
2052 : : {
2053 : 95016 : const bit_range &bound_range = concrete_key->get_bit_range ();
2054 : :
2055 : 95016 : bit_size_t reg_bit_size;
2056 : 95016 : if (!reg->get_bit_size (®_bit_size))
2057 : 12886 : return nullptr;
2058 : :
2059 : 95016 : bit_range reg_range (reg_offset.get_bit_offset (),
2060 : 95016 : reg_bit_size);
2061 : :
2062 : : /* Skip bindings that are outside the bit range of REG. */
2063 : 95016 : if (!bound_range.intersects_p (reg_range))
2064 : 72177 : continue;
2065 : :
2066 : : /* We shouldn't have an exact match; that should have been
2067 : : handled already. */
2068 : 22839 : gcc_assert (!(reg_range == bound_range));
2069 : :
2070 : 22839 : bit_range subrange (0, 0);
2071 : 22839 : if (reg_range.contains_p (bound_range, &subrange))
2072 : : {
2073 : : /* We have a bound range fully within REG.
2074 : : Add it to map, offsetting accordingly. */
2075 : :
2076 : : /* Get offset of KEY relative to REG, rather than to
2077 : : the cluster. */
2078 : 9877 : const concrete_binding *offset_concrete_key
2079 : 9877 : = mgr->get_concrete_binding (subrange);
2080 : 9877 : result_map.put (offset_concrete_key, sval);
2081 : :
2082 : : /* Clobber default_map, removing/trimming/spliting where
2083 : : it overlaps with offset_concrete_key. */
2084 : 9877 : default_map.remove_overlapping_bindings (mgr,
2085 : : offset_concrete_key,
2086 : : nullptr, nullptr, false);
2087 : : }
2088 : 12962 : else if (bound_range.contains_p (reg_range, &subrange))
2089 : : {
2090 : : /* REG is fully within the bound range, but
2091 : : is not equal to it; we're extracting a subvalue. */
2092 : 12886 : return sval->extract_bit_range (reg->get_type (),
2093 : : subrange,
2094 : 12886 : mgr->get_svalue_manager ());
2095 : : }
2096 : : else
2097 : : {
2098 : : /* REG and the bound range partially overlap. */
2099 : 76 : bit_range reg_subrange (0, 0);
2100 : 76 : bit_range bound_subrange (0, 0);
2101 : 76 : reg_range.intersects_p (bound_range,
2102 : : ®_subrange, &bound_subrange);
2103 : :
2104 : : /* Get the bits from the bound value for the bits at the
2105 : : intersection (relative to the bound value). */
2106 : 76 : const svalue *overlap_sval
2107 : 76 : = sval->extract_bit_range (NULL_TREE,
2108 : : bound_subrange,
2109 : : mgr->get_svalue_manager ());
2110 : :
2111 : : /* Get key for overlap, relative to the REG. */
2112 : 76 : const concrete_binding *overlap_concrete_key
2113 : 76 : = mgr->get_concrete_binding (reg_subrange);
2114 : 76 : result_map.put (overlap_concrete_key, overlap_sval);
2115 : :
2116 : : /* Clobber default_map, removing/trimming/spliting where
2117 : : it overlaps with overlap_concrete_key. */
2118 : 76 : default_map.remove_overlapping_bindings (mgr,
2119 : : overlap_concrete_key,
2120 : : nullptr, nullptr, false);
2121 : : }
2122 : : }
2123 : : else
2124 : : /* Can't handle symbolic bindings. */
2125 : : return nullptr;
2126 : : }
2127 : :
2128 : 83022 : if (result_map.elements () == 0)
2129 : : return nullptr;
2130 : :
2131 : : /* Merge any bindings from default_map into result_map. */
2132 : 3925 : for (auto iter : default_map)
2133 : : {
2134 : 368 : const binding_key *key = iter.m_key;
2135 : 368 : const svalue *sval = iter.m_sval;
2136 : 368 : result_map.put (key, sval);
2137 : : }
2138 : :
2139 : 3557 : return sval_mgr->get_or_create_compound_svalue (reg->get_type (), result_map);
2140 : 96791 : }
2141 : :
2142 : : /* Remove, truncate, and/or split any bindings within this map that
2143 : : could overlap REG.
2144 : :
2145 : : If REG's base region or this cluster is symbolic and they're different
2146 : : base regions, then remove everything in this cluster's map, on the
2147 : : grounds that REG could be referring to the same memory as anything
2148 : : in the map.
2149 : :
2150 : : If UNCERTAINTY is non-NULL, use it to record any svalues that
2151 : : were removed, as being maybe-bound.
2152 : :
2153 : : If MAYBE_LIVE_VALUES is non-NULL, use it to record any svalues that
2154 : : were removed, as being maybe-live. */
2155 : :
2156 : : void
2157 : 82123 : binding_cluster::remove_overlapping_bindings (store_manager *mgr,
2158 : : const region *reg,
2159 : : uncertainty_t *uncertainty,
2160 : : svalue_set *maybe_live_values)
2161 : : {
2162 : 82123 : if (reg->empty_p ())
2163 : : return;
2164 : 82123 : const binding_key *reg_binding = binding_key::make (mgr, reg);
2165 : :
2166 : 82123 : const region *cluster_base_reg = get_base_region ();
2167 : 82123 : const region *other_base_reg = reg->get_base_region ();
2168 : : /* If at least one of the base regions involved is symbolic, and they're
2169 : : not the same base region, then consider everything in the map as
2170 : : potentially overlapping with reg_binding (even if it's a concrete
2171 : : binding and things in the map are concrete - they could be referring
2172 : : to the same memory when the symbolic base regions are taken into
2173 : : account). */
2174 : 82123 : bool always_overlap = (cluster_base_reg != other_base_reg
2175 : 82123 : && (cluster_base_reg->get_kind () == RK_SYMBOLIC
2176 : 24509 : || other_base_reg->get_kind () == RK_SYMBOLIC));
2177 : 82123 : m_map.remove_overlapping_bindings (mgr, reg_binding, uncertainty,
2178 : : maybe_live_values,
2179 : : always_overlap);
2180 : : }
2181 : :
2182 : : /* Attempt to merge CLUSTER_A and CLUSTER_B into OUT_CLUSTER, using
2183 : : MGR and MERGER.
2184 : : Return true if they can be merged, false otherwise. */
2185 : :
2186 : : bool
2187 : 1157634 : binding_cluster::can_merge_p (const binding_cluster *cluster_a,
2188 : : const binding_cluster *cluster_b,
2189 : : binding_cluster *out_cluster,
2190 : : store *out_store,
2191 : : store_manager *mgr,
2192 : : model_merger *merger)
2193 : : {
2194 : 1157634 : gcc_assert (out_cluster);
2195 : :
2196 : : /* Merge flags ("ESCAPED" and "TOUCHED") by setting the merged flag to
2197 : : true if either of the inputs is true. */
2198 : 1157634 : if ((cluster_a && cluster_a->m_escaped)
2199 : 738427 : || (cluster_b && cluster_b->m_escaped))
2200 : 5016 : out_cluster->m_escaped = true;
2201 : 1157634 : if ((cluster_a && cluster_a->m_touched)
2202 : 790742 : || (cluster_b && cluster_b->m_touched))
2203 : 13078 : out_cluster->m_touched = true;
2204 : :
2205 : : /* At least one of CLUSTER_A and CLUSTER_B are non-NULL, but either
2206 : : could be NULL. Handle these cases. */
2207 : 1157634 : if (cluster_a == nullptr)
2208 : : {
2209 : 21987 : gcc_assert (cluster_b != nullptr);
2210 : 21987 : gcc_assert (cluster_b->m_base_region == out_cluster->m_base_region);
2211 : 21987 : out_cluster->make_unknown_relative_to (cluster_b, out_store, mgr);
2212 : 21987 : return true;
2213 : : }
2214 : 1135647 : if (cluster_b == nullptr)
2215 : : {
2216 : 80087 : gcc_assert (cluster_a != nullptr);
2217 : 80087 : gcc_assert (cluster_a->m_base_region == out_cluster->m_base_region);
2218 : 80087 : out_cluster->make_unknown_relative_to (cluster_a, out_store, mgr);
2219 : 80087 : return true;
2220 : : }
2221 : :
2222 : : /* The "both inputs are non-NULL" case. */
2223 : 1055560 : gcc_assert (cluster_a != nullptr && cluster_b != nullptr);
2224 : 1055560 : gcc_assert (cluster_a->m_base_region == out_cluster->m_base_region);
2225 : 1055560 : gcc_assert (cluster_b->m_base_region == out_cluster->m_base_region);
2226 : :
2227 : 1055560 : hash_set<const binding_key *> keys;
2228 : 2258137 : for (auto iter_a : cluster_a->m_map)
2229 : : {
2230 : 1202577 : const binding_key *key_a = iter_a.m_key;
2231 : 1202577 : keys.add (key_a);
2232 : : }
2233 : 2243272 : for (auto iter_b : cluster_b->m_map)
2234 : : {
2235 : 1187712 : const binding_key *key_b = iter_b.m_key;
2236 : 1187712 : keys.add (key_b);
2237 : : }
2238 : 1055560 : int num_symbolic_keys = 0;
2239 : 1055560 : int num_concrete_keys = 0;
2240 : 2135202 : for (hash_set<const binding_key *>::iterator iter = keys.begin ();
2241 : 3214844 : iter != keys.end (); ++iter)
2242 : : {
2243 : 1182916 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
2244 : 1182916 : const binding_key *key = *iter;
2245 : 1182916 : const svalue *sval_a = cluster_a->get_any_value (key);
2246 : 1182916 : const svalue *sval_b = cluster_b->get_any_value (key);
2247 : :
2248 : 1182916 : if (key->symbolic_p ())
2249 : 115522 : num_symbolic_keys++;
2250 : : else
2251 : 1067394 : num_concrete_keys++;
2252 : :
2253 : 1182916 : if (sval_a == sval_b)
2254 : : {
2255 : 878853 : gcc_assert (sval_a);
2256 : 878853 : out_cluster->m_map.put (key, sval_a);
2257 : 878853 : continue;
2258 : : }
2259 : 304063 : else if (sval_a && sval_b)
2260 : : {
2261 : 560253 : if (const svalue *merged_sval
2262 : 205960 : = sval_a->can_merge_p (sval_b, sval_mgr, merger))
2263 : : {
2264 : 148333 : out_cluster->m_map.put (key, merged_sval);
2265 : 148333 : continue;
2266 : : }
2267 : : /* Merger of the svalues failed. Reject merger of the cluster. */
2268 : 103274 : return false;
2269 : : }
2270 : :
2271 : : /* If we get here, then one cluster binds this key and the other
2272 : : doesn't; merge them as "UNKNOWN". */
2273 : 98103 : gcc_assert (sval_a || sval_b);
2274 : :
2275 : 98103 : const svalue *bound_sval = sval_a ? sval_a : sval_b;
2276 : 98103 : tree type = bound_sval->get_type ();
2277 : 98103 : const svalue *unknown_sval
2278 : 98103 : = mgr->get_svalue_manager ()->get_or_create_unknown_svalue (type);
2279 : :
2280 : : /* ...but reject the merger if this sval shouldn't be mergeable
2281 : : (e.g. reject merging svalues that have non-purgable sm-state,
2282 : : to avoid falsely reporting memory leaks by merging them
2283 : : with something else). */
2284 : 98103 : if (!bound_sval->can_merge_p (unknown_sval, sval_mgr, merger))
2285 : : return false;
2286 : :
2287 : 52456 : out_cluster->m_map.put (key, unknown_sval);
2288 : : }
2289 : :
2290 : : /* We can only have at most one symbolic key per cluster,
2291 : : and if we do, we can't have any concrete keys.
2292 : : If this happens, mark the cluster as touched, with no keys. */
2293 : 952286 : if (num_symbolic_keys >= 2
2294 : 951760 : || (num_concrete_keys > 0 && num_symbolic_keys > 0))
2295 : : {
2296 : 1639 : out_cluster->m_touched = true;
2297 : 1639 : out_cluster->m_map.clear ();
2298 : : }
2299 : :
2300 : : /* We don't handle other kinds of overlaps yet. */
2301 : :
2302 : : return true;
2303 : 1055560 : }
2304 : :
2305 : : /* Update this cluster to reflect an attempt to merge OTHER where there
2306 : : is no other cluster to merge with, and so we're notionally merging the
2307 : : bound values in OTHER with the initial value of the relevant regions.
2308 : :
2309 : : Any bound keys in OTHER should be bound to unknown in this. */
2310 : :
2311 : : void
2312 : 102074 : binding_cluster::make_unknown_relative_to (const binding_cluster *other,
2313 : : store *out_store,
2314 : : store_manager *mgr)
2315 : : {
2316 : 205398 : for (auto iter : *other)
2317 : : {
2318 : 103324 : const binding_key *iter_key = iter.m_key;
2319 : 103324 : const svalue *iter_sval = iter.m_sval;
2320 : 103324 : const svalue *unknown_sval
2321 : : = mgr->get_svalue_manager ()->get_or_create_unknown_svalue
2322 : 103324 : (iter_sval->get_type ());
2323 : 103324 : m_map.put (iter_key, unknown_sval);
2324 : :
2325 : : /* For any pointers in OTHER, the merger means that the
2326 : : concrete pointer becomes an unknown value, which could
2327 : : show up as a false report of a leak when considering what
2328 : : pointers are live before vs after.
2329 : : Avoid this by marking the base regions they point to as having
2330 : : escaped. */
2331 : 206648 : if (const region_svalue *region_sval
2332 : 103324 : = iter_sval->dyn_cast_region_svalue ())
2333 : : {
2334 : 5752 : const region *base_reg
2335 : 5752 : = region_sval->get_pointee ()->get_base_region ();
2336 : 5752 : if (base_reg->tracked_p ()
2337 : 5752 : && !base_reg->symbolic_for_unknown_ptr_p ())
2338 : : {
2339 : 5713 : binding_cluster *c
2340 : 5713 : = out_store->get_or_create_cluster (*mgr, base_reg);
2341 : 5713 : c->mark_as_escaped ();
2342 : : }
2343 : : }
2344 : : }
2345 : 102074 : }
2346 : :
2347 : : /* Mark this cluster as having escaped. */
2348 : :
2349 : : void
2350 : 46337 : binding_cluster::mark_as_escaped ()
2351 : : {
2352 : 46337 : m_escaped = true;
2353 : 46337 : }
2354 : :
2355 : : /* If this cluster has escaped (by this call, or by an earlier one, or
2356 : : by being an external param), then unbind all values and mark it
2357 : : as "touched", so that it has a conjured value, rather than an
2358 : : initial_svalue.
2359 : : Use P to purge state involving conjured_svalues. */
2360 : :
2361 : : void
2362 : 158022 : binding_cluster::on_unknown_fncall (const gcall &call,
2363 : : store_manager *mgr,
2364 : : const conjured_purge &p)
2365 : : {
2366 : 158022 : if (m_escaped)
2367 : : {
2368 : 28435 : m_map.clear ();
2369 : :
2370 : 28435 : if (!m_base_region->empty_p ())
2371 : : {
2372 : : /* Bind it to a new "conjured" value using CALL. */
2373 : 28435 : const svalue *sval
2374 : : = mgr->get_svalue_manager ()->get_or_create_conjured_svalue
2375 : 28435 : (m_base_region->get_type (), &call, m_base_region, p);
2376 : 28435 : bind (mgr, m_base_region, sval);
2377 : : }
2378 : :
2379 : 28435 : m_touched = true;
2380 : : }
2381 : 158022 : }
2382 : :
2383 : : /* Mark this cluster as having been clobbered by STMT.
2384 : : Use P to purge state involving conjured_svalues. */
2385 : :
2386 : : void
2387 : 522 : binding_cluster::on_asm (const gasm *stmt,
2388 : : store_manager *mgr,
2389 : : const conjured_purge &p)
2390 : : {
2391 : 522 : m_map.clear ();
2392 : :
2393 : : /* Bind it to a new "conjured" value using CALL. */
2394 : 522 : const svalue *sval
2395 : : = mgr->get_svalue_manager ()->get_or_create_conjured_svalue
2396 : 522 : (m_base_region->get_type (), stmt, m_base_region, p);
2397 : 522 : bind (mgr, m_base_region, sval);
2398 : :
2399 : 522 : m_touched = true;
2400 : 522 : }
2401 : :
2402 : : /* Return true if this cluster has escaped. */
2403 : :
2404 : : bool
2405 : 8387086 : binding_cluster::escaped_p () const
2406 : : {
2407 : : /* Consider the "errno" region to always have escaped. */
2408 : 8387086 : if (m_base_region->get_kind () == RK_ERRNO)
2409 : : return true;
2410 : 8357595 : return m_escaped;
2411 : : }
2412 : :
2413 : : /* Return true if this binding_cluster has no information
2414 : : i.e. if there are no bindings, and it hasn't been marked as having
2415 : : escaped, or touched symbolically. */
2416 : :
2417 : : bool
2418 : 182188 : binding_cluster::redundant_p () const
2419 : : {
2420 : 182188 : return (m_map.elements () == 0
2421 : 177044 : && !m_escaped
2422 : 358249 : && !m_touched);
2423 : : }
2424 : :
2425 : : /* Add PV to OUT_PVS, casting it to TYPE if it is not already of that type. */
2426 : :
2427 : : static void
2428 : 8468 : append_pathvar_with_type (path_var pv,
2429 : : tree type,
2430 : : auto_vec<path_var> *out_pvs)
2431 : : {
2432 : 8468 : gcc_assert (pv.m_tree);
2433 : :
2434 : 8468 : if (TREE_TYPE (pv.m_tree) != type)
2435 : 603 : pv.m_tree = build1 (NOP_EXPR, type, pv.m_tree);
2436 : :
2437 : 8468 : out_pvs->safe_push (pv);
2438 : 8468 : }
2439 : :
2440 : : /* Find representative path_vars for SVAL within this binding of BASE_REG,
2441 : : appending the results to OUT_PVS. */
2442 : :
2443 : : void
2444 : 58920 : binding_cluster::get_representative_path_vars (const region_model *model,
2445 : : svalue_set *visited,
2446 : : const region *base_reg,
2447 : : const svalue *sval,
2448 : : logger *logger,
2449 : : auto_vec<path_var> *out_pvs)
2450 : : const
2451 : : {
2452 : 58920 : sval = simplify_for_binding (sval);
2453 : :
2454 : 114247 : for (auto iter : m_map)
2455 : : {
2456 : 55327 : const binding_key *key = iter.m_key;
2457 : 55327 : const svalue *bound_sval = iter.m_sval;
2458 : 55327 : if (bound_sval == sval)
2459 : : {
2460 : 17790 : if (const concrete_binding *ckey
2461 : 8895 : = key->dyn_cast_concrete_binding ())
2462 : : {
2463 : 8831 : auto_vec <const region *> subregions;
2464 : 8831 : base_reg->get_subregions_for_binding
2465 : 8831 : (model->get_manager (),
2466 : : ckey->get_start_bit_offset (),
2467 : : ckey->get_size_in_bits (),
2468 : : sval->get_type (),
2469 : : &subregions);
2470 : 8831 : unsigned i;
2471 : 8831 : const region *subregion;
2472 : 25655 : FOR_EACH_VEC_ELT (subregions, i, subregion)
2473 : : {
2474 : 16824 : if (path_var pv
2475 : 8412 : = model->get_representative_path_var (subregion,
2476 : : visited,
2477 : 8412 : logger))
2478 : 8404 : append_pathvar_with_type (pv, sval->get_type (), out_pvs);
2479 : : }
2480 : 8831 : }
2481 : : else
2482 : : {
2483 : 64 : const symbolic_binding *skey = (const symbolic_binding *)key;
2484 : 128 : if (path_var pv
2485 : 64 : = model->get_representative_path_var (skey->get_region (),
2486 : : visited,
2487 : 64 : logger))
2488 : 64 : append_pathvar_with_type (pv, sval->get_type (), out_pvs);
2489 : : }
2490 : : }
2491 : : }
2492 : 58920 : }
2493 : :
2494 : : /* Get any svalue bound to KEY, or nullptr. */
2495 : :
2496 : : const svalue *
2497 : 2563177 : binding_cluster::get_any_value (const binding_key *key) const
2498 : : {
2499 : 2563177 : return m_map.get (key);
2500 : : }
2501 : :
2502 : : /* If this cluster has a single direct binding for the whole of the region,
2503 : : return it.
2504 : : For use in simplifying dumps. */
2505 : :
2506 : : const svalue *
2507 : 388954 : binding_cluster::maybe_get_simple_value (store_manager *mgr) const
2508 : : {
2509 : : /* Fail gracefully if MGR is nullptr to make it easier to dump store
2510 : : instances in the debugger. */
2511 : 388954 : if (mgr == nullptr)
2512 : : return nullptr;
2513 : :
2514 : 388954 : if (m_map.elements () != 1)
2515 : : return nullptr;
2516 : :
2517 : 197345 : if (m_base_region->empty_p ())
2518 : : return nullptr;
2519 : :
2520 : 197345 : const binding_key *key = binding_key::make (mgr, m_base_region);
2521 : 197345 : return get_any_value (key);
2522 : : }
2523 : :
2524 : : /* class store_manager. */
2525 : :
2526 : : logger *
2527 : 337250 : store_manager::get_logger () const
2528 : : {
2529 : 337250 : return m_mgr->get_logger ();
2530 : : }
2531 : :
2532 : : /* binding consolidation. */
2533 : :
2534 : : const concrete_binding *
2535 : 40449056 : store_manager::get_concrete_binding (bit_offset_t start_bit_offset,
2536 : : bit_offset_t size_in_bits)
2537 : : {
2538 : 40449056 : concrete_binding b (start_bit_offset, size_in_bits);
2539 : 80886033 : if (concrete_binding *existing = m_concrete_binding_key_mgr.get (b))
2540 : : return existing;
2541 : :
2542 : 12079 : concrete_binding *to_save = new concrete_binding (b);
2543 : 12079 : m_concrete_binding_key_mgr.put (b, to_save);
2544 : 12079 : return to_save;
2545 : 40449056 : }
2546 : :
2547 : : const symbolic_binding *
2548 : 4993647 : store_manager::get_symbolic_binding (const region *reg)
2549 : : {
2550 : 4993647 : symbolic_binding b (reg);
2551 : 9967803 : if (symbolic_binding *existing = m_symbolic_binding_key_mgr.get (b))
2552 : : return existing;
2553 : :
2554 : 19491 : symbolic_binding *to_save = new symbolic_binding (b);
2555 : 19491 : m_symbolic_binding_key_mgr.put (b, to_save);
2556 : 19491 : return to_save;
2557 : 4993647 : }
2558 : :
2559 : : /* class store. */
2560 : :
2561 : : /* store's default ctor. */
2562 : :
2563 : 360720 : store::store ()
2564 : 360720 : : m_called_unknown_fn (false)
2565 : : {
2566 : 360720 : }
2567 : :
2568 : : /* store's copy ctor. */
2569 : :
2570 : 3766755 : store::store (const store &other)
2571 : 3766755 : : m_cluster_map (other.m_cluster_map.elements ()),
2572 : 3766755 : m_called_unknown_fn (other.m_called_unknown_fn)
2573 : : {
2574 : 3766755 : for (cluster_map_t::iterator iter = other.m_cluster_map.begin ();
2575 : 27834774 : iter != other.m_cluster_map.end ();
2576 : 24068019 : ++iter)
2577 : : {
2578 : 24068019 : const region *reg = (*iter).first;
2579 : 0 : gcc_assert (reg);
2580 : 24068019 : binding_cluster *c = (*iter).second;
2581 : 24068019 : gcc_assert (c);
2582 : 24068019 : m_cluster_map.put (reg, new binding_cluster (*c));
2583 : : }
2584 : 3766755 : }
2585 : :
2586 : : /* store's dtor. */
2587 : :
2588 : 4127475 : store::~store ()
2589 : : {
2590 : 29456249 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2591 : 29456249 : iter != m_cluster_map.end ();
2592 : 25328774 : ++iter)
2593 : 25328774 : delete (*iter).second;
2594 : 4127475 : }
2595 : :
2596 : : /* store's assignment operator. */
2597 : :
2598 : : store &
2599 : 17894 : store::operator= (const store &other)
2600 : : {
2601 : : /* Delete existing cluster map. */
2602 : 133076 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2603 : 133076 : iter != m_cluster_map.end ();
2604 : 115182 : ++iter)
2605 : 230364 : delete (*iter).second;
2606 : 17894 : m_cluster_map.empty ();
2607 : :
2608 : 17894 : m_called_unknown_fn = other.m_called_unknown_fn;
2609 : :
2610 : 17894 : for (cluster_map_t::iterator iter = other.m_cluster_map.begin ();
2611 : 149165 : iter != other.m_cluster_map.end ();
2612 : 131271 : ++iter)
2613 : : {
2614 : 131271 : const region *reg = (*iter).first;
2615 : 131271 : gcc_assert (reg);
2616 : 131271 : binding_cluster *c = (*iter).second;
2617 : 131271 : gcc_assert (c);
2618 : 131271 : m_cluster_map.put (reg, new binding_cluster (*c));
2619 : : }
2620 : 17894 : return *this;
2621 : : }
2622 : :
2623 : : /* store's equality operator. */
2624 : :
2625 : : bool
2626 : 464181 : store::operator== (const store &other) const
2627 : : {
2628 : 464181 : if (m_called_unknown_fn != other.m_called_unknown_fn)
2629 : : return false;
2630 : :
2631 : 460026 : if (m_cluster_map.elements () != other.m_cluster_map.elements ())
2632 : : return false;
2633 : :
2634 : 2423015 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2635 : 2423015 : iter != m_cluster_map.end ();
2636 : 1986099 : ++iter)
2637 : : {
2638 : 2020738 : const region *reg = (*iter).first;
2639 : 2020738 : binding_cluster *c = (*iter).second;
2640 : 2020738 : binding_cluster **other_slot
2641 : 2020738 : = const_cast <cluster_map_t &> (other.m_cluster_map).get (reg);
2642 : 2020738 : if (other_slot == nullptr)
2643 : 34639 : return false;
2644 : 2019515 : if (*c != **other_slot)
2645 : : return false;
2646 : : }
2647 : :
2648 : 402277 : gcc_checking_assert (hash () == other.hash ());
2649 : :
2650 : : return true;
2651 : : }
2652 : :
2653 : : /* Get a hash value for this store. */
2654 : :
2655 : : hashval_t
2656 : 2058756 : store::hash () const
2657 : : {
2658 : 2058756 : hashval_t result = 0;
2659 : 2058756 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2660 : 12183980 : iter != m_cluster_map.end ();
2661 : 10125224 : ++iter)
2662 : 10125224 : result ^= (*iter).second->hash ();
2663 : 2058756 : return result;
2664 : : }
2665 : :
2666 : : /* Populate OUT with a sorted list of parent regions for the regions in IN,
2667 : : removing duplicate parents. */
2668 : :
2669 : : static void
2670 : 2016 : get_sorted_parent_regions (auto_vec<const region *> *out,
2671 : : auto_vec<const region *> &in)
2672 : : {
2673 : : /* Get the set of parent regions. */
2674 : 2016 : hash_set<const region *> parent_regions;
2675 : 2016 : const region *iter_reg;
2676 : 2016 : unsigned i;
2677 : 9998 : FOR_EACH_VEC_ELT (in, i, iter_reg)
2678 : : {
2679 : 7982 : const region *parent_reg = iter_reg->get_parent_region ();
2680 : 7982 : gcc_assert (parent_reg);
2681 : 7982 : parent_regions.add (parent_reg);
2682 : : }
2683 : :
2684 : : /* Write to OUT. */
2685 : 2016 : for (hash_set<const region *>::iterator iter = parent_regions.begin();
2686 : 10384 : iter != parent_regions.end(); ++iter)
2687 : 4184 : out->safe_push (*iter);
2688 : :
2689 : : /* Sort OUT. */
2690 : 3854 : out->qsort (region::cmp_ptr_ptr);
2691 : 2016 : }
2692 : :
2693 : : /* Dump a representation of this store to PP, using SIMPLE to control how
2694 : : svalues and regions are printed.
2695 : : MGR is used for simplifying dumps if non-NULL, but can also be nullptr
2696 : : (to make it easier to use from the debugger). */
2697 : :
2698 : : void
2699 : 2008 : store::dump_to_pp (pretty_printer *pp, bool simple, bool multiline,
2700 : : store_manager *mgr) const
2701 : : {
2702 : : /* Sort into some deterministic order. */
2703 : 2008 : auto_vec<const region *> base_regions;
2704 : 9990 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2705 : 17972 : iter != m_cluster_map.end (); ++iter)
2706 : : {
2707 : 7982 : const region *base_reg = (*iter).first;
2708 : 7982 : base_regions.safe_push (base_reg);
2709 : : }
2710 : 2008 : base_regions.qsort (region::cmp_ptr_ptr);
2711 : :
2712 : : /* Gather clusters, organize by parent region, so that we can group
2713 : : together locals, globals, etc. */
2714 : 2008 : auto_vec<const region *> parent_regions;
2715 : 2008 : get_sorted_parent_regions (&parent_regions, base_regions);
2716 : :
2717 : 2008 : const region *parent_reg;
2718 : 2008 : unsigned i;
2719 : 6192 : FOR_EACH_VEC_ELT (parent_regions, i, parent_reg)
2720 : : {
2721 : 4184 : gcc_assert (parent_reg);
2722 : 4184 : pp_string (pp, "clusters within ");
2723 : 4184 : parent_reg->dump_to_pp (pp, simple);
2724 : 4184 : if (multiline)
2725 : 1697 : pp_newline (pp);
2726 : : else
2727 : 2487 : pp_string (pp, " {");
2728 : :
2729 : : const region *base_reg;
2730 : : unsigned j;
2731 : 23959 : FOR_EACH_VEC_ELT (base_regions, j, base_reg)
2732 : : {
2733 : : /* This is O(N * M), but N ought to be small. */
2734 : 19775 : if (base_reg->get_parent_region () != parent_reg)
2735 : 11793 : continue;
2736 : 7982 : binding_cluster *cluster
2737 : 7982 : = *const_cast<cluster_map_t &> (m_cluster_map).get (base_reg);
2738 : 7982 : if (!multiline)
2739 : : {
2740 : 4151 : if (j > 0)
2741 : 3152 : pp_string (pp, ", ");
2742 : : }
2743 : 7982 : if (const svalue *sval = cluster->maybe_get_simple_value (mgr))
2744 : : {
2745 : : /* Special-case to simplify dumps for the common case where
2746 : : we just have one value directly bound to the whole of a
2747 : : region. */
2748 : 5725 : if (multiline)
2749 : : {
2750 : 2323 : pp_string (pp, " cluster for: ");
2751 : 2323 : base_reg->dump_to_pp (pp, simple);
2752 : 2323 : pp_string (pp, ": ");
2753 : 2323 : sval->dump_to_pp (pp, simple);
2754 : 2323 : if (cluster->escaped_p ())
2755 : 144 : pp_string (pp, " (ESCAPED)");
2756 : 2323 : if (cluster->touched_p ())
2757 : 6 : pp_string (pp, " (TOUCHED)");
2758 : 2323 : pp_newline (pp);
2759 : : }
2760 : : else
2761 : : {
2762 : 3402 : pp_string (pp, "region: {");
2763 : 3402 : base_reg->dump_to_pp (pp, simple);
2764 : 3402 : pp_string (pp, ", value: ");
2765 : 3402 : sval->dump_to_pp (pp, simple);
2766 : 3402 : if (cluster->escaped_p ())
2767 : 813 : pp_string (pp, " (ESCAPED)");
2768 : 3402 : if (cluster->touched_p ())
2769 : 813 : pp_string (pp, " (TOUCHED)");
2770 : 3402 : pp_string (pp, "}");
2771 : : }
2772 : : }
2773 : 2257 : else if (multiline)
2774 : : {
2775 : 1508 : pp_string (pp, " cluster for: ");
2776 : 1508 : base_reg->dump_to_pp (pp, simple);
2777 : 1508 : pp_newline (pp);
2778 : 1508 : cluster->dump_to_pp (pp, simple, multiline);
2779 : : }
2780 : : else
2781 : : {
2782 : 749 : pp_string (pp, "base region: {");
2783 : 749 : base_reg->dump_to_pp (pp, simple);
2784 : 749 : pp_string (pp, "} has cluster: {");
2785 : 749 : cluster->dump_to_pp (pp, simple, multiline);
2786 : 749 : pp_string (pp, "}");
2787 : : }
2788 : : }
2789 : 4184 : if (!multiline)
2790 : 2487 : pp_string (pp, "}");
2791 : : }
2792 : 2008 : pp_printf (pp, "m_called_unknown_fn: %s",
2793 : 2008 : m_called_unknown_fn ? "TRUE" : "FALSE");
2794 : 2008 : if (multiline)
2795 : 912 : pp_newline (pp);
2796 : 2008 : }
2797 : :
2798 : : /* Dump a multiline representation of this store to stderr. */
2799 : :
2800 : : DEBUG_FUNCTION void
2801 : 0 : store::dump (bool simple) const
2802 : : {
2803 : 0 : tree_dump_pretty_printer pp (stderr);
2804 : 0 : dump_to_pp (&pp, simple, true, nullptr);
2805 : 0 : pp_newline (&pp);
2806 : 0 : }
2807 : :
2808 : : /* Assert that this object is valid. */
2809 : :
2810 : : void
2811 : 1763782 : store::validate () const
2812 : : {
2813 : 10860943 : for (auto iter : m_cluster_map)
2814 : 9097161 : iter.second->validate ();
2815 : 1763782 : }
2816 : :
2817 : : /* Return a new json::object of the form
2818 : : {PARENT_REGION_DESC: {BASE_REGION_DESC: object for binding_map,
2819 : : ... for each cluster within parent region},
2820 : : ...for each parent region,
2821 : : "called_unknown_fn": true/false}. */
2822 : :
2823 : : std::unique_ptr<json::object>
2824 : 4 : store::to_json () const
2825 : : {
2826 : 4 : auto store_obj = std::make_unique<json::object> ();
2827 : :
2828 : : /* Sort into some deterministic order. */
2829 : 4 : auto_vec<const region *> base_regions;
2830 : 4 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2831 : 4 : iter != m_cluster_map.end (); ++iter)
2832 : : {
2833 : 0 : const region *base_reg = (*iter).first;
2834 : 0 : base_regions.safe_push (base_reg);
2835 : : }
2836 : 4 : base_regions.qsort (region::cmp_ptr_ptr);
2837 : :
2838 : : /* Gather clusters, organize by parent region, so that we can group
2839 : : together locals, globals, etc. */
2840 : 4 : auto_vec<const region *> parent_regions;
2841 : 4 : get_sorted_parent_regions (&parent_regions, base_regions);
2842 : :
2843 : 4 : const region *parent_reg;
2844 : 4 : unsigned i;
2845 : 4 : FOR_EACH_VEC_ELT (parent_regions, i, parent_reg)
2846 : : {
2847 : 0 : gcc_assert (parent_reg);
2848 : :
2849 : 0 : auto clusters_in_parent_reg_obj = std::make_unique<json::object> ();
2850 : :
2851 : 0 : const region *base_reg;
2852 : 0 : unsigned j;
2853 : 0 : FOR_EACH_VEC_ELT (base_regions, j, base_reg)
2854 : : {
2855 : : /* This is O(N * M), but N ought to be small. */
2856 : 0 : if (base_reg->get_parent_region () != parent_reg)
2857 : 0 : continue;
2858 : 0 : binding_cluster *cluster
2859 : 0 : = *const_cast<cluster_map_t &> (m_cluster_map).get (base_reg);
2860 : 0 : label_text base_reg_desc = base_reg->get_desc ();
2861 : 0 : clusters_in_parent_reg_obj->set (base_reg_desc.get (),
2862 : 0 : cluster->to_json ());
2863 : 0 : }
2864 : 0 : label_text parent_reg_desc = parent_reg->get_desc ();
2865 : 0 : store_obj->set (parent_reg_desc.get (),
2866 : : std::move (clusters_in_parent_reg_obj));
2867 : 0 : }
2868 : :
2869 : 4 : store_obj->set_bool ("called_unknown_fn", m_called_unknown_fn);
2870 : :
2871 : 4 : return store_obj;
2872 : 4 : }
2873 : :
2874 : : std::unique_ptr<text_art::tree_widget>
2875 : 4 : store::make_dump_widget (const text_art::dump_widget_info &dwi,
2876 : : store_manager *mgr) const
2877 : : {
2878 : 4 : std::unique_ptr<text_art::tree_widget> store_widget
2879 : 4 : (text_art::tree_widget::make (dwi, "Store"));
2880 : :
2881 : 4 : store_widget->add_child
2882 : 8 : (text_art::tree_widget::from_fmt (dwi, nullptr,
2883 : : "m_called_unknown_fn: %s",
2884 : 4 : m_called_unknown_fn ? "true" : "false"));
2885 : :
2886 : : /* Sort into some deterministic order. */
2887 : 4 : auto_vec<const region *> base_regions;
2888 : 4 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2889 : 4 : iter != m_cluster_map.end (); ++iter)
2890 : : {
2891 : 0 : const region *base_reg = (*iter).first;
2892 : 0 : base_regions.safe_push (base_reg);
2893 : : }
2894 : 4 : base_regions.qsort (region::cmp_ptr_ptr);
2895 : :
2896 : : /* Gather clusters, organize by parent region, so that we can group
2897 : : together locals, globals, etc. */
2898 : 4 : auto_vec<const region *> parent_regions;
2899 : 4 : get_sorted_parent_regions (&parent_regions, base_regions);
2900 : :
2901 : 4 : const region *parent_reg;
2902 : 4 : unsigned i;
2903 : 4 : FOR_EACH_VEC_ELT (parent_regions, i, parent_reg)
2904 : : {
2905 : 0 : gcc_assert (parent_reg);
2906 : :
2907 : 0 : pretty_printer the_pp;
2908 : 0 : pretty_printer * const pp = &the_pp;
2909 : 0 : pp_format_decoder (pp) = default_tree_printer;
2910 : 0 : pp_show_color (pp) = true;
2911 : 0 : const bool simple = true;
2912 : :
2913 : 0 : parent_reg->dump_to_pp (pp, simple);
2914 : :
2915 : 0 : std::unique_ptr<text_art::tree_widget> parent_reg_widget
2916 : 0 : (text_art::tree_widget::make (dwi, pp));
2917 : :
2918 : 0 : const region *base_reg;
2919 : 0 : unsigned j;
2920 : 0 : FOR_EACH_VEC_ELT (base_regions, j, base_reg)
2921 : : {
2922 : : /* This is O(N * M), but N ought to be small. */
2923 : 0 : if (base_reg->get_parent_region () != parent_reg)
2924 : 0 : continue;
2925 : 0 : binding_cluster *cluster
2926 : 0 : = *const_cast<cluster_map_t &> (m_cluster_map).get (base_reg);
2927 : 0 : parent_reg_widget->add_child
2928 : 0 : (cluster->make_dump_widget (dwi, mgr));
2929 : : }
2930 : 0 : store_widget->add_child (std::move (parent_reg_widget));
2931 : 0 : }
2932 : :
2933 : 4 : return store_widget;
2934 : 4 : }
2935 : :
2936 : : /* Get any svalue bound to REG, or nullptr. */
2937 : :
2938 : : const svalue *
2939 : 3771852 : store::get_any_binding (store_manager *mgr, const region *reg) const
2940 : : {
2941 : 3771852 : const region *base_reg = reg->get_base_region ();
2942 : 3771852 : binding_cluster **cluster_slot
2943 : 3771852 : = const_cast <cluster_map_t &> (m_cluster_map).get (base_reg);
2944 : 3771852 : if (!cluster_slot)
2945 : : return nullptr;
2946 : 1231000 : return (*cluster_slot)->get_any_binding (mgr, reg);
2947 : : }
2948 : :
2949 : : /* Set the value of LHS_REG to RHS_SVAL. */
2950 : :
2951 : : void
2952 : 337250 : store::set_value (store_manager *mgr, const region *lhs_reg,
2953 : : const svalue *rhs_sval,
2954 : : uncertainty_t *uncertainty)
2955 : : {
2956 : 337250 : logger *logger = mgr->get_logger ();
2957 : 337250 : LOG_SCOPE (logger);
2958 : :
2959 : 337250 : remove_overlapping_bindings (mgr, lhs_reg, uncertainty);
2960 : :
2961 : 337250 : if (lhs_reg->get_type ())
2962 : 324787 : rhs_sval = simplify_for_binding (rhs_sval);
2963 : : /* ...but if we have no type for the region, retain any cast. */
2964 : :
2965 : 337250 : const region *lhs_base_reg = lhs_reg->get_base_region ();
2966 : 337250 : binding_cluster *lhs_cluster;
2967 : 337250 : if (lhs_base_reg->symbolic_for_unknown_ptr_p ())
2968 : : {
2969 : : /* Reject attempting to bind values into a symbolic region
2970 : : for an unknown ptr; merely invalidate values below. */
2971 : 3230 : lhs_cluster = nullptr;
2972 : :
2973 : : /* The LHS of the write is *UNKNOWN. If the RHS is a pointer,
2974 : : then treat the region being pointed to as having escaped. */
2975 : 3230 : if (const region_svalue *ptr_sval = rhs_sval->dyn_cast_region_svalue ())
2976 : : {
2977 : 161 : const region *ptr_dst = ptr_sval->get_pointee ();
2978 : 161 : const region *ptr_base_reg = ptr_dst->get_base_region ();
2979 : 161 : mark_as_escaped (*mgr, ptr_base_reg);
2980 : : }
2981 : 3230 : if (uncertainty)
2982 : 1568 : uncertainty->on_maybe_bound_sval (rhs_sval);
2983 : : }
2984 : 334020 : else if (lhs_base_reg->tracked_p ())
2985 : : {
2986 : 333913 : lhs_cluster = get_or_create_cluster (*mgr, lhs_base_reg);
2987 : 333913 : lhs_cluster->bind (mgr, lhs_reg, rhs_sval);
2988 : : }
2989 : : else
2990 : : {
2991 : : /* Reject attempting to bind values into an untracked region;
2992 : : merely invalidate values below. */
2993 : : lhs_cluster = nullptr;
2994 : : }
2995 : :
2996 : : /* Bindings to a cluster can affect other clusters if a symbolic
2997 : : base region is involved.
2998 : : Writes to concrete clusters can't affect other concrete clusters,
2999 : : but can affect symbolic clusters.
3000 : : Writes to symbolic clusters can affect both concrete and symbolic
3001 : : clusters.
3002 : : Invalidate our knowledge of other clusters that might have been
3003 : : affected by the write.
3004 : : Gather the set of all svalues that might still be live even if
3005 : : the store doesn't refer to them. */
3006 : 337250 : svalue_set maybe_live_values;
3007 : 4440452 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3008 : 8543654 : iter != m_cluster_map.end (); ++iter)
3009 : : {
3010 : 4103202 : const region *iter_base_reg = (*iter).first;
3011 : 4103202 : binding_cluster *iter_cluster = (*iter).second;
3012 : 4103202 : if (iter_base_reg != lhs_base_reg
3013 : 4103202 : && (lhs_cluster == nullptr
3014 : 3717315 : || lhs_cluster->symbolic_p ()
3015 : 3642732 : || iter_cluster->symbolic_p ()))
3016 : : {
3017 : 552809 : tristate t_alias = eval_alias (lhs_base_reg, iter_base_reg);
3018 : 552809 : switch (t_alias.get_value ())
3019 : : {
3020 : 0 : default:
3021 : 0 : gcc_unreachable ();
3022 : :
3023 : 56195 : case tristate::TS_UNKNOWN:
3024 : 56195 : if (logger)
3025 : : {
3026 : 7 : pretty_printer *pp = logger->get_printer ();
3027 : 7 : logger->start_log_line ();
3028 : 7 : logger->log_partial ("possible aliasing of ");
3029 : 7 : iter_base_reg->dump_to_pp (pp, true);
3030 : 7 : logger->log_partial (" when writing SVAL: ");
3031 : 7 : rhs_sval->dump_to_pp (pp, true);
3032 : 7 : logger->log_partial (" to LHS_REG: ");
3033 : 7 : lhs_reg->dump_to_pp (pp, true);
3034 : 7 : logger->end_log_line ();
3035 : : }
3036 : : /* Mark all of iter_cluster's iter_base_reg as unknown,
3037 : : using LHS_REG when considering overlaps, to handle
3038 : : symbolic vs concrete issues. */
3039 : 56195 : iter_cluster->mark_region_as_unknown
3040 : 56195 : (mgr,
3041 : : iter_base_reg, /* reg_to_bind */
3042 : : lhs_reg, /* reg_for_overlap */
3043 : : uncertainty,
3044 : : &maybe_live_values);
3045 : 56195 : break;
3046 : :
3047 : 0 : case tristate::TS_TRUE:
3048 : 0 : gcc_unreachable ();
3049 : : break;
3050 : :
3051 : : case tristate::TS_FALSE:
3052 : : /* If they can't be aliases, then don't invalidate this
3053 : : cluster. */
3054 : : break;
3055 : : }
3056 : : }
3057 : : }
3058 : : /* Given the set of svalues that might still be live, process them
3059 : : (e.g. marking regions as escaped).
3060 : : We do this after the iteration to avoid potentially changing
3061 : : m_cluster_map whilst iterating over it. */
3062 : 337250 : on_maybe_live_values (*mgr, maybe_live_values);
3063 : 337250 : }
3064 : :
3065 : : /* Determine if BASE_REG_A could be an alias of BASE_REG_B. */
3066 : :
3067 : : tristate
3068 : 553370 : store::eval_alias (const region *base_reg_a,
3069 : : const region *base_reg_b) const
3070 : : {
3071 : : /* SSA names can't alias. */
3072 : 553370 : tree decl_a = base_reg_a->maybe_get_decl ();
3073 : 553370 : if (decl_a && TREE_CODE (decl_a) == SSA_NAME)
3074 : 369114 : return tristate::TS_FALSE;
3075 : 184256 : tree decl_b = base_reg_b->maybe_get_decl ();
3076 : 184256 : if (decl_b && TREE_CODE (decl_b) == SSA_NAME)
3077 : 60966 : return tristate::TS_FALSE;
3078 : :
3079 : : /* Try both ways, for symmetry. */
3080 : 123290 : tristate ts_ab = eval_alias_1 (base_reg_a, base_reg_b);
3081 : 123290 : if (ts_ab.is_false ())
3082 : 22307 : return tristate::TS_FALSE;
3083 : 100983 : tristate ts_ba = eval_alias_1 (base_reg_b, base_reg_a);
3084 : 100983 : if (ts_ba.is_false ())
3085 : 44522 : return tristate::TS_FALSE;
3086 : 56461 : return tristate::TS_UNKNOWN;
3087 : : }
3088 : :
3089 : : /* Half of store::eval_alias; called twice for symmetry. */
3090 : :
3091 : : tristate
3092 : 224273 : store::eval_alias_1 (const region *base_reg_a,
3093 : : const region *base_reg_b) const
3094 : : {
3095 : : /* If they're in different memory spaces, they can't alias. */
3096 : 224273 : {
3097 : 224273 : enum memory_space memspace_a = base_reg_a->get_memory_space ();
3098 : 224273 : if (memspace_a != MEMSPACE_UNKNOWN)
3099 : : {
3100 : 77197 : enum memory_space memspace_b = base_reg_b->get_memory_space ();
3101 : 77197 : if (memspace_b != MEMSPACE_UNKNOWN
3102 : 77197 : && memspace_a != memspace_b)
3103 : 249 : return tristate::TS_FALSE;
3104 : : }
3105 : : }
3106 : :
3107 : 448048 : if (const symbolic_region *sym_reg_a
3108 : 224024 : = base_reg_a->dyn_cast_symbolic_region ())
3109 : : {
3110 : 141699 : const svalue *sval_a = sym_reg_a->get_pointer ();
3111 : 141699 : if (tree decl_b = base_reg_b->maybe_get_decl ())
3112 : : {
3113 : 72298 : if (!may_be_aliased (decl_b))
3114 : 42078 : return tristate::TS_FALSE;
3115 : 30220 : if (sval_a->get_kind () == SK_INITIAL)
3116 : 18788 : if (!is_global_var (decl_b))
3117 : : {
3118 : : /* The initial value of a pointer can't point to a local. */
3119 : 13085 : return tristate::TS_FALSE;
3120 : : }
3121 : : }
3122 : 86536 : if (sval_a->get_kind () == SK_INITIAL
3123 : 86536 : && base_reg_b->get_kind () == RK_HEAP_ALLOCATED)
3124 : : {
3125 : : /* The initial value of a pointer can't point to a
3126 : : region that was allocated on the heap after the beginning of the
3127 : : path. */
3128 : 11122 : return tristate::TS_FALSE;
3129 : : }
3130 : 150828 : if (const widening_svalue *widening_sval_a
3131 : 75414 : = sval_a->dyn_cast_widening_svalue ())
3132 : : {
3133 : 3645 : const svalue *base = widening_sval_a->get_base_svalue ();
3134 : 7290 : if (const region_svalue *region_sval
3135 : 3645 : = base->dyn_cast_region_svalue ())
3136 : : {
3137 : 561 : const region *pointee = region_sval->get_pointee ();
3138 : : /* If we have sval_a is WIDENING(®ION, OP), and
3139 : : B can't alias REGION, then B can't alias A either.
3140 : : For example, A might arise from
3141 : : for (ptr = ®ION; ...; ptr++)
3142 : : where sval_a is ptr in the 2nd iteration of the loop.
3143 : : We want to ensure that "*ptr" can only clobber things
3144 : : within REGION's base region. */
3145 : 561 : tristate ts = eval_alias (pointee->get_base_region (),
3146 : : base_reg_b);
3147 : 561 : if (ts.is_false ())
3148 : 295 : return tristate::TS_FALSE;
3149 : : }
3150 : : }
3151 : : }
3152 : 157444 : return tristate::TS_UNKNOWN;
3153 : : }
3154 : :
3155 : : /* Record all of the values in MAYBE_LIVE_VALUES as being possibly live. */
3156 : :
3157 : : void
3158 : 337539 : store::on_maybe_live_values (store_manager &mgr,
3159 : : const svalue_set &maybe_live_values)
3160 : : {
3161 : 414041 : for (auto sval : maybe_live_values)
3162 : : {
3163 : 38251 : if (const region_svalue *ptr_sval = sval->dyn_cast_region_svalue ())
3164 : : {
3165 : 315 : const region *base_reg = ptr_sval->get_pointee ()->get_base_region ();
3166 : 315 : mark_as_escaped (mgr, base_reg);
3167 : : }
3168 : : }
3169 : 337539 : }
3170 : :
3171 : : /* Remove all bindings overlapping REG within this store. */
3172 : :
3173 : : void
3174 : 7011 : store::clobber_region (store_manager *mgr, const region *reg)
3175 : : {
3176 : 7011 : const region *base_reg = reg->get_base_region ();
3177 : 7011 : binding_cluster **slot = m_cluster_map.get (base_reg);
3178 : 7011 : if (!slot)
3179 : 2490 : return;
3180 : 4521 : binding_cluster *cluster = *slot;
3181 : 4521 : cluster->clobber_region (mgr, reg);
3182 : 4521 : if (cluster->redundant_p ())
3183 : : {
3184 : 2991 : delete cluster;
3185 : 2991 : m_cluster_map.remove (base_reg);
3186 : : }
3187 : : }
3188 : :
3189 : : /* Remove any bindings for REG within this store. */
3190 : :
3191 : : void
3192 : 177667 : store::purge_region (store_manager *mgr, const region *reg)
3193 : : {
3194 : 177667 : const region *base_reg = reg->get_base_region ();
3195 : 177667 : binding_cluster **slot = m_cluster_map.get (base_reg);
3196 : 177667 : if (!slot)
3197 : 0 : return;
3198 : 177667 : binding_cluster *cluster = *slot;
3199 : 177667 : cluster->purge_region (mgr, reg);
3200 : 177667 : if (cluster->redundant_p ())
3201 : : {
3202 : 172269 : delete cluster;
3203 : 172269 : m_cluster_map.remove (base_reg);
3204 : : }
3205 : : }
3206 : :
3207 : : /* Fill REG with SVAL. */
3208 : :
3209 : : void
3210 : 1426 : store::fill_region (store_manager *mgr, const region *reg, const svalue *sval)
3211 : : {
3212 : : /* Filling an empty region is a no-op. */
3213 : 1426 : if (reg->empty_p ())
3214 : : return;
3215 : :
3216 : 1398 : const region *base_reg = reg->get_base_region ();
3217 : 1398 : if (base_reg->symbolic_for_unknown_ptr_p ()
3218 : 1398 : || !base_reg->tracked_p ())
3219 : 6 : return;
3220 : 1392 : binding_cluster *cluster = get_or_create_cluster (*mgr, base_reg);
3221 : 1392 : cluster->fill_region (mgr, reg, sval);
3222 : : }
3223 : :
3224 : : /* Zero-fill REG. */
3225 : :
3226 : : void
3227 : 769 : store::zero_fill_region (store_manager *mgr, const region *reg)
3228 : : {
3229 : 769 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
3230 : 769 : const svalue *zero_sval = sval_mgr->get_or_create_int_cst (char_type_node, 0);
3231 : 769 : fill_region (mgr, reg, zero_sval);
3232 : 769 : }
3233 : :
3234 : : /* Mark REG as having unknown content. */
3235 : :
3236 : : void
3237 : 289 : store::mark_region_as_unknown (store_manager *mgr, const region *reg,
3238 : : uncertainty_t *uncertainty,
3239 : : svalue_set *maybe_live_values)
3240 : : {
3241 : 289 : const region *base_reg = reg->get_base_region ();
3242 : 289 : if (base_reg->symbolic_for_unknown_ptr_p ()
3243 : 289 : || !base_reg->tracked_p ())
3244 : 0 : return;
3245 : 289 : binding_cluster *cluster = get_or_create_cluster (*mgr, base_reg);
3246 : 289 : cluster->mark_region_as_unknown (mgr, reg, reg, uncertainty,
3247 : : maybe_live_values);
3248 : : }
3249 : :
3250 : : /* Purge state involving SVAL. */
3251 : :
3252 : : void
3253 : 38620 : store::purge_state_involving (const svalue *sval,
3254 : : region_model_manager *sval_mgr)
3255 : : {
3256 : 38620 : auto_vec <const region *> base_regs_to_purge;
3257 : 1207020 : for (auto iter : m_cluster_map)
3258 : : {
3259 : 584200 : const region *base_reg = iter.first;
3260 : 584200 : if (base_reg->involves_p (sval))
3261 : 189 : base_regs_to_purge.safe_push (base_reg);
3262 : : else
3263 : : {
3264 : 584011 : binding_cluster *cluster = iter.second;
3265 : 584011 : cluster->purge_state_involving (sval, sval_mgr);
3266 : : }
3267 : : }
3268 : :
3269 : 39187 : for (auto iter : base_regs_to_purge)
3270 : 189 : purge_cluster (iter);
3271 : 38620 : }
3272 : :
3273 : : /* Get the cluster for BASE_REG, or nullptr (const version). */
3274 : :
3275 : : const binding_cluster *
3276 : 2479251 : store::get_cluster (const region *base_reg) const
3277 : : {
3278 : 2479251 : gcc_assert (base_reg);
3279 : 2479251 : gcc_assert (base_reg->get_base_region () == base_reg);
3280 : 4958502 : if (binding_cluster **slot
3281 : 2479251 : = const_cast <cluster_map_t &> (m_cluster_map).get (base_reg))
3282 : 2354922 : return *slot;
3283 : : else
3284 : : return nullptr;
3285 : : }
3286 : :
3287 : : /* Get the cluster for BASE_REG, or nullptr (non-const version). */
3288 : :
3289 : : binding_cluster *
3290 : 9175289 : store::get_cluster (const region *base_reg)
3291 : : {
3292 : 9175289 : gcc_assert (base_reg);
3293 : 9175289 : gcc_assert (base_reg->get_base_region () == base_reg);
3294 : 9175289 : if (binding_cluster **slot = m_cluster_map.get (base_reg))
3295 : 7762171 : return *slot;
3296 : : else
3297 : : return nullptr;
3298 : : }
3299 : :
3300 : : /* Get the cluster for BASE_REG, creating it if doesn't already exist. */
3301 : :
3302 : : binding_cluster *
3303 : 1542557 : store::get_or_create_cluster (store_manager &store_mgr,
3304 : : const region *base_reg)
3305 : : {
3306 : 1542557 : gcc_assert (base_reg);
3307 : 1542557 : gcc_assert (base_reg->get_base_region () == base_reg);
3308 : :
3309 : : /* We shouldn't create clusters for dereferencing an UNKNOWN ptr. */
3310 : 1542557 : gcc_assert (!base_reg->symbolic_for_unknown_ptr_p ());
3311 : :
3312 : : /* We shouldn't create clusters for base regions that aren't trackable. */
3313 : 1542557 : gcc_assert (base_reg->tracked_p ());
3314 : :
3315 : 1542557 : if (binding_cluster **slot = m_cluster_map.get (base_reg))
3316 : 55574 : return *slot;
3317 : :
3318 : 1486983 : binding_cluster *cluster = new binding_cluster (store_mgr, base_reg);
3319 : 1486983 : m_cluster_map.put (base_reg, cluster);
3320 : :
3321 : 1486983 : return cluster;
3322 : : }
3323 : :
3324 : : /* Remove any cluster for BASE_REG, for use by
3325 : : region_model::unbind_region_and_descendents
3326 : : when popping stack frames and handling deleted heap regions. */
3327 : :
3328 : : void
3329 : 36077 : store::purge_cluster (const region *base_reg)
3330 : : {
3331 : 36077 : gcc_assert (base_reg->get_base_region () == base_reg);
3332 : 36077 : binding_cluster **slot = m_cluster_map.get (base_reg);
3333 : 36077 : if (!slot)
3334 : : return;
3335 : 36077 : binding_cluster *cluster = *slot;
3336 : 72154 : delete cluster;
3337 : 36077 : m_cluster_map.remove (base_reg);
3338 : : }
3339 : :
3340 : : /* Attempt to merge STORE_A and STORE_B into OUT_STORE.
3341 : : Return true if successful, or false if the stores can't be merged. */
3342 : :
3343 : : bool
3344 : 172300 : store::can_merge_p (const store *store_a, const store *store_b,
3345 : : store *out_store, store_manager *mgr,
3346 : : model_merger *merger)
3347 : : {
3348 : 172300 : if (store_a->m_called_unknown_fn || store_b->m_called_unknown_fn)
3349 : 82742 : out_store->m_called_unknown_fn = true;
3350 : :
3351 : : /* Get the union of all base regions for STORE_A and STORE_B. */
3352 : 172300 : hash_set<const region *> base_regions;
3353 : 1771282 : for (cluster_map_t::iterator iter_a = store_a->m_cluster_map.begin ();
3354 : 3370264 : iter_a != store_a->m_cluster_map.end (); ++iter_a)
3355 : : {
3356 : 1598982 : const region *base_reg_a = (*iter_a).first;
3357 : 1598982 : base_regions.add (base_reg_a);
3358 : : }
3359 : 1702093 : for (cluster_map_t::iterator iter_b = store_b->m_cluster_map.begin ();
3360 : 3231886 : iter_b != store_b->m_cluster_map.end (); ++iter_b)
3361 : : {
3362 : 1529793 : const region *base_reg_b = (*iter_b).first;
3363 : 1529793 : base_regions.add (base_reg_b);
3364 : : }
3365 : :
3366 : : /* Sort the base regions before considering them. This ought not to
3367 : : affect the results, but can affect which types UNKNOWN_REGIONs are
3368 : : created for in a run; sorting them thus avoids minor differences
3369 : : in logfiles. */
3370 : 172300 : auto_vec<const region *> vec_base_regions (base_regions.elements ());
3371 : 172300 : for (hash_set<const region *>::iterator iter = base_regions.begin ();
3372 : 3454240 : iter != base_regions.end (); ++iter)
3373 : 1640970 : vec_base_regions.quick_push (*iter);
3374 : 172300 : vec_base_regions.qsort (region::cmp_ptr_ptr);
3375 : : unsigned i;
3376 : : const region *base_reg;
3377 : 1398040 : FOR_EACH_VEC_ELT (vec_base_regions, i, base_reg)
3378 : : {
3379 : 1157634 : const binding_cluster *cluster_a = store_a->get_cluster (base_reg);
3380 : 1157634 : const binding_cluster *cluster_b = store_b->get_cluster (base_reg);
3381 : : /* At least one of cluster_a and cluster_b must be non-NULL. */
3382 : 1157634 : binding_cluster *out_cluster
3383 : 1157634 : = out_store->get_or_create_cluster (*mgr, base_reg);
3384 : 1157634 : if (!binding_cluster::can_merge_p (cluster_a, cluster_b,
3385 : : out_cluster, out_store, mgr, merger))
3386 : : return false;
3387 : : }
3388 : : return true;
3389 : 172300 : }
3390 : :
3391 : : /* Mark the cluster for BASE_REG as having escaped.
3392 : : For use when handling an unrecognized function call, and
3393 : : for params to "top-level" calls.
3394 : : Further unknown function calls could touch it, even if the cluster
3395 : : isn't reachable from args of those calls. */
3396 : :
3397 : : void
3398 : 43133 : store::mark_as_escaped (store_manager &mgr, const region *base_reg)
3399 : : {
3400 : 43133 : gcc_assert (base_reg);
3401 : 43133 : gcc_assert (base_reg->get_base_region () == base_reg);
3402 : :
3403 : 43133 : if (base_reg->symbolic_for_unknown_ptr_p ()
3404 : 43133 : || !base_reg->tracked_p ())
3405 : 5118 : return;
3406 : :
3407 : 38015 : binding_cluster *cluster = get_or_create_cluster (mgr, base_reg);
3408 : 38015 : cluster->mark_as_escaped ();
3409 : : }
3410 : :
3411 : : /* Handle an unknown fncall by updating any clusters that have escaped
3412 : : (either in this fncall, or in a prior one). */
3413 : :
3414 : : void
3415 : 19273 : store::on_unknown_fncall (const gcall &call, store_manager *mgr,
3416 : : const conjured_purge &p)
3417 : : {
3418 : 19273 : m_called_unknown_fn = true;
3419 : :
3420 : 177295 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3421 : 335317 : iter != m_cluster_map.end (); ++iter)
3422 : 158022 : (*iter).second->on_unknown_fncall (call, mgr, p);
3423 : 19273 : }
3424 : :
3425 : : /* Return true if a non-const pointer to BASE_REG (or something within it)
3426 : : has escaped to code outside of the TU being analyzed. */
3427 : :
3428 : : bool
3429 : 7853965 : store::escaped_p (const region *base_reg) const
3430 : : {
3431 : 7853965 : gcc_assert (base_reg);
3432 : 7853965 : gcc_assert (base_reg->get_base_region () == base_reg);
3433 : :
3434 : : /* "errno" can always be modified by external code. */
3435 : 7853965 : if (base_reg->get_kind () == RK_ERRNO)
3436 : : return true;
3437 : :
3438 : 15509064 : if (binding_cluster **cluster_slot
3439 : 7754532 : = const_cast <cluster_map_t &>(m_cluster_map).get (base_reg))
3440 : 7754532 : return (*cluster_slot)->escaped_p ();
3441 : : return false;
3442 : : }
3443 : :
3444 : : /* Populate OUT_PVS with a list of path_vars for describing SVAL based on
3445 : : this store, using VISITED to ensure the traversal terminates. */
3446 : :
3447 : : void
3448 : 14186 : store::get_representative_path_vars (const region_model *model,
3449 : : svalue_set *visited,
3450 : : const svalue *sval,
3451 : : logger *logger,
3452 : : auto_vec<path_var> *out_pvs) const
3453 : : {
3454 : 14186 : gcc_assert (sval);
3455 : :
3456 : : /* Find all bindings that reference SVAL. */
3457 : 73106 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3458 : 132026 : iter != m_cluster_map.end (); ++iter)
3459 : : {
3460 : 58920 : const region *base_reg = (*iter).first;
3461 : 58920 : binding_cluster *cluster = (*iter).second;
3462 : 58920 : cluster->get_representative_path_vars (model, visited, base_reg, sval,
3463 : : logger,
3464 : : out_pvs);
3465 : : }
3466 : :
3467 : 14186 : if (const initial_svalue *init_sval = sval->dyn_cast_initial_svalue ())
3468 : : {
3469 : 2567 : const region *reg = init_sval->get_region ();
3470 : 2567 : if (path_var pv = model->get_representative_path_var (reg,
3471 : : visited,
3472 : 2567 : logger))
3473 : 2447 : out_pvs->safe_push (pv);
3474 : : }
3475 : 14186 : }
3476 : :
3477 : : /* Remove all bindings overlapping REG within this store, removing
3478 : : any clusters that become redundant.
3479 : :
3480 : : If UNCERTAINTY is non-NULL, use it to record any svalues that
3481 : : were removed, as being maybe-bound. */
3482 : :
3483 : : void
3484 : 337250 : store::remove_overlapping_bindings (store_manager *mgr, const region *reg,
3485 : : uncertainty_t *uncertainty)
3486 : : {
3487 : 337250 : const region *base_reg = reg->get_base_region ();
3488 : 337250 : if (binding_cluster **cluster_slot = m_cluster_map.get (base_reg))
3489 : : {
3490 : 50669 : binding_cluster *cluster = *cluster_slot;
3491 : 50669 : if (reg == base_reg && !escaped_p (base_reg))
3492 : : {
3493 : : /* Remove whole cluster. */
3494 : 30980 : m_cluster_map.remove (base_reg);
3495 : 61960 : delete cluster;
3496 : 30980 : return;
3497 : : }
3498 : : /* Pass nullptr for the maybe_live_values here, as we don't want to
3499 : : record the old svalues as being maybe-bound. */
3500 : 19689 : cluster->remove_overlapping_bindings (mgr, reg, uncertainty, nullptr);
3501 : : }
3502 : : }
3503 : :
3504 : : /* Subclass of visitor that accumulates a hash_set of the regions that
3505 : : were visited. */
3506 : :
3507 : 2168710 : struct region_finder : public visitor
3508 : : {
3509 : 18900488 : void visit_region (const region *reg) final override
3510 : : {
3511 : 18900488 : m_regs.add (reg);
3512 : 18900488 : }
3513 : :
3514 : : hash_set<const region *> m_regs;
3515 : : };
3516 : :
3517 : : /* Canonicalize this store, to maximize the chance of equality between
3518 : : instances. */
3519 : :
3520 : : void
3521 : 1084355 : store::canonicalize (store_manager *mgr)
3522 : : {
3523 : : /* If we have e.g.:
3524 : : cluster for: HEAP_ALLOCATED_REGION(543)
3525 : : ESCAPED
3526 : : TOUCHED
3527 : : where the heap region is empty and unreferenced, then purge that
3528 : : cluster, to avoid unbounded state chains involving these. */
3529 : :
3530 : : /* Find regions that are referenced by bound values in the store. */
3531 : 1084355 : region_finder s;
3532 : 6905857 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3533 : 12727359 : iter != m_cluster_map.end (); ++iter)
3534 : : {
3535 : 5821502 : binding_cluster *cluster = (*iter).second;
3536 : 5821502 : for (binding_cluster::iterator_t bind_iter = cluster->m_map.begin ();
3537 : 11905553 : bind_iter != cluster->m_map.end (); ++bind_iter)
3538 : 6084051 : (*bind_iter).m_sval->accept (&s);
3539 : : }
3540 : :
3541 : : /* Locate heap-allocated regions that have empty bindings that weren't
3542 : : found above. */
3543 : 1084355 : hash_set<const region *> purgeable_regions;
3544 : 6905857 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3545 : 12727359 : iter != m_cluster_map.end (); ++iter)
3546 : : {
3547 : 5821502 : const region *base_reg = (*iter).first;
3548 : 5821502 : binding_cluster *cluster = (*iter).second;
3549 : 5821502 : if (base_reg->get_kind () == RK_HEAP_ALLOCATED)
3550 : : {
3551 : : /* Don't purge a heap-allocated region that's been marked as
3552 : : escaping, since this could be recording that a ptr to it
3553 : : was written to an unknown symbolic region along this
3554 : : path, and so we don't know whether it's referenced or
3555 : : not, and hence should report it as leaking
3556 : : (PR analyzer/106473). */
3557 : 483625 : if (cluster->escaped_p ())
3558 : 229912 : continue;
3559 : :
3560 : 253713 : if (cluster->empty_p ())
3561 : 612 : if (!s.m_regs.contains (base_reg))
3562 : 0 : purgeable_regions.add (base_reg);
3563 : :
3564 : : /* Also cover the UNKNOWN case. */
3565 : 253713 : if (const svalue *sval = cluster->maybe_get_simple_value (mgr))
3566 : 67683 : if (sval->get_kind () == SK_UNKNOWN)
3567 : 32427 : if (!s.m_regs.contains (base_reg))
3568 : 125 : purgeable_regions.add (base_reg);
3569 : : }
3570 : : }
3571 : :
3572 : : /* Purge them. */
3573 : 1084480 : for (hash_set<const region *>::iterator iter = purgeable_regions.begin ();
3574 : 2168960 : iter != purgeable_regions.end (); ++iter)
3575 : : {
3576 : 125 : const region *base_reg = *iter;
3577 : 125 : purge_cluster (base_reg);
3578 : : }
3579 : 1084355 : }
3580 : :
3581 : : /* Subroutine for use by exploded_path::feasible_p.
3582 : :
3583 : : We need to deal with state differences between:
3584 : : (a) when the exploded_graph is being initially constructed and
3585 : : (b) when replaying the state changes along a specific path in
3586 : : in exploded_path::feasible_p.
3587 : :
3588 : : In (a), state merging happens, so when exploring a loop
3589 : : for (i = 0; i < 1024; i++)
3590 : : on successive iterations we have i == 0, then i == WIDENING.
3591 : :
3592 : : In (b), no state merging happens, so naively replaying the path
3593 : : that goes twice through the loop then exits it
3594 : : would lead to i == 0, then i == 1, and then a (i >= 1024) eedge
3595 : : that exits the loop, which would be found to be infeasible as i == 1,
3596 : : and the path would be rejected.
3597 : :
3598 : : We need to fix up state during replay. This subroutine is
3599 : : called whenever we enter a supernode that we've already
3600 : : visited along this exploded_path, passing in OTHER_STORE
3601 : : from the destination enode's state.
3602 : :
3603 : : Find bindings to widening values in OTHER_STORE.
3604 : : For all that are found, update the binding in this store to UNKNOWN. */
3605 : :
3606 : : void
3607 : 8754 : store::loop_replay_fixup (const store *other_store,
3608 : : region_model_manager *mgr)
3609 : : {
3610 : 8754 : gcc_assert (other_store);
3611 : 75720 : for (cluster_map_t::iterator iter = other_store->m_cluster_map.begin ();
3612 : 142686 : iter != other_store->m_cluster_map.end (); ++iter)
3613 : : {
3614 : 66966 : const region *base_reg = (*iter).first;
3615 : 66966 : binding_cluster *cluster = (*iter).second;
3616 : 145184 : for (binding_cluster::iterator_t bind_iter = cluster->m_map.begin ();
3617 : 145184 : bind_iter != cluster->m_map.end (); ++bind_iter)
3618 : : {
3619 : 78218 : const binding_key *key = (*bind_iter).m_key;
3620 : 78218 : const svalue *sval = (*bind_iter).m_sval;
3621 : 78218 : if (sval->get_kind () == SK_WIDENING)
3622 : : {
3623 : 1715 : binding_cluster *this_cluster
3624 : 1715 : = get_or_create_cluster (*mgr->get_store_manager (),
3625 : : base_reg);
3626 : 1715 : const svalue *unknown
3627 : 1715 : = mgr->get_or_create_unknown_svalue (sval->get_type ());
3628 : 1715 : this_cluster->bind_key (key, unknown);
3629 : : }
3630 : : }
3631 : : }
3632 : 8754 : }
3633 : :
3634 : : /* Use R to replay the bindings from SUMMARY into this object. */
3635 : :
3636 : : void
3637 : 1528 : store::replay_call_summary (call_summary_replay &r,
3638 : : const store &summary)
3639 : : {
3640 : 1528 : if (summary.m_called_unknown_fn)
3641 : : {
3642 : : /* A call to an external function occurred in the summary.
3643 : : Hence we need to invalidate our knownledge of globals,
3644 : : escaped regions, etc. */
3645 : 87 : on_unknown_fncall (r.get_call_stmt (),
3646 : : r.get_store_manager (),
3647 : 87 : conjured_purge (r.get_caller_model (),
3648 : 87 : r.get_ctxt ()));
3649 : : }
3650 : :
3651 : 1528 : auto_vec<const region *> keys (summary.m_cluster_map.elements ());
3652 : 14776 : for (auto kv : summary.m_cluster_map)
3653 : 13248 : keys.quick_push (kv.first);
3654 : 1528 : keys.qsort (region::cmp_ptr_ptr);
3655 : 17792 : for (auto base_reg : keys)
3656 : 13248 : replay_call_summary_cluster (r, summary, base_reg);
3657 : 1528 : }
3658 : :
3659 : : /* Use R and SUMMARY to replay the bindings in SUMMARY_CLUSTER
3660 : : into this object. */
3661 : :
3662 : : void
3663 : 13248 : store::replay_call_summary_cluster (call_summary_replay &r,
3664 : : const store &summary,
3665 : : const region *summary_base_reg)
3666 : : {
3667 : 13248 : const call_details &cd = r.get_call_details ();
3668 : 13248 : region_model_manager *reg_mgr = r.get_manager ();
3669 : 13248 : store_manager *mgr = reg_mgr->get_store_manager ();
3670 : 13248 : const binding_cluster *summary_cluster
3671 : 13248 : = summary.get_cluster (summary_base_reg);
3672 : :
3673 : : /* Handle "ESCAPED" and "TOUCHED" flags. */
3674 : 13248 : if (summary_cluster->escaped_p () || summary_cluster->touched_p ())
3675 : 8850 : if (const region *caller_reg
3676 : 4425 : = r.convert_region_from_summary (summary_base_reg))
3677 : : {
3678 : 4332 : const region *caller_base_reg = caller_reg->get_base_region ();
3679 : 4332 : if (caller_base_reg->tracked_p ()
3680 : 4332 : && !caller_base_reg->symbolic_for_unknown_ptr_p ())
3681 : : {
3682 : 3364 : binding_cluster *caller_cluster
3683 : 3364 : = get_or_create_cluster (*mgr, caller_base_reg);
3684 : 3364 : if (summary_cluster->escaped_p ())
3685 : 2609 : caller_cluster->mark_as_escaped ();
3686 : 3364 : if (summary_cluster->touched_p ())
3687 : 2060 : caller_cluster->m_touched = true;
3688 : : }
3689 : : }
3690 : :
3691 : 13248 : switch (summary_base_reg->get_kind ())
3692 : : {
3693 : : /* Top-level regions. */
3694 : 0 : case RK_FRAME:
3695 : 0 : case RK_GLOBALS:
3696 : 0 : case RK_CODE:
3697 : 0 : case RK_STACK:
3698 : 0 : case RK_HEAP:
3699 : 0 : case RK_THREAD_LOCAL:
3700 : 0 : case RK_ROOT:
3701 : : /* Child regions. */
3702 : 0 : case RK_FIELD:
3703 : 0 : case RK_ELEMENT:
3704 : 0 : case RK_OFFSET:
3705 : 0 : case RK_SIZED:
3706 : 0 : case RK_CAST:
3707 : 0 : case RK_BIT_RANGE:
3708 : : /* Other regions. */
3709 : 0 : case RK_VAR_ARG:
3710 : 0 : case RK_UNKNOWN:
3711 : : /* These should never be the base region of a binding cluster. */
3712 : 0 : gcc_unreachable ();
3713 : : break;
3714 : :
3715 : : case RK_FUNCTION:
3716 : : case RK_LABEL:
3717 : : case RK_STRING:
3718 : : /* These can be marked as escaping. */
3719 : : break;
3720 : :
3721 : 3043 : case RK_SYMBOLIC:
3722 : 3043 : {
3723 : 3043 : const symbolic_region *summary_symbolic_reg
3724 : 3043 : = as_a <const symbolic_region *> (summary_base_reg);
3725 : 3043 : const svalue *summary_ptr_sval = summary_symbolic_reg->get_pointer ();
3726 : 3043 : const svalue *caller_ptr_sval
3727 : 3043 : = r.convert_svalue_from_summary (summary_ptr_sval);
3728 : 3043 : if (!caller_ptr_sval)
3729 : : return;
3730 : 2560 : const region *caller_dest_reg
3731 : 2560 : = cd.get_model ()->deref_rvalue (caller_ptr_sval,
3732 : : NULL_TREE,
3733 : : cd.get_ctxt ());
3734 : 2560 : const svalue *summary_sval
3735 : 2560 : = summary.get_any_binding (mgr, summary_base_reg);
3736 : 2560 : if (!summary_sval)
3737 : : return;
3738 : 2292 : const svalue *caller_sval
3739 : 2292 : = r.convert_svalue_from_summary (summary_sval);
3740 : 2292 : if (!caller_sval)
3741 : 2 : caller_sval =
3742 : 2 : reg_mgr->get_or_create_unknown_svalue (summary_sval->get_type ());
3743 : 2292 : set_value (mgr, caller_dest_reg,
3744 : : caller_sval, nullptr /* uncertainty_t * */);
3745 : : }
3746 : 2292 : break;
3747 : :
3748 : 10172 : case RK_HEAP_ALLOCATED:
3749 : 10172 : case RK_DECL:
3750 : 10172 : case RK_ERRNO:
3751 : 10172 : case RK_PRIVATE:
3752 : 10172 : {
3753 : 10172 : const region *caller_dest_reg
3754 : 10172 : = r.convert_region_from_summary (summary_base_reg);
3755 : 10172 : if (!caller_dest_reg)
3756 : : return;
3757 : 9887 : const svalue *summary_sval
3758 : 9887 : = summary.get_any_binding (mgr, summary_base_reg);
3759 : 9887 : if (!summary_sval)
3760 : 206 : summary_sval = reg_mgr->get_or_create_compound_svalue
3761 : 206 : (summary_base_reg->get_type (),
3762 : : summary_cluster->get_map ());
3763 : 9887 : const svalue *caller_sval
3764 : 9887 : = r.convert_svalue_from_summary (summary_sval);
3765 : 9887 : if (!caller_sval)
3766 : 2 : caller_sval =
3767 : 2 : reg_mgr->get_or_create_unknown_svalue (summary_sval->get_type ());
3768 : 9887 : set_value (mgr, caller_dest_reg,
3769 : : caller_sval, nullptr /* uncertainty_t * */);
3770 : : }
3771 : 9887 : break;
3772 : :
3773 : : case RK_ALLOCA:
3774 : : /* Ignore bindings of alloca regions in the summary. */
3775 : : break;
3776 : : }
3777 : : }
3778 : :
3779 : : #if CHECKING_P
3780 : :
3781 : : namespace selftest {
3782 : :
3783 : : /* Verify that bit_range::intersects_p works as expected. */
3784 : :
3785 : : static void
3786 : 4 : test_bit_range_intersects_p ()
3787 : : {
3788 : 4 : bit_range b0 (0, 1);
3789 : 4 : bit_range b1 (1, 1);
3790 : 4 : bit_range b2 (2, 1);
3791 : 4 : bit_range b3 (3, 1);
3792 : 4 : bit_range b4 (4, 1);
3793 : 4 : bit_range b5 (5, 1);
3794 : 4 : bit_range b6 (6, 1);
3795 : 4 : bit_range b7 (7, 1);
3796 : 4 : bit_range b1_to_6 (1, 6);
3797 : 4 : bit_range b0_to_7 (0, 8);
3798 : 4 : bit_range b3_to_5 (3, 3);
3799 : 4 : bit_range b6_to_7 (6, 2);
3800 : :
3801 : : /* self-intersection is true. */
3802 : 4 : ASSERT_TRUE (b0.intersects_p (b0));
3803 : 4 : ASSERT_TRUE (b7.intersects_p (b7));
3804 : 4 : ASSERT_TRUE (b1_to_6.intersects_p (b1_to_6));
3805 : 4 : ASSERT_TRUE (b0_to_7.intersects_p (b0_to_7));
3806 : :
3807 : 4 : ASSERT_FALSE (b0.intersects_p (b1));
3808 : 4 : ASSERT_FALSE (b1.intersects_p (b0));
3809 : 4 : ASSERT_FALSE (b0.intersects_p (b7));
3810 : 4 : ASSERT_FALSE (b7.intersects_p (b0));
3811 : :
3812 : 4 : ASSERT_TRUE (b0_to_7.intersects_p (b0));
3813 : 4 : ASSERT_TRUE (b0_to_7.intersects_p (b7));
3814 : 4 : ASSERT_TRUE (b0.intersects_p (b0_to_7));
3815 : 4 : ASSERT_TRUE (b7.intersects_p (b0_to_7));
3816 : :
3817 : 4 : ASSERT_FALSE (b0.intersects_p (b1_to_6));
3818 : 4 : ASSERT_FALSE (b1_to_6.intersects_p (b0));
3819 : 4 : ASSERT_TRUE (b1.intersects_p (b1_to_6));
3820 : 4 : ASSERT_TRUE (b1_to_6.intersects_p (b1));
3821 : 4 : ASSERT_TRUE (b1_to_6.intersects_p (b6));
3822 : 4 : ASSERT_FALSE (b1_to_6.intersects_p (b7));
3823 : :
3824 : 4 : ASSERT_TRUE (b1_to_6.intersects_p (b0_to_7));
3825 : 4 : ASSERT_TRUE (b0_to_7.intersects_p (b1_to_6));
3826 : :
3827 : 4 : ASSERT_FALSE (b3_to_5.intersects_p (b6_to_7));
3828 : 4 : ASSERT_FALSE (b6_to_7.intersects_p (b3_to_5));
3829 : :
3830 : 4 : bit_range r1 (0,0);
3831 : 4 : bit_range r2 (0,0);
3832 : 4 : ASSERT_TRUE (b1_to_6.intersects_p (b0_to_7, &r1, &r2));
3833 : 4 : ASSERT_EQ (r1.get_start_bit_offset (), 0);
3834 : 4 : ASSERT_EQ (r1.m_size_in_bits, 6);
3835 : 4 : ASSERT_EQ (r2.get_start_bit_offset (), 1);
3836 : 4 : ASSERT_EQ (r2.m_size_in_bits, 6);
3837 : :
3838 : 4 : ASSERT_TRUE (b0_to_7.intersects_p (b1_to_6, &r1, &r2));
3839 : 4 : ASSERT_EQ (r1.get_start_bit_offset (), 1);
3840 : 4 : ASSERT_EQ (r1.m_size_in_bits, 6);
3841 : 4 : ASSERT_EQ (r2.get_start_bit_offset (), 0);
3842 : 4 : ASSERT_EQ (r2.m_size_in_bits, 6);
3843 : 4 : }
3844 : :
3845 : : /* Implementation detail of ASSERT_BIT_RANGE_FROM_MASK_EQ. */
3846 : :
3847 : : static void
3848 : 76 : assert_bit_range_from_mask_eq (const location &loc,
3849 : : unsigned HOST_WIDE_INT mask,
3850 : : const bit_range &expected)
3851 : : {
3852 : 76 : bit_range actual (0, 0);
3853 : 76 : bool ok = bit_range::from_mask (mask, &actual);
3854 : 76 : ASSERT_TRUE_AT (loc, ok);
3855 : 76 : ASSERT_EQ_AT (loc, actual, expected);
3856 : 76 : }
3857 : :
3858 : : /* Assert that bit_range::from_mask (MASK) returns true, and writes
3859 : : out EXPECTED_BIT_RANGE. */
3860 : :
3861 : : #define ASSERT_BIT_RANGE_FROM_MASK_EQ(MASK, EXPECTED_BIT_RANGE) \
3862 : : SELFTEST_BEGIN_STMT \
3863 : : assert_bit_range_from_mask_eq (SELFTEST_LOCATION, MASK, \
3864 : : EXPECTED_BIT_RANGE); \
3865 : : SELFTEST_END_STMT
3866 : :
3867 : : /* Implementation detail of ASSERT_NO_BIT_RANGE_FROM_MASK. */
3868 : :
3869 : : static void
3870 : 12 : assert_no_bit_range_from_mask_eq (const location &loc,
3871 : : unsigned HOST_WIDE_INT mask)
3872 : : {
3873 : 12 : bit_range actual (0, 0);
3874 : 12 : bool ok = bit_range::from_mask (mask, &actual);
3875 : 12 : ASSERT_FALSE_AT (loc, ok);
3876 : 12 : }
3877 : :
3878 : : /* Assert that bit_range::from_mask (MASK) returns false. */
3879 : :
3880 : : #define ASSERT_NO_BIT_RANGE_FROM_MASK(MASK) \
3881 : : SELFTEST_BEGIN_STMT \
3882 : : assert_no_bit_range_from_mask_eq (SELFTEST_LOCATION, MASK); \
3883 : : SELFTEST_END_STMT
3884 : :
3885 : : /* Verify that bit_range::from_mask works as expected. */
3886 : :
3887 : : static void
3888 : 4 : test_bit_range_from_mask ()
3889 : : {
3890 : : /* Should fail on zero. */
3891 : 4 : ASSERT_NO_BIT_RANGE_FROM_MASK (0);
3892 : :
3893 : : /* Verify 1-bit masks. */
3894 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (1, bit_range (0, 1));
3895 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (2, bit_range (1, 1));
3896 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (4, bit_range (2, 1));
3897 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (8, bit_range (3, 1));
3898 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (16, bit_range (4, 1));
3899 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (32, bit_range (5, 1));
3900 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (64, bit_range (6, 1));
3901 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (128, bit_range (7, 1));
3902 : :
3903 : : /* Verify N-bit masks starting at bit 0. */
3904 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (3, bit_range (0, 2));
3905 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (7, bit_range (0, 3));
3906 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (15, bit_range (0, 4));
3907 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (31, bit_range (0, 5));
3908 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (63, bit_range (0, 6));
3909 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (127, bit_range (0, 7));
3910 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (255, bit_range (0, 8));
3911 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (0xffff, bit_range (0, 16));
3912 : :
3913 : : /* Various other tests. */
3914 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (0x30, bit_range (4, 2));
3915 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (0x700, bit_range (8, 3));
3916 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (0x600, bit_range (9, 2));
3917 : :
3918 : : /* Multiple ranges of set bits should fail. */
3919 : 4 : ASSERT_NO_BIT_RANGE_FROM_MASK (0x101);
3920 : 4 : ASSERT_NO_BIT_RANGE_FROM_MASK (0xf0f0f0f0);
3921 : 4 : }
3922 : :
3923 : : /* Implementation detail of ASSERT_OVERLAP. */
3924 : :
3925 : : static void
3926 : 56 : assert_overlap (const location &loc,
3927 : : const concrete_binding *b1,
3928 : : const concrete_binding *b2)
3929 : : {
3930 : 56 : ASSERT_TRUE_AT (loc, b1->overlaps_p (*b2));
3931 : 56 : ASSERT_TRUE_AT (loc, b2->overlaps_p (*b1));
3932 : 56 : }
3933 : :
3934 : : /* Implementation detail of ASSERT_DISJOINT. */
3935 : :
3936 : : static void
3937 : 20 : assert_disjoint (const location &loc,
3938 : : const concrete_binding *b1,
3939 : : const concrete_binding *b2)
3940 : : {
3941 : 20 : ASSERT_FALSE_AT (loc, b1->overlaps_p (*b2));
3942 : 20 : ASSERT_FALSE_AT (loc, b2->overlaps_p (*b1));
3943 : 20 : }
3944 : :
3945 : : /* Assert that B1 and B2 overlap, checking both ways. */
3946 : :
3947 : : #define ASSERT_OVERLAP(B1, B2) \
3948 : : SELFTEST_BEGIN_STMT \
3949 : : assert_overlap (SELFTEST_LOCATION, B1, B2); \
3950 : : SELFTEST_END_STMT
3951 : :
3952 : : /* Assert that B1 and B2 do not overlap, checking both ways. */
3953 : :
3954 : : #define ASSERT_DISJOINT(B1, B2) \
3955 : : SELFTEST_BEGIN_STMT \
3956 : : assert_disjoint (SELFTEST_LOCATION, B1, B2); \
3957 : : SELFTEST_END_STMT
3958 : :
3959 : : /* Verify that concrete_binding::overlaps_p works as expected. */
3960 : :
3961 : : static void
3962 : 4 : test_binding_key_overlap ()
3963 : : {
3964 : 4 : store_manager mgr (nullptr);
3965 : :
3966 : : /* Various 8-bit bindings. */
3967 : 4 : const concrete_binding *cb_0_7 = mgr.get_concrete_binding (0, 8);
3968 : 4 : const concrete_binding *cb_8_15 = mgr.get_concrete_binding (8, 8);
3969 : 4 : const concrete_binding *cb_16_23 = mgr.get_concrete_binding (16, 8);
3970 : 4 : const concrete_binding *cb_24_31 = mgr.get_concrete_binding (24, 8);
3971 : :
3972 : : /* 16-bit bindings. */
3973 : 4 : const concrete_binding *cb_0_15 = mgr.get_concrete_binding (0, 16);
3974 : 4 : const concrete_binding *cb_8_23 = mgr.get_concrete_binding (8, 16);
3975 : 4 : const concrete_binding *cb_16_31 = mgr.get_concrete_binding (16, 16);
3976 : :
3977 : : /* 32-bit binding. */
3978 : 4 : const concrete_binding *cb_0_31 = mgr.get_concrete_binding (0, 32);
3979 : :
3980 : : /* Everything should self-overlap. */
3981 : 4 : ASSERT_OVERLAP (cb_0_7, cb_0_7);
3982 : 4 : ASSERT_OVERLAP (cb_8_15, cb_8_15);
3983 : 4 : ASSERT_OVERLAP (cb_16_23, cb_16_23);
3984 : 4 : ASSERT_OVERLAP (cb_24_31, cb_24_31);
3985 : 4 : ASSERT_OVERLAP (cb_0_15, cb_0_15);
3986 : 4 : ASSERT_OVERLAP (cb_8_23, cb_8_23);
3987 : 4 : ASSERT_OVERLAP (cb_16_31, cb_16_31);
3988 : 4 : ASSERT_OVERLAP (cb_0_31, cb_0_31);
3989 : :
3990 : : /* Verify the 8-bit bindings that don't overlap each other. */
3991 : 4 : ASSERT_DISJOINT (cb_0_7, cb_8_15);
3992 : 4 : ASSERT_DISJOINT (cb_8_15, cb_16_23);
3993 : :
3994 : : /* Check for overlap of differently-sized bindings. */
3995 : 4 : ASSERT_OVERLAP (cb_0_7, cb_0_31);
3996 : : /* ...and with differing start points. */
3997 : 4 : ASSERT_OVERLAP (cb_8_15, cb_0_31);
3998 : 4 : ASSERT_DISJOINT (cb_8_15, cb_16_31);
3999 : 4 : ASSERT_OVERLAP (cb_16_23, cb_0_31);
4000 : 4 : ASSERT_OVERLAP (cb_16_31, cb_0_31);
4001 : :
4002 : 4 : ASSERT_DISJOINT (cb_0_7, cb_8_23);
4003 : 4 : ASSERT_OVERLAP (cb_8_23, cb_16_23);
4004 : 4 : ASSERT_OVERLAP (cb_8_23, cb_16_31);
4005 : 4 : ASSERT_DISJOINT (cb_8_23, cb_24_31);
4006 : 4 : }
4007 : :
4008 : : static void
4009 : 4 : test_binding_map_ops ()
4010 : : {
4011 : 4 : region_model_manager region_mgr;
4012 : 4 : store_manager store_mgr (®ion_mgr);
4013 : :
4014 : : /* Assignment of empty. */
4015 : 4 : {
4016 : 4 : binding_map src (store_mgr);
4017 : 4 : binding_map dst (store_mgr);
4018 : 4 : dst = src;
4019 : :
4020 : 4 : ASSERT_EQ (src, dst);
4021 : 4 : }
4022 : 4 : }
4023 : :
4024 : : /* Run all of the selftests within this file. */
4025 : :
4026 : : void
4027 : 4 : analyzer_store_cc_tests ()
4028 : : {
4029 : 4 : test_bit_range_intersects_p ();
4030 : 4 : test_bit_range_from_mask ();
4031 : 4 : test_binding_key_overlap ();
4032 : 4 : test_binding_map_ops ();
4033 : 4 : }
4034 : :
4035 : : } // namespace selftest
4036 : :
4037 : : #endif /* CHECKING_P */
4038 : :
4039 : : } // namespace ana
4040 : :
4041 : : #endif /* #if ENABLE_ANALYZER */
|
