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