Branch data Line data Source code
1 : : /* Classes for modeling the state of memory.
2 : : Copyright (C) 2020-2024 Free Software Foundation, Inc.
3 : : Contributed by David Malcolm <dmalcolm@redhat.com>.
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify it
8 : : under the terms of the GNU General Public License as published by
9 : : the Free Software Foundation; either version 3, or (at your option)
10 : : any later version.
11 : :
12 : : GCC is distributed in the hope that it will be useful, but
13 : : WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : : General Public License for more details.
16 : :
17 : : You should have received a copy of the GNU General Public License
18 : : along with GCC; see the file COPYING3. If not see
19 : : <http://www.gnu.org/licenses/>. */
20 : :
21 : : #include "config.h"
22 : : #define INCLUDE_VECTOR
23 : : #include "system.h"
24 : : #include "coretypes.h"
25 : : #include "tree.h"
26 : : #include "function.h"
27 : : #include "basic-block.h"
28 : : #include "gimple.h"
29 : : #include "gimple-iterator.h"
30 : : #include "diagnostic-core.h"
31 : : #include "graphviz.h"
32 : : #include "options.h"
33 : : #include "cgraph.h"
34 : : #include "tree-dfa.h"
35 : : #include "stringpool.h"
36 : : #include "convert.h"
37 : : #include "target.h"
38 : : #include "fold-const.h"
39 : : #include "tree-pretty-print.h"
40 : : #include "diagnostic-color.h"
41 : : #include "bitmap.h"
42 : : #include "selftest.h"
43 : : #include "analyzer/analyzer.h"
44 : : #include "analyzer/analyzer-logging.h"
45 : : #include "ordered-hash-map.h"
46 : : #include "options.h"
47 : : #include "cfg.h"
48 : : #include "analyzer/supergraph.h"
49 : : #include "sbitmap.h"
50 : : #include "analyzer/call-string.h"
51 : : #include "analyzer/program-point.h"
52 : : #include "analyzer/store.h"
53 : : #include "analyzer/region-model.h"
54 : : #include "analyzer/call-summary.h"
55 : : #include "analyzer/analyzer-selftests.h"
56 : : #include "stor-layout.h"
57 : : #include "text-art/tree-widget.h"
58 : : #include "make-unique.h"
59 : :
60 : : #if ENABLE_ANALYZER
61 : :
62 : : namespace ana {
63 : :
64 : : /* Dump SVALS to PP, sorting them to ensure determinism. */
65 : :
66 : : static void
67 : 496 : dump_svalue_set (const hash_set <const svalue *> &svals,
68 : : pretty_printer *pp, bool simple)
69 : : {
70 : 496 : auto_vec <const svalue *> v;
71 : 496 : for (hash_set<const svalue *>::iterator iter = svals.begin ();
72 : 560 : iter != svals.end (); ++iter)
73 : : {
74 : 32 : v.safe_push (*iter);
75 : : }
76 : 496 : v.qsort (svalue::cmp_ptr_ptr);
77 : :
78 : 496 : pp_character (pp, '{');
79 : 496 : const svalue *sval;
80 : 496 : unsigned i;
81 : 1024 : FOR_EACH_VEC_ELT (v, i, sval)
82 : : {
83 : 32 : if (i > 0)
84 : 19 : pp_string (pp, ", ");
85 : 32 : sval->dump_to_pp (pp, simple);
86 : : }
87 : 496 : pp_character (pp, '}');
88 : 496 : }
89 : :
90 : : /* class uncertainty_t. */
91 : :
92 : : /* Dump this object to PP. */
93 : :
94 : : void
95 : 248 : uncertainty_t::dump_to_pp (pretty_printer *pp, bool simple) const
96 : : {
97 : 248 : pp_string (pp, "{m_maybe_bound_svals: ");
98 : 248 : dump_svalue_set (m_maybe_bound_svals, pp, simple);
99 : :
100 : 248 : pp_string (pp, ", m_mutable_at_unknown_call_svals: ");
101 : 248 : dump_svalue_set (m_mutable_at_unknown_call_svals, pp, simple);
102 : 248 : pp_string (pp, "}");
103 : 248 : }
104 : :
105 : : /* Dump this object to stderr. */
106 : :
107 : : DEBUG_FUNCTION void
108 : 0 : uncertainty_t::dump (bool simple) const
109 : : {
110 : 0 : tree_dump_pretty_printer pp (stderr);
111 : 0 : dump_to_pp (&pp, simple);
112 : 0 : pp_newline (&pp);
113 : 0 : }
114 : :
115 : : /* class binding_key. */
116 : :
117 : : const binding_key *
118 : 3457924 : binding_key::make (store_manager *mgr, const region *r)
119 : : {
120 : 3457924 : region_offset offset = r->get_offset (mgr->get_svalue_manager ());
121 : 3457924 : if (offset.symbolic_p ())
122 : 36588 : return mgr->get_symbolic_binding (r);
123 : : else
124 : : {
125 : 3421336 : bit_size_t bit_size;
126 : 3421336 : if (r->get_bit_size (&bit_size))
127 : : {
128 : : /* Must be non-empty. */
129 : 2169283 : gcc_assert (bit_size > 0);
130 : 2169283 : return mgr->get_concrete_binding (offset.get_bit_offset (),
131 : 2169283 : bit_size);
132 : : }
133 : : else
134 : 1252053 : return mgr->get_symbolic_binding (r);
135 : : }
136 : : }
137 : :
138 : : /* Dump this binding_key to stderr. */
139 : :
140 : : DEBUG_FUNCTION void
141 : 0 : binding_key::dump (bool simple) const
142 : : {
143 : 0 : tree_dump_pretty_printer pp (stderr);
144 : 0 : dump_to_pp (&pp, simple);
145 : 0 : pp_newline (&pp);
146 : 0 : }
147 : :
148 : : /* Get a description of this binding_key. */
149 : :
150 : : label_text
151 : 0 : binding_key::get_desc (bool simple) const
152 : : {
153 : 0 : pretty_printer pp;
154 : 0 : pp_format_decoder (&pp) = default_tree_printer;
155 : 0 : dump_to_pp (&pp, simple);
156 : 0 : return label_text::take (xstrdup (pp_formatted_text (&pp)));
157 : 0 : }
158 : :
159 : : /* qsort callback. */
160 : :
161 : : int
162 : 4524 : binding_key::cmp_ptrs (const void *p1, const void *p2)
163 : : {
164 : 4524 : const binding_key * const *pk1 = (const binding_key * const *)p1;
165 : 4524 : const binding_key * const *pk2 = (const binding_key * const *)p2;
166 : 4524 : return cmp (*pk1, *pk2);
167 : : }
168 : :
169 : : /* Comparator for binding_keys. */
170 : :
171 : : int
172 : 4524 : binding_key::cmp (const binding_key *k1, const binding_key *k2)
173 : : {
174 : 4524 : int concrete1 = k1->concrete_p ();
175 : 4524 : int concrete2 = k2->concrete_p ();
176 : 4524 : if (int concrete_cmp = concrete1 - concrete2)
177 : : return concrete_cmp;
178 : 4524 : if (concrete1)
179 : : {
180 : 4524 : const concrete_binding *b1 = (const concrete_binding *)k1;
181 : 4524 : const concrete_binding *b2 = (const concrete_binding *)k2;
182 : 4524 : if (int start_cmp = wi::cmp (b1->get_start_bit_offset (),
183 : 4524 : b2->get_start_bit_offset (),
184 : : SIGNED))
185 : : return start_cmp;
186 : 1536 : return wi::cmp (b1->get_next_bit_offset (), b2->get_next_bit_offset (),
187 : : SIGNED);
188 : : }
189 : : else
190 : : {
191 : 0 : const symbolic_binding *s1 = (const symbolic_binding *)k1;
192 : 0 : const symbolic_binding *s2 = (const symbolic_binding *)k2;
193 : 0 : if (s1 > s2)
194 : : return 1;
195 : 0 : if (s1 < s2)
196 : : return -1;
197 : 0 : return 0;
198 : : }
199 : : }
200 : :
201 : : /* struct bit_range. */
202 : :
203 : : void
204 : 2313 : bit_range::dump_to_pp (pretty_printer *pp) const
205 : : {
206 : 2313 : byte_range bytes (0, 0);
207 : 2313 : if (as_byte_range (&bytes))
208 : 2313 : bytes.dump_to_pp (pp);
209 : : else
210 : : {
211 : 0 : pp_string (pp, "start: ");
212 : 0 : pp_wide_int (pp, m_start_bit_offset, SIGNED);
213 : 0 : pp_string (pp, ", size: ");
214 : 0 : pp_wide_int (pp, m_size_in_bits, SIGNED);
215 : 0 : pp_string (pp, ", next: ");
216 : 0 : pp_wide_int (pp, get_next_bit_offset (), SIGNED);
217 : : }
218 : 2313 : }
219 : :
220 : : /* Dump this object to stderr. */
221 : :
222 : : DEBUG_FUNCTION void
223 : 0 : bit_range::dump () const
224 : : {
225 : 0 : tree_dump_pretty_printer pp (stderr);
226 : 0 : dump_to_pp (&pp);
227 : 0 : pp_newline (&pp);
228 : 0 : }
229 : :
230 : : /* Generate a JSON value for this bit_range.
231 : : This is intended for debugging the analyzer rather
232 : : than serialization. */
233 : :
234 : : std::unique_ptr<json::object>
235 : 4 : bit_range::to_json () const
236 : : {
237 : 4 : auto obj = ::make_unique<json::object> ();
238 : 4 : obj->set ("start_bit_offset",
239 : 4 : bit_offset_to_json (m_start_bit_offset));
240 : 4 : obj->set ("size_in_bits",
241 : 4 : bit_offset_to_json (m_size_in_bits));
242 : 4 : return obj;
243 : : }
244 : :
245 : : /* If OTHER is a subset of this, return true and, if OUT is
246 : : non-null, write to *OUT the relative range of OTHER within this.
247 : : Otherwise return false. */
248 : :
249 : : bool
250 : 40080 : bit_range::contains_p (const bit_range &other, bit_range *out) const
251 : : {
252 : 40080 : if (contains_p (other.get_start_bit_offset ())
253 : 40080 : && contains_p (other.get_last_bit_offset ()))
254 : : {
255 : 27038 : if (out)
256 : : {
257 : 27038 : out->m_start_bit_offset = other.m_start_bit_offset - m_start_bit_offset;
258 : 27038 : out->m_size_in_bits = other.m_size_in_bits;
259 : : }
260 : 27038 : return true;
261 : : }
262 : : else
263 : 13042 : return false;
264 : : }
265 : :
266 : : /* If OTHER intersects this, return true and write
267 : : the relative range of OTHER within THIS to *OUT_THIS,
268 : : and the relative range of THIS within OTHER to *OUT_OTHER.
269 : : Otherwise return false. */
270 : :
271 : : bool
272 : 84 : bit_range::intersects_p (const bit_range &other,
273 : : bit_range *out_this,
274 : : bit_range *out_other) const
275 : : {
276 : 84 : if (get_start_bit_offset () < other.get_next_bit_offset ()
277 : 168 : && other.get_start_bit_offset () < get_next_bit_offset ())
278 : : {
279 : 84 : bit_offset_t overlap_start
280 : 84 : = MAX (get_start_bit_offset (),
281 : : other.get_start_bit_offset ());
282 : 84 : bit_offset_t overlap_next
283 : 84 : = MIN (get_next_bit_offset (),
284 : : other.get_next_bit_offset ());
285 : 84 : if (overlap_next <= overlap_start)
286 : : /* If this has happened, some kind of overflow has happened in
287 : : our arithmetic. For now, reject such cases. */
288 : : return false;
289 : 84 : bit_range abs_overlap_bits (overlap_start, overlap_next - overlap_start);
290 : 84 : *out_this = abs_overlap_bits - get_start_bit_offset ();
291 : 84 : *out_other = abs_overlap_bits - other.get_start_bit_offset ();
292 : 84 : return true;
293 : : }
294 : : else
295 : 0 : return false;
296 : : }
297 : :
298 : : /* Return true if THIS and OTHER intersect and write the number
299 : : of bits both buffers overlap to *OUT_NUM_OVERLAP_BITS.
300 : :
301 : : Otherwise return false. */
302 : :
303 : : bool
304 : 0 : bit_range::intersects_p (const bit_range &other,
305 : : bit_size_t *out_num_overlap_bits) const
306 : : {
307 : 0 : if (get_start_bit_offset () < other.get_next_bit_offset ()
308 : 0 : && other.get_start_bit_offset () < get_next_bit_offset ())
309 : : {
310 : 0 : bit_offset_t overlap_start = MAX (get_start_bit_offset (),
311 : : other.get_start_bit_offset ());
312 : 0 : bit_offset_t overlap_next = MIN (get_next_bit_offset (),
313 : : other.get_next_bit_offset ());
314 : 0 : if (overlap_next <= overlap_start)
315 : : /* If this has happened, some kind of overflow has happened in
316 : : our arithmetic. For now, reject such cases. */
317 : : return false;
318 : 0 : *out_num_overlap_bits = overlap_next - overlap_start;
319 : 0 : return true;
320 : : }
321 : : else
322 : 0 : return false;
323 : : }
324 : :
325 : : /* Return true if THIS exceeds OTHER and write the overhanging
326 : : bit range to OUT_OVERHANGING_BIT_RANGE. */
327 : :
328 : : bool
329 : 631753 : bit_range::exceeds_p (const bit_range &other,
330 : : bit_range *out_overhanging_bit_range) const
331 : : {
332 : 631753 : gcc_assert (!empty_p ());
333 : :
334 : 631753 : if (other.get_next_bit_offset () < get_next_bit_offset ())
335 : : {
336 : : /* THIS definitely exceeds OTHER. */
337 : 456 : bit_offset_t start = MAX (get_start_bit_offset (),
338 : : other.get_next_bit_offset ());
339 : 456 : bit_offset_t size = get_next_bit_offset () - start;
340 : 456 : if (size <= 0)
341 : : /* If this has happened, some kind of overflow has happened in
342 : : our arithmetic. For now, reject such cases. */
343 : : return false;
344 : 436 : out_overhanging_bit_range->m_start_bit_offset = start;
345 : 436 : out_overhanging_bit_range->m_size_in_bits = size;
346 : 436 : return true;
347 : : }
348 : : else
349 : : return false;
350 : : }
351 : :
352 : : /* Return true if THIS falls short of OFFSET and write the
353 : : bit range fallen short to OUT_FALL_SHORT_BITS. */
354 : :
355 : : bool
356 : 634728 : bit_range::falls_short_of_p (bit_offset_t offset,
357 : : bit_range *out_fall_short_bits) const
358 : : {
359 : 634728 : gcc_assert (!empty_p ());
360 : :
361 : 634728 : if (get_start_bit_offset () < offset)
362 : : {
363 : : /* THIS falls short of OFFSET. */
364 : 184 : bit_offset_t start = get_start_bit_offset ();
365 : 184 : bit_offset_t size = MIN (offset, get_next_bit_offset ()) - start;
366 : 184 : if (size <= 0)
367 : : /* If this has happened, some kind of overflow has happened in
368 : : our arithmetic. For now, reject such cases. */
369 : : return false;
370 : 164 : out_fall_short_bits->m_start_bit_offset = start;
371 : 164 : out_fall_short_bits->m_size_in_bits = size;
372 : 164 : return true;
373 : : }
374 : : else
375 : : return false;
376 : : }
377 : :
378 : : int
379 : 323 : bit_range::cmp (const bit_range &br1, const bit_range &br2)
380 : : {
381 : 323 : if (int start_cmp = wi::cmps (br1.m_start_bit_offset,
382 : 323 : br2.m_start_bit_offset))
383 : : return start_cmp;
384 : :
385 : 12 : return wi::cmpu (br1.m_size_in_bits, br2.m_size_in_bits);
386 : : }
387 : :
388 : : /* Offset this range by OFFSET. */
389 : :
390 : : bit_range
391 : 168 : bit_range::operator- (bit_offset_t offset) const
392 : : {
393 : 168 : return bit_range (m_start_bit_offset - offset, m_size_in_bits);
394 : : }
395 : :
396 : : /* If MASK is a contiguous range of set bits, write them
397 : : to *OUT and return true.
398 : : Otherwise return false. */
399 : :
400 : : bool
401 : 144 : bit_range::from_mask (unsigned HOST_WIDE_INT mask, bit_range *out)
402 : : {
403 : 144 : unsigned iter_bit_idx = 0;
404 : 144 : unsigned HOST_WIDE_INT iter_bit_mask = 1;
405 : :
406 : : /* Find the first contiguous run of set bits in MASK. */
407 : :
408 : : /* Find first set bit in MASK. */
409 : 780 : while (iter_bit_idx < HOST_BITS_PER_WIDE_INT)
410 : : {
411 : 776 : if (mask & iter_bit_mask)
412 : : break;
413 : 636 : iter_bit_idx++;
414 : 636 : iter_bit_mask <<= 1;
415 : : }
416 : 144 : if (iter_bit_idx == HOST_BITS_PER_WIDE_INT)
417 : : /* MASK is zero. */
418 : : return false;
419 : :
420 : 140 : unsigned first_set_iter_bit_idx = iter_bit_idx;
421 : 140 : unsigned num_set_bits = 1;
422 : 140 : iter_bit_idx++;
423 : 140 : iter_bit_mask <<= 1;
424 : :
425 : : /* Find next unset bit in MASK. */
426 : 396 : while (iter_bit_idx < HOST_BITS_PER_WIDE_INT)
427 : : {
428 : 396 : if (!(mask & iter_bit_mask))
429 : : break;
430 : 256 : num_set_bits++;
431 : 256 : iter_bit_idx++;
432 : 256 : iter_bit_mask <<= 1;
433 : : }
434 : 140 : if (iter_bit_idx == HOST_BITS_PER_WIDE_INT)
435 : : {
436 : 0 : *out = bit_range (first_set_iter_bit_idx, num_set_bits);
437 : 0 : return true;
438 : : }
439 : :
440 : : /* We now have the first contiguous run of set bits in MASK.
441 : : Fail if any other bits are set. */
442 : 7892 : while (iter_bit_idx < HOST_BITS_PER_WIDE_INT)
443 : : {
444 : 7760 : if (mask & iter_bit_mask)
445 : : return false;
446 : 7752 : iter_bit_idx++;
447 : 7752 : iter_bit_mask <<= 1;
448 : : }
449 : :
450 : 132 : *out = bit_range (first_set_iter_bit_idx, num_set_bits);
451 : 132 : return true;
452 : : }
453 : :
454 : : /* Attempt to convert this bit_range to a byte_range.
455 : : Return true if it is possible, writing the result to *OUT.
456 : : Otherwise return false. */
457 : :
458 : : bool
459 : 7584 : bit_range::as_byte_range (byte_range *out) const
460 : : {
461 : 7584 : if (m_start_bit_offset % BITS_PER_UNIT == 0
462 : 7584 : && m_size_in_bits % BITS_PER_UNIT == 0)
463 : : {
464 : 7565 : out->m_start_byte_offset = m_start_bit_offset / BITS_PER_UNIT;
465 : 7565 : out->m_size_in_bytes = m_size_in_bits / BITS_PER_UNIT;
466 : 7565 : return true;
467 : : }
468 : : return false;
469 : : }
470 : :
471 : : /* Dump this object to PP. */
472 : :
473 : : void
474 : 2313 : byte_range::dump_to_pp (pretty_printer *pp) const
475 : : {
476 : 2313 : if (m_size_in_bytes == 0)
477 : : {
478 : 0 : pp_string (pp, "empty");
479 : : }
480 : 2313 : else if (m_size_in_bytes == 1)
481 : : {
482 : 1595 : pp_string (pp, "byte ");
483 : 1595 : pp_wide_int (pp, m_start_byte_offset, SIGNED);
484 : : }
485 : : else
486 : : {
487 : 718 : pp_string (pp, "bytes ");
488 : 718 : pp_wide_int (pp, m_start_byte_offset, SIGNED);
489 : 718 : pp_string (pp, "-");
490 : 718 : pp_wide_int (pp, get_last_byte_offset (), SIGNED);
491 : : }
492 : 2313 : }
493 : :
494 : : /* Dump this object to stderr. */
495 : :
496 : : DEBUG_FUNCTION void
497 : 0 : byte_range::dump () const
498 : : {
499 : 0 : tree_dump_pretty_printer pp (stderr);
500 : 0 : dump_to_pp (&pp);
501 : 0 : pp_newline (&pp);
502 : 0 : }
503 : :
504 : : /* Generate a JSON value for this byte_range.
505 : : This is intended for debugging the analyzer rather
506 : : than serialization. */
507 : :
508 : : std::unique_ptr<json::object>
509 : 4 : byte_range::to_json () const
510 : : {
511 : 4 : auto obj = ::make_unique<json::object> ();
512 : 4 : obj->set ("start_byte_offset",
513 : 4 : byte_offset_to_json (m_start_byte_offset));
514 : 4 : obj->set ("size_in_bytes",
515 : 4 : byte_offset_to_json (m_size_in_bytes));
516 : 4 : return obj;
517 : : }
518 : :
519 : : /* If OTHER is a subset of this, return true and write
520 : : to *OUT the relative range of OTHER within this.
521 : : Otherwise return false. */
522 : :
523 : : bool
524 : 632 : byte_range::contains_p (const byte_range &other, byte_range *out) const
525 : : {
526 : 632 : if (contains_p (other.get_start_byte_offset ())
527 : 632 : && contains_p (other.get_last_byte_offset ()))
528 : : {
529 : 322 : out->m_start_byte_offset = other.m_start_byte_offset - m_start_byte_offset;
530 : 322 : out->m_size_in_bytes = other.m_size_in_bytes;
531 : 322 : return true;
532 : : }
533 : : else
534 : 310 : return false;
535 : : }
536 : :
537 : : /* qsort comparator for byte ranges. */
538 : :
539 : : int
540 : 571 : byte_range::cmp (const byte_range &br1, const byte_range &br2)
541 : : {
542 : : /* Order first by offset. */
543 : 571 : if (int start_cmp = wi::cmps (br1.m_start_byte_offset,
544 : 571 : br2.m_start_byte_offset))
545 : : return start_cmp;
546 : :
547 : : /* ...then by size. */
548 : 0 : return wi::cmpu (br1.m_size_in_bytes, br2.m_size_in_bytes);
549 : : }
550 : :
551 : : /* class concrete_binding : public binding_key. */
552 : :
553 : : /* Implementation of binding_key::dump_to_pp vfunc for concrete_binding. */
554 : :
555 : : void
556 : 1648 : concrete_binding::dump_to_pp (pretty_printer *pp, bool) const
557 : : {
558 : 1648 : m_bit_range.dump_to_pp (pp);
559 : 1648 : }
560 : :
561 : : /* Return true if this binding overlaps with OTHER. */
562 : :
563 : : bool
564 : 105686 : concrete_binding::overlaps_p (const concrete_binding &other) const
565 : : {
566 : 105686 : if (get_start_bit_offset () < other.get_next_bit_offset ()
567 : 105686 : && get_next_bit_offset () > other.get_start_bit_offset ())
568 : 65374 : return true;
569 : : return false;
570 : : }
571 : :
572 : : /* If this is expressible as a concrete byte range, return true
573 : : and write it to *OUT. Otherwise return false. */
574 : :
575 : : bool
576 : 683 : concrete_binding::get_byte_range (byte_range *out) const
577 : : {
578 : 683 : return m_bit_range.as_byte_range (out);
579 : : }
580 : :
581 : : /* Comparator for use by vec<const concrete_binding *>::qsort. */
582 : :
583 : : int
584 : 48 : concrete_binding::cmp_ptr_ptr (const void *p1, const void *p2)
585 : : {
586 : 48 : const concrete_binding *b1 = *(const concrete_binding * const *)p1;
587 : 48 : const concrete_binding *b2 = *(const concrete_binding * const *)p2;
588 : :
589 : 48 : return bit_range::cmp (b1->m_bit_range, b2->m_bit_range);
590 : : }
591 : :
592 : : /* class symbolic_binding : public binding_key. */
593 : :
594 : : void
595 : 2 : symbolic_binding::dump_to_pp (pretty_printer *pp, bool simple) const
596 : : {
597 : : //binding_key::dump_to_pp (pp, simple);
598 : 2 : pp_string (pp, "region: ");
599 : 2 : m_region->dump_to_pp (pp, simple);
600 : 2 : }
601 : :
602 : : /* Comparator for use by vec<const symbolic_binding *>::qsort. */
603 : :
604 : : int
605 : 4 : symbolic_binding::cmp_ptr_ptr (const void *p1, const void *p2)
606 : : {
607 : 4 : const symbolic_binding *b1 = *(const symbolic_binding * const *)p1;
608 : 4 : const symbolic_binding *b2 = *(const symbolic_binding * const *)p2;
609 : :
610 : 4 : return region::cmp_ids (b1->get_region (), b2->get_region ());
611 : : }
612 : :
613 : : /* The store is oblivious to the types of the svalues bound within
614 : : it: any type can get bound at any location.
615 : : Simplify any casts before binding.
616 : :
617 : : For example, if we have:
618 : : struct big { int ia[1024]; };
619 : : struct big src, dst;
620 : : memcpy (&dst, &src, sizeof (struct big));
621 : : this reaches us in gimple form as:
622 : : MEM <unsigned char[4096]> [(char * {ref-all})&dst]
623 : : = MEM <unsigned char[4096]> [(char * {ref-all})&src];
624 : : Using cast_region when handling the MEM_REF would give us:
625 : : INIT_VAL(CAST_REG(unsigned char[4096], src))
626 : : as rhs_sval, but we can fold that into a cast svalue:
627 : : CAST(unsigned char[4096], INIT_VAL(src))
628 : : We can discard that cast from the svalue when binding it in
629 : : the store for "dst", and simply store:
630 : : cluster for: dst
631 : : key: {kind: direct, start: 0, size: 32768, next: 32768}
632 : : value: ‘struct big’ {INIT_VAL(src)}. */
633 : :
634 : : static const svalue *
635 : 382959 : simplify_for_binding (const svalue *sval)
636 : : {
637 : 382959 : if (const svalue *cast_sval = sval->maybe_undo_cast ())
638 : 0 : sval = cast_sval;
639 : 61002 : return sval;
640 : : }
641 : :
642 : : /* class binding_map. */
643 : :
644 : : /* binding_map's copy ctor. */
645 : :
646 : 23860682 : binding_map::binding_map (const binding_map &other)
647 : 23860682 : : m_map (other.m_map)
648 : : {
649 : 23860682 : }
650 : :
651 : : /* binding_map's assignment operator. */
652 : :
653 : : binding_map&
654 : 0 : binding_map::operator=(const binding_map &other)
655 : : {
656 : : /* For now, assume we only ever copy to an empty cluster. */
657 : 0 : gcc_assert (m_map.elements () == 0);
658 : 0 : for (map_t::iterator iter = other.m_map.begin (); iter != other.m_map.end ();
659 : 0 : ++iter)
660 : : {
661 : 0 : const binding_key *key = (*iter).first;
662 : 0 : const svalue *sval = (*iter).second;
663 : 0 : m_map.put (key, sval);
664 : : }
665 : 0 : return *this;
666 : : }
667 : :
668 : : /* binding_map's equality operator. */
669 : :
670 : : bool
671 : 1967614 : binding_map::operator== (const binding_map &other) const
672 : : {
673 : 1967614 : if (m_map.elements () != other.m_map.elements ())
674 : : return false;
675 : :
676 : 5941060 : for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
677 : : {
678 : 2030794 : const binding_key *key = (*iter).first;
679 : 2030794 : const svalue *sval = (*iter).second;
680 : 2030794 : const svalue **other_slot
681 : 2030794 : = const_cast <map_t &> (other.m_map).get (key);
682 : 2030794 : if (other_slot == NULL)
683 : 35952 : return false;
684 : 2023812 : if (sval != *other_slot)
685 : : return false;
686 : : }
687 : 1915424 : gcc_checking_assert (hash () == other.hash ());
688 : : return true;
689 : : }
690 : :
691 : : /* Generate a hash value for this binding_map. */
692 : :
693 : : hashval_t
694 : 17412997 : binding_map::hash () const
695 : : {
696 : 17412997 : hashval_t result = 0;
697 : 35454374 : for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
698 : : {
699 : : /* Use a new hasher for each key to avoid depending on the ordering
700 : : of keys when accumulating the result. */
701 : 18041377 : inchash::hash hstate;
702 : 18041377 : hstate.add_ptr ((*iter).first);
703 : 18041377 : hstate.add_ptr ((*iter).second);
704 : 18041377 : result ^= hstate.end ();
705 : : }
706 : 17412997 : return result;
707 : : }
708 : :
709 : : /* Dump a representation of this binding_map to PP.
710 : : SIMPLE controls how values and regions are to be printed.
711 : : If MULTILINE, then split the dump over multiple lines and
712 : : use whitespace for readability, otherwise put all on one line. */
713 : :
714 : : void
715 : 2173 : binding_map::dump_to_pp (pretty_printer *pp, bool simple,
716 : : bool multiline) const
717 : : {
718 : 2173 : auto_vec <const binding_key *> binding_keys;
719 : 3816 : for (map_t::iterator iter = m_map.begin ();
720 : 5459 : iter != m_map.end (); ++iter)
721 : : {
722 : 1643 : const binding_key *key = (*iter).first;
723 : 1643 : binding_keys.safe_push (key);
724 : : }
725 : 2173 : binding_keys.qsort (binding_key::cmp_ptrs);
726 : :
727 : : const binding_key *key;
728 : : unsigned i;
729 : 4745 : FOR_EACH_VEC_ELT (binding_keys, i, key)
730 : : {
731 : 1643 : const svalue *value = *const_cast <map_t &> (m_map).get (key);
732 : 1643 : if (multiline)
733 : : {
734 : 328 : pp_string (pp, " key: {");
735 : 328 : key->dump_to_pp (pp, simple);
736 : 328 : pp_string (pp, "}");
737 : 328 : pp_newline (pp);
738 : 328 : pp_string (pp, " value: ");
739 : 328 : if (tree t = value->get_type ())
740 : 328 : dump_quoted_tree (pp, t);
741 : 328 : pp_string (pp, " {");
742 : 328 : value->dump_to_pp (pp, simple);
743 : 328 : pp_string (pp, "}");
744 : 328 : pp_newline (pp);
745 : : }
746 : : else
747 : : {
748 : 1315 : if (i > 0)
749 : 566 : pp_string (pp, ", ");
750 : 1315 : pp_string (pp, "binding key: {");
751 : 1315 : key->dump_to_pp (pp, simple);
752 : 1315 : pp_string (pp, "}, value: {");
753 : 1315 : value->dump_to_pp (pp, simple);
754 : 1315 : pp_string (pp, "}");
755 : : }
756 : : }
757 : 2173 : }
758 : :
759 : : /* Dump a multiline representation of this binding_map to stderr. */
760 : :
761 : : DEBUG_FUNCTION void
762 : 0 : binding_map::dump (bool simple) const
763 : : {
764 : 0 : tree_dump_pretty_printer pp (stderr);
765 : 0 : dump_to_pp (&pp, simple, true);
766 : 0 : pp_newline (&pp);
767 : 0 : }
768 : :
769 : : /* Return a new json::object of the form
770 : : {KEY_DESC : SVALUE_DESC,
771 : : ...for the various key/value pairs in this binding_map}. */
772 : :
773 : : std::unique_ptr<json::object>
774 : 0 : binding_map::to_json () const
775 : : {
776 : 0 : auto map_obj = ::make_unique<json::object> ();
777 : :
778 : 0 : auto_vec <const binding_key *> binding_keys;
779 : 0 : for (map_t::iterator iter = m_map.begin ();
780 : 0 : iter != m_map.end (); ++iter)
781 : : {
782 : 0 : const binding_key *key = (*iter).first;
783 : 0 : binding_keys.safe_push (key);
784 : : }
785 : 0 : binding_keys.qsort (binding_key::cmp_ptrs);
786 : :
787 : : const binding_key *key;
788 : : unsigned i;
789 : 0 : FOR_EACH_VEC_ELT (binding_keys, i, key)
790 : : {
791 : 0 : const svalue *value = *const_cast <map_t &> (m_map).get (key);
792 : 0 : label_text key_desc = key->get_desc ();
793 : 0 : map_obj->set (key_desc.get (), value->to_json ());
794 : 0 : }
795 : :
796 : 0 : return map_obj;
797 : 0 : }
798 : :
799 : : /* Add a child to PARENT_WIDGET expressing a binding between
800 : : KEY and SVAL. */
801 : :
802 : : static void
803 : 0 : add_binding_to_tree_widget (text_art::tree_widget &parent_widget,
804 : : const text_art::dump_widget_info &dwi,
805 : : const binding_key *key,
806 : : const svalue *sval)
807 : : {
808 : 0 : pretty_printer the_pp;
809 : 0 : pretty_printer * const pp = &the_pp;
810 : 0 : pp_format_decoder (pp) = default_tree_printer;
811 : 0 : pp_show_color (pp) = true;
812 : 0 : const bool simple = true;
813 : :
814 : 0 : key->dump_to_pp (pp, simple);
815 : 0 : pp_string (pp, ": ");
816 : 0 : if (tree t = sval->get_type ())
817 : 0 : dump_quoted_tree (pp, t);
818 : 0 : pp_string (pp, " {");
819 : 0 : sval->dump_to_pp (pp, simple);
820 : 0 : pp_string (pp, "}");
821 : :
822 : 0 : parent_widget.add_child (text_art::tree_widget::make (dwi, pp));
823 : 0 : }
824 : :
825 : : void
826 : 0 : binding_map::add_to_tree_widget (text_art::tree_widget &parent_widget,
827 : : const text_art::dump_widget_info &dwi) const
828 : : {
829 : 0 : auto_vec <const binding_key *> binding_keys;
830 : 0 : for (map_t::iterator iter = m_map.begin ();
831 : 0 : iter != m_map.end (); ++iter)
832 : : {
833 : 0 : const binding_key *key = (*iter).first;
834 : 0 : binding_keys.safe_push (key);
835 : : }
836 : 0 : binding_keys.qsort (binding_key::cmp_ptrs);
837 : :
838 : : const binding_key *key;
839 : : unsigned i;
840 : 0 : FOR_EACH_VEC_ELT (binding_keys, i, key)
841 : : {
842 : 0 : const svalue *sval = *const_cast <map_t &> (m_map).get (key);
843 : 0 : add_binding_to_tree_widget (parent_widget, dwi,
844 : : key, sval);
845 : : }
846 : 0 : }
847 : :
848 : :
849 : : /* Comparator for imposing an order on binding_maps. */
850 : :
851 : : int
852 : 0 : binding_map::cmp (const binding_map &map1, const binding_map &map2)
853 : : {
854 : 0 : if (int count_cmp = map1.elements () - map2.elements ())
855 : : return count_cmp;
856 : :
857 : 0 : auto_vec <const binding_key *> keys1 (map1.elements ());
858 : 0 : for (map_t::iterator iter = map1.begin ();
859 : 0 : iter != map1.end (); ++iter)
860 : 0 : keys1.quick_push ((*iter).first);
861 : 0 : keys1.qsort (binding_key::cmp_ptrs);
862 : :
863 : 0 : auto_vec <const binding_key *> keys2 (map2.elements ());
864 : 0 : for (map_t::iterator iter = map2.begin ();
865 : 0 : iter != map2.end (); ++iter)
866 : 0 : keys2.quick_push ((*iter).first);
867 : 0 : keys2.qsort (binding_key::cmp_ptrs);
868 : :
869 : 0 : for (size_t i = 0; i < keys1.length (); i++)
870 : : {
871 : 0 : const binding_key *k1 = keys1[i];
872 : 0 : const binding_key *k2 = keys2[i];
873 : 0 : if (int key_cmp = binding_key::cmp (k1, k2))
874 : : return key_cmp;
875 : 0 : gcc_assert (k1 == k2);
876 : 0 : if (int sval_cmp = svalue::cmp_ptr (map1.get (k1), map2.get (k2)))
877 : : return sval_cmp;
878 : : }
879 : :
880 : : return 0;
881 : 0 : }
882 : :
883 : : /* Get the child region of PARENT_REG based upon INDEX within a
884 : : CONSTRUCTOR. */
885 : :
886 : : static const region *
887 : 444 : get_subregion_within_ctor (const region *parent_reg, tree index,
888 : : region_model_manager *mgr)
889 : : {
890 : 444 : switch (TREE_CODE (index))
891 : : {
892 : 0 : default:
893 : 0 : gcc_unreachable ();
894 : 390 : case INTEGER_CST:
895 : 390 : {
896 : 390 : const svalue *index_sval
897 : 390 : = mgr->get_or_create_constant_svalue (index);
898 : 390 : return mgr->get_element_region (parent_reg,
899 : 390 : TREE_TYPE (parent_reg->get_type ()),
900 : 390 : index_sval);
901 : : }
902 : 54 : break;
903 : 54 : case FIELD_DECL:
904 : 54 : return mgr->get_field_region (parent_reg, index);
905 : : }
906 : : }
907 : :
908 : : /* Get the svalue for VAL, a non-CONSTRUCTOR value within a CONSTRUCTOR. */
909 : :
910 : : static const svalue *
911 : 405 : get_svalue_for_ctor_val (tree val, region_model_manager *mgr)
912 : : {
913 : : /* Reuse the get_rvalue logic from region_model. */
914 : 405 : region_model m (mgr);
915 : 405 : return m.get_rvalue (path_var (val, 0), NULL);
916 : 405 : }
917 : :
918 : : /* Bind values from CONSTRUCTOR to this map, relative to
919 : : PARENT_REG's relationship to its base region.
920 : : Return true if successful, false if there was a problem (e.g. due
921 : : to hitting a complexity limit). */
922 : :
923 : : bool
924 : 147 : binding_map::apply_ctor_to_region (const region *parent_reg, tree ctor,
925 : : region_model_manager *mgr)
926 : : {
927 : 147 : gcc_assert (parent_reg);
928 : 147 : gcc_assert (TREE_CODE (ctor) == CONSTRUCTOR);
929 : :
930 : 147 : unsigned ix;
931 : 147 : tree index;
932 : 147 : tree val;
933 : 147 : tree parent_type = parent_reg->get_type ();
934 : 147 : tree field;
935 : 147 : if (TREE_CODE (parent_type) == RECORD_TYPE)
936 : 48 : field = TYPE_FIELDS (parent_type);
937 : : else
938 : : field = NULL_TREE;
939 : 590 : FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), ix, index, val)
940 : : {
941 : 444 : if (!index)
942 : : {
943 : : /* If index is NULL, then iterate through the fields for
944 : : a RECORD_TYPE, or use an INTEGER_CST otherwise.
945 : : Compare with similar logic in output_constructor. */
946 : 135 : if (field)
947 : : {
948 : 0 : index = field;
949 : 0 : field = DECL_CHAIN (field);
950 : : }
951 : : else
952 : 135 : index = build_int_cst (integer_type_node, ix);
953 : : }
954 : 309 : else if (TREE_CODE (index) == RANGE_EXPR)
955 : : {
956 : 0 : tree min_index = TREE_OPERAND (index, 0);
957 : 0 : tree max_index = TREE_OPERAND (index, 1);
958 : 0 : if (min_index == max_index)
959 : : {
960 : 0 : if (!apply_ctor_pair_to_child_region (parent_reg, mgr,
961 : : min_index, val))
962 : : return false;
963 : : }
964 : : else
965 : : {
966 : 0 : if (!apply_ctor_val_to_range (parent_reg, mgr,
967 : : min_index, max_index, val))
968 : : return false;
969 : : }
970 : 0 : continue;
971 : 0 : }
972 : 444 : if (!apply_ctor_pair_to_child_region (parent_reg, mgr, index, val))
973 : : return false;
974 : : }
975 : : return true;
976 : : }
977 : :
978 : : /* Bind the value VAL into the range of elements within PARENT_REF
979 : : from MIN_INDEX to MAX_INDEX (including endpoints).
980 : : For use in handling RANGE_EXPR within a CONSTRUCTOR.
981 : : Return true if successful, false if there was a problem (e.g. due
982 : : to hitting a complexity limit). */
983 : :
984 : : bool
985 : 0 : binding_map::apply_ctor_val_to_range (const region *parent_reg,
986 : : region_model_manager *mgr,
987 : : tree min_index, tree max_index,
988 : : tree val)
989 : : {
990 : 0 : gcc_assert (TREE_CODE (min_index) == INTEGER_CST);
991 : 0 : gcc_assert (TREE_CODE (max_index) == INTEGER_CST);
992 : :
993 : : /* Generate a binding key for the range. */
994 : 0 : const region *min_element
995 : 0 : = get_subregion_within_ctor (parent_reg, min_index, mgr);
996 : 0 : const region *max_element
997 : 0 : = get_subregion_within_ctor (parent_reg, max_index, mgr);
998 : 0 : region_offset min_offset = min_element->get_offset (mgr);
999 : 0 : if (min_offset.symbolic_p ())
1000 : : return false;
1001 : 0 : bit_offset_t start_bit_offset = min_offset.get_bit_offset ();
1002 : 0 : store_manager *smgr = mgr->get_store_manager ();
1003 : 0 : if (max_element->empty_p ())
1004 : : return false;
1005 : 0 : const binding_key *max_element_key = binding_key::make (smgr, max_element);
1006 : 0 : if (max_element_key->symbolic_p ())
1007 : : return false;
1008 : 0 : const concrete_binding *max_element_ckey
1009 : 0 : = max_element_key->dyn_cast_concrete_binding ();
1010 : 0 : bit_size_t range_size_in_bits
1011 : 0 : = max_element_ckey->get_next_bit_offset () - start_bit_offset;
1012 : 0 : const concrete_binding *range_key
1013 : 0 : = smgr->get_concrete_binding (start_bit_offset, range_size_in_bits);
1014 : 0 : if (range_key->symbolic_p ())
1015 : : return false;
1016 : :
1017 : : /* Get the value. */
1018 : 0 : if (TREE_CODE (val) == CONSTRUCTOR)
1019 : : return false;
1020 : 0 : const svalue *sval = get_svalue_for_ctor_val (val, mgr);
1021 : :
1022 : : /* Bind the value to the range. */
1023 : 0 : put (range_key, sval);
1024 : 0 : return true;
1025 : : }
1026 : :
1027 : : /* Bind the value VAL into INDEX within PARENT_REF.
1028 : : For use in handling a pair of entries within a CONSTRUCTOR.
1029 : : Return true if successful, false if there was a problem (e.g. due
1030 : : to hitting a complexity limit). */
1031 : :
1032 : : bool
1033 : 444 : binding_map::apply_ctor_pair_to_child_region (const region *parent_reg,
1034 : : region_model_manager *mgr,
1035 : : tree index, tree val)
1036 : : {
1037 : 444 : const region *child_reg
1038 : 444 : = get_subregion_within_ctor (parent_reg, index, mgr);
1039 : 444 : if (TREE_CODE (val) == CONSTRUCTOR)
1040 : 39 : return apply_ctor_to_region (child_reg, val, mgr);
1041 : : else
1042 : : {
1043 : 405 : const svalue *sval = get_svalue_for_ctor_val (val, mgr);
1044 : 405 : if (child_reg->empty_p ())
1045 : : return false;
1046 : 405 : const binding_key *k
1047 : 405 : = binding_key::make (mgr->get_store_manager (), child_reg);
1048 : : /* Handle the case where we have an unknown size for child_reg
1049 : : (e.g. due to it being a trailing field with incomplete array
1050 : : type. */
1051 : 405 : if (!k->concrete_p ())
1052 : : {
1053 : : /* Assume that sval has a well-defined size for this case. */
1054 : 5 : tree sval_type = sval->get_type ();
1055 : 5 : gcc_assert (sval_type);
1056 : 5 : HOST_WIDE_INT sval_byte_size = int_size_in_bytes (sval_type);
1057 : 5 : gcc_assert (sval_byte_size != -1);
1058 : 5 : bit_size_t sval_bit_size = sval_byte_size * BITS_PER_UNIT;
1059 : : /* Get offset of child relative to base region. */
1060 : 5 : region_offset child_base_offset = child_reg->get_offset (mgr);
1061 : 5 : if (child_base_offset.symbolic_p ())
1062 : 1 : return false;
1063 : : /* Convert to an offset relative to the parent region. */
1064 : 4 : region_offset parent_base_offset = parent_reg->get_offset (mgr);
1065 : 4 : gcc_assert (!parent_base_offset.symbolic_p ());
1066 : 4 : bit_offset_t child_parent_offset
1067 : 4 : = (child_base_offset.get_bit_offset ()
1068 : 4 : - parent_base_offset.get_bit_offset ());
1069 : : /* Create a concrete key for the child within the parent. */
1070 : 4 : k = mgr->get_store_manager ()->get_concrete_binding
1071 : 4 : (child_parent_offset, sval_bit_size);
1072 : : }
1073 : 404 : gcc_assert (k->concrete_p ());
1074 : 404 : put (k, sval);
1075 : 404 : return true;
1076 : : }
1077 : : }
1078 : :
1079 : : /* Populate OUT with all bindings within this map that overlap KEY. */
1080 : :
1081 : : void
1082 : 41420 : binding_map::get_overlapping_bindings (const binding_key *key,
1083 : : auto_vec<const binding_key *> *out)
1084 : : {
1085 : 193940 : for (auto iter : *this)
1086 : : {
1087 : 76260 : const binding_key *iter_key = iter.first;
1088 : 152520 : if (const concrete_binding *ckey
1089 : 76260 : = key->dyn_cast_concrete_binding ())
1090 : : {
1091 : 147330 : if (const concrete_binding *iter_ckey
1092 : 73665 : = iter_key->dyn_cast_concrete_binding ())
1093 : : {
1094 : 72903 : if (ckey->overlaps_p (*iter_ckey))
1095 : 32631 : out->safe_push (iter_key);
1096 : : }
1097 : : else
1098 : : {
1099 : : /* Assume overlap. */
1100 : 762 : out->safe_push (iter_key);
1101 : : }
1102 : : }
1103 : : else
1104 : : {
1105 : : /* Assume overlap. */
1106 : 2595 : out->safe_push (iter_key);
1107 : : }
1108 : : }
1109 : 41420 : }
1110 : :
1111 : : /* Remove, truncate, and/or split any bindings within this map that
1112 : : overlap DROP_KEY.
1113 : :
1114 : : For example, if we have:
1115 : :
1116 : : +------------------------------------+
1117 : : | old binding |
1118 : : +------------------------------------+
1119 : :
1120 : : which is to be overwritten with:
1121 : :
1122 : : .......+----------------------+.......
1123 : : .......| new binding |.......
1124 : : .......+----------------------+.......
1125 : :
1126 : : this function "cuts a hole" out of the old binding:
1127 : :
1128 : : +------+......................+------+
1129 : : |prefix| hole for new binding |suffix|
1130 : : +------+......................+------+
1131 : :
1132 : : into which the new binding can be added without
1133 : : overlapping the prefix or suffix.
1134 : :
1135 : : The prefix and suffix (if added) will be bound to the pertinent
1136 : : parts of the value of the old binding.
1137 : :
1138 : : For example, given:
1139 : : struct s5
1140 : : {
1141 : : char arr[8];
1142 : : };
1143 : : void test_5 (struct s5 *p)
1144 : : {
1145 : : struct s5 f = *p;
1146 : : f.arr[3] = 42;
1147 : : }
1148 : : then after the "f = *p;" we have:
1149 : : cluster for: f: INIT_VAL((*INIT_VAL(p_33(D))))
1150 : : and at the "f.arr[3] = 42;" we remove the bindings overlapping
1151 : : "f.arr[3]", replacing it with a prefix (bytes 0-2) and suffix (bytes 4-7)
1152 : : giving:
1153 : : cluster for: f
1154 : : key: {bytes 0-2}
1155 : : value: {BITS_WITHIN(bytes 0-2, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
1156 : : key: {bytes 4-7}
1157 : : value: {BITS_WITHIN(bytes 4-7, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
1158 : : punching a hole into which the new value can be written at byte 3:
1159 : : cluster for: f
1160 : : key: {bytes 0-2}
1161 : : value: {BITS_WITHIN(bytes 0-2, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
1162 : : key: {byte 3}
1163 : : value: 'char' {(char)42}
1164 : : key: {bytes 4-7}
1165 : : value: {BITS_WITHIN(bytes 4-7, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
1166 : :
1167 : : If UNCERTAINTY is non-NULL, use it to record any svalues that
1168 : : were removed, as being maybe-bound.
1169 : :
1170 : : If MAYBE_LIVE_VALUES is non-NULL, then use it to record any svalues that
1171 : : were removed as being maybe-live.
1172 : :
1173 : : If ALWAYS_OVERLAP, then assume that DROP_KEY can overlap anything
1174 : : in the map, due to one or both of the underlying clusters being
1175 : : symbolic (but not the same symbolic region). Hence even if DROP_KEY is a
1176 : : concrete binding it could actually be referring to the same memory as
1177 : : distinct concrete bindings in the map. Remove all bindings, but
1178 : : register any svalues with *UNCERTAINTY. */
1179 : :
1180 : : void
1181 : 103280 : binding_map::remove_overlapping_bindings (store_manager *mgr,
1182 : : const binding_key *drop_key,
1183 : : uncertainty_t *uncertainty,
1184 : : svalue_set *maybe_live_values,
1185 : : bool always_overlap)
1186 : : {
1187 : : /* Get the bindings of interest within this map. */
1188 : 103280 : auto_vec<const binding_key *> bindings;
1189 : 103280 : if (always_overlap)
1190 : 186487 : for (auto iter : *this)
1191 : 62767 : bindings.safe_push (iter.first); /* Add all bindings. */
1192 : : else
1193 : : /* Just add overlapping bindings. */
1194 : 41420 : get_overlapping_bindings (drop_key, &bindings);
1195 : :
1196 : : unsigned i;
1197 : : const binding_key *iter_binding;
1198 : 293432 : FOR_EACH_VEC_ELT (bindings, i, iter_binding)
1199 : : {
1200 : : /* Record any svalues that were removed to *UNCERTAINTY as being
1201 : : maybe-bound, provided at least some part of the binding is symbolic.
1202 : :
1203 : : Specifically, if at least one of the bindings is symbolic, or we
1204 : : have ALWAYS_OVERLAP for the case where we have possibly aliasing
1205 : : regions, then we don't know that the svalue has been overwritten,
1206 : : and should record that to *UNCERTAINTY.
1207 : :
1208 : : However, if we have concrete keys accessing within the same symbolic
1209 : : region, then we *know* that the symbolic region has been overwritten,
1210 : : so we don't record it to *UNCERTAINTY, as this could be a genuine
1211 : : leak. */
1212 : 98755 : const svalue *old_sval = get (iter_binding);
1213 : 98755 : if (uncertainty
1214 : 128196 : && (drop_key->symbolic_p ()
1215 : 27136 : || iter_binding->symbolic_p ()
1216 : 23182 : || always_overlap))
1217 : 25559 : uncertainty->on_maybe_bound_sval (old_sval);
1218 : :
1219 : : /* Record any svalues that were removed to *MAYBE_LIVE_VALUES as being
1220 : : maybe-live. */
1221 : 98755 : if (maybe_live_values)
1222 : 62767 : maybe_live_values->add (old_sval);
1223 : :
1224 : : /* Begin by removing the old binding. */
1225 : 98755 : m_map.remove (iter_binding);
1226 : :
1227 : : /* Don't attempt to handle prefixes/suffixes for the
1228 : : "always_overlap" case; everything's being removed. */
1229 : 98755 : if (always_overlap)
1230 : 62767 : continue;
1231 : :
1232 : : /* Now potentially add the prefix and suffix. */
1233 : 71976 : if (const concrete_binding *drop_ckey
1234 : 35988 : = drop_key->dyn_cast_concrete_binding ())
1235 : 66786 : if (const concrete_binding *iter_ckey
1236 : 33393 : = iter_binding->dyn_cast_concrete_binding ())
1237 : : {
1238 : 32631 : gcc_assert (drop_ckey->overlaps_p (*iter_ckey));
1239 : :
1240 : 32631 : const bit_range &drop_bits = drop_ckey->get_bit_range ();
1241 : 32631 : const bit_range &iter_bits = iter_ckey->get_bit_range ();
1242 : :
1243 : 32631 : if (iter_bits.get_start_bit_offset ()
1244 : 32631 : < drop_bits.get_start_bit_offset ())
1245 : : {
1246 : : /* We have a truncated prefix. */
1247 : 5370 : bit_range prefix_bits (iter_bits.get_start_bit_offset (),
1248 : 10740 : (drop_bits.get_start_bit_offset ()
1249 : 5370 : - iter_bits.get_start_bit_offset ()));
1250 : 5370 : const concrete_binding *prefix_key
1251 : 5370 : = mgr->get_concrete_binding (prefix_bits);
1252 : 5370 : bit_range rel_prefix (0, prefix_bits.m_size_in_bits);
1253 : 5370 : const svalue *prefix_sval
1254 : 5370 : = old_sval->extract_bit_range (NULL_TREE,
1255 : : rel_prefix,
1256 : 5370 : mgr->get_svalue_manager ());
1257 : 5370 : m_map.put (prefix_key, prefix_sval);
1258 : : }
1259 : :
1260 : 65262 : if (iter_bits.get_next_bit_offset ()
1261 : 65262 : > drop_bits.get_next_bit_offset ())
1262 : : {
1263 : : /* We have a truncated suffix. */
1264 : 7706 : bit_range suffix_bits (drop_bits.get_next_bit_offset (),
1265 : 7706 : (iter_bits.get_next_bit_offset ()
1266 : 15412 : - drop_bits.get_next_bit_offset ()));
1267 : 7706 : const concrete_binding *suffix_key
1268 : 7706 : = mgr->get_concrete_binding (suffix_bits);
1269 : 7706 : bit_range rel_suffix (drop_bits.get_next_bit_offset ()
1270 : 7706 : - iter_bits.get_start_bit_offset (),
1271 : 7706 : suffix_bits.m_size_in_bits);
1272 : 7706 : const svalue *suffix_sval
1273 : 7706 : = old_sval->extract_bit_range (NULL_TREE,
1274 : : rel_suffix,
1275 : 7706 : mgr->get_svalue_manager ());
1276 : 7706 : m_map.put (suffix_key, suffix_sval);
1277 : : }
1278 : : }
1279 : : }
1280 : 103280 : }
1281 : :
1282 : : /* class binding_cluster. */
1283 : :
1284 : 1458248 : binding_cluster::binding_cluster (const region *base_region)
1285 : 1458248 : : m_base_region (base_region), m_map (),
1286 : 1458248 : m_escaped (false), m_touched (false)
1287 : : {
1288 : 1458248 : }
1289 : :
1290 : : /* binding_cluster's copy ctor. */
1291 : :
1292 : 23860053 : binding_cluster::binding_cluster (const binding_cluster &other)
1293 : 23860053 : : m_base_region (other.m_base_region), m_map (other.m_map),
1294 : 23860053 : m_escaped (other.m_escaped), m_touched (other.m_touched)
1295 : : {
1296 : 23860053 : }
1297 : :
1298 : : /* binding_cluster's assignment operator. */
1299 : :
1300 : : binding_cluster&
1301 : 0 : binding_cluster::operator= (const binding_cluster &other)
1302 : : {
1303 : 0 : gcc_assert (m_base_region == other.m_base_region);
1304 : 0 : m_map = other.m_map;
1305 : 0 : m_escaped = other.m_escaped;
1306 : 0 : m_touched = other.m_touched;
1307 : 0 : return *this;
1308 : : }
1309 : :
1310 : : /* binding_cluster's equality operator. */
1311 : :
1312 : : bool
1313 : 1940155 : binding_cluster::operator== (const binding_cluster &other) const
1314 : : {
1315 : 1940155 : if (m_map != other.m_map)
1316 : : return false;
1317 : :
1318 : 1910038 : if (m_base_region != other.m_base_region)
1319 : : return false;
1320 : :
1321 : 1910038 : if (m_escaped != other.m_escaped)
1322 : : return false;
1323 : :
1324 : 1909360 : if (m_touched != other.m_touched)
1325 : : return false;
1326 : :
1327 : 1907955 : gcc_checking_assert (hash () == other.hash ());
1328 : :
1329 : : return true;
1330 : : }
1331 : :
1332 : : /* Generate a hash value for this binding_cluster. */
1333 : :
1334 : : hashval_t
1335 : 13582149 : binding_cluster::hash () const
1336 : : {
1337 : 13582149 : return m_map.hash ();
1338 : : }
1339 : :
1340 : : /* Return true if this binding_cluster is symbolic
1341 : : i.e. its base region is symbolic. */
1342 : :
1343 : : bool
1344 : 7610211 : binding_cluster::symbolic_p () const
1345 : : {
1346 : 7610211 : return m_base_region->get_kind () == RK_SYMBOLIC;
1347 : : }
1348 : :
1349 : : /* Dump a representation of this binding_cluster to PP.
1350 : : SIMPLE controls how values and regions are to be printed.
1351 : : If MULTILINE, then split the dump over multiple lines and
1352 : : use whitespace for readability, otherwise put all on one line. */
1353 : :
1354 : : void
1355 : 2173 : binding_cluster::dump_to_pp (pretty_printer *pp, bool simple,
1356 : : bool multiline) const
1357 : : {
1358 : 2173 : if (m_escaped)
1359 : : {
1360 : 1422 : if (multiline)
1361 : : {
1362 : 1240 : pp_string (pp, " ESCAPED");
1363 : 1240 : pp_newline (pp);
1364 : : }
1365 : : else
1366 : 182 : pp_string (pp, "(ESCAPED)");
1367 : : }
1368 : 2173 : if (m_touched)
1369 : : {
1370 : 306 : if (multiline)
1371 : : {
1372 : 124 : pp_string (pp, " TOUCHED");
1373 : 124 : pp_newline (pp);
1374 : : }
1375 : : else
1376 : 182 : pp_string (pp, "(TOUCHED)");
1377 : : }
1378 : :
1379 : 2173 : m_map.dump_to_pp (pp, simple, multiline);
1380 : 2173 : }
1381 : :
1382 : : /* Dump a multiline representation of this binding_cluster to stderr. */
1383 : :
1384 : : DEBUG_FUNCTION void
1385 : 0 : binding_cluster::dump (bool simple) const
1386 : : {
1387 : 0 : tree_dump_pretty_printer pp (stderr);
1388 : 0 : pp_string (&pp, " cluster for: ");
1389 : 0 : m_base_region->dump_to_pp (&pp, simple);
1390 : 0 : pp_string (&pp, ": ");
1391 : 0 : pp_newline (&pp);
1392 : 0 : dump_to_pp (&pp, simple, true);
1393 : 0 : pp_newline (&pp);
1394 : 0 : }
1395 : :
1396 : : /* Assert that this object is valid. */
1397 : :
1398 : : void
1399 : 8829970 : binding_cluster::validate () const
1400 : : {
1401 : 8829970 : int num_symbolic = 0;
1402 : 8829970 : int num_concrete = 0;
1403 : 27169198 : for (auto iter : m_map)
1404 : : {
1405 : 9169614 : if (iter.first->symbolic_p ())
1406 : 849875 : num_symbolic++;
1407 : : else
1408 : 8319739 : num_concrete++;
1409 : : }
1410 : : /* We shouldn't have more than one symbolic key per cluster
1411 : : (or one would have clobbered the other). */
1412 : 8829970 : gcc_assert (num_symbolic < 2);
1413 : : /* We can't have both concrete and symbolic keys. */
1414 : 8829970 : gcc_assert (num_concrete == 0 || num_symbolic == 0);
1415 : 8829970 : }
1416 : :
1417 : : /* Return a new json::object of the form
1418 : : {"escaped": true/false,
1419 : : "touched": true/false,
1420 : : "map" : object for the binding_map. */
1421 : :
1422 : : std::unique_ptr<json::object>
1423 : 0 : binding_cluster::to_json () const
1424 : : {
1425 : 0 : auto cluster_obj = ::make_unique<json::object> ();
1426 : :
1427 : 0 : cluster_obj->set_bool ("escaped", m_escaped);
1428 : 0 : cluster_obj->set_bool ("touched", m_touched);
1429 : 0 : cluster_obj->set ("map", m_map.to_json ());
1430 : :
1431 : 0 : return cluster_obj;
1432 : : }
1433 : :
1434 : : std::unique_ptr<text_art::tree_widget>
1435 : 0 : binding_cluster::make_dump_widget (const text_art::dump_widget_info &dwi,
1436 : : store_manager *mgr) const
1437 : : {
1438 : 0 : pretty_printer the_pp;
1439 : 0 : pretty_printer * const pp = &the_pp;
1440 : 0 : pp_format_decoder (pp) = default_tree_printer;
1441 : 0 : pp_show_color (pp) = true;
1442 : 0 : const bool simple = true;
1443 : :
1444 : 0 : m_base_region->dump_to_pp (pp, simple);
1445 : 0 : pp_string (pp, ": ");
1446 : :
1447 : 0 : if (const svalue *sval = maybe_get_simple_value (mgr))
1448 : : {
1449 : : /* Special-case to simplify dumps for the common case where
1450 : : we just have one value directly bound to the whole of a
1451 : : region. */
1452 : 0 : sval->dump_to_pp (pp, simple);
1453 : 0 : if (escaped_p ())
1454 : 0 : pp_string (pp, " (ESCAPED)");
1455 : 0 : if (touched_p ())
1456 : 0 : pp_string (pp, " (TOUCHED)");
1457 : :
1458 : 0 : return text_art::tree_widget::make (dwi, pp);
1459 : : }
1460 : : else
1461 : : {
1462 : 0 : if (escaped_p ())
1463 : 0 : pp_string (pp, " (ESCAPED)");
1464 : 0 : if (touched_p ())
1465 : 0 : pp_string (pp, " (TOUCHED)");
1466 : :
1467 : 0 : std::unique_ptr<text_art::tree_widget> cluster_widget
1468 : 0 : (text_art::tree_widget::make (dwi, pp));
1469 : :
1470 : 0 : m_map.add_to_tree_widget (*cluster_widget, dwi);
1471 : :
1472 : 0 : return cluster_widget;
1473 : 0 : }
1474 : 0 : }
1475 : :
1476 : : /* Add a binding of SVAL of kind KIND to REG, unpacking SVAL if it is a
1477 : : compound_sval. */
1478 : :
1479 : : void
1480 : 417310 : binding_cluster::bind (store_manager *mgr,
1481 : : const region *reg, const svalue *sval)
1482 : : {
1483 : 834620 : if (const compound_svalue *compound_sval
1484 : 417310 : = sval->dyn_cast_compound_svalue ())
1485 : : {
1486 : 864 : bind_compound_sval (mgr, reg, compound_sval);
1487 : 864 : return;
1488 : : }
1489 : :
1490 : 416446 : if (reg->empty_p ())
1491 : : return;
1492 : 416446 : const binding_key *binding = binding_key::make (mgr, reg);
1493 : 416446 : bind_key (binding, sval);
1494 : : }
1495 : :
1496 : : /* Bind SVAL to KEY.
1497 : : Unpacking of compound_svalues should already have been done by the
1498 : : time this is called. */
1499 : :
1500 : : void
1501 : 420690 : binding_cluster::bind_key (const binding_key *key, const svalue *sval)
1502 : : {
1503 : 420690 : gcc_assert (sval->get_kind () != SK_COMPOUND);
1504 : :
1505 : 420690 : m_map.put (key, sval);
1506 : 420690 : if (key->symbolic_p ())
1507 : 30051 : m_touched = true;
1508 : 420690 : }
1509 : :
1510 : : /* Subroutine of binding_cluster::bind.
1511 : : Unpack compound_svals when binding them, so that we bind them
1512 : : element-wise. */
1513 : :
1514 : : void
1515 : 864 : binding_cluster::bind_compound_sval (store_manager *mgr,
1516 : : const region *reg,
1517 : : const compound_svalue *compound_sval)
1518 : : {
1519 : 864 : region_offset reg_offset
1520 : 864 : = reg->get_offset (mgr->get_svalue_manager ());
1521 : 864 : if (reg_offset.symbolic_p ())
1522 : : {
1523 : 4 : m_touched = true;
1524 : 4 : clobber_region (mgr, reg);
1525 : 4 : return;
1526 : : }
1527 : :
1528 : 3285 : for (map_t::iterator iter = compound_sval->begin ();
1529 : 6570 : iter != compound_sval->end (); ++iter)
1530 : : {
1531 : 2425 : const binding_key *iter_key = (*iter).first;
1532 : 2425 : const svalue *iter_sval = (*iter).second;
1533 : :
1534 : 4850 : if (const concrete_binding *concrete_key
1535 : 2425 : = iter_key->dyn_cast_concrete_binding ())
1536 : : {
1537 : 2425 : bit_offset_t effective_start
1538 : 2425 : = (concrete_key->get_start_bit_offset ()
1539 : 2425 : + reg_offset.get_bit_offset ());
1540 : 2425 : const concrete_binding *effective_concrete_key
1541 : 2425 : = mgr->get_concrete_binding (effective_start,
1542 : : concrete_key->get_size_in_bits ());
1543 : 2425 : bind_key (effective_concrete_key, iter_sval);
1544 : : }
1545 : : else
1546 : 0 : gcc_unreachable ();
1547 : : }
1548 : : }
1549 : :
1550 : : /* Remove all bindings overlapping REG within this cluster. */
1551 : :
1552 : : void
1553 : 6355 : binding_cluster::clobber_region (store_manager *mgr, const region *reg)
1554 : : {
1555 : 6355 : remove_overlapping_bindings (mgr, reg, NULL, NULL);
1556 : 6355 : }
1557 : :
1558 : : /* Remove any bindings for REG within this cluster. */
1559 : :
1560 : : void
1561 : 178731 : binding_cluster::purge_region (store_manager *mgr, const region *reg)
1562 : : {
1563 : 178731 : gcc_assert (reg->get_kind () == RK_DECL);
1564 : 178731 : if (reg->empty_p ())
1565 : : return;
1566 : 178731 : const binding_key *binding
1567 : 178731 : = binding_key::make (mgr, const_cast<region *> (reg));
1568 : 178731 : m_map.remove (binding);
1569 : : }
1570 : :
1571 : : /* Clobber REG and fill it with repeated copies of SVAL. */
1572 : :
1573 : : void
1574 : 1439 : binding_cluster::fill_region (store_manager *mgr,
1575 : : const region *reg,
1576 : : const svalue *sval)
1577 : : {
1578 : 1439 : clobber_region (mgr, reg);
1579 : :
1580 : 1439 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
1581 : 1439 : const svalue *byte_size_sval = reg->get_byte_size_sval (sval_mgr);
1582 : 1439 : const svalue *fill_sval
1583 : 1439 : = sval_mgr->get_or_create_repeated_svalue (reg->get_type (),
1584 : : byte_size_sval, sval);
1585 : 1439 : bind (mgr, reg, fill_sval);
1586 : 1439 : }
1587 : :
1588 : : /* Clobber REG within this cluster and fill it with zeroes. */
1589 : :
1590 : : void
1591 : 33 : binding_cluster::zero_fill_region (store_manager *mgr, const region *reg)
1592 : : {
1593 : 33 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
1594 : 33 : const svalue *zero_sval = sval_mgr->get_or_create_int_cst (char_type_node, 0);
1595 : 33 : fill_region (mgr, reg, zero_sval);
1596 : 33 : }
1597 : :
1598 : : /* Mark REG_TO_BIND within this cluster as being unknown.
1599 : :
1600 : : Remove any bindings overlapping REG_FOR_OVERLAP.
1601 : : If UNCERTAINTY is non-NULL, use it to record any svalues that
1602 : : had bindings to them removed, as being maybe-bound.
1603 : : If MAYBE_LIVE_VALUES is non-NULL, use it to record any svalues that
1604 : : had bindings to them removed, as being maybe-live.
1605 : :
1606 : : REG_TO_BIND and REG_FOR_OVERLAP are the same for
1607 : : store::mark_region_as_unknown, but are different in
1608 : : store::set_value's alias handling, for handling the case where
1609 : : we have a write to a symbolic REG_FOR_OVERLAP. */
1610 : :
1611 : : void
1612 : 62149 : binding_cluster::mark_region_as_unknown (store_manager *mgr,
1613 : : const region *reg_to_bind,
1614 : : const region *reg_for_overlap,
1615 : : uncertainty_t *uncertainty,
1616 : : svalue_set *maybe_live_values)
1617 : : {
1618 : 62149 : if (reg_to_bind->empty_p ())
1619 : : return;
1620 : :
1621 : 62149 : remove_overlapping_bindings (mgr, reg_for_overlap, uncertainty,
1622 : : maybe_live_values);
1623 : :
1624 : : /* Add a default binding to "unknown". */
1625 : 62149 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
1626 : 62149 : const svalue *sval
1627 : 62149 : = sval_mgr->get_or_create_unknown_svalue (reg_to_bind->get_type ());
1628 : 62149 : bind (mgr, reg_to_bind, sval);
1629 : : }
1630 : :
1631 : : /* Purge state involving SVAL. */
1632 : :
1633 : : void
1634 : 561814 : binding_cluster::purge_state_involving (const svalue *sval,
1635 : : region_model_manager *sval_mgr)
1636 : : {
1637 : 561814 : auto_vec<const binding_key *> to_remove;
1638 : 561814 : auto_vec<std::pair<const binding_key *, tree> > to_make_unknown;
1639 : 1689080 : for (auto iter : m_map)
1640 : : {
1641 : 563633 : const binding_key *iter_key = iter.first;
1642 : 1127266 : if (const symbolic_binding *symbolic_key
1643 : 563633 : = iter_key->dyn_cast_symbolic_binding ())
1644 : : {
1645 : 65725 : const region *reg = symbolic_key->get_region ();
1646 : 65725 : if (reg->involves_p (sval))
1647 : 0 : to_remove.safe_push (iter_key);
1648 : : }
1649 : 563633 : const svalue *iter_sval = iter.second;
1650 : 563633 : if (iter_sval->involves_p (sval))
1651 : 4279 : to_make_unknown.safe_push (std::make_pair(iter_key,
1652 : 4279 : iter_sval->get_type ()));
1653 : : }
1654 : 561814 : for (auto iter : to_remove)
1655 : : {
1656 : 0 : m_map.remove (iter);
1657 : 0 : m_touched = true;
1658 : : }
1659 : 574651 : for (auto iter : to_make_unknown)
1660 : : {
1661 : 4279 : const svalue *new_sval
1662 : 4279 : = sval_mgr->get_or_create_unknown_svalue (iter.second);
1663 : 4279 : m_map.put (iter.first, new_sval);
1664 : : }
1665 : 561814 : }
1666 : :
1667 : : /* Get any SVAL bound to REG within this cluster via kind KIND,
1668 : : without checking parent regions of REG. */
1669 : :
1670 : : const svalue *
1671 : 1398801 : binding_cluster::get_binding (store_manager *mgr,
1672 : : const region *reg) const
1673 : : {
1674 : 1398801 : if (reg->empty_p ())
1675 : : return NULL;
1676 : 1398801 : const binding_key *reg_binding = binding_key::make (mgr, reg);
1677 : 1398801 : const svalue *sval = m_map.get (reg_binding);
1678 : 1398801 : if (sval)
1679 : : {
1680 : : /* If we have a struct with a single field, then the binding of
1681 : : the field will equal that of the struct, and looking up e.g.
1682 : : PARENT_REG.field within:
1683 : : cluster for PARENT_REG: INIT_VAL(OTHER_REG)
1684 : : will erroneously return INIT_VAL(OTHER_REG), rather than
1685 : : SUB_VALUE(INIT_VAL(OTHER_REG), FIELD) == INIT_VAL(OTHER_REG.FIELD).
1686 : : Fix this issue by iterating upwards whilst the bindings are equal,
1687 : : expressing the lookups as subvalues.
1688 : : We have to gather a list of subregion accesses, then walk it
1689 : : in reverse to get the subvalues. */
1690 : 1093604 : auto_vec<const region *> regions;
1691 : 1103268 : while (const region *parent_reg = reg->get_parent_region ())
1692 : : {
1693 : 1103268 : const binding_key *parent_reg_binding
1694 : 1103268 : = binding_key::make (mgr, parent_reg);
1695 : 1103268 : if (parent_reg_binding == reg_binding
1696 : 12317 : && sval->get_type ()
1697 : 12305 : && reg->get_type ()
1698 : 1115573 : && sval->get_type () != reg->get_type ())
1699 : : {
1700 : 9664 : regions.safe_push (reg);
1701 : 9664 : reg = parent_reg;
1702 : : }
1703 : : else
1704 : : break;
1705 : 9664 : }
1706 : 1093604 : if (sval->get_type ()
1707 : 1084566 : && reg->get_type ()
1708 : 2177348 : && sval->get_type () == reg->get_type ())
1709 : : {
1710 : 902958 : unsigned i;
1711 : 902958 : const region *iter_reg;
1712 : 1120983 : FOR_EACH_VEC_ELT_REVERSE (regions, i, iter_reg)
1713 : : {
1714 : 9159 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
1715 : 9159 : sval = rmm_mgr->get_or_create_sub_svalue (iter_reg->get_type (),
1716 : : sval, iter_reg);
1717 : : }
1718 : : }
1719 : 1093604 : }
1720 : : return sval;
1721 : : }
1722 : :
1723 : : /* Get any SVAL bound to REG within this cluster,
1724 : : either directly for REG, or recursively checking for bindings within
1725 : : parent regions and extracting subvalues if need be. */
1726 : :
1727 : : const svalue *
1728 : 1398801 : binding_cluster::get_binding_recursive (store_manager *mgr,
1729 : : const region *reg) const
1730 : : {
1731 : 1398801 : if (const svalue *sval = get_binding (mgr, reg))
1732 : : return sval;
1733 : 305197 : if (reg != m_base_region)
1734 : 178766 : if (const region *parent_reg = reg->get_parent_region ())
1735 : 357532 : if (const svalue *parent_sval
1736 : 178766 : = get_binding_recursive (mgr, parent_reg))
1737 : : {
1738 : : /* Extract child svalue from parent svalue. */
1739 : 53467 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
1740 : 53467 : return rmm_mgr->get_or_create_sub_svalue (reg->get_type (),
1741 : 53467 : parent_sval, reg);
1742 : : }
1743 : : return NULL;
1744 : : }
1745 : :
1746 : : /* Get any value bound for REG within this cluster. */
1747 : :
1748 : : const svalue *
1749 : 1220035 : binding_cluster::get_any_binding (store_manager *mgr,
1750 : : const region *reg) const
1751 : : {
1752 : : /* Look for a direct binding. */
1753 : 2440070 : if (const svalue *direct_sval
1754 : 1220035 : = get_binding_recursive (mgr, reg))
1755 : : return direct_sval;
1756 : :
1757 : : /* If we had a write to a cluster of unknown size, we might
1758 : : have a self-binding of the whole base region with an svalue,
1759 : : where the base region is symbolic.
1760 : : Handle such cases by returning sub_svalue instances. */
1761 : 126431 : if (const svalue *cluster_sval = maybe_get_simple_value (mgr))
1762 : : {
1763 : : /* Extract child svalue from parent svalue. */
1764 : 0 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
1765 : 0 : return rmm_mgr->get_or_create_sub_svalue (reg->get_type (),
1766 : 0 : cluster_sval, reg);
1767 : : }
1768 : :
1769 : : /* If this cluster has been touched by a symbolic write, then the content
1770 : : of any subregion not currently specifically bound is "UNKNOWN". */
1771 : 126431 : if (m_touched)
1772 : : {
1773 : 4522 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
1774 : 4522 : return rmm_mgr->get_or_create_unknown_svalue (reg->get_type ());
1775 : : }
1776 : :
1777 : : /* Alternatively, if this is a symbolic read and the cluster has any bindings,
1778 : : then we don't know if we're reading those values or not, so the result
1779 : : is also "UNKNOWN". */
1780 : 121909 : if (reg->get_offset (mgr->get_svalue_manager ()).symbolic_p ()
1781 : 121909 : && m_map.elements () > 0)
1782 : : {
1783 : 583 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
1784 : 583 : return rmm_mgr->get_or_create_unknown_svalue (reg->get_type ());
1785 : : }
1786 : :
1787 : 121326 : if (const svalue *compound_sval = maybe_get_compound_binding (mgr, reg))
1788 : : return compound_sval;
1789 : :
1790 : : /* Otherwise, the initial value, or uninitialized. */
1791 : : return NULL;
1792 : : }
1793 : :
1794 : : /* Attempt to get a compound_svalue for the bindings within the cluster
1795 : : affecting REG (which could be the base region itself).
1796 : :
1797 : : Create a compound_svalue with the subset of bindings the affect REG,
1798 : : offsetting them so that the offsets are relative to the start of REG
1799 : : within the cluster.
1800 : :
1801 : : For example, REG could be one element within an array of structs.
1802 : :
1803 : : Return the resulting compound_svalue, or NULL if there's a problem. */
1804 : :
1805 : : const svalue *
1806 : 121326 : binding_cluster::maybe_get_compound_binding (store_manager *mgr,
1807 : : const region *reg) const
1808 : : {
1809 : 121326 : region_offset cluster_offset
1810 : 121326 : = m_base_region->get_offset (mgr->get_svalue_manager ());
1811 : 121326 : if (cluster_offset.symbolic_p ())
1812 : : return NULL;
1813 : 121326 : region_offset reg_offset = reg->get_offset (mgr->get_svalue_manager ());
1814 : 121326 : if (reg_offset.symbolic_p ())
1815 : : return NULL;
1816 : :
1817 : 96768 : if (reg->empty_p ())
1818 : : return NULL;
1819 : :
1820 : 96768 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
1821 : :
1822 : : /* We will a build the result map in two parts:
1823 : : (a) result_map, holding the concrete keys from this cluster,
1824 : :
1825 : : (b) default_map, holding the initial values for the region
1826 : : (e.g. uninitialized, initializer values, or zero), unless this
1827 : : cluster has been touched.
1828 : :
1829 : : We will populate (a), and as we do, clobber (b), trimming and
1830 : : splitting its bindings as necessary.
1831 : : Finally, we will merge (b) into (a), giving a concrete map
1832 : : that merges both the initial values and the bound values from
1833 : : the binding_cluster.
1834 : : Doing it this way reduces N for the O(N^2) intersection-finding,
1835 : : perhaps we should have a spatial-organized data structure for
1836 : : concrete keys, though. */
1837 : :
1838 : 96768 : binding_map result_map;
1839 : 96768 : binding_map default_map;
1840 : :
1841 : : /* Set up default values in default_map. */
1842 : 96768 : const svalue *default_sval;
1843 : 96768 : if (m_touched)
1844 : 0 : default_sval = sval_mgr->get_or_create_unknown_svalue (reg->get_type ());
1845 : : else
1846 : 96768 : default_sval = sval_mgr->get_or_create_initial_value (reg);
1847 : 96768 : const binding_key *default_key = binding_key::make (mgr, reg);
1848 : :
1849 : : /* Express the bit-range of the default key for REG relative to REG,
1850 : : rather than to the base region. */
1851 : 96768 : const concrete_binding *concrete_default_key
1852 : 96768 : = default_key->dyn_cast_concrete_binding ();
1853 : 96768 : if (!concrete_default_key)
1854 : : return nullptr;
1855 : 95877 : const concrete_binding *default_key_relative_to_reg
1856 : 95877 : = mgr->get_concrete_binding (0, concrete_default_key->get_size_in_bits ());
1857 : 95877 : default_map.put (default_key_relative_to_reg, default_sval);
1858 : :
1859 : 317499 : for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
1860 : : {
1861 : 123701 : const binding_key *key = (*iter).first;
1862 : 123701 : const svalue *sval = (*iter).second;
1863 : :
1864 : 247402 : if (const concrete_binding *concrete_key
1865 : 123701 : = key->dyn_cast_concrete_binding ())
1866 : : {
1867 : 123701 : const bit_range &bound_range = concrete_key->get_bit_range ();
1868 : :
1869 : 123701 : bit_size_t reg_bit_size;
1870 : 123701 : if (!reg->get_bit_size (®_bit_size))
1871 : 12890 : return NULL;
1872 : :
1873 : 123701 : bit_range reg_range (reg_offset.get_bit_offset (),
1874 : 123701 : reg_bit_size);
1875 : :
1876 : : /* Skip bindings that are outside the bit range of REG. */
1877 : 123701 : if (!bound_range.intersects_p (reg_range))
1878 : 96587 : continue;
1879 : :
1880 : : /* We shouldn't have an exact match; that should have been
1881 : : handled already. */
1882 : 27114 : gcc_assert (!(reg_range == bound_range));
1883 : :
1884 : 27114 : bit_range subrange (0, 0);
1885 : 27114 : if (reg_range.contains_p (bound_range, &subrange))
1886 : : {
1887 : : /* We have a bound range fully within REG.
1888 : : Add it to map, offsetting accordingly. */
1889 : :
1890 : : /* Get offset of KEY relative to REG, rather than to
1891 : : the cluster. */
1892 : 14148 : const concrete_binding *offset_concrete_key
1893 : 14148 : = mgr->get_concrete_binding (subrange);
1894 : 14148 : result_map.put (offset_concrete_key, sval);
1895 : :
1896 : : /* Clobber default_map, removing/trimming/spliting where
1897 : : it overlaps with offset_concrete_key. */
1898 : 14148 : default_map.remove_overlapping_bindings (mgr,
1899 : : offset_concrete_key,
1900 : : NULL, NULL, false);
1901 : : }
1902 : 12966 : else if (bound_range.contains_p (reg_range, &subrange))
1903 : : {
1904 : : /* REG is fully within the bound range, but
1905 : : is not equal to it; we're extracting a subvalue. */
1906 : 12890 : return sval->extract_bit_range (reg->get_type (),
1907 : : subrange,
1908 : 12890 : mgr->get_svalue_manager ());
1909 : : }
1910 : : else
1911 : : {
1912 : : /* REG and the bound range partially overlap. */
1913 : 76 : bit_range reg_subrange (0, 0);
1914 : 76 : bit_range bound_subrange (0, 0);
1915 : 76 : reg_range.intersects_p (bound_range,
1916 : : ®_subrange, &bound_subrange);
1917 : :
1918 : : /* Get the bits from the bound value for the bits at the
1919 : : intersection (relative to the bound value). */
1920 : 76 : const svalue *overlap_sval
1921 : 76 : = sval->extract_bit_range (NULL_TREE,
1922 : : bound_subrange,
1923 : : mgr->get_svalue_manager ());
1924 : :
1925 : : /* Get key for overlap, relative to the REG. */
1926 : 76 : const concrete_binding *overlap_concrete_key
1927 : 76 : = mgr->get_concrete_binding (reg_subrange);
1928 : 76 : result_map.put (overlap_concrete_key, overlap_sval);
1929 : :
1930 : : /* Clobber default_map, removing/trimming/spliting where
1931 : : it overlaps with overlap_concrete_key. */
1932 : 76 : default_map.remove_overlapping_bindings (mgr,
1933 : : overlap_concrete_key,
1934 : : NULL, NULL, false);
1935 : : }
1936 : : }
1937 : : else
1938 : : /* Can't handle symbolic bindings. */
1939 : : return NULL;
1940 : : }
1941 : :
1942 : 82987 : if (result_map.elements () == 0)
1943 : : return NULL;
1944 : :
1945 : : /* Merge any bindings from default_map into result_map. */
1946 : 5752 : for (auto iter : default_map)
1947 : : {
1948 : 368 : const binding_key *key = iter.first;
1949 : 368 : const svalue *sval = iter.second;
1950 : 368 : result_map.put (key, sval);
1951 : : }
1952 : :
1953 : 5384 : return sval_mgr->get_or_create_compound_svalue (reg->get_type (), result_map);
1954 : 96768 : }
1955 : :
1956 : : /* Remove, truncate, and/or split any bindings within this map that
1957 : : could overlap REG.
1958 : :
1959 : : If REG's base region or this cluster is symbolic and they're different
1960 : : base regions, then remove everything in this cluster's map, on the
1961 : : grounds that REG could be referring to the same memory as anything
1962 : : in the map.
1963 : :
1964 : : If UNCERTAINTY is non-NULL, use it to record any svalues that
1965 : : were removed, as being maybe-bound.
1966 : :
1967 : : If MAYBE_LIVE_VALUES is non-NULL, use it to record any svalues that
1968 : : were removed, as being maybe-live. */
1969 : :
1970 : : void
1971 : 89056 : binding_cluster::remove_overlapping_bindings (store_manager *mgr,
1972 : : const region *reg,
1973 : : uncertainty_t *uncertainty,
1974 : : svalue_set *maybe_live_values)
1975 : : {
1976 : 89056 : if (reg->empty_p ())
1977 : : return;
1978 : 89056 : const binding_key *reg_binding = binding_key::make (mgr, reg);
1979 : :
1980 : 89056 : const region *cluster_base_reg = get_base_region ();
1981 : 89056 : const region *other_base_reg = reg->get_base_region ();
1982 : : /* If at least one of the base regions involved is symbolic, and they're
1983 : : not the same base region, then consider everything in the map as
1984 : : potentially overlapping with reg_binding (even if it's a concrete
1985 : : binding and things in the map are concrete - they could be referring
1986 : : to the same memory when the symbolic base regions are taken into
1987 : : account). */
1988 : 89056 : bool always_overlap = (cluster_base_reg != other_base_reg
1989 : 89056 : && (cluster_base_reg->get_kind () == RK_SYMBOLIC
1990 : 28159 : || other_base_reg->get_kind () == RK_SYMBOLIC));
1991 : 89056 : m_map.remove_overlapping_bindings (mgr, reg_binding, uncertainty,
1992 : : maybe_live_values,
1993 : : always_overlap);
1994 : : }
1995 : :
1996 : : /* Attempt to merge CLUSTER_A and CLUSTER_B into OUT_CLUSTER, using
1997 : : MGR and MERGER.
1998 : : Return true if they can be merged, false otherwise. */
1999 : :
2000 : : bool
2001 : 1137774 : binding_cluster::can_merge_p (const binding_cluster *cluster_a,
2002 : : const binding_cluster *cluster_b,
2003 : : binding_cluster *out_cluster,
2004 : : store *out_store,
2005 : : store_manager *mgr,
2006 : : model_merger *merger)
2007 : : {
2008 : 1137774 : gcc_assert (out_cluster);
2009 : :
2010 : : /* Merge flags ("ESCAPED" and "TOUCHED") by setting the merged flag to
2011 : : true if either of the inputs is true. */
2012 : 1137774 : if ((cluster_a && cluster_a->m_escaped)
2013 : 729005 : || (cluster_b && cluster_b->m_escaped))
2014 : 3880 : out_cluster->m_escaped = true;
2015 : 1137774 : if ((cluster_a && cluster_a->m_touched)
2016 : 792888 : || (cluster_b && cluster_b->m_touched))
2017 : 9397 : out_cluster->m_touched = true;
2018 : :
2019 : : /* At least one of CLUSTER_A and CLUSTER_B are non-NULL, but either
2020 : : could be NULL. Handle these cases. */
2021 : 1137774 : if (cluster_a == NULL)
2022 : : {
2023 : 20847 : gcc_assert (cluster_b != NULL);
2024 : 20847 : gcc_assert (cluster_b->m_base_region == out_cluster->m_base_region);
2025 : 20847 : out_cluster->make_unknown_relative_to (cluster_b, out_store, mgr);
2026 : 20847 : return true;
2027 : : }
2028 : 1116927 : if (cluster_b == NULL)
2029 : : {
2030 : 77090 : gcc_assert (cluster_a != NULL);
2031 : 77090 : gcc_assert (cluster_a->m_base_region == out_cluster->m_base_region);
2032 : 77090 : out_cluster->make_unknown_relative_to (cluster_a, out_store, mgr);
2033 : 77090 : return true;
2034 : : }
2035 : :
2036 : : /* The "both inputs are non-NULL" case. */
2037 : 1039837 : gcc_assert (cluster_a != NULL && cluster_b != NULL);
2038 : 1039837 : gcc_assert (cluster_a->m_base_region == out_cluster->m_base_region);
2039 : 1039837 : gcc_assert (cluster_b->m_base_region == out_cluster->m_base_region);
2040 : :
2041 : 1039837 : hash_set<const binding_key *> keys;
2042 : 2219136 : for (map_t::iterator iter_a = cluster_a->m_map.begin ();
2043 : 3398435 : iter_a != cluster_a->m_map.end (); ++iter_a)
2044 : : {
2045 : 1179299 : const binding_key *key_a = (*iter_a).first;
2046 : 1179299 : keys.add (key_a);
2047 : : }
2048 : 2202529 : for (map_t::iterator iter_b = cluster_b->m_map.begin ();
2049 : 3365221 : iter_b != cluster_b->m_map.end (); ++iter_b)
2050 : : {
2051 : 1162692 : const binding_key *key_b = (*iter_b).first;
2052 : 1162692 : keys.add (key_b);
2053 : : }
2054 : 1039837 : int num_symbolic_keys = 0;
2055 : 1039837 : int num_concrete_keys = 0;
2056 : 2117054 : for (hash_set<const binding_key *>::iterator iter = keys.begin ();
2057 : 3194271 : iter != keys.end (); ++iter)
2058 : : {
2059 : 1162322 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
2060 : 1162322 : const binding_key *key = *iter;
2061 : 1162322 : const svalue *sval_a = cluster_a->get_any_value (key);
2062 : 1162322 : const svalue *sval_b = cluster_b->get_any_value (key);
2063 : :
2064 : 1162322 : if (key->symbolic_p ())
2065 : 110311 : num_symbolic_keys++;
2066 : : else
2067 : 1052011 : num_concrete_keys++;
2068 : :
2069 : 1162322 : if (sval_a == sval_b)
2070 : : {
2071 : 889687 : gcc_assert (sval_a);
2072 : 889687 : out_cluster->m_map.put (key, sval_a);
2073 : 889687 : continue;
2074 : : }
2075 : 272635 : else if (sval_a && sval_b)
2076 : : {
2077 : 524437 : if (const svalue *merged_sval
2078 : 190601 : = sval_a->can_merge_p (sval_b, sval_mgr, merger))
2079 : : {
2080 : 143235 : out_cluster->m_map.put (key, merged_sval);
2081 : 143235 : continue;
2082 : : }
2083 : : /* Merger of the svalues failed. Reject merger of the cluster. */
2084 : 85105 : return false;
2085 : : }
2086 : :
2087 : : /* If we get here, then one cluster binds this key and the other
2088 : : doesn't; merge them as "UNKNOWN". */
2089 : 82034 : gcc_assert (sval_a || sval_b);
2090 : :
2091 : 82034 : const svalue *bound_sval = sval_a ? sval_a : sval_b;
2092 : 82034 : tree type = bound_sval->get_type ();
2093 : 82034 : const svalue *unknown_sval
2094 : 82034 : = mgr->get_svalue_manager ()->get_or_create_unknown_svalue (type);
2095 : :
2096 : : /* ...but reject the merger if this sval shouldn't be mergeable
2097 : : (e.g. reject merging svalues that have non-purgable sm-state,
2098 : : to avoid falsely reporting memory leaks by merging them
2099 : : with something else). */
2100 : 82034 : if (!bound_sval->can_merge_p (unknown_sval, sval_mgr, merger))
2101 : : return false;
2102 : :
2103 : 44295 : out_cluster->m_map.put (key, unknown_sval);
2104 : : }
2105 : :
2106 : : /* We can only have at most one symbolic key per cluster,
2107 : : and if we do, we can't have any concrete keys.
2108 : : If this happens, mark the cluster as touched, with no keys. */
2109 : 954732 : if (num_symbolic_keys >= 2
2110 : 954242 : || (num_concrete_keys > 0 && num_symbolic_keys > 0))
2111 : : {
2112 : 1679 : out_cluster->m_touched = true;
2113 : 1041516 : out_cluster->m_map.empty ();
2114 : : }
2115 : :
2116 : : /* We don't handle other kinds of overlaps yet. */
2117 : :
2118 : : return true;
2119 : 1039837 : }
2120 : :
2121 : : /* Update this cluster to reflect an attempt to merge OTHER where there
2122 : : is no other cluster to merge with, and so we're notionally merging the
2123 : : bound values in OTHER with the initial value of the relevant regions.
2124 : :
2125 : : Any bound keys in OTHER should be bound to unknown in this. */
2126 : :
2127 : : void
2128 : 97937 : binding_cluster::make_unknown_relative_to (const binding_cluster *other,
2129 : : store *out_store,
2130 : : store_manager *mgr)
2131 : : {
2132 : 197740 : for (map_t::iterator iter = other->m_map.begin ();
2133 : 297543 : iter != other->m_map.end (); ++iter)
2134 : : {
2135 : 99803 : const binding_key *iter_key = (*iter).first;
2136 : 99803 : const svalue *iter_sval = (*iter).second;
2137 : 99803 : const svalue *unknown_sval
2138 : : = mgr->get_svalue_manager ()->get_or_create_unknown_svalue
2139 : 99803 : (iter_sval->get_type ());
2140 : 99803 : m_map.put (iter_key, unknown_sval);
2141 : :
2142 : : /* For any pointers in OTHER, the merger means that the
2143 : : concrete pointer becomes an unknown value, which could
2144 : : show up as a false report of a leak when considering what
2145 : : pointers are live before vs after.
2146 : : Avoid this by marking the base regions they point to as having
2147 : : escaped. */
2148 : 199606 : if (const region_svalue *region_sval
2149 : 99803 : = iter_sval->dyn_cast_region_svalue ())
2150 : : {
2151 : 5731 : const region *base_reg
2152 : 5731 : = region_sval->get_pointee ()->get_base_region ();
2153 : 5731 : if (base_reg->tracked_p ()
2154 : 5731 : && !base_reg->symbolic_for_unknown_ptr_p ())
2155 : : {
2156 : 5692 : binding_cluster *c = out_store->get_or_create_cluster (base_reg);
2157 : 5692 : c->mark_as_escaped ();
2158 : : }
2159 : : }
2160 : : }
2161 : 97937 : }
2162 : :
2163 : : /* Mark this cluster as having escaped. */
2164 : :
2165 : : void
2166 : 45166 : binding_cluster::mark_as_escaped ()
2167 : : {
2168 : 45166 : m_escaped = true;
2169 : 45166 : }
2170 : :
2171 : : /* If this cluster has escaped (by this call, or by an earlier one, or
2172 : : by being an external param), then unbind all values and mark it
2173 : : as "touched", so that it has a conjured value, rather than an
2174 : : initial_svalue.
2175 : : Use P to purge state involving conjured_svalues. */
2176 : :
2177 : : void
2178 : 163813 : binding_cluster::on_unknown_fncall (const gcall *call,
2179 : : store_manager *mgr,
2180 : : const conjured_purge &p)
2181 : : {
2182 : 163813 : if (m_escaped)
2183 : : {
2184 : 27243 : m_map.empty ();
2185 : :
2186 : 27243 : if (!m_base_region->empty_p ())
2187 : : {
2188 : : /* Bind it to a new "conjured" value using CALL. */
2189 : 27243 : const svalue *sval
2190 : : = mgr->get_svalue_manager ()->get_or_create_conjured_svalue
2191 : 27243 : (m_base_region->get_type (), call, m_base_region, p);
2192 : 27243 : bind (mgr, m_base_region, sval);
2193 : : }
2194 : :
2195 : 27243 : m_touched = true;
2196 : : }
2197 : 163813 : }
2198 : :
2199 : : /* Mark this cluster as having been clobbered by STMT.
2200 : : Use P to purge state involving conjured_svalues. */
2201 : :
2202 : : void
2203 : 522 : binding_cluster::on_asm (const gasm *stmt,
2204 : : store_manager *mgr,
2205 : : const conjured_purge &p)
2206 : : {
2207 : 522 : m_map.empty ();
2208 : :
2209 : : /* Bind it to a new "conjured" value using CALL. */
2210 : 522 : const svalue *sval
2211 : : = mgr->get_svalue_manager ()->get_or_create_conjured_svalue
2212 : 522 : (m_base_region->get_type (), stmt, m_base_region, p);
2213 : 522 : bind (mgr, m_base_region, sval);
2214 : :
2215 : 522 : m_touched = true;
2216 : 522 : }
2217 : :
2218 : : /* Return true if this cluster has escaped. */
2219 : :
2220 : : bool
2221 : 8275144 : binding_cluster::escaped_p () const
2222 : : {
2223 : : /* Consider the "errno" region to always have escaped. */
2224 : 8275144 : if (m_base_region->get_kind () == RK_ERRNO)
2225 : : return true;
2226 : 8244337 : return m_escaped;
2227 : : }
2228 : :
2229 : : /* Return true if this binding_cluster has no information
2230 : : i.e. if there are no bindings, and it hasn't been marked as having
2231 : : escaped, or touched symbolically. */
2232 : :
2233 : : bool
2234 : 183643 : binding_cluster::redundant_p () const
2235 : : {
2236 : 183643 : return (m_map.elements () == 0
2237 : 175926 : && !m_escaped
2238 : 358498 : && !m_touched);
2239 : : }
2240 : :
2241 : : /* Add PV to OUT_PVS, casting it to TYPE if it is not already of that type. */
2242 : :
2243 : : static void
2244 : 8348 : append_pathvar_with_type (path_var pv,
2245 : : tree type,
2246 : : auto_vec<path_var> *out_pvs)
2247 : : {
2248 : 8348 : gcc_assert (pv.m_tree);
2249 : :
2250 : 8348 : if (TREE_TYPE (pv.m_tree) != type)
2251 : 509 : pv.m_tree = build1 (NOP_EXPR, type, pv.m_tree);
2252 : :
2253 : 8348 : out_pvs->safe_push (pv);
2254 : 8348 : }
2255 : :
2256 : : /* Find representative path_vars for SVAL within this binding of BASE_REG,
2257 : : appending the results to OUT_PVS. */
2258 : :
2259 : : void
2260 : 61002 : binding_cluster::get_representative_path_vars (const region_model *model,
2261 : : svalue_set *visited,
2262 : : const region *base_reg,
2263 : : const svalue *sval,
2264 : : logger *logger,
2265 : : auto_vec<path_var> *out_pvs)
2266 : : const
2267 : : {
2268 : 61002 : sval = simplify_for_binding (sval);
2269 : :
2270 : 175932 : for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
2271 : : {
2272 : 57465 : const binding_key *key = (*iter).first;
2273 : 57465 : const svalue *bound_sval = (*iter).second;
2274 : 57465 : if (bound_sval == sval)
2275 : : {
2276 : 17528 : if (const concrete_binding *ckey
2277 : 8764 : = key->dyn_cast_concrete_binding ())
2278 : : {
2279 : 8700 : auto_vec <const region *> subregions;
2280 : 8700 : base_reg->get_subregions_for_binding
2281 : 8700 : (model->get_manager (),
2282 : : ckey->get_start_bit_offset (),
2283 : : ckey->get_size_in_bits (),
2284 : : sval->get_type (),
2285 : : &subregions);
2286 : 8700 : unsigned i;
2287 : 8700 : const region *subregion;
2288 : 25284 : FOR_EACH_VEC_ELT (subregions, i, subregion)
2289 : : {
2290 : 16584 : if (path_var pv
2291 : 8292 : = model->get_representative_path_var (subregion,
2292 : : visited,
2293 : 8292 : logger))
2294 : 8284 : append_pathvar_with_type (pv, sval->get_type (), out_pvs);
2295 : : }
2296 : 8700 : }
2297 : : else
2298 : : {
2299 : 64 : const symbolic_binding *skey = (const symbolic_binding *)key;
2300 : 128 : if (path_var pv
2301 : 64 : = model->get_representative_path_var (skey->get_region (),
2302 : : visited,
2303 : 64 : logger))
2304 : 64 : append_pathvar_with_type (pv, sval->get_type (), out_pvs);
2305 : : }
2306 : : }
2307 : : }
2308 : 61002 : }
2309 : :
2310 : : /* Get any svalue bound to KEY, or NULL. */
2311 : :
2312 : : const svalue *
2313 : 2494422 : binding_cluster::get_any_value (const binding_key *key) const
2314 : : {
2315 : 2494422 : return m_map.get (key);
2316 : : }
2317 : :
2318 : : /* If this cluster has a single direct binding for the whole of the region,
2319 : : return it.
2320 : : For use in simplifying dumps. */
2321 : :
2322 : : const svalue *
2323 : 361219 : binding_cluster::maybe_get_simple_value (store_manager *mgr) const
2324 : : {
2325 : : /* Fail gracefully if MGR is NULL to make it easier to dump store
2326 : : instances in the debugger. */
2327 : 361219 : if (mgr == NULL)
2328 : : return NULL;
2329 : :
2330 : 361219 : if (m_map.elements () != 1)
2331 : : return NULL;
2332 : :
2333 : 169778 : if (m_base_region->empty_p ())
2334 : : return NULL;
2335 : :
2336 : 169778 : const binding_key *key = binding_key::make (mgr, m_base_region);
2337 : 169778 : return get_any_value (key);
2338 : : }
2339 : :
2340 : : /* class store_manager. */
2341 : :
2342 : : logger *
2343 : 329258 : store_manager::get_logger () const
2344 : : {
2345 : 329258 : return m_mgr->get_logger ();
2346 : : }
2347 : :
2348 : : /* binding consolidation. */
2349 : :
2350 : : const concrete_binding *
2351 : 2295157 : store_manager::get_concrete_binding (bit_offset_t start_bit_offset,
2352 : : bit_offset_t size_in_bits)
2353 : : {
2354 : 2295157 : concrete_binding b (start_bit_offset, size_in_bits);
2355 : 4578770 : if (concrete_binding *existing = m_concrete_binding_key_mgr.get (b))
2356 : : return existing;
2357 : :
2358 : 11544 : concrete_binding *to_save = new concrete_binding (b);
2359 : 11544 : m_concrete_binding_key_mgr.put (b, to_save);
2360 : 11544 : return to_save;
2361 : 2295157 : }
2362 : :
2363 : : const symbolic_binding *
2364 : 1288641 : store_manager::get_symbolic_binding (const region *reg)
2365 : : {
2366 : 1288641 : symbolic_binding b (reg);
2367 : 2559152 : if (symbolic_binding *existing = m_symbolic_binding_key_mgr.get (b))
2368 : : return existing;
2369 : :
2370 : 18130 : symbolic_binding *to_save = new symbolic_binding (b);
2371 : 18130 : m_symbolic_binding_key_mgr.put (b, to_save);
2372 : 18130 : return to_save;
2373 : 1288641 : }
2374 : :
2375 : : /* class store. */
2376 : :
2377 : : /* store's default ctor. */
2378 : :
2379 : 338513 : store::store ()
2380 : 338513 : : m_called_unknown_fn (false)
2381 : : {
2382 : 338513 : }
2383 : :
2384 : : /* store's copy ctor. */
2385 : :
2386 : 3527887 : store::store (const store &other)
2387 : 3527887 : : m_cluster_map (other.m_cluster_map.elements ()),
2388 : 3527887 : m_called_unknown_fn (other.m_called_unknown_fn)
2389 : : {
2390 : 3527887 : for (cluster_map_t::iterator iter = other.m_cluster_map.begin ();
2391 : 27259736 : iter != other.m_cluster_map.end ();
2392 : 23731849 : ++iter)
2393 : : {
2394 : 23731849 : const region *reg = (*iter).first;
2395 : 0 : gcc_assert (reg);
2396 : 23731849 : binding_cluster *c = (*iter).second;
2397 : 23731849 : gcc_assert (c);
2398 : 23731849 : m_cluster_map.put (reg, new binding_cluster (*c));
2399 : : }
2400 : 3527887 : }
2401 : :
2402 : : /* store's dtor. */
2403 : :
2404 : 3866400 : store::~store ()
2405 : : {
2406 : 28832048 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2407 : 28832048 : iter != m_cluster_map.end ();
2408 : 24965648 : ++iter)
2409 : 24965648 : delete (*iter).second;
2410 : 3866400 : }
2411 : :
2412 : : /* store's assignment operator. */
2413 : :
2414 : : store &
2415 : 17533 : store::operator= (const store &other)
2416 : : {
2417 : : /* Delete existing cluster map. */
2418 : 132479 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2419 : 132479 : iter != m_cluster_map.end ();
2420 : 114946 : ++iter)
2421 : 229892 : delete (*iter).second;
2422 : 17533 : m_cluster_map.empty ();
2423 : :
2424 : 17533 : m_called_unknown_fn = other.m_called_unknown_fn;
2425 : :
2426 : 17533 : for (cluster_map_t::iterator iter = other.m_cluster_map.begin ();
2427 : 145737 : iter != other.m_cluster_map.end ();
2428 : 128204 : ++iter)
2429 : : {
2430 : 128204 : const region *reg = (*iter).first;
2431 : 128204 : gcc_assert (reg);
2432 : 128204 : binding_cluster *c = (*iter).second;
2433 : 128204 : gcc_assert (c);
2434 : 128204 : m_cluster_map.put (reg, new binding_cluster (*c));
2435 : : }
2436 : 17533 : return *this;
2437 : : }
2438 : :
2439 : : /* store's equality operator. */
2440 : :
2441 : : bool
2442 : 431202 : store::operator== (const store &other) const
2443 : : {
2444 : 431202 : if (m_called_unknown_fn != other.m_called_unknown_fn)
2445 : : return false;
2446 : :
2447 : 428275 : if (m_cluster_map.elements () != other.m_cluster_map.elements ())
2448 : : return false;
2449 : :
2450 : 2313051 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2451 : 2313051 : iter != m_cluster_map.end ();
2452 : 1907955 : ++iter)
2453 : : {
2454 : 1941228 : const region *reg = (*iter).first;
2455 : 1941228 : binding_cluster *c = (*iter).second;
2456 : 1941228 : binding_cluster **other_slot
2457 : 1941228 : = const_cast <cluster_map_t &> (other.m_cluster_map).get (reg);
2458 : 1941228 : if (other_slot == NULL)
2459 : 33273 : return false;
2460 : 1940155 : if (*c != **other_slot)
2461 : : return false;
2462 : : }
2463 : :
2464 : 371823 : gcc_checking_assert (hash () == other.hash ());
2465 : :
2466 : : return true;
2467 : : }
2468 : :
2469 : : /* Get a hash value for this store. */
2470 : :
2471 : : hashval_t
2472 : 1908673 : store::hash () const
2473 : : {
2474 : 1908673 : hashval_t result = 0;
2475 : 1908673 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2476 : 11674912 : iter != m_cluster_map.end ();
2477 : 9766239 : ++iter)
2478 : 9766239 : result ^= (*iter).second->hash ();
2479 : 1908673 : return result;
2480 : : }
2481 : :
2482 : : /* Populate OUT with a sorted list of parent regions for the regions in IN,
2483 : : removing duplicate parents. */
2484 : :
2485 : : static void
2486 : 1960 : get_sorted_parent_regions (auto_vec<const region *> *out,
2487 : : auto_vec<const region *> &in)
2488 : : {
2489 : : /* Get the set of parent regions. */
2490 : 1960 : hash_set<const region *> parent_regions;
2491 : 1960 : const region *iter_reg;
2492 : 1960 : unsigned i;
2493 : 9843 : FOR_EACH_VEC_ELT (in, i, iter_reg)
2494 : : {
2495 : 7883 : const region *parent_reg = iter_reg->get_parent_region ();
2496 : 7883 : gcc_assert (parent_reg);
2497 : 7883 : parent_regions.add (parent_reg);
2498 : : }
2499 : :
2500 : : /* Write to OUT. */
2501 : 1960 : for (hash_set<const region *>::iterator iter = parent_regions.begin();
2502 : 10214 : iter != parent_regions.end(); ++iter)
2503 : 4127 : out->safe_push (*iter);
2504 : :
2505 : : /* Sort OUT. */
2506 : 3747 : out->qsort (region::cmp_ptr_ptr);
2507 : 1960 : }
2508 : :
2509 : : /* Dump a representation of this store to PP, using SIMPLE to control how
2510 : : svalues and regions are printed.
2511 : : MGR is used for simplifying dumps if non-NULL, but can also be NULL
2512 : : (to make it easier to use from the debugger). */
2513 : :
2514 : : void
2515 : 1952 : store::dump_to_pp (pretty_printer *pp, bool simple, bool multiline,
2516 : : store_manager *mgr) const
2517 : : {
2518 : : /* Sort into some deterministic order. */
2519 : 1952 : auto_vec<const region *> base_regions;
2520 : 9835 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2521 : 17718 : iter != m_cluster_map.end (); ++iter)
2522 : : {
2523 : 7883 : const region *base_reg = (*iter).first;
2524 : 7883 : base_regions.safe_push (base_reg);
2525 : : }
2526 : 1952 : base_regions.qsort (region::cmp_ptr_ptr);
2527 : :
2528 : : /* Gather clusters, organize by parent region, so that we can group
2529 : : together locals, globals, etc. */
2530 : 1952 : auto_vec<const region *> parent_regions;
2531 : 1952 : get_sorted_parent_regions (&parent_regions, base_regions);
2532 : :
2533 : 1952 : const region *parent_reg;
2534 : 1952 : unsigned i;
2535 : 6079 : FOR_EACH_VEC_ELT (parent_regions, i, parent_reg)
2536 : : {
2537 : 4127 : gcc_assert (parent_reg);
2538 : 4127 : pp_string (pp, "clusters within ");
2539 : 4127 : parent_reg->dump_to_pp (pp, simple);
2540 : 4127 : if (multiline)
2541 : 1640 : pp_newline (pp);
2542 : : else
2543 : 2487 : pp_string (pp, " {");
2544 : :
2545 : : const region *base_reg;
2546 : : unsigned j;
2547 : 23791 : FOR_EACH_VEC_ELT (base_regions, j, base_reg)
2548 : : {
2549 : : /* This is O(N * M), but N ought to be small. */
2550 : 19664 : if (base_reg->get_parent_region () != parent_reg)
2551 : 11781 : continue;
2552 : 7883 : binding_cluster *cluster
2553 : 7883 : = *const_cast<cluster_map_t &> (m_cluster_map).get (base_reg);
2554 : 7883 : if (!multiline)
2555 : : {
2556 : 4151 : if (j > 0)
2557 : 3152 : pp_string (pp, ", ");
2558 : : }
2559 : 7883 : if (const svalue *sval = cluster->maybe_get_simple_value (mgr))
2560 : : {
2561 : : /* Special-case to simplify dumps for the common case where
2562 : : we just have one value directly bound to the whole of a
2563 : : region. */
2564 : 5710 : if (multiline)
2565 : : {
2566 : 2308 : pp_string (pp, " cluster for: ");
2567 : 2308 : base_reg->dump_to_pp (pp, simple);
2568 : 2308 : pp_string (pp, ": ");
2569 : 2308 : sval->dump_to_pp (pp, simple);
2570 : 2308 : if (cluster->escaped_p ())
2571 : 144 : pp_string (pp, " (ESCAPED)");
2572 : 2308 : if (cluster->touched_p ())
2573 : 0 : pp_string (pp, " (TOUCHED)");
2574 : 2308 : pp_newline (pp);
2575 : : }
2576 : : else
2577 : : {
2578 : 3402 : pp_string (pp, "region: {");
2579 : 3402 : base_reg->dump_to_pp (pp, simple);
2580 : 3402 : pp_string (pp, ", value: ");
2581 : 3402 : sval->dump_to_pp (pp, simple);
2582 : 3402 : if (cluster->escaped_p ())
2583 : 813 : pp_string (pp, " (ESCAPED)");
2584 : 3402 : if (cluster->touched_p ())
2585 : 813 : pp_string (pp, " (TOUCHED)");
2586 : 3402 : pp_string (pp, "}");
2587 : : }
2588 : : }
2589 : 2173 : else if (multiline)
2590 : : {
2591 : 1424 : pp_string (pp, " cluster for: ");
2592 : 1424 : base_reg->dump_to_pp (pp, simple);
2593 : 1424 : pp_newline (pp);
2594 : 1424 : cluster->dump_to_pp (pp, simple, multiline);
2595 : : }
2596 : : else
2597 : : {
2598 : 749 : pp_string (pp, "base region: {");
2599 : 749 : base_reg->dump_to_pp (pp, simple);
2600 : 749 : pp_string (pp, "} has cluster: {");
2601 : 749 : cluster->dump_to_pp (pp, simple, multiline);
2602 : 749 : pp_string (pp, "}");
2603 : : }
2604 : : }
2605 : 4127 : if (!multiline)
2606 : 2487 : pp_string (pp, "}");
2607 : : }
2608 : 1952 : pp_printf (pp, "m_called_unknown_fn: %s",
2609 : 1952 : m_called_unknown_fn ? "TRUE" : "FALSE");
2610 : 1952 : if (multiline)
2611 : 856 : pp_newline (pp);
2612 : 1952 : }
2613 : :
2614 : : /* Dump a multiline representation of this store to stderr. */
2615 : :
2616 : : DEBUG_FUNCTION void
2617 : 0 : store::dump (bool simple) const
2618 : : {
2619 : 0 : tree_dump_pretty_printer pp (stderr);
2620 : 0 : dump_to_pp (&pp, simple, true, NULL);
2621 : 0 : pp_newline (&pp);
2622 : 0 : }
2623 : :
2624 : : /* Assert that this object is valid. */
2625 : :
2626 : : void
2627 : 1644747 : store::validate () const
2628 : : {
2629 : 10474717 : for (auto iter : m_cluster_map)
2630 : 8829970 : iter.second->validate ();
2631 : 1644747 : }
2632 : :
2633 : : /* Return a new json::object of the form
2634 : : {PARENT_REGION_DESC: {BASE_REGION_DESC: object for binding_map,
2635 : : ... for each cluster within parent region},
2636 : : ...for each parent region,
2637 : : "called_unknown_fn": true/false}. */
2638 : :
2639 : : std::unique_ptr<json::object>
2640 : 4 : store::to_json () const
2641 : : {
2642 : 4 : auto store_obj = ::make_unique<json::object> ();
2643 : :
2644 : : /* Sort into some deterministic order. */
2645 : 4 : auto_vec<const region *> base_regions;
2646 : 4 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2647 : 4 : iter != m_cluster_map.end (); ++iter)
2648 : : {
2649 : 0 : const region *base_reg = (*iter).first;
2650 : 0 : base_regions.safe_push (base_reg);
2651 : : }
2652 : 4 : base_regions.qsort (region::cmp_ptr_ptr);
2653 : :
2654 : : /* Gather clusters, organize by parent region, so that we can group
2655 : : together locals, globals, etc. */
2656 : 4 : auto_vec<const region *> parent_regions;
2657 : 4 : get_sorted_parent_regions (&parent_regions, base_regions);
2658 : :
2659 : 4 : const region *parent_reg;
2660 : 4 : unsigned i;
2661 : 4 : FOR_EACH_VEC_ELT (parent_regions, i, parent_reg)
2662 : : {
2663 : 0 : gcc_assert (parent_reg);
2664 : :
2665 : 0 : auto clusters_in_parent_reg_obj = ::make_unique<json::object> ();
2666 : :
2667 : 0 : const region *base_reg;
2668 : 0 : unsigned j;
2669 : 0 : FOR_EACH_VEC_ELT (base_regions, j, base_reg)
2670 : : {
2671 : : /* This is O(N * M), but N ought to be small. */
2672 : 0 : if (base_reg->get_parent_region () != parent_reg)
2673 : 0 : continue;
2674 : 0 : binding_cluster *cluster
2675 : 0 : = *const_cast<cluster_map_t &> (m_cluster_map).get (base_reg);
2676 : 0 : label_text base_reg_desc = base_reg->get_desc ();
2677 : 0 : clusters_in_parent_reg_obj->set (base_reg_desc.get (),
2678 : 0 : cluster->to_json ());
2679 : 0 : }
2680 : 0 : label_text parent_reg_desc = parent_reg->get_desc ();
2681 : 0 : store_obj->set (parent_reg_desc.get (),
2682 : : std::move (clusters_in_parent_reg_obj));
2683 : 0 : }
2684 : :
2685 : 4 : store_obj->set_bool ("called_unknown_fn", m_called_unknown_fn);
2686 : :
2687 : 4 : return store_obj;
2688 : 4 : }
2689 : :
2690 : : std::unique_ptr<text_art::tree_widget>
2691 : 4 : store::make_dump_widget (const text_art::dump_widget_info &dwi,
2692 : : store_manager *mgr) const
2693 : : {
2694 : 4 : std::unique_ptr<text_art::tree_widget> store_widget
2695 : 4 : (text_art::tree_widget::make (dwi, "Store"));
2696 : :
2697 : 4 : store_widget->add_child
2698 : 8 : (text_art::tree_widget::from_fmt (dwi, nullptr,
2699 : : "m_called_unknown_fn: %s",
2700 : 4 : m_called_unknown_fn ? "true" : "false"));
2701 : :
2702 : : /* Sort into some deterministic order. */
2703 : 4 : auto_vec<const region *> base_regions;
2704 : 4 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2705 : 4 : iter != m_cluster_map.end (); ++iter)
2706 : : {
2707 : 0 : const region *base_reg = (*iter).first;
2708 : 0 : base_regions.safe_push (base_reg);
2709 : : }
2710 : 4 : base_regions.qsort (region::cmp_ptr_ptr);
2711 : :
2712 : : /* Gather clusters, organize by parent region, so that we can group
2713 : : together locals, globals, etc. */
2714 : 4 : auto_vec<const region *> parent_regions;
2715 : 4 : get_sorted_parent_regions (&parent_regions, base_regions);
2716 : :
2717 : 4 : const region *parent_reg;
2718 : 4 : unsigned i;
2719 : 4 : FOR_EACH_VEC_ELT (parent_regions, i, parent_reg)
2720 : : {
2721 : 0 : gcc_assert (parent_reg);
2722 : :
2723 : 0 : pretty_printer the_pp;
2724 : 0 : pretty_printer * const pp = &the_pp;
2725 : 0 : pp_format_decoder (pp) = default_tree_printer;
2726 : 0 : pp_show_color (pp) = true;
2727 : 0 : const bool simple = true;
2728 : :
2729 : 0 : parent_reg->dump_to_pp (pp, simple);
2730 : :
2731 : 0 : std::unique_ptr<text_art::tree_widget> parent_reg_widget
2732 : 0 : (text_art::tree_widget::make (dwi, pp));
2733 : :
2734 : 0 : const region *base_reg;
2735 : 0 : unsigned j;
2736 : 0 : FOR_EACH_VEC_ELT (base_regions, j, base_reg)
2737 : : {
2738 : : /* This is O(N * M), but N ought to be small. */
2739 : 0 : if (base_reg->get_parent_region () != parent_reg)
2740 : 0 : continue;
2741 : 0 : binding_cluster *cluster
2742 : 0 : = *const_cast<cluster_map_t &> (m_cluster_map).get (base_reg);
2743 : 0 : parent_reg_widget->add_child
2744 : 0 : (cluster->make_dump_widget (dwi, mgr));
2745 : : }
2746 : 0 : store_widget->add_child (std::move (parent_reg_widget));
2747 : 0 : }
2748 : :
2749 : 4 : return store_widget;
2750 : 4 : }
2751 : :
2752 : : /* Get any svalue bound to REG, or NULL. */
2753 : :
2754 : : const svalue *
2755 : 3718888 : store::get_any_binding (store_manager *mgr, const region *reg) const
2756 : : {
2757 : 3718888 : const region *base_reg = reg->get_base_region ();
2758 : 3718888 : binding_cluster **cluster_slot
2759 : 3718888 : = const_cast <cluster_map_t &> (m_cluster_map).get (base_reg);
2760 : 3718888 : if (!cluster_slot)
2761 : : return NULL;
2762 : 1219863 : return (*cluster_slot)->get_any_binding (mgr, reg);
2763 : : }
2764 : :
2765 : : /* Set the value of LHS_REG to RHS_SVAL. */
2766 : :
2767 : : void
2768 : 329258 : store::set_value (store_manager *mgr, const region *lhs_reg,
2769 : : const svalue *rhs_sval,
2770 : : uncertainty_t *uncertainty)
2771 : : {
2772 : 329258 : logger *logger = mgr->get_logger ();
2773 : 329258 : LOG_SCOPE (logger);
2774 : :
2775 : 329258 : remove_overlapping_bindings (mgr, lhs_reg, uncertainty);
2776 : :
2777 : 329258 : if (lhs_reg->get_type ())
2778 : 321957 : rhs_sval = simplify_for_binding (rhs_sval);
2779 : : /* ...but if we have no type for the region, retain any cast. */
2780 : :
2781 : 329258 : const region *lhs_base_reg = lhs_reg->get_base_region ();
2782 : 329258 : binding_cluster *lhs_cluster;
2783 : 329258 : if (lhs_base_reg->symbolic_for_unknown_ptr_p ())
2784 : : {
2785 : : /* Reject attempting to bind values into a symbolic region
2786 : : for an unknown ptr; merely invalidate values below. */
2787 : 3394 : lhs_cluster = NULL;
2788 : :
2789 : : /* The LHS of the write is *UNKNOWN. If the RHS is a pointer,
2790 : : then treat the region being pointed to as having escaped. */
2791 : 3394 : if (const region_svalue *ptr_sval = rhs_sval->dyn_cast_region_svalue ())
2792 : : {
2793 : 161 : const region *ptr_dst = ptr_sval->get_pointee ();
2794 : 161 : const region *ptr_base_reg = ptr_dst->get_base_region ();
2795 : 161 : mark_as_escaped (ptr_base_reg);
2796 : : }
2797 : 3394 : if (uncertainty)
2798 : 1571 : uncertainty->on_maybe_bound_sval (rhs_sval);
2799 : : }
2800 : 325864 : else if (lhs_base_reg->tracked_p ())
2801 : : {
2802 : 325785 : lhs_cluster = get_or_create_cluster (lhs_base_reg);
2803 : 325785 : lhs_cluster->bind (mgr, lhs_reg, rhs_sval);
2804 : : }
2805 : : else
2806 : : {
2807 : : /* Reject attempting to bind values into an untracked region;
2808 : : merely invalidate values below. */
2809 : : lhs_cluster = NULL;
2810 : : }
2811 : :
2812 : : /* Bindings to a cluster can affect other clusters if a symbolic
2813 : : base region is involved.
2814 : : Writes to concrete clusters can't affect other concrete clusters,
2815 : : but can affect symbolic clusters.
2816 : : Writes to symbolic clusters can affect both concrete and symbolic
2817 : : clusters.
2818 : : Invalidate our knowledge of other clusters that might have been
2819 : : affected by the write.
2820 : : Gather the set of all svalues that might still be live even if
2821 : : the store doesn't refer to them. */
2822 : 329258 : svalue_set maybe_live_values;
2823 : 4556470 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2824 : 8783682 : iter != m_cluster_map.end (); ++iter)
2825 : : {
2826 : 4227212 : const region *iter_base_reg = (*iter).first;
2827 : 4227212 : binding_cluster *iter_cluster = (*iter).second;
2828 : 4227212 : if (iter_base_reg != lhs_base_reg
2829 : 4227212 : && (lhs_cluster == NULL
2830 : 3845436 : || lhs_cluster->symbolic_p ()
2831 : 3764775 : || iter_cluster->symbolic_p ()))
2832 : : {
2833 : 568656 : tristate t_alias = eval_alias (lhs_base_reg, iter_base_reg);
2834 : 568656 : switch (t_alias.get_value ())
2835 : : {
2836 : 0 : default:
2837 : 0 : gcc_unreachable ();
2838 : :
2839 : 61860 : case tristate::TS_UNKNOWN:
2840 : 61860 : if (logger)
2841 : : {
2842 : 7 : pretty_printer *pp = logger->get_printer ();
2843 : 7 : logger->start_log_line ();
2844 : 7 : logger->log_partial ("possible aliasing of ");
2845 : 7 : iter_base_reg->dump_to_pp (pp, true);
2846 : 7 : logger->log_partial (" when writing SVAL: ");
2847 : 7 : rhs_sval->dump_to_pp (pp, true);
2848 : 7 : logger->log_partial (" to LHS_REG: ");
2849 : 7 : lhs_reg->dump_to_pp (pp, true);
2850 : 7 : logger->end_log_line ();
2851 : : }
2852 : : /* Mark all of iter_cluster's iter_base_reg as unknown,
2853 : : using LHS_REG when considering overlaps, to handle
2854 : : symbolic vs concrete issues. */
2855 : 61860 : iter_cluster->mark_region_as_unknown
2856 : 61860 : (mgr,
2857 : : iter_base_reg, /* reg_to_bind */
2858 : : lhs_reg, /* reg_for_overlap */
2859 : : uncertainty,
2860 : : &maybe_live_values);
2861 : 61860 : break;
2862 : :
2863 : 0 : case tristate::TS_TRUE:
2864 : 0 : gcc_unreachable ();
2865 : : break;
2866 : :
2867 : : case tristate::TS_FALSE:
2868 : : /* If they can't be aliases, then don't invalidate this
2869 : : cluster. */
2870 : : break;
2871 : : }
2872 : : }
2873 : : }
2874 : : /* Given the set of svalues that might still be live, process them
2875 : : (e.g. marking regions as escaped).
2876 : : We do this after the iteration to avoid potentially changing
2877 : : m_cluster_map whilst iterating over it. */
2878 : 329258 : on_maybe_live_values (maybe_live_values);
2879 : 329258 : }
2880 : :
2881 : : /* Determine if BASE_REG_A could be an alias of BASE_REG_B. */
2882 : :
2883 : : tristate
2884 : 569211 : store::eval_alias (const region *base_reg_a,
2885 : : const region *base_reg_b) const
2886 : : {
2887 : : /* SSA names can't alias. */
2888 : 569211 : tree decl_a = base_reg_a->maybe_get_decl ();
2889 : 569211 : if (decl_a && TREE_CODE (decl_a) == SSA_NAME)
2890 : 375028 : return tristate::TS_FALSE;
2891 : 194183 : tree decl_b = base_reg_b->maybe_get_decl ();
2892 : 194183 : if (decl_b && TREE_CODE (decl_b) == SSA_NAME)
2893 : 64826 : return tristate::TS_FALSE;
2894 : :
2895 : : /* Try both ways, for symmetry. */
2896 : 129357 : tristate ts_ab = eval_alias_1 (base_reg_a, base_reg_b);
2897 : 129357 : if (ts_ab.is_false ())
2898 : 23976 : return tristate::TS_FALSE;
2899 : 105381 : tristate ts_ba = eval_alias_1 (base_reg_b, base_reg_a);
2900 : 105381 : if (ts_ba.is_false ())
2901 : 43261 : return tristate::TS_FALSE;
2902 : 62120 : return tristate::TS_UNKNOWN;
2903 : : }
2904 : :
2905 : : /* Half of store::eval_alias; called twice for symmetry. */
2906 : :
2907 : : tristate
2908 : 234738 : store::eval_alias_1 (const region *base_reg_a,
2909 : : const region *base_reg_b) const
2910 : : {
2911 : : /* If they're in different memory spaces, they can't alias. */
2912 : 234738 : {
2913 : 234738 : enum memory_space memspace_a = base_reg_a->get_memory_space ();
2914 : 234738 : if (memspace_a != MEMSPACE_UNKNOWN)
2915 : : {
2916 : 80205 : enum memory_space memspace_b = base_reg_b->get_memory_space ();
2917 : 80205 : if (memspace_b != MEMSPACE_UNKNOWN
2918 : 80205 : && memspace_a != memspace_b)
2919 : 249 : return tristate::TS_FALSE;
2920 : : }
2921 : : }
2922 : :
2923 : 468978 : if (const symbolic_region *sym_reg_a
2924 : 234489 : = base_reg_a->dyn_cast_symbolic_region ())
2925 : : {
2926 : 148699 : const svalue *sval_a = sym_reg_a->get_pointer ();
2927 : 148699 : if (tree decl_b = base_reg_b->maybe_get_decl ())
2928 : : {
2929 : 76074 : if (!may_be_aliased (decl_b))
2930 : 44294 : return tristate::TS_FALSE;
2931 : 31780 : if (sval_a->get_kind () == SK_INITIAL)
2932 : 19084 : if (!is_global_var (decl_b))
2933 : : {
2934 : : /* The initial value of a pointer can't point to a local. */
2935 : 13033 : return tristate::TS_FALSE;
2936 : : }
2937 : : }
2938 : 91372 : if (sval_a->get_kind () == SK_INITIAL
2939 : 91372 : && base_reg_b->get_kind () == RK_HEAP_ALLOCATED)
2940 : : {
2941 : : /* The initial value of a pointer can't point to a
2942 : : region that was allocated on the heap after the beginning of the
2943 : : path. */
2944 : 9366 : return tristate::TS_FALSE;
2945 : : }
2946 : 164012 : if (const widening_svalue *widening_sval_a
2947 : 82006 : = sval_a->dyn_cast_widening_svalue ())
2948 : : {
2949 : 3579 : const svalue *base = widening_sval_a->get_base_svalue ();
2950 : 7158 : if (const region_svalue *region_sval
2951 : 3579 : = base->dyn_cast_region_svalue ())
2952 : : {
2953 : 555 : const region *pointee = region_sval->get_pointee ();
2954 : : /* If we have sval_a is WIDENING(®ION, OP), and
2955 : : B can't alias REGION, then B can't alias A either.
2956 : : For example, A might arise from
2957 : : for (ptr = ®ION; ...; ptr++)
2958 : : where sval_a is ptr in the 2nd iteration of the loop.
2959 : : We want to ensure that "*ptr" can only clobber things
2960 : : within REGION's base region. */
2961 : 555 : tristate ts = eval_alias (pointee->get_base_region (),
2962 : : base_reg_b);
2963 : 555 : if (ts.is_false ())
2964 : 295 : return tristate::TS_FALSE;
2965 : : }
2966 : : }
2967 : : }
2968 : 167501 : return tristate::TS_UNKNOWN;
2969 : : }
2970 : :
2971 : : /* Record all of the values in MAYBE_LIVE_VALUES as being possibly live. */
2972 : :
2973 : : void
2974 : 329547 : store::on_maybe_live_values (const svalue_set &maybe_live_values)
2975 : : {
2976 : 412459 : for (auto sval : maybe_live_values)
2977 : : {
2978 : 41456 : if (const region_svalue *ptr_sval = sval->dyn_cast_region_svalue ())
2979 : : {
2980 : 295 : const region *base_reg = ptr_sval->get_pointee ()->get_base_region ();
2981 : 295 : mark_as_escaped (base_reg);
2982 : : }
2983 : : }
2984 : 329547 : }
2985 : :
2986 : : /* Remove all bindings overlapping REG within this store. */
2987 : :
2988 : : void
2989 : 6152 : store::clobber_region (store_manager *mgr, const region *reg)
2990 : : {
2991 : 6152 : const region *base_reg = reg->get_base_region ();
2992 : 6152 : binding_cluster **slot = m_cluster_map.get (base_reg);
2993 : 6152 : if (!slot)
2994 : 1240 : return;
2995 : 4912 : binding_cluster *cluster = *slot;
2996 : 4912 : cluster->clobber_region (mgr, reg);
2997 : 4912 : if (cluster->redundant_p ())
2998 : : {
2999 : 3214 : delete cluster;
3000 : 3214 : m_cluster_map.remove (base_reg);
3001 : : }
3002 : : }
3003 : :
3004 : : /* Remove any bindings for REG within this store. */
3005 : :
3006 : : void
3007 : 178731 : store::purge_region (store_manager *mgr, const region *reg)
3008 : : {
3009 : 178731 : const region *base_reg = reg->get_base_region ();
3010 : 178731 : binding_cluster **slot = m_cluster_map.get (base_reg);
3011 : 178731 : if (!slot)
3012 : 0 : return;
3013 : 178731 : binding_cluster *cluster = *slot;
3014 : 178731 : cluster->purge_region (mgr, reg);
3015 : 178731 : if (cluster->redundant_p ())
3016 : : {
3017 : 170703 : delete cluster;
3018 : 170703 : m_cluster_map.remove (base_reg);
3019 : : }
3020 : : }
3021 : :
3022 : : /* Fill REG with SVAL. */
3023 : :
3024 : : void
3025 : 1440 : store::fill_region (store_manager *mgr, const region *reg, const svalue *sval)
3026 : : {
3027 : : /* Filling an empty region is a no-op. */
3028 : 1440 : if (reg->empty_p ())
3029 : : return;
3030 : :
3031 : 1412 : const region *base_reg = reg->get_base_region ();
3032 : 1412 : if (base_reg->symbolic_for_unknown_ptr_p ()
3033 : 1412 : || !base_reg->tracked_p ())
3034 : 6 : return;
3035 : 1406 : binding_cluster *cluster = get_or_create_cluster (base_reg);
3036 : 1406 : cluster->fill_region (mgr, reg, sval);
3037 : : }
3038 : :
3039 : : /* Zero-fill REG. */
3040 : :
3041 : : void
3042 : 777 : store::zero_fill_region (store_manager *mgr, const region *reg)
3043 : : {
3044 : 777 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
3045 : 777 : const svalue *zero_sval = sval_mgr->get_or_create_int_cst (char_type_node, 0);
3046 : 777 : fill_region (mgr, reg, zero_sval);
3047 : 777 : }
3048 : :
3049 : : /* Mark REG as having unknown content. */
3050 : :
3051 : : void
3052 : 289 : store::mark_region_as_unknown (store_manager *mgr, const region *reg,
3053 : : uncertainty_t *uncertainty,
3054 : : svalue_set *maybe_live_values)
3055 : : {
3056 : 289 : const region *base_reg = reg->get_base_region ();
3057 : 289 : if (base_reg->symbolic_for_unknown_ptr_p ()
3058 : 289 : || !base_reg->tracked_p ())
3059 : 0 : return;
3060 : 289 : binding_cluster *cluster = get_or_create_cluster (base_reg);
3061 : 289 : cluster->mark_region_as_unknown (mgr, reg, reg, uncertainty,
3062 : : maybe_live_values);
3063 : : }
3064 : :
3065 : : /* Purge state involving SVAL. */
3066 : :
3067 : : void
3068 : 34398 : store::purge_state_involving (const svalue *sval,
3069 : : region_model_manager *sval_mgr)
3070 : : {
3071 : 34398 : auto_vec <const region *> base_regs_to_purge;
3072 : 1158390 : for (auto iter : m_cluster_map)
3073 : : {
3074 : 561996 : const region *base_reg = iter.first;
3075 : 561996 : if (base_reg->involves_p (sval))
3076 : 182 : base_regs_to_purge.safe_push (base_reg);
3077 : : else
3078 : : {
3079 : 561814 : binding_cluster *cluster = iter.second;
3080 : 561814 : cluster->purge_state_involving (sval, sval_mgr);
3081 : : }
3082 : : }
3083 : :
3084 : 34944 : for (auto iter : base_regs_to_purge)
3085 : 182 : purge_cluster (iter);
3086 : 34398 : }
3087 : :
3088 : : /* Get the cluster for BASE_REG, or NULL (const version). */
3089 : :
3090 : : const binding_cluster *
3091 : 2419218 : store::get_cluster (const region *base_reg) const
3092 : : {
3093 : 2419218 : gcc_assert (base_reg);
3094 : 2419218 : gcc_assert (base_reg->get_base_region () == base_reg);
3095 : 4838436 : if (binding_cluster **slot
3096 : 2419218 : = const_cast <cluster_map_t &> (m_cluster_map).get (base_reg))
3097 : 2299205 : return *slot;
3098 : : else
3099 : : return NULL;
3100 : : }
3101 : :
3102 : : /* Get the cluster for BASE_REG, or NULL (non-const version). */
3103 : :
3104 : : binding_cluster *
3105 : 9065209 : store::get_cluster (const region *base_reg)
3106 : : {
3107 : 9065209 : gcc_assert (base_reg);
3108 : 9065209 : gcc_assert (base_reg->get_base_region () == base_reg);
3109 : 9065209 : if (binding_cluster **slot = m_cluster_map.get (base_reg))
3110 : 7693574 : return *slot;
3111 : : else
3112 : : return NULL;
3113 : : }
3114 : :
3115 : : /* Get the cluster for BASE_REG, creating it if doesn't already exist. */
3116 : :
3117 : : binding_cluster *
3118 : 1513582 : store::get_or_create_cluster (const region *base_reg)
3119 : : {
3120 : 1513582 : gcc_assert (base_reg);
3121 : 1513582 : gcc_assert (base_reg->get_base_region () == base_reg);
3122 : :
3123 : : /* We shouldn't create clusters for dereferencing an UNKNOWN ptr. */
3124 : 1513582 : gcc_assert (!base_reg->symbolic_for_unknown_ptr_p ());
3125 : :
3126 : : /* We shouldn't create clusters for base regions that aren't trackable. */
3127 : 1513582 : gcc_assert (base_reg->tracked_p ());
3128 : :
3129 : 1513582 : if (binding_cluster **slot = m_cluster_map.get (base_reg))
3130 : 55539 : return *slot;
3131 : :
3132 : 1458043 : binding_cluster *cluster = new binding_cluster (base_reg);
3133 : 1458043 : m_cluster_map.put (base_reg, cluster);
3134 : :
3135 : 1458043 : return cluster;
3136 : : }
3137 : :
3138 : : /* Remove any cluster for BASE_REG, for use by
3139 : : region_model::unbind_region_and_descendents
3140 : : when popping stack frames and handling deleted heap regions. */
3141 : :
3142 : : void
3143 : 32819 : store::purge_cluster (const region *base_reg)
3144 : : {
3145 : 32819 : gcc_assert (base_reg->get_base_region () == base_reg);
3146 : 32819 : binding_cluster **slot = m_cluster_map.get (base_reg);
3147 : 32819 : if (!slot)
3148 : : return;
3149 : 32819 : binding_cluster *cluster = *slot;
3150 : 65638 : delete cluster;
3151 : 32819 : m_cluster_map.remove (base_reg);
3152 : : }
3153 : :
3154 : : /* Attempt to merge STORE_A and STORE_B into OUT_STORE.
3155 : : Return true if successful, or false if the stores can't be merged. */
3156 : :
3157 : : bool
3158 : 151668 : store::can_merge_p (const store *store_a, const store *store_b,
3159 : : store *out_store, store_manager *mgr,
3160 : : model_merger *merger)
3161 : : {
3162 : 151668 : if (store_a->m_called_unknown_fn || store_b->m_called_unknown_fn)
3163 : 60383 : out_store->m_called_unknown_fn = true;
3164 : :
3165 : : /* Get the union of all base regions for STORE_A and STORE_B. */
3166 : 151668 : hash_set<const region *> base_regions;
3167 : 1656307 : for (cluster_map_t::iterator iter_a = store_a->m_cluster_map.begin ();
3168 : 3160946 : iter_a != store_a->m_cluster_map.end (); ++iter_a)
3169 : : {
3170 : 1504639 : const region *base_reg_a = (*iter_a).first;
3171 : 1504639 : base_regions.add (base_reg_a);
3172 : : }
3173 : 1588847 : for (cluster_map_t::iterator iter_b = store_b->m_cluster_map.begin ();
3174 : 3026026 : iter_b != store_b->m_cluster_map.end (); ++iter_b)
3175 : : {
3176 : 1437179 : const region *base_reg_b = (*iter_b).first;
3177 : 1437179 : base_regions.add (base_reg_b);
3178 : : }
3179 : :
3180 : : /* Sort the base regions before considering them. This ought not to
3181 : : affect the results, but can affect which types UNKNOWN_REGIONs are
3182 : : created for in a run; sorting them thus avoids minor differences
3183 : : in logfiles. */
3184 : 151668 : auto_vec<const region *> vec_base_regions (base_regions.elements ());
3185 : 151668 : for (hash_set<const region *>::iterator iter = base_regions.begin ();
3186 : 3242364 : iter != base_regions.end (); ++iter)
3187 : 1545348 : vec_base_regions.quick_push (*iter);
3188 : 151668 : vec_base_regions.qsort (region::cmp_ptr_ptr);
3189 : : unsigned i;
3190 : : const region *base_reg;
3191 : 1355029 : FOR_EACH_VEC_ELT (vec_base_regions, i, base_reg)
3192 : : {
3193 : 1137774 : const binding_cluster *cluster_a = store_a->get_cluster (base_reg);
3194 : 1137774 : const binding_cluster *cluster_b = store_b->get_cluster (base_reg);
3195 : : /* At least one of cluster_a and cluster_b must be non-NULL. */
3196 : 1137774 : binding_cluster *out_cluster
3197 : 1137774 : = out_store->get_or_create_cluster (base_reg);
3198 : 1137774 : if (!binding_cluster::can_merge_p (cluster_a, cluster_b,
3199 : : out_cluster, out_store, mgr, merger))
3200 : : return false;
3201 : : }
3202 : : return true;
3203 : 151668 : }
3204 : :
3205 : : /* Mark the cluster for BASE_REG as having escaped.
3206 : : For use when handling an unrecognized function call, and
3207 : : for params to "top-level" calls.
3208 : : Further unknown function calls could touch it, even if the cluster
3209 : : isn't reachable from args of those calls. */
3210 : :
3211 : : void
3212 : 41640 : store::mark_as_escaped (const region *base_reg)
3213 : : {
3214 : 41640 : gcc_assert (base_reg);
3215 : 41640 : gcc_assert (base_reg->get_base_region () == base_reg);
3216 : :
3217 : 41640 : if (base_reg->symbolic_for_unknown_ptr_p ()
3218 : 41640 : || !base_reg->tracked_p ())
3219 : 5035 : return;
3220 : :
3221 : 36605 : binding_cluster *cluster = get_or_create_cluster (base_reg);
3222 : 36605 : cluster->mark_as_escaped ();
3223 : : }
3224 : :
3225 : : /* Handle an unknown fncall by updating any clusters that have escaped
3226 : : (either in this fncall, or in a prior one). */
3227 : :
3228 : : void
3229 : 18527 : store::on_unknown_fncall (const gcall *call, store_manager *mgr,
3230 : : const conjured_purge &p)
3231 : : {
3232 : 18527 : m_called_unknown_fn = true;
3233 : :
3234 : 182340 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3235 : 346153 : iter != m_cluster_map.end (); ++iter)
3236 : 163813 : (*iter).second->on_unknown_fncall (call, mgr, p);
3237 : 18527 : }
3238 : :
3239 : : /* Return true if a non-const pointer to BASE_REG (or something within it)
3240 : : has escaped to code outside of the TU being analyzed. */
3241 : :
3242 : : bool
3243 : 7770036 : store::escaped_p (const region *base_reg) const
3244 : : {
3245 : 7770036 : gcc_assert (base_reg);
3246 : 7770036 : gcc_assert (base_reg->get_base_region () == base_reg);
3247 : :
3248 : : /* "errno" can always be modified by external code. */
3249 : 7770036 : if (base_reg->get_kind () == RK_ERRNO)
3250 : : return true;
3251 : :
3252 : 15335582 : if (binding_cluster **cluster_slot
3253 : 7667791 : = const_cast <cluster_map_t &>(m_cluster_map).get (base_reg))
3254 : 7667791 : return (*cluster_slot)->escaped_p ();
3255 : : return false;
3256 : : }
3257 : :
3258 : : /* Populate OUT_PVS with a list of path_vars for describing SVAL based on
3259 : : this store, using VISITED to ensure the traversal terminates. */
3260 : :
3261 : : void
3262 : 14167 : store::get_representative_path_vars (const region_model *model,
3263 : : svalue_set *visited,
3264 : : const svalue *sval,
3265 : : logger *logger,
3266 : : auto_vec<path_var> *out_pvs) const
3267 : : {
3268 : 14167 : gcc_assert (sval);
3269 : :
3270 : : /* Find all bindings that reference SVAL. */
3271 : 75169 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3272 : 136171 : iter != m_cluster_map.end (); ++iter)
3273 : : {
3274 : 61002 : const region *base_reg = (*iter).first;
3275 : 61002 : binding_cluster *cluster = (*iter).second;
3276 : 61002 : cluster->get_representative_path_vars (model, visited, base_reg, sval,
3277 : : logger,
3278 : : out_pvs);
3279 : : }
3280 : :
3281 : 14167 : if (const initial_svalue *init_sval = sval->dyn_cast_initial_svalue ())
3282 : : {
3283 : 2573 : const region *reg = init_sval->get_region ();
3284 : 2573 : if (path_var pv = model->get_representative_path_var (reg,
3285 : : visited,
3286 : 2573 : logger))
3287 : 2451 : out_pvs->safe_push (pv);
3288 : : }
3289 : 14167 : }
3290 : :
3291 : : /* Remove all bindings overlapping REG within this store, removing
3292 : : any clusters that become redundant.
3293 : :
3294 : : If UNCERTAINTY is non-NULL, use it to record any svalues that
3295 : : were removed, as being maybe-bound. */
3296 : :
3297 : : void
3298 : 329258 : store::remove_overlapping_bindings (store_manager *mgr, const region *reg,
3299 : : uncertainty_t *uncertainty)
3300 : : {
3301 : 329258 : const region *base_reg = reg->get_base_region ();
3302 : 329258 : if (binding_cluster **cluster_slot = m_cluster_map.get (base_reg))
3303 : : {
3304 : 51318 : binding_cluster *cluster = *cluster_slot;
3305 : 51318 : if (reg == base_reg && !escaped_p (base_reg))
3306 : : {
3307 : : /* Remove whole cluster. */
3308 : 30766 : m_cluster_map.remove (base_reg);
3309 : 61532 : delete cluster;
3310 : 30766 : return;
3311 : : }
3312 : : /* Pass NULL for the maybe_live_values here, as we don't want to
3313 : : record the old svalues as being maybe-bound. */
3314 : 20552 : cluster->remove_overlapping_bindings (mgr, reg, uncertainty, NULL);
3315 : : }
3316 : : }
3317 : :
3318 : : /* Subclass of visitor that accumulates a hash_set of the regions that
3319 : : were visited. */
3320 : :
3321 : 2039420 : struct region_finder : public visitor
3322 : : {
3323 : 18063054 : void visit_region (const region *reg) final override
3324 : : {
3325 : 18063054 : m_regs.add (reg);
3326 : 18063054 : }
3327 : :
3328 : : hash_set<const region *> m_regs;
3329 : : };
3330 : :
3331 : : /* Canonicalize this store, to maximize the chance of equality between
3332 : : instances. */
3333 : :
3334 : : void
3335 : 1019710 : store::canonicalize (store_manager *mgr)
3336 : : {
3337 : : /* If we have e.g.:
3338 : : cluster for: HEAP_ALLOCATED_REGION(543)
3339 : : ESCAPED
3340 : : TOUCHED
3341 : : where the heap region is empty and unreferenced, then purge that
3342 : : cluster, to avoid unbounded state chains involving these. */
3343 : :
3344 : : /* Find regions that are referenced by bound values in the store. */
3345 : 1019710 : region_finder s;
3346 : 1019710 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3347 : 12429244 : iter != m_cluster_map.end (); ++iter)
3348 : : {
3349 : 5704767 : binding_cluster *cluster = (*iter).second;
3350 : 11696290 : for (binding_cluster::iterator_t bind_iter = cluster->m_map.begin ();
3351 : 23392580 : bind_iter != cluster->m_map.end (); ++bind_iter)
3352 : 5991523 : (*bind_iter).second->accept (&s);
3353 : : }
3354 : :
3355 : : /* Locate heap-allocated regions that have empty bindings that weren't
3356 : : found above. */
3357 : 1019710 : hash_set<const region *> purgeable_regions;
3358 : 6724477 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3359 : 12429244 : iter != m_cluster_map.end (); ++iter)
3360 : : {
3361 : 5704767 : const region *base_reg = (*iter).first;
3362 : 5704767 : binding_cluster *cluster = (*iter).second;
3363 : 5704767 : if (base_reg->get_kind () == RK_HEAP_ALLOCATED)
3364 : : {
3365 : : /* Don't purge a heap-allocated region that's been marked as
3366 : : escaping, since this could be recording that a ptr to it
3367 : : was written to an unknown symbolic region along this
3368 : : path, and so we don't know whether it's referenced or
3369 : : not, and hence should report it as leaking
3370 : : (PR analyzer/106473). */
3371 : 478255 : if (cluster->escaped_p ())
3372 : 251350 : continue;
3373 : :
3374 : 226905 : if (cluster->empty_p ())
3375 : 612 : if (!s.m_regs.contains (base_reg))
3376 : 0 : purgeable_regions.add (base_reg);
3377 : :
3378 : : /* Also cover the UNKNOWN case. */
3379 : 226905 : if (const svalue *sval = cluster->maybe_get_simple_value (mgr))
3380 : 44649 : if (sval->get_kind () == SK_UNKNOWN)
3381 : 32552 : if (!s.m_regs.contains (base_reg))
3382 : 36 : purgeable_regions.add (base_reg);
3383 : : }
3384 : : }
3385 : :
3386 : : /* Purge them. */
3387 : 1019746 : for (hash_set<const region *>::iterator iter = purgeable_regions.begin ();
3388 : 2039492 : iter != purgeable_regions.end (); ++iter)
3389 : : {
3390 : 36 : const region *base_reg = *iter;
3391 : 36 : purge_cluster (base_reg);
3392 : : }
3393 : 1019710 : }
3394 : :
3395 : : /* Subroutine for use by exploded_path::feasible_p.
3396 : :
3397 : : We need to deal with state differences between:
3398 : : (a) when the exploded_graph is being initially constructed and
3399 : : (b) when replaying the state changes along a specific path in
3400 : : in exploded_path::feasible_p.
3401 : :
3402 : : In (a), state merging happens, so when exploring a loop
3403 : : for (i = 0; i < 1024; i++)
3404 : : on successive iterations we have i == 0, then i == WIDENING.
3405 : :
3406 : : In (b), no state merging happens, so naively replaying the path
3407 : : that goes twice through the loop then exits it
3408 : : would lead to i == 0, then i == 1, and then a (i >= 1024) eedge
3409 : : that exits the loop, which would be found to be infeasible as i == 1,
3410 : : and the path would be rejected.
3411 : :
3412 : : We need to fix up state during replay. This subroutine is
3413 : : called whenever we enter a supernode that we've already
3414 : : visited along this exploded_path, passing in OTHER_STORE
3415 : : from the destination enode's state.
3416 : :
3417 : : Find bindings to widening values in OTHER_STORE.
3418 : : For all that are found, update the binding in this store to UNKNOWN. */
3419 : :
3420 : : void
3421 : 9119 : store::loop_replay_fixup (const store *other_store,
3422 : : region_model_manager *mgr)
3423 : : {
3424 : 9119 : gcc_assert (other_store);
3425 : 9119 : for (cluster_map_t::iterator iter = other_store->m_cluster_map.begin ();
3426 : 155993 : iter != other_store->m_cluster_map.end (); ++iter)
3427 : : {
3428 : 73437 : const region *base_reg = (*iter).first;
3429 : 73437 : binding_cluster *cluster = (*iter).second;
3430 : 157917 : for (binding_cluster::iterator_t bind_iter = cluster->m_map.begin ();
3431 : 315834 : bind_iter != cluster->m_map.end (); ++bind_iter)
3432 : : {
3433 : 84480 : const binding_key *key = (*bind_iter).first;
3434 : 84480 : const svalue *sval = (*bind_iter).second;
3435 : 84480 : if (sval->get_kind () == SK_WIDENING)
3436 : : {
3437 : 1819 : binding_cluster *this_cluster
3438 : 1819 : = get_or_create_cluster (base_reg);
3439 : 1819 : const svalue *unknown
3440 : 1819 : = mgr->get_or_create_unknown_svalue (sval->get_type ());
3441 : 1819 : this_cluster->bind_key (key, unknown);
3442 : : }
3443 : : }
3444 : : }
3445 : 9119 : }
3446 : :
3447 : : /* Use R to replay the bindings from SUMMARY into this object. */
3448 : :
3449 : : void
3450 : 1598 : store::replay_call_summary (call_summary_replay &r,
3451 : : const store &summary)
3452 : : {
3453 : 1598 : if (summary.m_called_unknown_fn)
3454 : : {
3455 : : /* A call to an external function occurred in the summary.
3456 : : Hence we need to invalidate our knownledge of globals,
3457 : : escaped regions, etc. */
3458 : 67 : on_unknown_fncall (r.get_call_stmt (),
3459 : : r.get_store_manager (),
3460 : 67 : conjured_purge (r.get_caller_model (),
3461 : 67 : r.get_ctxt ()));
3462 : : }
3463 : :
3464 : 1598 : auto_vec<const region *> keys (summary.m_cluster_map.elements ());
3465 : 16038 : for (auto kv : summary.m_cluster_map)
3466 : 14440 : keys.quick_push (kv.first);
3467 : 1598 : keys.qsort (region::cmp_ptr_ptr);
3468 : 19178 : for (auto base_reg : keys)
3469 : 14440 : replay_call_summary_cluster (r, summary, base_reg);
3470 : 1598 : }
3471 : :
3472 : : /* Use R and SUMMARY to replay the bindings in SUMMARY_CLUSTER
3473 : : into this object. */
3474 : :
3475 : : void
3476 : 14440 : store::replay_call_summary_cluster (call_summary_replay &r,
3477 : : const store &summary,
3478 : : const region *summary_base_reg)
3479 : : {
3480 : 14440 : const call_details &cd = r.get_call_details ();
3481 : 14440 : region_model_manager *reg_mgr = r.get_manager ();
3482 : 14440 : store_manager *mgr = reg_mgr->get_store_manager ();
3483 : 14440 : const binding_cluster *summary_cluster
3484 : 14440 : = summary.get_cluster (summary_base_reg);
3485 : :
3486 : : /* Handle "ESCAPED" and "TOUCHED" flags. */
3487 : 14440 : if (summary_cluster->escaped_p () || summary_cluster->touched_p ())
3488 : 9458 : if (const region *caller_reg
3489 : 4729 : = r.convert_region_from_summary (summary_base_reg))
3490 : : {
3491 : 4720 : const region *caller_base_reg = caller_reg->get_base_region ();
3492 : 4720 : if (caller_base_reg->tracked_p ()
3493 : 4720 : && !caller_base_reg->symbolic_for_unknown_ptr_p ())
3494 : : {
3495 : 3690 : binding_cluster *caller_cluster
3496 : 3690 : = get_or_create_cluster (caller_base_reg);
3497 : 3690 : if (summary_cluster->escaped_p ())
3498 : 2869 : caller_cluster->mark_as_escaped ();
3499 : 3690 : if (summary_cluster->touched_p ())
3500 : 2266 : caller_cluster->m_touched = true;
3501 : : }
3502 : : }
3503 : :
3504 : 14440 : switch (summary_base_reg->get_kind ())
3505 : : {
3506 : : /* Top-level regions. */
3507 : 0 : case RK_FRAME:
3508 : 0 : case RK_GLOBALS:
3509 : 0 : case RK_CODE:
3510 : 0 : case RK_STACK:
3511 : 0 : case RK_HEAP:
3512 : 0 : case RK_THREAD_LOCAL:
3513 : 0 : case RK_ROOT:
3514 : : /* Child regions. */
3515 : 0 : case RK_FIELD:
3516 : 0 : case RK_ELEMENT:
3517 : 0 : case RK_OFFSET:
3518 : 0 : case RK_SIZED:
3519 : 0 : case RK_CAST:
3520 : 0 : case RK_BIT_RANGE:
3521 : : /* Other regions. */
3522 : 0 : case RK_VAR_ARG:
3523 : 0 : case RK_UNKNOWN:
3524 : : /* These should never be the base region of a binding cluster. */
3525 : 0 : gcc_unreachable ();
3526 : : break;
3527 : :
3528 : : case RK_FUNCTION:
3529 : : case RK_LABEL:
3530 : : case RK_STRING:
3531 : : /* These can be marked as escaping. */
3532 : : break;
3533 : :
3534 : 3321 : case RK_SYMBOLIC:
3535 : 3321 : {
3536 : 3321 : const symbolic_region *summary_symbolic_reg
3537 : 3321 : = as_a <const symbolic_region *> (summary_base_reg);
3538 : 3321 : const svalue *summary_ptr_sval = summary_symbolic_reg->get_pointer ();
3539 : 3321 : const svalue *caller_ptr_sval
3540 : 3321 : = r.convert_svalue_from_summary (summary_ptr_sval);
3541 : 3321 : if (!caller_ptr_sval)
3542 : : return;
3543 : 2776 : const region *caller_dest_reg
3544 : 2776 : = cd.get_model ()->deref_rvalue (caller_ptr_sval,
3545 : : NULL_TREE,
3546 : : cd.get_ctxt ());
3547 : 2776 : const svalue *summary_sval
3548 : 2776 : = summary.get_any_binding (mgr, summary_base_reg);
3549 : 2776 : if (!summary_sval)
3550 : : return;
3551 : 2508 : const svalue *caller_sval
3552 : 2508 : = r.convert_svalue_from_summary (summary_sval);
3553 : 2508 : if (!caller_sval)
3554 : 2 : caller_sval =
3555 : 2 : reg_mgr->get_or_create_unknown_svalue (summary_sval->get_type ());
3556 : 2508 : set_value (mgr, caller_dest_reg,
3557 : : caller_sval, NULL /* uncertainty_t * */);
3558 : : }
3559 : 2508 : break;
3560 : :
3561 : 11114 : case RK_HEAP_ALLOCATED:
3562 : 11114 : case RK_DECL:
3563 : 11114 : case RK_ERRNO:
3564 : 11114 : case RK_PRIVATE:
3565 : 11114 : {
3566 : 11114 : const region *caller_dest_reg
3567 : 11114 : = r.convert_region_from_summary (summary_base_reg);
3568 : 11114 : if (!caller_dest_reg)
3569 : : return;
3570 : 10885 : const svalue *summary_sval
3571 : 10885 : = summary.get_any_binding (mgr, summary_base_reg);
3572 : 10885 : if (!summary_sval)
3573 : 206 : summary_sval = reg_mgr->get_or_create_compound_svalue
3574 : 206 : (summary_base_reg->get_type (),
3575 : : summary_cluster->get_map ());
3576 : 10885 : const svalue *caller_sval
3577 : 10885 : = r.convert_svalue_from_summary (summary_sval);
3578 : 10885 : if (!caller_sval)
3579 : 2 : caller_sval =
3580 : 2 : reg_mgr->get_or_create_unknown_svalue (summary_sval->get_type ());
3581 : 10885 : set_value (mgr, caller_dest_reg,
3582 : : caller_sval, NULL /* uncertainty_t * */);
3583 : : }
3584 : 10885 : break;
3585 : :
3586 : : case RK_ALLOCA:
3587 : : /* Ignore bindings of alloca regions in the summary. */
3588 : : break;
3589 : : }
3590 : : }
3591 : :
3592 : : #if CHECKING_P
3593 : :
3594 : : namespace selftest {
3595 : :
3596 : : /* Verify that bit_range::intersects_p works as expected. */
3597 : :
3598 : : static void
3599 : 4 : test_bit_range_intersects_p ()
3600 : : {
3601 : 4 : bit_range b0 (0, 1);
3602 : 4 : bit_range b1 (1, 1);
3603 : 4 : bit_range b2 (2, 1);
3604 : 4 : bit_range b3 (3, 1);
3605 : 4 : bit_range b4 (4, 1);
3606 : 4 : bit_range b5 (5, 1);
3607 : 4 : bit_range b6 (6, 1);
3608 : 4 : bit_range b7 (7, 1);
3609 : 4 : bit_range b1_to_6 (1, 6);
3610 : 4 : bit_range b0_to_7 (0, 8);
3611 : 4 : bit_range b3_to_5 (3, 3);
3612 : 4 : bit_range b6_to_7 (6, 2);
3613 : :
3614 : : /* self-intersection is true. */
3615 : 4 : ASSERT_TRUE (b0.intersects_p (b0));
3616 : 4 : ASSERT_TRUE (b7.intersects_p (b7));
3617 : 4 : ASSERT_TRUE (b1_to_6.intersects_p (b1_to_6));
3618 : 4 : ASSERT_TRUE (b0_to_7.intersects_p (b0_to_7));
3619 : :
3620 : 4 : ASSERT_FALSE (b0.intersects_p (b1));
3621 : 4 : ASSERT_FALSE (b1.intersects_p (b0));
3622 : 4 : ASSERT_FALSE (b0.intersects_p (b7));
3623 : 4 : ASSERT_FALSE (b7.intersects_p (b0));
3624 : :
3625 : 4 : ASSERT_TRUE (b0_to_7.intersects_p (b0));
3626 : 4 : ASSERT_TRUE (b0_to_7.intersects_p (b7));
3627 : 4 : ASSERT_TRUE (b0.intersects_p (b0_to_7));
3628 : 4 : ASSERT_TRUE (b7.intersects_p (b0_to_7));
3629 : :
3630 : 4 : ASSERT_FALSE (b0.intersects_p (b1_to_6));
3631 : 4 : ASSERT_FALSE (b1_to_6.intersects_p (b0));
3632 : 4 : ASSERT_TRUE (b1.intersects_p (b1_to_6));
3633 : 4 : ASSERT_TRUE (b1_to_6.intersects_p (b1));
3634 : 4 : ASSERT_TRUE (b1_to_6.intersects_p (b6));
3635 : 4 : ASSERT_FALSE (b1_to_6.intersects_p (b7));
3636 : :
3637 : 4 : ASSERT_TRUE (b1_to_6.intersects_p (b0_to_7));
3638 : 4 : ASSERT_TRUE (b0_to_7.intersects_p (b1_to_6));
3639 : :
3640 : 4 : ASSERT_FALSE (b3_to_5.intersects_p (b6_to_7));
3641 : 4 : ASSERT_FALSE (b6_to_7.intersects_p (b3_to_5));
3642 : :
3643 : 4 : bit_range r1 (0,0);
3644 : 4 : bit_range r2 (0,0);
3645 : 4 : ASSERT_TRUE (b1_to_6.intersects_p (b0_to_7, &r1, &r2));
3646 : 4 : ASSERT_EQ (r1.get_start_bit_offset (), 0);
3647 : 4 : ASSERT_EQ (r1.m_size_in_bits, 6);
3648 : 4 : ASSERT_EQ (r2.get_start_bit_offset (), 1);
3649 : 4 : ASSERT_EQ (r2.m_size_in_bits, 6);
3650 : :
3651 : 4 : ASSERT_TRUE (b0_to_7.intersects_p (b1_to_6, &r1, &r2));
3652 : 4 : ASSERT_EQ (r1.get_start_bit_offset (), 1);
3653 : 4 : ASSERT_EQ (r1.m_size_in_bits, 6);
3654 : 4 : ASSERT_EQ (r2.get_start_bit_offset (), 0);
3655 : 4 : ASSERT_EQ (r2.m_size_in_bits, 6);
3656 : 4 : }
3657 : :
3658 : : /* Implementation detail of ASSERT_BIT_RANGE_FROM_MASK_EQ. */
3659 : :
3660 : : static void
3661 : 76 : assert_bit_range_from_mask_eq (const location &loc,
3662 : : unsigned HOST_WIDE_INT mask,
3663 : : const bit_range &expected)
3664 : : {
3665 : 76 : bit_range actual (0, 0);
3666 : 76 : bool ok = bit_range::from_mask (mask, &actual);
3667 : 76 : ASSERT_TRUE_AT (loc, ok);
3668 : 76 : ASSERT_EQ_AT (loc, actual, expected);
3669 : 76 : }
3670 : :
3671 : : /* Assert that bit_range::from_mask (MASK) returns true, and writes
3672 : : out EXPECTED_BIT_RANGE. */
3673 : :
3674 : : #define ASSERT_BIT_RANGE_FROM_MASK_EQ(MASK, EXPECTED_BIT_RANGE) \
3675 : : SELFTEST_BEGIN_STMT \
3676 : : assert_bit_range_from_mask_eq (SELFTEST_LOCATION, MASK, \
3677 : : EXPECTED_BIT_RANGE); \
3678 : : SELFTEST_END_STMT
3679 : :
3680 : : /* Implementation detail of ASSERT_NO_BIT_RANGE_FROM_MASK. */
3681 : :
3682 : : static void
3683 : 12 : assert_no_bit_range_from_mask_eq (const location &loc,
3684 : : unsigned HOST_WIDE_INT mask)
3685 : : {
3686 : 12 : bit_range actual (0, 0);
3687 : 12 : bool ok = bit_range::from_mask (mask, &actual);
3688 : 12 : ASSERT_FALSE_AT (loc, ok);
3689 : 12 : }
3690 : :
3691 : : /* Assert that bit_range::from_mask (MASK) returns false. */
3692 : :
3693 : : #define ASSERT_NO_BIT_RANGE_FROM_MASK(MASK) \
3694 : : SELFTEST_BEGIN_STMT \
3695 : : assert_no_bit_range_from_mask_eq (SELFTEST_LOCATION, MASK); \
3696 : : SELFTEST_END_STMT
3697 : :
3698 : : /* Verify that bit_range::from_mask works as expected. */
3699 : :
3700 : : static void
3701 : 4 : test_bit_range_from_mask ()
3702 : : {
3703 : : /* Should fail on zero. */
3704 : 4 : ASSERT_NO_BIT_RANGE_FROM_MASK (0);
3705 : :
3706 : : /* Verify 1-bit masks. */
3707 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (1, bit_range (0, 1));
3708 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (2, bit_range (1, 1));
3709 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (4, bit_range (2, 1));
3710 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (8, bit_range (3, 1));
3711 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (16, bit_range (4, 1));
3712 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (32, bit_range (5, 1));
3713 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (64, bit_range (6, 1));
3714 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (128, bit_range (7, 1));
3715 : :
3716 : : /* Verify N-bit masks starting at bit 0. */
3717 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (3, bit_range (0, 2));
3718 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (7, bit_range (0, 3));
3719 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (15, bit_range (0, 4));
3720 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (31, bit_range (0, 5));
3721 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (63, bit_range (0, 6));
3722 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (127, bit_range (0, 7));
3723 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (255, bit_range (0, 8));
3724 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (0xffff, bit_range (0, 16));
3725 : :
3726 : : /* Various other tests. */
3727 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (0x30, bit_range (4, 2));
3728 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (0x700, bit_range (8, 3));
3729 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (0x600, bit_range (9, 2));
3730 : :
3731 : : /* Multiple ranges of set bits should fail. */
3732 : 4 : ASSERT_NO_BIT_RANGE_FROM_MASK (0x101);
3733 : 4 : ASSERT_NO_BIT_RANGE_FROM_MASK (0xf0f0f0f0);
3734 : 4 : }
3735 : :
3736 : : /* Implementation detail of ASSERT_OVERLAP. */
3737 : :
3738 : : static void
3739 : 56 : assert_overlap (const location &loc,
3740 : : const concrete_binding *b1,
3741 : : const concrete_binding *b2)
3742 : : {
3743 : 56 : ASSERT_TRUE_AT (loc, b1->overlaps_p (*b2));
3744 : 56 : ASSERT_TRUE_AT (loc, b2->overlaps_p (*b1));
3745 : 56 : }
3746 : :
3747 : : /* Implementation detail of ASSERT_DISJOINT. */
3748 : :
3749 : : static void
3750 : 20 : assert_disjoint (const location &loc,
3751 : : const concrete_binding *b1,
3752 : : const concrete_binding *b2)
3753 : : {
3754 : 20 : ASSERT_FALSE_AT (loc, b1->overlaps_p (*b2));
3755 : 20 : ASSERT_FALSE_AT (loc, b2->overlaps_p (*b1));
3756 : 20 : }
3757 : :
3758 : : /* Assert that B1 and B2 overlap, checking both ways. */
3759 : :
3760 : : #define ASSERT_OVERLAP(B1, B2) \
3761 : : SELFTEST_BEGIN_STMT \
3762 : : assert_overlap (SELFTEST_LOCATION, B1, B2); \
3763 : : SELFTEST_END_STMT
3764 : :
3765 : : /* Assert that B1 and B2 do not overlap, checking both ways. */
3766 : :
3767 : : #define ASSERT_DISJOINT(B1, B2) \
3768 : : SELFTEST_BEGIN_STMT \
3769 : : assert_disjoint (SELFTEST_LOCATION, B1, B2); \
3770 : : SELFTEST_END_STMT
3771 : :
3772 : : /* Verify that concrete_binding::overlaps_p works as expected. */
3773 : :
3774 : : static void
3775 : 4 : test_binding_key_overlap ()
3776 : : {
3777 : 4 : store_manager mgr (NULL);
3778 : :
3779 : : /* Various 8-bit bindings. */
3780 : 4 : const concrete_binding *cb_0_7 = mgr.get_concrete_binding (0, 8);
3781 : 4 : const concrete_binding *cb_8_15 = mgr.get_concrete_binding (8, 8);
3782 : 4 : const concrete_binding *cb_16_23 = mgr.get_concrete_binding (16, 8);
3783 : 4 : const concrete_binding *cb_24_31 = mgr.get_concrete_binding (24, 8);
3784 : :
3785 : : /* 16-bit bindings. */
3786 : 4 : const concrete_binding *cb_0_15 = mgr.get_concrete_binding (0, 16);
3787 : 4 : const concrete_binding *cb_8_23 = mgr.get_concrete_binding (8, 16);
3788 : 4 : const concrete_binding *cb_16_31 = mgr.get_concrete_binding (16, 16);
3789 : :
3790 : : /* 32-bit binding. */
3791 : 4 : const concrete_binding *cb_0_31 = mgr.get_concrete_binding (0, 32);
3792 : :
3793 : : /* Everything should self-overlap. */
3794 : 4 : ASSERT_OVERLAP (cb_0_7, cb_0_7);
3795 : 4 : ASSERT_OVERLAP (cb_8_15, cb_8_15);
3796 : 4 : ASSERT_OVERLAP (cb_16_23, cb_16_23);
3797 : 4 : ASSERT_OVERLAP (cb_24_31, cb_24_31);
3798 : 4 : ASSERT_OVERLAP (cb_0_15, cb_0_15);
3799 : 4 : ASSERT_OVERLAP (cb_8_23, cb_8_23);
3800 : 4 : ASSERT_OVERLAP (cb_16_31, cb_16_31);
3801 : 4 : ASSERT_OVERLAP (cb_0_31, cb_0_31);
3802 : :
3803 : : /* Verify the 8-bit bindings that don't overlap each other. */
3804 : 4 : ASSERT_DISJOINT (cb_0_7, cb_8_15);
3805 : 4 : ASSERT_DISJOINT (cb_8_15, cb_16_23);
3806 : :
3807 : : /* Check for overlap of differently-sized bindings. */
3808 : 4 : ASSERT_OVERLAP (cb_0_7, cb_0_31);
3809 : : /* ...and with differing start points. */
3810 : 4 : ASSERT_OVERLAP (cb_8_15, cb_0_31);
3811 : 4 : ASSERT_DISJOINT (cb_8_15, cb_16_31);
3812 : 4 : ASSERT_OVERLAP (cb_16_23, cb_0_31);
3813 : 4 : ASSERT_OVERLAP (cb_16_31, cb_0_31);
3814 : :
3815 : 4 : ASSERT_DISJOINT (cb_0_7, cb_8_23);
3816 : 4 : ASSERT_OVERLAP (cb_8_23, cb_16_23);
3817 : 4 : ASSERT_OVERLAP (cb_8_23, cb_16_31);
3818 : 4 : ASSERT_DISJOINT (cb_8_23, cb_24_31);
3819 : 4 : }
3820 : :
3821 : : /* Run all of the selftests within this file. */
3822 : :
3823 : : void
3824 : 4 : analyzer_store_cc_tests ()
3825 : : {
3826 : 4 : test_bit_range_intersects_p ();
3827 : 4 : test_bit_range_from_mask ();
3828 : 4 : test_binding_key_overlap ();
3829 : 4 : }
3830 : :
3831 : : } // namespace selftest
3832 : :
3833 : : #endif /* CHECKING_P */
3834 : :
3835 : : } // namespace ana
3836 : :
3837 : : #endif /* #if ENABLE_ANALYZER */
|
