Branch data Line data Source code
1 : : /* Classes for modeling the state of memory.
2 : : Copyright (C) 2020-2025 Free Software Foundation, Inc.
3 : : Contributed by David Malcolm <dmalcolm@redhat.com>.
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify it
8 : : under the terms of the GNU General Public License as published by
9 : : the Free Software Foundation; either version 3, or (at your option)
10 : : any later version.
11 : :
12 : : GCC is distributed in the hope that it will be useful, but
13 : : WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : : General Public License for more details.
16 : :
17 : : You should have received a copy of the GNU General Public License
18 : : along with GCC; see the file COPYING3. If not see
19 : : <http://www.gnu.org/licenses/>. */
20 : :
21 : : #include "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 : 3457592 : binding_key::make (store_manager *mgr, const region *r)
119 : : {
120 : 3457592 : region_offset offset = r->get_offset (mgr->get_svalue_manager ());
121 : 3457592 : if (offset.symbolic_p ())
122 : 36621 : return mgr->get_symbolic_binding (r);
123 : : else
124 : : {
125 : 3420971 : bit_size_t bit_size;
126 : 3420971 : if (r->get_bit_size (&bit_size))
127 : : {
128 : : /* Must be non-empty. */
129 : 2169693 : gcc_assert (bit_size > 0);
130 : 2169693 : return mgr->get_concrete_binding (offset.get_bit_offset (),
131 : 2169693 : bit_size);
132 : : }
133 : : else
134 : 1251278 : 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 : 4540 : binding_key::cmp (const binding_key *k1, const binding_key *k2)
173 : : {
174 : 4540 : int concrete1 = k1->concrete_p ();
175 : 4540 : int concrete2 = k2->concrete_p ();
176 : 4540 : if (int concrete_cmp = concrete1 - concrete2)
177 : : return concrete_cmp;
178 : 4540 : if (concrete1)
179 : : {
180 : 4540 : const concrete_binding *b1 = (const concrete_binding *)k1;
181 : 4540 : const concrete_binding *b2 = (const concrete_binding *)k2;
182 : 4540 : if (int start_cmp = wi::cmp (b1->get_start_bit_offset (),
183 : 4540 : b2->get_start_bit_offset (),
184 : : SIGNED))
185 : : return start_cmp;
186 : 1552 : 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 : 40074 : bit_range::contains_p (const bit_range &other, bit_range *out) const
251 : : {
252 : 40074 : if (contains_p (other.get_start_bit_offset ())
253 : 40074 : && contains_p (other.get_last_bit_offset ()))
254 : : {
255 : 27032 : if (out)
256 : : {
257 : 27032 : out->m_start_bit_offset = other.m_start_bit_offset - m_start_bit_offset;
258 : 27032 : out->m_size_in_bits = other.m_size_in_bits;
259 : : }
260 : 27032 : 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 : 632365 : bit_range::exceeds_p (const bit_range &other,
330 : : bit_range *out_overhanging_bit_range) const
331 : : {
332 : 632365 : gcc_assert (!empty_p ());
333 : :
334 : 632365 : if (other.get_next_bit_offset () < get_next_bit_offset ())
335 : : {
336 : : /* THIS definitely exceeds OTHER. */
337 : 464 : bit_offset_t start = MAX (get_start_bit_offset (),
338 : : other.get_next_bit_offset ());
339 : 464 : bit_offset_t size = get_next_bit_offset () - start;
340 : 464 : 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 : 444 : out_overhanging_bit_range->m_start_bit_offset = start;
345 : 444 : out_overhanging_bit_range->m_size_in_bits = size;
346 : 444 : 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 : 635332 : bit_range::falls_short_of_p (bit_offset_t offset,
357 : : bit_range *out_fall_short_bits) const
358 : : {
359 : 635332 : gcc_assert (!empty_p ());
360 : :
361 : 635332 : if (get_start_bit_offset () < offset)
362 : : {
363 : : /* THIS falls short of OFFSET. */
364 : 192 : bit_offset_t start = get_start_bit_offset ();
365 : 192 : bit_offset_t size = MIN (offset, get_next_bit_offset ()) - start;
366 : 192 : 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 : 172 : out_fall_short_bits->m_start_bit_offset = start;
371 : 172 : out_fall_short_bits->m_size_in_bits = size;
372 : 172 : return true;
373 : : }
374 : : else
375 : : return false;
376 : : }
377 : :
378 : : int
379 : 322 : bit_range::cmp (const bit_range &br1, const bit_range &br2)
380 : : {
381 : 322 : if (int start_cmp = wi::cmps (br1.m_start_bit_offset,
382 : 322 : 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 : 7590 : bit_range::as_byte_range (byte_range *out) const
460 : : {
461 : 7590 : if (m_start_bit_offset % BITS_PER_UNIT == 0
462 : 7590 : && m_size_in_bits % BITS_PER_UNIT == 0)
463 : : {
464 : 7571 : out->m_start_byte_offset = m_start_bit_offset / BITS_PER_UNIT;
465 : 7571 : out->m_size_in_bytes = m_size_in_bits / BITS_PER_UNIT;
466 : 7571 : 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 : 627 : byte_range::contains_p (const byte_range &other, byte_range *out) const
525 : : {
526 : 627 : if (contains_p (other.get_start_byte_offset ())
527 : 627 : && contains_p (other.get_last_byte_offset ()))
528 : : {
529 : 316 : out->m_start_byte_offset = other.m_start_byte_offset - m_start_byte_offset;
530 : 316 : out->m_size_in_bytes = other.m_size_in_bytes;
531 : 316 : return true;
532 : : }
533 : : else
534 : 311 : 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 : 105413 : concrete_binding::overlaps_p (const concrete_binding &other) const
565 : : {
566 : 105413 : if (get_start_bit_offset () < other.get_next_bit_offset ()
567 : 105413 : && get_next_bit_offset () > other.get_start_bit_offset ())
568 : 65224 : 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 : 383378 : simplify_for_binding (const svalue *sval)
636 : : {
637 : 383378 : if (const svalue *cast_sval = sval->maybe_undo_cast ())
638 : 0 : sval = cast_sval;
639 : 60981 : return sval;
640 : : }
641 : :
642 : : /* class binding_map. */
643 : :
644 : : /* binding_map's copy ctor. */
645 : :
646 : 23846057 : binding_map::binding_map (const binding_map &other)
647 : 23846057 : : m_map (other.m_map)
648 : : {
649 : 23846057 : }
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 : 1964734 : binding_map::operator== (const binding_map &other) const
672 : : {
673 : 1964734 : if (m_map.elements () != other.m_map.elements ())
674 : : return false;
675 : :
676 : 5934218 : for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
677 : : {
678 : 2027831 : const binding_key *key = (*iter).first;
679 : 2027831 : const svalue *sval = (*iter).second;
680 : 2027831 : const svalue **other_slot
681 : 2027831 : = const_cast <map_t &> (other.m_map).get (key);
682 : 2027831 : if (other_slot == NULL)
683 : 35254 : return false;
684 : 2021277 : if (sval != *other_slot)
685 : : return false;
686 : : }
687 : 1913810 : 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 : 17377198 : binding_map::hash () const
695 : : {
696 : 17377198 : hashval_t result = 0;
697 : 35381382 : 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 : 18004184 : inchash::hash hstate;
702 : 18004184 : hstate.add_ptr ((*iter).first);
703 : 18004184 : hstate.add_ptr ((*iter).second);
704 : 18004184 : result ^= hstate.end ();
705 : : }
706 : 17377198 : 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 : 16 : binding_map::cmp (const binding_map &map1, const binding_map &map2)
853 : : {
854 : 16 : if (int count_cmp = map1.elements () - map2.elements ())
855 : : return count_cmp;
856 : :
857 : 16 : auto_vec <const binding_key *> keys1 (map1.elements ());
858 : 16 : for (map_t::iterator iter = map1.begin ();
859 : 48 : iter != map1.end (); ++iter)
860 : 16 : keys1.quick_push ((*iter).first);
861 : 16 : keys1.qsort (binding_key::cmp_ptrs);
862 : :
863 : 16 : auto_vec <const binding_key *> keys2 (map2.elements ());
864 : 16 : for (map_t::iterator iter = map2.begin ();
865 : 48 : iter != map2.end (); ++iter)
866 : 16 : keys2.quick_push ((*iter).first);
867 : 16 : keys2.qsort (binding_key::cmp_ptrs);
868 : :
869 : 32 : for (size_t i = 0; i < keys1.length (); i++)
870 : : {
871 : 16 : const binding_key *k1 = keys1[i];
872 : 16 : const binding_key *k2 = keys2[i];
873 : 16 : if (int key_cmp = binding_key::cmp (k1, k2))
874 : : return key_cmp;
875 : 16 : gcc_assert (k1 == k2);
876 : 48 : if (int sval_cmp = svalue::cmp_ptr (map1.get (k1), map2.get (k2)))
877 : : return sval_cmp;
878 : : }
879 : :
880 : : return 0;
881 : 16 : }
882 : :
883 : : /* Get the child region of PARENT_REG based upon INDEX within a
884 : : CONSTRUCTOR. */
885 : :
886 : : static const region *
887 : 454 : get_subregion_within_ctor (const region *parent_reg, tree index,
888 : : region_model_manager *mgr)
889 : : {
890 : 454 : switch (TREE_CODE (index))
891 : : {
892 : 0 : default:
893 : 0 : gcc_unreachable ();
894 : 400 : case INTEGER_CST:
895 : 400 : {
896 : 400 : const svalue *index_sval
897 : 400 : = mgr->get_or_create_constant_svalue (index);
898 : 400 : return mgr->get_element_region (parent_reg,
899 : 400 : TREE_TYPE (parent_reg->get_type ()),
900 : 400 : 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 child region of PARENT_REG based upon (INDEX, VALUE) within a
909 : : CONSTRUCTOR. */
910 : :
911 : : static const region *
912 : 454 : get_subregion_within_ctor_for_ctor_pair (const region *parent_reg,
913 : : tree index,
914 : : tree value,
915 : : region_model_manager *mgr)
916 : : {
917 : 454 : if (TREE_CODE (index) == INTEGER_CST
918 : 400 : && TREE_CODE (value) == RAW_DATA_CST)
919 : : {
920 : : /* Special-case; see tree.def's description of CONSTRUCTOR.
921 : : We have RAW_DATA_LENGTH of bytes, starting at INDEX's start. */
922 : 14 : const region *start_reg
923 : 14 : = get_subregion_within_ctor (parent_reg, index, mgr);
924 : : /* Build a bit range, relative to PARENT_REG. */
925 : 14 : region_offset start_offset = start_reg->get_offset (mgr);
926 : :
927 : 14 : if (!start_offset.concrete_p ())
928 : : return nullptr;
929 : 14 : bit_offset_t start_bit_offset = start_offset.get_bit_offset ();
930 : 14 : int length = RAW_DATA_LENGTH (value);
931 : 14 : bit_range bits (start_bit_offset, length * BITS_PER_UNIT);
932 : :
933 : 14 : return mgr->get_bit_range (parent_reg, NULL_TREE, bits);
934 : : }
935 : :
936 : 440 : return get_subregion_within_ctor (parent_reg, index, mgr);
937 : : }
938 : :
939 : : /* Get the svalue for VAL, a non-CONSTRUCTOR value within a CONSTRUCTOR. */
940 : :
941 : : static const svalue *
942 : 415 : get_svalue_for_ctor_val (tree val, region_model_manager *mgr)
943 : : {
944 : : /* Reuse the get_rvalue logic from region_model. */
945 : 415 : region_model m (mgr);
946 : 415 : return m.get_rvalue (path_var (val, 0), NULL);
947 : 415 : }
948 : :
949 : : /* Bind values from CONSTRUCTOR to this map, relative to
950 : : PARENT_REG's relationship to its base region.
951 : : Return true if successful, false if there was a problem (e.g. due
952 : : to hitting a complexity limit). */
953 : :
954 : : bool
955 : 157 : binding_map::apply_ctor_to_region (const region *parent_reg, tree ctor,
956 : : region_model_manager *mgr)
957 : : {
958 : 157 : gcc_assert (parent_reg);
959 : 157 : gcc_assert (TREE_CODE (ctor) == CONSTRUCTOR);
960 : :
961 : 157 : unsigned ix;
962 : 157 : tree index;
963 : 157 : tree val;
964 : 157 : tree parent_type = parent_reg->get_type ();
965 : 157 : tree field;
966 : 157 : if (TREE_CODE (parent_type) == RECORD_TYPE)
967 : 48 : field = TYPE_FIELDS (parent_type);
968 : : else
969 : : field = NULL_TREE;
970 : 610 : FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), ix, index, val)
971 : : {
972 : 454 : if (!index)
973 : : {
974 : : /* If index is NULL, then iterate through the fields for
975 : : a RECORD_TYPE, or use an INTEGER_CST otherwise.
976 : : Compare with similar logic in output_constructor. */
977 : 135 : if (field)
978 : : {
979 : 0 : index = field;
980 : 0 : field = DECL_CHAIN (field);
981 : : }
982 : : else
983 : 135 : index = build_int_cst (integer_type_node, ix);
984 : : }
985 : 319 : else if (TREE_CODE (index) == RANGE_EXPR)
986 : : {
987 : 0 : tree min_index = TREE_OPERAND (index, 0);
988 : 0 : tree max_index = TREE_OPERAND (index, 1);
989 : 0 : if (min_index == max_index)
990 : : {
991 : 0 : if (!apply_ctor_pair_to_child_region (parent_reg, mgr,
992 : : min_index, val))
993 : : return false;
994 : : }
995 : : else
996 : : {
997 : 0 : if (!apply_ctor_val_to_range (parent_reg, mgr,
998 : : min_index, max_index, val))
999 : : return false;
1000 : : }
1001 : 0 : continue;
1002 : 0 : }
1003 : 454 : if (!apply_ctor_pair_to_child_region (parent_reg, mgr, index, val))
1004 : : return false;
1005 : : }
1006 : : return true;
1007 : : }
1008 : :
1009 : : /* Bind the value VAL into the range of elements within PARENT_REF
1010 : : from MIN_INDEX to MAX_INDEX (including endpoints).
1011 : : For use in handling RANGE_EXPR within a CONSTRUCTOR.
1012 : : Return true if successful, false if there was a problem (e.g. due
1013 : : to hitting a complexity limit). */
1014 : :
1015 : : bool
1016 : 0 : binding_map::apply_ctor_val_to_range (const region *parent_reg,
1017 : : region_model_manager *mgr,
1018 : : tree min_index, tree max_index,
1019 : : tree val)
1020 : : {
1021 : 0 : gcc_assert (TREE_CODE (min_index) == INTEGER_CST);
1022 : 0 : gcc_assert (TREE_CODE (max_index) == INTEGER_CST);
1023 : :
1024 : : /* Generate a binding key for the range. */
1025 : 0 : const region *min_element
1026 : 0 : = get_subregion_within_ctor (parent_reg, min_index, mgr);
1027 : 0 : const region *max_element
1028 : 0 : = get_subregion_within_ctor (parent_reg, max_index, mgr);
1029 : 0 : region_offset min_offset = min_element->get_offset (mgr);
1030 : 0 : if (min_offset.symbolic_p ())
1031 : : return false;
1032 : 0 : bit_offset_t start_bit_offset = min_offset.get_bit_offset ();
1033 : 0 : store_manager *smgr = mgr->get_store_manager ();
1034 : 0 : if (max_element->empty_p ())
1035 : : return false;
1036 : 0 : const binding_key *max_element_key = binding_key::make (smgr, max_element);
1037 : 0 : if (max_element_key->symbolic_p ())
1038 : : return false;
1039 : 0 : const concrete_binding *max_element_ckey
1040 : 0 : = max_element_key->dyn_cast_concrete_binding ();
1041 : 0 : bit_size_t range_size_in_bits
1042 : 0 : = max_element_ckey->get_next_bit_offset () - start_bit_offset;
1043 : 0 : const concrete_binding *range_key
1044 : 0 : = smgr->get_concrete_binding (start_bit_offset, range_size_in_bits);
1045 : 0 : if (range_key->symbolic_p ())
1046 : : return false;
1047 : :
1048 : : /* Get the value. */
1049 : 0 : if (TREE_CODE (val) == CONSTRUCTOR)
1050 : : return false;
1051 : 0 : const svalue *sval = get_svalue_for_ctor_val (val, mgr);
1052 : :
1053 : : /* Bind the value to the range. */
1054 : 0 : put (range_key, sval);
1055 : 0 : return true;
1056 : : }
1057 : :
1058 : : /* Bind the value VAL into INDEX within PARENT_REF.
1059 : : For use in handling a pair of entries within a CONSTRUCTOR.
1060 : : Return true if successful, false if there was a problem (e.g. due
1061 : : to hitting a complexity limit). */
1062 : :
1063 : : bool
1064 : 454 : binding_map::apply_ctor_pair_to_child_region (const region *parent_reg,
1065 : : region_model_manager *mgr,
1066 : : tree index, tree val)
1067 : : {
1068 : 454 : const region *child_reg
1069 : 454 : = get_subregion_within_ctor_for_ctor_pair (parent_reg, index, val, mgr);
1070 : 454 : if (!child_reg)
1071 : : return false;
1072 : 454 : if (TREE_CODE (val) == CONSTRUCTOR)
1073 : 39 : return apply_ctor_to_region (child_reg, val, mgr);
1074 : : else
1075 : : {
1076 : 415 : const svalue *sval = get_svalue_for_ctor_val (val, mgr);
1077 : 415 : if (child_reg->empty_p ())
1078 : : return false;
1079 : 415 : const binding_key *k
1080 : 415 : = binding_key::make (mgr->get_store_manager (), child_reg);
1081 : : /* Handle the case where we have an unknown size for child_reg
1082 : : (e.g. due to it being a trailing field with incomplete array
1083 : : type. */
1084 : 415 : if (!k->concrete_p ())
1085 : : {
1086 : : /* Assume that sval has a well-defined size for this case. */
1087 : 5 : tree sval_type = sval->get_type ();
1088 : 5 : gcc_assert (sval_type);
1089 : 5 : HOST_WIDE_INT sval_byte_size = int_size_in_bytes (sval_type);
1090 : 5 : gcc_assert (sval_byte_size != -1);
1091 : 5 : bit_size_t sval_bit_size = sval_byte_size * BITS_PER_UNIT;
1092 : : /* Get offset of child relative to base region. */
1093 : 5 : region_offset child_base_offset = child_reg->get_offset (mgr);
1094 : 5 : if (child_base_offset.symbolic_p ())
1095 : 1 : return false;
1096 : : /* Convert to an offset relative to the parent region. */
1097 : 4 : region_offset parent_base_offset = parent_reg->get_offset (mgr);
1098 : 4 : gcc_assert (!parent_base_offset.symbolic_p ());
1099 : 4 : bit_offset_t child_parent_offset
1100 : 4 : = (child_base_offset.get_bit_offset ()
1101 : 4 : - parent_base_offset.get_bit_offset ());
1102 : : /* Create a concrete key for the child within the parent. */
1103 : 4 : k = mgr->get_store_manager ()->get_concrete_binding
1104 : 4 : (child_parent_offset, sval_bit_size);
1105 : : }
1106 : 414 : gcc_assert (k->concrete_p ());
1107 : 414 : put (k, sval);
1108 : 414 : return true;
1109 : : }
1110 : : }
1111 : :
1112 : : /* Populate OUT with all bindings within this map that overlap KEY. */
1113 : :
1114 : : void
1115 : 41311 : binding_map::get_overlapping_bindings (const binding_key *key,
1116 : : auto_vec<const binding_key *> *out)
1117 : : {
1118 : 193451 : for (auto iter : *this)
1119 : : {
1120 : 76070 : const binding_key *iter_key = iter.first;
1121 : 152140 : if (const concrete_binding *ckey
1122 : 76070 : = key->dyn_cast_concrete_binding ())
1123 : : {
1124 : 146914 : if (const concrete_binding *iter_ckey
1125 : 73457 : = iter_key->dyn_cast_concrete_binding ())
1126 : : {
1127 : 72705 : if (ckey->overlaps_p (*iter_ckey))
1128 : 32556 : out->safe_push (iter_key);
1129 : : }
1130 : : else
1131 : : {
1132 : : /* Assume overlap. */
1133 : 752 : out->safe_push (iter_key);
1134 : : }
1135 : : }
1136 : : else
1137 : : {
1138 : : /* Assume overlap. */
1139 : 2613 : out->safe_push (iter_key);
1140 : : }
1141 : : }
1142 : 41311 : }
1143 : :
1144 : : /* Remove, truncate, and/or split any bindings within this map that
1145 : : overlap DROP_KEY.
1146 : :
1147 : : For example, if we have:
1148 : :
1149 : : +------------------------------------+
1150 : : | old binding |
1151 : : +------------------------------------+
1152 : :
1153 : : which is to be overwritten with:
1154 : :
1155 : : .......+----------------------+.......
1156 : : .......| new binding |.......
1157 : : .......+----------------------+.......
1158 : :
1159 : : this function "cuts a hole" out of the old binding:
1160 : :
1161 : : +------+......................+------+
1162 : : |prefix| hole for new binding |suffix|
1163 : : +------+......................+------+
1164 : :
1165 : : into which the new binding can be added without
1166 : : overlapping the prefix or suffix.
1167 : :
1168 : : The prefix and suffix (if added) will be bound to the pertinent
1169 : : parts of the value of the old binding.
1170 : :
1171 : : For example, given:
1172 : : struct s5
1173 : : {
1174 : : char arr[8];
1175 : : };
1176 : : void test_5 (struct s5 *p)
1177 : : {
1178 : : struct s5 f = *p;
1179 : : f.arr[3] = 42;
1180 : : }
1181 : : then after the "f = *p;" we have:
1182 : : cluster for: f: INIT_VAL((*INIT_VAL(p_33(D))))
1183 : : and at the "f.arr[3] = 42;" we remove the bindings overlapping
1184 : : "f.arr[3]", replacing it with a prefix (bytes 0-2) and suffix (bytes 4-7)
1185 : : giving:
1186 : : cluster for: f
1187 : : key: {bytes 0-2}
1188 : : value: {BITS_WITHIN(bytes 0-2, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
1189 : : key: {bytes 4-7}
1190 : : value: {BITS_WITHIN(bytes 4-7, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
1191 : : punching a hole into which the new value can be written at byte 3:
1192 : : cluster for: f
1193 : : key: {bytes 0-2}
1194 : : value: {BITS_WITHIN(bytes 0-2, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
1195 : : key: {byte 3}
1196 : : value: 'char' {(char)42}
1197 : : key: {bytes 4-7}
1198 : : value: {BITS_WITHIN(bytes 4-7, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
1199 : :
1200 : : If UNCERTAINTY is non-NULL, use it to record any svalues that
1201 : : were removed, as being maybe-bound.
1202 : :
1203 : : If MAYBE_LIVE_VALUES is non-NULL, then use it to record any svalues that
1204 : : were removed as being maybe-live.
1205 : :
1206 : : If ALWAYS_OVERLAP, then assume that DROP_KEY can overlap anything
1207 : : in the map, due to one or both of the underlying clusters being
1208 : : symbolic (but not the same symbolic region). Hence even if DROP_KEY is a
1209 : : concrete binding it could actually be referring to the same memory as
1210 : : distinct concrete bindings in the map. Remove all bindings, but
1211 : : register any svalues with *UNCERTAINTY. */
1212 : :
1213 : : void
1214 : 103066 : binding_map::remove_overlapping_bindings (store_manager *mgr,
1215 : : const binding_key *drop_key,
1216 : : uncertainty_t *uncertainty,
1217 : : svalue_set *maybe_live_values,
1218 : : bool always_overlap)
1219 : : {
1220 : : /* Get the bindings of interest within this map. */
1221 : 103066 : auto_vec<const binding_key *> bindings;
1222 : 103066 : if (always_overlap)
1223 : 186172 : for (auto iter : *this)
1224 : 62662 : bindings.safe_push (iter.first); /* Add all bindings. */
1225 : : else
1226 : : /* Just add overlapping bindings. */
1227 : 41311 : get_overlapping_bindings (drop_key, &bindings);
1228 : :
1229 : : unsigned i;
1230 : : const binding_key *iter_binding;
1231 : 292854 : FOR_EACH_VEC_ELT (bindings, i, iter_binding)
1232 : : {
1233 : : /* Record any svalues that were removed to *UNCERTAINTY as being
1234 : : maybe-bound, provided at least some part of the binding is symbolic.
1235 : :
1236 : : Specifically, if at least one of the bindings is symbolic, or we
1237 : : have ALWAYS_OVERLAP for the case where we have possibly aliasing
1238 : : regions, then we don't know that the svalue has been overwritten,
1239 : : and should record that to *UNCERTAINTY.
1240 : :
1241 : : However, if we have concrete keys accessing within the same symbolic
1242 : : region, then we *know* that the symbolic region has been overwritten,
1243 : : so we don't record it to *UNCERTAINTY, as this could be a genuine
1244 : : leak. */
1245 : 98583 : const svalue *old_sval = get (iter_binding);
1246 : 98583 : if (uncertainty
1247 : 127871 : && (drop_key->symbolic_p ()
1248 : 26982 : || iter_binding->symbolic_p ()
1249 : 23034 : || always_overlap))
1250 : 25478 : uncertainty->on_maybe_bound_sval (old_sval);
1251 : :
1252 : : /* Record any svalues that were removed to *MAYBE_LIVE_VALUES as being
1253 : : maybe-live. */
1254 : 98583 : if (maybe_live_values)
1255 : 62662 : maybe_live_values->add (old_sval);
1256 : :
1257 : : /* Begin by removing the old binding. */
1258 : 98583 : m_map.remove (iter_binding);
1259 : :
1260 : : /* Don't attempt to handle prefixes/suffixes for the
1261 : : "always_overlap" case; everything's being removed. */
1262 : 98583 : if (always_overlap)
1263 : 62662 : continue;
1264 : :
1265 : : /* Now potentially add the prefix and suffix. */
1266 : 71842 : if (const concrete_binding *drop_ckey
1267 : 35921 : = drop_key->dyn_cast_concrete_binding ())
1268 : 66616 : if (const concrete_binding *iter_ckey
1269 : 33308 : = iter_binding->dyn_cast_concrete_binding ())
1270 : : {
1271 : 32556 : gcc_assert (drop_ckey->overlaps_p (*iter_ckey));
1272 : :
1273 : 32556 : const bit_range &drop_bits = drop_ckey->get_bit_range ();
1274 : 32556 : const bit_range &iter_bits = iter_ckey->get_bit_range ();
1275 : :
1276 : 32556 : if (iter_bits.get_start_bit_offset ()
1277 : 32556 : < drop_bits.get_start_bit_offset ())
1278 : : {
1279 : : /* We have a truncated prefix. */
1280 : 6385 : bit_range prefix_bits (iter_bits.get_start_bit_offset (),
1281 : 12770 : (drop_bits.get_start_bit_offset ()
1282 : 6385 : - iter_bits.get_start_bit_offset ()));
1283 : 6385 : const concrete_binding *prefix_key
1284 : 6385 : = mgr->get_concrete_binding (prefix_bits);
1285 : 6385 : bit_range rel_prefix (0, prefix_bits.m_size_in_bits);
1286 : 6385 : const svalue *prefix_sval
1287 : 6385 : = old_sval->extract_bit_range (NULL_TREE,
1288 : : rel_prefix,
1289 : 6385 : mgr->get_svalue_manager ());
1290 : 6385 : m_map.put (prefix_key, prefix_sval);
1291 : : }
1292 : :
1293 : 65112 : if (iter_bits.get_next_bit_offset ()
1294 : 65112 : > drop_bits.get_next_bit_offset ())
1295 : : {
1296 : : /* We have a truncated suffix. */
1297 : 6695 : bit_range suffix_bits (drop_bits.get_next_bit_offset (),
1298 : 6695 : (iter_bits.get_next_bit_offset ()
1299 : 13390 : - drop_bits.get_next_bit_offset ()));
1300 : 6695 : const concrete_binding *suffix_key
1301 : 6695 : = mgr->get_concrete_binding (suffix_bits);
1302 : 6695 : bit_range rel_suffix (drop_bits.get_next_bit_offset ()
1303 : 6695 : - iter_bits.get_start_bit_offset (),
1304 : 6695 : suffix_bits.m_size_in_bits);
1305 : 6695 : const svalue *suffix_sval
1306 : 6695 : = old_sval->extract_bit_range (NULL_TREE,
1307 : : rel_suffix,
1308 : 6695 : mgr->get_svalue_manager ());
1309 : 6695 : m_map.put (suffix_key, suffix_sval);
1310 : : }
1311 : : }
1312 : : }
1313 : 103066 : }
1314 : :
1315 : : /* class binding_cluster. */
1316 : :
1317 : 1443766 : binding_cluster::binding_cluster (const region *base_region)
1318 : 1443766 : : m_base_region (base_region), m_map (),
1319 : 1443766 : m_escaped (false), m_touched (false)
1320 : : {
1321 : 1443766 : }
1322 : :
1323 : : /* binding_cluster's copy ctor. */
1324 : :
1325 : 23845420 : binding_cluster::binding_cluster (const binding_cluster &other)
1326 : 23845420 : : m_base_region (other.m_base_region), m_map (other.m_map),
1327 : 23845420 : m_escaped (other.m_escaped), m_touched (other.m_touched)
1328 : : {
1329 : 23845420 : }
1330 : :
1331 : : /* binding_cluster's assignment operator. */
1332 : :
1333 : : binding_cluster&
1334 : 0 : binding_cluster::operator= (const binding_cluster &other)
1335 : : {
1336 : 0 : gcc_assert (m_base_region == other.m_base_region);
1337 : 0 : m_map = other.m_map;
1338 : 0 : m_escaped = other.m_escaped;
1339 : 0 : m_touched = other.m_touched;
1340 : 0 : return *this;
1341 : : }
1342 : :
1343 : : /* binding_cluster's equality operator. */
1344 : :
1345 : : bool
1346 : 1938062 : binding_cluster::operator== (const binding_cluster &other) const
1347 : : {
1348 : 1938062 : if (m_map != other.m_map)
1349 : : return false;
1350 : :
1351 : 1908424 : if (m_base_region != other.m_base_region)
1352 : : return false;
1353 : :
1354 : 1908424 : if (m_escaped != other.m_escaped)
1355 : : return false;
1356 : :
1357 : 1907760 : if (m_touched != other.m_touched)
1358 : : return false;
1359 : :
1360 : 1906293 : gcc_checking_assert (hash () == other.hash ());
1361 : :
1362 : : return true;
1363 : : }
1364 : :
1365 : : /* Generate a hash value for this binding_cluster. */
1366 : :
1367 : : hashval_t
1368 : 13549578 : binding_cluster::hash () const
1369 : : {
1370 : 13549578 : return m_map.hash ();
1371 : : }
1372 : :
1373 : : /* Return true if this binding_cluster is symbolic
1374 : : i.e. its base region is symbolic. */
1375 : :
1376 : : bool
1377 : 7610670 : binding_cluster::symbolic_p () const
1378 : : {
1379 : 7610670 : return m_base_region->get_kind () == RK_SYMBOLIC;
1380 : : }
1381 : :
1382 : : /* Dump a representation of this binding_cluster to PP.
1383 : : SIMPLE controls how values and regions are to be printed.
1384 : : If MULTILINE, then split the dump over multiple lines and
1385 : : use whitespace for readability, otherwise put all on one line. */
1386 : :
1387 : : void
1388 : 2173 : binding_cluster::dump_to_pp (pretty_printer *pp, bool simple,
1389 : : bool multiline) const
1390 : : {
1391 : 2173 : if (m_escaped)
1392 : : {
1393 : 1422 : if (multiline)
1394 : : {
1395 : 1240 : pp_string (pp, " ESCAPED");
1396 : 1240 : pp_newline (pp);
1397 : : }
1398 : : else
1399 : 182 : pp_string (pp, "(ESCAPED)");
1400 : : }
1401 : 2173 : if (m_touched)
1402 : : {
1403 : 306 : if (multiline)
1404 : : {
1405 : 124 : pp_string (pp, " TOUCHED");
1406 : 124 : pp_newline (pp);
1407 : : }
1408 : : else
1409 : 182 : pp_string (pp, "(TOUCHED)");
1410 : : }
1411 : :
1412 : 2173 : m_map.dump_to_pp (pp, simple, multiline);
1413 : 2173 : }
1414 : :
1415 : : /* Dump a multiline representation of this binding_cluster to stderr. */
1416 : :
1417 : : DEBUG_FUNCTION void
1418 : 0 : binding_cluster::dump (bool simple) const
1419 : : {
1420 : 0 : tree_dump_pretty_printer pp (stderr);
1421 : 0 : pp_string (&pp, " cluster for: ");
1422 : 0 : m_base_region->dump_to_pp (&pp, simple);
1423 : 0 : pp_string (&pp, ": ");
1424 : 0 : pp_newline (&pp);
1425 : 0 : dump_to_pp (&pp, simple, true);
1426 : 0 : pp_newline (&pp);
1427 : 0 : }
1428 : :
1429 : : /* Assert that this object is valid. */
1430 : :
1431 : : void
1432 : 8804630 : binding_cluster::validate () const
1433 : : {
1434 : 8804630 : int num_symbolic = 0;
1435 : 8804630 : int num_concrete = 0;
1436 : 27092758 : for (auto iter : m_map)
1437 : : {
1438 : 9144064 : if (iter.first->symbolic_p ())
1439 : 849265 : num_symbolic++;
1440 : : else
1441 : 8294799 : num_concrete++;
1442 : : }
1443 : : /* We shouldn't have more than one symbolic key per cluster
1444 : : (or one would have clobbered the other). */
1445 : 8804630 : gcc_assert (num_symbolic < 2);
1446 : : /* We can't have both concrete and symbolic keys. */
1447 : 8804630 : gcc_assert (num_concrete == 0 || num_symbolic == 0);
1448 : 8804630 : }
1449 : :
1450 : : /* Return a new json::object of the form
1451 : : {"escaped": true/false,
1452 : : "touched": true/false,
1453 : : "map" : object for the binding_map. */
1454 : :
1455 : : std::unique_ptr<json::object>
1456 : 0 : binding_cluster::to_json () const
1457 : : {
1458 : 0 : auto cluster_obj = ::make_unique<json::object> ();
1459 : :
1460 : 0 : cluster_obj->set_bool ("escaped", m_escaped);
1461 : 0 : cluster_obj->set_bool ("touched", m_touched);
1462 : 0 : cluster_obj->set ("map", m_map.to_json ());
1463 : :
1464 : 0 : return cluster_obj;
1465 : : }
1466 : :
1467 : : std::unique_ptr<text_art::tree_widget>
1468 : 0 : binding_cluster::make_dump_widget (const text_art::dump_widget_info &dwi,
1469 : : store_manager *mgr) const
1470 : : {
1471 : 0 : pretty_printer the_pp;
1472 : 0 : pretty_printer * const pp = &the_pp;
1473 : 0 : pp_format_decoder (pp) = default_tree_printer;
1474 : 0 : pp_show_color (pp) = true;
1475 : 0 : const bool simple = true;
1476 : :
1477 : 0 : m_base_region->dump_to_pp (pp, simple);
1478 : 0 : pp_string (pp, ": ");
1479 : :
1480 : 0 : if (const svalue *sval = maybe_get_simple_value (mgr))
1481 : : {
1482 : : /* Special-case to simplify dumps for the common case where
1483 : : we just have one value directly bound to the whole of a
1484 : : region. */
1485 : 0 : sval->dump_to_pp (pp, simple);
1486 : 0 : if (escaped_p ())
1487 : 0 : pp_string (pp, " (ESCAPED)");
1488 : 0 : if (touched_p ())
1489 : 0 : pp_string (pp, " (TOUCHED)");
1490 : :
1491 : 0 : return text_art::tree_widget::make (dwi, pp);
1492 : : }
1493 : : else
1494 : : {
1495 : 0 : if (escaped_p ())
1496 : 0 : pp_string (pp, " (ESCAPED)");
1497 : 0 : if (touched_p ())
1498 : 0 : pp_string (pp, " (TOUCHED)");
1499 : :
1500 : 0 : std::unique_ptr<text_art::tree_widget> cluster_widget
1501 : 0 : (text_art::tree_widget::make (dwi, pp));
1502 : :
1503 : 0 : m_map.add_to_tree_widget (*cluster_widget, dwi);
1504 : :
1505 : 0 : return cluster_widget;
1506 : 0 : }
1507 : 0 : }
1508 : :
1509 : : /* Add a binding of SVAL of kind KIND to REG, unpacking SVAL if it is a
1510 : : compound_sval. */
1511 : :
1512 : : void
1513 : 417568 : binding_cluster::bind (store_manager *mgr,
1514 : : const region *reg, const svalue *sval)
1515 : : {
1516 : 835136 : if (const compound_svalue *compound_sval
1517 : 417568 : = sval->dyn_cast_compound_svalue ())
1518 : : {
1519 : 868 : bind_compound_sval (mgr, reg, compound_sval);
1520 : 868 : return;
1521 : : }
1522 : :
1523 : 416700 : if (reg->empty_p ())
1524 : : return;
1525 : 416700 : const binding_key *binding = binding_key::make (mgr, reg);
1526 : 416700 : bind_key (binding, sval);
1527 : : }
1528 : :
1529 : : /* Bind SVAL to KEY.
1530 : : Unpacking of compound_svalues should already have been done by the
1531 : : time this is called. */
1532 : :
1533 : : void
1534 : 420952 : binding_cluster::bind_key (const binding_key *key, const svalue *sval)
1535 : : {
1536 : 420952 : gcc_assert (sval->get_kind () != SK_COMPOUND);
1537 : :
1538 : 420952 : m_map.put (key, sval);
1539 : 420952 : if (key->symbolic_p ())
1540 : 29967 : m_touched = true;
1541 : 420952 : }
1542 : :
1543 : : /* Subroutine of binding_cluster::bind.
1544 : : Unpack compound_svals when binding them, so that we bind them
1545 : : element-wise. */
1546 : :
1547 : : void
1548 : 868 : binding_cluster::bind_compound_sval (store_manager *mgr,
1549 : : const region *reg,
1550 : : const compound_svalue *compound_sval)
1551 : : {
1552 : 868 : region_offset reg_offset
1553 : 868 : = reg->get_offset (mgr->get_svalue_manager ());
1554 : 868 : if (reg_offset.symbolic_p ())
1555 : : {
1556 : 4 : m_touched = true;
1557 : 4 : clobber_region (mgr, reg);
1558 : 4 : return;
1559 : : }
1560 : :
1561 : 3293 : for (map_t::iterator iter = compound_sval->begin ();
1562 : 6586 : iter != compound_sval->end (); ++iter)
1563 : : {
1564 : 2429 : const binding_key *iter_key = (*iter).first;
1565 : 2429 : const svalue *iter_sval = (*iter).second;
1566 : :
1567 : 4858 : if (const concrete_binding *concrete_key
1568 : 2429 : = iter_key->dyn_cast_concrete_binding ())
1569 : : {
1570 : 2429 : bit_offset_t effective_start
1571 : 2429 : = (concrete_key->get_start_bit_offset ()
1572 : 2429 : + reg_offset.get_bit_offset ());
1573 : 2429 : const concrete_binding *effective_concrete_key
1574 : 2429 : = mgr->get_concrete_binding (effective_start,
1575 : : concrete_key->get_size_in_bits ());
1576 : 2429 : bind_key (effective_concrete_key, iter_sval);
1577 : : }
1578 : : else
1579 : 0 : gcc_unreachable ();
1580 : : }
1581 : : }
1582 : :
1583 : : /* Remove all bindings overlapping REG within this cluster. */
1584 : :
1585 : : void
1586 : 6366 : binding_cluster::clobber_region (store_manager *mgr, const region *reg)
1587 : : {
1588 : 6366 : remove_overlapping_bindings (mgr, reg, NULL, NULL);
1589 : 6366 : }
1590 : :
1591 : : /* Remove any bindings for REG within this cluster. */
1592 : :
1593 : : void
1594 : 179051 : binding_cluster::purge_region (store_manager *mgr, const region *reg)
1595 : : {
1596 : 179051 : gcc_assert (reg->get_kind () == RK_DECL);
1597 : 179051 : if (reg->empty_p ())
1598 : : return;
1599 : 179051 : const binding_key *binding
1600 : 179051 : = binding_key::make (mgr, const_cast<region *> (reg));
1601 : 179051 : m_map.remove (binding);
1602 : : }
1603 : :
1604 : : /* Clobber REG and fill it with repeated copies of SVAL. */
1605 : :
1606 : : void
1607 : 1437 : binding_cluster::fill_region (store_manager *mgr,
1608 : : const region *reg,
1609 : : const svalue *sval)
1610 : : {
1611 : 1437 : clobber_region (mgr, reg);
1612 : :
1613 : 1437 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
1614 : 1437 : const svalue *byte_size_sval = reg->get_byte_size_sval (sval_mgr);
1615 : 1437 : const svalue *fill_sval
1616 : 1437 : = sval_mgr->get_or_create_repeated_svalue (reg->get_type (),
1617 : : byte_size_sval, sval);
1618 : 1437 : bind (mgr, reg, fill_sval);
1619 : 1437 : }
1620 : :
1621 : : /* Clobber REG within this cluster and fill it with zeroes. */
1622 : :
1623 : : void
1624 : 33 : binding_cluster::zero_fill_region (store_manager *mgr, const region *reg)
1625 : : {
1626 : 33 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
1627 : 33 : const svalue *zero_sval = sval_mgr->get_or_create_int_cst (char_type_node, 0);
1628 : 33 : fill_region (mgr, reg, zero_sval);
1629 : 33 : }
1630 : :
1631 : : /* Mark REG_TO_BIND within this cluster as being unknown.
1632 : :
1633 : : Remove any bindings overlapping REG_FOR_OVERLAP.
1634 : : If UNCERTAINTY is non-NULL, use it to record any svalues that
1635 : : had bindings to them removed, as being maybe-bound.
1636 : : If MAYBE_LIVE_VALUES is non-NULL, use it to record any svalues that
1637 : : had bindings to them removed, as being maybe-live.
1638 : :
1639 : : REG_TO_BIND and REG_FOR_OVERLAP are the same for
1640 : : store::mark_region_as_unknown, but are different in
1641 : : store::set_value's alias handling, for handling the case where
1642 : : we have a write to a symbolic REG_FOR_OVERLAP. */
1643 : :
1644 : : void
1645 : 62044 : binding_cluster::mark_region_as_unknown (store_manager *mgr,
1646 : : const region *reg_to_bind,
1647 : : const region *reg_for_overlap,
1648 : : uncertainty_t *uncertainty,
1649 : : svalue_set *maybe_live_values)
1650 : : {
1651 : 62044 : if (reg_to_bind->empty_p ())
1652 : : return;
1653 : :
1654 : 62044 : remove_overlapping_bindings (mgr, reg_for_overlap, uncertainty,
1655 : : maybe_live_values);
1656 : :
1657 : : /* Add a default binding to "unknown". */
1658 : 62044 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
1659 : 62044 : const svalue *sval
1660 : 62044 : = sval_mgr->get_or_create_unknown_svalue (reg_to_bind->get_type ());
1661 : 62044 : bind (mgr, reg_to_bind, sval);
1662 : : }
1663 : :
1664 : : /* Purge state involving SVAL. */
1665 : :
1666 : : void
1667 : 561530 : binding_cluster::purge_state_involving (const svalue *sval,
1668 : : region_model_manager *sval_mgr)
1669 : : {
1670 : 561530 : auto_vec<const binding_key *> to_remove;
1671 : 561530 : auto_vec<std::pair<const binding_key *, tree> > to_make_unknown;
1672 : 1688958 : for (auto iter : m_map)
1673 : : {
1674 : 563714 : const binding_key *iter_key = iter.first;
1675 : 1127428 : if (const symbolic_binding *symbolic_key
1676 : 563714 : = iter_key->dyn_cast_symbolic_binding ())
1677 : : {
1678 : 65698 : const region *reg = symbolic_key->get_region ();
1679 : 65698 : if (reg->involves_p (sval))
1680 : 0 : to_remove.safe_push (iter_key);
1681 : : }
1682 : 563714 : const svalue *iter_sval = iter.second;
1683 : 563714 : if (iter_sval->involves_p (sval))
1684 : 4279 : to_make_unknown.safe_push (std::make_pair(iter_key,
1685 : 4279 : iter_sval->get_type ()));
1686 : : }
1687 : 561530 : for (auto iter : to_remove)
1688 : : {
1689 : 0 : m_map.remove (iter);
1690 : 0 : m_touched = true;
1691 : : }
1692 : 574367 : for (auto iter : to_make_unknown)
1693 : : {
1694 : 4279 : const svalue *new_sval
1695 : 4279 : = sval_mgr->get_or_create_unknown_svalue (iter.second);
1696 : 4279 : m_map.put (iter.first, new_sval);
1697 : : }
1698 : 561530 : }
1699 : :
1700 : : /* Get any SVAL bound to REG within this cluster via kind KIND,
1701 : : without checking parent regions of REG. */
1702 : :
1703 : : const svalue *
1704 : 1398552 : binding_cluster::get_binding (store_manager *mgr,
1705 : : const region *reg) const
1706 : : {
1707 : 1398552 : if (reg->empty_p ())
1708 : : return NULL;
1709 : 1398552 : const binding_key *reg_binding = binding_key::make (mgr, reg);
1710 : 1398552 : const svalue *sval = m_map.get (reg_binding);
1711 : 1398552 : if (sval)
1712 : : {
1713 : : /* If we have a struct with a single field, then the binding of
1714 : : the field will equal that of the struct, and looking up e.g.
1715 : : PARENT_REG.field within:
1716 : : cluster for PARENT_REG: INIT_VAL(OTHER_REG)
1717 : : will erroneously return INIT_VAL(OTHER_REG), rather than
1718 : : SUB_VALUE(INIT_VAL(OTHER_REG), FIELD) == INIT_VAL(OTHER_REG.FIELD).
1719 : : Fix this issue by iterating upwards whilst the bindings are equal,
1720 : : expressing the lookups as subvalues.
1721 : : We have to gather a list of subregion accesses, then walk it
1722 : : in reverse to get the subvalues. */
1723 : 1093012 : auto_vec<const region *> regions;
1724 : 1102676 : while (const region *parent_reg = reg->get_parent_region ())
1725 : : {
1726 : 1102676 : const binding_key *parent_reg_binding
1727 : 1102676 : = binding_key::make (mgr, parent_reg);
1728 : 1102676 : if (parent_reg_binding == reg_binding
1729 : 12313 : && sval->get_type ()
1730 : 12301 : && reg->get_type ()
1731 : 1114977 : && sval->get_type () != reg->get_type ())
1732 : : {
1733 : 9664 : regions.safe_push (reg);
1734 : 9664 : reg = parent_reg;
1735 : : }
1736 : : else
1737 : : break;
1738 : 9664 : }
1739 : 1093012 : if (sval->get_type ()
1740 : 1083988 : && reg->get_type ()
1741 : 2176183 : && sval->get_type () == reg->get_type ())
1742 : : {
1743 : 902918 : unsigned i;
1744 : 902918 : const region *iter_reg;
1745 : 1120391 : FOR_EACH_VEC_ELT_REVERSE (regions, i, iter_reg)
1746 : : {
1747 : 9159 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
1748 : 9159 : sval = rmm_mgr->get_or_create_sub_svalue (iter_reg->get_type (),
1749 : : sval, iter_reg);
1750 : : }
1751 : : }
1752 : 1093012 : }
1753 : : return sval;
1754 : : }
1755 : :
1756 : : /* Get any SVAL bound to REG within this cluster,
1757 : : either directly for REG, or recursively checking for bindings within
1758 : : parent regions and extracting subvalues if need be. */
1759 : :
1760 : : const svalue *
1761 : 1398552 : binding_cluster::get_binding_recursive (store_manager *mgr,
1762 : : const region *reg) const
1763 : : {
1764 : 1398552 : if (const svalue *sval = get_binding (mgr, reg))
1765 : : return sval;
1766 : 305540 : if (reg != m_base_region)
1767 : 179066 : if (const region *parent_reg = reg->get_parent_region ())
1768 : 358132 : if (const svalue *parent_sval
1769 : 179066 : = get_binding_recursive (mgr, parent_reg))
1770 : : {
1771 : : /* Extract child svalue from parent svalue. */
1772 : 53787 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
1773 : 53787 : return rmm_mgr->get_or_create_sub_svalue (reg->get_type (),
1774 : 53787 : parent_sval, reg);
1775 : : }
1776 : : return NULL;
1777 : : }
1778 : :
1779 : : /* Get any value bound for REG within this cluster. */
1780 : :
1781 : : const svalue *
1782 : 1219486 : binding_cluster::get_any_binding (store_manager *mgr,
1783 : : const region *reg) const
1784 : : {
1785 : : /* Look for a direct binding. */
1786 : 2438972 : if (const svalue *direct_sval
1787 : 1219486 : = get_binding_recursive (mgr, reg))
1788 : : return direct_sval;
1789 : :
1790 : : /* If we had a write to a cluster of unknown size, we might
1791 : : have a self-binding of the whole base region with an svalue,
1792 : : where the base region is symbolic.
1793 : : Handle such cases by returning sub_svalue instances. */
1794 : 126474 : if (const svalue *cluster_sval = maybe_get_simple_value (mgr))
1795 : : {
1796 : : /* Extract child svalue from parent svalue. */
1797 : 0 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
1798 : 0 : return rmm_mgr->get_or_create_sub_svalue (reg->get_type (),
1799 : 0 : cluster_sval, reg);
1800 : : }
1801 : :
1802 : : /* If this cluster has been touched by a symbolic write, then the content
1803 : : of any subregion not currently specifically bound is "UNKNOWN". */
1804 : 126474 : if (m_touched)
1805 : : {
1806 : 4522 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
1807 : 4522 : return rmm_mgr->get_or_create_unknown_svalue (reg->get_type ());
1808 : : }
1809 : :
1810 : : /* Alternatively, if this is a symbolic read and the cluster has any bindings,
1811 : : then we don't know if we're reading those values or not, so the result
1812 : : is also "UNKNOWN". */
1813 : 121952 : if (reg->get_offset (mgr->get_svalue_manager ()).symbolic_p ()
1814 : 121952 : && m_map.elements () > 0)
1815 : : {
1816 : 571 : region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
1817 : 571 : return rmm_mgr->get_or_create_unknown_svalue (reg->get_type ());
1818 : : }
1819 : :
1820 : 121381 : if (const svalue *compound_sval = maybe_get_compound_binding (mgr, reg))
1821 : : return compound_sval;
1822 : :
1823 : : /* Otherwise, the initial value, or uninitialized. */
1824 : : return NULL;
1825 : : }
1826 : :
1827 : : /* Attempt to get a compound_svalue for the bindings within the cluster
1828 : : affecting REG (which could be the base region itself).
1829 : :
1830 : : Create a compound_svalue with the subset of bindings the affect REG,
1831 : : offsetting them so that the offsets are relative to the start of REG
1832 : : within the cluster.
1833 : :
1834 : : For example, REG could be one element within an array of structs.
1835 : :
1836 : : Return the resulting compound_svalue, or NULL if there's a problem. */
1837 : :
1838 : : const svalue *
1839 : 121381 : binding_cluster::maybe_get_compound_binding (store_manager *mgr,
1840 : : const region *reg) const
1841 : : {
1842 : 121381 : region_offset cluster_offset
1843 : 121381 : = m_base_region->get_offset (mgr->get_svalue_manager ());
1844 : 121381 : if (cluster_offset.symbolic_p ())
1845 : : return NULL;
1846 : 121381 : region_offset reg_offset = reg->get_offset (mgr->get_svalue_manager ());
1847 : 121381 : if (reg_offset.symbolic_p ())
1848 : : return NULL;
1849 : :
1850 : 96823 : if (reg->empty_p ())
1851 : : return NULL;
1852 : :
1853 : 96823 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
1854 : :
1855 : : /* We will a build the result map in two parts:
1856 : : (a) result_map, holding the concrete keys from this cluster,
1857 : :
1858 : : (b) default_map, holding the initial values for the region
1859 : : (e.g. uninitialized, initializer values, or zero), unless this
1860 : : cluster has been touched.
1861 : :
1862 : : We will populate (a), and as we do, clobber (b), trimming and
1863 : : splitting its bindings as necessary.
1864 : : Finally, we will merge (b) into (a), giving a concrete map
1865 : : that merges both the initial values and the bound values from
1866 : : the binding_cluster.
1867 : : Doing it this way reduces N for the O(N^2) intersection-finding,
1868 : : perhaps we should have a spatial-organized data structure for
1869 : : concrete keys, though. */
1870 : :
1871 : 96823 : binding_map result_map;
1872 : 96823 : binding_map default_map;
1873 : :
1874 : : /* Set up default values in default_map. */
1875 : 96823 : const svalue *default_sval;
1876 : 96823 : if (m_touched)
1877 : 0 : default_sval = sval_mgr->get_or_create_unknown_svalue (reg->get_type ());
1878 : : else
1879 : 96823 : default_sval = sval_mgr->get_or_create_initial_value (reg);
1880 : 96823 : const binding_key *default_key = binding_key::make (mgr, reg);
1881 : :
1882 : : /* Express the bit-range of the default key for REG relative to REG,
1883 : : rather than to the base region. */
1884 : 96823 : const concrete_binding *concrete_default_key
1885 : 96823 : = default_key->dyn_cast_concrete_binding ();
1886 : 96823 : if (!concrete_default_key)
1887 : : return nullptr;
1888 : 95935 : const concrete_binding *default_key_relative_to_reg
1889 : 95935 : = mgr->get_concrete_binding (0, concrete_default_key->get_size_in_bits ());
1890 : 95935 : default_map.put (default_key_relative_to_reg, default_sval);
1891 : :
1892 : 313601 : for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
1893 : : {
1894 : 121723 : const binding_key *key = (*iter).first;
1895 : 121723 : const svalue *sval = (*iter).second;
1896 : :
1897 : 243446 : if (const concrete_binding *concrete_key
1898 : 121723 : = key->dyn_cast_concrete_binding ())
1899 : : {
1900 : 121723 : const bit_range &bound_range = concrete_key->get_bit_range ();
1901 : :
1902 : 121723 : bit_size_t reg_bit_size;
1903 : 121723 : if (!reg->get_bit_size (®_bit_size))
1904 : 12890 : return NULL;
1905 : :
1906 : 121723 : bit_range reg_range (reg_offset.get_bit_offset (),
1907 : 121723 : reg_bit_size);
1908 : :
1909 : : /* Skip bindings that are outside the bit range of REG. */
1910 : 121723 : if (!bound_range.intersects_p (reg_range))
1911 : 94615 : continue;
1912 : :
1913 : : /* We shouldn't have an exact match; that should have been
1914 : : handled already. */
1915 : 27108 : gcc_assert (!(reg_range == bound_range));
1916 : :
1917 : 27108 : bit_range subrange (0, 0);
1918 : 27108 : if (reg_range.contains_p (bound_range, &subrange))
1919 : : {
1920 : : /* We have a bound range fully within REG.
1921 : : Add it to map, offsetting accordingly. */
1922 : :
1923 : : /* Get offset of KEY relative to REG, rather than to
1924 : : the cluster. */
1925 : 14142 : const concrete_binding *offset_concrete_key
1926 : 14142 : = mgr->get_concrete_binding (subrange);
1927 : 14142 : result_map.put (offset_concrete_key, sval);
1928 : :
1929 : : /* Clobber default_map, removing/trimming/spliting where
1930 : : it overlaps with offset_concrete_key. */
1931 : 14142 : default_map.remove_overlapping_bindings (mgr,
1932 : : offset_concrete_key,
1933 : : NULL, NULL, false);
1934 : : }
1935 : 12966 : else if (bound_range.contains_p (reg_range, &subrange))
1936 : : {
1937 : : /* REG is fully within the bound range, but
1938 : : is not equal to it; we're extracting a subvalue. */
1939 : 12890 : return sval->extract_bit_range (reg->get_type (),
1940 : : subrange,
1941 : 12890 : mgr->get_svalue_manager ());
1942 : : }
1943 : : else
1944 : : {
1945 : : /* REG and the bound range partially overlap. */
1946 : 76 : bit_range reg_subrange (0, 0);
1947 : 76 : bit_range bound_subrange (0, 0);
1948 : 76 : reg_range.intersects_p (bound_range,
1949 : : ®_subrange, &bound_subrange);
1950 : :
1951 : : /* Get the bits from the bound value for the bits at the
1952 : : intersection (relative to the bound value). */
1953 : 76 : const svalue *overlap_sval
1954 : 76 : = sval->extract_bit_range (NULL_TREE,
1955 : : bound_subrange,
1956 : : mgr->get_svalue_manager ());
1957 : :
1958 : : /* Get key for overlap, relative to the REG. */
1959 : 76 : const concrete_binding *overlap_concrete_key
1960 : 76 : = mgr->get_concrete_binding (reg_subrange);
1961 : 76 : result_map.put (overlap_concrete_key, overlap_sval);
1962 : :
1963 : : /* Clobber default_map, removing/trimming/spliting where
1964 : : it overlaps with overlap_concrete_key. */
1965 : 76 : default_map.remove_overlapping_bindings (mgr,
1966 : : overlap_concrete_key,
1967 : : NULL, NULL, false);
1968 : : }
1969 : : }
1970 : : else
1971 : : /* Can't handle symbolic bindings. */
1972 : : return NULL;
1973 : : }
1974 : :
1975 : 83045 : if (result_map.elements () == 0)
1976 : : return NULL;
1977 : :
1978 : : /* Merge any bindings from default_map into result_map. */
1979 : 5750 : for (auto iter : default_map)
1980 : : {
1981 : 368 : const binding_key *key = iter.first;
1982 : 368 : const svalue *sval = iter.second;
1983 : 368 : result_map.put (key, sval);
1984 : : }
1985 : :
1986 : 5382 : return sval_mgr->get_or_create_compound_svalue (reg->get_type (), result_map);
1987 : 96823 : }
1988 : :
1989 : : /* Remove, truncate, and/or split any bindings within this map that
1990 : : could overlap REG.
1991 : :
1992 : : If REG's base region or this cluster is symbolic and they're different
1993 : : base regions, then remove everything in this cluster's map, on the
1994 : : grounds that REG could be referring to the same memory as anything
1995 : : in the map.
1996 : :
1997 : : If UNCERTAINTY is non-NULL, use it to record any svalues that
1998 : : were removed, as being maybe-bound.
1999 : :
2000 : : If MAYBE_LIVE_VALUES is non-NULL, use it to record any svalues that
2001 : : were removed, as being maybe-live. */
2002 : :
2003 : : void
2004 : 88848 : binding_cluster::remove_overlapping_bindings (store_manager *mgr,
2005 : : const region *reg,
2006 : : uncertainty_t *uncertainty,
2007 : : svalue_set *maybe_live_values)
2008 : : {
2009 : 88848 : if (reg->empty_p ())
2010 : : return;
2011 : 88848 : const binding_key *reg_binding = binding_key::make (mgr, reg);
2012 : :
2013 : 88848 : const region *cluster_base_reg = get_base_region ();
2014 : 88848 : const region *other_base_reg = reg->get_base_region ();
2015 : : /* If at least one of the base regions involved is symbolic, and they're
2016 : : not the same base region, then consider everything in the map as
2017 : : potentially overlapping with reg_binding (even if it's a concrete
2018 : : binding and things in the map are concrete - they could be referring
2019 : : to the same memory when the symbolic base regions are taken into
2020 : : account). */
2021 : 88848 : bool always_overlap = (cluster_base_reg != other_base_reg
2022 : 88848 : && (cluster_base_reg->get_kind () == RK_SYMBOLIC
2023 : 28144 : || other_base_reg->get_kind () == RK_SYMBOLIC));
2024 : 88848 : m_map.remove_overlapping_bindings (mgr, reg_binding, uncertainty,
2025 : : maybe_live_values,
2026 : : always_overlap);
2027 : : }
2028 : :
2029 : : /* Attempt to merge CLUSTER_A and CLUSTER_B into OUT_CLUSTER, using
2030 : : MGR and MERGER.
2031 : : Return true if they can be merged, false otherwise. */
2032 : :
2033 : : bool
2034 : 1122746 : binding_cluster::can_merge_p (const binding_cluster *cluster_a,
2035 : : const binding_cluster *cluster_b,
2036 : : binding_cluster *out_cluster,
2037 : : store *out_store,
2038 : : store_manager *mgr,
2039 : : model_merger *merger)
2040 : : {
2041 : 1122746 : gcc_assert (out_cluster);
2042 : :
2043 : : /* Merge flags ("ESCAPED" and "TOUCHED") by setting the merged flag to
2044 : : true if either of the inputs is true. */
2045 : 1122746 : if ((cluster_a && cluster_a->m_escaped)
2046 : 726623 : || (cluster_b && cluster_b->m_escaped))
2047 : 3880 : out_cluster->m_escaped = true;
2048 : 1122746 : if ((cluster_a && cluster_a->m_touched)
2049 : 790616 : || (cluster_b && cluster_b->m_touched))
2050 : 9397 : out_cluster->m_touched = true;
2051 : :
2052 : : /* At least one of CLUSTER_A and CLUSTER_B are non-NULL, but either
2053 : : could be NULL. Handle these cases. */
2054 : 1122746 : if (cluster_a == NULL)
2055 : : {
2056 : 20695 : gcc_assert (cluster_b != NULL);
2057 : 20695 : gcc_assert (cluster_b->m_base_region == out_cluster->m_base_region);
2058 : 20695 : out_cluster->make_unknown_relative_to (cluster_b, out_store, mgr);
2059 : 20695 : return true;
2060 : : }
2061 : 1102051 : if (cluster_b == NULL)
2062 : : {
2063 : 74730 : gcc_assert (cluster_a != NULL);
2064 : 74730 : gcc_assert (cluster_a->m_base_region == out_cluster->m_base_region);
2065 : 74730 : out_cluster->make_unknown_relative_to (cluster_a, out_store, mgr);
2066 : 74730 : return true;
2067 : : }
2068 : :
2069 : : /* The "both inputs are non-NULL" case. */
2070 : 1027321 : gcc_assert (cluster_a != NULL && cluster_b != NULL);
2071 : 1027321 : gcc_assert (cluster_a->m_base_region == out_cluster->m_base_region);
2072 : 1027321 : gcc_assert (cluster_b->m_base_region == out_cluster->m_base_region);
2073 : :
2074 : 1027321 : hash_set<const binding_key *> keys;
2075 : 2194172 : for (map_t::iterator iter_a = cluster_a->m_map.begin ();
2076 : 3361023 : iter_a != cluster_a->m_map.end (); ++iter_a)
2077 : : {
2078 : 1166851 : const binding_key *key_a = (*iter_a).first;
2079 : 1166851 : keys.add (key_a);
2080 : : }
2081 : 2177705 : for (map_t::iterator iter_b = cluster_b->m_map.begin ();
2082 : 3328089 : iter_b != cluster_b->m_map.end (); ++iter_b)
2083 : : {
2084 : 1150384 : const binding_key *key_b = (*iter_b).first;
2085 : 1150384 : keys.add (key_b);
2086 : : }
2087 : 1027321 : int num_symbolic_keys = 0;
2088 : 1027321 : int num_concrete_keys = 0;
2089 : 2093221 : for (hash_set<const binding_key *>::iterator iter = keys.begin ();
2090 : 3159121 : iter != keys.end (); ++iter)
2091 : : {
2092 : 1151013 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
2093 : 1151013 : const binding_key *key = *iter;
2094 : 1151013 : const svalue *sval_a = cluster_a->get_any_value (key);
2095 : 1151013 : const svalue *sval_b = cluster_b->get_any_value (key);
2096 : :
2097 : 1151013 : if (key->symbolic_p ())
2098 : 111690 : num_symbolic_keys++;
2099 : : else
2100 : 1039323 : num_concrete_keys++;
2101 : :
2102 : 1151013 : if (sval_a == sval_b)
2103 : : {
2104 : 881080 : gcc_assert (sval_a);
2105 : 881080 : out_cluster->m_map.put (key, sval_a);
2106 : 881080 : continue;
2107 : : }
2108 : 269933 : else if (sval_a && sval_b)
2109 : : {
2110 : 520407 : if (const svalue *merged_sval
2111 : 189324 : = sval_a->can_merge_p (sval_b, sval_mgr, merger))
2112 : : {
2113 : 141759 : out_cluster->m_map.put (key, merged_sval);
2114 : 141759 : continue;
2115 : : }
2116 : : /* Merger of the svalues failed. Reject merger of the cluster. */
2117 : 85113 : return false;
2118 : : }
2119 : :
2120 : : /* If we get here, then one cluster binds this key and the other
2121 : : doesn't; merge them as "UNKNOWN". */
2122 : 80609 : gcc_assert (sval_a || sval_b);
2123 : :
2124 : 80609 : const svalue *bound_sval = sval_a ? sval_a : sval_b;
2125 : 80609 : tree type = bound_sval->get_type ();
2126 : 80609 : const svalue *unknown_sval
2127 : 80609 : = mgr->get_svalue_manager ()->get_or_create_unknown_svalue (type);
2128 : :
2129 : : /* ...but reject the merger if this sval shouldn't be mergeable
2130 : : (e.g. reject merging svalues that have non-purgable sm-state,
2131 : : to avoid falsely reporting memory leaks by merging them
2132 : : with something else). */
2133 : 80609 : if (!bound_sval->can_merge_p (unknown_sval, sval_mgr, merger))
2134 : : return false;
2135 : :
2136 : 43061 : out_cluster->m_map.put (key, unknown_sval);
2137 : : }
2138 : :
2139 : : /* We can only have at most one symbolic key per cluster,
2140 : : and if we do, we can't have any concrete keys.
2141 : : If this happens, mark the cluster as touched, with no keys. */
2142 : 942208 : if (num_symbolic_keys >= 2
2143 : 941718 : || (num_concrete_keys > 0 && num_symbolic_keys > 0))
2144 : : {
2145 : 1687 : out_cluster->m_touched = true;
2146 : 1029008 : out_cluster->m_map.empty ();
2147 : : }
2148 : :
2149 : : /* We don't handle other kinds of overlaps yet. */
2150 : :
2151 : : return true;
2152 : 1027321 : }
2153 : :
2154 : : /* Update this cluster to reflect an attempt to merge OTHER where there
2155 : : is no other cluster to merge with, and so we're notionally merging the
2156 : : bound values in OTHER with the initial value of the relevant regions.
2157 : :
2158 : : Any bound keys in OTHER should be bound to unknown in this. */
2159 : :
2160 : : void
2161 : 95425 : binding_cluster::make_unknown_relative_to (const binding_cluster *other,
2162 : : store *out_store,
2163 : : store_manager *mgr)
2164 : : {
2165 : 192716 : for (map_t::iterator iter = other->m_map.begin ();
2166 : 290007 : iter != other->m_map.end (); ++iter)
2167 : : {
2168 : 97291 : const binding_key *iter_key = (*iter).first;
2169 : 97291 : const svalue *iter_sval = (*iter).second;
2170 : 97291 : const svalue *unknown_sval
2171 : : = mgr->get_svalue_manager ()->get_or_create_unknown_svalue
2172 : 97291 : (iter_sval->get_type ());
2173 : 97291 : m_map.put (iter_key, unknown_sval);
2174 : :
2175 : : /* For any pointers in OTHER, the merger means that the
2176 : : concrete pointer becomes an unknown value, which could
2177 : : show up as a false report of a leak when considering what
2178 : : pointers are live before vs after.
2179 : : Avoid this by marking the base regions they point to as having
2180 : : escaped. */
2181 : 194582 : if (const region_svalue *region_sval
2182 : 97291 : = iter_sval->dyn_cast_region_svalue ())
2183 : : {
2184 : 5731 : const region *base_reg
2185 : 5731 : = region_sval->get_pointee ()->get_base_region ();
2186 : 5731 : if (base_reg->tracked_p ()
2187 : 5731 : && !base_reg->symbolic_for_unknown_ptr_p ())
2188 : : {
2189 : 5692 : binding_cluster *c = out_store->get_or_create_cluster (base_reg);
2190 : 5692 : c->mark_as_escaped ();
2191 : : }
2192 : : }
2193 : : }
2194 : 95425 : }
2195 : :
2196 : : /* Mark this cluster as having escaped. */
2197 : :
2198 : : void
2199 : 45094 : binding_cluster::mark_as_escaped ()
2200 : : {
2201 : 45094 : m_escaped = true;
2202 : 45094 : }
2203 : :
2204 : : /* If this cluster has escaped (by this call, or by an earlier one, or
2205 : : by being an external param), then unbind all values and mark it
2206 : : as "touched", so that it has a conjured value, rather than an
2207 : : initial_svalue.
2208 : : Use P to purge state involving conjured_svalues. */
2209 : :
2210 : : void
2211 : 163843 : binding_cluster::on_unknown_fncall (const gcall *call,
2212 : : store_manager *mgr,
2213 : : const conjured_purge &p)
2214 : : {
2215 : 163843 : if (m_escaped)
2216 : : {
2217 : 27178 : m_map.empty ();
2218 : :
2219 : 27178 : if (!m_base_region->empty_p ())
2220 : : {
2221 : : /* Bind it to a new "conjured" value using CALL. */
2222 : 27178 : const svalue *sval
2223 : : = mgr->get_svalue_manager ()->get_or_create_conjured_svalue
2224 : 27178 : (m_base_region->get_type (), call, m_base_region, p);
2225 : 27178 : bind (mgr, m_base_region, sval);
2226 : : }
2227 : :
2228 : 27178 : m_touched = true;
2229 : : }
2230 : 163843 : }
2231 : :
2232 : : /* Mark this cluster as having been clobbered by STMT.
2233 : : Use P to purge state involving conjured_svalues. */
2234 : :
2235 : : void
2236 : 522 : binding_cluster::on_asm (const gasm *stmt,
2237 : : store_manager *mgr,
2238 : : const conjured_purge &p)
2239 : : {
2240 : 522 : m_map.empty ();
2241 : :
2242 : : /* Bind it to a new "conjured" value using CALL. */
2243 : 522 : const svalue *sval
2244 : : = mgr->get_svalue_manager ()->get_or_create_conjured_svalue
2245 : 522 : (m_base_region->get_type (), stmt, m_base_region, p);
2246 : 522 : bind (mgr, m_base_region, sval);
2247 : :
2248 : 522 : m_touched = true;
2249 : 522 : }
2250 : :
2251 : : /* Return true if this cluster has escaped. */
2252 : :
2253 : : bool
2254 : 8268154 : binding_cluster::escaped_p () const
2255 : : {
2256 : : /* Consider the "errno" region to always have escaped. */
2257 : 8268154 : if (m_base_region->get_kind () == RK_ERRNO)
2258 : : return true;
2259 : 8237515 : return m_escaped;
2260 : : }
2261 : :
2262 : : /* Return true if this binding_cluster has no information
2263 : : i.e. if there are no bindings, and it hasn't been marked as having
2264 : : escaped, or touched symbolically. */
2265 : :
2266 : : bool
2267 : 183976 : binding_cluster::redundant_p () const
2268 : : {
2269 : 183976 : return (m_map.elements () == 0
2270 : 176219 : && !m_escaped
2271 : 359117 : && !m_touched);
2272 : : }
2273 : :
2274 : : /* Add PV to OUT_PVS, casting it to TYPE if it is not already of that type. */
2275 : :
2276 : : static void
2277 : 8356 : append_pathvar_with_type (path_var pv,
2278 : : tree type,
2279 : : auto_vec<path_var> *out_pvs)
2280 : : {
2281 : 8356 : gcc_assert (pv.m_tree);
2282 : :
2283 : 8356 : if (TREE_TYPE (pv.m_tree) != type)
2284 : 513 : pv.m_tree = build1 (NOP_EXPR, type, pv.m_tree);
2285 : :
2286 : 8356 : out_pvs->safe_push (pv);
2287 : 8356 : }
2288 : :
2289 : : /* Find representative path_vars for SVAL within this binding of BASE_REG,
2290 : : appending the results to OUT_PVS. */
2291 : :
2292 : : void
2293 : 60981 : binding_cluster::get_representative_path_vars (const region_model *model,
2294 : : svalue_set *visited,
2295 : : const region *base_reg,
2296 : : const svalue *sval,
2297 : : logger *logger,
2298 : : auto_vec<path_var> *out_pvs)
2299 : : const
2300 : : {
2301 : 60981 : sval = simplify_for_binding (sval);
2302 : :
2303 : 175869 : for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
2304 : : {
2305 : 57444 : const binding_key *key = (*iter).first;
2306 : 57444 : const svalue *bound_sval = (*iter).second;
2307 : 57444 : if (bound_sval == sval)
2308 : : {
2309 : 17546 : if (const concrete_binding *ckey
2310 : 8773 : = key->dyn_cast_concrete_binding ())
2311 : : {
2312 : 8709 : auto_vec <const region *> subregions;
2313 : 8709 : base_reg->get_subregions_for_binding
2314 : 8709 : (model->get_manager (),
2315 : : ckey->get_start_bit_offset (),
2316 : : ckey->get_size_in_bits (),
2317 : : sval->get_type (),
2318 : : &subregions);
2319 : 8709 : unsigned i;
2320 : 8709 : const region *subregion;
2321 : 25309 : FOR_EACH_VEC_ELT (subregions, i, subregion)
2322 : : {
2323 : 16600 : if (path_var pv
2324 : 8300 : = model->get_representative_path_var (subregion,
2325 : : visited,
2326 : 8300 : logger))
2327 : 8292 : append_pathvar_with_type (pv, sval->get_type (), out_pvs);
2328 : : }
2329 : 8709 : }
2330 : : else
2331 : : {
2332 : 64 : const symbolic_binding *skey = (const symbolic_binding *)key;
2333 : 128 : if (path_var pv
2334 : 64 : = model->get_representative_path_var (skey->get_region (),
2335 : : visited,
2336 : 64 : logger))
2337 : 64 : append_pathvar_with_type (pv, sval->get_type (), out_pvs);
2338 : : }
2339 : : }
2340 : : }
2341 : 60981 : }
2342 : :
2343 : : /* Get any svalue bound to KEY, or NULL. */
2344 : :
2345 : : const svalue *
2346 : 2471834 : binding_cluster::get_any_value (const binding_key *key) const
2347 : : {
2348 : 2471834 : return m_map.get (key);
2349 : : }
2350 : :
2351 : : /* If this cluster has a single direct binding for the whole of the region,
2352 : : return it.
2353 : : For use in simplifying dumps. */
2354 : :
2355 : : const svalue *
2356 : 361325 : binding_cluster::maybe_get_simple_value (store_manager *mgr) const
2357 : : {
2358 : : /* Fail gracefully if MGR is NULL to make it easier to dump store
2359 : : instances in the debugger. */
2360 : 361325 : if (mgr == NULL)
2361 : : return NULL;
2362 : :
2363 : 361325 : if (m_map.elements () != 1)
2364 : : return NULL;
2365 : :
2366 : 169808 : if (m_base_region->empty_p ())
2367 : : return NULL;
2368 : :
2369 : 169808 : const binding_key *key = binding_key::make (mgr, m_base_region);
2370 : 169808 : return get_any_value (key);
2371 : : }
2372 : :
2373 : : /* class store_manager. */
2374 : :
2375 : : logger *
2376 : 329684 : store_manager::get_logger () const
2377 : : {
2378 : 329684 : return m_mgr->get_logger ();
2379 : : }
2380 : :
2381 : : /* binding consolidation. */
2382 : :
2383 : : const concrete_binding *
2384 : 2295627 : store_manager::get_concrete_binding (bit_offset_t start_bit_offset,
2385 : : bit_offset_t size_in_bits)
2386 : : {
2387 : 2295627 : concrete_binding b (start_bit_offset, size_in_bits);
2388 : 4579599 : if (concrete_binding *existing = m_concrete_binding_key_mgr.get (b))
2389 : : return existing;
2390 : :
2391 : 11655 : concrete_binding *to_save = new concrete_binding (b);
2392 : 11655 : m_concrete_binding_key_mgr.put (b, to_save);
2393 : 11655 : return to_save;
2394 : 2295627 : }
2395 : :
2396 : : const symbolic_binding *
2397 : 1287899 : store_manager::get_symbolic_binding (const region *reg)
2398 : : {
2399 : 1287899 : symbolic_binding b (reg);
2400 : 2557648 : if (symbolic_binding *existing = m_symbolic_binding_key_mgr.get (b))
2401 : : return existing;
2402 : :
2403 : 18150 : symbolic_binding *to_save = new symbolic_binding (b);
2404 : 18150 : m_symbolic_binding_key_mgr.put (b, to_save);
2405 : 18150 : return to_save;
2406 : 1287899 : }
2407 : :
2408 : : /* class store. */
2409 : :
2410 : : /* store's default ctor. */
2411 : :
2412 : 337381 : store::store ()
2413 : 337381 : : m_called_unknown_fn (false)
2414 : : {
2415 : 337381 : }
2416 : :
2417 : : /* store's copy ctor. */
2418 : :
2419 : 3530444 : store::store (const store &other)
2420 : 3530444 : : m_cluster_map (other.m_cluster_map.elements ()),
2421 : 3530444 : m_called_unknown_fn (other.m_called_unknown_fn)
2422 : : {
2423 : 3530444 : for (cluster_map_t::iterator iter = other.m_cluster_map.begin ();
2424 : 27247608 : iter != other.m_cluster_map.end ();
2425 : 23717164 : ++iter)
2426 : : {
2427 : 23717164 : const region *reg = (*iter).first;
2428 : 0 : gcc_assert (reg);
2429 : 23717164 : binding_cluster *c = (*iter).second;
2430 : 23717164 : gcc_assert (c);
2431 : 23717164 : m_cluster_map.put (reg, new binding_cluster (*c));
2432 : : }
2433 : 3530444 : }
2434 : :
2435 : : /* store's dtor. */
2436 : :
2437 : 3867825 : store::~store ()
2438 : : {
2439 : 28804091 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2440 : 28804091 : iter != m_cluster_map.end ();
2441 : 24936266 : ++iter)
2442 : 24936266 : delete (*iter).second;
2443 : 3867825 : }
2444 : :
2445 : : /* store's assignment operator. */
2446 : :
2447 : : store &
2448 : 17557 : store::operator= (const store &other)
2449 : : {
2450 : : /* Delete existing cluster map. */
2451 : 132503 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2452 : 132503 : iter != m_cluster_map.end ();
2453 : 114946 : ++iter)
2454 : 229892 : delete (*iter).second;
2455 : 17557 : m_cluster_map.empty ();
2456 : :
2457 : 17557 : m_called_unknown_fn = other.m_called_unknown_fn;
2458 : :
2459 : 17557 : for (cluster_map_t::iterator iter = other.m_cluster_map.begin ();
2460 : 145813 : iter != other.m_cluster_map.end ();
2461 : 128256 : ++iter)
2462 : : {
2463 : 128256 : const region *reg = (*iter).first;
2464 : 128256 : gcc_assert (reg);
2465 : 128256 : binding_cluster *c = (*iter).second;
2466 : 128256 : gcc_assert (c);
2467 : 128256 : m_cluster_map.put (reg, new binding_cluster (*c));
2468 : : }
2469 : 17557 : return *this;
2470 : : }
2471 : :
2472 : : /* store's equality operator. */
2473 : :
2474 : : bool
2475 : 430813 : store::operator== (const store &other) const
2476 : : {
2477 : 430813 : if (m_called_unknown_fn != other.m_called_unknown_fn)
2478 : : return false;
2479 : :
2480 : 427879 : if (m_cluster_map.elements () != other.m_cluster_map.elements ())
2481 : : return false;
2482 : :
2483 : 2310963 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2484 : 2310963 : iter != m_cluster_map.end ();
2485 : 1906293 : ++iter)
2486 : : {
2487 : 1939212 : const region *reg = (*iter).first;
2488 : 1939212 : binding_cluster *c = (*iter).second;
2489 : 1939212 : binding_cluster **other_slot
2490 : 1939212 : = const_cast <cluster_map_t &> (other.m_cluster_map).get (reg);
2491 : 1939212 : if (other_slot == NULL)
2492 : 32919 : return false;
2493 : 1938062 : if (*c != **other_slot)
2494 : : return false;
2495 : : }
2496 : :
2497 : 371751 : gcc_checking_assert (hash () == other.hash ());
2498 : :
2499 : : return true;
2500 : : }
2501 : :
2502 : : /* Get a hash value for this store. */
2503 : :
2504 : : hashval_t
2505 : 1907642 : store::hash () const
2506 : : {
2507 : 1907642 : hashval_t result = 0;
2508 : 1907642 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2509 : 11644634 : iter != m_cluster_map.end ();
2510 : 9736992 : ++iter)
2511 : 9736992 : result ^= (*iter).second->hash ();
2512 : 1907642 : return result;
2513 : : }
2514 : :
2515 : : /* Populate OUT with a sorted list of parent regions for the regions in IN,
2516 : : removing duplicate parents. */
2517 : :
2518 : : static void
2519 : 1960 : get_sorted_parent_regions (auto_vec<const region *> *out,
2520 : : auto_vec<const region *> &in)
2521 : : {
2522 : : /* Get the set of parent regions. */
2523 : 1960 : hash_set<const region *> parent_regions;
2524 : 1960 : const region *iter_reg;
2525 : 1960 : unsigned i;
2526 : 9843 : FOR_EACH_VEC_ELT (in, i, iter_reg)
2527 : : {
2528 : 7883 : const region *parent_reg = iter_reg->get_parent_region ();
2529 : 7883 : gcc_assert (parent_reg);
2530 : 7883 : parent_regions.add (parent_reg);
2531 : : }
2532 : :
2533 : : /* Write to OUT. */
2534 : 1960 : for (hash_set<const region *>::iterator iter = parent_regions.begin();
2535 : 10214 : iter != parent_regions.end(); ++iter)
2536 : 4127 : out->safe_push (*iter);
2537 : :
2538 : : /* Sort OUT. */
2539 : 3747 : out->qsort (region::cmp_ptr_ptr);
2540 : 1960 : }
2541 : :
2542 : : /* Dump a representation of this store to PP, using SIMPLE to control how
2543 : : svalues and regions are printed.
2544 : : MGR is used for simplifying dumps if non-NULL, but can also be NULL
2545 : : (to make it easier to use from the debugger). */
2546 : :
2547 : : void
2548 : 1952 : store::dump_to_pp (pretty_printer *pp, bool simple, bool multiline,
2549 : : store_manager *mgr) const
2550 : : {
2551 : : /* Sort into some deterministic order. */
2552 : 1952 : auto_vec<const region *> base_regions;
2553 : 9835 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2554 : 17718 : iter != m_cluster_map.end (); ++iter)
2555 : : {
2556 : 7883 : const region *base_reg = (*iter).first;
2557 : 7883 : base_regions.safe_push (base_reg);
2558 : : }
2559 : 1952 : base_regions.qsort (region::cmp_ptr_ptr);
2560 : :
2561 : : /* Gather clusters, organize by parent region, so that we can group
2562 : : together locals, globals, etc. */
2563 : 1952 : auto_vec<const region *> parent_regions;
2564 : 1952 : get_sorted_parent_regions (&parent_regions, base_regions);
2565 : :
2566 : 1952 : const region *parent_reg;
2567 : 1952 : unsigned i;
2568 : 6079 : FOR_EACH_VEC_ELT (parent_regions, i, parent_reg)
2569 : : {
2570 : 4127 : gcc_assert (parent_reg);
2571 : 4127 : pp_string (pp, "clusters within ");
2572 : 4127 : parent_reg->dump_to_pp (pp, simple);
2573 : 4127 : if (multiline)
2574 : 1640 : pp_newline (pp);
2575 : : else
2576 : 2487 : pp_string (pp, " {");
2577 : :
2578 : : const region *base_reg;
2579 : : unsigned j;
2580 : 23791 : FOR_EACH_VEC_ELT (base_regions, j, base_reg)
2581 : : {
2582 : : /* This is O(N * M), but N ought to be small. */
2583 : 19664 : if (base_reg->get_parent_region () != parent_reg)
2584 : 11781 : continue;
2585 : 7883 : binding_cluster *cluster
2586 : 7883 : = *const_cast<cluster_map_t &> (m_cluster_map).get (base_reg);
2587 : 7883 : if (!multiline)
2588 : : {
2589 : 4151 : if (j > 0)
2590 : 3152 : pp_string (pp, ", ");
2591 : : }
2592 : 7883 : if (const svalue *sval = cluster->maybe_get_simple_value (mgr))
2593 : : {
2594 : : /* Special-case to simplify dumps for the common case where
2595 : : we just have one value directly bound to the whole of a
2596 : : region. */
2597 : 5710 : if (multiline)
2598 : : {
2599 : 2308 : pp_string (pp, " cluster for: ");
2600 : 2308 : base_reg->dump_to_pp (pp, simple);
2601 : 2308 : pp_string (pp, ": ");
2602 : 2308 : sval->dump_to_pp (pp, simple);
2603 : 2308 : if (cluster->escaped_p ())
2604 : 144 : pp_string (pp, " (ESCAPED)");
2605 : 2308 : if (cluster->touched_p ())
2606 : 0 : pp_string (pp, " (TOUCHED)");
2607 : 2308 : pp_newline (pp);
2608 : : }
2609 : : else
2610 : : {
2611 : 3402 : pp_string (pp, "region: {");
2612 : 3402 : base_reg->dump_to_pp (pp, simple);
2613 : 3402 : pp_string (pp, ", value: ");
2614 : 3402 : sval->dump_to_pp (pp, simple);
2615 : 3402 : if (cluster->escaped_p ())
2616 : 813 : pp_string (pp, " (ESCAPED)");
2617 : 3402 : if (cluster->touched_p ())
2618 : 813 : pp_string (pp, " (TOUCHED)");
2619 : 3402 : pp_string (pp, "}");
2620 : : }
2621 : : }
2622 : 2173 : else if (multiline)
2623 : : {
2624 : 1424 : pp_string (pp, " cluster for: ");
2625 : 1424 : base_reg->dump_to_pp (pp, simple);
2626 : 1424 : pp_newline (pp);
2627 : 1424 : cluster->dump_to_pp (pp, simple, multiline);
2628 : : }
2629 : : else
2630 : : {
2631 : 749 : pp_string (pp, "base region: {");
2632 : 749 : base_reg->dump_to_pp (pp, simple);
2633 : 749 : pp_string (pp, "} has cluster: {");
2634 : 749 : cluster->dump_to_pp (pp, simple, multiline);
2635 : 749 : pp_string (pp, "}");
2636 : : }
2637 : : }
2638 : 4127 : if (!multiline)
2639 : 2487 : pp_string (pp, "}");
2640 : : }
2641 : 1952 : pp_printf (pp, "m_called_unknown_fn: %s",
2642 : 1952 : m_called_unknown_fn ? "TRUE" : "FALSE");
2643 : 1952 : if (multiline)
2644 : 856 : pp_newline (pp);
2645 : 1952 : }
2646 : :
2647 : : /* Dump a multiline representation of this store to stderr. */
2648 : :
2649 : : DEBUG_FUNCTION void
2650 : 0 : store::dump (bool simple) const
2651 : : {
2652 : 0 : tree_dump_pretty_printer pp (stderr);
2653 : 0 : dump_to_pp (&pp, simple, true, NULL);
2654 : 0 : pp_newline (&pp);
2655 : 0 : }
2656 : :
2657 : : /* Assert that this object is valid. */
2658 : :
2659 : : void
2660 : 1644046 : store::validate () const
2661 : : {
2662 : 10448676 : for (auto iter : m_cluster_map)
2663 : 8804630 : iter.second->validate ();
2664 : 1644046 : }
2665 : :
2666 : : /* Return a new json::object of the form
2667 : : {PARENT_REGION_DESC: {BASE_REGION_DESC: object for binding_map,
2668 : : ... for each cluster within parent region},
2669 : : ...for each parent region,
2670 : : "called_unknown_fn": true/false}. */
2671 : :
2672 : : std::unique_ptr<json::object>
2673 : 4 : store::to_json () const
2674 : : {
2675 : 4 : auto store_obj = ::make_unique<json::object> ();
2676 : :
2677 : : /* Sort into some deterministic order. */
2678 : 4 : auto_vec<const region *> base_regions;
2679 : 4 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2680 : 4 : iter != m_cluster_map.end (); ++iter)
2681 : : {
2682 : 0 : const region *base_reg = (*iter).first;
2683 : 0 : base_regions.safe_push (base_reg);
2684 : : }
2685 : 4 : base_regions.qsort (region::cmp_ptr_ptr);
2686 : :
2687 : : /* Gather clusters, organize by parent region, so that we can group
2688 : : together locals, globals, etc. */
2689 : 4 : auto_vec<const region *> parent_regions;
2690 : 4 : get_sorted_parent_regions (&parent_regions, base_regions);
2691 : :
2692 : 4 : const region *parent_reg;
2693 : 4 : unsigned i;
2694 : 4 : FOR_EACH_VEC_ELT (parent_regions, i, parent_reg)
2695 : : {
2696 : 0 : gcc_assert (parent_reg);
2697 : :
2698 : 0 : auto clusters_in_parent_reg_obj = ::make_unique<json::object> ();
2699 : :
2700 : 0 : const region *base_reg;
2701 : 0 : unsigned j;
2702 : 0 : FOR_EACH_VEC_ELT (base_regions, j, base_reg)
2703 : : {
2704 : : /* This is O(N * M), but N ought to be small. */
2705 : 0 : if (base_reg->get_parent_region () != parent_reg)
2706 : 0 : continue;
2707 : 0 : binding_cluster *cluster
2708 : 0 : = *const_cast<cluster_map_t &> (m_cluster_map).get (base_reg);
2709 : 0 : label_text base_reg_desc = base_reg->get_desc ();
2710 : 0 : clusters_in_parent_reg_obj->set (base_reg_desc.get (),
2711 : 0 : cluster->to_json ());
2712 : 0 : }
2713 : 0 : label_text parent_reg_desc = parent_reg->get_desc ();
2714 : 0 : store_obj->set (parent_reg_desc.get (),
2715 : : std::move (clusters_in_parent_reg_obj));
2716 : 0 : }
2717 : :
2718 : 4 : store_obj->set_bool ("called_unknown_fn", m_called_unknown_fn);
2719 : :
2720 : 4 : return store_obj;
2721 : 4 : }
2722 : :
2723 : : std::unique_ptr<text_art::tree_widget>
2724 : 4 : store::make_dump_widget (const text_art::dump_widget_info &dwi,
2725 : : store_manager *mgr) const
2726 : : {
2727 : 4 : std::unique_ptr<text_art::tree_widget> store_widget
2728 : 4 : (text_art::tree_widget::make (dwi, "Store"));
2729 : :
2730 : 4 : store_widget->add_child
2731 : 8 : (text_art::tree_widget::from_fmt (dwi, nullptr,
2732 : : "m_called_unknown_fn: %s",
2733 : 4 : m_called_unknown_fn ? "true" : "false"));
2734 : :
2735 : : /* Sort into some deterministic order. */
2736 : 4 : auto_vec<const region *> base_regions;
2737 : 4 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2738 : 4 : iter != m_cluster_map.end (); ++iter)
2739 : : {
2740 : 0 : const region *base_reg = (*iter).first;
2741 : 0 : base_regions.safe_push (base_reg);
2742 : : }
2743 : 4 : base_regions.qsort (region::cmp_ptr_ptr);
2744 : :
2745 : : /* Gather clusters, organize by parent region, so that we can group
2746 : : together locals, globals, etc. */
2747 : 4 : auto_vec<const region *> parent_regions;
2748 : 4 : get_sorted_parent_regions (&parent_regions, base_regions);
2749 : :
2750 : 4 : const region *parent_reg;
2751 : 4 : unsigned i;
2752 : 4 : FOR_EACH_VEC_ELT (parent_regions, i, parent_reg)
2753 : : {
2754 : 0 : gcc_assert (parent_reg);
2755 : :
2756 : 0 : pretty_printer the_pp;
2757 : 0 : pretty_printer * const pp = &the_pp;
2758 : 0 : pp_format_decoder (pp) = default_tree_printer;
2759 : 0 : pp_show_color (pp) = true;
2760 : 0 : const bool simple = true;
2761 : :
2762 : 0 : parent_reg->dump_to_pp (pp, simple);
2763 : :
2764 : 0 : std::unique_ptr<text_art::tree_widget> parent_reg_widget
2765 : 0 : (text_art::tree_widget::make (dwi, pp));
2766 : :
2767 : 0 : const region *base_reg;
2768 : 0 : unsigned j;
2769 : 0 : FOR_EACH_VEC_ELT (base_regions, j, base_reg)
2770 : : {
2771 : : /* This is O(N * M), but N ought to be small. */
2772 : 0 : if (base_reg->get_parent_region () != parent_reg)
2773 : 0 : continue;
2774 : 0 : binding_cluster *cluster
2775 : 0 : = *const_cast<cluster_map_t &> (m_cluster_map).get (base_reg);
2776 : 0 : parent_reg_widget->add_child
2777 : 0 : (cluster->make_dump_widget (dwi, mgr));
2778 : : }
2779 : 0 : store_widget->add_child (std::move (parent_reg_widget));
2780 : 0 : }
2781 : :
2782 : 4 : return store_widget;
2783 : 4 : }
2784 : :
2785 : : /* Get any svalue bound to REG, or NULL. */
2786 : :
2787 : : const svalue *
2788 : 3715829 : store::get_any_binding (store_manager *mgr, const region *reg) const
2789 : : {
2790 : 3715829 : const region *base_reg = reg->get_base_region ();
2791 : 3715829 : binding_cluster **cluster_slot
2792 : 3715829 : = const_cast <cluster_map_t &> (m_cluster_map).get (base_reg);
2793 : 3715829 : if (!cluster_slot)
2794 : : return NULL;
2795 : 1219310 : return (*cluster_slot)->get_any_binding (mgr, reg);
2796 : : }
2797 : :
2798 : : /* Set the value of LHS_REG to RHS_SVAL. */
2799 : :
2800 : : void
2801 : 329684 : store::set_value (store_manager *mgr, const region *lhs_reg,
2802 : : const svalue *rhs_sval,
2803 : : uncertainty_t *uncertainty)
2804 : : {
2805 : 329684 : logger *logger = mgr->get_logger ();
2806 : 329684 : LOG_SCOPE (logger);
2807 : :
2808 : 329684 : remove_overlapping_bindings (mgr, lhs_reg, uncertainty);
2809 : :
2810 : 329684 : if (lhs_reg->get_type ())
2811 : 322397 : rhs_sval = simplify_for_binding (rhs_sval);
2812 : : /* ...but if we have no type for the region, retain any cast. */
2813 : :
2814 : 329684 : const region *lhs_base_reg = lhs_reg->get_base_region ();
2815 : 329684 : binding_cluster *lhs_cluster;
2816 : 329684 : if (lhs_base_reg->symbolic_for_unknown_ptr_p ())
2817 : : {
2818 : : /* Reject attempting to bind values into a symbolic region
2819 : : for an unknown ptr; merely invalidate values below. */
2820 : 3394 : lhs_cluster = NULL;
2821 : :
2822 : : /* The LHS of the write is *UNKNOWN. If the RHS is a pointer,
2823 : : then treat the region being pointed to as having escaped. */
2824 : 3394 : if (const region_svalue *ptr_sval = rhs_sval->dyn_cast_region_svalue ())
2825 : : {
2826 : 161 : const region *ptr_dst = ptr_sval->get_pointee ();
2827 : 161 : const region *ptr_base_reg = ptr_dst->get_base_region ();
2828 : 161 : mark_as_escaped (ptr_base_reg);
2829 : : }
2830 : 3394 : if (uncertainty)
2831 : 1571 : uncertainty->on_maybe_bound_sval (rhs_sval);
2832 : : }
2833 : 326290 : else if (lhs_base_reg->tracked_p ())
2834 : : {
2835 : 326211 : lhs_cluster = get_or_create_cluster (lhs_base_reg);
2836 : 326211 : lhs_cluster->bind (mgr, lhs_reg, rhs_sval);
2837 : : }
2838 : : else
2839 : : {
2840 : : /* Reject attempting to bind values into an untracked region;
2841 : : merely invalidate values below. */
2842 : : lhs_cluster = NULL;
2843 : : }
2844 : :
2845 : : /* Bindings to a cluster can affect other clusters if a symbolic
2846 : : base region is involved.
2847 : : Writes to concrete clusters can't affect other concrete clusters,
2848 : : but can affect symbolic clusters.
2849 : : Writes to symbolic clusters can affect both concrete and symbolic
2850 : : clusters.
2851 : : Invalidate our knowledge of other clusters that might have been
2852 : : affected by the write.
2853 : : Gather the set of all svalues that might still be live even if
2854 : : the store doesn't refer to them. */
2855 : 329684 : svalue_set maybe_live_values;
2856 : 4557300 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2857 : 8784916 : iter != m_cluster_map.end (); ++iter)
2858 : : {
2859 : 4227616 : const region *iter_base_reg = (*iter).first;
2860 : 4227616 : binding_cluster *iter_cluster = (*iter).second;
2861 : 4227616 : if (iter_base_reg != lhs_base_reg
2862 : 4227616 : && (lhs_cluster == NULL
2863 : 3845414 : || lhs_cluster->symbolic_p ()
2864 : 3765256 : || iter_cluster->symbolic_p ()))
2865 : : {
2866 : 567546 : tristate t_alias = eval_alias (lhs_base_reg, iter_base_reg);
2867 : 567546 : switch (t_alias.get_value ())
2868 : : {
2869 : 0 : default:
2870 : 0 : gcc_unreachable ();
2871 : :
2872 : 61755 : case tristate::TS_UNKNOWN:
2873 : 61755 : if (logger)
2874 : : {
2875 : 7 : pretty_printer *pp = logger->get_printer ();
2876 : 7 : logger->start_log_line ();
2877 : 7 : logger->log_partial ("possible aliasing of ");
2878 : 7 : iter_base_reg->dump_to_pp (pp, true);
2879 : 7 : logger->log_partial (" when writing SVAL: ");
2880 : 7 : rhs_sval->dump_to_pp (pp, true);
2881 : 7 : logger->log_partial (" to LHS_REG: ");
2882 : 7 : lhs_reg->dump_to_pp (pp, true);
2883 : 7 : logger->end_log_line ();
2884 : : }
2885 : : /* Mark all of iter_cluster's iter_base_reg as unknown,
2886 : : using LHS_REG when considering overlaps, to handle
2887 : : symbolic vs concrete issues. */
2888 : 61755 : iter_cluster->mark_region_as_unknown
2889 : 61755 : (mgr,
2890 : : iter_base_reg, /* reg_to_bind */
2891 : : lhs_reg, /* reg_for_overlap */
2892 : : uncertainty,
2893 : : &maybe_live_values);
2894 : 61755 : break;
2895 : :
2896 : 0 : case tristate::TS_TRUE:
2897 : 0 : gcc_unreachable ();
2898 : : break;
2899 : :
2900 : : case tristate::TS_FALSE:
2901 : : /* If they can't be aliases, then don't invalidate this
2902 : : cluster. */
2903 : : break;
2904 : : }
2905 : : }
2906 : : }
2907 : : /* Given the set of svalues that might still be live, process them
2908 : : (e.g. marking regions as escaped).
2909 : : We do this after the iteration to avoid potentially changing
2910 : : m_cluster_map whilst iterating over it. */
2911 : 329684 : on_maybe_live_values (maybe_live_values);
2912 : 329684 : }
2913 : :
2914 : : /* Determine if BASE_REG_A could be an alias of BASE_REG_B. */
2915 : :
2916 : : tristate
2917 : 568101 : store::eval_alias (const region *base_reg_a,
2918 : : const region *base_reg_b) const
2919 : : {
2920 : : /* SSA names can't alias. */
2921 : 568101 : tree decl_a = base_reg_a->maybe_get_decl ();
2922 : 568101 : if (decl_a && TREE_CODE (decl_a) == SSA_NAME)
2923 : 374503 : return tristate::TS_FALSE;
2924 : 193598 : tree decl_b = base_reg_b->maybe_get_decl ();
2925 : 193598 : if (decl_b && TREE_CODE (decl_b) == SSA_NAME)
2926 : 64364 : return tristate::TS_FALSE;
2927 : :
2928 : : /* Try both ways, for symmetry. */
2929 : 129234 : tristate ts_ab = eval_alias_1 (base_reg_a, base_reg_b);
2930 : 129234 : if (ts_ab.is_false ())
2931 : 23966 : return tristate::TS_FALSE;
2932 : 105268 : tristate ts_ba = eval_alias_1 (base_reg_b, base_reg_a);
2933 : 105268 : if (ts_ba.is_false ())
2934 : 43253 : return tristate::TS_FALSE;
2935 : 62015 : return tristate::TS_UNKNOWN;
2936 : : }
2937 : :
2938 : : /* Half of store::eval_alias; called twice for symmetry. */
2939 : :
2940 : : tristate
2941 : 234502 : store::eval_alias_1 (const region *base_reg_a,
2942 : : const region *base_reg_b) const
2943 : : {
2944 : : /* If they're in different memory spaces, they can't alias. */
2945 : 234502 : {
2946 : 234502 : enum memory_space memspace_a = base_reg_a->get_memory_space ();
2947 : 234502 : if (memspace_a != MEMSPACE_UNKNOWN)
2948 : : {
2949 : 80108 : enum memory_space memspace_b = base_reg_b->get_memory_space ();
2950 : 80108 : if (memspace_b != MEMSPACE_UNKNOWN
2951 : 80108 : && memspace_a != memspace_b)
2952 : 249 : return tristate::TS_FALSE;
2953 : : }
2954 : : }
2955 : :
2956 : 468506 : if (const symbolic_region *sym_reg_a
2957 : 234253 : = base_reg_a->dyn_cast_symbolic_region ())
2958 : : {
2959 : 148560 : const svalue *sval_a = sym_reg_a->get_pointer ();
2960 : 148560 : if (tree decl_b = base_reg_b->maybe_get_decl ())
2961 : : {
2962 : 75990 : if (!may_be_aliased (decl_b))
2963 : 44289 : return tristate::TS_FALSE;
2964 : 31701 : if (sval_a->get_kind () == SK_INITIAL)
2965 : 19005 : if (!is_global_var (decl_b))
2966 : : {
2967 : : /* The initial value of a pointer can't point to a local. */
2968 : 13026 : return tristate::TS_FALSE;
2969 : : }
2970 : : }
2971 : 91245 : if (sval_a->get_kind () == SK_INITIAL
2972 : 91245 : && base_reg_b->get_kind () == RK_HEAP_ALLOCATED)
2973 : : {
2974 : : /* The initial value of a pointer can't point to a
2975 : : region that was allocated on the heap after the beginning of the
2976 : : path. */
2977 : 9360 : return tristate::TS_FALSE;
2978 : : }
2979 : 163770 : if (const widening_svalue *widening_sval_a
2980 : 81885 : = sval_a->dyn_cast_widening_svalue ())
2981 : : {
2982 : 3571 : const svalue *base = widening_sval_a->get_base_svalue ();
2983 : 7142 : if (const region_svalue *region_sval
2984 : 3571 : = base->dyn_cast_region_svalue ())
2985 : : {
2986 : 555 : const region *pointee = region_sval->get_pointee ();
2987 : : /* If we have sval_a is WIDENING(®ION, OP), and
2988 : : B can't alias REGION, then B can't alias A either.
2989 : : For example, A might arise from
2990 : : for (ptr = ®ION; ...; ptr++)
2991 : : where sval_a is ptr in the 2nd iteration of the loop.
2992 : : We want to ensure that "*ptr" can only clobber things
2993 : : within REGION's base region. */
2994 : 555 : tristate ts = eval_alias (pointee->get_base_region (),
2995 : : base_reg_b);
2996 : 555 : if (ts.is_false ())
2997 : 295 : return tristate::TS_FALSE;
2998 : : }
2999 : : }
3000 : : }
3001 : 167283 : return tristate::TS_UNKNOWN;
3002 : : }
3003 : :
3004 : : /* Record all of the values in MAYBE_LIVE_VALUES as being possibly live. */
3005 : :
3006 : : void
3007 : 329973 : store::on_maybe_live_values (const svalue_set &maybe_live_values)
3008 : : {
3009 : 412675 : for (auto sval : maybe_live_values)
3010 : : {
3011 : 41351 : if (const region_svalue *ptr_sval = sval->dyn_cast_region_svalue ())
3012 : : {
3013 : 295 : const region *base_reg = ptr_sval->get_pointee ()->get_base_region ();
3014 : 295 : mark_as_escaped (base_reg);
3015 : : }
3016 : : }
3017 : 329973 : }
3018 : :
3019 : : /* Remove all bindings overlapping REG within this store. */
3020 : :
3021 : : void
3022 : 6176 : store::clobber_region (store_manager *mgr, const region *reg)
3023 : : {
3024 : 6176 : const region *base_reg = reg->get_base_region ();
3025 : 6176 : binding_cluster **slot = m_cluster_map.get (base_reg);
3026 : 6176 : if (!slot)
3027 : 1251 : return;
3028 : 4925 : binding_cluster *cluster = *slot;
3029 : 4925 : cluster->clobber_region (mgr, reg);
3030 : 4925 : if (cluster->redundant_p ())
3031 : : {
3032 : 3216 : delete cluster;
3033 : 3216 : m_cluster_map.remove (base_reg);
3034 : : }
3035 : : }
3036 : :
3037 : : /* Remove any bindings for REG within this store. */
3038 : :
3039 : : void
3040 : 179051 : store::purge_region (store_manager *mgr, const region *reg)
3041 : : {
3042 : 179051 : const region *base_reg = reg->get_base_region ();
3043 : 179051 : binding_cluster **slot = m_cluster_map.get (base_reg);
3044 : 179051 : if (!slot)
3045 : 0 : return;
3046 : 179051 : binding_cluster *cluster = *slot;
3047 : 179051 : cluster->purge_region (mgr, reg);
3048 : 179051 : if (cluster->redundant_p ())
3049 : : {
3050 : 170935 : delete cluster;
3051 : 170935 : m_cluster_map.remove (base_reg);
3052 : : }
3053 : : }
3054 : :
3055 : : /* Fill REG with SVAL. */
3056 : :
3057 : : void
3058 : 1438 : store::fill_region (store_manager *mgr, const region *reg, const svalue *sval)
3059 : : {
3060 : : /* Filling an empty region is a no-op. */
3061 : 1438 : if (reg->empty_p ())
3062 : : return;
3063 : :
3064 : 1410 : const region *base_reg = reg->get_base_region ();
3065 : 1410 : if (base_reg->symbolic_for_unknown_ptr_p ()
3066 : 1410 : || !base_reg->tracked_p ())
3067 : 6 : return;
3068 : 1404 : binding_cluster *cluster = get_or_create_cluster (base_reg);
3069 : 1404 : cluster->fill_region (mgr, reg, sval);
3070 : : }
3071 : :
3072 : : /* Zero-fill REG. */
3073 : :
3074 : : void
3075 : 781 : store::zero_fill_region (store_manager *mgr, const region *reg)
3076 : : {
3077 : 781 : region_model_manager *sval_mgr = mgr->get_svalue_manager ();
3078 : 781 : const svalue *zero_sval = sval_mgr->get_or_create_int_cst (char_type_node, 0);
3079 : 781 : fill_region (mgr, reg, zero_sval);
3080 : 781 : }
3081 : :
3082 : : /* Mark REG as having unknown content. */
3083 : :
3084 : : void
3085 : 289 : store::mark_region_as_unknown (store_manager *mgr, const region *reg,
3086 : : uncertainty_t *uncertainty,
3087 : : svalue_set *maybe_live_values)
3088 : : {
3089 : 289 : const region *base_reg = reg->get_base_region ();
3090 : 289 : if (base_reg->symbolic_for_unknown_ptr_p ()
3091 : 289 : || !base_reg->tracked_p ())
3092 : 0 : return;
3093 : 289 : binding_cluster *cluster = get_or_create_cluster (base_reg);
3094 : 289 : cluster->mark_region_as_unknown (mgr, reg, reg, uncertainty,
3095 : : maybe_live_values);
3096 : : }
3097 : :
3098 : : /* Purge state involving SVAL. */
3099 : :
3100 : : void
3101 : 34345 : store::purge_state_involving (const svalue *sval,
3102 : : region_model_manager *sval_mgr)
3103 : : {
3104 : 34345 : auto_vec <const region *> base_regs_to_purge;
3105 : 1157769 : for (auto iter : m_cluster_map)
3106 : : {
3107 : 561712 : const region *base_reg = iter.first;
3108 : 561712 : if (base_reg->involves_p (sval))
3109 : 182 : base_regs_to_purge.safe_push (base_reg);
3110 : : else
3111 : : {
3112 : 561530 : binding_cluster *cluster = iter.second;
3113 : 561530 : cluster->purge_state_involving (sval, sval_mgr);
3114 : : }
3115 : : }
3116 : :
3117 : 34891 : for (auto iter : base_regs_to_purge)
3118 : 182 : purge_cluster (iter);
3119 : 34345 : }
3120 : :
3121 : : /* Get the cluster for BASE_REG, or NULL (const version). */
3122 : :
3123 : : const binding_cluster *
3124 : 2388838 : store::get_cluster (const region *base_reg) const
3125 : : {
3126 : 2388838 : gcc_assert (base_reg);
3127 : 2388838 : gcc_assert (base_reg->get_base_region () == base_reg);
3128 : 4777676 : if (binding_cluster **slot
3129 : 2388838 : = const_cast <cluster_map_t &> (m_cluster_map).get (base_reg))
3130 : 2271331 : return *slot;
3131 : : else
3132 : : return NULL;
3133 : : }
3134 : :
3135 : : /* Get the cluster for BASE_REG, or NULL (non-const version). */
3136 : :
3137 : : binding_cluster *
3138 : 9058201 : store::get_cluster (const region *base_reg)
3139 : : {
3140 : 9058201 : gcc_assert (base_reg);
3141 : 9058201 : gcc_assert (base_reg->get_base_region () == base_reg);
3142 : 9058201 : if (binding_cluster **slot = m_cluster_map.get (base_reg))
3143 : 7687493 : return *slot;
3144 : : else
3145 : : return NULL;
3146 : : }
3147 : :
3148 : : /* Get the cluster for BASE_REG, creating it if doesn't already exist. */
3149 : :
3150 : : binding_cluster *
3151 : 1498910 : store::get_or_create_cluster (const region *base_reg)
3152 : : {
3153 : 1498910 : gcc_assert (base_reg);
3154 : 1498910 : gcc_assert (base_reg->get_base_region () == base_reg);
3155 : :
3156 : : /* We shouldn't create clusters for dereferencing an UNKNOWN ptr. */
3157 : 1498910 : gcc_assert (!base_reg->symbolic_for_unknown_ptr_p ());
3158 : :
3159 : : /* We shouldn't create clusters for base regions that aren't trackable. */
3160 : 1498910 : gcc_assert (base_reg->tracked_p ());
3161 : :
3162 : 1498910 : if (binding_cluster **slot = m_cluster_map.get (base_reg))
3163 : 55353 : return *slot;
3164 : :
3165 : 1443557 : binding_cluster *cluster = new binding_cluster (base_reg);
3166 : 1443557 : m_cluster_map.put (base_reg, cluster);
3167 : :
3168 : 1443557 : return cluster;
3169 : : }
3170 : :
3171 : : /* Remove any cluster for BASE_REG, for use by
3172 : : region_model::unbind_region_and_descendents
3173 : : when popping stack frames and handling deleted heap regions. */
3174 : :
3175 : : void
3176 : 32836 : store::purge_cluster (const region *base_reg)
3177 : : {
3178 : 32836 : gcc_assert (base_reg->get_base_region () == base_reg);
3179 : 32836 : binding_cluster **slot = m_cluster_map.get (base_reg);
3180 : 32836 : if (!slot)
3181 : : return;
3182 : 32836 : binding_cluster *cluster = *slot;
3183 : 65672 : delete cluster;
3184 : 32836 : m_cluster_map.remove (base_reg);
3185 : : }
3186 : :
3187 : : /* Attempt to merge STORE_A and STORE_B into OUT_STORE.
3188 : : Return true if successful, or false if the stores can't be merged. */
3189 : :
3190 : : bool
3191 : 150347 : store::can_merge_p (const store *store_a, const store *store_b,
3192 : : store *out_store, store_manager *mgr,
3193 : : model_merger *merger)
3194 : : {
3195 : 150347 : if (store_a->m_called_unknown_fn || store_b->m_called_unknown_fn)
3196 : 58949 : out_store->m_called_unknown_fn = true;
3197 : :
3198 : : /* Get the union of all base regions for STORE_A and STORE_B. */
3199 : 150347 : hash_set<const region *> base_regions;
3200 : 1640090 : for (cluster_map_t::iterator iter_a = store_a->m_cluster_map.begin ();
3201 : 3129833 : iter_a != store_a->m_cluster_map.end (); ++iter_a)
3202 : : {
3203 : 1489743 : const region *base_reg_a = (*iter_a).first;
3204 : 1489743 : base_regions.add (base_reg_a);
3205 : : }
3206 : 1574874 : for (cluster_map_t::iterator iter_b = store_b->m_cluster_map.begin ();
3207 : 2999401 : iter_b != store_b->m_cluster_map.end (); ++iter_b)
3208 : : {
3209 : 1424527 : const region *base_reg_b = (*iter_b).first;
3210 : 1424527 : base_regions.add (base_reg_b);
3211 : : }
3212 : :
3213 : : /* Sort the base regions before considering them. This ought not to
3214 : : affect the results, but can affect which types UNKNOWN_REGIONs are
3215 : : created for in a run; sorting them thus avoids minor differences
3216 : : in logfiles. */
3217 : 150347 : auto_vec<const region *> vec_base_regions (base_regions.elements ());
3218 : 150347 : for (hash_set<const region *>::iterator iter = base_regions.begin ();
3219 : 3210947 : iter != base_regions.end (); ++iter)
3220 : 1530300 : vec_base_regions.quick_push (*iter);
3221 : 150347 : vec_base_regions.qsort (region::cmp_ptr_ptr);
3222 : : unsigned i;
3223 : : const region *base_reg;
3224 : 1337324 : FOR_EACH_VEC_ELT (vec_base_regions, i, base_reg)
3225 : : {
3226 : 1122746 : const binding_cluster *cluster_a = store_a->get_cluster (base_reg);
3227 : 1122746 : const binding_cluster *cluster_b = store_b->get_cluster (base_reg);
3228 : : /* At least one of cluster_a and cluster_b must be non-NULL. */
3229 : 1122746 : binding_cluster *out_cluster
3230 : 1122746 : = out_store->get_or_create_cluster (base_reg);
3231 : 1122746 : if (!binding_cluster::can_merge_p (cluster_a, cluster_b,
3232 : : out_cluster, out_store, mgr, merger))
3233 : : return false;
3234 : : }
3235 : : return true;
3236 : 150347 : }
3237 : :
3238 : : /* Mark the cluster for BASE_REG as having escaped.
3239 : : For use when handling an unrecognized function call, and
3240 : : for params to "top-level" calls.
3241 : : Further unknown function calls could touch it, even if the cluster
3242 : : isn't reachable from args of those calls. */
3243 : :
3244 : : void
3245 : 41568 : store::mark_as_escaped (const region *base_reg)
3246 : : {
3247 : 41568 : gcc_assert (base_reg);
3248 : 41568 : gcc_assert (base_reg->get_base_region () == base_reg);
3249 : :
3250 : 41568 : if (base_reg->symbolic_for_unknown_ptr_p ()
3251 : 41568 : || !base_reg->tracked_p ())
3252 : 5035 : return;
3253 : :
3254 : 36533 : binding_cluster *cluster = get_or_create_cluster (base_reg);
3255 : 36533 : cluster->mark_as_escaped ();
3256 : : }
3257 : :
3258 : : /* Handle an unknown fncall by updating any clusters that have escaped
3259 : : (either in this fncall, or in a prior one). */
3260 : :
3261 : : void
3262 : 18497 : store::on_unknown_fncall (const gcall *call, store_manager *mgr,
3263 : : const conjured_purge &p)
3264 : : {
3265 : 18497 : m_called_unknown_fn = true;
3266 : :
3267 : 182340 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3268 : 346183 : iter != m_cluster_map.end (); ++iter)
3269 : 163843 : (*iter).second->on_unknown_fncall (call, mgr, p);
3270 : 18497 : }
3271 : :
3272 : : /* Return true if a non-const pointer to BASE_REG (or something within it)
3273 : : has escaped to code outside of the TU being analyzed. */
3274 : :
3275 : : bool
3276 : 7763341 : store::escaped_p (const region *base_reg) const
3277 : : {
3278 : 7763341 : gcc_assert (base_reg);
3279 : 7763341 : gcc_assert (base_reg->get_base_region () == base_reg);
3280 : :
3281 : : /* "errno" can always be modified by external code. */
3282 : 7763341 : if (base_reg->get_kind () == RK_ERRNO)
3283 : : return true;
3284 : :
3285 : 15322144 : if (binding_cluster **cluster_slot
3286 : 7661072 : = const_cast <cluster_map_t &>(m_cluster_map).get (base_reg))
3287 : 7661072 : return (*cluster_slot)->escaped_p ();
3288 : : return false;
3289 : : }
3290 : :
3291 : : /* Populate OUT_PVS with a list of path_vars for describing SVAL based on
3292 : : this store, using VISITED to ensure the traversal terminates. */
3293 : :
3294 : : void
3295 : 14172 : store::get_representative_path_vars (const region_model *model,
3296 : : svalue_set *visited,
3297 : : const svalue *sval,
3298 : : logger *logger,
3299 : : auto_vec<path_var> *out_pvs) const
3300 : : {
3301 : 14172 : gcc_assert (sval);
3302 : :
3303 : : /* Find all bindings that reference SVAL. */
3304 : 75153 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3305 : 136134 : iter != m_cluster_map.end (); ++iter)
3306 : : {
3307 : 60981 : const region *base_reg = (*iter).first;
3308 : 60981 : binding_cluster *cluster = (*iter).second;
3309 : 60981 : cluster->get_representative_path_vars (model, visited, base_reg, sval,
3310 : : logger,
3311 : : out_pvs);
3312 : : }
3313 : :
3314 : 14172 : if (const initial_svalue *init_sval = sval->dyn_cast_initial_svalue ())
3315 : : {
3316 : 2573 : const region *reg = init_sval->get_region ();
3317 : 2573 : if (path_var pv = model->get_representative_path_var (reg,
3318 : : visited,
3319 : 2573 : logger))
3320 : 2451 : out_pvs->safe_push (pv);
3321 : : }
3322 : 14172 : }
3323 : :
3324 : : /* Remove all bindings overlapping REG within this store, removing
3325 : : any clusters that become redundant.
3326 : :
3327 : : If UNCERTAINTY is non-NULL, use it to record any svalues that
3328 : : were removed, as being maybe-bound. */
3329 : :
3330 : : void
3331 : 329684 : store::remove_overlapping_bindings (store_manager *mgr, const region *reg,
3332 : : uncertainty_t *uncertainty)
3333 : : {
3334 : 329684 : const region *base_reg = reg->get_base_region ();
3335 : 329684 : if (binding_cluster **cluster_slot = m_cluster_map.get (base_reg))
3336 : : {
3337 : 51216 : binding_cluster *cluster = *cluster_slot;
3338 : 51216 : if (reg == base_reg && !escaped_p (base_reg))
3339 : : {
3340 : : /* Remove whole cluster. */
3341 : 30778 : m_cluster_map.remove (base_reg);
3342 : 61556 : delete cluster;
3343 : 30778 : return;
3344 : : }
3345 : : /* Pass NULL for the maybe_live_values here, as we don't want to
3346 : : record the old svalues as being maybe-bound. */
3347 : 20438 : cluster->remove_overlapping_bindings (mgr, reg, uncertainty, NULL);
3348 : : }
3349 : : }
3350 : :
3351 : : /* Subclass of visitor that accumulates a hash_set of the regions that
3352 : : were visited. */
3353 : :
3354 : 2037944 : struct region_finder : public visitor
3355 : : {
3356 : 18067403 : void visit_region (const region *reg) final override
3357 : : {
3358 : 18067403 : m_regs.add (reg);
3359 : 18067403 : }
3360 : :
3361 : : hash_set<const region *> m_regs;
3362 : : };
3363 : :
3364 : : /* Canonicalize this store, to maximize the chance of equality between
3365 : : instances. */
3366 : :
3367 : : void
3368 : 1018972 : store::canonicalize (store_manager *mgr)
3369 : : {
3370 : : /* If we have e.g.:
3371 : : cluster for: HEAP_ALLOCATED_REGION(543)
3372 : : ESCAPED
3373 : : TOUCHED
3374 : : where the heap region is empty and unreferenced, then purge that
3375 : : cluster, to avoid unbounded state chains involving these. */
3376 : :
3377 : : /* Find regions that are referenced by bound values in the store. */
3378 : 1018972 : region_finder s;
3379 : 1018972 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3380 : 12388834 : iter != m_cluster_map.end (); ++iter)
3381 : : {
3382 : 5684931 : binding_cluster *cluster = (*iter).second;
3383 : 11656671 : for (binding_cluster::iterator_t bind_iter = cluster->m_map.begin ();
3384 : 23313342 : bind_iter != cluster->m_map.end (); ++bind_iter)
3385 : 5971740 : (*bind_iter).second->accept (&s);
3386 : : }
3387 : :
3388 : : /* Locate heap-allocated regions that have empty bindings that weren't
3389 : : found above. */
3390 : 1018972 : hash_set<const region *> purgeable_regions;
3391 : 6703903 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
3392 : 12388834 : iter != m_cluster_map.end (); ++iter)
3393 : : {
3394 : 5684931 : const region *base_reg = (*iter).first;
3395 : 5684931 : binding_cluster *cluster = (*iter).second;
3396 : 5684931 : if (base_reg->get_kind () == RK_HEAP_ALLOCATED)
3397 : : {
3398 : : /* Don't purge a heap-allocated region that's been marked as
3399 : : escaping, since this could be recording that a ptr to it
3400 : : was written to an unknown symbolic region along this
3401 : : path, and so we don't know whether it's referenced or
3402 : : not, and hence should report it as leaking
3403 : : (PR analyzer/106473). */
3404 : 478314 : if (cluster->escaped_p ())
3405 : 251346 : continue;
3406 : :
3407 : 226968 : if (cluster->empty_p ())
3408 : 612 : if (!s.m_regs.contains (base_reg))
3409 : 0 : purgeable_regions.add (base_reg);
3410 : :
3411 : : /* Also cover the UNKNOWN case. */
3412 : 226968 : if (const svalue *sval = cluster->maybe_get_simple_value (mgr))
3413 : 44357 : if (sval->get_kind () == SK_UNKNOWN)
3414 : 32260 : if (!s.m_regs.contains (base_reg))
3415 : 36 : purgeable_regions.add (base_reg);
3416 : : }
3417 : : }
3418 : :
3419 : : /* Purge them. */
3420 : 1019008 : for (hash_set<const region *>::iterator iter = purgeable_regions.begin ();
3421 : 2038016 : iter != purgeable_regions.end (); ++iter)
3422 : : {
3423 : 36 : const region *base_reg = *iter;
3424 : 36 : purge_cluster (base_reg);
3425 : : }
3426 : 1018972 : }
3427 : :
3428 : : /* Subroutine for use by exploded_path::feasible_p.
3429 : :
3430 : : We need to deal with state differences between:
3431 : : (a) when the exploded_graph is being initially constructed and
3432 : : (b) when replaying the state changes along a specific path in
3433 : : in exploded_path::feasible_p.
3434 : :
3435 : : In (a), state merging happens, so when exploring a loop
3436 : : for (i = 0; i < 1024; i++)
3437 : : on successive iterations we have i == 0, then i == WIDENING.
3438 : :
3439 : : In (b), no state merging happens, so naively replaying the path
3440 : : that goes twice through the loop then exits it
3441 : : would lead to i == 0, then i == 1, and then a (i >= 1024) eedge
3442 : : that exits the loop, which would be found to be infeasible as i == 1,
3443 : : and the path would be rejected.
3444 : :
3445 : : We need to fix up state during replay. This subroutine is
3446 : : called whenever we enter a supernode that we've already
3447 : : visited along this exploded_path, passing in OTHER_STORE
3448 : : from the destination enode's state.
3449 : :
3450 : : Find bindings to widening values in OTHER_STORE.
3451 : : For all that are found, update the binding in this store to UNKNOWN. */
3452 : :
3453 : : void
3454 : 9123 : store::loop_replay_fixup (const store *other_store,
3455 : : region_model_manager *mgr)
3456 : : {
3457 : 9123 : gcc_assert (other_store);
3458 : 9123 : for (cluster_map_t::iterator iter = other_store->m_cluster_map.begin ();
3459 : 156021 : iter != other_store->m_cluster_map.end (); ++iter)
3460 : : {
3461 : 73449 : const region *base_reg = (*iter).first;
3462 : 73449 : binding_cluster *cluster = (*iter).second;
3463 : 157949 : for (binding_cluster::iterator_t bind_iter = cluster->m_map.begin ();
3464 : 315898 : bind_iter != cluster->m_map.end (); ++bind_iter)
3465 : : {
3466 : 84500 : const binding_key *key = (*bind_iter).first;
3467 : 84500 : const svalue *sval = (*bind_iter).second;
3468 : 84500 : if (sval->get_kind () == SK_WIDENING)
3469 : : {
3470 : 1823 : binding_cluster *this_cluster
3471 : 1823 : = get_or_create_cluster (base_reg);
3472 : 1823 : const svalue *unknown
3473 : 1823 : = mgr->get_or_create_unknown_svalue (sval->get_type ());
3474 : 1823 : this_cluster->bind_key (key, unknown);
3475 : : }
3476 : : }
3477 : : }
3478 : 9123 : }
3479 : :
3480 : : /* Use R to replay the bindings from SUMMARY into this object. */
3481 : :
3482 : : void
3483 : 1598 : store::replay_call_summary (call_summary_replay &r,
3484 : : const store &summary)
3485 : : {
3486 : 1598 : if (summary.m_called_unknown_fn)
3487 : : {
3488 : : /* A call to an external function occurred in the summary.
3489 : : Hence we need to invalidate our knownledge of globals,
3490 : : escaped regions, etc. */
3491 : 67 : on_unknown_fncall (r.get_call_stmt (),
3492 : : r.get_store_manager (),
3493 : 67 : conjured_purge (r.get_caller_model (),
3494 : 67 : r.get_ctxt ()));
3495 : : }
3496 : :
3497 : 1598 : auto_vec<const region *> keys (summary.m_cluster_map.elements ());
3498 : 16038 : for (auto kv : summary.m_cluster_map)
3499 : 14440 : keys.quick_push (kv.first);
3500 : 1598 : keys.qsort (region::cmp_ptr_ptr);
3501 : 19178 : for (auto base_reg : keys)
3502 : 14440 : replay_call_summary_cluster (r, summary, base_reg);
3503 : 1598 : }
3504 : :
3505 : : /* Use R and SUMMARY to replay the bindings in SUMMARY_CLUSTER
3506 : : into this object. */
3507 : :
3508 : : void
3509 : 14440 : store::replay_call_summary_cluster (call_summary_replay &r,
3510 : : const store &summary,
3511 : : const region *summary_base_reg)
3512 : : {
3513 : 14440 : const call_details &cd = r.get_call_details ();
3514 : 14440 : region_model_manager *reg_mgr = r.get_manager ();
3515 : 14440 : store_manager *mgr = reg_mgr->get_store_manager ();
3516 : 14440 : const binding_cluster *summary_cluster
3517 : 14440 : = summary.get_cluster (summary_base_reg);
3518 : :
3519 : : /* Handle "ESCAPED" and "TOUCHED" flags. */
3520 : 14440 : if (summary_cluster->escaped_p () || summary_cluster->touched_p ())
3521 : 9458 : if (const region *caller_reg
3522 : 4729 : = r.convert_region_from_summary (summary_base_reg))
3523 : : {
3524 : 4720 : const region *caller_base_reg = caller_reg->get_base_region ();
3525 : 4720 : if (caller_base_reg->tracked_p ()
3526 : 4720 : && !caller_base_reg->symbolic_for_unknown_ptr_p ())
3527 : : {
3528 : 3690 : binding_cluster *caller_cluster
3529 : 3690 : = get_or_create_cluster (caller_base_reg);
3530 : 3690 : if (summary_cluster->escaped_p ())
3531 : 2869 : caller_cluster->mark_as_escaped ();
3532 : 3690 : if (summary_cluster->touched_p ())
3533 : 2266 : caller_cluster->m_touched = true;
3534 : : }
3535 : : }
3536 : :
3537 : 14440 : switch (summary_base_reg->get_kind ())
3538 : : {
3539 : : /* Top-level regions. */
3540 : 0 : case RK_FRAME:
3541 : 0 : case RK_GLOBALS:
3542 : 0 : case RK_CODE:
3543 : 0 : case RK_STACK:
3544 : 0 : case RK_HEAP:
3545 : 0 : case RK_THREAD_LOCAL:
3546 : 0 : case RK_ROOT:
3547 : : /* Child regions. */
3548 : 0 : case RK_FIELD:
3549 : 0 : case RK_ELEMENT:
3550 : 0 : case RK_OFFSET:
3551 : 0 : case RK_SIZED:
3552 : 0 : case RK_CAST:
3553 : 0 : case RK_BIT_RANGE:
3554 : : /* Other regions. */
3555 : 0 : case RK_VAR_ARG:
3556 : 0 : case RK_UNKNOWN:
3557 : : /* These should never be the base region of a binding cluster. */
3558 : 0 : gcc_unreachable ();
3559 : : break;
3560 : :
3561 : : case RK_FUNCTION:
3562 : : case RK_LABEL:
3563 : : case RK_STRING:
3564 : : /* These can be marked as escaping. */
3565 : : break;
3566 : :
3567 : 3321 : case RK_SYMBOLIC:
3568 : 3321 : {
3569 : 3321 : const symbolic_region *summary_symbolic_reg
3570 : 3321 : = as_a <const symbolic_region *> (summary_base_reg);
3571 : 3321 : const svalue *summary_ptr_sval = summary_symbolic_reg->get_pointer ();
3572 : 3321 : const svalue *caller_ptr_sval
3573 : 3321 : = r.convert_svalue_from_summary (summary_ptr_sval);
3574 : 3321 : if (!caller_ptr_sval)
3575 : : return;
3576 : 2776 : const region *caller_dest_reg
3577 : 2776 : = cd.get_model ()->deref_rvalue (caller_ptr_sval,
3578 : : NULL_TREE,
3579 : : cd.get_ctxt ());
3580 : 2776 : const svalue *summary_sval
3581 : 2776 : = summary.get_any_binding (mgr, summary_base_reg);
3582 : 2776 : if (!summary_sval)
3583 : : return;
3584 : 2508 : const svalue *caller_sval
3585 : 2508 : = r.convert_svalue_from_summary (summary_sval);
3586 : 2508 : if (!caller_sval)
3587 : 2 : caller_sval =
3588 : 2 : reg_mgr->get_or_create_unknown_svalue (summary_sval->get_type ());
3589 : 2508 : set_value (mgr, caller_dest_reg,
3590 : : caller_sval, NULL /* uncertainty_t * */);
3591 : : }
3592 : 2508 : break;
3593 : :
3594 : 11114 : case RK_HEAP_ALLOCATED:
3595 : 11114 : case RK_DECL:
3596 : 11114 : case RK_ERRNO:
3597 : 11114 : case RK_PRIVATE:
3598 : 11114 : {
3599 : 11114 : const region *caller_dest_reg
3600 : 11114 : = r.convert_region_from_summary (summary_base_reg);
3601 : 11114 : if (!caller_dest_reg)
3602 : : return;
3603 : 10885 : const svalue *summary_sval
3604 : 10885 : = summary.get_any_binding (mgr, summary_base_reg);
3605 : 10885 : if (!summary_sval)
3606 : 206 : summary_sval = reg_mgr->get_or_create_compound_svalue
3607 : 206 : (summary_base_reg->get_type (),
3608 : : summary_cluster->get_map ());
3609 : 10885 : const svalue *caller_sval
3610 : 10885 : = r.convert_svalue_from_summary (summary_sval);
3611 : 10885 : if (!caller_sval)
3612 : 2 : caller_sval =
3613 : 2 : reg_mgr->get_or_create_unknown_svalue (summary_sval->get_type ());
3614 : 10885 : set_value (mgr, caller_dest_reg,
3615 : : caller_sval, NULL /* uncertainty_t * */);
3616 : : }
3617 : 10885 : break;
3618 : :
3619 : : case RK_ALLOCA:
3620 : : /* Ignore bindings of alloca regions in the summary. */
3621 : : break;
3622 : : }
3623 : : }
3624 : :
3625 : : #if CHECKING_P
3626 : :
3627 : : namespace selftest {
3628 : :
3629 : : /* Verify that bit_range::intersects_p works as expected. */
3630 : :
3631 : : static void
3632 : 4 : test_bit_range_intersects_p ()
3633 : : {
3634 : 4 : bit_range b0 (0, 1);
3635 : 4 : bit_range b1 (1, 1);
3636 : 4 : bit_range b2 (2, 1);
3637 : 4 : bit_range b3 (3, 1);
3638 : 4 : bit_range b4 (4, 1);
3639 : 4 : bit_range b5 (5, 1);
3640 : 4 : bit_range b6 (6, 1);
3641 : 4 : bit_range b7 (7, 1);
3642 : 4 : bit_range b1_to_6 (1, 6);
3643 : 4 : bit_range b0_to_7 (0, 8);
3644 : 4 : bit_range b3_to_5 (3, 3);
3645 : 4 : bit_range b6_to_7 (6, 2);
3646 : :
3647 : : /* self-intersection is true. */
3648 : 4 : ASSERT_TRUE (b0.intersects_p (b0));
3649 : 4 : ASSERT_TRUE (b7.intersects_p (b7));
3650 : 4 : ASSERT_TRUE (b1_to_6.intersects_p (b1_to_6));
3651 : 4 : ASSERT_TRUE (b0_to_7.intersects_p (b0_to_7));
3652 : :
3653 : 4 : ASSERT_FALSE (b0.intersects_p (b1));
3654 : 4 : ASSERT_FALSE (b1.intersects_p (b0));
3655 : 4 : ASSERT_FALSE (b0.intersects_p (b7));
3656 : 4 : ASSERT_FALSE (b7.intersects_p (b0));
3657 : :
3658 : 4 : ASSERT_TRUE (b0_to_7.intersects_p (b0));
3659 : 4 : ASSERT_TRUE (b0_to_7.intersects_p (b7));
3660 : 4 : ASSERT_TRUE (b0.intersects_p (b0_to_7));
3661 : 4 : ASSERT_TRUE (b7.intersects_p (b0_to_7));
3662 : :
3663 : 4 : ASSERT_FALSE (b0.intersects_p (b1_to_6));
3664 : 4 : ASSERT_FALSE (b1_to_6.intersects_p (b0));
3665 : 4 : ASSERT_TRUE (b1.intersects_p (b1_to_6));
3666 : 4 : ASSERT_TRUE (b1_to_6.intersects_p (b1));
3667 : 4 : ASSERT_TRUE (b1_to_6.intersects_p (b6));
3668 : 4 : ASSERT_FALSE (b1_to_6.intersects_p (b7));
3669 : :
3670 : 4 : ASSERT_TRUE (b1_to_6.intersects_p (b0_to_7));
3671 : 4 : ASSERT_TRUE (b0_to_7.intersects_p (b1_to_6));
3672 : :
3673 : 4 : ASSERT_FALSE (b3_to_5.intersects_p (b6_to_7));
3674 : 4 : ASSERT_FALSE (b6_to_7.intersects_p (b3_to_5));
3675 : :
3676 : 4 : bit_range r1 (0,0);
3677 : 4 : bit_range r2 (0,0);
3678 : 4 : ASSERT_TRUE (b1_to_6.intersects_p (b0_to_7, &r1, &r2));
3679 : 4 : ASSERT_EQ (r1.get_start_bit_offset (), 0);
3680 : 4 : ASSERT_EQ (r1.m_size_in_bits, 6);
3681 : 4 : ASSERT_EQ (r2.get_start_bit_offset (), 1);
3682 : 4 : ASSERT_EQ (r2.m_size_in_bits, 6);
3683 : :
3684 : 4 : ASSERT_TRUE (b0_to_7.intersects_p (b1_to_6, &r1, &r2));
3685 : 4 : ASSERT_EQ (r1.get_start_bit_offset (), 1);
3686 : 4 : ASSERT_EQ (r1.m_size_in_bits, 6);
3687 : 4 : ASSERT_EQ (r2.get_start_bit_offset (), 0);
3688 : 4 : ASSERT_EQ (r2.m_size_in_bits, 6);
3689 : 4 : }
3690 : :
3691 : : /* Implementation detail of ASSERT_BIT_RANGE_FROM_MASK_EQ. */
3692 : :
3693 : : static void
3694 : 76 : assert_bit_range_from_mask_eq (const location &loc,
3695 : : unsigned HOST_WIDE_INT mask,
3696 : : const bit_range &expected)
3697 : : {
3698 : 76 : bit_range actual (0, 0);
3699 : 76 : bool ok = bit_range::from_mask (mask, &actual);
3700 : 76 : ASSERT_TRUE_AT (loc, ok);
3701 : 76 : ASSERT_EQ_AT (loc, actual, expected);
3702 : 76 : }
3703 : :
3704 : : /* Assert that bit_range::from_mask (MASK) returns true, and writes
3705 : : out EXPECTED_BIT_RANGE. */
3706 : :
3707 : : #define ASSERT_BIT_RANGE_FROM_MASK_EQ(MASK, EXPECTED_BIT_RANGE) \
3708 : : SELFTEST_BEGIN_STMT \
3709 : : assert_bit_range_from_mask_eq (SELFTEST_LOCATION, MASK, \
3710 : : EXPECTED_BIT_RANGE); \
3711 : : SELFTEST_END_STMT
3712 : :
3713 : : /* Implementation detail of ASSERT_NO_BIT_RANGE_FROM_MASK. */
3714 : :
3715 : : static void
3716 : 12 : assert_no_bit_range_from_mask_eq (const location &loc,
3717 : : unsigned HOST_WIDE_INT mask)
3718 : : {
3719 : 12 : bit_range actual (0, 0);
3720 : 12 : bool ok = bit_range::from_mask (mask, &actual);
3721 : 12 : ASSERT_FALSE_AT (loc, ok);
3722 : 12 : }
3723 : :
3724 : : /* Assert that bit_range::from_mask (MASK) returns false. */
3725 : :
3726 : : #define ASSERT_NO_BIT_RANGE_FROM_MASK(MASK) \
3727 : : SELFTEST_BEGIN_STMT \
3728 : : assert_no_bit_range_from_mask_eq (SELFTEST_LOCATION, MASK); \
3729 : : SELFTEST_END_STMT
3730 : :
3731 : : /* Verify that bit_range::from_mask works as expected. */
3732 : :
3733 : : static void
3734 : 4 : test_bit_range_from_mask ()
3735 : : {
3736 : : /* Should fail on zero. */
3737 : 4 : ASSERT_NO_BIT_RANGE_FROM_MASK (0);
3738 : :
3739 : : /* Verify 1-bit masks. */
3740 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (1, bit_range (0, 1));
3741 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (2, bit_range (1, 1));
3742 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (4, bit_range (2, 1));
3743 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (8, bit_range (3, 1));
3744 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (16, bit_range (4, 1));
3745 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (32, bit_range (5, 1));
3746 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (64, bit_range (6, 1));
3747 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (128, bit_range (7, 1));
3748 : :
3749 : : /* Verify N-bit masks starting at bit 0. */
3750 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (3, bit_range (0, 2));
3751 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (7, bit_range (0, 3));
3752 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (15, bit_range (0, 4));
3753 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (31, bit_range (0, 5));
3754 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (63, bit_range (0, 6));
3755 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (127, bit_range (0, 7));
3756 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (255, bit_range (0, 8));
3757 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (0xffff, bit_range (0, 16));
3758 : :
3759 : : /* Various other tests. */
3760 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (0x30, bit_range (4, 2));
3761 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (0x700, bit_range (8, 3));
3762 : 4 : ASSERT_BIT_RANGE_FROM_MASK_EQ (0x600, bit_range (9, 2));
3763 : :
3764 : : /* Multiple ranges of set bits should fail. */
3765 : 4 : ASSERT_NO_BIT_RANGE_FROM_MASK (0x101);
3766 : 4 : ASSERT_NO_BIT_RANGE_FROM_MASK (0xf0f0f0f0);
3767 : 4 : }
3768 : :
3769 : : /* Implementation detail of ASSERT_OVERLAP. */
3770 : :
3771 : : static void
3772 : 56 : assert_overlap (const location &loc,
3773 : : const concrete_binding *b1,
3774 : : const concrete_binding *b2)
3775 : : {
3776 : 56 : ASSERT_TRUE_AT (loc, b1->overlaps_p (*b2));
3777 : 56 : ASSERT_TRUE_AT (loc, b2->overlaps_p (*b1));
3778 : 56 : }
3779 : :
3780 : : /* Implementation detail of ASSERT_DISJOINT. */
3781 : :
3782 : : static void
3783 : 20 : assert_disjoint (const location &loc,
3784 : : const concrete_binding *b1,
3785 : : const concrete_binding *b2)
3786 : : {
3787 : 20 : ASSERT_FALSE_AT (loc, b1->overlaps_p (*b2));
3788 : 20 : ASSERT_FALSE_AT (loc, b2->overlaps_p (*b1));
3789 : 20 : }
3790 : :
3791 : : /* Assert that B1 and B2 overlap, checking both ways. */
3792 : :
3793 : : #define ASSERT_OVERLAP(B1, B2) \
3794 : : SELFTEST_BEGIN_STMT \
3795 : : assert_overlap (SELFTEST_LOCATION, B1, B2); \
3796 : : SELFTEST_END_STMT
3797 : :
3798 : : /* Assert that B1 and B2 do not overlap, checking both ways. */
3799 : :
3800 : : #define ASSERT_DISJOINT(B1, B2) \
3801 : : SELFTEST_BEGIN_STMT \
3802 : : assert_disjoint (SELFTEST_LOCATION, B1, B2); \
3803 : : SELFTEST_END_STMT
3804 : :
3805 : : /* Verify that concrete_binding::overlaps_p works as expected. */
3806 : :
3807 : : static void
3808 : 4 : test_binding_key_overlap ()
3809 : : {
3810 : 4 : store_manager mgr (NULL);
3811 : :
3812 : : /* Various 8-bit bindings. */
3813 : 4 : const concrete_binding *cb_0_7 = mgr.get_concrete_binding (0, 8);
3814 : 4 : const concrete_binding *cb_8_15 = mgr.get_concrete_binding (8, 8);
3815 : 4 : const concrete_binding *cb_16_23 = mgr.get_concrete_binding (16, 8);
3816 : 4 : const concrete_binding *cb_24_31 = mgr.get_concrete_binding (24, 8);
3817 : :
3818 : : /* 16-bit bindings. */
3819 : 4 : const concrete_binding *cb_0_15 = mgr.get_concrete_binding (0, 16);
3820 : 4 : const concrete_binding *cb_8_23 = mgr.get_concrete_binding (8, 16);
3821 : 4 : const concrete_binding *cb_16_31 = mgr.get_concrete_binding (16, 16);
3822 : :
3823 : : /* 32-bit binding. */
3824 : 4 : const concrete_binding *cb_0_31 = mgr.get_concrete_binding (0, 32);
3825 : :
3826 : : /* Everything should self-overlap. */
3827 : 4 : ASSERT_OVERLAP (cb_0_7, cb_0_7);
3828 : 4 : ASSERT_OVERLAP (cb_8_15, cb_8_15);
3829 : 4 : ASSERT_OVERLAP (cb_16_23, cb_16_23);
3830 : 4 : ASSERT_OVERLAP (cb_24_31, cb_24_31);
3831 : 4 : ASSERT_OVERLAP (cb_0_15, cb_0_15);
3832 : 4 : ASSERT_OVERLAP (cb_8_23, cb_8_23);
3833 : 4 : ASSERT_OVERLAP (cb_16_31, cb_16_31);
3834 : 4 : ASSERT_OVERLAP (cb_0_31, cb_0_31);
3835 : :
3836 : : /* Verify the 8-bit bindings that don't overlap each other. */
3837 : 4 : ASSERT_DISJOINT (cb_0_7, cb_8_15);
3838 : 4 : ASSERT_DISJOINT (cb_8_15, cb_16_23);
3839 : :
3840 : : /* Check for overlap of differently-sized bindings. */
3841 : 4 : ASSERT_OVERLAP (cb_0_7, cb_0_31);
3842 : : /* ...and with differing start points. */
3843 : 4 : ASSERT_OVERLAP (cb_8_15, cb_0_31);
3844 : 4 : ASSERT_DISJOINT (cb_8_15, cb_16_31);
3845 : 4 : ASSERT_OVERLAP (cb_16_23, cb_0_31);
3846 : 4 : ASSERT_OVERLAP (cb_16_31, cb_0_31);
3847 : :
3848 : 4 : ASSERT_DISJOINT (cb_0_7, cb_8_23);
3849 : 4 : ASSERT_OVERLAP (cb_8_23, cb_16_23);
3850 : 4 : ASSERT_OVERLAP (cb_8_23, cb_16_31);
3851 : 4 : ASSERT_DISJOINT (cb_8_23, cb_24_31);
3852 : 4 : }
3853 : :
3854 : : /* Run all of the selftests within this file. */
3855 : :
3856 : : void
3857 : 4 : analyzer_store_cc_tests ()
3858 : : {
3859 : 4 : test_bit_range_intersects_p ();
3860 : 4 : test_bit_range_from_mask ();
3861 : 4 : test_binding_key_overlap ();
3862 : 4 : }
3863 : :
3864 : : } // namespace selftest
3865 : :
3866 : : #endif /* CHECKING_P */
3867 : :
3868 : : } // namespace ana
3869 : :
3870 : : #endif /* #if ENABLE_ANALYZER */
|
