Line data Source code
1 : /* Symbolic maps of bits e.g. "bytes [0-4): <bitvec>, bytes[16-20): <bitvec>"
2 : Copyright (C) 2019-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 "gimple-pretty-print.h"
24 : #include "tm.h"
25 :
26 : #include "diagnostics/markup.h"
27 :
28 : #include "selftest.h"
29 :
30 : #include "analyzer/symbolic-bit-contents.h"
31 : #include "analyzer/region-model.h"
32 : #include "analyzer/type.h"
33 : #include "analyzer/record-layout.h"
34 :
35 : #if ENABLE_ANALYZER
36 :
37 : namespace ana {
38 : namespace symbolic {
39 :
40 : bool
41 18090531 : baseline_key::operator< (const baseline_key &other) const
42 : {
43 18090531 : if (int c = node::cmp (*m_base_reg, *other.m_base_reg))
44 14196791 : return c < 0;
45 3893740 : return m_baseline_state < other.m_baseline_state;
46 : }
47 :
48 : // class bit_contents : public symbolic::node
49 :
50 : const bit_vector &
51 764 : bit_contents::get_bytes (const symbolic_byte_range &byte_range) const
52 : {
53 764 : return get_bits (bits_from_bytes (byte_range));
54 : }
55 :
56 : const bit_vector &
57 1739681 : bit_contents::get_bits (const concrete_bit_range &bit_range) const
58 : {
59 1739681 : return get_bits (symbolic_bit_range (bit_range,
60 1739681 : m_node_mgr.get_scalars ().get_bits ()));
61 : }
62 :
63 : const bit_vector &
64 764 : bit_contents::get_bytes (const concrete_byte_range &byte_range) const
65 : {
66 764 : return get_bytes
67 764 : (symbolic_byte_range (byte_range,
68 764 : m_node_mgr.get_scalars ().get_bytes ()));
69 : }
70 :
71 : const bit_contents &
72 305005 : bit_contents::set_bits (const symbolic_bit_range &bit_range,
73 : const bit_vector &bv,
74 : uncertainty_t *uncertainty) const
75 : {
76 305005 : auto &mgr = get_bit_contents_manager ();
77 305005 : return mgr.set_bits (*this, bit_range, bv, uncertainty);
78 : }
79 :
80 : const bit_contents &
81 683 : bit_contents::set_bits (const concrete_bit_range &conc_bit_range,
82 : const bit_vector &bv,
83 : uncertainty_t *uncertainty) const
84 : {
85 683 : return set_bits
86 683 : (symbolic_bit_range (conc_bit_range,
87 683 : m_node_mgr.get_scalars ().get_bits ()),
88 : bv,
89 683 : uncertainty);
90 : }
91 :
92 : const bit_contents &
93 284 : bit_contents::set_bytes (const symbolic_byte_range &byte_range,
94 : const bit_vector &bv,
95 : uncertainty_t *uncertainty) const
96 : {
97 284 : return set_bits (bits_from_bytes (byte_range), bv, uncertainty);
98 : }
99 :
100 : const bit_contents &
101 240 : bit_contents::set_bytes (const concrete_byte_range &byte_range,
102 : const bit_vector &bv,
103 : uncertainty_t *uncertainty) const
104 : {
105 240 : return set_bytes
106 240 : (symbolic_byte_range (byte_range,
107 240 : m_node_mgr.get_scalars ().get_bytes ()),
108 : bv,
109 240 : uncertainty);
110 : }
111 :
112 : const bit_contents &
113 76 : bit_contents::set_byte (integer_with_unit<units::byte> byte_offset,
114 : uint8_t value,
115 : uncertainty_t *uncertainty) const
116 : {
117 76 : auto &bv_mgr = get_bit_vector_manager ();
118 228 : return set_bytes (concrete_byte_range (byte_offset, 1_byte),
119 : bv_mgr.get_uint8 (value),
120 76 : uncertainty);
121 : }
122 :
123 : const bit_contents *
124 422141 : bit_contents::can_merge_p (const bit_contents &bit_contents_a,
125 : const bit_contents &bit_contents_b,
126 : tree type,
127 : model_merger *merger)
128 : {
129 422141 : if (&bit_contents_a == &bit_contents_b)
130 : return &bit_contents_a;
131 :
132 107266 : auto &bit_contents_mgr = bit_contents_a.get_bit_contents_manager ();
133 :
134 : /* Attempt mergers of concrete_bit_overlay, and with their baselines. */
135 107266 : auto *conc_bit_overlay_a = bit_contents_a.dyn_cast_concrete_bit_overlay ();
136 107266 : auto *conc_bit_overlay_b = bit_contents_b.dyn_cast_concrete_bit_overlay ();
137 107266 : if (conc_bit_overlay_a)
138 : {
139 68262 : if (conc_bit_overlay_b)
140 : {
141 62357 : if (&conc_bit_overlay_a->get_baseline ()
142 62357 : == &conc_bit_overlay_b->get_baseline ())
143 59444 : return concrete_bit_overlay::can_merge_p
144 59444 : (bit_contents_a,
145 : bit_contents_b,
146 : conc_bit_overlay_a->get_baseline (),
147 : conc_bit_overlay_a,
148 : conc_bit_overlay_b,
149 : type,
150 59444 : merger);
151 : }
152 : else
153 : {
154 5905 : if (&conc_bit_overlay_a->get_baseline () == &bit_contents_b)
155 2416 : return concrete_bit_overlay::can_merge_p
156 2416 : (bit_contents_a,
157 : bit_contents_b,
158 : bit_contents_b,
159 : conc_bit_overlay_a,
160 : nullptr,
161 : type,
162 2416 : merger);
163 : }
164 : }
165 : else
166 : {
167 39004 : if (conc_bit_overlay_b)
168 : {
169 8941 : if (&conc_bit_overlay_b->get_baseline () == &bit_contents_a)
170 1597 : return concrete_bit_overlay::can_merge_p
171 1597 : (bit_contents_a,
172 : bit_contents_b,
173 : bit_contents_a,
174 : nullptr,
175 : conc_bit_overlay_b,
176 : type,
177 1597 : merger);
178 : }
179 : else
180 : {
181 : /* Neither are concrete bit overlays. */
182 : }
183 : }
184 :
185 : /* Allow mergers of e.g. conjured_bit_vector. */
186 43809 : value_set maybe_live_in_a = bit_contents_a.get_maybe_live_values ();
187 43809 : value_set maybe_live_in_b = bit_contents_b.get_maybe_live_values ();
188 43809 : value_set maybe_live_in_either = maybe_live_in_a.union_ (maybe_live_in_b);
189 43809 : return &bit_contents_mgr.get_untracked (std::move (maybe_live_in_either));
190 43809 : }
191 :
192 : value_set
193 88461 : bit_contents::get_maybe_live_values () const
194 : {
195 88461 : value_set maybe_live;
196 88461 : this->for_each_value ([] (const symbolic::value_node &val,
197 : void *user_data) -> iter_result {
198 : value_set *maybe_live = static_cast<value_set *> (user_data);
199 : maybe_live->add (&val);
200 : return iter_result::keep_going;
201 : }, &maybe_live);
202 88461 : return maybe_live;
203 : }
204 :
205 : // class uniform_bit_contents : public bit_contents
206 :
207 : const bit_contents *
208 12 : uniform_bit_contents::maybe_fold_offset (const symbolic_bit_offset &) const
209 : {
210 : /* Ignore the offset and fold to this bit_contents. */
211 12 : return this;
212 : }
213 :
214 : iter_result
215 3361759 : uniform_bit_contents::
216 : for_each_value (iter_result (*) (const symbolic::value_node &val,
217 : void *user_data),
218 : void *) const
219 : {
220 : // No-op
221 3361759 : return iter_result::keep_going;
222 : }
223 :
224 : // class uninit_contents : public uniform_bit_contents
225 :
226 4409 : uninit_contents::uninit_contents (node_manager &node_mgr)
227 4409 : : uniform_bit_contents (complexity (1, 1), node_mgr)
228 : {
229 4409 : }
230 :
231 : const bit_vector &
232 1610074 : uninit_contents::get_bits (const symbolic_bit_range &bit_range) const
233 : {
234 1610074 : return get_bit_vector_manager ().get_uninitialized_bits
235 1610074 : (bit_range.get_size ());
236 : }
237 :
238 : void
239 1375 : uninit_contents::print_dump_widget_label (pretty_printer *pp) const
240 : {
241 1375 : pp_string (pp, "uninitialized contents");
242 1375 : }
243 :
244 : void
245 514 : uninit_contents::add_dump_widget_children (text_art::tree_widget &,
246 : node_dump_state &) const
247 : {
248 : // no-op
249 514 : }
250 :
251 : void
252 17852 : uninit_contents::accept_node_visitor (node_visitor &v) const
253 : {
254 17852 : v.visit_bit_contents (*this);
255 17852 : }
256 :
257 : std::unique_ptr<json::object>
258 4 : uninit_contents::to_json () const
259 : {
260 4 : return make_json_obj ("uninit_contents");
261 : }
262 :
263 : std::unique_ptr<diagnostics::markup::node>
264 0 : uninit_contents::make_markup_node (markup_context &) const
265 : {
266 0 : return diagnostics::markup::make_text_node ("uninit_contents");
267 : }
268 :
269 : string_scan
270 389 : uninit_contents::
271 : scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset) const
272 : {
273 389 : return string_scan::found_poison (start_byte_offset, poison_kind::uninit);
274 : }
275 :
276 : void
277 6 : uninit_contents::
278 : get_representative_path_vars (const region_model *,
279 : value_set *,
280 : const region *,
281 : const svalue *,
282 : tree,
283 : logger *,
284 : auto_vec<path_var> *) const
285 : {
286 : // no-op
287 6 : }
288 :
289 : const bit_contents &
290 558 : uninit_contents::
291 : poison_any_pointers_to_descendents (const region *,
292 : enum poison_kind) const
293 : {
294 : // no-op
295 558 : return *this;
296 : }
297 :
298 : const bit_contents &
299 1394 : uninit_contents::purge_state_involving (const symbolic::node &) const
300 : {
301 : // no-op
302 1394 : return *this;
303 : }
304 :
305 : // class untracked_bit_contents : public uniform_bit_contents
306 :
307 : bool
308 482904 : untracked_bit_contents::key::operator< (const key &other) const
309 : {
310 482904 : return m_maybe_live < other.m_maybe_live;
311 : }
312 :
313 : complexity
314 3420 : untracked_bit_contents::key::get_complexity () const
315 : {
316 3420 : complexity child_complexities (0, 0);
317 :
318 9920 : for (auto iter : m_maybe_live)
319 6500 : child_complexities += iter->get_complexity ();
320 :
321 : /* One extra node for the node itself; one more level of depth. */
322 3420 : return complexity (child_complexities.m_num_nodes + 1,
323 3420 : child_complexities.m_max_depth + 1);
324 : }
325 :
326 3420 : untracked_bit_contents::untracked_bit_contents (node_manager &node_mgr,
327 : const key &k)
328 : : uniform_bit_contents (k.get_complexity (), node_mgr),
329 3420 : m_maybe_live (k.m_maybe_live)
330 : {
331 3420 : if (CHECKING_P)
332 9920 : for (auto iter : m_maybe_live)
333 6500 : gcc_assert (track_value_liveness_p (*iter));
334 3420 : }
335 :
336 : const bit_vector &
337 94299 : untracked_bit_contents::get_bits (const symbolic_bit_range &bit_range) const
338 : {
339 94299 : return get_bit_vector_manager ().get_unknown_bits (bit_range.get_size ());
340 : }
341 :
342 : void
343 160 : untracked_bit_contents::print_dump_widget_label (pretty_printer *pp) const
344 : {
345 160 : pp_string (pp, "untracked_bit_contents");
346 160 : }
347 :
348 : void
349 160 : untracked_bit_contents::add_dump_widget_children (text_art::tree_widget &w,
350 : node_dump_state &nds) const
351 : {
352 160 : if (!m_maybe_live.empty ())
353 : {
354 5 : using tree_widget = text_art::tree_widget;
355 5 : std::unique_ptr<tree_widget> maybe_live_w
356 5 : (tree_widget::from_fmt (nds, nullptr, "maybe live values"));
357 15 : for (auto iter : m_maybe_live)
358 20 : maybe_live_w->add_child (iter->make_dump_widget (nds));
359 10 : w.add_child (std::move (maybe_live_w));
360 5 : }
361 160 : }
362 :
363 : void
364 20344 : untracked_bit_contents::accept_node_visitor (node_visitor &v) const
365 : {
366 20344 : if (v.visit_bit_contents (*this))
367 48907 : for (auto iter : m_maybe_live)
368 28563 : iter->accept_node_visitor (v);
369 20344 : }
370 :
371 : std::unique_ptr<json::object>
372 0 : untracked_bit_contents::to_json () const
373 : {
374 0 : return make_json_obj ("untracked_bit_contents");
375 : }
376 :
377 : std::unique_ptr<diagnostics::markup::node>
378 0 : untracked_bit_contents::make_markup_node (markup_context &) const
379 : {
380 0 : return diagnostics::markup::make_text_node ("untracked_bit_contents");
381 : }
382 :
383 : string_scan
384 285 : untracked_bit_contents::
385 : scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset) const
386 : {
387 285 : return string_scan::cannot_scan (start_byte_offset);
388 : }
389 :
390 : void
391 885 : untracked_bit_contents::
392 : get_representative_path_vars (const region_model *,
393 : value_set *,
394 : const region *,
395 : const svalue *,
396 : tree,
397 : logger *,
398 : auto_vec<path_var> *) const
399 : {
400 : // no-op
401 885 : }
402 :
403 : const bit_contents &
404 12337 : untracked_bit_contents::
405 : poison_any_pointers_to_descendents (const region *,
406 : enum poison_kind) const
407 : {
408 : // no-op
409 12337 : return *this;
410 : }
411 :
412 : const bit_contents &
413 18940 : untracked_bit_contents::purge_state_involving (const symbolic::node &n) const
414 : {
415 18940 : value_set survivors;
416 49789 : for (auto iter : m_maybe_live)
417 30849 : if (!iter->involves_p (n))
418 30714 : survivors.add (iter);
419 :
420 18940 : return get_bit_contents_manager ().get_untracked (std::move (survivors));
421 18940 : }
422 :
423 : bool
424 568335 : untracked_bit_contents::bits_live_p (const bit_vector_from_ubc &bv) const
425 : {
426 568335 : return false;
427 : }
428 :
429 : iter_result
430 915509 : untracked_bit_contents::
431 : for_each_value (iter_result (*cb) (const symbolic::value_node &val,
432 : void *user_data),
433 : void *user_data) const
434 : {
435 2048780 : for (auto iter : m_maybe_live)
436 1133271 : if (cb (*iter, user_data) == iter_result::stop)
437 915509 : return iter_result::stop;
438 :
439 : return iter_result::keep_going;
440 : }
441 :
442 : bool
443 188415 : untracked_bit_contents::track_value_liveness_p (const symbolic::value_node &val)
444 : {
445 188415 : if (auto *sval = val.dyn_cast_svalue ())
446 107319 : return track_svalue_liveness_p (*sval);
447 81096 : else if (auto *bv = val.dyn_cast_bit_vector ())
448 81096 : return track_bit_vector_liveness_p (*bv);
449 0 : gcc_unreachable ();
450 : }
451 :
452 : bool
453 145375 : untracked_bit_contents::track_svalue_liveness_p (const svalue &sval)
454 : {
455 145375 : switch (sval.get_kind ())
456 : {
457 0 : default:
458 0 : gcc_unreachable ();
459 :
460 : case SK_CONSTANT:
461 : case SK_UNKNOWN:
462 : case SK_POISONED:
463 : return false;
464 :
465 111750 : case SK_POINTER:
466 111750 : case SK_SETJMP:
467 111750 : case SK_INITIAL:
468 111750 : case SK_UNARYOP:
469 111750 : case SK_BINOP:
470 111750 : case SK_UNMERGEABLE:
471 111750 : case SK_PLACEHOLDER:
472 111750 : case SK_WIDENING:
473 111750 : case SK_ASM_OUTPUT:
474 111750 : case SK_CONST_FN_RESULT:
475 111750 : return true;
476 :
477 20317 : case SK_BIT_VECTOR:
478 20317 : {
479 20317 : auto &from_bv = static_cast<const svalue_from_bit_vector &> (sval);
480 20317 : return track_bit_vector_liveness_p (from_bv.get_bit_vector ());
481 : }
482 : break;
483 : }
484 :
485 : gcc_unreachable ();
486 : }
487 :
488 : bool
489 101413 : untracked_bit_contents::
490 : track_bit_vector_liveness_p (const symbolic::bit_vector &bv)
491 : {
492 102345 : switch (bv.get_kind ())
493 : {
494 0 : default:
495 0 : gcc_unreachable ();
496 :
497 : case bit_vector::kind::empty:
498 : case bit_vector::kind::poisoned:
499 : case bit_vector::kind::tristate:
500 : return false;
501 :
502 : case bit_vector::kind::conjured:
503 : case bit_vector::kind::from_ubc:
504 : case bit_vector::kind::named_test:
505 : return true;
506 :
507 0 : case bit_vector::kind::concat:
508 0 : {
509 0 : auto &concat_bv = static_cast<const concat_bit_vector &> (bv);
510 0 : for (auto iter : concat_bv)
511 0 : if (track_bit_vector_liveness_p (*iter))
512 52206 : return true;
513 : return false;
514 : }
515 268 : break;
516 :
517 268 : case bit_vector::kind::cropped:
518 268 : {
519 268 : auto &cropped_bv = static_cast<const cropped_bit_vector &> (bv);
520 268 : return track_bit_vector_liveness_p
521 268 : (cropped_bv.get_uncropped_bit_vector ());
522 : }
523 664 : break;
524 :
525 664 : case bit_vector::kind::repeated:
526 664 : {
527 664 : auto &repeated_bv = static_cast<const repeated_bit_vector &> (bv);
528 664 : return track_bit_vector_liveness_p
529 664 : (repeated_bv.get_inner_bit_vector ());
530 : }
531 38056 : break;
532 :
533 38056 : case bit_vector::kind::svalue:
534 38056 : {
535 38056 : auto &from_sval = static_cast<const bit_vector_from_svalue &> (bv);
536 38056 : return track_svalue_liveness_p (from_sval.get_svalue ());
537 : }
538 : break;
539 : }
540 :
541 : gcc_unreachable ();
542 : }
543 :
544 : // class zero_contents : public uniform_bit_contents
545 :
546 4409 : zero_contents::zero_contents (node_manager &node_mgr)
547 4409 : : uniform_bit_contents (complexity (1, 1), node_mgr)
548 : {
549 4409 : }
550 :
551 : const bit_vector &
552 3102 : zero_contents::get_bits (const symbolic_bit_range &bit_range) const
553 : {
554 3102 : return get_bit_vector_manager ().get_all_zeros (bit_range.get_size ());
555 : }
556 :
557 : void
558 0 : zero_contents::print_dump_widget_label (pretty_printer *pp) const
559 : {
560 0 : pp_string (pp, "zero contents");
561 0 : }
562 :
563 : void
564 0 : zero_contents::add_dump_widget_children (text_art::tree_widget &,
565 : node_dump_state &) const
566 : {
567 : // no-op
568 0 : }
569 :
570 : void
571 9 : zero_contents::accept_node_visitor (node_visitor &v) const
572 : {
573 9 : v.visit_bit_contents (*this);
574 9 : }
575 :
576 : std::unique_ptr<json::object>
577 4 : zero_contents::to_json () const
578 : {
579 4 : return make_json_obj ("zero_contents");
580 : }
581 :
582 : std::unique_ptr<diagnostics::markup::node>
583 0 : zero_contents::make_markup_node (markup_context &) const
584 : {
585 0 : return diagnostics::markup::make_text_node ("zero_contents");
586 : }
587 :
588 : string_scan
589 88 : zero_contents::
590 : scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset) const
591 : {
592 88 : return string_scan::found_nul (start_byte_offset);
593 : }
594 :
595 : void
596 0 : zero_contents::
597 : get_representative_path_vars (const region_model *,
598 : value_set *,
599 : const region *,
600 : const svalue *,
601 : tree,
602 : logger *,
603 : auto_vec<path_var> *) const
604 : {
605 : // no-op
606 0 : }
607 :
608 : const bit_contents &
609 14 : zero_contents::
610 : poison_any_pointers_to_descendents (const region *,
611 : enum poison_kind) const
612 : {
613 : // no-op
614 14 : return *this;
615 : }
616 :
617 : const bit_contents &
618 1 : zero_contents::purge_state_involving (const symbolic::node &) const
619 : {
620 : // no-op
621 1 : return *this;
622 : }
623 :
624 : // class unfoldable_bit_contents : public bit_contents
625 :
626 : const symbolic::bit_vector &
627 327115 : unfoldable_bit_contents::get_bits (const symbolic_bit_range &bit_range) const
628 : {
629 327115 : auto &bv_mgr = get_bit_vector_manager ();
630 327115 : if (bit_range.get_size ().is_zero_p ())
631 30 : return bv_mgr.get_empty ();
632 :
633 327085 : auto iter = m_range_to_bv_map.find (bit_range);
634 327085 : if (iter != m_range_to_bv_map.end ())
635 312542 : return *(iter->second);
636 :
637 14543 : auto bv_up
638 14543 : = std::make_unique<symbolic::bit_vector_from_ubc> (*this, bit_range);
639 14543 : auto &result = *bv_up;
640 14543 : m_range_to_bv_map.insert ({bit_range, std::move (bv_up)});
641 14543 : return result;
642 14543 : }
643 :
644 : string_scan
645 2615 : unfoldable_bit_contents::
646 : scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset) const
647 : {
648 2615 : return string_scan::cannot_scan (start_byte_offset);
649 : }
650 :
651 : bool
652 89227 : unfoldable_bit_contents::
653 : bits_live_p (const symbolic::bit_vector_from_ubc &bv_from_ubc) const
654 : {
655 89227 : return &bv_from_ubc.get_bit_contents () == this;
656 : }
657 :
658 : /* Identify when SVAL is a cropping from this unfoldable_bit_contents,
659 : reporting it to OUT_PVS as the appropriate subregion of BASE_REG. */
660 :
661 : void
662 4537 : unfoldable_bit_contents::
663 : get_representative_path_vars (const region_model *model,
664 : value_set *visited,
665 : const region *base_reg,
666 : const svalue *sval,
667 : tree desired_type,
668 : logger *logger,
669 : auto_vec<path_var> *out_pvs) const
670 : {
671 4537 : auto *from_bv = sval->dyn_cast_svalue_from_bit_vector ();
672 4537 : if (!from_bv)
673 4392 : return;
674 :
675 1968 : auto &bv = from_bv->get_bit_vector ();
676 1968 : auto *from_bc = bv.dyn_cast_bit_vector_from_ubc ();
677 1968 : if (!from_bc)
678 : return;
679 :
680 338 : if (&from_bc->get_bit_contents () != this)
681 : return;
682 :
683 196 : symbolic::memory_range mem_range (*base_reg, from_bc->get_bit_range ());
684 196 : auto *subreg = model->maybe_get_region_for_mem_range (mem_range,
685 : desired_type,
686 : logger);
687 196 : if (!subreg)
688 : return;
689 :
690 196 : auto *cast_reg
691 196 : = model->get_manager ()->get_cast_region (subreg, desired_type);
692 196 : path_var pv = model->get_representative_path_var (cast_reg, visited, logger);
693 196 : if (!pv)
694 : return;
695 :
696 145 : out_pvs->safe_push (pv);
697 : }
698 :
699 : // class baseline_bit_contents : public unfoldable_bit_contents
700 :
701 7978 : baseline_bit_contents::
702 : baseline_bit_contents (node_manager &node_mgr, const baseline_key &bk)
703 7978 : : symbolic::unfoldable_bit_contents (complexity (bk.m_base_reg), node_mgr),
704 7978 : m_baseline_key (bk)
705 : {
706 7978 : gcc_assert (!m_baseline_key.region_has_meaningful_size_p (node_mgr));
707 7978 : }
708 :
709 : void
710 99 : baseline_bit_contents::print_dump_widget_label (pretty_printer *pp) const
711 : {
712 99 : pp_printf (pp, "baseline_bit_contents");
713 99 : }
714 :
715 : void
716 99 : baseline_bit_contents::add_dump_widget_children (text_art::tree_widget &w,
717 : node_dump_state &nds) const
718 : {
719 198 : w.add_child (m_baseline_key.m_base_reg->make_dump_widget (nds, "base_reg"));
720 99 : }
721 :
722 : void
723 3563588 : baseline_bit_contents::accept_node_visitor (node_visitor &v) const
724 : {
725 3563588 : if (v.visit_bit_contents (*this))
726 3563588 : m_baseline_key.m_base_reg->accept_node_visitor (v);
727 3563588 : }
728 :
729 : std::unique_ptr<json::object>
730 14 : baseline_bit_contents::to_json () const
731 : {
732 14 : auto obj = make_json_obj ("baseline_bit_contents");
733 14 : obj->set ("baseline_key", m_baseline_key.to_json ());
734 14 : return obj;
735 : }
736 :
737 : std::unique_ptr<diagnostics::markup::node>
738 0 : baseline_bit_contents::make_markup_node (markup_context &) const
739 : {
740 0 : return diagnostics::markup::make_text_node ("baseline_bit_contents");
741 : }
742 :
743 : const bit_contents &
744 8023 : baseline_bit_contents::
745 : poison_any_pointers_to_descendents (const region *reg,
746 : enum poison_kind pkind) const
747 : {
748 8023 : if (reg == m_baseline_key.m_base_reg)
749 : {
750 : // TODO
751 : }
752 8023 : return *this;
753 : }
754 :
755 : const bit_contents &
756 7733 : baseline_bit_contents::purge_state_involving (const symbolic::node &) const
757 : {
758 7733 : return *this;
759 : }
760 :
761 : iter_result
762 503869 : baseline_bit_contents::
763 : for_each_value (iter_result (*) (const symbolic::value_node &val,
764 : void *user_data),
765 : void *user_data) const
766 : {
767 : // No-op
768 503869 : return iter_result::keep_going;
769 : }
770 : // class conjured_bit_contents : public unfoldable_bit_contents
771 :
772 : bool
773 268553 : conjured_bit_contents::key::operator< (const key &other) const
774 : {
775 268553 : if (int c = m_stmt->uid - other.m_stmt->uid)
776 186695 : return c < 0;
777 81858 : if (int c = node::cmp (*m_id_reg, *other.m_id_reg))
778 55216 : return c < 0;
779 26642 : return m_idx < other.m_idx;
780 : }
781 :
782 : complexity
783 12211 : conjured_bit_contents::key::get_complexity () const
784 : {
785 12211 : return complexity (m_id_reg);
786 : }
787 :
788 12211 : conjured_bit_contents::
789 : conjured_bit_contents (node_manager &node_mgr, const key &k)
790 : : symbolic::unfoldable_bit_contents (k.get_complexity (), node_mgr),
791 12211 : m_stmt (k.m_stmt),
792 12211 : m_id_reg (k.m_id_reg),
793 12211 : m_idx (k.m_idx)
794 : {
795 12211 : }
796 :
797 : void
798 803 : conjured_bit_contents::print_dump_widget_label (pretty_printer *pp) const
799 : {
800 803 : pp_printf (pp, "conjured_bit_contents (");
801 803 : pp_gimple_stmt_1 (pp, m_stmt, 0, (dump_flags_t)0);
802 803 : if (m_idx != 0)
803 0 : pp_printf (pp, ", %i", m_idx);
804 803 : pp_character (pp, ')');
805 803 : }
806 :
807 : void
808 650 : conjured_bit_contents::add_dump_widget_children (text_art::tree_widget &w,
809 : node_dump_state &nds) const
810 : {
811 1300 : w.add_child (m_id_reg->make_dump_widget (nds, "id_reg"));
812 650 : }
813 :
814 : void
815 10864826 : conjured_bit_contents::accept_node_visitor (node_visitor &v) const
816 : {
817 10864826 : if (v.visit_bit_contents (*this))
818 10864826 : m_id_reg->accept_node_visitor (v);
819 10864826 : }
820 :
821 : std::unique_ptr<json::object>
822 0 : conjured_bit_contents::to_json () const
823 : {
824 0 : auto obj = make_json_obj ("conjured_bit_contents");
825 :
826 0 : {
827 0 : pretty_printer pp;
828 0 : pp_format_decoder (&pp) = default_tree_printer;
829 0 : pp_gimple_stmt_1 (&pp, m_stmt, 0, (dump_flags_t)0);
830 0 : obj->set_string ("stmt", pp_formatted_text (&pp));
831 0 : }
832 0 : obj->set ("id_reg", m_id_reg->to_json ());
833 0 : obj->set_integer ("id", m_idx);
834 :
835 0 : return obj;
836 : }
837 :
838 : std::unique_ptr<diagnostics::markup::node>
839 0 : conjured_bit_contents::make_markup_node (markup_context &) const
840 : {
841 0 : return diagnostics::markup::make_text_node ("conjured_bit_contents");
842 : }
843 :
844 : const bit_contents &
845 11401 : conjured_bit_contents::
846 : poison_any_pointers_to_descendents (const region *reg,
847 : enum poison_kind pkind) const
848 : {
849 11401 : if (reg == m_id_reg)
850 : {
851 : // TODO
852 : }
853 11401 : return *this;
854 : }
855 :
856 : const bit_contents &
857 47248 : conjured_bit_contents::purge_state_involving (const symbolic::node &) const
858 : {
859 47248 : return *this;
860 : }
861 :
862 : iter_result
863 359540 : conjured_bit_contents::
864 : for_each_value (iter_result (*) (const symbolic::value_node &val,
865 : void *user_data),
866 : void *) const
867 : {
868 : // No-op
869 359540 : return iter_result::keep_going;
870 : }
871 :
872 : #if CHECKING_P
873 :
874 : // class named_test_bit_contents : public unfoldable_bit_contents
875 :
876 64 : named_test_bit_contents::named_test_bit_contents (node_manager &node_mgr,
877 : std::string name)
878 64 : : unfoldable_bit_contents (complexity (1, 1), node_mgr),
879 64 : m_name (std::move (name))
880 : {
881 64 : }
882 :
883 : void
884 4 : named_test_bit_contents::print_dump_widget_label (pretty_printer *pp) const
885 : {
886 4 : pp_printf (pp, "named_test_bit_contents: %s", m_name.c_str ());
887 4 : }
888 :
889 : void
890 4 : named_test_bit_contents::
891 : add_dump_widget_children (text_art::tree_widget &,
892 : node_dump_state &) const
893 : {
894 : // no-op
895 4 : }
896 :
897 : void
898 0 : named_test_bit_contents::accept_node_visitor (node_visitor &v) const
899 : {
900 0 : v.visit_bit_contents (*this);
901 0 : }
902 :
903 : std::unique_ptr<json::object>
904 12 : named_test_bit_contents::to_json () const
905 : {
906 12 : auto obj = make_json_obj ("named_test_bit_contents");
907 24 : obj->set_string ("name", m_name);
908 12 : return obj;
909 : }
910 :
911 : std::unique_ptr<diagnostics::markup::node>
912 0 : named_test_bit_contents::make_markup_node (markup_context &) const
913 : {
914 0 : return diagnostics::markup::make_text_node (m_name);
915 : }
916 :
917 : const bit_contents &
918 0 : named_test_bit_contents::
919 : poison_any_pointers_to_descendents (const region *,
920 : enum poison_kind) const
921 : {
922 : // no-op
923 0 : return *this;
924 : }
925 :
926 : const bit_contents &
927 0 : named_test_bit_contents::purge_state_involving (const symbolic::node &) const
928 :
929 : {
930 : // no-op
931 0 : return *this;
932 : }
933 :
934 : iter_result
935 4 : named_test_bit_contents::
936 : for_each_value (iter_result (*) (const symbolic::value_node &val,
937 : void *user_data),
938 : void *) const
939 : {
940 : // No-op
941 4 : return iter_result::keep_going;
942 : }
943 :
944 : #endif /* #if CHECKING_P */
945 :
946 : // class concrete_bit_overlay : public bit_overlay
947 :
948 : bool
949 5688106 : concrete_bit_overlay::key::
950 : operator< (const concrete_bit_overlay::key &other) const
951 : {
952 5688106 : if (int c = node::cmp (*m_baseline, *other.m_baseline))
953 250585 : return c < 0;
954 5437521 : if (m_concrete_range_map.size () != other.m_concrete_range_map.size ())
955 209261 : return m_concrete_range_map.size () < other.m_concrete_range_map.size ();
956 :
957 5228260 : auto iter_a = m_concrete_range_map.begin ();
958 5228260 : auto iter_b = other.m_concrete_range_map.begin ();
959 :
960 6594636 : while (iter_a != m_concrete_range_map.end ())
961 : {
962 5392752 : if (int c = node::cmp (iter_a->second, iter_b->second))
963 4023657 : return c < 0;
964 1369095 : if (int c = concrete_bit_range::cmp (iter_a->first, iter_b->first))
965 2719 : return c < 0;
966 1366376 : ++iter_a;
967 1366376 : ++iter_b;
968 : }
969 :
970 : return false;
971 : }
972 :
973 : complexity
974 77824 : concrete_bit_overlay::key::get_complexity () const
975 : {
976 77824 : complexity child_complexities = m_baseline->get_complexity ();
977 169011 : for (auto iter : m_concrete_range_map)
978 182374 : child_complexities += iter.second.get_complexity ();
979 77824 : return complexity::from_child_complexities (child_complexities);
980 : }
981 :
982 : /* Canonicalize by removing bindings where the bit_vector matches the
983 : baseline's bit_vector. */
984 :
985 : void
986 1360989 : concrete_bit_overlay::key::remove_redundant_bindings ()
987 : {
988 1360989 : for (auto iter = m_concrete_range_map.begin ();
989 2847470 : iter != m_concrete_range_map.end ();
990 : )
991 : {
992 1486481 : auto &conc_bit_range = iter->first;
993 1486481 : auto &new_bv = iter->second;
994 1486481 : auto &existing_bv = m_baseline->get_bits (conc_bit_range);
995 1486481 : if (&existing_bv == &new_bv)
996 4227 : iter = m_concrete_range_map.erase (iter);
997 : else
998 1482254 : ++iter;
999 : }
1000 1360989 : }
1001 :
1002 77824 : concrete_bit_overlay::concrete_bit_overlay (const key &k)
1003 77824 : : bit_overlay (k.get_complexity (), *k.m_baseline),
1004 77824 : m_concrete_range_map (k.m_concrete_range_map)
1005 : {
1006 77824 : if (CHECKING_P)
1007 : {
1008 77824 : gcc_assert (!m_concrete_range_map.empty ());
1009 :
1010 : /* Avoid nesting of overlays. */
1011 77824 : gcc_assert
1012 : (get_baseline ().get_kind () != bit_contents::kind::concrete_overlay
1013 : && get_baseline ().get_kind () != bit_contents::kind::symbolic_overlay);
1014 :
1015 77824 : for (auto iter = m_concrete_range_map.begin ();
1016 169011 : iter != m_concrete_range_map.end ();
1017 91187 : ++iter)
1018 : {
1019 91187 : auto &conc_bit_range = iter->first;
1020 91187 : auto &overlay_bv = iter->second;
1021 :
1022 91187 : auto next = iter;
1023 91187 : ++next;
1024 :
1025 : // Check for ordering and non-overlapping bit ranges
1026 91187 : if (next != m_concrete_range_map.end ())
1027 : {
1028 13363 : auto &next_conc_bit_range = next->first;
1029 26726 : gcc_assert (conc_bit_range.get_start_offset ()
1030 : < next_conc_bit_range.get_start_offset ());
1031 26726 : gcc_assert (conc_bit_range.get_last_offset ()
1032 : < next_conc_bit_range.get_start_offset ());
1033 : }
1034 :
1035 : /* Must not have redundant bindings. */
1036 91187 : auto &baseline_bv = get_baseline ().get_bits (conc_bit_range);
1037 91187 : gcc_assert (&overlay_bv != &baseline_bv);
1038 :
1039 : /* The size of each bit_vector must be concrete and match that of
1040 : the bit range it is bound to. */
1041 91187 : concrete_bit_size conc_bv_size;
1042 91187 : bool got_conc_bv_size
1043 91187 : = overlay_bv.maybe_get_concrete_size_in_bits (&conc_bv_size);
1044 91187 : gcc_assert (got_conc_bv_size);
1045 91187 : gcc_assert (conc_bv_size == conc_bit_range.get_size ());
1046 :
1047 91187 : if (auto *concat_bv = overlay_bv.dyn_cast_concat_bit_vector ())
1048 : {
1049 : /* Check for no leading concrete-sized child elements. */
1050 0 : auto first_child_bv = concat_bv->begin ();
1051 0 : gcc_assert
1052 : (!(*first_child_bv)->get_size ().dyn_cast_concrete_scalar ());
1053 : }
1054 91187 : }
1055 : }
1056 77824 : }
1057 :
1058 : const bit_vector &
1059 2171760 : concrete_bit_overlay::get_bits (const symbolic_bit_range &sym_bit_range) const
1060 : {
1061 2171760 : concrete_bit_range conc_bit_range;
1062 2171760 : if (concrete_from_symbolic (sym_bit_range, &conc_bit_range))
1063 2169162 : return get_concrete_bits (conc_bit_range);
1064 :
1065 : // TODO: should we be returning a bit_vector_from_ubc here?
1066 2598 : auto &bv_mgr = get_bit_vector_manager ();
1067 2598 : return bv_mgr.get_unknown_bits (sym_bit_range.get_size ()); // FIXME
1068 2171760 : }
1069 :
1070 : void
1071 1516 : concrete_bit_overlay::print_dump_widget_label (pretty_printer *pp) const
1072 : {
1073 1516 : pp_string (pp, "concrete bit overlay");
1074 1516 : }
1075 :
1076 : void
1077 1471 : concrete_bit_overlay::add_dump_widget_children (text_art::tree_widget &w,
1078 : node_dump_state &nds) const
1079 : {
1080 1471 : using tree_widget = text_art::tree_widget;
1081 1471 : std::unique_ptr<tree_widget> ranges_widget
1082 1471 : (tree_widget::from_fmt (nds, nullptr, "concrete ranges"));
1083 2942 : for (auto iter : m_concrete_range_map)
1084 : {
1085 1471 : auto &bit_range = iter.first;
1086 1471 : auto &bv = iter.second;
1087 1471 : pretty_printer pp;
1088 1471 : bit_range.dump_to_pp_pretty (&pp);
1089 2942 : ranges_widget->add_child (bv.make_dump_widget (nds,
1090 : pp_formatted_text (&pp)));
1091 2942 : }
1092 2942 : w.add_child (std::move (ranges_widget));
1093 2942 : w.add_child (get_baseline ().make_dump_widget (nds, "baseline"));
1094 1471 : }
1095 :
1096 : void
1097 17511 : concrete_bit_overlay::accept_node_visitor (node_visitor &v) const
1098 : {
1099 17511 : if (v.visit_bit_contents (*this))
1100 : {
1101 17511 : get_baseline ().accept_node_visitor (v);
1102 36250 : for (auto iter : m_concrete_range_map)
1103 : {
1104 18739 : auto &bit_range = iter.first;
1105 18739 : auto &bv = iter.second;
1106 : // FIXME: bit_range.accept_node_visitor (v);
1107 18739 : bv.accept_node_visitor (v);
1108 18739 : }
1109 : }
1110 17511 : }
1111 :
1112 : std::unique_ptr<json::object>
1113 20 : concrete_bit_overlay::to_json () const
1114 : {
1115 20 : auto obj = make_json_obj ("concrete_bit_overlay");
1116 20 : auto arr = std::make_unique<json::array> ();
1117 96 : for (auto iter : m_concrete_range_map)
1118 : {
1119 76 : auto &bit_range = iter.first;
1120 76 : auto &bv = iter.second;
1121 76 : auto element = std::make_unique<json::object> ();
1122 76 : element->set ("range", bit_range.to_json ());
1123 76 : element->set ("bv", bv.to_json ());
1124 76 : arr->append (std::move (element));
1125 152 : }
1126 20 : obj->set ("concrete_range_map", std::move (arr));
1127 20 : obj->set ("baseline", get_baseline ().to_json ());
1128 40 : return obj;
1129 20 : }
1130 :
1131 : std::unique_ptr<diagnostics::markup::node>
1132 0 : concrete_bit_overlay::make_markup_node (markup_context &) const
1133 : {
1134 0 : return diagnostics::markup::make_text_node ("concrete_bit_overlay");
1135 : }
1136 :
1137 : string_scan
1138 3782 : concrete_bit_overlay::
1139 : scan_for_first_zero_byte (string_scan::byte_offset_type start_scan_offset) const
1140 : {
1141 5311 : for (auto iter : m_concrete_range_map)
1142 : {
1143 5084 : auto &bit_range = iter.first;
1144 5084 : auto &bv = iter.second;
1145 :
1146 5084 : concrete_byte_range byte_range;
1147 10168 : if (!maybe_bytes_from_bits (bit_range, &byte_range))
1148 0 : return string_scan::cannot_scan (start_scan_offset);
1149 :
1150 5084 : if (start_scan_offset < byte_range.get_start_offset ())
1151 : {
1152 : /* We're looking before the range. See it we have non-zero
1153 : bytes leading to the range. */
1154 234 : string_scan scan
1155 234 : = get_baseline ().scan_for_first_zero_byte (start_scan_offset);
1156 234 : switch (scan.m_state)
1157 : {
1158 234 : default:
1159 234 : return scan;
1160 0 : case string_scan::state::beyond_domain:
1161 : /* We have non-zero bytes leading to the range. */
1162 0 : start_scan_offset = byte_range.get_start_offset ();
1163 0 : break;
1164 : }
1165 234 : }
1166 :
1167 4850 : if (start_scan_offset < byte_range.get_next_offset ())
1168 : {
1169 : /* Look within this bv. */
1170 3763 : auto bv_result = bv.scan_for_first_zero_byte
1171 3763 : (start_scan_offset
1172 3763 : - byte_range.get_start_offset ());
1173 3763 : if (bv_result.m_state == string_scan::state::beyond_domain)
1174 : {
1175 : /* Try to carry on to the next range (or gap). */
1176 442 : start_scan_offset = byte_range.get_next_offset ();
1177 442 : continue;
1178 : }
1179 : else
1180 3321 : return string_scan (bv_result.m_byte_offset
1181 6642 : + byte_range.get_start_offset (),
1182 6642 : bv_result.m_state);
1183 3763 : }
1184 : else
1185 : {
1186 : /* We're scannning after this overlay; ignore it. */
1187 1087 : continue;
1188 : }
1189 10168 : }
1190 :
1191 : // Beyond the end of the overlay ranges; look at underlying bit contents:
1192 227 : return get_baseline ().scan_for_first_zero_byte (start_scan_offset);
1193 : }
1194 :
1195 : static bool
1196 25210 : bit_vector_matches_sval_p (const symbolic::bit_vector &bv,
1197 : const svalue &sval)
1198 : {
1199 25210 : if (auto *bvs = bv.dyn_cast_bit_vector_from_svalue ())
1200 : {
1201 16227 : if (&bvs->get_svalue () == &sval)
1202 : return true;
1203 25192 : if (auto *sym_ptr_from_bv
1204 12596 : = bvs->get_svalue ().maybe_get_symbolic_pointer ())
1205 8814 : if (auto *sym_ptr_from_sval = sval.maybe_get_symbolic_pointer ())
1206 5695 : if (*sym_ptr_from_bv == *sym_ptr_from_sval)
1207 : return true;
1208 : }
1209 19455 : auto &bv_mgr = bv.get_bit_vector_manager ();
1210 19455 : if (auto *bv_from_sval = bv_mgr.maybe_fold_bits_for_svalue (sval))
1211 6154 : if (&bv == bv_from_sval)
1212 2284 : return true;
1213 : return false;
1214 : }
1215 :
1216 : void
1217 21438 : concrete_bit_overlay::
1218 : get_representative_path_vars (const region_model *model,
1219 : value_set *visited,
1220 : const region *base_reg,
1221 : const svalue *sval,
1222 : tree desired_type,
1223 : logger *logger,
1224 : auto_vec<path_var> *out_pvs) const
1225 : {
1226 : /* Find if SVAL is present anywhere in m_concrete_range_map. */
1227 43704 : for (auto iter : m_concrete_range_map)
1228 : {
1229 22266 : auto &bit_range = iter.first;
1230 22266 : auto &bv = iter.second;
1231 :
1232 22266 : if (bit_vector_matches_sval_p (bv, *sval))
1233 : {
1234 : /* Found SVAL at bit_range relative to BASE_REG.
1235 : Try to convert that to a subregion, and from there
1236 : to a path_var. */
1237 7965 : auto_vec<const region *> sub_regions;
1238 7965 : base_reg->get_subregions_for_bit_range (model->get_manager (),
1239 : bit_range,
1240 : desired_type,
1241 : &sub_regions);
1242 30732 : for (auto reg : sub_regions)
1243 15178 : if (path_var pv
1244 7589 : = model->get_representative_path_var (reg,
1245 : visited,
1246 7589 : logger))
1247 7589 : append_pathvar_with_type (pv, desired_type, out_pvs);
1248 7965 : }
1249 22266 : }
1250 21438 : }
1251 :
1252 : /* Helper subroutine for poison_any_pointers_to_descendents implementations.
1253 : Return true for descendents of BAD_ANCESTOR_REG, but not to zero-offset
1254 : pointers (otherwise double-free detection doesn't work, since sm-state
1255 : for "free" is stored on the original ptr svalue). */
1256 :
1257 : static bool
1258 35645 : should_poison_sym_ptr_p (const symbolic::pointer &sym_ptr,
1259 : const region &bad_ancestor_reg)
1260 : {
1261 35645 : const region &base_reg = sym_ptr.get_base_region ();
1262 35645 : if (!base_reg.descendent_of_p (&bad_ancestor_reg))
1263 : return false;
1264 12791 : if (&base_reg == &bad_ancestor_reg
1265 12791 : && sym_ptr.get_byte_offset ().is_zero_p ())
1266 12244 : return false;
1267 : return true;
1268 : }
1269 :
1270 : const bit_contents &
1271 89980 : concrete_bit_overlay::
1272 : poison_any_pointers_to_descendents (const region *reg,
1273 : enum poison_kind pkind) const
1274 : {
1275 89980 : concrete_bit_overlay::key k {&get_baseline (), {}};
1276 :
1277 186105 : for (auto iter : m_concrete_range_map)
1278 : {
1279 96125 : auto &bit_range = iter.first;
1280 96125 : const bit_vector *bv = &iter.second;
1281 :
1282 96125 : if (auto *bvs = bv->dyn_cast_bit_vector_from_svalue ())
1283 : {
1284 67884 : if (auto *sym_ptr = bvs->get_svalue ().maybe_get_symbolic_pointer ())
1285 35578 : if (should_poison_sym_ptr_p (*sym_ptr, *reg))
1286 : {
1287 547 : auto &bv_mgr = get_bit_vector_manager ();
1288 547 : bv = &bv_mgr.get_poisoned_bits (bv->get_size (), pkind);
1289 : }
1290 : }
1291 192250 : k.m_concrete_range_map.insert ({bit_range, *bv});
1292 96125 : }
1293 :
1294 89980 : return get_bit_contents_manager ().get_concrete_bit_overlay (std::move (k),
1295 89980 : nullptr);
1296 89980 : }
1297 :
1298 : const bit_contents &
1299 246134 : concrete_bit_overlay::purge_state_involving (const symbolic::node &node) const
1300 : {
1301 246134 : concrete_bit_overlay::key k {&get_baseline (), {}};
1302 :
1303 502732 : for (auto iter : m_concrete_range_map)
1304 : {
1305 256598 : auto &bit_range = iter.first;
1306 256598 : const bit_vector *bv = &iter.second;
1307 :
1308 256598 : if (bv->involves_p (node))
1309 : {
1310 2401 : auto &bv_mgr = get_bit_vector_manager ();
1311 2401 : bv = &bv_mgr.get_unknown_bits (bv->get_size ());
1312 : }
1313 513196 : k.m_concrete_range_map.insert ({bit_range, *bv});
1314 256598 : }
1315 :
1316 246134 : return get_bit_contents_manager ().get_concrete_bit_overlay (std::move (k),
1317 246134 : nullptr);
1318 246134 : }
1319 :
1320 : bool
1321 683916 : concrete_bit_overlay::bits_live_p (const symbolic::bit_vector_from_ubc &) const
1322 : {
1323 683916 : return false;
1324 : }
1325 :
1326 : iter_result
1327 3454677 : concrete_bit_overlay::
1328 : for_each_value (iter_result (*cb) (const symbolic::value_node &val,
1329 : void *user_data),
1330 : void *user_data) const
1331 : {
1332 3454677 : if (get_baseline ().for_each_value (cb, user_data) == iter_result::stop)
1333 : return iter_result::stop;
1334 7610753 : for (auto iter : m_concrete_range_map)
1335 : {
1336 4156076 : const bit_vector *bv = &iter.second;
1337 4156076 : if (cb (*bv, user_data) == iter_result::stop)
1338 0 : return iter_result::stop;
1339 4156076 : }
1340 3454677 : return iter_result::keep_going;
1341 : }
1342 :
1343 : // Implementation detail of concrete_bit_overlay::get_concrete_bits
1344 :
1345 2169162 : class pending_bit_vector
1346 : {
1347 : public:
1348 2169162 : pending_bit_vector (bit_vector_manager &bv_mgr,
1349 : const bit_contents &baseline)
1350 2169162 : : m_bv_mgr (bv_mgr),
1351 2169162 : m_baseline (baseline),
1352 2169162 : m_accum_size (0_bits)
1353 : {}
1354 :
1355 : void
1356 2476328 : on_concrete_mapping (const concrete_bit_range &key_range,
1357 : const bit_vector &bv_value,
1358 : const concrete_bit_range &crop_range)
1359 : {
1360 2476328 : concrete_bit_range overlap;
1361 2476328 : if (key_range.intersects_p (crop_range, &overlap))
1362 : {
1363 2154665 : integer_with_unit<units::bit> start_offset_within_full_bv
1364 2154665 : = overlap.get_start_offset () - key_range.get_start_offset ();
1365 2154665 : concrete_bit_range bits_to_use (start_offset_within_full_bv,
1366 4309330 : overlap.get_size ());
1367 :
1368 : /* Add any necessary leading padding. */
1369 2154665 : integer_with_unit<units::bit> size_up_to_start_of_binding
1370 2154665 : = key_range.get_start_offset () - crop_range.get_start_offset ();
1371 2154665 : append_any_gap
1372 6463995 : (concrete_bit_range (crop_range.get_start_offset () + m_accum_size,
1373 4309330 : size_up_to_start_of_binding - m_accum_size));
1374 :
1375 2154665 : auto &cropped_bv = bv_value.get_cropped_bits (bits_to_use);
1376 2154665 : append_bit_vector (cropped_bv);
1377 4309330 : }
1378 2476328 : }
1379 :
1380 : void
1381 4323827 : append_any_gap (concrete_bit_range gap_range)
1382 : {
1383 4323827 : if (gap_range.get_size () > 0_bits)
1384 17195 : append_bit_vector (m_baseline.get_bits (gap_range));
1385 4323827 : }
1386 :
1387 : void
1388 2169162 : add_any_trailing_gap (const concrete_bit_range &bit_range)
1389 : {
1390 2169162 : append_any_gap
1391 6507486 : (concrete_bit_range (bit_range.get_start_offset () + m_accum_size,
1392 6507486 : bit_range.get_size () - m_accum_size));
1393 2169162 : }
1394 :
1395 : const bit_vector &
1396 2169162 : to_bit_vector ()
1397 : {
1398 2169162 : return m_bv_mgr.get_concat_bits (std::move (m_bit_vectors));
1399 : }
1400 :
1401 : private:
1402 : void
1403 2171860 : append_bit_vector (const symbolic::bit_vector &bv)
1404 : {
1405 2171860 : concrete_bit_size conc_size;
1406 2171860 : if (!concrete_from_symbolic (bv.get_size (), &conc_size))
1407 0 : gcc_unreachable ();
1408 2171860 : m_bit_vectors.push_back (&bv);
1409 2171860 : m_accum_size += conc_size;
1410 2171860 : }
1411 :
1412 : bit_vector_manager &m_bv_mgr;
1413 : const bit_contents &m_baseline;
1414 : std::vector<const symbolic::bit_vector *> m_bit_vectors;
1415 : concrete_bit_size m_accum_size;
1416 : };
1417 :
1418 : const bit_vector &
1419 2169162 : concrete_bit_overlay::
1420 : get_concrete_bits (const concrete_bit_range &bit_range) const
1421 : {
1422 2169162 : pending_bit_vector pending (get_bit_vector_manager (), get_baseline ());
1423 4645490 : for (auto iter : m_concrete_range_map)
1424 4952656 : pending.on_concrete_mapping (iter.first, iter.second, bit_range);
1425 2169162 : pending.add_any_trailing_gap (bit_range);
1426 :
1427 2169162 : auto &result = pending.to_bit_vector ();
1428 2169162 : gcc_assert (result.get_size ().dyn_cast_concrete_scalar ()->get_concrete ()
1429 : == bit_range.get_size ());
1430 2169162 : return result;
1431 2169162 : }
1432 :
1433 : /* Return true iff CONC_BIT_OFFSET is bound in one of this
1434 : concrete_bit_overlay's ranges. */
1435 :
1436 : bool
1437 140585 : concrete_bit_overlay::
1438 : bit_offset_is_bound_p (concrete_bit_offset conc_bit_offset) const
1439 : {
1440 : /* The concrete range comparator sorts by offset, then by size,
1441 : so we use a zero-sized range. */
1442 140585 : auto iter = m_concrete_range_map.lower_bound
1443 421755 : (concrete_bit_range (conc_bit_offset, 0_bits));
1444 140585 : if (iter != m_concrete_range_map.end ()
1445 279264 : && iter->first.contains_p (conc_bit_offset))
1446 : return true;
1447 3458 : if (iter == m_concrete_range_map.begin ())
1448 : return false;
1449 3155 : --iter;
1450 3155 : return iter->first.contains_p (conc_bit_offset);
1451 : }
1452 :
1453 : /* Populate a map for mapping BV to NEW_BIT_RANGE.
1454 : Canonicalize concat_bit_vector into multiple ranges where
1455 : possible. */
1456 :
1457 : std::map<concrete_bit_range, const bit_vector &>
1458 357359 : concrete_bit_overlay::
1459 : canonicalize_new_bit_vec (const concrete_bit_range &new_bit_range,
1460 : const bit_vector &bv)
1461 : {
1462 357359 : if (auto *concat_bv = bv.dyn_cast_concat_bit_vector ())
1463 : {
1464 : /* Canonicalize by splitting out leading concrete-sized elements
1465 : from concat_bv as separate bindings. */
1466 526 : std::map<concrete_bit_range, const bit_vector &> split_map;
1467 526 : concrete_bit_offset curr_start_offset = new_bit_range.get_start_offset ();
1468 1885 : for (auto iter : *concat_bv)
1469 : {
1470 1359 : concrete_bit_size conc_element_size;
1471 1359 : if (iter->maybe_get_concrete_size_in_bits (&conc_element_size))
1472 : {
1473 1359 : concrete_bit_range element_bit_range (curr_start_offset,
1474 2718 : conc_element_size);
1475 1359 : split_map.insert ({element_bit_range, *iter});
1476 1359 : curr_start_offset += conc_element_size;
1477 1359 : }
1478 : else
1479 : {
1480 : /* We have a symbolically-sized element; do as a single range. */
1481 0 : return {{new_bit_range, bv}};
1482 : }
1483 1359 : }
1484 526 : return split_map;
1485 526 : }
1486 :
1487 : /* Do BV as a single range. */
1488 713666 : return {{new_bit_range, bv}};
1489 : }
1490 :
1491 : /* Generate a map from MAP where any adjacent bindings have been
1492 : consolidated, combining the ranges and concatenating the bit_vectors. */
1493 :
1494 : std::map<concrete_bit_range, const bit_vector &>
1495 44501 : concrete_bit_overlay::
1496 : consolidate_adjacent (std::map<concrete_bit_range, const bit_vector &> map,
1497 : bit_vector_manager &bv_mgr)
1498 : {
1499 44501 : std::vector<std::pair<concrete_bit_range, const bit_vector &>> result;
1500 128579 : for (auto iter : map)
1501 : {
1502 84078 : if (!result.empty ())
1503 : {
1504 39577 : const concrete_bit_range &prev_range = result.back ().first;
1505 39577 : const concrete_bit_range &iter_range = iter.first;
1506 39577 : if (prev_range.get_next_offset () == iter_range.get_start_offset ())
1507 : {
1508 : /* They touch. Try concatenating the vectors, to see if
1509 : the results simplifies. */
1510 37255 : const bit_vector &prev_bv = result.back ().second;
1511 37255 : const bit_vector &iter_bv = iter.second;
1512 37255 : auto &concat
1513 37255 : = bv_mgr.get_concat_bits ({&prev_bv, &iter_bv});
1514 37255 : if (!concat.dyn_cast_concat_bit_vector ())
1515 : {
1516 : /* We were able to consolidate adjacent vectors.
1517 : Overwrite with the consolidated range/bit_vector,
1518 : rather than inserting a new element. */
1519 2036 : concrete_bit_range combined_range
1520 4072 : (prev_range.get_start_offset (),
1521 6108 : prev_range.get_size () + iter_range.get_size ());
1522 2036 : result.pop_back ();
1523 2036 : result.push_back ({combined_range, concat});
1524 2036 : continue;
1525 2036 : }
1526 : }
1527 : }
1528 164084 : result.push_back (iter);
1529 84078 : }
1530 44501 : return std::map<concrete_bit_range, const bit_vector &> (result.begin (),
1531 44501 : result.end ());
1532 44501 : }
1533 :
1534 : /* Consider:
1535 : | +------------------------------------+
1536 : | | old binding |
1537 : | +------------------------------------+
1538 : |
1539 : | +----------------------+
1540 : | | new binding |
1541 : | +----------------------+
1542 :
1543 : This function makes a new overlay by adding the new
1544 : binding, then "cutting a hole" out of any old bindings:
1545 : | +------+......................+------+
1546 : | |prefix| hole for new binding |suffix|
1547 : | +------+......................+------+
1548 : and adding them where they are not overwritten. */
1549 :
1550 : const bit_contents &
1551 44501 : concrete_bit_overlay::set_concrete_bits (const concrete_bit_range &new_bit_range,
1552 : const bit_vector &bv) const
1553 : {
1554 44501 : std::map<concrete_bit_range, const bit_vector &> new_concrete_range_map
1555 44501 : = canonicalize_new_bit_vec (new_bit_range, bv);
1556 :
1557 119765 : for (auto iter : m_concrete_range_map)
1558 : {
1559 75264 : auto &original_bit_range = iter.first;
1560 75264 : concrete_bit_range overlap;
1561 75264 : if (!new_bit_range.intersects_p (original_bit_range, &overlap))
1562 : {
1563 : // No overlap
1564 36706 : new_concrete_range_map.insert (iter);
1565 36706 : continue;
1566 : }
1567 :
1568 : /* Otherwise we have overlap. There are various cases that can occur:
1569 :
1570 : If NEW_BIT_RANGE is fully within original_bit_range:
1571 : | +------------------------------------+
1572 : | | original_bit_range |
1573 : | +------------------------------------+
1574 : | +----------------------+
1575 : | | new_bit_range |
1576 : | +----------------------+
1577 : then cut the old binding into two cropped pieces:
1578 : | +------+......................+------+
1579 : | |prefix| hole for new binding |suffix|
1580 : | +------+......................+------+
1581 :
1582 : If original_bit_range is fully within NEW_BIT_RANGE:
1583 : | +----------------------+
1584 : | | original_bit_range |
1585 : | +----------------------+
1586 : | +------------------------------------+
1587 : | | new_bit_range |
1588 : | +------------------------------------+
1589 : then the old binding is fully discarded
1590 :
1591 : Otherwise, we have either this case:
1592 : | +------------------+
1593 : | |original_bit_range|
1594 : | +------------------+
1595 : | +----------------------+
1596 : | | new_bit_range |
1597 : | +----------------------+
1598 : | +------+
1599 : | |prefix|
1600 : | +------+
1601 : or this case:
1602 : | +------------------+
1603 : | |original_bit_range|
1604 : | +------------------+
1605 : | +----------------------+
1606 : | | new_bit_range |
1607 : | +----------------------+
1608 : | +------+
1609 : | |suffix|
1610 : | +------+
1611 :
1612 : Handle these four cases by adding any prefix
1613 : and adding any suffix. */
1614 :
1615 : /* Add any prefix. */
1616 77116 : auto prefix_size = (overlap.get_start_offset ()
1617 38558 : - original_bit_range.get_start_offset ());
1618 38558 : if (prefix_size > 0_bits)
1619 : {
1620 730 : concrete_bit_range prefix_range
1621 1460 : (original_bit_range.get_start_offset (),
1622 1460 : prefix_size);
1623 730 : auto &prefix_bv = iter.second.get_prefix (prefix_size);
1624 730 : for (auto iter_prefix : canonicalize_new_bit_vec (prefix_range,
1625 1460 : prefix_bv))
1626 2190 : new_concrete_range_map.insert (iter_prefix);
1627 730 : }
1628 :
1629 : /* Add any suffix. */
1630 77116 : auto suffix_size = (original_bit_range.get_next_offset ()
1631 38558 : - overlap.get_next_offset ());
1632 38558 : if (suffix_size > 0_bits)
1633 : {
1634 1951 : concrete_bit_range suffix_range
1635 3902 : (overlap.get_next_offset (),
1636 3902 : suffix_size);
1637 1951 : auto &suffix_bv = iter.second.get_suffix (suffix_size);
1638 1959 : for (auto iter_suffix : canonicalize_new_bit_vec (suffix_range,
1639 3910 : suffix_bv))
1640 5869 : new_concrete_range_map.insert (iter_suffix);
1641 1951 : }
1642 189086 : }
1643 :
1644 : // TODO: is there any other canonicalization we want to do here?
1645 89002 : new_concrete_range_map = consolidate_adjacent (new_concrete_range_map,
1646 44501 : get_bit_vector_manager ());
1647 :
1648 44501 : concrete_bit_overlay::key k {&get_baseline (),
1649 44501 : std::move (new_concrete_range_map)};
1650 44501 : return get_bit_contents_manager ().get_concrete_bit_overlay (std::move (k),
1651 44501 : nullptr);
1652 44501 : }
1653 :
1654 : /* Attempt to extract an svalue (with type), a special-case for handling
1655 : interprocedural type-checking of variadic args. */
1656 :
1657 : const svalue *
1658 557 : concrete_bit_overlay::maybe_get_var_arg_svalue () const
1659 : {
1660 : /* Look for an initial binding to a bit_vector. */
1661 557 : auto iter = m_concrete_range_map.begin ();
1662 557 : if (iter == m_concrete_range_map.end ())
1663 : return nullptr;
1664 557 : auto &bv = iter->second;
1665 557 : auto *bv_from_sval = bv.dyn_cast_bit_vector_from_svalue ();
1666 557 : if (!bv_from_sval)
1667 : return nullptr;
1668 557 : return &bv_from_sval->get_svalue ();
1669 : }
1670 :
1671 : static tree
1672 75467 : maybe_get_type_for_range (tree type, const concrete_bit_range &bit_range)
1673 : {
1674 75467 : if (!type)
1675 : return NULL_TREE;
1676 :
1677 69585 : if (bit_range.get_start_offset () == 0_bits)
1678 : {
1679 63635 : bit_size_t type_size;
1680 63635 : if (int_size_in_bits (type, &type_size))
1681 63442 : if (bit_range.get_size () == convert_from_bit_size_t (type_size))
1682 : /* We have the full size of TYPE, use it. */
1683 61374 : return type;
1684 : }
1685 :
1686 8211 : if (TREE_CODE (type) == RECORD_TYPE)
1687 : {
1688 : // TODO: maybe cache this?
1689 3063 : record_layout layout (type);
1690 :
1691 3063 : if (auto *item = layout.get_item_at (bit_range.get_start_offset ()))
1692 : {
1693 3058 : const_tree field = item->m_field;
1694 3058 : concrete_bit_range range_relative_to_field
1695 3058 : (bit_range.get_start_offset ()
1696 9174 : - item->get_start_offset (),
1697 6116 : bit_range.get_size ());
1698 3058 : return maybe_get_type_for_range (TREE_TYPE (field),
1699 : range_relative_to_field);
1700 3058 : }
1701 3063 : }
1702 :
1703 : return NULL_TREE;
1704 : }
1705 :
1706 : /* Attempt to merge BIT_CONTENTS_A and BIT_CONTENTS_B.
1707 : At least one is a concrete_bit_overlay with SHARED_BASELINE,
1708 : otherwise they *are* SHARED_BASELINE.
1709 : CONC_BIT_OVERLAY_{A,B} are the result of dynamic casting each of
1710 : BIT_CONTENTS_{A,B} to concrete_bit_overlay. */
1711 :
1712 : const bit_contents *
1713 63457 : concrete_bit_overlay::
1714 : can_merge_p (const bit_contents &bit_contents_a,
1715 : const bit_contents &bit_contents_b,
1716 : const bit_contents &shared_baseline,
1717 : const concrete_bit_overlay *conc_bit_overlay_a,
1718 : const concrete_bit_overlay *conc_bit_overlay_b,
1719 : tree type,
1720 : model_merger *merger)
1721 : {
1722 : /* Locate all transitions. */
1723 63457 : std::set<concrete_bit_offset> bit_offsets;
1724 63457 : if (conc_bit_overlay_a)
1725 131897 : for (auto iter : conc_bit_overlay_a->m_concrete_range_map)
1726 : {
1727 70037 : bit_offsets.insert (iter.first.get_start_offset ());
1728 70037 : bit_offsets.insert (iter.first.get_next_offset ());
1729 70037 : }
1730 63457 : if (conc_bit_overlay_b)
1731 129225 : for (auto iter : conc_bit_overlay_b->m_concrete_range_map)
1732 : {
1733 68184 : bit_offsets.insert (iter.first.get_start_offset ());
1734 68184 : bit_offsets.insert (iter.first.get_next_offset ());
1735 68184 : }
1736 :
1737 : /* Convert into a vector of ranges, expressing the ranges
1738 : between elements in the set of transition offsets. */
1739 63457 : concrete_bit_offset prev_offset;
1740 63457 : std::vector<concrete_bit_range> bit_ranges;
1741 63457 : for (auto iter = bit_offsets.begin ();
1742 200310 : iter != bit_offsets.end ();
1743 136853 : ++iter)
1744 : {
1745 136853 : if (iter != bit_offsets.begin ())
1746 : {
1747 73396 : auto &next_offset = *iter;
1748 73396 : auto size = next_offset - prev_offset;
1749 220188 : bit_ranges.push_back (concrete_bit_range (prev_offset, size));
1750 73396 : }
1751 136853 : prev_offset = *iter;
1752 : }
1753 :
1754 : /* Now try to merge the bit vectors at each range. */
1755 63457 : concrete_bit_overlay::key k {&shared_baseline, {}};
1756 117833 : for (auto bit_range : bit_ranges)
1757 : {
1758 72409 : tree type_for_range = maybe_get_type_for_range (type, bit_range);
1759 :
1760 : /* Subroutine: return true if the start offset of BIT_RANGE is bound
1761 : within CONC_BIT_OVERLAY. */
1762 217227 : auto range_is_bound_p = []
1763 : (const concrete_bit_range &bit_range,
1764 : const concrete_bit_overlay *conc_bit_overlay) -> bool
1765 : {
1766 144818 : if (!conc_bit_overlay)
1767 : return false;
1768 140389 : return conc_bit_overlay->bit_offset_is_bound_p
1769 140389 : (bit_range.get_start_offset ());
1770 : };
1771 72409 : bool bound_in_a = range_is_bound_p (bit_range, conc_bit_overlay_a);
1772 72409 : bool bound_in_b = range_is_bound_p (bit_range, conc_bit_overlay_b);
1773 :
1774 72409 : const bit_vector *merged_bv = nullptr;
1775 :
1776 72409 : auto &bv_a = bit_contents_a.get_bits (bit_range);
1777 72409 : auto &bv_b = bit_contents_b.get_bits (bit_range);
1778 72409 : if (bound_in_a && bound_in_b)
1779 : {
1780 : /* Bound in both. */
1781 65874 : merged_bv = bit_vector::can_merge_p (bv_a,
1782 : bv_b,
1783 : type_for_range,
1784 : merger);
1785 : }
1786 6535 : else if (bound_in_a || bound_in_b)
1787 : {
1788 : /* We only have a binding for iter in one of the concrete_range_maps,
1789 : i.e. an attempt to merge bound and not-bound.
1790 : We might be dealing with conditional initialization, or of an
1791 : initialization of a growing region of a buffer in a loop. */
1792 6303 : if ((bound_in_a
1793 6303 : && !conc_bit_overlay_b
1794 2709 : && bv_b.dyn_cast_poisoned_bit_vector ())
1795 6303 : || (bound_in_b
1796 5128 : && !conc_bit_overlay_a
1797 1679 : && bv_a.dyn_cast_poisoned_bit_vector ()))
1798 : {
1799 : /* One is bound; the other is fully unbound and is uninitialized
1800 : over the range of interest.
1801 : Assume this is conditional initialization, and block the
1802 : merger. */
1803 : return nullptr;
1804 : }
1805 :
1806 : /* Otherwise, merge this bit range as "UNKNOWN" (assuming the other
1807 : bv is mergeable). */
1808 4299 : auto &bv_mgr = bit_contents_a.get_bit_vector_manager ();
1809 4299 : auto &unknown_bv
1810 4299 : = bv_mgr.get_unknown_bits (bit_range.get_size ());
1811 4299 : auto &bound_bv = bound_in_a ? bv_a : bv_b;
1812 4299 : if (bit_vector::can_merge_p (unknown_bv,
1813 : bound_bv,
1814 : type_for_range,
1815 : merger))
1816 : merged_bv = &unknown_bv;
1817 : }
1818 : else
1819 : {
1820 : /* We have a "hole" where neither has a binding. */
1821 232 : continue;
1822 : }
1823 :
1824 69248 : if (merged_bv)
1825 108288 : for (auto iter : canonicalize_new_bit_vec (bit_range, *merged_bv))
1826 162432 : k.m_concrete_range_map.insert (iter);
1827 : else
1828 : return nullptr;
1829 72409 : }
1830 :
1831 45424 : auto &bit_contents_mgr = shared_baseline.get_bit_contents_manager ();
1832 45424 : return &bit_contents_mgr.get_concrete_bit_overlay (std::move (k),
1833 : nullptr);
1834 63457 : }
1835 :
1836 : // class symbolic_bit_overlay : public bit_overlay
1837 :
1838 : bool
1839 183955 : symbolic_bit_overlay::key::
1840 : operator< (const symbolic_bit_overlay::key &other) const
1841 : {
1842 183955 : if (int c = node::cmp (*m_baseline, *other.m_baseline))
1843 9729 : return c < 0;
1844 174226 : if (m_symbolic_range_map.size () != other.m_symbolic_range_map.size ())
1845 0 : return m_symbolic_range_map.size () < other.m_symbolic_range_map.size ();
1846 :
1847 174226 : auto iter_a = m_symbolic_range_map.begin ();
1848 174226 : auto iter_b = other.m_symbolic_range_map.begin ();
1849 :
1850 205584 : while (iter_a != m_symbolic_range_map.end ())
1851 : {
1852 174226 : if (int c = node::cmp (iter_a->second, iter_b->second))
1853 141460 : return c < 0;
1854 32766 : if (int c = symbolic_bit_range::cmp (iter_a->first, iter_b->first))
1855 1408 : return c < 0;
1856 31358 : ++iter_a;
1857 31358 : ++iter_b;
1858 : }
1859 :
1860 : return false;
1861 : }
1862 :
1863 : complexity
1864 2424 : symbolic_bit_overlay::key::get_complexity () const
1865 : {
1866 2424 : complexity child_complexities = m_baseline->get_complexity ();
1867 4848 : for (auto iter : m_symbolic_range_map)
1868 : {
1869 2424 : child_complexities += iter.first.get_complexity ();
1870 2424 : child_complexities += iter.second.get_complexity ();
1871 : }
1872 2424 : return complexity::from_child_complexities (child_complexities);
1873 : }
1874 :
1875 : /* Canonicalize by removing bindings where the bit_vector matches the
1876 : baseline's bit_vector. */
1877 :
1878 : void
1879 37046 : symbolic_bit_overlay::key::remove_redundant_bindings ()
1880 : {
1881 37046 : for (auto iter = m_symbolic_range_map.begin ();
1882 74092 : iter != m_symbolic_range_map.end ();
1883 : )
1884 : {
1885 37046 : auto &sym_bit_range = iter->first;
1886 37046 : auto &new_bv = iter->second;
1887 37046 : auto &existing_bv = m_baseline->get_bits (sym_bit_range);
1888 37046 : if (&existing_bv == &new_bv)
1889 643 : iter = m_symbolic_range_map.erase (iter);
1890 : else
1891 36403 : ++iter;
1892 : }
1893 37046 : }
1894 :
1895 2424 : symbolic_bit_overlay::symbolic_bit_overlay (const key &k)
1896 2424 : : bit_overlay (k.get_complexity (), *k.m_baseline),
1897 2424 : m_symbolic_range_map (k.m_symbolic_range_map)
1898 : {
1899 2424 : if (CHECKING_P)
1900 : {
1901 2424 : gcc_assert (!m_symbolic_range_map.empty ());
1902 2424 : gcc_assert (m_symbolic_range_map.size () == 1);
1903 :
1904 : /* Avoid nesting of overlays. */
1905 2424 : gcc_assert
1906 : (get_baseline ().get_kind () != bit_contents::kind::concrete_overlay
1907 : && get_baseline ().get_kind () != bit_contents::kind::symbolic_overlay);
1908 :
1909 4848 : for (auto iter : m_symbolic_range_map)
1910 : {
1911 2424 : auto &bit_range = iter.first;
1912 2424 : auto &overlay_bv = iter.second;
1913 :
1914 : /* Start offsets are not allowed to be "unknown". */
1915 2424 : gcc_assert (!bit_range.get_start_offset ().is_unknown_p ());
1916 :
1917 : // TODO(design question): do we want to allow unknown sizes?
1918 : #if 0
1919 : gcc_assert (!bit_range.get_size ().is_unknown_p ());
1920 : #endif
1921 :
1922 : // Bit ranges in the map are not allowed to be fully concrete
1923 2424 : concrete_bit_range conc_bit_range;
1924 2424 : bool got_conc_bit_range
1925 2424 : = concrete_from_symbolic (bit_range, &conc_bit_range);
1926 2424 : gcc_assert (!got_conc_bit_range);
1927 :
1928 : /* Must not have redundant bindings. */
1929 2424 : auto &baseline_bv = get_baseline ().get_bits (bit_range);
1930 2424 : gcc_assert (&overlay_bv != &baseline_bv);
1931 :
1932 : /* The size of each bit_vector must match that of the bit
1933 : range it is bound to. */
1934 2424 : gcc_assert (&overlay_bv.get_size ()
1935 : == &bit_range.get_size ());
1936 2424 : }
1937 : }
1938 2424 : }
1939 :
1940 : const bit_vector &
1941 2911 : symbolic_bit_overlay::get_bits (const symbolic_bit_range &sym_bit_range) const
1942 : {
1943 : /* TODO: we currently ignore the baseline
1944 : should we be clobbering the baseline when we create this? */
1945 :
1946 2911 : auto iter = m_symbolic_range_map.find (sym_bit_range);
1947 2911 : if (iter != m_symbolic_range_map.end ())
1948 911 : return iter->second;
1949 :
1950 : /* TODO: check for crops, etc
1951 : if no intersection, return the baseline. */
1952 :
1953 2000 : auto &bv_mgr = get_bit_vector_manager ();
1954 2000 : return bv_mgr.get_unknown_bits (sym_bit_range.get_size ());
1955 : }
1956 :
1957 : void
1958 11 : symbolic_bit_overlay::print_dump_widget_label (pretty_printer *pp) const
1959 : {
1960 11 : pp_string (pp, "symbolic bit overlay");
1961 11 : }
1962 :
1963 : void
1964 11 : symbolic_bit_overlay::add_dump_widget_children (text_art::tree_widget &w,
1965 : node_dump_state &nds) const
1966 : {
1967 11 : using tree_widget = text_art::tree_widget;
1968 11 : std::unique_ptr<tree_widget> ranges_widget
1969 11 : (tree_widget::from_fmt (nds, nullptr, "symbolic ranges"));
1970 22 : for (auto iter : m_symbolic_range_map)
1971 : {
1972 11 : auto &bit_range = iter.first;
1973 11 : auto &bv = iter.second;
1974 22 : ranges_widget->add_child (bit_range.make_dump_widget (nds));
1975 22 : ranges_widget->add_child (bv.make_dump_widget (nds));
1976 : }
1977 22 : w.add_child (std::move (ranges_widget));
1978 22 : w.add_child (get_baseline ().make_dump_widget (nds, "baseline"));
1979 11 : }
1980 :
1981 : void
1982 1026 : symbolic_bit_overlay::accept_node_visitor (node_visitor &v) const
1983 : {
1984 1026 : if (v.visit_bit_contents (*this))
1985 : {
1986 1026 : get_baseline ().accept_node_visitor (v);
1987 2052 : for (auto iter : m_symbolic_range_map)
1988 : {
1989 1026 : auto &bit_range = iter.first;
1990 1026 : auto &bv = iter.second;
1991 1026 : bit_range.accept_node_visitor (v);
1992 1026 : bv.accept_node_visitor (v);
1993 : }
1994 : }
1995 1026 : }
1996 :
1997 : std::unique_ptr<json::object>
1998 0 : symbolic_bit_overlay::to_json () const
1999 : {
2000 0 : auto obj = make_json_obj ("symbolic_bit_overlay");
2001 0 : auto arr = std::make_unique<json::array> ();
2002 0 : for (auto iter : m_symbolic_range_map)
2003 : {
2004 0 : auto &bit_range = iter.first;
2005 0 : auto &bv = iter.second;
2006 0 : auto element = std::make_unique<json::object> ();
2007 0 : element->set ("range", bit_range.to_json ());
2008 0 : element->set ("bv", bv.to_json ());
2009 0 : arr->append (std::move (element));
2010 0 : }
2011 0 : obj->set ("concrete_range_map", std::move (arr));
2012 0 : obj->set ("baseline", get_baseline ().to_json ());
2013 0 : return obj;
2014 0 : }
2015 :
2016 : std::unique_ptr<diagnostics::markup::node>
2017 0 : symbolic_bit_overlay::make_markup_node (markup_context &) const
2018 : {
2019 0 : return diagnostics::markup::make_text_node ("symbolic_bit_overlay");
2020 : }
2021 :
2022 : string_scan
2023 96 : symbolic_bit_overlay::
2024 : scan_for_first_zero_byte (string_scan::byte_offset_type start_scan_offset) const
2025 : {
2026 182 : for (auto iter : m_symbolic_range_map)
2027 : {
2028 96 : auto &bit_range = iter.first;
2029 96 : auto &bv = iter.second;
2030 :
2031 96 : symbolic_byte_range byte_range;
2032 96 : if (!maybe_bytes_from_bits (bit_range, &byte_range))
2033 7 : return string_scan::cannot_scan (start_scan_offset);
2034 :
2035 89 : auto *concrete_start_offset
2036 89 : = byte_range.get_start_offset ().dyn_cast_concrete_scalar ();
2037 89 : if (!concrete_start_offset)
2038 3 : return string_scan::cannot_scan (start_scan_offset);
2039 86 : concrete_byte_offset start_of_range_byte_offset
2040 86 : = concrete_start_offset->get_concrete ();
2041 :
2042 86 : if (start_scan_offset < start_of_range_byte_offset)
2043 : {
2044 : /* TODO: look at underlying bit contents. */
2045 0 : return string_scan::cannot_scan (start_scan_offset);
2046 : }
2047 86 : else if (start_scan_offset == start_of_range_byte_offset)
2048 : {
2049 : /* Look within this bv. */
2050 86 : auto bv_result = bv.scan_for_first_zero_byte (0_bytes);
2051 86 : if (bv_result.m_state == string_scan::state::beyond_domain)
2052 : {
2053 : /* Try to carry on to the next range (or gap). */
2054 0 : auto *concrete_next_offset
2055 0 : = byte_range.get_next_offset ().dyn_cast_concrete_scalar ();
2056 0 : if (concrete_next_offset)
2057 0 : start_scan_offset = concrete_next_offset->get_concrete ();
2058 : else
2059 0 : return string_scan::cannot_scan (start_scan_offset);
2060 0 : continue;
2061 0 : }
2062 86 : }
2063 : else
2064 : /* We might be scannning within or after this overlay; give up. */
2065 0 : return string_scan::cannot_scan (start_scan_offset);
2066 86 : }
2067 :
2068 : // Beyond the end of the overlay ranges; look at underlying bit contents:
2069 86 : return get_baseline ().scan_for_first_zero_byte (start_scan_offset);
2070 : }
2071 :
2072 : void
2073 2944 : symbolic_bit_overlay::
2074 : get_representative_path_vars (const region_model *model,
2075 : value_set *visited,
2076 : const region *base_reg,
2077 : const svalue *sval,
2078 : tree desired_type,
2079 : logger *logger,
2080 : auto_vec<path_var> *out_pvs) const
2081 : {
2082 : /* Find if SVAL is present anywhere in m_symbolic_range_map. */
2083 5888 : for (auto iter : m_symbolic_range_map)
2084 : {
2085 2944 : auto &bit_range = iter.first;
2086 2944 : auto &bv = iter.second;
2087 :
2088 2944 : if (bit_vector_matches_sval_p (bv, *sval))
2089 : {
2090 : /* Found SVAL at bit_range relative to BASE_REG.
2091 : Try to convert that to a subregion, and from there
2092 : to a path_var. */
2093 74 : symbolic::memory_range mem_range (*base_reg,
2094 74 : bit_range);
2095 148 : if (auto *reg = model->maybe_get_region_for_mem_range
2096 74 : (mem_range,
2097 : desired_type,
2098 : logger))
2099 148 : if (path_var pv
2100 74 : = model->get_representative_path_var (reg,
2101 : visited,
2102 74 : logger))
2103 70 : append_pathvar_with_type (pv, desired_type, out_pvs);
2104 : }
2105 : }
2106 2944 : }
2107 :
2108 : const bit_contents &
2109 3367 : symbolic_bit_overlay::
2110 : poison_any_pointers_to_descendents (const region *reg,
2111 : enum poison_kind pkind) const
2112 : {
2113 3367 : symbolic_bit_overlay::key k {&get_baseline (), {}};
2114 :
2115 6734 : for (auto iter : m_symbolic_range_map)
2116 : {
2117 3367 : auto &bit_range = iter.first;
2118 3367 : const bit_vector *bv = &iter.second;
2119 :
2120 3367 : if (auto *bvs = bv->dyn_cast_bit_vector_from_svalue ())
2121 : {
2122 87 : if (auto *sym_ptr = bvs->get_svalue ().maybe_get_symbolic_pointer ())
2123 67 : if (should_poison_sym_ptr_p (*sym_ptr, *reg))
2124 : {
2125 0 : auto &bv_mgr = get_bit_vector_manager ();
2126 0 : bv = &bv_mgr.get_poisoned_bits (bv->get_size (), pkind);
2127 : }
2128 : }
2129 3367 : k.m_symbolic_range_map.insert ({bit_range, *bv});
2130 : }
2131 :
2132 3367 : return get_bit_contents_manager ().get_symbolic_bit_overlay (std::move (k),
2133 3367 : nullptr);
2134 3367 : }
2135 :
2136 : const bit_contents &
2137 11071 : symbolic_bit_overlay::purge_state_involving (const symbolic::node &node) const
2138 : {
2139 11071 : symbolic_bit_overlay::key k {&get_baseline (), {}};
2140 :
2141 22142 : for (auto iter : m_symbolic_range_map)
2142 : {
2143 11071 : auto &bit_range = iter.first;
2144 : // FIXME: also need to purge bit_range
2145 11071 : const bit_vector *bv = &iter.second;
2146 :
2147 11071 : if (bv->involves_p (node))
2148 : {
2149 3 : auto &bv_mgr = get_bit_vector_manager ();
2150 3 : bv = &bv_mgr.get_unknown_bits (bv->get_size ());
2151 : }
2152 11071 : k.m_symbolic_range_map.insert ({bit_range, *bv});
2153 : }
2154 :
2155 11071 : return get_bit_contents_manager ().get_symbolic_bit_overlay (std::move (k),
2156 11071 : nullptr);
2157 11071 : }
2158 :
2159 : bool
2160 1924 : symbolic_bit_overlay::bits_live_p (const symbolic::bit_vector_from_ubc &) const
2161 : {
2162 1924 : return false;
2163 : }
2164 :
2165 : iter_result
2166 83866 : symbolic_bit_overlay::
2167 : for_each_value (iter_result (*cb) (const symbolic::value_node &val,
2168 : void *user_data),
2169 : void *user_data) const
2170 : {
2171 83866 : if (get_baseline ().for_each_value (cb, user_data) == iter_result::stop)
2172 : return iter_result::stop;
2173 167732 : for (auto iter : m_symbolic_range_map)
2174 : {
2175 83866 : const bit_vector *bv = &iter.second;
2176 83866 : if (cb (*bv, user_data) == iter_result::stop)
2177 83866 : return iter_result::stop;
2178 : }
2179 : return iter_result::keep_going;
2180 : }
2181 :
2182 : // class offset_bit_contents : public bit_contents
2183 :
2184 : bool
2185 28 : offset_bit_contents::key::operator< (const key &other) const
2186 : {
2187 28 : if (int c = node::cmp (*m_inner_bc, *other.m_inner_bc))
2188 0 : return c < 0;
2189 28 : return node::cmp (*m_bit_offset, *other.m_bit_offset) < 0;
2190 : }
2191 :
2192 : complexity
2193 9 : offset_bit_contents::key::get_complexity () const
2194 : {
2195 9 : return complexity::from_pair (m_inner_bc->get_complexity (),
2196 9 : m_bit_offset->get_complexity ());
2197 : }
2198 :
2199 9 : offset_bit_contents::offset_bit_contents (node_manager &node_mgr,
2200 : const key &k)
2201 : : bit_contents (k.get_complexity (), node_mgr),
2202 9 : m_inner_bc (*k.m_inner_bc),
2203 9 : m_bit_offset (*k.m_bit_offset)
2204 : {
2205 9 : gcc_assert (!m_bit_offset.is_zero_p ());
2206 9 : gcc_assert (!m_inner_bc.dyn_cast_uniform_bit_contents ());
2207 :
2208 : /* No nesting. */
2209 9 : gcc_assert (!m_inner_bc.dyn_cast_offset_bit_contents ());
2210 9 : }
2211 :
2212 : const bit_vector &
2213 7 : offset_bit_contents::get_bits (const symbolic_bit_range &bit_range) const
2214 : {
2215 7 : symbolic_bit_range range_in_inner (bit_range.get_start_offset ()
2216 7 : + m_bit_offset,
2217 7 : bit_range.get_size ());
2218 7 : return m_inner_bc.get_bits (range_in_inner);
2219 : }
2220 :
2221 : void
2222 0 : offset_bit_contents::print_dump_widget_label (pretty_printer *pp) const
2223 : {
2224 0 : pp_string (pp, "offset_bit_contents");
2225 0 : }
2226 :
2227 : void
2228 0 : offset_bit_contents::add_dump_widget_children (text_art::tree_widget &w,
2229 : node_dump_state &nds) const
2230 : {
2231 0 : w.add_child (m_inner_bc.make_dump_widget (nds, "inner_bc"));
2232 0 : w.add_child (m_bit_offset.make_dump_widget (nds, "bit_offset"));
2233 0 : }
2234 :
2235 : void
2236 0 : offset_bit_contents::accept_node_visitor (node_visitor &v) const
2237 : {
2238 0 : if (v.visit_bit_contents (*this))
2239 : {
2240 0 : m_inner_bc.accept_node_visitor (v);
2241 0 : m_bit_offset.accept_node_visitor (v);
2242 : }
2243 0 : }
2244 :
2245 : std::unique_ptr<json::object>
2246 0 : offset_bit_contents::to_json () const
2247 : {
2248 0 : auto obj = make_json_obj ("offset_bit_contents");
2249 :
2250 0 : obj->set ("inner_bc", m_inner_bc.to_json ());
2251 0 : obj->set ("bit_offset", m_bit_offset.to_json ());
2252 :
2253 0 : return obj;
2254 : }
2255 :
2256 : std::unique_ptr<diagnostics::markup::node>
2257 0 : offset_bit_contents::make_markup_node (markup_context &) const
2258 : {
2259 0 : return diagnostics::markup::make_text_node ("offset_bit_contents");
2260 : }
2261 :
2262 : string_scan
2263 0 : offset_bit_contents::
2264 : scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset) const
2265 : {
2266 0 : concrete_bit_offset conc_bit_offset;
2267 0 : if (concrete_from_symbolic (m_bit_offset, &conc_bit_offset))
2268 : {
2269 0 : concrete_byte_offset conc_byte_offset;
2270 0 : if (maybe_bytes_from_bits (conc_bit_offset, &conc_byte_offset))
2271 : {
2272 0 : string_scan inner
2273 0 : = m_inner_bc.scan_for_first_zero_byte (start_byte_offset
2274 0 : + conc_byte_offset);
2275 0 : inner.m_byte_offset -= conc_byte_offset;
2276 0 : return inner;
2277 : }
2278 0 : }
2279 :
2280 0 : return string_scan::cannot_scan (start_byte_offset);
2281 0 : }
2282 :
2283 : void
2284 0 : offset_bit_contents::
2285 : get_representative_path_vars (const region_model *,
2286 : value_set *,
2287 : const region *,
2288 : const svalue *,
2289 : tree,
2290 : logger *,
2291 : auto_vec<path_var> *) const
2292 : {
2293 : // no-op
2294 0 : }
2295 :
2296 : const bit_contents &
2297 0 : offset_bit_contents::
2298 : poison_any_pointers_to_descendents (const region *reg,
2299 : enum poison_kind pkind) const
2300 : {
2301 0 : auto &poisoned_inner
2302 0 : = m_inner_bc.poison_any_pointers_to_descendents (reg, pkind);
2303 0 : return get_bit_contents_manager ().get_offset_bit_contents (poisoned_inner,
2304 0 : m_bit_offset);
2305 : }
2306 :
2307 : const bit_contents &
2308 0 : offset_bit_contents::purge_state_involving (const symbolic::node &n) const
2309 : {
2310 0 : auto &purged_inner = m_inner_bc.purge_state_involving (n);
2311 0 : return get_bit_contents_manager ().get_offset_bit_contents (purged_inner,
2312 0 : m_bit_offset);
2313 : }
2314 :
2315 : bool
2316 0 : offset_bit_contents::
2317 : bits_live_p (const symbolic::bit_vector_from_ubc &bv_from_ubc) const
2318 : {
2319 0 : return m_inner_bc.bits_live_p (bv_from_ubc);
2320 : }
2321 :
2322 : iter_result
2323 0 : offset_bit_contents::
2324 : for_each_value (iter_result (*cb) (const symbolic::value_node &val,
2325 : void *user_data),
2326 : void *user_data) const
2327 : {
2328 0 : return m_inner_bc.for_each_value (cb, user_data);
2329 : }
2330 :
2331 : /* offset(offset(bc, x), y) --> offset(bc, x + y). */
2332 :
2333 : const bit_contents *
2334 5 : offset_bit_contents::
2335 : maybe_fold_offset (const symbolic_bit_offset &bit_offset) const
2336 : {
2337 5 : return &(get_bit_contents_manager ()
2338 5 : .get_offset_bit_contents (m_inner_bc,
2339 5 : m_bit_offset + bit_offset));
2340 : }
2341 :
2342 : // class bit_contents_manager
2343 :
2344 4409 : bit_contents_manager::bit_contents_manager (node_manager &node_mgr)
2345 4409 : : m_node_mgr (node_mgr),
2346 4409 : m_uninit_contents (node_mgr),
2347 4409 : m_zero_contents (node_mgr)
2348 : {
2349 4409 : }
2350 :
2351 : const bit_contents &
2352 127920 : bit_contents_manager::get_untracked (value_set maybe_live)
2353 : {
2354 127920 : value_set canonical_vs;
2355 309835 : for (auto iter : maybe_live)
2356 181915 : if (untracked_bit_contents::track_value_liveness_p (*iter))
2357 157456 : canonical_vs.add (iter);
2358 :
2359 127920 : untracked_bit_contents::key k (std::move (canonical_vs));
2360 :
2361 127920 : auto iter = m_untracked_bit_contents.find (k);
2362 127920 : if (iter != m_untracked_bit_contents.end ())
2363 124500 : return *(iter->second);
2364 :
2365 3420 : auto p = std::make_unique<untracked_bit_contents> (m_node_mgr, k);
2366 3420 : auto &result = *p;
2367 3420 : m_untracked_bit_contents.insert ({k, std::move (p)});
2368 3420 : return result;
2369 131340 : }
2370 :
2371 : const bit_contents &
2372 305005 : bit_contents_manager::set_bits (const bit_contents &original,
2373 : const symbolic_bit_range &sym_bit_range,
2374 : const bit_vector &bv,
2375 : uncertainty_t *uncertainty)
2376 : {
2377 305005 : concrete_bit_range conc_bit_range;
2378 305005 : if (concrete_from_symbolic (sym_bit_range, &conc_bit_range))
2379 300534 : return set_bits (original, conc_bit_range, bv, uncertainty);
2380 :
2381 4471 : std::map<symbolic_bit_range, const bit_vector &> overlays;
2382 4471 : overlays.insert ({sym_bit_range, bv});
2383 4471 : symbolic_bit_overlay::key k {&original, std::move (overlays)};
2384 4471 : return get_symbolic_bit_overlay (std::move (k), uncertainty);
2385 4471 : }
2386 :
2387 : const bit_contents &
2388 300534 : bit_contents_manager::set_bits (const bit_contents &original,
2389 : const concrete_bit_range &conc_bit_range,
2390 : const bit_vector &bv,
2391 : uncertainty_t *uncertainty)
2392 : {
2393 300534 : if (auto *conc_overlay = original.dyn_cast_concrete_bit_overlay ())
2394 44501 : return conc_overlay->set_concrete_bits (conc_bit_range, bv);
2395 :
2396 256033 : std::map<concrete_bit_range, const bit_vector &> overlays
2397 256033 : = concrete_bit_overlay::canonicalize_new_bit_vec (conc_bit_range, bv);
2398 256033 : concrete_bit_overlay::key k {&original, std::move (overlays)};
2399 256033 : return get_concrete_bit_overlay (std::move (k), uncertainty);
2400 256033 : }
2401 :
2402 : const bit_contents &
2403 682223 : bit_contents_manager::
2404 : get_concrete_bit_overlay (concrete_bit_overlay::key k,
2405 : uncertainty_t *uncertainty)
2406 : {
2407 682223 : gcc_assert (k.m_baseline);
2408 :
2409 682223 : k.remove_redundant_bindings ();
2410 :
2411 682223 : if (k.m_concrete_range_map.size () == 0)
2412 3457 : return *k.m_baseline;
2413 :
2414 : /* Avoid nesting of overlays.
2415 : Any attempt to make a concrete_bit_overlay on top of another
2416 : concrete_bit_overlay should have been flattened by now. */
2417 678766 : gcc_assert (k.m_baseline->get_kind () != bit_contents::kind::concrete_overlay);
2418 678766 : if (k.m_baseline->get_kind () == bit_contents::kind::symbolic_overlay)
2419 : {
2420 72 : if (uncertainty)
2421 42 : uncertainty->add_bit_contents (*k.m_baseline);
2422 72 : value_set maybe_live = k.m_baseline->get_maybe_live_values ();
2423 72 : k.m_baseline = &get_untracked (std::move (maybe_live));
2424 72 : }
2425 :
2426 678766 : k.remove_redundant_bindings ();
2427 678766 : if (k.m_concrete_range_map.size () == 0)
2428 0 : return *k.m_baseline;
2429 :
2430 678766 : auto iter = m_concrete_bit_overlays.find (k);
2431 678766 : if (iter != m_concrete_bit_overlays.end ())
2432 600942 : return *(iter->second);
2433 :
2434 77824 : auto p = std::make_unique<concrete_bit_overlay> (k);
2435 77824 : auto &result = *p;
2436 77824 : m_concrete_bit_overlays.insert ({k, std::move (p)});
2437 77824 : return result;
2438 77824 : }
2439 :
2440 : const bit_contents &
2441 18943 : bit_contents_manager::
2442 : get_symbolic_bit_overlay (symbolic_bit_overlay::key k,
2443 : uncertainty_t *uncertainty)
2444 : {
2445 18943 : gcc_assert (k.m_baseline);
2446 :
2447 18943 : k.remove_redundant_bindings ();
2448 :
2449 18943 : if (k.m_symbolic_range_map.size () == 0)
2450 643 : return *k.m_baseline;
2451 :
2452 36403 : for (auto &iter : k.m_symbolic_range_map)
2453 : {
2454 18300 : auto &bit_range = iter.first;
2455 : /* If any of the bit ranges start at an unknown offset,
2456 : fall back to the whole bit contents being unknown. */
2457 18300 : if (bit_range.get_start_offset ().is_unknown_p ())
2458 : {
2459 197 : if (uncertainty)
2460 183 : uncertainty->add_bit_contents (*k.m_baseline);
2461 :
2462 197 : value_set maybe_live = k.m_baseline->get_maybe_live_values ();
2463 394 : for (auto &iter2 : k.m_symbolic_range_map)
2464 : {
2465 197 : auto &bv = iter2.second;
2466 197 : if (uncertainty)
2467 183 : uncertainty->on_maybe_bound_value (bv);
2468 197 : maybe_live.add (&bv);
2469 : }
2470 197 : return get_untracked (std::move (maybe_live));
2471 197 : }
2472 : }
2473 :
2474 : /* Avoid nesting of overlays. */
2475 18103 : if (k.m_baseline->get_kind () == bit_contents::kind::concrete_overlay
2476 18103 : || k.m_baseline->get_kind () == bit_contents::kind::symbolic_overlay)
2477 : {
2478 574 : if (uncertainty)
2479 412 : uncertainty->add_bit_contents (*k.m_baseline);
2480 574 : value_set maybe_live = k.m_baseline->get_maybe_live_values ();
2481 574 : k.m_baseline = &get_untracked (std::move (maybe_live));
2482 574 : }
2483 :
2484 18103 : k.remove_redundant_bindings ();
2485 :
2486 18103 : if (k.m_symbolic_range_map.size () == 0)
2487 0 : return *k.m_baseline;
2488 :
2489 : /* Any attempt to create more than one symbolic key ought to have been
2490 : folded into an "untracked" baseline by now. */
2491 18103 : gcc_assert (k.m_symbolic_range_map.size () == 1);
2492 :
2493 18103 : auto iter = m_symbolic_bit_overlays.find (k);
2494 18103 : if (iter != m_symbolic_bit_overlays.end ())
2495 15679 : return *(iter->second);
2496 :
2497 2424 : auto p = std::make_unique<symbolic_bit_overlay> (k);
2498 2424 : auto &result = *p;
2499 2424 : m_symbolic_bit_overlays.insert ({k, std::move (p)});
2500 2424 : return result;
2501 2424 : }
2502 :
2503 : /* Create a bit_contents that is uninitialized everywhere, apart from
2504 : bytes [0-sizeof(TREE_CST)), which are bound to TREE_CST's representation
2505 : on the target. */
2506 :
2507 : const bit_contents &
2508 0 : bit_contents_manager::make_bit_contents_for_constant (tree tree_cst)
2509 : {
2510 0 : auto &bv_mgr = m_node_mgr.get_bit_vector_manager ();
2511 0 : auto &bit_mgr = m_node_mgr.get_scalars ().get_bits ();
2512 0 : auto &bv = bv_mgr.get_bits_for_constant (tree_cst);
2513 :
2514 0 : return (get_uninitialized ()
2515 0 : .set_bits (symbolic_bit_range (bit_mgr.get_concrete (0_bits),
2516 0 : bv.get_size ()),
2517 : bv,
2518 0 : nullptr));
2519 : }
2520 :
2521 : const bit_contents &
2522 0 : bit_contents_manager::get_bit_contents_for_constant (tree tree_cst)
2523 : {
2524 0 : auto iter = m_bit_contents_for_constants.find (tree_cst);
2525 0 : if (iter != m_bit_contents_for_constants.end ())
2526 0 : return iter->second;
2527 :
2528 0 : auto &bc = make_bit_contents_for_constant (tree_cst);
2529 0 : m_bit_contents_for_constants.insert ({tree_cst, bc});
2530 0 : return bc;
2531 : }
2532 :
2533 : bool
2534 38148 : baseline_key::
2535 : region_has_meaningful_size_p (symbolic::node_manager &node_mgr) const
2536 : {
2537 38148 : if (m_base_reg->get_kind () == RK_SYMBOLIC)
2538 : {
2539 : /* We don't know the size of the underlying region:
2540 : "T *ptr" could be just one T, but could be an array
2541 : of T, or within an array of T. */
2542 : return false;
2543 : }
2544 :
2545 22276 : auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
2546 22276 : if (m_base_reg->maybe_get_bit_size (bit_mgr))
2547 22192 : return true;
2548 :
2549 : return false;
2550 : }
2551 :
2552 : std::unique_ptr<json::object>
2553 14 : baseline_key::to_json () const
2554 : {
2555 14 : auto obj = std::make_unique<json::object> ();
2556 14 : obj->set ("base_reg", m_base_reg->to_json ());
2557 14 : obj->set_string ("baseline_state", baseline_state_to_str (m_baseline_state));
2558 14 : return obj;
2559 : }
2560 :
2561 : const bit_contents &
2562 130809 : bit_contents_manager::make_baseline_contents (baseline_key k)
2563 : {
2564 130809 : if (!k.m_base_reg->can_have_initial_svalue_p ())
2565 100441 : return get_uninitialized ();
2566 :
2567 30368 : auto &rmm = m_node_mgr.get_svalue_manager ();
2568 30368 : switch (k.m_baseline_state)
2569 : {
2570 0 : default:
2571 0 : gcc_unreachable ();
2572 :
2573 1214 : case baseline_state::main:
2574 1214 : {
2575 1214 : if (auto *decl_reg = k.m_base_reg->dyn_cast_decl_region ())
2576 : {
2577 : /* Attempt to get the initializer value for base_reg as a
2578 : bit_contents. */
2579 789 : if (auto *bc = decl_reg->maybe_get_bit_contents_for_initializer (&rmm))
2580 : return *bc;
2581 : }
2582 : }
2583 : break;
2584 :
2585 : case baseline_state::after_main:
2586 : break;
2587 : }
2588 :
2589 30170 : if (k.region_has_meaningful_size_p (m_node_mgr))
2590 : {
2591 : /* Get or create a concrete_bit_overlay, with a baseline bit_vector
2592 : at [0, size), and uninitialized everywhere else. */
2593 22192 : auto &bv_mgr = m_node_mgr.get_bit_vector_manager ();
2594 22192 : auto &bit_mgr = m_node_mgr.get_scalars ().get_bits ();
2595 22192 : auto &baseline_bv
2596 22192 : = bv_mgr.get_baseline_bit_vector (*k.m_base_reg,
2597 : k.m_baseline_state);
2598 22192 : return (get_uninitialized ()
2599 22192 : .set_bits (symbolic_bit_range (bit_mgr.get_concrete (0_bits),
2600 44384 : baseline_bv.get_size ()),
2601 : baseline_bv,
2602 : nullptr));
2603 : }
2604 : else
2605 : {
2606 : /* Make a baseline_bit_contents. */
2607 7978 : auto bc
2608 7978 : = std::make_unique<baseline_bit_contents> (m_node_mgr, k);
2609 7978 : auto &result = *bc;
2610 7978 : m_unfoldable_bit_contents.push_back (std::move (bc));
2611 7978 : return result;
2612 7978 : }
2613 : }
2614 :
2615 : const bit_contents &
2616 2077083 : bit_contents_manager::
2617 : get_baseline_contents (const region &base_reg,
2618 : baseline_state bs)
2619 : {
2620 : /* Read-only var decls don't change,
2621 : so always use baseline_state::main for them. */
2622 2077083 : if (tree decl = base_reg.maybe_get_decl ())
2623 1731129 : if (VAR_P (decl) && TREE_READONLY (decl))
2624 : bs = baseline_state::main;
2625 :
2626 2077083 : baseline_key k {&base_reg, bs};
2627 2077083 : auto iter = m_baseline_contents.find (k);
2628 2077083 : if (iter != m_baseline_contents.end ())
2629 1946274 : return iter->second;
2630 :
2631 130809 : auto &bc = make_baseline_contents (k);
2632 130809 : m_baseline_contents.insert ({k, bc});
2633 130809 : return bc;
2634 : }
2635 :
2636 : const bit_contents &
2637 25532 : bit_contents_manager::
2638 : get_conjured_bit_contents (const region &base_reg,
2639 : const gimple *stmt,
2640 : const conjured_purge &p,
2641 : unsigned idx)
2642 : {
2643 25532 : const symbolic::conjured_bit_contents::key k (stmt, &base_reg, idx);
2644 25532 : auto iter = m_conjured_map.find (k);
2645 25532 : if (iter != m_conjured_map.end ())
2646 : {
2647 13321 : auto *bc = iter->second.get ();
2648 : /* We're reusing an existing conjured_bit_contents, perhaps from a
2649 : different state within this analysis, or perhaps from an earlier state
2650 : on this execution path. For the latter, purge any state involving the
2651 : "new" bit_contents from the current program_state. */
2652 13321 : p.purge (*bc);
2653 13321 : return *bc;
2654 : }
2655 12211 : auto bc = std::make_unique<symbolic::conjured_bit_contents> (m_node_mgr, k);
2656 12211 : auto &result = *bc.get ();
2657 12211 : m_conjured_map.insert ({k, std::move (bc)});
2658 12211 : return result;
2659 12211 : }
2660 :
2661 : #if CHECKING_P
2662 : const bit_contents &
2663 60 : bit_contents_manager::
2664 : get_named_test_bit_contents (std::string name)
2665 : {
2666 60 : auto obj_up = std::make_unique<named_test_bit_contents> (m_node_mgr,
2667 60 : std::move (name));
2668 60 : auto &result = *obj_up.get ();
2669 60 : m_unfoldable_bit_contents.push_back (std::move (obj_up));
2670 120 : return result;
2671 60 : }
2672 : #endif
2673 :
2674 : const bit_contents &
2675 373 : bit_contents_manager::
2676 : get_offset_bit_contents (const bit_contents &inner_bc,
2677 : const symbolic_bit_offset &bit_offset)
2678 : {
2679 : /* An offset of zero can always be ignored. */
2680 373 : if (bit_offset.is_zero_p ())
2681 : return inner_bc;
2682 :
2683 30 : if (auto *folded = inner_bc.maybe_fold_offset (bit_offset))
2684 : return *folded;
2685 :
2686 13 : const symbolic::offset_bit_contents::key k {&inner_bc, &bit_offset};
2687 13 : auto iter = m_offset_map.find (k);
2688 13 : if (iter != m_offset_map.end ())
2689 4 : return *(iter->second);
2690 :
2691 9 : auto bc = std::make_unique<symbolic::offset_bit_contents> (m_node_mgr, k);
2692 9 : auto &result = *bc.get ();
2693 9 : m_offset_map.insert ({k, std::move (bc)});
2694 9 : return result;
2695 9 : }
2696 :
2697 : } // namespace ana::symbolic
2698 :
2699 : #if CHECKING_P
2700 :
2701 : namespace selftest {
2702 :
2703 : static void
2704 4 : test_uninit ()
2705 : {
2706 4 : symbolic::node_manager mgr;
2707 4 : auto &bit_cont_mgr = mgr.get_bit_contents_manager ();
2708 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
2709 4 : auto &uninit_bc = bit_cont_mgr.get_uninitialized ();
2710 12 : ASSERT_SAME_SYMBOLIC_NODE
2711 : (uninit_bc.get_bytes (concrete_byte_range (0_bytes, 10_bytes)),
2712 : bv_mgr.get_uninitialized_bytes (10_bytes));
2713 4 : }
2714 :
2715 : static void
2716 4 : test_untracked ()
2717 : {
2718 4 : symbolic::node_manager mgr;
2719 4 : auto &bit_cont_mgr = mgr.get_bit_contents_manager ();
2720 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
2721 4 : auto &untracked_bc = bit_cont_mgr.get_untracked ({});
2722 12 : ASSERT_SAME_SYMBOLIC_NODE
2723 : (untracked_bc.get_bytes (concrete_byte_range (0_bytes, 10_bytes)),
2724 : bv_mgr.get_unknown_bytes (10_bytes));
2725 :
2726 4 : ASSERT_SAME_SYMBOLIC_NODE
2727 : (untracked_bc,
2728 : bit_cont_mgr.get_untracked ({}));
2729 :
2730 4 : auto &custom_byte_a = bv_mgr.get_named_test_bit_vector (8_bits,
2731 4 : "custom_byte_a");
2732 4 : auto &custom_byte_b = bv_mgr.get_named_test_bit_vector (8_bits,
2733 4 : "custom_byte_b");
2734 :
2735 4 : value_set maybe_live_a;
2736 4 : maybe_live_a.add (&custom_byte_a);
2737 :
2738 4 : value_set maybe_live_b;
2739 4 : maybe_live_b.add (&custom_byte_b);
2740 :
2741 4 : ASSERT_NE (maybe_live_a, maybe_live_b);
2742 :
2743 4 : value_set maybe_live_ab;
2744 4 : maybe_live_ab.add (&custom_byte_a);
2745 4 : maybe_live_ab.add (&custom_byte_b);
2746 :
2747 4 : value_set maybe_live_ba;
2748 4 : maybe_live_ba.add (&custom_byte_b);
2749 4 : maybe_live_ba.add (&custom_byte_a);
2750 :
2751 : // Insertion order shouldn't matter
2752 4 : ASSERT_EQ (maybe_live_ab, maybe_live_ba);
2753 :
2754 4 : ASSERT_DIFFERENT_SYMBOLIC_NODE
2755 : (untracked_bc,
2756 : bit_cont_mgr.get_untracked (maybe_live_a));
2757 :
2758 4 : ASSERT_SAME_SYMBOLIC_NODE
2759 : (bit_cont_mgr.get_untracked (maybe_live_a),
2760 : bit_cont_mgr.get_untracked (maybe_live_a));
2761 :
2762 4 : ASSERT_DIFFERENT_SYMBOLIC_NODE
2763 : (bit_cont_mgr.get_untracked (maybe_live_a),
2764 : bit_cont_mgr.get_untracked (maybe_live_b));
2765 :
2766 4 : ASSERT_SAME_SYMBOLIC_NODE
2767 : (bit_cont_mgr.get_untracked (maybe_live_ab),
2768 : bit_cont_mgr.get_untracked (maybe_live_ba));
2769 4 : }
2770 :
2771 : static void
2772 4 : test_all_zeros ()
2773 : {
2774 4 : symbolic::node_manager mgr;
2775 4 : auto &bit_cont_mgr = mgr.get_bit_contents_manager ();
2776 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
2777 4 : auto &all_zeros_bc = bit_cont_mgr.get_all_zeros ();
2778 12 : ASSERT_SAME_SYMBOLIC_NODE
2779 : (all_zeros_bc.get_bytes (concrete_byte_range (0_bytes, 1024_bytes)),
2780 : bv_mgr.get_all_zeros (1024_bytes));
2781 4 : }
2782 :
2783 : /* Simulation of "char buf[10];" */
2784 :
2785 : static void
2786 4 : test_static_sized_char_array ()
2787 : {
2788 4 : symbolic::node_manager mgr;
2789 4 : auto &bit_cont_mgr = mgr.get_bit_contents_manager ();
2790 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
2791 :
2792 4 : const symbolic::bit_contents *zeroed_buf = &bit_cont_mgr.get_all_zeros ();
2793 4 : const symbolic::bit_contents *uninit_buf = &bit_cont_mgr.get_uninitialized ();
2794 :
2795 4 : {
2796 12 : auto &bv = zeroed_buf->get_bytes (concrete_byte_range (0_bytes, 10_bytes));
2797 4 : ASSERT_SAME_SYMBOLIC_NODE (bv,
2798 : bv_mgr.get_all_zeros (10_bytes));
2799 : }
2800 :
2801 4 : {
2802 12 : auto &bv = uninit_buf->get_bytes (concrete_byte_range (0_bytes, 10_bytes));
2803 4 : ASSERT_SAME_SYMBOLIC_NODE (bv,
2804 : bv_mgr.get_uninitialized_bytes (10_bytes));
2805 : }
2806 :
2807 12 : auto set_abc0 = [] (const auto *buf)
2808 : {
2809 8 : buf = &buf->set_byte (0_bytes, 'a', nullptr);
2810 8 : buf = &buf->set_byte (1_byte, 'b', nullptr);
2811 8 : buf = &buf->set_byte (2_bytes, 'c', nullptr);
2812 8 : buf = &buf->set_byte (3_bytes, '\0', nullptr);
2813 8 : return buf;
2814 : };
2815 :
2816 4 : zeroed_buf = set_abc0 (zeroed_buf);
2817 4 : uninit_buf = set_abc0 (uninit_buf);
2818 :
2819 4 : zeroed_buf->to_json ();
2820 4 : uninit_buf->to_json ();
2821 :
2822 4 : {
2823 12 : auto &bv = zeroed_buf->get_bytes (concrete_byte_range (0_bytes, 10_bytes));
2824 4 : ASSERT_SAME_SYMBOLIC_NODE
2825 : (bv,
2826 : bv_mgr.get_concat_bits
2827 : ({&bv_mgr.get_uint8 ('a'),
2828 : &bv_mgr.get_uint8 ('b'),
2829 : &bv_mgr.get_uint8 ('c'),
2830 : &bv_mgr.get_all_zeros (7_bytes)}));
2831 : }
2832 4 : {
2833 12 : auto &bv = uninit_buf->get_bytes (concrete_byte_range (0_bytes, 10_bytes));
2834 4 : ASSERT_SAME_SYMBOLIC_NODE
2835 : (bv,
2836 : bv_mgr.get_concat_bits
2837 : ({&bv_mgr.get_uint8 ('a'),
2838 : &bv_mgr.get_uint8 ('b'),
2839 : &bv_mgr.get_uint8 ('c'),
2840 : &bv_mgr.get_uint8 (0),
2841 : &bv_mgr.get_uninitialized_bytes (6_bytes)}));
2842 : }
2843 :
2844 : /* Verify scanning for zero bytes. */
2845 4 : {
2846 : /* For byte offsets [0, 3), both should find the NUL at offset 3. */
2847 24 : for (concrete_byte_offset i = 0_bytes; i < 4_bytes; ++i)
2848 : {
2849 16 : ASSERT_EQ (zeroed_buf->scan_for_first_zero_byte (i),
2850 : string_scan::found_nul (3_bytes));
2851 16 : ASSERT_EQ (uninit_buf->scan_for_first_zero_byte (i),
2852 : string_scan::found_nul (3_bytes));
2853 4 : }
2854 :
2855 : /* Verify byte offsets outside that range (both negative and positive).
2856 : For zeroed_buf, we should find NUL at every offset.
2857 : For uninit_buf, we should report a problem at every offset. */
2858 4 : {
2859 : /* Negative byte offsets. */
2860 44 : for (concrete_byte_offset i = -10_bytes; i < 0_bytes; ++i)
2861 : {
2862 40 : ASSERT_EQ (zeroed_buf->scan_for_first_zero_byte (i),
2863 : string_scan::found_nul (i));
2864 40 : ASSERT_EQ (uninit_buf->scan_for_first_zero_byte (i),
2865 : string_scan::found_poison (i, poison_kind::uninit));
2866 4 : }
2867 32 : for (concrete_byte_offset i = 4_bytes; i < 10_bytes; ++i)
2868 : {
2869 24 : ASSERT_EQ (zeroed_buf->scan_for_first_zero_byte (i),
2870 : string_scan::found_nul (i));
2871 24 : ASSERT_EQ (uninit_buf->scan_for_first_zero_byte (i),
2872 : string_scan::found_poison (i, poison_kind::uninit));
2873 4 : }
2874 : }
2875 : }
2876 4 : }
2877 :
2878 : /* Construct a non-trivial bit_contents, then sample it as a bit_vector
2879 : at various ranges, including negative offsets. */
2880 :
2881 : static void
2882 4 : test_reading_nontrivial_bit_map ()
2883 : {
2884 4 : symbolic::node_manager mgr;
2885 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
2886 4 : auto &bc_mgr = mgr.get_bit_contents_manager ();
2887 :
2888 4 : auto &unbound = bc_mgr.get_named_test_bit_contents ("unbound");
2889 :
2890 : // Check reading from the baseline contents:
2891 20 : ASSERT_SAME_SYMBOLIC_NODE
2892 : (unbound.get_bytes (concrete_byte_range (0_bytes, 100_bytes)),
2893 : unbound.get_bytes (concrete_byte_range (0_bytes, 100_bytes)));
2894 :
2895 : /* Set up this binding:
2896 : | [-4]: 'x'
2897 : | [-3]: 'y'
2898 : | [-2]: 'z'
2899 : | [-1]: unbound
2900 : |[0 - 10): zero-filled (10 bytes)
2901 : | [10-16): unbound
2902 : | [16-32): 0xff-filled (16 bytes)
2903 : | [32): unbound
2904 : | [33]: 'a'
2905 : | [34): unbound
2906 : | [35]: 'b'
2907 : | [36): unbound
2908 : | [37]: 'c'
2909 : | [38]: 'c'
2910 : */
2911 4 : const symbolic::bit_contents *bmap = &unbound;
2912 4 : bmap = &bmap->set_byte (-4_bytes, 'x', nullptr);
2913 4 : bmap = &bmap->set_byte (-3_bytes, 'y', nullptr);
2914 4 : bmap = &bmap->set_byte (-2_bytes, 'z', nullptr);
2915 16 : bmap = &bmap->set_bytes (concrete_byte_range (0_bytes, 10_bytes),
2916 4 : bv_mgr.get_all_zeros (10_bytes),
2917 : nullptr);
2918 16 : bmap = &bmap->set_bytes (concrete_byte_range(16_bytes, 16_bytes),
2919 4 : bv_mgr.get_all_ones (16_bytes),
2920 : nullptr);
2921 4 : bmap = &bmap->set_byte (33_bytes, 'a', nullptr);
2922 4 : bmap = &bmap->set_byte (35_bytes, 'b', nullptr);
2923 4 : bmap = &bmap->set_byte (37_bytes, 'c', nullptr);
2924 4 : bmap = &bmap->set_byte (38_bytes, 'c', nullptr);
2925 :
2926 : // We should have a single concrete overlay over "unbound"
2927 4 : auto *conc_bit_overlay = bmap->dyn_cast_concrete_bit_overlay ();
2928 4 : ASSERT_NE (conc_bit_overlay, nullptr);
2929 4 : ASSERT_SAME_SYMBOLIC_NODE (conc_bit_overlay->get_baseline (),
2930 : unbound);
2931 :
2932 4 : bmap->to_json ();
2933 :
2934 : // Test individual bytes
2935 4 : {
2936 : /* Subroutines to determine if the initial/final bit of the byte at
2937 : the given offset is bound in conc_bit_overlay. */
2938 4 : auto initial_bit_offset_is_bound_p
2939 188 : = [conc_bit_overlay] (concrete_byte_offset byte_offset) -> bool
2940 : {
2941 188 : auto initial_bit_offset = bits_from_bytes (byte_offset);
2942 188 : return conc_bit_overlay->bit_offset_is_bound_p (initial_bit_offset);
2943 192 : };
2944 4 : auto final_bit_offset_is_bound_p
2945 8 : = [conc_bit_overlay] (concrete_byte_offset byte_offset) -> bool
2946 : {
2947 8 : auto initial_bit_offset = bits_from_bytes (byte_offset);
2948 8 : return conc_bit_overlay->bit_offset_is_bound_p
2949 8 : (initial_bit_offset + 7_bits);
2950 12 : };
2951 :
2952 : // A long way before the first binding:
2953 4 : ASSERT_FALSE (initial_bit_offset_is_bound_p (-100_bytes));
2954 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (-100_bytes),
2955 : unbound.get_byte (-100_bytes));
2956 :
2957 : // Immediately before the first binding:
2958 4 : ASSERT_FALSE (initial_bit_offset_is_bound_p (-5_bytes));
2959 4 : ASSERT_FALSE (final_bit_offset_is_bound_p (-5_bytes));
2960 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (-5_bytes),
2961 : unbound.get_byte (-5_bytes));
2962 :
2963 : // The xyz bindings:
2964 4 : ASSERT_TRUE (initial_bit_offset_is_bound_p (-4_bytes));
2965 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (-4_bytes),
2966 : bv_mgr.get_uint8 ('x'));
2967 :
2968 4 : ASSERT_TRUE (initial_bit_offset_is_bound_p (-3_bytes));
2969 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (-3_bytes),
2970 : bv_mgr.get_uint8 ('y'));
2971 :
2972 4 : ASSERT_TRUE (initial_bit_offset_is_bound_p (-2_bytes));
2973 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (-2_bytes),
2974 : bv_mgr.get_uint8 ('z'));
2975 :
2976 : // Immediately after the xyz bindings:
2977 4 : ASSERT_FALSE (initial_bit_offset_is_bound_p (-1_byte));
2978 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (-1_byte),
2979 : unbound.get_byte (-1_byte));
2980 :
2981 48 : for (auto i = 0_bytes; i < 10_bytes; ++i)
2982 : {
2983 40 : ASSERT_TRUE (initial_bit_offset_is_bound_p (i));
2984 40 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (i),
2985 : bv_mgr.get_uint8 (0));
2986 4 : }
2987 32 : for (auto i = 10_bytes; i < 16_bytes; ++i)
2988 : {
2989 24 : ASSERT_FALSE (initial_bit_offset_is_bound_p (i));
2990 24 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (i),
2991 : unbound.get_byte (i));
2992 4 : }
2993 72 : for (auto i = 16_bytes; i < 32_bytes; ++i)
2994 : {
2995 64 : ASSERT_TRUE (initial_bit_offset_is_bound_p (i));
2996 64 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (i),
2997 : bv_mgr.get_uint8 (0xff));
2998 4 : }
2999 :
3000 4 : ASSERT_FALSE (initial_bit_offset_is_bound_p (32_bytes));
3001 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (32_bytes),
3002 : unbound.get_byte (32_bytes));
3003 :
3004 4 : ASSERT_TRUE (initial_bit_offset_is_bound_p (33_bytes));
3005 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (33_bytes),
3006 : bv_mgr.get_uint8 ('a'));
3007 :
3008 4 : ASSERT_FALSE (initial_bit_offset_is_bound_p (34_bytes));
3009 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (34_bytes),
3010 : unbound.get_byte (34_bytes));
3011 :
3012 4 : ASSERT_TRUE (initial_bit_offset_is_bound_p (35_bytes));
3013 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (35_bytes),
3014 : bv_mgr.get_uint8 ('b'));
3015 :
3016 4 : ASSERT_FALSE (initial_bit_offset_is_bound_p (36_bytes));
3017 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (36_bytes),
3018 : unbound.get_byte (36_bytes));
3019 :
3020 4 : ASSERT_TRUE (initial_bit_offset_is_bound_p (37_bytes));
3021 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (37_bytes),
3022 : bv_mgr.get_uint8 ('c'));
3023 :
3024 4 : ASSERT_TRUE (initial_bit_offset_is_bound_p (38_bytes));
3025 4 : ASSERT_TRUE (final_bit_offset_is_bound_p (38_bytes));
3026 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (38_bytes),
3027 : bv_mgr.get_uint8 ('c'));
3028 :
3029 : // Immediately after the last binding:
3030 4 : ASSERT_FALSE (initial_bit_offset_is_bound_p (39_bytes));
3031 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (39_bytes),
3032 : unbound.get_byte (39_bytes));
3033 :
3034 : // A long way after the last binding:
3035 4 : ASSERT_FALSE (initial_bit_offset_is_bound_p (100_bytes));
3036 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (100_bytes),
3037 : unbound.get_byte (100_bytes));
3038 : }
3039 :
3040 : // Test ranges of bytes
3041 4 : {
3042 : /* Before the first binding. */
3043 20 : ASSERT_SAME_SYMBOLIC_NODE
3044 : (bmap->get_bytes (concrete_byte_range (-100_bytes, 10_bytes)),
3045 : unbound.get_bytes (concrete_byte_range (-100_bytes, 10_bytes)));
3046 :
3047 : /* Partial read of the zero bytes. */
3048 12 : ASSERT_SAME_SYMBOLIC_NODE
3049 : (bmap->get_bytes (concrete_byte_range (5_bytes, 2_bytes)),
3050 : bv_mgr.get_all_zeros (2_bytes));
3051 :
3052 : /* Test that the two neighboring 'c' chars are consolidated
3053 : when read as a bit vector. */
3054 12 : ASSERT_SAME_SYMBOLIC_NODE
3055 : (bmap->get_bytes (concrete_byte_range (37_bytes, 2_bytes)),
3056 : bv_mgr.get_repeated_bits (bv_mgr.get_uint8 ('c'), 2));
3057 :
3058 : /* After the last binding. */
3059 20 : ASSERT_SAME_SYMBOLIC_NODE
3060 : (bmap->get_bytes (concrete_byte_range (100_bytes, 10_bytes)),
3061 : unbound.get_bytes (concrete_byte_range (100_bytes, 10_bytes)));
3062 : }
3063 :
3064 : /* Verify scanning for NUL bytes. */
3065 4 : {
3066 : // A long way before the first binding:
3067 4 : ASSERT_EQ (bmap->scan_for_first_zero_byte (-100_bytes),
3068 : string_scan::cannot_scan (-100_bytes));
3069 :
3070 : // Immediately before the first binding:
3071 4 : ASSERT_EQ (bmap->scan_for_first_zero_byte (-5_bytes),
3072 : string_scan::cannot_scan (-5_bytes));
3073 :
3074 : // Scanning the xyz bindings should fail, at the "unbound" successor.
3075 16 : for (auto i = -4_bytes; i < -1_byte; ++i)
3076 12 : ASSERT_EQ (bmap->scan_for_first_zero_byte (i),
3077 4 : string_scan::cannot_scan (-1_byte));
3078 :
3079 : // Immediately after the xyz bindings:
3080 4 : ASSERT_EQ (bmap->scan_for_first_zero_byte (-1_byte),
3081 : string_scan::cannot_scan (-1_byte));
3082 :
3083 48 : for (auto i = 0_bytes; i < 10_bytes; ++i)
3084 40 : ASSERT_EQ (bmap->scan_for_first_zero_byte (i),
3085 4 : string_scan::found_nul (i));
3086 32 : for (auto i = 10_bytes; i < 16_bytes; ++i)
3087 24 : ASSERT_EQ (bmap->scan_for_first_zero_byte (i),
3088 4 : string_scan::cannot_scan (i));
3089 :
3090 : /* Scanning after that point should hit an unbound byte
3091 : and thus be unable to scan there. */
3092 :
3093 : // Scans that should hit the unbound byte 32:
3094 72 : for (auto i = 16_bytes; i < 32_bytes; ++i)
3095 64 : ASSERT_EQ (bmap->scan_for_first_zero_byte (i),
3096 4 : string_scan::cannot_scan (32_bytes));
3097 4 : ASSERT_EQ (bmap->scan_for_first_zero_byte (32_bytes),
3098 : string_scan::cannot_scan (32_bytes));
3099 :
3100 : // Scans that should hit the unbound byte 34:
3101 4 : ASSERT_EQ (bmap->scan_for_first_zero_byte (33_bytes),
3102 : string_scan::cannot_scan (34_bytes));
3103 4 : ASSERT_EQ (bmap->scan_for_first_zero_byte (34_bytes),
3104 : string_scan::cannot_scan (34_bytes));
3105 :
3106 : // Scans that should hit the unbound byte 36:
3107 4 : ASSERT_EQ (bmap->scan_for_first_zero_byte (35_bytes),
3108 : string_scan::cannot_scan (36_bytes));
3109 4 : ASSERT_EQ (bmap->scan_for_first_zero_byte (36_bytes),
3110 : string_scan::cannot_scan (36_bytes));
3111 :
3112 : // Scans that should hit the unbound bytes 39 onwards:
3113 4 : ASSERT_EQ (bmap->scan_for_first_zero_byte (37_bytes),
3114 : string_scan::cannot_scan (39_bytes));
3115 4 : ASSERT_EQ (bmap->scan_for_first_zero_byte (38_bytes),
3116 : string_scan::cannot_scan (39_bytes));
3117 4 : ASSERT_EQ (bmap->scan_for_first_zero_byte (39_bytes),
3118 : string_scan::cannot_scan (39_bytes));
3119 4 : ASSERT_EQ (bmap->scan_for_first_zero_byte (40_bytes),
3120 : string_scan::cannot_scan (40_bytes));
3121 4 : ASSERT_EQ (bmap->scan_for_first_zero_byte (100_bytes),
3122 : string_scan::cannot_scan (100_bytes));
3123 : }
3124 4 : }
3125 :
3126 : /* Test of two successive updates to a bitmap which don't overlap,
3127 : with a gap. */
3128 :
3129 : static void
3130 4 : test_update_no_overlap_with_gap ()
3131 : {
3132 4 : symbolic::node_manager mgr;
3133 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
3134 4 : auto &bc_mgr = mgr.get_bit_contents_manager ();
3135 :
3136 4 : auto &unbound = bc_mgr.get_named_test_bit_contents ("unbound");
3137 :
3138 4 : const symbolic::bit_contents *bmap = &unbound;
3139 :
3140 : /* Fill [20, 35) with a 15-byte custom bit vector. */
3141 4 : auto &first = bv_mgr.get_named_test_bit_vector (15_bytes, "first");
3142 12 : bmap = &bmap->set_bytes (concrete_byte_range (20_bytes, 15_bytes),
3143 : first, nullptr);
3144 12 : ASSERT_SAME_SYMBOLIC_NODE
3145 : (bmap->get_bytes (concrete_byte_range (20_bytes, 15_bytes)),
3146 : first);
3147 28 : ASSERT_SAME_SYMBOLIC_NODE
3148 : (bmap->get_bytes (concrete_byte_range (0_bytes, 100_bytes)),
3149 : bv_mgr.get_concat_bits
3150 : ({&unbound.get_bytes (concrete_byte_range (0_bytes, 20_bytes)),
3151 : &first,
3152 : &unbound.get_bytes (concrete_byte_range (35_bytes, 65_bytes))}));
3153 :
3154 : /* Fill [40, 90) with a second 50-byte custom vector.
3155 : They don't overlap, so this should give us:
3156 : [20, 35) : first
3157 : [40, 90) : second. */
3158 4 : auto &second = bv_mgr.get_named_test_bit_vector (50_bytes, "second");
3159 12 : bmap = &bmap->set_bytes (concrete_byte_range (40_bytes, 50_bytes),
3160 : second,
3161 : nullptr);
3162 4 : bmap->to_json ();
3163 :
3164 12 : ASSERT_SAME_SYMBOLIC_NODE
3165 : (bmap->get_bytes (concrete_byte_range (20_bytes, 15_bytes)),
3166 : first);
3167 12 : ASSERT_SAME_SYMBOLIC_NODE
3168 : (bmap->get_bytes (concrete_byte_range (40_bytes, 50_bytes)),
3169 : second);
3170 36 : ASSERT_SAME_SYMBOLIC_NODE
3171 : (bmap->get_bytes (concrete_byte_range (0_bytes, 100_bytes)),
3172 : bv_mgr.get_concat_bits
3173 : ({&unbound.get_bytes (concrete_byte_range (0_bytes, 20_bytes)),
3174 : &first,
3175 : &unbound.get_bytes (concrete_byte_range (35_bytes, 5_bytes)),
3176 : &second,
3177 : &unbound.get_bytes (concrete_byte_range (90_bytes, 10_bytes))}));
3178 4 : }
3179 :
3180 : /* Test of two successive updates to a bitmap which don't overlap,
3181 : but do touch. */
3182 :
3183 : static void
3184 4 : test_update_no_overlap_touching ()
3185 : {
3186 4 : symbolic::node_manager mgr;
3187 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
3188 4 : auto &bc_mgr = mgr.get_bit_contents_manager ();
3189 :
3190 4 : auto &unbound = bc_mgr.get_named_test_bit_contents ("unbound");
3191 :
3192 4 : const symbolic::bit_contents *bmap = &unbound;
3193 :
3194 : /* Starts as unbound. */
3195 20 : ASSERT_SAME_SYMBOLIC_NODE
3196 : (bmap->get_bytes (concrete_byte_range (0_bytes, 100_bytes)),
3197 : unbound.get_bytes (concrete_byte_range (0_bytes, 100_bytes)));
3198 :
3199 : /* Fill [20, 35) with a 15-byte custom bit vector. */
3200 4 : auto &first = bv_mgr.get_named_test_bit_vector (15_bytes, "first");
3201 12 : bmap = &bmap->set_bytes (concrete_byte_range (20_bytes, 15_bytes),
3202 : first,
3203 : nullptr);
3204 12 : ASSERT_SAME_SYMBOLIC_NODE
3205 : (bmap->get_bytes (concrete_byte_range (20_bytes, 15_bytes)),
3206 : first);
3207 28 : ASSERT_SAME_SYMBOLIC_NODE
3208 : (bmap->get_bytes (concrete_byte_range (0_bytes, 100_bytes)),
3209 : bv_mgr.get_concat_bits
3210 : ({&unbound.get_bytes (concrete_byte_range (0_bytes, 20_bytes)),
3211 : &first,
3212 : &unbound.get_bytes (concrete_byte_range (35_bytes, 65_bytes))}));
3213 :
3214 : /* Fill [35, 75) with with a second custom vector (40 bytes).
3215 : They don't overlap, so this should give us:
3216 : [20, 35) : first
3217 : [35, 75) : second. */
3218 4 : auto &second = bv_mgr.get_named_test_bit_vector (40_bytes, "second");
3219 12 : bmap = &bmap->set_bytes (concrete_byte_range (35_bytes, 40_bytes),
3220 : second,
3221 : nullptr);
3222 4 : bmap->to_json ();
3223 12 : ASSERT_SAME_SYMBOLIC_NODE
3224 : (bmap->get_bytes (concrete_byte_range (20_bytes, 15_bytes)),
3225 : first);
3226 12 : ASSERT_SAME_SYMBOLIC_NODE
3227 : (bmap->get_bytes (concrete_byte_range (35_bytes, 40_bytes)),
3228 : second);
3229 28 : ASSERT_SAME_SYMBOLIC_NODE
3230 : (bmap->get_bytes (concrete_byte_range (0_bytes, 100_bytes)),
3231 : bv_mgr.get_concat_bits
3232 : ({&unbound.get_bytes (concrete_byte_range (0_bytes, 20_bytes)),
3233 : &first,
3234 : &second,
3235 : &unbound.get_bytes (concrete_byte_range (75_bytes, 25_bytes))}));
3236 4 : }
3237 :
3238 : /* Consider:
3239 : | +------------------------------------+
3240 : | | old binding |
3241 : | +------------------------------------+
3242 : then writing to:
3243 : | +----------------------+
3244 : | | new binding |
3245 : | +----------------------+
3246 :
3247 : Verify that we "punch a hole" and fill it with the new binding:
3248 : | +------+----------------------+------+
3249 : | |prefix| new binding |suffix|
3250 : | +------+----------------------+------+
3251 : */
3252 :
3253 : static void
3254 4 : test_update_punching_a_hole ()
3255 : {
3256 4 : symbolic::node_manager mgr;
3257 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
3258 4 : auto &bc_mgr = mgr.get_bit_contents_manager ();
3259 :
3260 4 : auto &unbound = bc_mgr.get_named_test_bit_contents ("unbound");
3261 :
3262 4 : const symbolic::bit_contents *bmap = &unbound;
3263 :
3264 : /* Fill [20, 90) with a 70-byte custom bit vector. */
3265 4 : auto &first = bv_mgr.get_named_test_bit_vector (70_bytes, "first");
3266 12 : bmap = &bmap->set_bytes (concrete_byte_range (20_bytes, 70_bytes),
3267 : first,
3268 : nullptr);
3269 12 : ASSERT_SAME_SYMBOLIC_NODE
3270 : (bmap->get_bytes (concrete_byte_range (20_bytes, 70_bytes)),
3271 : first);
3272 28 : ASSERT_SAME_SYMBOLIC_NODE
3273 : (bmap->get_bytes (concrete_byte_range (0_bytes, 100_bytes)),
3274 : bv_mgr.get_concat_bits
3275 : ({&unbound.get_bytes (concrete_byte_range (0_bytes, 20_bytes)),
3276 : &first,
3277 : &unbound.get_bytes (concrete_byte_range (90_bytes, 10_bytes))}));
3278 :
3279 : /* Fill [25, 75) with a second bit vector (50 byte), punching a hole
3280 : in "first"
3281 : This should give us:
3282 : [20, 25) : first 5 bytes of first
3283 : [25, 75) : "second"
3284 : [75, 90) : last 15 bytes of first. */
3285 4 : auto &second = bv_mgr.get_named_test_bit_vector (50_bytes, "second");
3286 12 : bmap = &bmap->set_bytes (concrete_byte_range (25_bytes, 50_bytes),
3287 : second,
3288 : nullptr);
3289 : // Test what's now in the range that "first" was stored to:
3290 12 : ASSERT_SAME_SYMBOLIC_NODE
3291 : (bmap->get_bytes (concrete_byte_range (20_bytes, 70_bytes)),
3292 : bv_mgr.get_concat_bits
3293 : ({&first.get_prefix (5_bytes),
3294 : &second,
3295 : &first.get_suffix (15_bytes)}));
3296 : // Test what's in the range that "second" was stored to:
3297 12 : ASSERT_SAME_SYMBOLIC_NODE
3298 : (bmap->get_bytes (concrete_byte_range (25_bytes, 50_bytes)),
3299 : second);
3300 : // Test everything:
3301 28 : ASSERT_SAME_SYMBOLIC_NODE
3302 : (bmap->get_bytes (concrete_byte_range (0_bytes, 100_bytes)),
3303 : bv_mgr.get_concat_bits
3304 : ({&unbound.get_bytes (concrete_byte_range (0_bytes, 20_bytes)),
3305 : &first.get_prefix (5_bytes),
3306 : &second,
3307 : &first.get_suffix (15_bytes),
3308 : &unbound.get_bytes (concrete_byte_range (90_bytes, 10_bytes))}));
3309 4 : }
3310 :
3311 : /* Verify the effect of a pair of overwrites to the same range. */
3312 :
3313 : static void
3314 4 : test_update_full_overwrite ()
3315 : {
3316 4 : symbolic::node_manager mgr;
3317 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
3318 4 : auto &bc_mgr = mgr.get_bit_contents_manager ();
3319 :
3320 4 : auto &unbound = bc_mgr.get_named_test_bit_contents ("unbound");
3321 :
3322 4 : const symbolic::bit_contents *bmap = &unbound;
3323 :
3324 : /* Fill [20, 90) with a 70-byte custom bit vector. */
3325 4 : auto &first = bv_mgr.get_named_test_bit_vector (70_bytes, "first");
3326 12 : bmap = &bmap->set_bytes (concrete_byte_range (20_bytes, 70_bytes),
3327 : first,
3328 : nullptr);
3329 12 : ASSERT_SAME_SYMBOLIC_NODE
3330 : (bmap->get_bytes (concrete_byte_range (20_bytes, 70_bytes)),
3331 : first);
3332 28 : ASSERT_SAME_SYMBOLIC_NODE
3333 : (bmap->get_bytes (concrete_byte_range (0_bytes, 100_bytes)),
3334 : bv_mgr.get_concat_bits
3335 : ({&unbound.get_bytes (concrete_byte_range (0_bytes, 20_bytes)),
3336 : &first,
3337 : &unbound.get_bytes (concrete_byte_range (90_bytes, 10_bytes))}));
3338 :
3339 : /* Overwrite it with a different 70-byte custom bit vector. */
3340 4 : auto &second = bv_mgr.get_named_test_bit_vector (70_bytes, "second");
3341 12 : bmap = &bmap->set_bytes (concrete_byte_range (20_bytes, 70_bytes),
3342 : second,
3343 : nullptr);
3344 12 : ASSERT_SAME_SYMBOLIC_NODE
3345 : (bmap->get_bytes (concrete_byte_range (20_bytes, 70_bytes)),
3346 : second);
3347 28 : ASSERT_SAME_SYMBOLIC_NODE
3348 : (bmap->get_bytes (concrete_byte_range (0_bytes, 100_bytes)),
3349 : bv_mgr.get_concat_bits
3350 : ({&unbound.get_bytes (concrete_byte_range (0_bytes, 20_bytes)),
3351 : &second,
3352 : &unbound.get_bytes (concrete_byte_range (90_bytes, 10_bytes))}));
3353 4 : }
3354 :
3355 : /* Verify the correct handling of this pair of writes:
3356 : | +-----------------------+
3357 : | |first |
3358 : | +-----------------------+
3359 : | +----------------------+
3360 : | | second |
3361 : | +----------------------+
3362 :
3363 : We should end up with:
3364 : | +------+----------------------+
3365 : | |prefix| second |
3366 : | +------+----------------------+
3367 : */
3368 :
3369 : static void
3370 4 : test_update_overlap_with_prefix ()
3371 : {
3372 4 : symbolic::node_manager mgr;
3373 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
3374 4 : auto &bc_mgr = mgr.get_bit_contents_manager ();
3375 :
3376 4 : auto &unbound = bc_mgr.get_named_test_bit_contents ("unbound");
3377 :
3378 4 : const symbolic::bit_contents *bmap = &unbound;
3379 :
3380 : /* Fill [20, 90) with a 70-byte custom bit vector. */
3381 4 : auto &first = bv_mgr.get_named_test_bit_vector (70_bytes, "first");
3382 12 : bmap = &bmap->set_bytes (concrete_byte_range (20_bytes, 70_bytes),
3383 : first,
3384 : nullptr);
3385 12 : ASSERT_SAME_SYMBOLIC_NODE
3386 : (bmap->get_bytes (concrete_byte_range (20_bytes, 70_bytes)),
3387 : first);
3388 28 : ASSERT_SAME_SYMBOLIC_NODE
3389 : (bmap->get_bytes (concrete_byte_range (0_bytes, 100_bytes)),
3390 : bv_mgr.get_concat_bits
3391 : ({&unbound.get_bytes (concrete_byte_range (0_bytes, 20_bytes)),
3392 : &first,
3393 : &unbound.get_bytes (concrete_byte_range (90_bytes, 10_bytes))}));
3394 :
3395 : /* Fill [30, 95) with a second bvec.
3396 : This should give us:
3397 : [20, 30) : first 10 bytes of first
3398 : [30, 95): second. */
3399 4 : auto &second = bv_mgr.get_named_test_bit_vector (65_bytes, "second");
3400 12 : bmap = &bmap->set_bytes (concrete_byte_range (30_bytes, 65_bytes),
3401 : second,
3402 : nullptr);
3403 : // Test what's now in the range that "first" was stored to:
3404 12 : ASSERT_SAME_SYMBOLIC_NODE
3405 : (bmap->get_bytes (concrete_byte_range (20_bytes, 70_bytes)),
3406 : bv_mgr.get_concat_bits
3407 : ({&first.get_prefix (10_bytes),
3408 : &second.get_prefix (60_bytes)}));
3409 : // Test what's in the range that "second" was stored to:
3410 12 : ASSERT_SAME_SYMBOLIC_NODE
3411 : (bmap->get_bytes (concrete_byte_range (30_bytes, 65_bytes)),
3412 : second);
3413 : // Test everything:
3414 28 : ASSERT_SAME_SYMBOLIC_NODE
3415 : (bmap->get_bytes (concrete_byte_range (0_bytes, 100_bytes)),
3416 : bv_mgr.get_concat_bits
3417 : ({&unbound.get_bytes (concrete_byte_range (0_bytes, 20_bytes)),
3418 : &first.get_prefix (10_bytes),
3419 : &second,
3420 : &unbound.get_bytes (concrete_byte_range (95_bytes, 5_bytes))}));
3421 4 : }
3422 :
3423 : /* Verify the correct handling of this pair of writes:
3424 : | +-----------------------+
3425 : | |first |
3426 : | +-----------------------+
3427 : | +----------------------+
3428 : | | second |
3429 : | +----------------------+
3430 :
3431 : We should end up with:
3432 : | +----------------------+------+
3433 : | | second |suffix|
3434 : | +----------------------+------+
3435 : */
3436 :
3437 : static void
3438 4 : test_update_overlap_with_suffix ()
3439 : {
3440 4 : symbolic::node_manager mgr;
3441 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
3442 4 : auto &bc_mgr = mgr.get_bit_contents_manager ();
3443 :
3444 4 : auto &unbound = bc_mgr.get_named_test_bit_contents ("unbound");
3445 :
3446 4 : const symbolic::bit_contents *bmap = &unbound;
3447 :
3448 : /* Fill [20, 90) with a 70-byte custom bit vector. */
3449 4 : auto &first = bv_mgr.get_named_test_bit_vector (70_bytes, "first");
3450 12 : bmap = &bmap->set_bytes (concrete_byte_range (20_bytes, 70_bytes),
3451 : first,
3452 : nullptr);
3453 12 : ASSERT_SAME_SYMBOLIC_NODE
3454 : (bmap->get_bytes (concrete_byte_range (20_bytes, 70_bytes)),
3455 : first);
3456 28 : ASSERT_SAME_SYMBOLIC_NODE
3457 : (bmap->get_bytes (concrete_byte_range (0_bytes, 100_bytes)),
3458 : bv_mgr.get_concat_bits
3459 : ({&unbound.get_bytes (concrete_byte_range (0_bytes, 20_bytes)),
3460 : &first,
3461 : &unbound.get_bytes (concrete_byte_range (90_bytes, 10_bytes))}));
3462 :
3463 : /* Fill [5, 70) with a second bvec.
3464 : This should give us:
3465 : [5, 70) : second.
3466 : [70, 90): last 20 bytes of first. */
3467 4 : auto &second = bv_mgr.get_named_test_bit_vector (65_bytes, "second");
3468 12 : bmap = &bmap->set_bytes (concrete_byte_range (5_bytes, 65_bytes),
3469 : second,
3470 : nullptr);
3471 :
3472 : // Test what's now in the range that "first" was stored to:
3473 12 : ASSERT_SAME_SYMBOLIC_NODE
3474 : (bmap->get_bytes (concrete_byte_range (20_bytes, 70_bytes)),
3475 : bv_mgr.get_concat_bits
3476 : ({&second.get_suffix (50_bytes),
3477 : &first.get_suffix (20_bytes)}));
3478 : // Test what's in the range that "second" was stored to:
3479 12 : ASSERT_SAME_SYMBOLIC_NODE
3480 : (bmap->get_bytes (concrete_byte_range (5_bytes, 65_bytes)),
3481 : second);
3482 : // Test everything:
3483 28 : ASSERT_SAME_SYMBOLIC_NODE
3484 : (bmap->get_bytes (concrete_byte_range (0_bytes, 100_bytes)),
3485 : bv_mgr.get_concat_bits
3486 : ({&unbound.get_bytes (concrete_byte_range (0_bytes, 5_bytes)),
3487 : &second,
3488 : &first.get_suffix (20_bytes),
3489 : &unbound.get_bytes (concrete_byte_range (90_bytes, 10_bytes))}));
3490 4 : }
3491 :
3492 : /* Verify the correct handling of this bit_map:
3493 : | +-------+ +-------+ +-------+ +-------+ +-------+
3494 : | | A | | B | | C | | D | | E |
3495 : | +-------+ +-------+ +-------+ +-------+ +-------+
3496 : when overwritten with:
3497 : | +----------------------+
3498 : | | F |
3499 : | +----------------------+
3500 :
3501 : We should end up with:
3502 : | +-------+ +---+----------------------+----+ +-------+
3503 : | | A | | B'| F | D' | | E |
3504 : | +-------+ +---+----------------------+----+ +-------+
3505 : */
3506 :
3507 : static void
3508 4 : test_update_multiple_overlaps ()
3509 : {
3510 4 : symbolic::node_manager mgr;
3511 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
3512 4 : auto &bc_mgr = mgr.get_bit_contents_manager ();
3513 :
3514 4 : auto &unbound = bc_mgr.get_named_test_bit_contents ("unbound");
3515 :
3516 4 : const symbolic::bit_contents *bmap = &unbound;
3517 :
3518 : /* Populate it with:
3519 : [10,15): A
3520 : [20,30): B
3521 : [40,60): C
3522 : [70,80): D
3523 : [90,95): E. */
3524 4 : auto &a = bv_mgr.get_named_test_bit_vector (5_bytes, "A");
3525 12 : bmap = &bmap->set_bytes (concrete_byte_range (10_bytes, 5_bytes),
3526 : a, nullptr);
3527 4 : auto &b = bv_mgr.get_named_test_bit_vector (10_bytes, "B");
3528 12 : bmap = &bmap->set_bytes (concrete_byte_range (20_bytes, 10_bytes),
3529 : b, nullptr);
3530 4 : auto &c = bv_mgr.get_named_test_bit_vector (20_bytes, "C");
3531 12 : bmap = &bmap->set_bytes (concrete_byte_range (40_bytes, 20_bytes),
3532 : c, nullptr);
3533 4 : auto &d = bv_mgr.get_named_test_bit_vector (10_bytes, "D");
3534 12 : bmap = &bmap->set_bytes (concrete_byte_range (70_bytes, 10_bytes),
3535 : d, nullptr);
3536 4 : auto &e = bv_mgr.get_named_test_bit_vector (5_bytes, "E");
3537 12 : bmap = &bmap->set_bytes (concrete_byte_range (90_bytes, 5_bytes),
3538 : e, nullptr);
3539 :
3540 60 : ASSERT_SAME_SYMBOLIC_NODE
3541 : (bmap->get_bytes (concrete_byte_range (0_bytes, 100_bytes)),
3542 : bv_mgr.get_concat_bits
3543 : ({&unbound.get_bytes (concrete_byte_range (0_bytes, 10_bytes)),
3544 : &a,
3545 : &unbound.get_bytes (concrete_byte_range (15_bytes, 5_bytes)),
3546 : &b,
3547 : &unbound.get_bytes (concrete_byte_range (30_bytes, 10_bytes)),
3548 : &c,
3549 : &unbound.get_bytes (concrete_byte_range (60_bytes, 10_bytes)),
3550 : &d,
3551 : &unbound.get_bytes (concrete_byte_range (80_bytes, 10_bytes)),
3552 : &e,
3553 : &unbound.get_bytes (concrete_byte_range (95_bytes, 5_bytes))}));
3554 :
3555 : /* Overwrite [25, 75) with F. */
3556 4 : auto &f = bv_mgr.get_named_test_bit_vector (50_bytes, "F");
3557 12 : bmap = &bmap->set_bytes (concrete_byte_range (25_bytes, 50_bytes),
3558 : f, nullptr);
3559 :
3560 44 : ASSERT_SAME_SYMBOLIC_NODE
3561 : (bmap->get_bytes (concrete_byte_range (0_bytes, 100_bytes)),
3562 : bv_mgr.get_concat_bits
3563 : ({&unbound.get_bytes (concrete_byte_range (0_bytes, 10_bytes)),
3564 : &a,
3565 : &unbound.get_bytes (concrete_byte_range (15_bytes, 5_bytes)),
3566 : &b.get_prefix (5_bytes),
3567 : &f,
3568 : &d.get_suffix (5_bytes),
3569 : &unbound.get_bytes (concrete_byte_range (80_bytes, 10_bytes)),
3570 : &e,
3571 : &unbound.get_bytes (concrete_byte_range (95_bytes, 5_bytes))}));
3572 4 : }
3573 :
3574 : static void
3575 4 : test_uint32 ()
3576 : {
3577 4 : symbolic::node_manager mgr;
3578 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
3579 4 : auto &bc_mgr = mgr.get_bit_contents_manager ();
3580 4 : auto &rmm = mgr.get_region_model_manager ();
3581 :
3582 4 : auto &unbound = bc_mgr.get_named_test_bit_contents ("unbound");
3583 :
3584 4 : const symbolic::bit_contents *bmap = &unbound;
3585 :
3586 16 : bmap = &bmap->set_bytes (concrete_byte_range (0_bytes, 4_bytes),
3587 4 : bv_mgr.get_all_zeros (32_bits),
3588 : nullptr);
3589 :
3590 4 : auto &zero_byte = bv_mgr.get_uint8 (0);
3591 :
3592 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (-1_byte),
3593 : unbound.get_byte (-1_byte));
3594 :
3595 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (0_bytes),
3596 : zero_byte);
3597 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (1_byte),
3598 : zero_byte);
3599 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (2_bytes),
3600 : zero_byte);
3601 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (3_bytes),
3602 : zero_byte);
3603 :
3604 4 : ASSERT_SAME_SYMBOLIC_NODE (bmap->get_byte (4_bytes),
3605 : unbound.get_byte (4_bytes));
3606 :
3607 : // Read the zero, with a gap at both start and end:
3608 28 : ASSERT_SAME_SYMBOLIC_NODE
3609 : (bmap->get_bytes (concrete_byte_range (-2_bytes, 8_bytes)),
3610 : bv_mgr.get_concat_bits
3611 : ({&unbound.get_bytes (concrete_byte_range (-2_bytes, 2_bytes)),
3612 : &bv_mgr.get_all_zeros (4_bytes),
3613 : &unbound.get_bytes (concrete_byte_range (4_bytes, 2_bytes))}));
3614 :
3615 : // Read the zero bytes as an uint32_t svalue.
3616 4 : {
3617 12 : auto &bvec = bmap->get_bytes (concrete_byte_range (0_bytes, 4_bytes));
3618 4 : auto &sval = *rmm.get_svalue_from_bit_vector (uint32_type_node, bvec);
3619 4 : ASSERT_SAME_SYMBOLIC_NODE
3620 : (sval,
3621 : *rmm.get_or_create_int_cst (uint32_type_node, 0));
3622 : }
3623 :
3624 : // Store (uint32_t)42, and try reading it back.
3625 4 : {
3626 4 : auto &int_42 = *rmm.get_or_create_int_cst (uint32_type_node, 42);
3627 12 : bmap = &bmap->set_bytes (concrete_byte_range (0_bytes, 4_bytes),
3628 : bv_mgr.get_bit_vector_from_svalue (int_42),
3629 : nullptr);
3630 :
3631 12 : auto &bvec = bmap->get_bytes (concrete_byte_range (0_bytes, 4_bytes));
3632 4 : auto &sval = *rmm.get_svalue_from_bit_vector (uint32_type_node, bvec);
3633 4 : ASSERT_SAME_SYMBOLIC_NODE (sval, int_42);
3634 : }
3635 4 : }
3636 :
3637 : static void
3638 48 : assert_byte_eq (const ::selftest::location &loc,
3639 : const symbolic::bit_contents *bmap,
3640 : concrete_byte_offset byte_offset,
3641 : uint8_t expected_value,
3642 : symbolic::node_manager &mgr)
3643 : {
3644 48 : auto &rmm = mgr.get_region_model_manager ();
3645 48 : auto &actual_bvec = bmap->get_byte (byte_offset);
3646 48 : auto &actual_sval
3647 48 : = *rmm.get_svalue_from_bit_vector (unsigned_char_type_node, actual_bvec);
3648 48 : auto &expected_sval
3649 48 : = *rmm.get_or_create_int_cst (unsigned_char_type_node, expected_value);
3650 48 : ASSERT_SAME_SYMBOLIC_NODE_AT (loc, actual_sval, expected_sval);
3651 48 : }
3652 :
3653 : #define ASSERT_BYTE_EQ(BMAP, BYTE_OFFSET, EXPECTED_VALUE, NODE_MGR) \
3654 : SELFTEST_BEGIN_STMT \
3655 : assert_byte_eq (SELFTEST_LOCATION, (BMAP), (BYTE_OFFSET), \
3656 : (EXPECTED_VALUE), (NODE_MGR)); \
3657 : SELFTEST_END_STMT
3658 :
3659 : /* Consider these 12 bytes:
3660 :
3661 : struct foo {
3662 : uint32_t x;
3663 : uint32_t y;
3664 : char str[]
3665 : } f = {0x00000042, 0x12345678, "abc"};
3666 :
3667 : where we thus have:
3668 :
3669 : uint32_t x : 0x00000042
3670 : uint32_t y : 0x12345678
3671 : char str[] : "abc\0"
3672 :
3673 : +------------------------------+--------------------------------------------+
3674 : | Field: | Bytes: |
3675 : | +--------+-----------------+-----------------+
3676 : | | | Big-endian | Little-endian |
3677 : +------+----------+------------+--------+-----+-----------|-----+-----------+
3678 : | name | type | value | offset | hex | binary | hex | binary |
3679 : +------+----------+------------+--------+-----+-----------|-----+-----------+
3680 : | x | uint32_t | 0x00000042 | [0] | 00 | 0000 0000 | 42 | 0100 0010 |
3681 : | | | | [1] | 00 | 0000 0000 | 00 | 0000 0000 |
3682 : | | | | [2] | 00 | 0000 0000 | 00 | 0000 0000 |
3683 : | | | | [3] | 42 | 0100 0010 | 00 | 0000 0000 |
3684 : +------+----------+------------+--------+-----+-----------|-----+-----------+
3685 : | y | uint32_t | 0x12345678 | [4] | 12 | 0001 0010 | 78 | 0111 1000 |
3686 : | | | | [5] | 34 | 0011 0100 | 56 | 0101 0110 |
3687 : | | | | [6] | 56 | 0101 0110 | 34 | 0011 0100 |
3688 : | | | | [7] | 78 | 0111 1000 | 12 | 0001 0010 |
3689 : +------+----------+------------+--------+-----+-----------+-----+-----------+
3690 : | str | char[] | "abc\0" | [8] | 61 | 0110 0001 | 61 | 0110 0001 |
3691 : | | | | [9] | 62 | 0110 0010 | 62 | 0110 0010 |
3692 : | | | | [10] | 63 | 0110 0011 | 63 | 0110 0011 |
3693 : | | | | [11] | 00 | 0000 0000 | 00 | 0000 0000 |
3694 : +------+----------+------------+--------+-----+-----------+-----+-----------+
3695 :
3696 : Verify that we can store/retrieve these values, and then try type-punning
3697 : it all to bytes as per the target's endianness. */
3698 :
3699 : static void
3700 4 : test_endianness ()
3701 : {
3702 4 : symbolic::node_manager mgr;
3703 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
3704 4 : auto &bc_mgr = mgr.get_bit_contents_manager ();
3705 4 : auto &rmm = mgr.get_region_model_manager ();
3706 :
3707 4 : auto &unbound = bc_mgr.get_named_test_bit_contents ("unbound");
3708 :
3709 4 : const symbolic::bit_contents *bmap = &unbound;
3710 :
3711 : // Populate bmap as above.
3712 4 : auto &int_0x42 = *rmm.get_or_create_int_cst (uint32_type_node, 0x42);
3713 4 : bmap = &bmap->set_bytes
3714 12 : (concrete_byte_range (0_bytes, 4_bytes),
3715 : bv_mgr.get_bit_vector_from_svalue (int_0x42),
3716 : nullptr);
3717 4 : auto &int_0x12345678
3718 4 : = *rmm.get_or_create_int_cst (uint32_type_node, 0x12345678);
3719 4 : bmap = &bmap->set_bytes
3720 12 : (concrete_byte_range (4_bytes, 4_bytes),
3721 : bv_mgr.get_bit_vector_from_svalue (int_0x12345678),
3722 : nullptr);
3723 4 : bmap = &bmap->set_byte (8_bytes, 'a', nullptr);
3724 4 : bmap = &bmap->set_byte (9_bytes, 'b', nullptr);
3725 4 : bmap = &bmap->set_byte (10_bytes, 'c', nullptr);
3726 4 : bmap = &bmap->set_byte (11_bytes, 0, nullptr);
3727 :
3728 : // Try reading the values back, using the types we used when setting them
3729 4 : {
3730 4 : {
3731 12 : auto &bvec = bmap->get_bytes (concrete_byte_range (0_bytes, 4_bytes));
3732 4 : auto &sval = *rmm.get_svalue_from_bit_vector (uint32_type_node, bvec);
3733 4 : ASSERT_SAME_SYMBOLIC_NODE (sval, int_0x42);
3734 : }
3735 4 : {
3736 12 : auto &bvec = bmap->get_bytes (concrete_byte_range (4_bytes, 4_bytes));
3737 4 : auto &sval = *rmm.get_svalue_from_bit_vector (uint32_type_node, bvec);
3738 4 : ASSERT_SAME_SYMBOLIC_NODE (sval, int_0x12345678);
3739 : }
3740 4 : ASSERT_BYTE_EQ (bmap, 8_bytes, 'a', mgr);
3741 4 : ASSERT_BYTE_EQ (bmap, 9_bytes, 'b', mgr);
3742 4 : ASSERT_BYTE_EQ (bmap, 10_bytes, 'c', mgr);
3743 4 : ASSERT_BYTE_EQ (bmap, 11_bytes, 0, mgr);
3744 : }
3745 :
3746 : // Try type-punning the uint32_t fields to bytes
3747 4 : {
3748 4 : if (BYTES_BIG_ENDIAN)
3749 : {
3750 : /* Big-endian. */
3751 : ASSERT_BYTE_EQ (bmap, 0_bytes, 0x00, mgr);
3752 : ASSERT_BYTE_EQ (bmap, 1_byte, 0x00, mgr);
3753 : ASSERT_BYTE_EQ (bmap, 2_bytes, 0x00, mgr);
3754 : ASSERT_BYTE_EQ (bmap, 3_bytes, 0x42, mgr);
3755 :
3756 : ASSERT_BYTE_EQ (bmap, 4_bytes, 0x12, mgr);
3757 : ASSERT_BYTE_EQ (bmap, 5_bytes, 0x34, mgr);
3758 : ASSERT_BYTE_EQ (bmap, 6_bytes, 0x56, mgr);
3759 : ASSERT_BYTE_EQ (bmap, 7_bytes, 0x78, mgr);
3760 : }
3761 : else
3762 : {
3763 : /* Little-endian. */
3764 4 : if (!WORDS_BIG_ENDIAN)
3765 : {
3766 4 : ASSERT_BYTE_EQ (bmap, 0_bytes, 0x42, mgr);
3767 4 : ASSERT_BYTE_EQ (bmap, 1_byte, 0x00, mgr);
3768 4 : ASSERT_BYTE_EQ (bmap, 2_bytes, 0x00, mgr);
3769 4 : ASSERT_BYTE_EQ (bmap, 3_bytes, 0x00, mgr);
3770 :
3771 4 : ASSERT_BYTE_EQ (bmap, 4_bytes, 0x78, mgr);
3772 4 : ASSERT_BYTE_EQ (bmap, 5_bytes, 0x56, mgr);
3773 4 : ASSERT_BYTE_EQ (bmap, 6_bytes, 0x34, mgr);
3774 4 : ASSERT_BYTE_EQ (bmap, 7_bytes, 0x12, mgr);
3775 : }
3776 : }
3777 : }
3778 :
3779 : // Try scanning for zero bytes
3780 4 : if (BYTES_BIG_ENDIAN)
3781 : {
3782 : /* Big-endian. */
3783 : /* First 3 bytes are all zero. */
3784 : for (auto i = 0_bytes; i < 3_bytes; ++i)
3785 : ASSERT_EQ (bmap->scan_for_first_zero_byte (i),
3786 : string_scan::found_nul (i));
3787 : /* Then non-zero until byte 11. */
3788 : for (auto i = 4_bytes; i < 11_bytes; ++i)
3789 : ASSERT_EQ (bmap->scan_for_first_zero_byte (i),
3790 : string_scan::found_nul (11_bytes));
3791 : }
3792 : else
3793 : {
3794 : /* Little-endian. */
3795 4 : if (!WORDS_BIG_ENDIAN)
3796 : {
3797 : /* First byte is non-zero (42). */
3798 4 : ASSERT_EQ (bmap->scan_for_first_zero_byte (0_bytes),
3799 : string_scan::found_nul (1_byte));
3800 : /* Then 3 zero bytes. */
3801 20 : for (auto i = 1_byte; i < 4_bytes; ++i)
3802 12 : ASSERT_EQ (bmap->scan_for_first_zero_byte (i),
3803 4 : string_scan::found_nul (i));
3804 : /* Then non-zero until byte 11. */
3805 36 : for (auto i = 4_bytes; i < 11_bytes; ++i)
3806 28 : ASSERT_EQ (bmap->scan_for_first_zero_byte (i),
3807 4 : string_scan::found_nul (11_bytes));
3808 : }
3809 : }
3810 4 : }
3811 :
3812 : /* Consider:
3813 : | struct foo {
3814 : | uint32_t x;
3815 : | uint32_t y;
3816 : | } f;
3817 : | f.x = 10;
3818 : | f.y = 42;
3819 : Verify that we canonicalize this as two adjacent bindings of
3820 : bit_vectors, rather than one binding to a concat bit_vector. */
3821 :
3822 : static void
3823 4 : test_canonicalize_concat ()
3824 : {
3825 4 : symbolic::node_manager mgr;
3826 4 : auto &rmm = mgr.get_region_model_manager ();
3827 4 : auto &int_10 = *rmm.get_or_create_int_cst (uint32_type_node, 10);
3828 4 : auto &int_42 = *rmm.get_or_create_int_cst (uint32_type_node, 42);
3829 :
3830 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
3831 4 : auto &bv_10 = bv_mgr.get_bit_vector_from_svalue (int_10);
3832 4 : auto &bv_42 = bv_mgr.get_bit_vector_from_svalue (int_42);
3833 :
3834 4 : auto &bc_mgr = mgr.get_bit_contents_manager ();
3835 4 : auto &unbound = bc_mgr.get_named_test_bit_contents ("unbound");
3836 :
3837 : /* Approach A: create it as two 4-byte bindings. */
3838 4 : const symbolic::bit_contents *bmap_a = &unbound;
3839 12 : bmap_a = &bmap_a->set_bytes (concrete_byte_range (0_bytes, 4_bytes),
3840 : bv_10, nullptr);
3841 12 : bmap_a = &bmap_a->set_bytes (concrete_byte_range(4_bytes, 4_bytes),
3842 : bv_42, nullptr);
3843 :
3844 : /* Approach B: create it as one 8-byte binding. */
3845 4 : const symbolic::bit_contents *bmap_b = &unbound;
3846 4 : auto &concat_bv
3847 4 : = bv_mgr.get_concat_bits ({&bv_10, &bv_42});
3848 12 : bmap_b = &bmap_b->set_bytes (concrete_byte_range (0_bytes, 8_bytes),
3849 : concat_bv, nullptr);
3850 :
3851 : /* Verify that they are canonicalized to the same symbol. */
3852 4 : ASSERT_SAME_SYMBOLIC_NODE (*bmap_a, *bmap_b);
3853 :
3854 : /* Verify that internally we used approach A. */
3855 4 : ASSERT_EQ (bmap_a->dyn_cast_concrete_bit_overlay ()->size (), 2);
3856 4 : }
3857 :
3858 : /* Consider a map of (10 bytes of zeros) then (5 bytes of zeros)
3859 : as opposed to a map of (15 bytes of zeros). */
3860 :
3861 : static void
3862 4 : test_consolidation ()
3863 : {
3864 4 : symbolic::node_manager mgr;
3865 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
3866 4 : auto &bc_mgr = mgr.get_bit_contents_manager ();
3867 :
3868 4 : auto &unbound = bc_mgr.get_named_test_bit_contents ("unbound");
3869 :
3870 : /* Approach A: create it as two adjacent bindings. */
3871 4 : const symbolic::bit_contents *bmap_a = &unbound;
3872 16 : bmap_a = &bmap_a->set_bytes (concrete_byte_range (0_bytes, 10_bytes),
3873 4 : bv_mgr.get_all_zeros (10_bytes),
3874 : nullptr);
3875 16 : bmap_a = &bmap_a->set_bytes (concrete_byte_range(10_bytes, 5_bytes),
3876 4 : bv_mgr.get_all_zeros (5_bytes),
3877 : nullptr);
3878 :
3879 : /* Approach B: create it as one binding. */
3880 4 : const symbolic::bit_contents *bmap_b = &unbound;
3881 16 : bmap_b = &bmap_b->set_bytes (concrete_byte_range (0_bytes, 15_bytes),
3882 4 : bv_mgr.get_all_zeros (15_bytes),
3883 : nullptr);
3884 :
3885 : /* Verify that they are canonicalized to the same symbolic node. */
3886 4 : ASSERT_SAME_SYMBOLIC_NODE (*bmap_a, *bmap_b);
3887 :
3888 : /* Verify that internally we used approach B. */
3889 4 : ASSERT_EQ (bmap_a->dyn_cast_concrete_bit_overlay ()->size (), 1);
3890 4 : }
3891 :
3892 : /* Verify that we canonicalize redundant bindings of bit ranges
3893 : when building concrete and symbolic overlays. */
3894 :
3895 : static void
3896 4 : test_redundant_bindings ()
3897 : {
3898 4 : symbolic::node_manager mgr;
3899 4 : auto &bit_contents_mgr = mgr.get_bit_contents_manager ();
3900 4 : auto &bv_mgr = mgr.get_bit_vector_manager ();
3901 4 : auto &byte_mgr = mgr.get_scalars ().get_bytes ();
3902 :
3903 4 : auto &zero_everywhere = bit_contents_mgr.get_all_zeros ();
3904 4 : auto &untracked_bc = bit_contents_mgr.get_untracked ({});
3905 :
3906 4 : const symbolic_byte_size &one_byte
3907 4 : = symbolic_from_concrete (1_byte, byte_mgr);
3908 :
3909 4 : auto &zero_byte = bv_mgr.get_uint8 (0);
3910 4 : auto &custom_byte_a = bv_mgr.get_named_test_bit_vector (8_bits,
3911 4 : "custom_byte_a");
3912 4 : auto &custom_byte_b = bv_mgr.get_named_test_bit_vector (8_bits,
3913 4 : "custom_byte_b");
3914 4 : auto &unknown_byte = bv_mgr.get_unknown_bytes (1_byte);
3915 :
3916 4 : auto &kilobyte_of_zeros
3917 12 : = untracked_bc.set_bytes (concrete_byte_range (0_bytes, 1024_bytes),
3918 4 : bv_mgr.get_all_zeros (1024_bytes),
3919 : nullptr);
3920 :
3921 4 : auto &offset_x = byte_mgr.get_named_test_scalar ("x");
3922 4 : auto &offset_y = byte_mgr.get_named_test_scalar ("y");
3923 4 : auto one_byte_at_offset_x = symbolic_byte_range (offset_x, one_byte);
3924 4 : auto one_byte_at_offset_y = symbolic_byte_range (offset_y, one_byte);
3925 :
3926 : /* Concrete bit ranges. */
3927 12 : ASSERT_SAME_SYMBOLIC_NODE
3928 : (untracked_bc.set_bytes (concrete_byte_range (0_bytes, 1_byte),
3929 : unknown_byte,
3930 : nullptr),
3931 : untracked_bc);
3932 12 : ASSERT_SAME_SYMBOLIC_NODE
3933 : (zero_everywhere.set_bytes (concrete_byte_range (0_bytes, 1_byte),
3934 : zero_byte,
3935 : nullptr),
3936 : zero_everywhere);
3937 :
3938 : /* 1024 zero bytes; redundantly writing a zero into it at offset 16 ought to
3939 : canonicalized to the same representation. */
3940 12 : ASSERT_SAME_SYMBOLIC_NODE
3941 : (kilobyte_of_zeros.set_bytes (concrete_byte_range (16_bytes, 1_byte),
3942 : zero_byte,
3943 : nullptr),
3944 : kilobyte_of_zeros);
3945 : /* Writing a redundant value matching the baseline should split
3946 : the binding. */
3947 28 : ASSERT_SAME_SYMBOLIC_NODE
3948 : (kilobyte_of_zeros.set_bytes (concrete_byte_range (512_bytes, 1_byte),
3949 : unknown_byte,
3950 : nullptr),
3951 : untracked_bc
3952 : .set_bytes (concrete_byte_range (0_bytes, 512_bytes),
3953 : bv_mgr.get_all_zeros (512_bytes),
3954 : nullptr)
3955 : .set_bytes (concrete_byte_range (513_bytes, 511_bytes),
3956 : bv_mgr.get_all_zeros (511_bytes),
3957 : nullptr));
3958 : /* Writes to outside the bound range that match the baseline also ought
3959 : to be canonicalized away. */
3960 12 : ASSERT_SAME_SYMBOLIC_NODE
3961 : (kilobyte_of_zeros.set_bytes (concrete_byte_range (4096_bytes, 1_byte),
3962 : unknown_byte,
3963 : nullptr),
3964 : kilobyte_of_zeros);
3965 :
3966 : /* Symbolic start offsets. */
3967 :
3968 : /* Unknown start offsets. */
3969 4 : auto one_byte_at_unknown_offset
3970 4 : = symbolic_byte_range (byte_mgr.get_unknown (), one_byte);
3971 4 : ASSERT_SAME_SYMBOLIC_NODE
3972 : (untracked_bc.set_bytes (one_byte_at_unknown_offset,
3973 : unknown_byte,
3974 : nullptr),
3975 : untracked_bc);
3976 4 : ASSERT_SAME_SYMBOLIC_NODE
3977 : (zero_everywhere.set_bytes (one_byte_at_unknown_offset,
3978 : zero_byte,
3979 : nullptr),
3980 : zero_everywhere);
3981 :
3982 : /* Symbolic write on top of symbolic binding on top of "untracked". */
3983 4 : {
3984 4 : auto &zero_at_x = untracked_bc.set_bytes (one_byte_at_offset_x,
3985 : zero_byte,
3986 : nullptr);
3987 4 : auto &result = zero_at_x.set_bytes (one_byte_at_offset_y, custom_byte_a,
3988 : nullptr);
3989 : /* We should have the last bound bit_vec, on top of
3990 : "untracked-with-A-maybe-live". */
3991 4 : value_set maybe_live;
3992 4 : maybe_live.add (&zero_byte);
3993 4 : ASSERT_SAME_SYMBOLIC_NODE
3994 : (result,
3995 : bit_contents_mgr.get_untracked (maybe_live)
3996 : .set_bytes (one_byte_at_offset_y,
3997 : custom_byte_a,
3998 : nullptr));
3999 4 : }
4000 :
4001 : /* Symbolic write on top of symbolic binding on top of "zero". */
4002 4 : {
4003 4 : auto &custom_at_x = zero_everywhere.set_bytes (one_byte_at_offset_x,
4004 : custom_byte_a,
4005 : nullptr);
4006 4 : auto &result = custom_at_x.set_bytes (one_byte_at_offset_y, custom_byte_b,
4007 : nullptr);
4008 : /* We should have the last bound bit_vec, on top of
4009 : "untracked, with custom_byte_a maybe-live". */
4010 4 : value_set maybe_live;
4011 4 : maybe_live.add (&custom_byte_a);
4012 4 : ASSERT_SAME_SYMBOLIC_NODE
4013 : (result,
4014 : bit_contents_mgr.get_untracked (maybe_live)
4015 : .set_bytes (one_byte_at_offset_y,
4016 : custom_byte_b,
4017 : nullptr));
4018 4 : }
4019 :
4020 : /* Concrete write on top of symbolic binding. */
4021 4 : {
4022 4 : auto &custom_at_x = zero_everywhere.set_bytes (one_byte_at_offset_x,
4023 : custom_byte_a,
4024 : nullptr);
4025 12 : auto &result = custom_at_x.set_bytes (concrete_byte_range (0_bytes, 1_byte),
4026 : custom_byte_b,
4027 : nullptr);
4028 : /* We should have the last bound bit_vec, on top of
4029 : "untracked, with custom_byte_a maybe-live". */
4030 4 : value_set maybe_live;
4031 4 : maybe_live.add (&custom_byte_a);
4032 12 : ASSERT_SAME_SYMBOLIC_NODE
4033 : (result,
4034 : bit_contents_mgr.get_untracked (maybe_live)
4035 : .set_bytes (concrete_byte_range (0_bytes, 1_byte),
4036 : custom_byte_b,
4037 : nullptr));
4038 4 : }
4039 4 : }
4040 :
4041 : static void
4042 4 : test_offset_bit_contents ()
4043 : {
4044 4 : symbolic::node_manager node_mgr;
4045 4 : auto &bit_contents_mgr = node_mgr.get_bit_contents_manager ();
4046 4 : auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
4047 :
4048 4 : symbolic::named_test_bit_contents placeholder_bc
4049 4 : (node_mgr, "placeholder_bc");
4050 :
4051 4 : auto &x_bits = bit_mgr.get_named_test_scalar ("x");
4052 4 : auto &y_bits = bit_mgr.get_named_test_scalar ("y");
4053 :
4054 : /* Verify that we fold away zero offsets. */
4055 4 : {
4056 4 : auto &zero_offset = bit_mgr.get_concrete (0_bits);
4057 4 : ASSERT_SAME_SYMBOLIC_NODE
4058 : (placeholder_bc,
4059 : bit_contents_mgr.get_offset_bit_contents
4060 : (placeholder_bc,
4061 : zero_offset));
4062 : }
4063 :
4064 : /* Verify that we fold away offsets of the various uniform_bit_contents
4065 : subclasses. */
4066 4 : {
4067 4 : ASSERT_SAME_SYMBOLIC_NODE
4068 : (bit_contents_mgr.get_untracked ({}),
4069 : bit_contents_mgr.get_offset_bit_contents
4070 : (bit_contents_mgr.get_untracked ({}),
4071 : x_bits));
4072 4 : ASSERT_SAME_SYMBOLIC_NODE
4073 : (bit_contents_mgr.get_uninitialized (),
4074 : bit_contents_mgr.get_offset_bit_contents
4075 : (bit_contents_mgr.get_uninitialized (),
4076 : x_bits));
4077 4 : ASSERT_SAME_SYMBOLIC_NODE
4078 : (bit_contents_mgr.get_all_zeros (),
4079 : bit_contents_mgr.get_offset_bit_contents
4080 : (bit_contents_mgr.get_all_zeros (),
4081 : x_bits));
4082 : }
4083 :
4084 : /* Verify the not-folded case. */
4085 4 : auto &offset_bc = bit_contents_mgr.get_offset_bit_contents (placeholder_bc,
4086 : x_bits);
4087 4 : {
4088 4 : auto *as_offset_bc = offset_bc.dyn_cast_offset_bit_contents ();
4089 4 : ASSERT_NE (as_offset_bc, nullptr);
4090 4 : ASSERT_SAME_SYMBOLIC_NODE (as_offset_bc->get_inner_bit_contents (),
4091 : placeholder_bc);
4092 4 : ASSERT_SAME_SYMBOLIC_NODE (as_offset_bc->get_bit_offset (),
4093 : x_bits);
4094 :
4095 4 : ASSERT_SAME_SYMBOLIC_NODE
4096 : (offset_bc.get_byte (10_bytes),
4097 : placeholder_bc.get_bits
4098 : (symbolic_bit_range (bit_mgr.get_concrete (bits_from_bytes (10_bytes))
4099 : + x_bits,
4100 : bit_mgr.get_concrete (8_bits))));
4101 : }
4102 :
4103 : /* Verify that offset-of-offset folds to sum of offsets. */
4104 4 : ASSERT_SAME_SYMBOLIC_NODE
4105 : (bit_contents_mgr.get_offset_bit_contents (offset_bc,
4106 : y_bits),
4107 : bit_contents_mgr.get_offset_bit_contents (placeholder_bc,
4108 : x_bits + y_bits));
4109 4 : }
4110 :
4111 : /* Consider:
4112 : | struct str {
4113 : | uint32_t m_len;
4114 : | char m_buf[];
4115 : | } *s;
4116 : |
4117 : | s->m_len = n;
4118 : | memcpy (s->m_buf, src, n);
4119 : | s->m_buf[n] = '\0'; */
4120 :
4121 : static void
4122 4 : test_string_with_trailing_array ()
4123 : {
4124 4 : symbolic::node_manager node_mgr;
4125 4 : auto &bv_mgr = node_mgr.get_bit_vector_manager ();
4126 4 : auto &bc_mgr = node_mgr.get_bit_contents_manager ();
4127 4 : auto &byte_mgr = node_mgr.get_scalars ().get_bytes ();
4128 :
4129 4 : auto &unbound = bc_mgr.get_named_test_bit_contents ("unbound");
4130 4 : const symbolic::bit_contents *bmap = &unbound;
4131 :
4132 4 : placeholder_svalue n_sval
4133 4 : (node_mgr.alloc_node_id (), uint32_type_node, "n");
4134 4 : auto &n_bytes = byte_mgr.get_scalar_from_svalue (n_sval);
4135 4 : auto &src_bv = bv_mgr.get_named_test_bit_vector (n_bytes, "src");
4136 :
4137 : /* "s->m_len = n;" */
4138 12 : bmap = &bmap->set_bytes (concrete_byte_range (0_bytes, 4_bytes),
4139 : bv_mgr.get_bit_vector_from_svalue (n_sval),
4140 : nullptr);
4141 :
4142 : /* "memcpy (s->m_buf, src, n);" */
4143 4 : bmap = &bmap->set_bytes (symbolic_byte_range (byte_mgr.get_concrete (4_bytes),
4144 4 : n_bytes),
4145 : src_bv,
4146 : nullptr);
4147 :
4148 : /* "s->m_buf[n] = '\0';" */
4149 12 : bmap = &bmap->set_bytes (symbolic_byte_range (byte_mgr.get_concrete (4_bytes)
4150 : + n_bytes,
4151 12 : byte_mgr.get_concrete (1_byte)),
4152 : bv_mgr.get_uint8 (0),
4153 : nullptr);
4154 4 : }
4155 :
4156 :
4157 : /* Run all of the selftests within this file. */
4158 :
4159 : void
4160 4 : analyzer_symbolic_bit_contents_cc_tests ()
4161 : {
4162 4 : test_uninit ();
4163 4 : test_untracked ();
4164 4 : test_all_zeros ();
4165 : // rule of 5 ?
4166 4 : test_static_sized_char_array ();
4167 4 : test_reading_nontrivial_bit_map ();
4168 4 : test_update_no_overlap_with_gap ();
4169 4 : test_update_no_overlap_touching ();
4170 4 : test_update_punching_a_hole ();
4171 4 : test_update_full_overwrite ();
4172 4 : test_update_overlap_with_prefix ();
4173 4 : test_update_overlap_with_suffix ();
4174 4 : test_update_multiple_overlaps ();
4175 4 : test_uint32 ();
4176 4 : test_endianness ();
4177 4 : test_canonicalize_concat ();
4178 4 : test_consolidation ();
4179 4 : test_redundant_bindings ();
4180 4 : test_offset_bit_contents ();
4181 4 : test_string_with_trailing_array ();
4182 4 : }
4183 :
4184 : } // namespace selftest
4185 :
4186 : #endif /* CHECKING_P */
4187 :
4188 : } // namespace ana
4189 :
4190 : #endif /* #if ENABLE_ANALYZER */
|