Line data Source code
1 : /* Classes for modeling the state of memory.
2 : Copyright (C) 2020-2026 Free Software Foundation, Inc.
3 : Contributed by David Malcolm <dmalcolm@redhat.com>.
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it
8 : under the terms of the GNU General Public License as published by
9 : the Free Software Foundation; either version 3, or (at your option)
10 : any later version.
11 :
12 : GCC is distributed in the hope that it will be useful, but
13 : WITHOUT ANY WARRANTY; without even the implied warranty of
14 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : General Public License for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #include "analyzer/common.h"
22 :
23 : #include "ordered-hash-map.h"
24 : #include "cfg.h"
25 : #include "sbitmap.h"
26 : #include "stor-layout.h"
27 :
28 : #include "text-art/tree-widget.h"
29 :
30 : #include "analyzer/analyzer-logging.h"
31 : #include "analyzer/supergraph.h"
32 : #include "analyzer/call-string.h"
33 : #include "analyzer/program-point.h"
34 : #include "analyzer/store.h"
35 : #include "analyzer/region-model.h"
36 : #include "analyzer/call-summary.h"
37 : #include "analyzer/analyzer-selftests.h"
38 :
39 : #if ENABLE_ANALYZER
40 :
41 : namespace ana {
42 :
43 : /* class uncertainty_t. */
44 :
45 : void
46 57651 : uncertainty_t::on_maybe_bound_value (const symbolic::value_node &val)
47 : {
48 57651 : m_maybe_bound_vals.add (&val);
49 57651 : }
50 :
51 : void
52 20264 : uncertainty_t::
53 : on_mutable_value_at_unknown_call (const symbolic::value_node &val)
54 : {
55 20264 : m_mutable_at_unknown_call_vals.add (&val);
56 20264 : }
57 :
58 : bool
59 352256 : uncertainty_t::unknown_sm_state_p (const svalue *sval)
60 : {
61 352256 : if (m_maybe_bound_vals.contains (sval))
62 : return true;
63 351907 : if (m_mutable_at_unknown_call_vals.contains (sval))
64 : return true;
65 :
66 351907 : if (auto *from_bv = sval->dyn_cast_svalue_from_bit_vector ())
67 : {
68 69721 : auto *bv = &from_bv->get_bit_vector ();
69 69721 : if (m_maybe_bound_vals.contains (bv)
70 69721 : || m_mutable_at_unknown_call_vals.contains (bv))
71 : return true;
72 : }
73 :
74 : return false;
75 : }
76 :
77 : /* Mark all in BC as being maybe bound. */
78 :
79 : void
80 637 : uncertainty_t::add_bit_contents (const symbolic::bit_contents &bc)
81 : {
82 637 : bc.for_each_value ([] (const symbolic::value_node &val,
83 : void *user_data) -> iter_result {
84 844 : uncertainty_t *self = static_cast<uncertainty_t *> (user_data);
85 844 : self->on_maybe_bound_value (val);
86 844 : return val.for_each_svalue ([] (const svalue &sval,
87 : void *user_data) -> iter_result
88 : {
89 : uncertainty_t *uncertainty = static_cast<uncertainty_t *> (user_data);
90 : uncertainty->on_maybe_bound_value (sval);
91 : return iter_result::keep_going;
92 : }, user_data);
93 : return iter_result::keep_going;
94 : }, this);
95 637 : }
96 :
97 : /* Dump a tree-like representation of this object to stderr. */
98 :
99 : DEBUG_FUNCTION void
100 0 : uncertainty_t::dump () const
101 : {
102 0 : symbolic::dump_node_tree_to_stderr<uncertainty_t> (*this);
103 0 : }
104 :
105 : void
106 114 : uncertainty_t::dump_to_logger (logger &log) const
107 : {
108 114 : symbolic::dump_node_tree_to_logger<uncertainty_t> (*this, log);
109 114 : }
110 :
111 : std::unique_ptr<text_art::tree_widget>
112 114 : uncertainty_t::make_dump_widget (symbolic::node_dump_state &nds) const
113 : {
114 114 : using text_art::tree_widget;
115 114 : std::unique_ptr<tree_widget> w
116 114 : (tree_widget::from_fmt (nds, nullptr, "uncertainty_t"));
117 :
118 114 : {
119 114 : std::unique_ptr<tree_widget> child
120 114 : (tree_widget::from_fmt (nds, nullptr, "m_maybe_bound_vals"));
121 114 : for (auto iter : m_maybe_bound_vals)
122 0 : child->add_child (iter->make_dump_widget (nds));
123 228 : w->add_child (std::move (child));
124 114 : }
125 114 : {
126 114 : std::unique_ptr<tree_widget> child
127 114 : (tree_widget::from_fmt (nds, nullptr, "m_mutable_at_unknown_call_vals"));
128 120 : for (auto iter : m_mutable_at_unknown_call_vals)
129 12 : child->add_child (iter->make_dump_widget (nds));
130 228 : w->add_child (std::move (child));
131 114 : }
132 :
133 114 : return w;
134 : }
135 :
136 : /* struct bit_range. */
137 :
138 : void
139 0 : bit_range::dump_to_pp (pretty_printer *pp) const
140 : {
141 0 : byte_range bytes (0, 0);
142 0 : if (as_byte_range (&bytes))
143 0 : bytes.dump_to_pp (pp);
144 : else
145 : {
146 0 : pp_string (pp, "start: ");
147 0 : pp_wide_int (pp, m_start_bit_offset, SIGNED);
148 0 : pp_string (pp, ", size: ");
149 0 : pp_wide_int (pp, m_size_in_bits, SIGNED);
150 0 : pp_string (pp, ", next: ");
151 0 : pp_wide_int (pp, get_next_bit_offset (), SIGNED);
152 : }
153 0 : }
154 :
155 : /* Dump this object to stderr. */
156 :
157 : DEBUG_FUNCTION void
158 0 : bit_range::dump () const
159 : {
160 0 : tree_dump_pretty_printer pp (stderr);
161 0 : dump_to_pp (&pp);
162 0 : pp_newline (&pp);
163 0 : }
164 :
165 : /* Generate a JSON value for this bit_range.
166 : This is intended for debugging the analyzer rather
167 : than serialization. */
168 :
169 : std::unique_ptr<json::object>
170 0 : bit_range::to_json () const
171 : {
172 0 : auto obj = std::make_unique<json::object> ();
173 0 : obj->set ("start_bit_offset",
174 0 : bit_offset_to_json (m_start_bit_offset));
175 0 : obj->set ("size_in_bits",
176 0 : bit_offset_to_json (m_size_in_bits));
177 0 : return obj;
178 : }
179 :
180 : /* If OTHER is a subset of this, return true and, if OUT is
181 : non-null, write to *OUT the relative range of OTHER within this.
182 : Otherwise return false. */
183 :
184 : bool
185 0 : bit_range::contains_p (const bit_range &other, bit_range *out) const
186 : {
187 0 : if (contains_p (other.get_start_bit_offset ())
188 0 : && contains_p (other.get_last_bit_offset ()))
189 : {
190 0 : if (out)
191 : {
192 0 : out->m_start_bit_offset = other.m_start_bit_offset - m_start_bit_offset;
193 0 : out->m_size_in_bits = other.m_size_in_bits;
194 : }
195 : return true;
196 : }
197 : else
198 : return false;
199 : }
200 :
201 : /* If OTHER intersects this, return true and write
202 : the relative range of OTHER within THIS to *OUT_THIS,
203 : and the relative range of THIS within OTHER to *OUT_OTHER.
204 : Otherwise return false. */
205 :
206 : bool
207 8 : bit_range::intersects_p (const bit_range &other,
208 : bit_range *out_this,
209 : bit_range *out_other) const
210 : {
211 8 : if (get_start_bit_offset () < other.get_next_bit_offset ()
212 16 : && other.get_start_bit_offset () < get_next_bit_offset ())
213 : {
214 8 : bit_offset_t overlap_start
215 8 : = MAX (get_start_bit_offset (),
216 : other.get_start_bit_offset ());
217 8 : bit_offset_t overlap_next
218 8 : = MIN (get_next_bit_offset (),
219 : other.get_next_bit_offset ());
220 8 : if (overlap_next <= overlap_start)
221 : /* If this has happened, some kind of overflow has happened in
222 : our arithmetic. For now, reject such cases. */
223 : return false;
224 8 : bit_range abs_overlap_bits (overlap_start, overlap_next - overlap_start);
225 8 : *out_this = abs_overlap_bits - get_start_bit_offset ();
226 8 : *out_other = abs_overlap_bits - other.get_start_bit_offset ();
227 8 : return true;
228 : }
229 : else
230 0 : return false;
231 : }
232 :
233 : /* Return true if THIS and OTHER intersect and write the number
234 : of bits both buffers overlap to *OUT_NUM_OVERLAP_BITS.
235 :
236 : Otherwise return false. */
237 :
238 : bool
239 0 : bit_range::intersects_p (const bit_range &other,
240 : bit_size_t *out_num_overlap_bits) const
241 : {
242 0 : if (get_start_bit_offset () < other.get_next_bit_offset ()
243 0 : && other.get_start_bit_offset () < get_next_bit_offset ())
244 : {
245 0 : bit_offset_t overlap_start = MAX (get_start_bit_offset (),
246 : other.get_start_bit_offset ());
247 0 : bit_offset_t overlap_next = MIN (get_next_bit_offset (),
248 : other.get_next_bit_offset ());
249 0 : if (overlap_next <= overlap_start)
250 : /* If this has happened, some kind of overflow has happened in
251 : our arithmetic. For now, reject such cases. */
252 : return false;
253 0 : *out_num_overlap_bits = overlap_next - overlap_start;
254 0 : return true;
255 : }
256 : else
257 0 : return false;
258 : }
259 :
260 : /* Return true if THIS exceeds OTHER and write the overhanging
261 : bit range to OUT_OVERHANGING_BIT_RANGE. */
262 :
263 : bool
264 0 : bit_range::exceeds_p (const bit_range &other,
265 : bit_range *out_overhanging_bit_range) const
266 : {
267 0 : gcc_assert (!empty_p ());
268 :
269 0 : if (other.get_next_bit_offset () < get_next_bit_offset ())
270 : {
271 : /* THIS definitely exceeds OTHER. */
272 0 : bit_offset_t start = MAX (get_start_bit_offset (),
273 : other.get_next_bit_offset ());
274 0 : bit_offset_t size = get_next_bit_offset () - start;
275 0 : if (size <= 0)
276 : /* If this has happened, some kind of overflow has happened in
277 : our arithmetic. For now, reject such cases. */
278 : return false;
279 0 : out_overhanging_bit_range->m_start_bit_offset = start;
280 0 : out_overhanging_bit_range->m_size_in_bits = size;
281 0 : return true;
282 : }
283 : else
284 : return false;
285 : }
286 :
287 : /* Return true if THIS falls short of OFFSET and write the
288 : bit range fallen short to OUT_FALL_SHORT_BITS. */
289 :
290 : bool
291 0 : bit_range::falls_short_of_p (bit_offset_t offset,
292 : bit_range *out_fall_short_bits) const
293 : {
294 0 : gcc_assert (!empty_p ());
295 :
296 0 : if (get_start_bit_offset () < offset)
297 : {
298 : /* THIS falls short of OFFSET. */
299 0 : bit_offset_t start = get_start_bit_offset ();
300 0 : bit_offset_t size = MIN (offset, get_next_bit_offset ()) - start;
301 0 : if (size <= 0)
302 : /* If this has happened, some kind of overflow has happened in
303 : our arithmetic. For now, reject such cases. */
304 : return false;
305 0 : out_fall_short_bits->m_start_bit_offset = start;
306 0 : out_fall_short_bits->m_size_in_bits = size;
307 0 : return true;
308 : }
309 : else
310 : return false;
311 : }
312 :
313 : int
314 0 : bit_range::cmp (const bit_range &br1, const bit_range &br2)
315 : {
316 0 : if (int start_cmp = wi::cmps (br1.m_start_bit_offset,
317 0 : br2.m_start_bit_offset))
318 : return start_cmp;
319 :
320 0 : return wi::cmpu (br1.m_size_in_bits, br2.m_size_in_bits);
321 : }
322 :
323 : /* Offset this range by OFFSET. */
324 :
325 : bit_range
326 16 : bit_range::operator- (bit_offset_t offset) const
327 : {
328 16 : return bit_range (m_start_bit_offset - offset, m_size_in_bits);
329 : }
330 :
331 : /* Attempt to convert this bit_range to a byte_range.
332 : Return true if it is possible, writing the result to *OUT.
333 : Otherwise return false. */
334 :
335 : bool
336 0 : bit_range::as_byte_range (byte_range *out) const
337 : {
338 0 : if (m_start_bit_offset % BITS_PER_UNIT == 0
339 0 : && m_size_in_bits % BITS_PER_UNIT == 0)
340 : {
341 0 : out->m_start_byte_offset = m_start_bit_offset / BITS_PER_UNIT;
342 0 : out->m_size_in_bytes = m_size_in_bits / BITS_PER_UNIT;
343 0 : return true;
344 : }
345 : return false;
346 : }
347 :
348 : /* Dump this object to PP. */
349 :
350 : void
351 0 : byte_range::dump_to_pp (pretty_printer *pp) const
352 : {
353 0 : if (m_size_in_bytes == 0)
354 : {
355 0 : pp_string (pp, "empty");
356 : }
357 0 : else if (m_size_in_bytes == 1)
358 : {
359 0 : pp_string (pp, "byte ");
360 0 : pp_wide_int (pp, m_start_byte_offset, SIGNED);
361 : }
362 : else
363 : {
364 0 : pp_string (pp, "bytes ");
365 0 : pp_wide_int (pp, m_start_byte_offset, SIGNED);
366 0 : pp_string (pp, "-");
367 0 : pp_wide_int (pp, get_last_byte_offset (), SIGNED);
368 : }
369 0 : }
370 :
371 : /* Dump this object to stderr. */
372 :
373 : DEBUG_FUNCTION void
374 0 : byte_range::dump () const
375 : {
376 0 : tree_dump_pretty_printer pp (stderr);
377 0 : dump_to_pp (&pp);
378 0 : pp_newline (&pp);
379 0 : }
380 :
381 : /* Generate a JSON value for this byte_range.
382 : This is intended for debugging the analyzer rather
383 : than serialization. */
384 :
385 : std::unique_ptr<json::object>
386 0 : byte_range::to_json () const
387 : {
388 0 : auto obj = std::make_unique<json::object> ();
389 0 : obj->set ("start_byte_offset",
390 0 : byte_offset_to_json (m_start_byte_offset));
391 0 : obj->set ("size_in_bytes",
392 0 : byte_offset_to_json (m_size_in_bytes));
393 0 : return obj;
394 : }
395 :
396 : /* If OTHER is a subset of this, return true and write
397 : to *OUT the relative range of OTHER within this.
398 : Otherwise return false. */
399 :
400 : bool
401 0 : byte_range::contains_p (const byte_range &other, byte_range *out) const
402 : {
403 0 : if (contains_p (other.get_start_byte_offset ())
404 0 : && contains_p (other.get_last_byte_offset ()))
405 : {
406 0 : out->m_start_byte_offset = other.m_start_byte_offset - m_start_byte_offset;
407 0 : out->m_size_in_bytes = other.m_size_in_bytes;
408 0 : return true;
409 : }
410 : else
411 : return false;
412 : }
413 :
414 : /* qsort comparator for byte ranges. */
415 :
416 : int
417 0 : byte_range::cmp (const byte_range &br1, const byte_range &br2)
418 : {
419 : /* Order first by offset. */
420 0 : if (int start_cmp = wi::cmps (br1.m_start_byte_offset,
421 0 : br2.m_start_byte_offset))
422 : return start_cmp;
423 :
424 : /* ...then by size. */
425 0 : return wi::cmpu (br1.m_size_in_bytes, br2.m_size_in_bytes);
426 : }
427 :
428 : static const svalue *
429 29810 : simplify_for_binding (const svalue *sval)
430 : {
431 29810 : if (const svalue *cast_sval = sval->maybe_undo_cast ())
432 574 : sval = cast_sval;
433 29810 : return sval;
434 : }
435 :
436 : /* class binding_cluster. */
437 :
438 718396 : binding_cluster::binding_cluster (symbolic::node_manager &node_mgr,
439 : const region *base_region,
440 : const symbolic::bit_contents &contents)
441 718396 : : m_node_mgr (node_mgr),
442 718396 : m_base_region (base_region),
443 718396 : m_contents (&contents),
444 718396 : m_escaped (false), m_touched (false)
445 : {
446 718396 : if (CHECKING_P)
447 : {
448 718396 : gcc_assert (base_region);
449 718396 : gcc_assert (base_region->base_region_p ());
450 :
451 : /* We shouldn't create clusters for dereferencing an UNKNOWN ptr. */
452 718396 : gcc_assert (!base_region->symbolic_for_unknown_ptr_p ());
453 :
454 : /* We shouldn't create clusters for base regions that aren't trackable. */
455 718396 : gcc_assert (base_region->tracked_p ());
456 : }
457 718396 : }
458 :
459 : /* binding_cluster's copy ctor. */
460 :
461 16667178 : binding_cluster::binding_cluster (const binding_cluster &other)
462 16667178 : : m_node_mgr (other.m_node_mgr),
463 16667178 : m_base_region (other.m_base_region),
464 16667178 : m_contents (other.m_contents),
465 16667178 : m_escaped (other.m_escaped), m_touched (other.m_touched)
466 : {
467 16667178 : }
468 :
469 : /* binding_cluster's assignment operator. */
470 :
471 : binding_cluster&
472 0 : binding_cluster::operator= (const binding_cluster &other)
473 : {
474 0 : gcc_assert (m_base_region == other.m_base_region);
475 0 : m_contents = other.m_contents;
476 0 : m_escaped = other.m_escaped;
477 0 : m_touched = other.m_touched;
478 0 : return *this;
479 : }
480 :
481 : /* binding_cluster's equality operator. */
482 :
483 : bool
484 1908648 : binding_cluster::operator== (const binding_cluster &other) const
485 : {
486 1908648 : if (m_contents != other.m_contents)
487 : return false;
488 :
489 1879186 : if (m_base_region != other.m_base_region)
490 : return false;
491 :
492 1879186 : if (m_escaped != other.m_escaped)
493 : return false;
494 :
495 1879099 : if (m_touched != other.m_touched)
496 0 : return false;
497 :
498 : return true;
499 : }
500 :
501 : /* Generate a hash value for this binding_cluster. */
502 :
503 : hashval_t
504 9311839 : binding_cluster::hash () const
505 : {
506 9311839 : inchash::hash h;
507 9311839 : h.add_int (m_contents->get_id ());
508 :
509 9311839 : h.add_flag (m_escaped);
510 9311839 : h.add_flag (m_touched);
511 9311839 : h.commit_flag ();
512 :
513 9311839 : return h.end ();
514 : }
515 :
516 : /* Return true if this binding_cluster is symbolic
517 : i.e. its base region is symbolic. */
518 :
519 : bool
520 4546158 : binding_cluster::symbolic_p () const
521 : {
522 4546158 : return m_base_region->get_kind () == RK_SYMBOLIC;
523 : }
524 :
525 : DEBUG_FUNCTION void
526 0 : binding_cluster::dump () const
527 : {
528 0 : symbolic::dump_node_tree_to_stderr<binding_cluster> (*this);
529 0 : }
530 :
531 : /* Assert that this object is valid. */
532 :
533 : void
534 7912308 : binding_cluster::validate () const
535 : {
536 : // no-op
537 7912308 : }
538 :
539 : /* Return a new json::object of the form
540 : {"escaped": true/false,
541 : "touched": true/false,
542 : "map" : object for the binding_map. */
543 :
544 : std::unique_ptr<json::object>
545 14 : binding_cluster::to_json () const
546 : {
547 14 : auto cluster_obj = std::make_unique<json::object> ();
548 :
549 14 : cluster_obj->set_bool ("escaped", m_escaped);
550 14 : cluster_obj->set_bool ("touched", m_touched);
551 14 : cluster_obj->set ("contents", m_contents->to_json ());
552 :
553 14 : return cluster_obj;
554 : }
555 :
556 : std::unique_ptr<text_art::tree_widget>
557 1910 : binding_cluster::make_dump_widget (symbolic::node_dump_state &nds) const
558 : {
559 1910 : pretty_printer the_pp;
560 1910 : pretty_printer * const pp = &the_pp;
561 1910 : pp_format_decoder (pp) = default_tree_printer;
562 1910 : pp_show_color (pp) = true;
563 1910 : const bool simple = true;
564 :
565 1910 : m_base_region->dump_to_pp (pp, simple);
566 1910 : pp_string (pp, ": ");
567 :
568 1910 : if (escaped_p ())
569 446 : pp_string (pp, " (ESCAPED)");
570 1910 : if (touched_p ())
571 446 : pp_string (pp, " (TOUCHED)");
572 :
573 1910 : std::unique_ptr<text_art::tree_widget> cluster_widget
574 1910 : (text_art::tree_widget::make (nds, pp));
575 :
576 1910 : gcc_assert (m_contents);
577 3820 : cluster_widget->add_child (m_contents->make_dump_widget (nds));
578 :
579 3820 : return cluster_widget;
580 1910 : }
581 :
582 : const symbolic::bit_vector &
583 973862 : binding_cluster::get_bits (symbolic_bit_range bit_range) const
584 : {
585 973862 : return m_contents->get_bits (bit_range);
586 : }
587 :
588 : void
589 281846 : binding_cluster::set_bits (symbolic_bit_range bit_range,
590 : const symbolic::bit_vector &bv,
591 : uncertainty_t *uncertainty)
592 : {
593 281846 : m_contents = &m_contents->set_bits (bit_range, bv, uncertainty);
594 281846 : }
595 :
596 : /* Mark this cluster as being unknown.
597 :
598 : If UNCERTAINTY is non-NULL, use it to record any svalues that
599 : had bindings to them removed, as being maybe-bound.
600 : If MAYBE_LIVE_VALUES is non-NULL, use it to record any svalues that
601 : had bindings to them removed, as being maybe-live. */
602 :
603 : void
604 18064 : binding_cluster::mark_as_untracked (symbolic::node_manager &node_mgr,
605 : uncertainty_t *uncertainty,
606 : value_set *maybe_live_values)
607 : {
608 18064 : if (uncertainty)
609 : {
610 14844 : m_contents->for_each_value ([] (const symbolic::value_node &val,
611 : void *user_data) -> iter_result
612 : {
613 31492 : uncertainty_t *uncertainty = static_cast<uncertainty_t *> (user_data);
614 31492 : uncertainty->on_maybe_bound_value (val);
615 31492 : return val.for_each_svalue ([] (const svalue &sval,
616 : void *user_data) -> iter_result
617 : {
618 : uncertainty_t *uncertainty = static_cast<uncertainty_t *> (user_data);
619 : uncertainty->on_maybe_bound_value (sval);
620 : return iter_result::keep_going;
621 31492 : }, user_data);
622 : }, uncertainty);
623 : }
624 18064 : if (maybe_live_values)
625 : {
626 17541 : m_contents->for_each_value ([] (const symbolic::value_node &val,
627 : void *user_data) -> iter_result
628 : {
629 34802 : value_set *maybe_live_values = static_cast<value_set *> (user_data);
630 34802 : maybe_live_values->add (&val);
631 34802 : return val.for_each_svalue ([] (const svalue &sval,
632 : void *user_data) -> iter_result
633 : {
634 : value_set *maybe_live_values = static_cast<value_set *> (user_data);
635 : maybe_live_values->add (&sval);
636 : return iter_result::keep_going;
637 34802 : }, user_data);
638 : }, maybe_live_values);
639 : }
640 :
641 18064 : value_set maybe_live;
642 18064 : m_contents->for_each_value ([] (const symbolic::value_node &val,
643 : void *user_data) -> iter_result
644 : {
645 : value_set *maybe_live = static_cast<value_set *> (user_data);
646 : maybe_live->add (&val);
647 : return iter_result::keep_going;
648 : }, &maybe_live);
649 :
650 18064 : auto &bc_mgr = node_mgr.get_bit_contents_manager ();
651 18064 : m_contents = &bc_mgr.get_untracked (std::move (maybe_live));
652 18064 : }
653 :
654 : /* Purge state involving NODE. */
655 :
656 : void
657 332521 : binding_cluster::purge_state_involving (const symbolic::node &node)
658 : {
659 332521 : m_contents = &m_contents->purge_state_involving (node);
660 332521 : }
661 :
662 : /* Attempt to merge CLUSTER_A and CLUSTER_B into OUT_CLUSTER, using
663 : MGR and MERGER.
664 : Return true if they can be merged, false otherwise. */
665 :
666 : bool
667 447453 : binding_cluster::can_merge_p (const binding_cluster *cluster_a,
668 : const binding_cluster *cluster_b,
669 : binding_cluster *out_cluster,
670 : store *out_store,
671 : model_merger *merger)
672 : {
673 447453 : gcc_assert (out_cluster);
674 :
675 : /* Merge flags ("ESCAPED" and "TOUCHED") by setting the merged flag to
676 : true if either of the inputs is true. */
677 447453 : if ((cluster_a && cluster_a->m_escaped)
678 305448 : || (cluster_b && cluster_b->m_escaped))
679 991 : out_cluster->m_escaped = true;
680 447453 : if ((cluster_a && cluster_a->m_touched)
681 346019 : || (cluster_b && cluster_b->m_touched))
682 103229 : out_cluster->m_touched = true;
683 :
684 472765 : auto get_baseline_state = [merger] () -> baseline_state
685 : {
686 25312 : return merger->m_model_a->get_baseline_state ();
687 447453 : };
688 :
689 : /* At least one of CLUSTER_A and CLUSTER_B are non-NULL, but either
690 : could be NULL. Handle these cases. */
691 447453 : if (cluster_a == nullptr)
692 : {
693 4212 : gcc_assert (cluster_b != nullptr);
694 4212 : gcc_assert (cluster_b->m_base_region == out_cluster->m_base_region);
695 4212 : out_cluster->make_unknown_relative_to (cluster_b, out_store,
696 : get_baseline_state ());
697 4212 : return true;
698 : }
699 443241 : if (cluster_b == nullptr)
700 : {
701 21100 : gcc_assert (cluster_a != nullptr);
702 21100 : gcc_assert (cluster_a->m_base_region == out_cluster->m_base_region);
703 21100 : out_cluster->make_unknown_relative_to (cluster_a, out_store,
704 : get_baseline_state ());
705 21100 : return true;
706 : }
707 :
708 : /* The "both inputs are non-NULL" case. */
709 422141 : gcc_assert (cluster_a != nullptr && cluster_b != nullptr);
710 422141 : gcc_assert (cluster_a->m_base_region == out_cluster->m_base_region);
711 422141 : gcc_assert (cluster_b->m_base_region == out_cluster->m_base_region);
712 :
713 422141 : tree type = nullptr;
714 422141 : if (cluster_a->get_base_region ()->get_type ()
715 391499 : && cluster_b->get_base_region ()->get_type ()
716 422141 : && (cluster_a->get_base_region ()->get_type ()
717 391499 : == cluster_b->get_base_region ()->get_type ()))
718 : type = cluster_a->get_base_region ()->get_type ();
719 :
720 844282 : if (auto *merged_contents
721 422141 : = symbolic::bit_contents::can_merge_p (*cluster_a->m_contents,
722 422141 : *cluster_b->m_contents,
723 : type,
724 : merger))
725 : {
726 404108 : out_cluster->m_contents = merged_contents;
727 404108 : return true;
728 : }
729 :
730 : return false;
731 : }
732 :
733 : /* Concrete visitor subclass, where any svalues that are visited are
734 : to be treated as possibly alive: regions pointed to are marked
735 : as escaping, and the svalues are added to any uncertainty_y. */
736 :
737 889 : class possibly_overwritten_values_visitor : public symbolic::node_visitor
738 : {
739 : public:
740 26201 : possibly_overwritten_values_visitor (store &store_,
741 : uncertainty_t *uncertainty,
742 : baseline_state bs)
743 26201 : : m_store (store_),
744 26201 : m_uncertainty (uncertainty),
745 26201 : m_baseline_state (bs)
746 : {
747 : }
748 :
749 : bool
750 100571 : visit_svalue (const svalue &n) final override
751 : {
752 100571 : if (!visit_node (n))
753 : return false;
754 100571 : m_maybe_live.add (&n);
755 100571 : if (auto *sym_ptr = n.maybe_get_symbolic_pointer ())
756 2205 : m_store.mark_as_escaped (&sym_ptr->get_base_region (),
757 : m_baseline_state);
758 100571 : if (m_uncertainty)
759 574 : m_uncertainty->on_maybe_bound_value (n);
760 : return true;
761 : }
762 :
763 : bool
764 29254 : visit_bit_vector (const symbolic::bit_vector &bv) final override
765 : {
766 29254 : if (!visit_node (bv))
767 : return false;
768 29254 : m_maybe_live.add (&bv);
769 29254 : if (m_uncertainty)
770 846 : m_uncertainty->on_maybe_bound_value (bv);
771 : return true;
772 : }
773 :
774 : const value_set &
775 : get_maybe_live () const { return m_maybe_live; }
776 :
777 : private:
778 : store &m_store;
779 : uncertainty_t *m_uncertainty;
780 : baseline_state m_baseline_state;
781 : value_set m_maybe_live;
782 : };
783 :
784 : /* Update this cluster to reflect an attempt to merge OTHER where there
785 : is no other cluster to merge with, and so we're notionally merging the
786 : bound values in OTHER with the initial value of the relevant regions.
787 :
788 : Any bound keys in OTHER should be bound to unknown in this. */
789 :
790 : void
791 25312 : binding_cluster::make_unknown_relative_to (const binding_cluster *other,
792 : store *out_store,
793 : baseline_state bs)
794 : {
795 25312 : gcc_assert (other);
796 25312 : gcc_assert (m_base_region == other->m_base_region);
797 :
798 25312 : auto &bcm = m_node_mgr.get_bit_contents_manager ();
799 :
800 25312 : possibly_overwritten_values_visitor v (*out_store,
801 : nullptr,
802 25312 : bs);
803 25312 : other->m_contents->accept_node_visitor (v);
804 :
805 25312 : m_contents = &bcm.get_untracked (v.get_maybe_live ());
806 25312 : }
807 :
808 : iter_result
809 5001134 : binding_cluster::
810 : for_each_value (iter_result (*cb) (const symbolic::value_node &val,
811 : void *user_data),
812 : void *user_data) const
813 : {
814 5001134 : return m_contents->for_each_value (cb, user_data);
815 : }
816 :
817 : /* Mark this cluster as having escaped. */
818 :
819 : void
820 33710 : binding_cluster::mark_as_escaped ()
821 : {
822 33710 : m_escaped = true;
823 33710 : }
824 :
825 : /* If this cluster has escaped (by this call, or by an earlier one, or
826 : by being an external param), then unbind all values and mark it
827 : as "touched", so that it has a conjured value, rather than an
828 : initial_svalue.
829 : Use P to purge state involving conjured_svalues. */
830 :
831 : void
832 111842 : binding_cluster::on_unknown_fncall (const gcall &call,
833 : const conjured_purge &p)
834 : {
835 111842 : if (m_escaped)
836 18940 : mark_region_as_conjured (call, p);
837 111842 : }
838 :
839 : void
840 19954 : binding_cluster::mark_region_as_conjured (const gimple &stmt,
841 : const conjured_purge &p)
842 : {
843 19954 : auto &bc_mgr = m_node_mgr.get_bit_contents_manager ();
844 19954 : m_contents = &bc_mgr.get_conjured_bit_contents (*m_base_region,
845 : &stmt,
846 : p);
847 19954 : m_touched = true;
848 19954 : }
849 :
850 : /* Mark this cluster as having been clobbered by STMT.
851 : Use P to purge state involving conjured_svalues. */
852 :
853 : void
854 510 : binding_cluster::on_asm (const gasm *stmt,
855 : const conjured_purge &p)
856 : {
857 510 : mark_region_as_conjured (*stmt, p);
858 510 : }
859 :
860 : /* Return true if this cluster has escaped. */
861 :
862 : bool
863 5335551 : binding_cluster::escaped_p () const
864 : {
865 : /* Consider the "errno" region to always have escaped. */
866 5335551 : if (m_base_region->get_kind () == RK_ERRNO)
867 : return true;
868 :
869 : /* Symbolic regions arising from dereferencing a conjured pointer
870 : are escaped, as the conjured pointer originates from "outside". */
871 5328550 : if (auto *sym_reg = m_base_region->dyn_cast_symbolic_region ())
872 : {
873 1110155 : const svalue *ptr = sym_reg->get_pointer ();
874 1110155 : if (ptr->conjured_p ())
875 : return true;
876 : }
877 :
878 5290657 : return m_escaped;
879 : }
880 :
881 : /* Return true if this binding_cluster has no information
882 : i.e. if it has its implicit contents, and it hasn't been marked as having
883 : escaped, or touched symbolically. */
884 :
885 : bool
886 596 : binding_cluster::redundant_p (const store &store_,
887 : baseline_state bs) const
888 : {
889 596 : if (m_escaped || m_touched)
890 : return false;
891 :
892 269 : auto &implicit_bc = store_.get_implicit_contents (*m_base_region, bs);
893 :
894 269 : return m_contents == &implicit_bc;
895 : }
896 :
897 : /* Add PV to OUT_PVS, casting it to TYPE if it is not already of that type. */
898 :
899 : void
900 7659 : append_pathvar_with_type (path_var pv,
901 : tree type,
902 : auto_vec<path_var> *out_pvs)
903 : {
904 7659 : gcc_assert (pv.m_tree);
905 :
906 7659 : if (type && TREE_TYPE (pv.m_tree) != type)
907 2984 : pv.m_tree = build1 (NOP_EXPR, type, pv.m_tree);
908 :
909 7659 : out_pvs->safe_push (pv);
910 7659 : }
911 :
912 : /* Find representative path_vars for SVAL within this binding of BASE_REG,
913 : appending the results to OUT_PVS. */
914 :
915 : void
916 29810 : binding_cluster::get_representative_path_vars (const region_model *model,
917 : value_set *visited,
918 : const region *base_reg,
919 : const svalue *sval,
920 : logger *logger,
921 : auto_vec<path_var> *out_pvs)
922 : const
923 : {
924 29810 : tree desired_type = sval->get_type ();
925 29810 : sval = simplify_for_binding (sval);
926 :
927 29810 : m_contents->get_representative_path_vars (model,
928 : visited,
929 : base_reg,
930 : sval,
931 : desired_type,
932 : logger,
933 : out_pvs);
934 29810 : }
935 :
936 : void
937 125680 : binding_cluster::poison_any_pointers_to_descendents (const region *reg,
938 : enum poison_kind pkind)
939 : {
940 125680 : m_contents = &m_contents->poison_any_pointers_to_descendents (reg, pkind);
941 125680 : }
942 :
943 : bool
944 1343613 : binding_cluster::
945 : bits_live_p (const symbolic::bit_vector_from_ubc &bv_from_ubc) const
946 : {
947 1343613 : return m_contents->bits_live_p (bv_from_ubc);
948 : }
949 :
950 : /* class store. */
951 :
952 : /* store's default ctor. */
953 :
954 195403 : store::store (symbolic::node_manager &node_mgr)
955 195403 : : m_node_mgr (node_mgr),
956 195403 : m_called_unknown_fn (false)
957 : {
958 195403 : }
959 :
960 : /* store's copy ctor. */
961 :
962 2720490 : store::store (const store &other)
963 2720490 : : m_node_mgr (other.m_node_mgr),
964 2720490 : m_cluster_map (other.m_cluster_map.elements ()),
965 2720490 : m_called_unknown_fn (other.m_called_unknown_fn)
966 : {
967 2720490 : for (cluster_map_t::iterator iter = other.m_cluster_map.begin ();
968 18894606 : iter != other.m_cluster_map.end ();
969 16174116 : ++iter)
970 : {
971 16174116 : const region *reg = (*iter).first;
972 0 : gcc_assert (reg);
973 16174116 : binding_cluster *c = (*iter).second;
974 16174116 : gcc_assert (c);
975 16174116 : m_cluster_map.put (reg, new binding_cluster (*c));
976 : }
977 2720490 : }
978 :
979 : /* store's dtor. */
980 :
981 2915893 : store::~store ()
982 : {
983 19950913 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
984 19950913 : iter != m_cluster_map.end ();
985 17035020 : ++iter)
986 17035020 : delete (*iter).second;
987 2915893 : }
988 :
989 : /* store's assignment operator. */
990 :
991 : store &
992 58968 : store::operator= (const store &other)
993 : {
994 : /* Delete existing cluster map. */
995 200612 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
996 200612 : iter != m_cluster_map.end ();
997 141644 : ++iter)
998 141644 : delete (*iter).second;
999 58968 : m_cluster_map.empty ();
1000 :
1001 58968 : m_called_unknown_fn = other.m_called_unknown_fn;
1002 :
1003 58968 : for (cluster_map_t::iterator iter = other.m_cluster_map.begin ();
1004 552030 : iter != other.m_cluster_map.end ();
1005 493062 : ++iter)
1006 : {
1007 493062 : const region *reg = (*iter).first;
1008 493062 : gcc_assert (reg);
1009 493062 : binding_cluster *c = (*iter).second;
1010 493062 : gcc_assert (c);
1011 493062 : m_cluster_map.put (reg, new binding_cluster (*c));
1012 : }
1013 58968 : return *this;
1014 : }
1015 :
1016 : /* store's equality operator. */
1017 :
1018 : bool
1019 437680 : store::operator== (const store &other) const
1020 : {
1021 437680 : if (m_called_unknown_fn != other.m_called_unknown_fn)
1022 : return false;
1023 :
1024 434227 : if (m_cluster_map.elements () != other.m_cluster_map.elements ())
1025 : return false;
1026 :
1027 2294727 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
1028 2294727 : iter != m_cluster_map.end ();
1029 1879099 : ++iter)
1030 : {
1031 1910295 : const region *reg = (*iter).first;
1032 1910295 : binding_cluster *c = (*iter).second;
1033 1910295 : binding_cluster **other_slot
1034 1910295 : = const_cast <cluster_map_t &> (other.m_cluster_map).get (reg);
1035 1910295 : if (other_slot == nullptr)
1036 31196 : return false;
1037 1908648 : if (*c != **other_slot)
1038 : return false;
1039 : }
1040 :
1041 384432 : gcc_checking_assert (hash () == other.hash ());
1042 :
1043 : return true;
1044 : }
1045 :
1046 : /* Get a hash value for this store. */
1047 :
1048 : hashval_t
1049 1943575 : store::hash () const
1050 : {
1051 1943575 : hashval_t result = 0;
1052 1943575 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
1053 11255414 : iter != m_cluster_map.end ();
1054 9311839 : ++iter)
1055 9311839 : result ^= (*iter).second->hash ();
1056 1943575 : return result;
1057 : }
1058 :
1059 : /* Populate OUT with a sorted list of parent regions for the regions in IN,
1060 : removing duplicate parents. */
1061 :
1062 : static void
1063 739 : get_sorted_parent_regions (auto_vec<const region *> *out,
1064 : auto_vec<const region *> &in)
1065 : {
1066 : /* Get the set of parent regions. */
1067 739 : hash_set<const region *> parent_regions;
1068 739 : const region *iter_reg;
1069 739 : unsigned i;
1070 3402 : FOR_EACH_VEC_ELT (in, i, iter_reg)
1071 : {
1072 1924 : const region *parent_reg = iter_reg->get_parent_region ();
1073 1924 : gcc_assert (parent_reg);
1074 1924 : parent_regions.add (parent_reg);
1075 : }
1076 :
1077 : /* Write to OUT. */
1078 739 : for (hash_set<const region *>::iterator iter = parent_regions.begin();
1079 1765 : iter != parent_regions.end(); ++iter)
1080 1026 : out->safe_push (*iter);
1081 :
1082 : /* Sort OUT. */
1083 1337 : out->qsort (region::cmp_ptr_ptr);
1084 739 : }
1085 :
1086 : /* Dump a tree-like representation of this store to stderr. */
1087 :
1088 : DEBUG_FUNCTION void
1089 0 : store::dump () const
1090 : {
1091 0 : symbolic::dump_node_tree_to_stderr<store> (*this);
1092 0 : }
1093 :
1094 : /* Assert that this object is valid. */
1095 :
1096 : void
1097 1599565 : store::validate () const
1098 : {
1099 9511873 : for (auto iter : m_cluster_map)
1100 7912308 : iter.second->validate ();
1101 1599565 : }
1102 :
1103 : /* Return a new json::object of the form
1104 : {PARENT_REGION_DESC: {BASE_REGION_DESC: object for binding_map,
1105 : ... for each cluster within parent region},
1106 : ...for each parent region,
1107 : "called_unknown_fn": true/false}. */
1108 :
1109 : std::unique_ptr<json::object>
1110 19 : store::to_json () const
1111 : {
1112 19 : auto store_obj = std::make_unique<json::object> ();
1113 :
1114 : /* Sort into some deterministic order. */
1115 19 : auto_vec<const region *> base_regions;
1116 33 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
1117 33 : iter != m_cluster_map.end (); ++iter)
1118 : {
1119 14 : const region *base_reg = (*iter).first;
1120 14 : base_regions.safe_push (base_reg);
1121 : }
1122 19 : base_regions.qsort (region::cmp_ptr_ptr);
1123 :
1124 : /* Gather clusters, organize by parent region, so that we can group
1125 : together locals, globals, etc. */
1126 19 : auto_vec<const region *> parent_regions;
1127 19 : get_sorted_parent_regions (&parent_regions, base_regions);
1128 :
1129 19 : const region *parent_reg;
1130 19 : unsigned i;
1131 52 : FOR_EACH_VEC_ELT (parent_regions, i, parent_reg)
1132 : {
1133 14 : gcc_assert (parent_reg);
1134 :
1135 14 : auto clusters_in_parent_reg_obj = std::make_unique<json::object> ();
1136 :
1137 14 : const region *base_reg;
1138 14 : unsigned j;
1139 56 : FOR_EACH_VEC_ELT (base_regions, j, base_reg)
1140 : {
1141 : /* This is O(N * M), but N ought to be small. */
1142 14 : if (base_reg->get_parent_region () != parent_reg)
1143 0 : continue;
1144 14 : binding_cluster *cluster
1145 14 : = *const_cast<cluster_map_t &> (m_cluster_map).get (base_reg);
1146 14 : label_text base_reg_desc = base_reg->get_desc ();
1147 14 : clusters_in_parent_reg_obj->set (base_reg_desc.get (),
1148 14 : cluster->to_json ());
1149 14 : }
1150 14 : label_text parent_reg_desc = parent_reg->get_desc ();
1151 14 : store_obj->set (parent_reg_desc.get (),
1152 : std::move (clusters_in_parent_reg_obj));
1153 14 : }
1154 :
1155 19 : store_obj->set_bool ("called_unknown_fn", m_called_unknown_fn);
1156 :
1157 19 : return store_obj;
1158 19 : }
1159 :
1160 : static const char *
1161 0 : get_string_for_baseline_state (baseline_state bs)
1162 : {
1163 0 : switch (bs)
1164 : {
1165 0 : default:
1166 0 : gcc_unreachable ();
1167 :
1168 : case baseline_state::main:
1169 : return "main";
1170 :
1171 0 : case baseline_state::after_main:
1172 0 : return "after_main";
1173 : }
1174 : }
1175 :
1176 : std::unique_ptr<text_art::tree_widget>
1177 720 : store::make_dump_widget (symbolic::node_dump_state &nds) const
1178 : {
1179 720 : std::unique_ptr<text_art::tree_widget> store_widget
1180 720 : (text_art::tree_widget::make (nds, "Store"));
1181 :
1182 720 : store_widget->add_child
1183 1440 : (text_art::tree_widget::from_fmt (nds, nullptr,
1184 : "m_called_unknown_fn: %s",
1185 720 : m_called_unknown_fn ? "true" : "false"));
1186 :
1187 : /* Sort into some deterministic order. */
1188 720 : auto_vec<const region *> base_regions;
1189 2630 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
1190 2630 : iter != m_cluster_map.end (); ++iter)
1191 : {
1192 1910 : const region *base_reg = (*iter).first;
1193 1910 : base_regions.safe_push (base_reg);
1194 : }
1195 720 : base_regions.qsort (region::cmp_ptr_ptr);
1196 :
1197 : /* Gather clusters, organize by parent region, so that we can group
1198 : together locals, globals, etc. */
1199 720 : auto_vec<const region *> parent_regions;
1200 720 : get_sorted_parent_regions (&parent_regions, base_regions);
1201 :
1202 720 : const region *parent_reg;
1203 720 : unsigned i;
1204 2452 : FOR_EACH_VEC_ELT (parent_regions, i, parent_reg)
1205 : {
1206 1012 : gcc_assert (parent_reg);
1207 :
1208 1012 : pretty_printer the_pp;
1209 1012 : pretty_printer * const pp = &the_pp;
1210 1012 : pp_format_decoder (pp) = default_tree_printer;
1211 1012 : pp_show_color (pp) = true;
1212 1012 : const bool simple = true;
1213 :
1214 1012 : parent_reg->dump_to_pp (pp, simple);
1215 :
1216 1012 : std::unique_ptr<text_art::tree_widget> parent_reg_widget
1217 1012 : (text_art::tree_widget::make (nds, pp));
1218 :
1219 1012 : const region *base_reg;
1220 1012 : unsigned j;
1221 6682 : FOR_EACH_VEC_ELT (base_regions, j, base_reg)
1222 : {
1223 : /* This is O(N * M), but N ought to be small. */
1224 3646 : if (base_reg->get_parent_region () != parent_reg)
1225 1736 : continue;
1226 1910 : binding_cluster *cluster
1227 1910 : = *const_cast<cluster_map_t &> (m_cluster_map).get (base_reg);
1228 1910 : parent_reg_widget->add_child
1229 3820 : (cluster->make_dump_widget (nds));
1230 : }
1231 2024 : store_widget->add_child (std::move (parent_reg_widget));
1232 1012 : }
1233 :
1234 720 : return store_widget;
1235 720 : }
1236 :
1237 : const symbolic::bit_vector &
1238 2347437 : store::get_bits (const symbolic::memory_range &mem_range,
1239 : baseline_state bs) const
1240 : {
1241 2347437 : const region &base_reg = mem_range.get_base_region ();
1242 2347437 : binding_cluster **cluster_slot
1243 2347437 : = const_cast <cluster_map_t &> (m_cluster_map).get (&base_reg);
1244 2347437 : if (!cluster_slot)
1245 : {
1246 1373575 : auto &baseline = get_implicit_contents (base_reg, bs);
1247 1373575 : return baseline.get_bits (mem_range.get_bit_range ());
1248 : }
1249 :
1250 973862 : return (*cluster_slot)->get_bits (mem_range.get_bit_range ());
1251 : }
1252 :
1253 : const symbolic::bit_contents &
1254 14710 : store::get_bit_contents (const region &base_reg,
1255 : baseline_state bs) const
1256 : {
1257 14710 : binding_cluster **cluster_slot
1258 14710 : = const_cast <cluster_map_t &> (m_cluster_map).get (&base_reg);
1259 14710 : if (!cluster_slot)
1260 : {
1261 4781 : auto &bc = get_implicit_contents (base_reg, bs);
1262 4781 : return bc;
1263 : }
1264 :
1265 9929 : return (*cluster_slot)->get_bit_contents ();
1266 : }
1267 :
1268 : void
1269 673 : store::set_bits (const region *lhs_reg,
1270 : const symbolic::bit_vector &bits,
1271 : uncertainty_t *uncertainty,
1272 : const region_model &model)
1273 : {
1274 673 : auto mem_range = lhs_reg->get_memory_range (*model.get_manager ());
1275 673 : set_bits (mem_range, bits, uncertainty, model);
1276 673 : }
1277 :
1278 : void
1279 282201 : store::set_bits (const symbolic::memory_range &mem_range,
1280 : const symbolic::bit_vector &bv,
1281 : uncertainty_t *uncertainty,
1282 : const region_model &model)
1283 : {
1284 282201 : logger *logger = model.get_manager ()->get_logger ();
1285 282201 : LOG_SCOPE (logger);
1286 :
1287 282201 : const region *lhs_base_reg = &mem_range.get_base_region ();
1288 282201 : binding_cluster *lhs_cluster;
1289 282201 : if (lhs_base_reg->symbolic_for_unknown_ptr_p ())
1290 : {
1291 : /* Reject attempting to bind values into a symbolic region
1292 : for an unknown ptr; merely invalidate values below. */
1293 889 : lhs_cluster = nullptr;
1294 :
1295 : /* The LHS of the write is *UNKNOWN. If BITS contains any pointers,
1296 : then treat any region being pointed to as having escaped. */
1297 889 : possibly_overwritten_values_visitor v (*this, uncertainty,
1298 889 : model.get_baseline_state ());
1299 889 : bv.accept_node_visitor (v);
1300 889 : }
1301 281312 : else if (lhs_base_reg->tracked_p ())
1302 : {
1303 281250 : lhs_cluster = get_or_create_cluster (lhs_base_reg,
1304 : model.get_baseline_state ());
1305 281250 : lhs_cluster->set_bits (mem_range.get_bit_range (), bv,
1306 : uncertainty);
1307 : }
1308 : else
1309 : {
1310 : /* Reject attempting to bind values into an untracked region;
1311 : merely invalidate values below. */
1312 : lhs_cluster = nullptr;
1313 : }
1314 :
1315 : /* Bindings to a cluster can affect other clusters if a symbolic
1316 : base region is involved.
1317 : Writes to concrete clusters can't affect other concrete clusters,
1318 : but can affect symbolic clusters.
1319 : Writes to symbolic clusters can affect both concrete and symbolic
1320 : clusters.
1321 : Invalidate our knowledge of other clusters that might have been
1322 : affected by the write.
1323 : Gather the set of all svalues that might still be live even if
1324 : the store doesn't refer to them. */
1325 282201 : value_set maybe_live_values;
1326 2864096 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
1327 2864096 : iter != m_cluster_map.end (); ++iter)
1328 : {
1329 2581895 : const region *iter_base_reg = (*iter).first;
1330 2581895 : binding_cluster *iter_cluster = (*iter).second;
1331 2581895 : if (iter_base_reg != lhs_base_reg
1332 2581895 : && (lhs_cluster == nullptr
1333 2289875 : || lhs_cluster->symbolic_p ()
1334 2256283 : || iter_cluster->symbolic_p ()))
1335 : {
1336 371587 : tristate t_alias = eval_alias (lhs_base_reg, iter_base_reg,
1337 : model);
1338 371587 : switch (t_alias.get_value ())
1339 : {
1340 0 : default:
1341 0 : gcc_unreachable ();
1342 :
1343 17541 : case tristate::TS_UNKNOWN:
1344 17541 : if (logger)
1345 : {
1346 0 : pretty_printer *pp = logger->get_printer ();
1347 0 : logger->start_log_line ();
1348 0 : logger->log_partial ("possible aliasing of ");
1349 0 : iter_base_reg->dump_to_pp (pp, true);
1350 0 : logger->log_partial (" when writing SVAL: ");
1351 : #if 0
1352 : rhs_sval->dump_to_pp (pp, true);
1353 : logger->log_partial (" to LHS_REG: ");
1354 : lhs_reg->dump_to_pp (pp, true);
1355 : #endif
1356 0 : logger->end_log_line ();
1357 : }
1358 : /* Mark all of iter_cluster's as untracked,
1359 : to handle symbolic vs concrete issues. */
1360 17541 : iter_cluster->mark_as_untracked
1361 17541 : (model.get_manager ()->get_node_manager (),
1362 : uncertainty,
1363 : &maybe_live_values);
1364 17541 : break;
1365 :
1366 0 : case tristate::TS_TRUE:
1367 0 : gcc_unreachable ();
1368 : break;
1369 :
1370 : case tristate::TS_FALSE:
1371 : /* If they can't be aliases, then don't invalidate this
1372 : cluster. */
1373 : break;
1374 : }
1375 : }
1376 : }
1377 :
1378 : /* Given the set of svalues that might still be live, process them
1379 : (e.g. marking regions as escaped).
1380 : We do this after the iteration to avoid potentially changing
1381 : m_cluster_map whilst iterating over it. */
1382 282201 : on_maybe_live_values (maybe_live_values,
1383 : model.get_baseline_state ());
1384 282201 : }
1385 :
1386 : void
1387 5578 : store::set_bit_contents_raw (const region &base_reg,
1388 : const symbolic::bit_contents &bc,
1389 : const region_model &model)
1390 : {
1391 5578 : logger *logger = model.get_manager ()->get_logger ();
1392 5578 : LOG_SCOPE (logger);
1393 :
1394 5578 : if (base_reg.tracked_p ())
1395 : {
1396 5578 : auto *cluster = get_or_create_cluster (&base_reg,
1397 : model.get_baseline_state ());
1398 5578 : cluster->set_bit_contents (bc);
1399 : }
1400 5578 : }
1401 :
1402 : /* Determine if BASE_REG_A could be an alias of BASE_REG_B.
1403 : Use information from MODEL when comparing pointers. */
1404 :
1405 : tristate
1406 372543 : store::eval_alias (const region *base_reg_a,
1407 : const region *base_reg_b,
1408 : const region_model &model) const
1409 : {
1410 372543 : if (base_reg_a == base_reg_b)
1411 344 : return tristate (true);
1412 :
1413 : /* SSA names can't alias. */
1414 372199 : tree decl_a = base_reg_a->maybe_get_decl ();
1415 372199 : if (decl_a && TREE_CODE (decl_a) == SSA_NAME)
1416 293550 : return tristate::TS_FALSE;
1417 78649 : tree decl_b = base_reg_b->maybe_get_decl ();
1418 78649 : if (decl_b && TREE_CODE (decl_b) == SSA_NAME)
1419 26557 : return tristate::TS_FALSE;
1420 :
1421 : /* Different decls don't alias. */
1422 52092 : if (decl_a && decl_b && decl_a != decl_b)
1423 212 : return tristate::TS_FALSE;
1424 :
1425 : /* Try both ways, for symmetry. */
1426 51880 : tristate ts_ab = eval_alias_1 (base_reg_a, base_reg_b, model);
1427 51880 : if (ts_ab.is_false ())
1428 3637 : return tristate::TS_FALSE;
1429 48243 : tristate ts_ba = eval_alias_1 (base_reg_b, base_reg_a, model);
1430 48243 : if (ts_ba.is_false ())
1431 30352 : return tristate::TS_FALSE;
1432 :
1433 17891 : gcc_assert (base_reg_a != base_reg_b);
1434 17891 : enum region_kind kind_a = base_reg_a->get_kind ();
1435 17891 : enum region_kind kind_b = base_reg_b->get_kind ();
1436 17891 : if (kind_a == kind_b)
1437 : {
1438 : /* We have two different base region instances of the same kind.
1439 : For many kinds of region this implies they must have different
1440 : addresses. */
1441 10445 : switch (kind_a)
1442 : {
1443 : /* Invalid cases. */
1444 :
1445 0 : default:
1446 0 : gcc_unreachable ();
1447 :
1448 0 : case RK_CODE:
1449 0 : case RK_ERRNO:
1450 0 : case RK_GLOBALS:
1451 0 : case RK_HEAP:
1452 0 : case RK_ROOT:
1453 0 : case RK_STACK:
1454 0 : case RK_THREAD_LOCAL:
1455 : /* We expect these to be singletons. */
1456 0 : gcc_unreachable ();
1457 :
1458 0 : case RK_BIT_RANGE:
1459 0 : case RK_CAST:
1460 0 : case RK_ELEMENT:
1461 0 : case RK_FIELD:
1462 0 : case RK_OFFSET:
1463 0 : case RK_SIZED:
1464 : /* These aren't base regions. */
1465 0 : gcc_unreachable ();
1466 :
1467 : /* Valid cases. */
1468 :
1469 45 : case RK_ALLOCA:
1470 45 : case RK_DECL:
1471 45 : case RK_FRAME:
1472 45 : case RK_FUNCTION:
1473 45 : case RK_LABEL:
1474 45 : case RK_PRIVATE:
1475 45 : case RK_VAR_ARG:
1476 : /* We expect different regions of these kinds to have
1477 : different addresses. */
1478 45 : return tristate (false);
1479 :
1480 289 : case RK_HEAP_ALLOCATED:
1481 : /* We have results of two different heap allocations.
1482 : If they were non-zero-sized allocations they are different from
1483 : each other, but zero-sized allocations might alias.
1484 : Note that this doesn't handle the case where of a freed pointer
1485 : possibly being reused, but we don't have a way to distinguish
1486 : this case from the "two different allocations case", and it seems
1487 : much more important to keep the latter from aliasing each
1488 : other (for precision when tracking writes). */
1489 289 : {
1490 289 : tristate size_a_gt_zero (tristate::unknown ());
1491 289 : tristate size_b_gt_zero (tristate::unknown ());
1492 289 : const svalue *zero_size
1493 289 : = model.get_manager ()->get_or_create_int_cst (size_type_node, 0);
1494 :
1495 289 : if (auto sval_size_a = model.get_dynamic_extents (base_reg_a))
1496 : {
1497 267 : size_a_gt_zero = model.eval_condition (sval_size_a,
1498 : GT_EXPR,
1499 : zero_size);
1500 : }
1501 289 : if (auto sval_size_b = model.get_dynamic_extents (base_reg_b))
1502 : {
1503 224 : size_b_gt_zero = model.eval_condition (sval_size_b,
1504 : GT_EXPR,
1505 : zero_size);
1506 : }
1507 289 : if (size_a_gt_zero.is_known () && size_b_gt_zero.is_known ())
1508 : {
1509 : /* We have results of two different heap allocations, and for
1510 : each we know if the size was non-zero. */
1511 158 : if (size_a_gt_zero.is_false () && size_b_gt_zero.is_false ())
1512 : {
1513 : /* Different allocations, both zero-sized. We don't
1514 : know if they have the same address. */
1515 0 : return tristate::unknown ();
1516 : }
1517 : else
1518 : {
1519 : /* We either have different allocations of non-zero size,
1520 : or different allocations where one has non-zero size, the
1521 : other is zero-sized. We know these have different
1522 : addresses. */
1523 158 : return tristate (false);
1524 : }
1525 : }
1526 131 : if (size_a_gt_zero.is_true () || size_b_gt_zero.is_true ())
1527 : {
1528 : /* Different allocations, of which at least one > 0 in size.
1529 : They must have different addresses. */
1530 74 : return tristate (false);
1531 : }
1532 : /* At least one size might be zero. */
1533 57 : return tristate::unknown ();
1534 : }
1535 :
1536 10095 : case RK_SYMBOLIC:
1537 10095 : case RK_UNKNOWN:
1538 : /* We don't know that such regions are different from each other. */
1539 10095 : return tristate::unknown ();
1540 :
1541 16 : case RK_STRING:
1542 : /* For now, don't attempt to decide if string literals alias
1543 : each other. */
1544 16 : return tristate::unknown ();
1545 : }
1546 : }
1547 : else
1548 : {
1549 : /* We have two base region instances of different kinds.
1550 : For many kinds of region this implies they must have different
1551 : addresses. */
1552 7446 : if (kind_b == RK_SYMBOLIC || kind_b == RK_UNKNOWN)
1553 3342 : return tristate::unknown ();
1554 :
1555 4104 : switch (kind_a)
1556 : {
1557 : /* Invalid cases. */
1558 :
1559 0 : default:
1560 0 : gcc_unreachable ();
1561 :
1562 0 : case RK_CODE:
1563 0 : case RK_ERRNO:
1564 0 : case RK_GLOBALS:
1565 0 : case RK_HEAP:
1566 0 : case RK_ROOT:
1567 0 : case RK_STACK:
1568 0 : case RK_THREAD_LOCAL:
1569 : /* We expect these to be singletons. */
1570 0 : gcc_unreachable ();
1571 :
1572 0 : case RK_BIT_RANGE:
1573 0 : case RK_CAST:
1574 0 : case RK_ELEMENT:
1575 0 : case RK_FIELD:
1576 0 : case RK_OFFSET:
1577 0 : case RK_SIZED:
1578 : /* These aren't base regions. */
1579 0 : gcc_unreachable ();
1580 :
1581 : /* Valid cases. */
1582 :
1583 0 : case RK_ALLOCA:
1584 0 : case RK_DECL:
1585 0 : case RK_FRAME:
1586 0 : case RK_FUNCTION:
1587 0 : case RK_HEAP_ALLOCATED:
1588 0 : case RK_LABEL:
1589 0 : case RK_PRIVATE:
1590 0 : case RK_STRING:
1591 0 : case RK_VAR_ARG:
1592 : /* We expect regions of these kinds to have different addresses
1593 : from regions of other kinds (apart from symbolic/unknown). */
1594 0 : return tristate (false);
1595 :
1596 4104 : case RK_SYMBOLIC:
1597 4104 : case RK_UNKNOWN:
1598 : /* We don't know anything about such regions. */
1599 4104 : return tristate::unknown ();
1600 : }
1601 : }
1602 : }
1603 :
1604 : /* Half of store::eval_alias; called twice for symmetry. */
1605 :
1606 : tristate
1607 100123 : store::eval_alias_1 (const region *base_reg_a,
1608 : const region *base_reg_b,
1609 : const region_model &model) const
1610 : {
1611 100123 : gcc_assert (base_reg_a != base_reg_b);
1612 :
1613 : /* If they're in different memory spaces, they can't alias. */
1614 100123 : {
1615 100123 : enum memory_space memspace_a = base_reg_a->get_memory_space ();
1616 100123 : if (memspace_a != MEMSPACE_UNKNOWN)
1617 : {
1618 37329 : enum memory_space memspace_b = base_reg_b->get_memory_space ();
1619 37329 : if (memspace_b != MEMSPACE_UNKNOWN
1620 37329 : && memspace_a != memspace_b)
1621 78 : return tristate::TS_FALSE;
1622 : }
1623 : }
1624 :
1625 200090 : if (const symbolic_region *sym_reg_a
1626 100045 : = base_reg_a->dyn_cast_symbolic_region ())
1627 : {
1628 61547 : const svalue *sval_a = sym_reg_a->get_pointer ();
1629 61547 : if (tree decl_b = base_reg_b->maybe_get_decl ())
1630 : {
1631 32379 : if (!may_be_aliased (decl_b))
1632 15421 : return tristate::TS_FALSE;
1633 16958 : if (sval_a->derived_from_initial_value_p ())
1634 14600 : if (!is_global_var (decl_b))
1635 : {
1636 : /* The initial value of a pointer can't point to a local. */
1637 13298 : return tristate::TS_FALSE;
1638 : }
1639 : }
1640 32828 : if (sval_a->derived_from_initial_value_p ()
1641 32828 : && base_reg_b->get_kind () == RK_HEAP_ALLOCATED)
1642 : {
1643 : /* The initial value of a pointer can't point to a
1644 : region that was allocated on the heap after the beginning of the
1645 : path. */
1646 5192 : return tristate::TS_FALSE;
1647 : }
1648 55272 : if (const widening_svalue *widening_sval_a
1649 27636 : = sval_a->dyn_cast_widening_svalue ())
1650 : {
1651 1451 : const svalue *base = widening_sval_a->get_base_svalue ();
1652 2902 : if (const pointer_svalue *region_sval
1653 1451 : = base->dyn_cast_pointer_svalue ())
1654 : {
1655 0 : gcc_unreachable (); // FIXME
1656 : #if 0
1657 : const region *pointee = region_sval->get_pointee ();
1658 : /* If we have sval_a is WIDENING(®ION, OP), and
1659 : B can't alias REGION, then B can't alias A either.
1660 : For example, A might arise from
1661 : for (ptr = ®ION; ...; ptr++)
1662 : where sval_a is ptr in the 2nd iteration of the loop.
1663 : We want to ensure that "*ptr" can only clobber things
1664 : within REGION's base region. */
1665 : tristate ts = eval_alias (pointee->get_base_region (),
1666 : base_reg_b,
1667 : model);
1668 : if (ts.is_false ())
1669 : return tristate::TS_FALSE;
1670 : #endif
1671 : }
1672 : }
1673 : }
1674 :
1675 66134 : return tristate::TS_UNKNOWN;
1676 : }
1677 :
1678 :
1679 : const symbolic::bit_contents &
1680 2077083 : store::get_baseline_contents (const region &base_reg,
1681 : baseline_state bs) const
1682 : {
1683 2077083 : auto &mgr = m_node_mgr.get_bit_contents_manager ();
1684 2077083 : return mgr.get_baseline_contents (base_reg, bs);
1685 : }
1686 :
1687 : /* Get the bit_contents for BASE_REG at BS, for use when BASE_REG
1688 : does not have a binding_cluster (and is thus currently having
1689 : its contents modelled implicitly). */
1690 :
1691 : const symbolic::bit_contents &
1692 2097021 : store::get_implicit_contents (const region &base_reg,
1693 : baseline_state bs) const
1694 : {
1695 2097021 : if (m_called_unknown_fn
1696 2097021 : && base_reg.get_parent_region ()->get_kind () == RK_GLOBALS)
1697 36778 : if (tree decl = base_reg.maybe_get_decl ())
1698 36778 : if (TREE_PUBLIC (decl) && !TREE_READONLY (decl))
1699 : {
1700 14955 : auto &bc_mgr = m_node_mgr.get_bit_contents_manager ();
1701 14955 : return bc_mgr.get_untracked ({});
1702 : }
1703 2082066 : if (base_reg.symbolic_for_unknown_ptr_p ())
1704 : {
1705 4983 : auto &bc_mgr = m_node_mgr.get_bit_contents_manager ();
1706 4983 : return bc_mgr.get_untracked ({});
1707 : }
1708 :
1709 2077083 : return get_baseline_contents (base_reg, bs);
1710 : }
1711 :
1712 : /* Record all of the values in MAYBE_LIVE_VALUES as being possibly live. */
1713 :
1714 : void
1715 282201 : store::on_maybe_live_values (const value_set &maybe_live_values,
1716 : baseline_state bs)
1717 : {
1718 309684 : for (auto val : maybe_live_values)
1719 27483 : if (auto *sval = val->dyn_cast_svalue ())
1720 17591 : if (auto *sym_ptr = sval->maybe_get_symbolic_pointer ())
1721 : {
1722 722 : const region *base_reg = &sym_ptr->get_base_region ();
1723 722 : mark_as_escaped (base_reg, bs);
1724 : }
1725 282201 : }
1726 :
1727 : /* Return true iff the bits of BIT_RANGE from UBC are live within
1728 : this store. */
1729 :
1730 : bool
1731 287978 : store::bits_live_p (const symbolic::bit_vector_from_ubc &bv_from_ubc,
1732 : const region_model &model) const
1733 : {
1734 287978 : if (auto *baseline_bc
1735 287978 : = bv_from_ubc.get_bit_contents ().dyn_cast_baseline_bit_contents ())
1736 : {
1737 : /* Are the bits implicitly live due to the region
1738 : being untouched? */
1739 227297 : const region *base_reg = baseline_bc->get_baseline_key ().m_base_reg;
1740 227297 : symbolic::memory_range mem_range (*base_reg,
1741 227297 : bv_from_ubc.get_bit_range ());
1742 227297 : if (&get_bits (mem_range, model.get_baseline_state ()) == &bv_from_ubc)
1743 166105 : return true;
1744 : }
1745 :
1746 1421270 : for (auto iter : m_cluster_map)
1747 : {
1748 1343613 : const region *base_reg = iter.first;
1749 1343613 : binding_cluster *cluster = iter.second;
1750 1343613 : if (cluster->bits_live_p (bv_from_ubc))
1751 44216 : return true;
1752 : }
1753 77657 : return false;
1754 : }
1755 :
1756 : /* Remove all bindings overlapping REG within this store. */
1757 :
1758 : void
1759 7338 : store::clobber_region (const region *reg,
1760 : baseline_state bs,
1761 : region_model_manager &rmm)
1762 : {
1763 7338 : const region *base_reg = reg->get_base_region ();
1764 7338 : binding_cluster **slot = m_cluster_map.get (base_reg);
1765 7338 : if (!slot)
1766 2826 : return;
1767 4512 : binding_cluster *cluster = *slot;
1768 :
1769 4512 : if (reg == base_reg)
1770 : {
1771 3916 : delete cluster;
1772 3916 : m_cluster_map.remove (base_reg);
1773 : }
1774 : else
1775 : {
1776 596 : auto mem_range = reg->get_memory_range (rmm);
1777 596 : auto &bv_mgr = rmm.get_node_manager ().get_bit_vector_manager ();
1778 596 : auto &uninit_bv
1779 596 : = bv_mgr.get_uninitialized_bits (mem_range.get_size ());
1780 596 : cluster->set_bits (mem_range.get_bit_range (),
1781 : uninit_bv,
1782 : nullptr);
1783 596 : if (cluster->redundant_p (*this, bs))
1784 : {
1785 134 : delete cluster;
1786 134 : m_cluster_map.remove (base_reg);
1787 : }
1788 : }
1789 : }
1790 :
1791 : /* Remove any bindings for REG within this store. */
1792 :
1793 : void
1794 173109 : store::purge_region (const region *reg)
1795 : {
1796 173109 : const region *base_reg = reg->get_base_region ();
1797 173109 : gcc_assert (reg == base_reg);
1798 173109 : binding_cluster **slot = m_cluster_map.get (base_reg);
1799 173109 : if (!slot)
1800 0 : return;
1801 173109 : binding_cluster *cluster = *slot;
1802 173109 : delete cluster;
1803 173109 : m_cluster_map.remove (base_reg);
1804 : }
1805 :
1806 : /* Mark REG as having unknown content. */
1807 :
1808 : void
1809 558 : store::mark_region_as_unknown (const region *reg,
1810 : baseline_state bs,
1811 : uncertainty_t *uncertainty,
1812 : const region_model &model)
1813 : {
1814 558 : const region *base_reg = reg->get_base_region ();
1815 558 : if (base_reg->symbolic_for_unknown_ptr_p ()
1816 558 : || !base_reg->tracked_p ())
1817 0 : return;
1818 :
1819 558 : auto &rmm = m_node_mgr.get_region_model_manager ();
1820 558 : auto mem_range = reg->get_memory_range (rmm);
1821 558 : if (mem_range.get_size ().is_zero_p ())
1822 : return;
1823 :
1824 558 : auto &bv_mgr = m_node_mgr.get_bit_vector_manager ();
1825 558 : auto &unknown_bv = bv_mgr.get_unknown_bits (mem_range.get_size ());
1826 558 : set_bits (mem_range, unknown_bv,
1827 : uncertainty,
1828 : model);
1829 : }
1830 :
1831 : /* Purge state involving NODE. */
1832 :
1833 : void
1834 24941 : store::purge_state_involving (const symbolic::node &node)
1835 : {
1836 24941 : auto_vec <const region *> base_regs_to_purge;
1837 357489 : for (auto iter : m_cluster_map)
1838 : {
1839 332548 : const region *base_reg = iter.first;
1840 332548 : if (base_reg->involves_p (node))
1841 27 : base_regs_to_purge.safe_push (base_reg);
1842 : else
1843 : {
1844 332521 : binding_cluster *cluster = iter.second;
1845 332521 : cluster->purge_state_involving (node);
1846 : }
1847 : }
1848 :
1849 25022 : for (auto iter : base_regs_to_purge)
1850 27 : purge_cluster (iter);
1851 24941 : }
1852 :
1853 : /* Get the cluster for BASE_REG, or nullptr (const version). */
1854 :
1855 : const binding_cluster *
1856 1115966 : store::get_cluster (const region *base_reg) const
1857 : {
1858 1115966 : gcc_assert (base_reg);
1859 1115966 : gcc_assert (base_reg->get_base_region () == base_reg);
1860 2231932 : if (binding_cluster **slot
1861 1115966 : = const_cast <cluster_map_t &> (m_cluster_map).get (base_reg))
1862 1052176 : return *slot;
1863 : else
1864 : return nullptr;
1865 : }
1866 :
1867 : /* Get the cluster for BASE_REG, or nullptr (non-const version). */
1868 :
1869 : binding_cluster *
1870 6157071 : store::get_cluster (const region *base_reg)
1871 : {
1872 6157071 : gcc_assert (base_reg);
1873 6157071 : gcc_assert (base_reg->get_base_region () == base_reg);
1874 6157071 : if (binding_cluster **slot = m_cluster_map.get (base_reg))
1875 5047470 : return *slot;
1876 : else
1877 : return nullptr;
1878 : }
1879 :
1880 : /* Get the cluster for BASE_REG, creating it if doesn't already exist. */
1881 :
1882 : binding_cluster *
1883 770417 : store::get_or_create_cluster (const region *base_reg,
1884 : baseline_state bs)
1885 : {
1886 770417 : gcc_assert (base_reg);
1887 770417 : gcc_assert (base_reg->get_base_region () == base_reg);
1888 :
1889 : /* We shouldn't create clusters for dereferencing an UNKNOWN ptr. */
1890 770417 : gcc_assert (!base_reg->symbolic_for_unknown_ptr_p ());
1891 :
1892 : /* We shouldn't create clusters for base regions that aren't trackable. */
1893 770417 : gcc_assert (base_reg->tracked_p ());
1894 :
1895 770417 : if (binding_cluster **slot = m_cluster_map.get (base_reg))
1896 52021 : return *slot;
1897 :
1898 718396 : auto &baseline = get_implicit_contents (*base_reg, bs);
1899 718396 : binding_cluster *cluster
1900 718396 : = new binding_cluster (m_node_mgr, base_reg, baseline);
1901 718396 : m_cluster_map.put (base_reg, cluster);
1902 :
1903 718396 : return cluster;
1904 : }
1905 :
1906 : /* Remove any cluster for BASE_REG, for use by
1907 : region_model::unbind_region_and_descendents
1908 : when popping stack frames and handling deleted heap regions. */
1909 :
1910 : void
1911 31751 : store::purge_cluster (const region *base_reg)
1912 : {
1913 31751 : gcc_assert (base_reg->get_base_region () == base_reg);
1914 31751 : binding_cluster **slot = m_cluster_map.get (base_reg);
1915 31751 : if (!slot)
1916 : return;
1917 31751 : binding_cluster *cluster = *slot;
1918 31751 : delete cluster;
1919 31751 : m_cluster_map.remove (base_reg);
1920 : }
1921 :
1922 : /* Attempt to merge STORE_A and STORE_B into OUT_STORE.
1923 : Return true if successful, or false if the stores can't be merged. */
1924 :
1925 : bool
1926 63282 : store::can_merge_p (const store *store_a, const store *store_b,
1927 : store *out_store,
1928 : model_merger *merger)
1929 : {
1930 63282 : if (store_a->m_called_unknown_fn || store_b->m_called_unknown_fn)
1931 30098 : out_store->m_called_unknown_fn = true;
1932 :
1933 : /* Get the union of all base regions for STORE_A and STORE_B. */
1934 63282 : hash_set<const region *> base_regions;
1935 545291 : for (cluster_map_t::iterator iter_a = store_a->m_cluster_map.begin ();
1936 545291 : iter_a != store_a->m_cluster_map.end (); ++iter_a)
1937 : {
1938 482009 : const region *base_reg_a = (*iter_a).first;
1939 482009 : base_regions.add (base_reg_a);
1940 : }
1941 526387 : for (cluster_map_t::iterator iter_b = store_b->m_cluster_map.begin ();
1942 526387 : iter_b != store_b->m_cluster_map.end (); ++iter_b)
1943 : {
1944 463105 : const region *base_reg_b = (*iter_b).first;
1945 463105 : base_regions.add (base_reg_b);
1946 : }
1947 :
1948 : /* Sort the base regions before considering them. This ought not to
1949 : affect the results, but can affect which types UNKNOWN_REGIONs are
1950 : created for in a run; sorting them thus avoids minor differences
1951 : in logfiles. */
1952 63282 : auto_vec<const region *> vec_base_regions (base_regions.elements ());
1953 63282 : for (hash_set<const region *>::iterator iter = base_regions.begin ();
1954 551304 : iter != base_regions.end (); ++iter)
1955 488022 : vec_base_regions.quick_push (*iter);
1956 63282 : vec_base_regions.qsort (region::cmp_ptr_ptr);
1957 63282 : unsigned i;
1958 63282 : const region *base_reg;
1959 555083 : FOR_EACH_VEC_ELT (vec_base_regions, i, base_reg)
1960 : {
1961 447453 : const binding_cluster *cluster_a = store_a->get_cluster (base_reg);
1962 447453 : const binding_cluster *cluster_b = store_b->get_cluster (base_reg);
1963 : /* At least one of cluster_a and cluster_b must be non-NULL. */
1964 447453 : binding_cluster *out_cluster
1965 : = out_store->get_or_create_cluster
1966 447453 : (base_reg,
1967 447453 : merger->m_model_a->get_baseline_state ());
1968 447453 : if (!binding_cluster::can_merge_p (cluster_a, cluster_b,
1969 : out_cluster, out_store, merger))
1970 : return false;
1971 : }
1972 : return true;
1973 63282 : }
1974 :
1975 : /* Mark the cluster for BASE_REG as having escaped.
1976 : For use when handling an unrecognized function call, and
1977 : for params to "top-level" calls.
1978 : Further unknown function calls could touch it, even if the cluster
1979 : isn't reachable from args of those calls. */
1980 :
1981 : void
1982 37992 : store::mark_as_escaped (const region *base_reg,
1983 : baseline_state bs)
1984 : {
1985 37992 : gcc_assert (base_reg);
1986 37992 : gcc_assert (base_reg->get_base_region () == base_reg);
1987 :
1988 37992 : if (base_reg->symbolic_for_unknown_ptr_p ()
1989 37992 : || !base_reg->tracked_p ())
1990 : return;
1991 :
1992 33338 : binding_cluster *cluster = get_or_create_cluster (base_reg, bs);
1993 33338 : cluster->mark_as_escaped ();
1994 : }
1995 :
1996 : /* Handle an unknown fncall by updating any clusters that have escaped
1997 : (either in this fncall, or in a prior one). */
1998 :
1999 : void
2000 17587 : store::on_unknown_fncall (const gcall &call,
2001 : const conjured_purge &p)
2002 : {
2003 17587 : m_called_unknown_fn = true;
2004 :
2005 17587 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2006 129429 : iter != m_cluster_map.end (); ++iter)
2007 111842 : (*iter).second->on_unknown_fncall (call, p);
2008 17587 : }
2009 :
2010 : /* Mark all of BASE_REG as having conjured contents. */
2011 :
2012 : void
2013 508 : store::mark_region_as_conjured (const region &base_reg,
2014 : baseline_state bs,
2015 : const gimple &stmt,
2016 : const conjured_purge &p)
2017 : {
2018 508 : gcc_assert (base_reg.get_base_region () == &base_reg);
2019 :
2020 : // TODO: what if symbolic?
2021 :
2022 508 : if (!base_reg.tracked_p ())
2023 : return;
2024 :
2025 504 : binding_cluster *cluster = get_or_create_cluster (&base_reg, bs);
2026 504 : cluster->mark_region_as_conjured (stmt, p);
2027 : }
2028 :
2029 : /* Return true if a non-const pointer to BASE_REG (or something within it)
2030 : has escaped to code outside of the TU being analyzed. */
2031 :
2032 : bool
2033 5189414 : store::escaped_p (const region *base_reg) const
2034 : {
2035 5189414 : gcc_assert (base_reg);
2036 5189414 : gcc_assert (base_reg->get_base_region () == base_reg);
2037 :
2038 : /* "errno" can always be modified by external code. */
2039 5189414 : if (base_reg->get_kind () == RK_ERRNO)
2040 : return true;
2041 :
2042 10301338 : if (binding_cluster **cluster_slot
2043 5150669 : = const_cast <cluster_map_t &>(m_cluster_map).get (base_reg))
2044 5150669 : return (*cluster_slot)->escaped_p ();
2045 : return false;
2046 : }
2047 :
2048 : /* Populate OUT_PVS with a list of path_vars for describing SVAL based on
2049 : this store, using VISITED to ensure the traversal terminates. */
2050 :
2051 : void
2052 11590 : store::get_representative_path_vars (const region_model *model,
2053 : value_set *visited,
2054 : const svalue *sval,
2055 : logger *logger,
2056 : auto_vec<path_var> *out_pvs) const
2057 : {
2058 11590 : gcc_assert (sval);
2059 :
2060 : /* Find all bindings that reference SVAL. */
2061 41400 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
2062 41400 : iter != m_cluster_map.end (); ++iter)
2063 : {
2064 29810 : const region *base_reg = (*iter).first;
2065 29810 : binding_cluster *cluster = (*iter).second;
2066 29810 : cluster->get_representative_path_vars (model, visited, base_reg, sval,
2067 : logger,
2068 : out_pvs);
2069 : }
2070 :
2071 11590 : if (const initial_svalue *init_sval = sval->dyn_cast_initial_svalue ())
2072 : {
2073 2000 : const region *reg = init_sval->get_region ();
2074 2000 : if (path_var pv = model->get_representative_path_var (reg,
2075 : visited,
2076 2000 : logger))
2077 2000 : out_pvs->safe_push (pv);
2078 : }
2079 11590 : }
2080 :
2081 : /* Canonicalize this store, to maximize the chance of equality between
2082 : instances. */
2083 :
2084 : void
2085 781679 : store::canonicalize ()
2086 : {
2087 : // No-op
2088 781679 : }
2089 :
2090 : static bool
2091 9940 : needs_loop_replay_fixup_p (const symbolic::node &node)
2092 : {
2093 19880 : struct my_visitor : public symbolic::node_visitor
2094 : {
2095 9940 : my_visitor () : m_found_widening (false) {}
2096 :
2097 : bool
2098 14153 : visit_svalue (const svalue &sval) final override
2099 : {
2100 14153 : if (sval.dyn_cast_widening_svalue ())
2101 527 : m_found_widening = true;
2102 14153 : return true;
2103 : }
2104 :
2105 : bool m_found_widening;
2106 9940 : } v;
2107 :
2108 9940 : node.accept_node_visitor (v);
2109 9940 : return v.m_found_widening;
2110 9940 : }
2111 :
2112 : /* Subroutine for use by exploded_path::feasible_p.
2113 :
2114 : We need to deal with state differences between:
2115 : (a) when the exploded_graph is being initially constructed and
2116 : (b) when replaying the state changes along a specific path in
2117 : in exploded_path::feasible_p.
2118 :
2119 : In (a), state merging happens, so when exploring a loop
2120 : for (i = 0; i < 1024; i++)
2121 : on successive iterations we have i == 0, then i == WIDENING.
2122 :
2123 : In (b), no state merging happens, so naively replaying the path
2124 : that goes twice through the loop then exits it
2125 : would lead to i == 0, then i == 1, and then a (i >= 1024) eedge
2126 : that exits the loop, which would be found to be infeasible as i == 1,
2127 : and the path would be rejected.
2128 :
2129 : We need to fix up state during replay. This subroutine is
2130 : called whenever we enter a supernode that we've already
2131 : visited along this exploded_path, passing in OTHER_STORE
2132 : from the destination enode's state.
2133 :
2134 : Find bindings to widening values in OTHER_STORE.
2135 : For all that are found, update the binding in this store to UNKNOWN. */
2136 :
2137 : void
2138 1554 : store::loop_replay_fixup (const store *other_store,
2139 : baseline_state bs,
2140 : region_model_manager *mgr)
2141 : {
2142 1554 : gcc_assert (other_store);
2143 11494 : for (cluster_map_t::iterator iter = other_store->m_cluster_map.begin ();
2144 11494 : iter != other_store->m_cluster_map.end (); ++iter)
2145 : {
2146 9940 : const region *base_reg = (*iter).first;
2147 9940 : binding_cluster *cluster = (*iter).second;
2148 :
2149 9940 : if (needs_loop_replay_fixup_p (*cluster->m_contents))
2150 : {
2151 523 : binding_cluster *this_cluster = get_or_create_cluster (base_reg, bs);
2152 523 : auto &node_mgr = mgr->get_node_manager ();
2153 523 : this_cluster->mark_as_untracked (node_mgr, nullptr, nullptr);
2154 : }
2155 : }
2156 1554 : }
2157 :
2158 : /* Attempt to use R to replay the bindings from SUMMARY into this object.
2159 : Return true if successful. */
2160 :
2161 : bool
2162 677 : store::replay_call_summary (call_summary_replay &r,
2163 : const store &summary)
2164 : {
2165 677 : if (summary.m_called_unknown_fn)
2166 : {
2167 : /* A call to an external function occurred in the summary.
2168 : Hence we need to invalidate our knowledge of globals,
2169 : escaped regions, etc. */
2170 40 : on_unknown_fncall (r.get_call_stmt (),
2171 40 : conjured_purge (r.get_caller_model (),
2172 40 : r.get_ctxt ()));
2173 : }
2174 :
2175 677 : auto_vec<const region *> keys (summary.m_cluster_map.elements ());
2176 2726 : for (auto kv : summary.m_cluster_map)
2177 2049 : keys.quick_push (kv.first);
2178 677 : keys.qsort (region::cmp_ptr_ptr);
2179 3628 : for (auto base_reg : keys)
2180 1775 : if (!replay_call_summary_cluster (r, summary, base_reg))
2181 : return false;
2182 : return true;
2183 677 : }
2184 :
2185 : /* Attempt to use R and SUMMARY to replay the bindings in SUMMARY_CLUSTER
2186 : into this object.
2187 : Return true if successful. */
2188 :
2189 : bool
2190 1775 : store::replay_call_summary_cluster (call_summary_replay &r,
2191 : const store &summary,
2192 : const region *summary_base_reg)
2193 : {
2194 1775 : const call_details &cd = r.get_call_details ();
2195 1775 : region_model_manager *reg_mgr = r.get_manager ();
2196 1775 : const binding_cluster *summary_cluster
2197 1775 : = summary.get_cluster (summary_base_reg);
2198 :
2199 1775 : auto &bit_contents_mgr
2200 1775 : = reg_mgr->get_node_manager ().get_bit_contents_manager ();
2201 :
2202 : /* Handle "ESCAPED" and "TOUCHED" flags. */
2203 1775 : if (summary_cluster->escaped_p () || summary_cluster->touched_p ())
2204 872 : if (const region *caller_reg
2205 436 : = r.convert_region_from_summary (summary_base_reg))
2206 : {
2207 436 : const region *caller_base_reg = caller_reg->get_base_region ();
2208 436 : if (caller_base_reg->tracked_p ()
2209 436 : && !caller_base_reg->symbolic_for_unknown_ptr_p ())
2210 : {
2211 372 : binding_cluster *caller_cluster
2212 : = get_or_create_cluster
2213 372 : (caller_base_reg,
2214 : r.get_caller_model ()->get_baseline_state ());
2215 372 : if (summary_cluster->escaped_p ())
2216 372 : caller_cluster->mark_as_escaped ();
2217 372 : if (summary_cluster->touched_p ())
2218 36 : caller_cluster->m_touched = true;
2219 : }
2220 : }
2221 :
2222 1775 : switch (summary_base_reg->get_kind ())
2223 : {
2224 : /* Top-level regions. */
2225 0 : case RK_FRAME:
2226 0 : case RK_GLOBALS:
2227 0 : case RK_CODE:
2228 0 : case RK_STACK:
2229 0 : case RK_HEAP:
2230 0 : case RK_THREAD_LOCAL:
2231 0 : case RK_ROOT:
2232 : /* Child regions. */
2233 0 : case RK_FIELD:
2234 0 : case RK_ELEMENT:
2235 0 : case RK_OFFSET:
2236 0 : case RK_SIZED:
2237 0 : case RK_CAST:
2238 0 : case RK_BIT_RANGE:
2239 : /* Other regions. */
2240 0 : case RK_VAR_ARG:
2241 0 : case RK_UNKNOWN:
2242 : /* These should never be the base region of a binding cluster. */
2243 0 : gcc_unreachable ();
2244 : break;
2245 :
2246 : case RK_FUNCTION:
2247 : case RK_LABEL:
2248 : case RK_STRING:
2249 : /* These can be marked as escaping. */
2250 : break;
2251 :
2252 462 : case RK_SYMBOLIC:
2253 462 : {
2254 462 : const symbolic_region *summary_symbolic_reg
2255 462 : = as_a <const symbolic_region *> (summary_base_reg);
2256 462 : const svalue *summary_ptr_sval = summary_symbolic_reg->get_pointer ();
2257 462 : const svalue *caller_ptr_sval
2258 462 : = r.convert_svalue_from_summary (summary_ptr_sval);
2259 462 : if (!caller_ptr_sval)
2260 : return false;
2261 454 : const region *caller_dest_reg
2262 454 : = cd.get_model ()->deref_rvalue (caller_ptr_sval,
2263 : NULL_TREE,
2264 : cd.get_ctxt ());
2265 454 : auto &summary_bits
2266 454 : = summary.get_bit_contents (*summary_symbolic_reg,
2267 : r.get_caller_model ()->get_baseline_state ());
2268 454 : if (auto *baseline_bc = summary_bits.dyn_cast_baseline_bit_contents ())
2269 163 : if (baseline_bc->get_baseline_key ().m_base_reg == summary_base_reg)
2270 : {
2271 : /* The summary's bit contents is just the baseline for
2272 : summary_base_reg; we don't need to write anything. */
2273 : return true;
2274 : }
2275 291 : auto *caller_bits = r.convert_bit_contents_from_summary (summary_bits);
2276 291 : if (!caller_bits)
2277 1 : caller_bits = &bit_contents_mgr.get_untracked ({});
2278 291 : return replay_call_summary_bit_contents
2279 291 : (r, summary, *summary_base_reg,
2280 291 : *caller_dest_reg, *caller_bits);
2281 : }
2282 1308 : break;
2283 :
2284 1308 : case RK_HEAP_ALLOCATED:
2285 1308 : case RK_DECL:
2286 1308 : case RK_ERRNO:
2287 1308 : case RK_PRIVATE:
2288 1308 : {
2289 1308 : const region *caller_dest_reg
2290 1308 : = r.convert_region_from_summary (summary_base_reg);
2291 1308 : if (!caller_dest_reg)
2292 : return false;
2293 1248 : auto &summary_bits
2294 1248 : = summary.get_bit_contents (*summary_base_reg,
2295 : r.get_caller_model ()->get_baseline_state ());
2296 1248 : if (auto *baseline_bc = summary_bits.dyn_cast_baseline_bit_contents ())
2297 0 : if (baseline_bc->get_baseline_key ().m_base_reg == summary_base_reg)
2298 : {
2299 : /* The summary's bit contents is just the baseline for
2300 : summary_base_reg; we don't need to write anything. */
2301 : return true;
2302 : }
2303 1248 : auto *caller_bits = r.convert_bit_contents_from_summary (summary_bits);
2304 1248 : if (!caller_bits)
2305 211 : caller_bits = &bit_contents_mgr.get_untracked ({});
2306 1248 : return replay_call_summary_bit_contents
2307 1248 : (r, summary, *summary_base_reg,
2308 1248 : *caller_dest_reg, *caller_bits);
2309 : }
2310 : break;
2311 :
2312 : case RK_ALLOCA:
2313 : /* Ignore bindings of alloca regions in the summary. */
2314 : break;
2315 : }
2316 :
2317 : return true;
2318 : }
2319 :
2320 : bool
2321 2216 : store::replay_call_summary_bit_contents (call_summary_replay &r,
2322 : const store &summary,
2323 : const region &summary_base_reg,
2324 : const region &caller_dest_reg,
2325 : const symbolic::bit_contents &caller_bc)
2326 : {
2327 2216 : if (caller_dest_reg.symbolic_for_unknown_ptr_p ())
2328 : return false;
2329 :
2330 2148 : switch (caller_bc.get_kind ())
2331 : {
2332 : default:
2333 : return false; // TODO
2334 :
2335 : case symbolic::bit_contents::kind::uninit:
2336 : /* No-op: nothing was written in summary, so the replay
2337 : writes nothing. */
2338 : break;
2339 :
2340 882 : case symbolic::bit_contents::kind::untracked:
2341 882 : {
2342 882 : const region *base_reg = caller_dest_reg.get_base_region ();
2343 882 : if (base_reg->tracked_p ())
2344 : {
2345 882 : binding_cluster *caller_cluster
2346 882 : = get_or_create_cluster (caller_dest_reg.get_base_region (),
2347 : r.get_caller_model ()->get_baseline_state ());
2348 882 : caller_cluster->set_bit_contents (caller_bc);
2349 : }
2350 : }
2351 : break;
2352 :
2353 : case symbolic::bit_contents::kind::zero:
2354 : {
2355 : return false; // TODO
2356 : }
2357 7 : break;
2358 :
2359 7 : case symbolic::bit_contents::kind::baseline:
2360 7 : case symbolic::bit_contents::kind::offset:
2361 7 : {
2362 7 : auto &rmm = *r.get_manager ();
2363 7 : auto caller_dest_mem_offset = caller_dest_reg.get_memory_offset (rmm);
2364 7 : auto &bc_mgr = caller_bc.get_bit_contents_manager ();
2365 7 : auto &caller_offset_bc = bc_mgr.get_offset_bit_contents
2366 14 : (caller_bc,
2367 7 : caller_dest_mem_offset.get_bit_offset ());
2368 : // FIXME: is the sign of the offset correct?
2369 7 : binding_cluster *caller_cluster
2370 7 : = get_or_create_cluster (&caller_dest_mem_offset.get_base_region (),
2371 : r.get_caller_model ()->get_baseline_state ()); // FIXME
2372 7 : caller_cluster->set_bit_contents (caller_offset_bc);
2373 : // FIXME: this bypasses access checks; should it?
2374 : }
2375 7 : break;
2376 : case symbolic::bit_contents::kind::conjured:
2377 : return false; // TODO
2378 :
2379 : case symbolic::bit_contents::kind::named_test:
2380 : return false; // TODO
2381 :
2382 643 : case symbolic::bit_contents::kind::concrete_overlay:
2383 643 : {
2384 643 : auto &caller_overlay
2385 : = (const symbolic::concrete_bit_overlay &)caller_bc;
2386 :
2387 : /* First, apply the baseline. */
2388 643 : auto &caller_baseline = caller_overlay.get_baseline ();
2389 643 : replay_call_summary_bit_contents (r, summary, summary_base_reg,
2390 : caller_dest_reg, caller_baseline);
2391 :
2392 : /* Now apply the bindings. */
2393 1316 : for (auto iter : caller_overlay.m_concrete_range_map)
2394 : {
2395 673 : auto &conc_range = iter.first;
2396 673 : auto &bv = iter.second;
2397 673 : auto &rmm = *r.get_manager ();
2398 673 : auto *affected_region
2399 673 : = rmm.get_bit_range (&caller_dest_reg, NULL_TREE, conc_range);
2400 673 : set_bits (affected_region, bv, nullptr, *r.get_caller_model ());
2401 673 : }
2402 : }
2403 643 : break;
2404 34 : case symbolic::bit_contents::kind::symbolic_overlay:
2405 34 : {
2406 34 : auto &caller_overlay
2407 : = (const symbolic::symbolic_bit_overlay &)caller_bc;
2408 :
2409 : /* First, apply the baseline. */
2410 34 : auto &caller_baseline = caller_overlay.get_baseline ();
2411 34 : replay_call_summary_bit_contents (r, summary, summary_base_reg,
2412 : caller_dest_reg, caller_baseline);
2413 :
2414 : /* Now apply the bindings. */
2415 34 : for (auto iter : caller_overlay.m_symbolic_range_map)
2416 : {
2417 2216 : return false; // TODO
2418 : }
2419 : }
2420 : break;
2421 : }
2422 :
2423 : return true;
2424 : }
2425 :
2426 : #if CHECKING_P
2427 :
2428 : namespace selftest {
2429 :
2430 : /* Verify that bit_range::intersects_p works as expected. */
2431 :
2432 : static void
2433 4 : test_bit_range_intersects_p ()
2434 : {
2435 4 : bit_range b0 (0, 1);
2436 4 : bit_range b1 (1, 1);
2437 4 : bit_range b2 (2, 1);
2438 4 : bit_range b3 (3, 1);
2439 4 : bit_range b4 (4, 1);
2440 4 : bit_range b5 (5, 1);
2441 4 : bit_range b6 (6, 1);
2442 4 : bit_range b7 (7, 1);
2443 4 : bit_range b1_to_6 (1, 6);
2444 4 : bit_range b0_to_7 (0, 8);
2445 4 : bit_range b3_to_5 (3, 3);
2446 4 : bit_range b6_to_7 (6, 2);
2447 :
2448 : /* self-intersection is true. */
2449 4 : ASSERT_TRUE (b0.intersects_p (b0));
2450 4 : ASSERT_TRUE (b7.intersects_p (b7));
2451 4 : ASSERT_TRUE (b1_to_6.intersects_p (b1_to_6));
2452 4 : ASSERT_TRUE (b0_to_7.intersects_p (b0_to_7));
2453 :
2454 4 : ASSERT_FALSE (b0.intersects_p (b1));
2455 4 : ASSERT_FALSE (b1.intersects_p (b0));
2456 4 : ASSERT_FALSE (b0.intersects_p (b7));
2457 4 : ASSERT_FALSE (b7.intersects_p (b0));
2458 :
2459 4 : ASSERT_TRUE (b0_to_7.intersects_p (b0));
2460 4 : ASSERT_TRUE (b0_to_7.intersects_p (b7));
2461 4 : ASSERT_TRUE (b0.intersects_p (b0_to_7));
2462 4 : ASSERT_TRUE (b7.intersects_p (b0_to_7));
2463 :
2464 4 : ASSERT_FALSE (b0.intersects_p (b1_to_6));
2465 4 : ASSERT_FALSE (b1_to_6.intersects_p (b0));
2466 4 : ASSERT_TRUE (b1.intersects_p (b1_to_6));
2467 4 : ASSERT_TRUE (b1_to_6.intersects_p (b1));
2468 4 : ASSERT_TRUE (b1_to_6.intersects_p (b6));
2469 4 : ASSERT_FALSE (b1_to_6.intersects_p (b7));
2470 :
2471 4 : ASSERT_TRUE (b1_to_6.intersects_p (b0_to_7));
2472 4 : ASSERT_TRUE (b0_to_7.intersects_p (b1_to_6));
2473 :
2474 4 : ASSERT_FALSE (b3_to_5.intersects_p (b6_to_7));
2475 4 : ASSERT_FALSE (b6_to_7.intersects_p (b3_to_5));
2476 :
2477 4 : bit_range r1 (0,0);
2478 4 : bit_range r2 (0,0);
2479 4 : ASSERT_TRUE (b1_to_6.intersects_p (b0_to_7, &r1, &r2));
2480 4 : ASSERT_EQ (r1.get_start_bit_offset (), 0);
2481 4 : ASSERT_EQ (r1.m_size_in_bits, 6);
2482 4 : ASSERT_EQ (r2.get_start_bit_offset (), 1);
2483 4 : ASSERT_EQ (r2.m_size_in_bits, 6);
2484 :
2485 4 : ASSERT_TRUE (b0_to_7.intersects_p (b1_to_6, &r1, &r2));
2486 4 : ASSERT_EQ (r1.get_start_bit_offset (), 1);
2487 4 : ASSERT_EQ (r1.m_size_in_bits, 6);
2488 4 : ASSERT_EQ (r2.get_start_bit_offset (), 0);
2489 4 : ASSERT_EQ (r2.m_size_in_bits, 6);
2490 4 : }
2491 :
2492 : /* Run all of the selftests within this file. */
2493 :
2494 : void
2495 4 : analyzer_store_cc_tests ()
2496 : {
2497 4 : test_bit_range_intersects_p ();
2498 4 : }
2499 :
2500 : } // namespace selftest
2501 :
2502 : #endif /* CHECKING_P */
2503 :
2504 : } // namespace ana
2505 :
2506 : #endif /* #if ENABLE_ANALYZER */
|