LCOV - code coverage report
Current view: top level - gcc/analyzer - symbolic-bit-contents.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 91.1 % 1770 1613
Test Date: 2026-11-14 16:39:50 Functions: 84.1 % 189 159
Legend: Lines:     hit not hit

            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 */
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.