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