LCOV - code coverage report
Current view: top level - gcc/analyzer - symbolic-bit-vectors.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 93.6 % 1980 1853
Test Date: 2026-11-14 16:39:50 Functions: 85.6 % 201 172
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Symbolic vectors of bits e.g. "(buf_a[0-10) + buf_b[0-len) + (0b * 8))"
       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 "fold-const.h"
      25              : #include "tm.h"
      26              : 
      27              : #include "diagnostics/markup.h"
      28              : #include "selftest.h"
      29              : 
      30              : #include "analyzer/symbolic-bit-vectors.h"
      31              : #include "analyzer/region-model.h"
      32              : #include "analyzer/liveness-context.h"
      33              : #include "analyzer/analyzer-selftests.h"
      34              : 
      35              : #if ENABLE_ANALYZER
      36              : 
      37              : namespace ana {
      38              : 
      39              : // TODO: move this
      40              : /* class conjured_purge.  */
      41              : 
      42              : /* Purge state relating to BV.  */
      43              : 
      44              : void
      45        11572 : conjured_purge::purge (const symbolic::conjured_bit_vector &bv) const
      46              : {
      47        11572 :   m_model->purge_state_involving (bv, m_ctxt);
      48        11572 : }
      49              : 
      50              : /* Purge state relating to BV.  */
      51              : 
      52              : void
      53        13321 : conjured_purge::purge (const symbolic::conjured_bit_contents &bc) const
      54              : {
      55        13321 :   m_model->purge_state_involving (bc, m_ctxt);
      56        13321 : }
      57              : 
      58              : namespace symbolic {
      59              : 
      60              : // class bit_vector : public symbolic::node
      61              : 
      62      1257080 : bit_vector::bit_vector (bit_vector_manager &bv_mgr,
      63              :                         complexity c,
      64              :                         const symbolic_bit_size &size_in_bits)
      65      1257080 : : value_node (c, bv_mgr.get_node_manager ().alloc_node_id ()),
      66      1257080 :   m_bv_mgr (bv_mgr),
      67      1257080 :   m_size_in_bits (size_in_bits)
      68              : {
      69      1257080 : }
      70              : 
      71              : void
      72         2754 : bit_vector::print_dump_widget_label (pretty_printer *pp) const
      73              : {
      74         2754 :   start_any_dump_color (pp);
      75              : 
      76         2754 :   print_prefix_for_dump_widget_label (pp);
      77              : 
      78         2754 :   pp_string (pp, "[size: ");
      79              : 
      80         2754 :   end_any_dump_color (pp);
      81         2754 :   m_size_in_bits.start_any_dump_color (pp);
      82              : 
      83         2754 :   m_size_in_bits.dump_inline_to_pp (pp, units::role::size);
      84              : 
      85         2754 :   m_size_in_bits.end_any_dump_color (pp);
      86         2754 :   start_any_dump_color (pp);
      87              : 
      88         2754 :   pp_string (pp, "]");
      89              : 
      90         2754 :   print_any_suffix_for_dump_widget_label (pp);
      91              : 
      92         2754 :   end_any_dump_color (pp);
      93         2754 : }
      94              : 
      95              : bool
      96            0 : bit_vector::maybe_print_for_user (pretty_printer *,
      97              :                                   const region_model &,
      98              :                                   const symbolic::node *) const
      99              : {
     100            0 :   return false;
     101              : }
     102              : 
     103              : const symbolic_byte_size *
     104          106 : bit_vector::maybe_get_size_in_bytes () const
     105              : {
     106          106 :   return maybe_bytes_from_bits (m_size_in_bits);
     107              : }
     108              : 
     109              : bool
     110       870480 : bit_vector::maybe_get_concrete_size_in_bits (concrete_bit_size *out) const
     111              : {
     112       870480 :   return concrete_from_symbolic (m_size_in_bits, out);
     113              : }
     114              : 
     115              : bool
     116       747482 : bit_vector::maybe_get_concrete_size_in_bytes (concrete_byte_size *out) const
     117              : {
     118       747482 :   concrete_bit_size conc_bit_size;
     119       747482 :   if (!maybe_get_concrete_size_in_bits (&conc_bit_size))
     120              :     return false;
     121       736326 :   return maybe_bytes_from_bits (conc_bit_size, out);
     122       747482 : }
     123              : 
     124              : /* Base implementation of get_tristate_at_offset: crop to one bit, and get
     125              :    that bit as a tristate.  */
     126              : 
     127              : tristate
     128          832 : bit_vector::get_tristate_at_offset (const symbolic_bit_offset &bit) const
     129              : {
     130          832 :   auto &bit_mgr = m_bv_mgr.get_node_manager ().get_scalars ().get_bits ();
     131          832 :   auto &bv_for_bit = get_cropped_bits
     132          832 :     (symbolic_bit_range (bit,
     133          832 :                          bit_mgr.get_concrete (1_bit)));
     134          832 :   gcc_assert (bv_for_bit.get_size ().is_one_p ());
     135          832 :   auto *ts_bv = bv_for_bit.dyn_cast_tristate_bit_vector ();
     136          832 :   if (!ts_bv)
     137           24 :     return tristate::unknown ();
     138          808 :   return ts_bv->get_bit_value ();
     139              : }
     140              : 
     141              : class hexdumper
     142              : {
     143              : public:
     144           56 :   hexdumper (text_art::style_manager &sm,
     145              :              const hexdump_options &hexdump_opts)
     146           56 :   : m_sm (sm),
     147           56 :     m_hexdump_opts (hexdump_opts),
     148           56 :     m_num_columns (1),
     149           56 :     m_x_bit_range (0),
     150           56 :     m_x_binary (-1),
     151           56 :     m_x_hex (-1),
     152           56 :     m_x_ascii (-1)
     153              :   {
     154           56 :     if (hexdump_opts.m_show_binary)
     155           36 :       m_x_binary = m_num_columns++;
     156           56 :     if (hexdump_opts.m_show_hex)
     157           52 :       m_x_hex = m_num_columns++;
     158           56 :     if (hexdump_opts.m_show_ascii)
     159           36 :       m_x_ascii = m_num_columns++;
     160           56 :   }
     161              : 
     162              :   text_art::table
     163           56 :   make_table (const bit_vector &bv,
     164              :               concrete_bit_size conc_bit_size)
     165              :   {
     166           56 :     using namespace text_art;
     167              : 
     168           56 :     auto bits_per_line = bits_from_bytes (m_hexdump_opts.m_bytes_per_line);
     169              : 
     170           56 :     table t (table::size_t (m_num_columns, 0));
     171              : 
     172           56 :     if (m_hexdump_opts.m_show_headings)
     173              :       {
     174            4 :         int y_headings = t.add_row ();
     175            4 :         if (m_x_binary >= 0)
     176            4 :           t.set_cell (table::coord_t (m_x_binary, y_headings),
     177            8 :                       styled_string (m_sm, "Binary"));
     178            4 :         if (m_x_hex >= 0)
     179            4 :           t.set_cell (table::coord_t (m_x_hex, y_headings),
     180            8 :                       styled_string (m_sm, "Hex"));
     181            4 :         if (m_x_ascii >= 0)
     182            4 :           t.set_cell (table::coord_t (m_x_ascii, y_headings),
     183            8 :                       styled_string (m_sm, "ASCII"));
     184              :       }
     185              : 
     186           56 :     for (concrete_bit_offset start_of_this_line = 0_bits;
     187          148 :          start_of_this_line < conc_bit_size;
     188           92 :          start_of_this_line += bits_per_line)
     189              :       {
     190           92 :         auto start_of_next_line = start_of_this_line + bits_per_line;
     191           92 :         auto size_of_this_line = (start_of_next_line < conc_bit_size
     192           92 :                                   ? bits_per_line
     193           92 :                                   : conc_bit_size - start_of_this_line);
     194          184 :         add_hexdump_line (t,
     195              :                           bv,
     196           92 :                           concrete_bit_range (start_of_this_line,
     197          276 :                                               size_of_this_line));
     198           92 :     }
     199           56 :     return t;
     200           56 :   }
     201              : 
     202              : private:
     203              :   void
     204           92 :   add_hexdump_line (text_art::table &t,
     205              :                     const bit_vector &bv,
     206              :                     concrete_bit_range bits_on_line)
     207              :   {
     208           92 :     using namespace text_art;
     209              : 
     210          184 :     gcc_assert (bits_on_line.get_start_offset () >= 0_bits);
     211              :     //gcc_assert (bits_on_line.get_last_offset () < bv.get_size ());
     212              : 
     213           92 :     auto row_y = t.add_row ();
     214              : 
     215           92 :     {
     216           92 :       pretty_printer pp;
     217           92 :       bits_on_line.dump_to_pp_pretty (&pp);
     218           92 :       t.set_cell (table::coord_t (0, row_y),
     219          184 :                   styled_string (m_sm, pp_formatted_text (&pp)),
     220              :                   x_align::RIGHT);
     221           92 :     }
     222              : 
     223              :     /* Try to print the individual bits.  */
     224           92 :     if (m_x_binary >= 0)
     225              :       {
     226           60 :         pretty_printer pp;
     227           60 :         int count = 0;
     228           60 :         for (concrete_bit_offset i = bits_on_line.get_start_offset ();
     229         1872 :              i < bits_on_line.get_next_offset ();
     230         1812 :              i += 1_bit, ++count)
     231              :           {
     232         1812 :             tristate ts = bv.get_tristate_at_offset (i);
     233         1812 :             pp_character (&pp, get_dump_char_for_tristate_bit (ts));
     234              : 
     235              :             // Add a space every 8 bits:
     236         3624 :             if (count % 8 == 7
     237         2036 :                 && i < bits_on_line.get_last_offset ())
     238          168 :               pp_space (&pp);
     239           60 :           }
     240           60 :         t.set_cell (table::coord_t (m_x_binary, row_y),
     241          120 :                     styled_string (m_sm, pp_formatted_text (&pp)),
     242              :                     x_align::LEFT);
     243           60 :       }
     244              : 
     245              :     /* Try to print individual bytes.  */
     246           92 :     if (m_x_hex >= 0)
     247              :       {
     248           88 :         pretty_printer pp;
     249           88 :         bool first = true;
     250          496 :         for (concrete_bit_offset i = bits_on_line.get_start_offset ();
     251          496 :              i < bits_on_line.get_next_offset ();
     252          408 :              i += 8_bits)
     253              :           {
     254          408 :             if (i + 7_bits < bits_on_line.get_next_offset ())
     255              :               {
     256          408 :                 auto &byte
     257         1224 :                   = bv.get_cropped_bits (concrete_bit_range (i, 8_bits));
     258          408 :                 uint8_t byte_val;
     259          408 :                 if (first)
     260              :                   first = false;
     261              :                 else
     262          320 :                   pp_space (&pp);
     263          408 :                 if (byte.maybe_as_uint8 (&byte_val))
     264          376 :                   print_byte_as_hex (&pp, byte_val);
     265              :                 else
     266           32 :                   pp_string (&pp, "??");
     267              :               }
     268           88 :           }
     269           88 :         t.set_cell (table::coord_t (m_x_hex, row_y),
     270          176 :                     styled_string (m_sm, pp_formatted_text (&pp)),
     271              :                     x_align::LEFT);
     272           88 :       }
     273              : 
     274              :     // Try to print ASCII
     275           92 :     if (m_x_ascii >= 0)
     276              :       {
     277           64 :         pretty_printer pp;
     278          376 :         for (concrete_bit_offset i = bits_on_line.get_start_offset ();
     279          376 :              i < bits_on_line.get_next_offset ();
     280          312 :              i += 8_bits)
     281              :           {
     282          312 :             if (i + 7_bits < bits_on_line.get_next_offset ())
     283              :               {
     284          312 :                 auto &byte
     285          936 :                   = bv.get_cropped_bits (concrete_bit_range (i, 8_bits));
     286          312 :                 pp_character (&pp, get_dump_char_for_byte (byte));
     287              :               }
     288           64 :           }
     289           64 :         t.set_cell (table::coord_t (m_x_ascii, row_y),
     290          128 :                     styled_string (m_sm, pp_formatted_text (&pp)),
     291              :                     x_align::LEFT);
     292           64 :       }
     293           92 :   }
     294              : 
     295              :   static char
     296         1812 :   get_dump_char_for_tristate_bit (tristate t)
     297              :   {
     298         1812 :     switch (t.get_value ())
     299              :       {
     300            0 :       default:
     301            0 :         gcc_unreachable ();
     302              :       case tristate::TS_UNKNOWN:
     303              :         return '?';
     304              :       case tristate::TS_TRUE:
     305              :         return '1';
     306              :       case tristate::TS_FALSE:
     307              :         return '0';
     308              :       }
     309              :   }
     310              : 
     311              :   static void
     312          376 :   print_byte_as_hex (pretty_printer *pp, uint8_t byte)
     313              :   {
     314          376 :     const char *const hexchars = "0123456789abcdef";
     315          376 :     pp_character (pp, hexchars[byte / 16]);
     316          376 :     pp_character (pp, hexchars[byte % 16]);
     317          376 :   }
     318              : 
     319              :   static char
     320          312 :   get_dump_char_for_byte (const bit_vector &bv)
     321              :   {
     322          312 :     uint8_t byte_val;
     323          312 :     if (!bv.maybe_as_uint8 (&byte_val))
     324              :       return '?';
     325          296 :     gcc_assert (byte_val >= 0 && byte_val <= 255);
     326          296 :     if (ISPRINT (byte_val))
     327          244 :       return byte_val;
     328              :     else
     329              :       return '.';
     330              :   }
     331              : 
     332              :   text_art::style_manager &m_sm;
     333              : 
     334              :   const hexdump_options &m_hexdump_opts;
     335              :   int m_num_columns;
     336              :   int m_x_bit_range;
     337              :   int m_x_binary;
     338              :   int m_x_hex;
     339              :   int m_x_ascii;
     340              : };
     341              : 
     342              : static std::unique_ptr<text_art::canvas>
     343           56 : make_hexdump_canvas (const bit_vector &bv,
     344              :                      const hexdump_options &hexdump_opts)
     345              : {
     346           56 :   concrete_bit_size conc_bit_size;
     347           56 :   if (!concrete_from_symbolic (bv.get_size (), &conc_bit_size))
     348            0 :     return nullptr;
     349              : 
     350           56 :   text_art::style_manager sm;
     351           56 :   text_art::ascii_theme theme;
     352           56 :   hexdumper h (sm, hexdump_opts);
     353           56 :   auto t = h.make_table (bv, conc_bit_size);
     354           56 :   return std::make_unique<text_art::canvas> (t.to_canvas (theme, sm));
     355           56 : }
     356              : 
     357              : void
     358           56 : bit_vector::hexdump_to_pp (pretty_printer *pp,
     359              :                            const hexdump_options &hexdump_opts) const
     360              : {
     361           56 :   auto c = make_hexdump_canvas (*this, hexdump_opts);
     362           56 :   if (!c)
     363            0 :     return;
     364           56 :   c->print_to_pp (pp);
     365           56 : }
     366              : 
     367              : void
     368            0 : bit_vector::hexdump (const hexdump_options &hexdump_opts) const
     369              : {
     370            0 :   tree_dump_pretty_printer pp (stderr);
     371            0 :   hexdump_to_pp (&pp, hexdump_opts);
     372            0 : }
     373              : 
     374              : void
     375            0 : bit_vector::hexdump () const
     376              : {
     377            0 :   hexdump_options hexdump_opts;
     378            0 :   hexdump_opts.m_show_headings = true;
     379            0 :   hexdump_opts.m_show_binary = false;
     380            0 :   hexdump_opts.m_show_hex = true;
     381            0 :   hexdump_opts.m_show_ascii = true;
     382            0 :   hexdump (hexdump_opts);
     383            0 : }
     384              : 
     385              : bool
     386          284 : bit_vector::conjured_p () const
     387              : {
     388          284 :   return false;
     389              : }
     390              : 
     391              : tristate
     392       798956 : bit_vector::get_tristate_at_offset (const concrete_bit_offset &bit) const
     393              : {
     394       798956 :   auto &bit_mgr = m_bv_mgr.get_node_manager ().get_scalars ().get_bits ();
     395       798956 :   auto &sym_bit_offset = bit_mgr.get_concrete (bit);
     396       798956 :   return get_tristate_at_offset (sym_bit_offset);
     397              : }
     398              : 
     399              : const bit_vector &
     400        18112 : bit_vector::get_cropped_bits (const symbolic_bit_range &bits_to_use) const
     401              : {
     402        18112 :   return m_bv_mgr.get_cropped_bits (*this, bits_to_use);
     403              : }
     404              : 
     405              : const bit_vector &
     406      2164001 : bit_vector::get_cropped_bits (const concrete_bit_range &bits_to_use) const
     407              : {
     408      2164001 :   auto &bit_mgr = m_bv_mgr.get_bit_manager ();
     409      2164001 :   return m_bv_mgr.get_cropped_bits (*this,
     410      2164001 :                                     symbolic_from_concrete (bits_to_use,
     411      2164001 :                                                             bit_mgr));
     412              : }
     413              : 
     414              : const bit_vector &
     415            0 : bit_vector::get_cropped_bytes (const symbolic_byte_range &bytes_to_use) const
     416              : {
     417            0 :   return m_bv_mgr.get_cropped_bits (*this, bits_from_bytes (bytes_to_use));
     418              : }
     419              : 
     420              : const bit_vector &
     421          140 : bit_vector::get_cropped_bytes (const concrete_byte_range &bytes_to_use) const
     422              : {
     423          140 :   auto &bit_mgr = m_bv_mgr.get_bit_manager ();
     424          140 :   return m_bv_mgr.get_cropped_bits
     425          140 :     (*this,
     426          280 :      symbolic_from_concrete (bits_from_bytes (bytes_to_use),
     427          140 :                              bit_mgr));
     428              : }
     429              : 
     430              : /* Get the first SIZE bits of this bit_vector.  */
     431              : 
     432              : const bit_vector &
     433          925 : bit_vector::get_prefix (const symbolic_bit_size &size) const
     434              : {
     435          925 :   auto &bit_mgr = m_bv_mgr.get_bit_manager ();
     436          925 :   return m_bv_mgr.get_cropped_bits
     437          925 :     (*this,
     438          925 :      symbolic_bit_range (bit_mgr.get_concrete (0_bits),
     439          925 :                          size));
     440              : }
     441              : 
     442              : const bit_vector &
     443          917 : bit_vector::get_prefix (const concrete_bit_size &size) const
     444              : {
     445          917 :   return get_prefix (symbolic_from_concrete (size,
     446          917 :                                              m_bv_mgr.get_bit_manager ()));
     447              : }
     448              : 
     449              : /* Get the last SIZE bits of this bit_vector.  */
     450              : 
     451              : const bit_vector &
     452         1983 : bit_vector::get_suffix (const symbolic_bit_size &size) const
     453              : {
     454         1983 :   return m_bv_mgr.get_cropped_bits (*this,
     455         1983 :                                     symbolic_bit_range (get_size () - size,
     456         1983 :                                                         size));
     457              : }
     458              : 
     459              : const bit_vector &
     460         1983 : bit_vector::get_suffix (const concrete_bit_size &size) const
     461              : {
     462         1983 :   return get_suffix (symbolic_from_concrete (size,
     463         1983 :                                              m_bv_mgr.get_bit_manager ()));
     464              : }
     465              : 
     466              : const bit_vector &
     467            0 : bit_vector::get_byte_at_offset (const symbolic_byte_offset &byte_offset) const
     468              : {
     469            0 :   auto &byte_mgr = m_bv_mgr.get_node_manager ().get_scalars ().get_bytes ();
     470            0 :   return m_bv_mgr.get_cropped_bytes
     471            0 :     (*this,
     472            0 :      symbolic_byte_range (byte_offset,
     473            0 :                           byte_mgr.get_concrete (1_byte)));
     474              : }
     475              : 
     476              : const bit_vector &
     477       475598 : bit_vector::get_byte_at_offset (const concrete_byte_offset &byte_offset) const
     478              : {
     479       475598 :   auto &byte_mgr = m_bv_mgr.get_node_manager ().get_scalars ().get_bytes ();
     480       475598 :   return m_bv_mgr.get_cropped_bytes
     481       475598 :     (*this,
     482       951196 :      symbolic_byte_range (byte_mgr.get_concrete (byte_offset),
     483       475598 :                           byte_mgr.get_concrete (1_byte)));
     484              : }
     485              : 
     486              : const bit_vector *
     487        75878 : bit_vector::maybe_fold_crop (const symbolic_bit_range &) const
     488              : {
     489        75878 :   return nullptr;
     490              : }
     491              : 
     492              : /* If this is an 8-bit constant value, return true and write it to *OUT.
     493              :    Otherwise return false.  */
     494              : 
     495              : bool
     496       477094 : bit_vector::maybe_as_uint8 (uint8_t *out) const
     497              : {
     498       477094 :   concrete_byte_size byte_size;
     499       477094 :   if (!maybe_get_concrete_size_in_bytes (&byte_size))
     500              :     return false;
     501       477094 :   if (byte_size != 1_byte)
     502              :     return false;
     503              : 
     504       477094 :   if (auto *ts = dyn_cast_tristate_bit_vector ())
     505       250033 :     switch (ts->get_bit_value ().get_value ())
     506              :       {
     507            0 :       default:
     508            0 :         gcc_unreachable ();
     509              :       case tristate::TS_UNKNOWN:
     510              :         return false;
     511              : 
     512           84 :       case tristate::TS_TRUE:
     513           84 :         *out = 0xff;
     514           84 :         return true;
     515              : 
     516       249917 :       case tristate::TS_FALSE:
     517       249917 :         *out = 0x00;
     518       249917 :         return true;
     519              :       }
     520              : 
     521       227061 :   if (auto *sval_bv = dyn_cast_bit_vector_from_svalue ())
     522              :     {
     523         2425 :       auto &sval = sval_bv->get_svalue ();
     524         2425 :       if (tree type = sval.get_type ())
     525         2425 :         if (INTEGRAL_TYPE_P (type)
     526         2425 :             && TYPE_PRECISION (type) == 8)
     527         2425 :           if (tree cst = sval.maybe_get_constant ())
     528              :             {
     529         2379 :               *out = TREE_INT_CST_LOW (cst);
     530         2379 :               return true;
     531              :             }
     532              :     }
     533              : 
     534              :   return false;
     535       477094 : }
     536              : 
     537              : const bit_vector *
     538        70173 : bit_vector::can_merge_p (const bit_vector &bv_a,
     539              :                          const bit_vector &bv_b,
     540              :                          tree type,
     541              :                          model_merger *merger)
     542              : {
     543        70173 :   if (&bv_a == &bv_b)
     544              :     return &bv_a;
     545              : 
     546        62276 :   auto &bv_mgr = bv_a.m_bv_mgr;
     547              : 
     548              :   /* Reject attempts to merge poisoned bit vectors with other bit vectors
     549              :      (either non-poisoned, or other kinds of poison), so that e.g.
     550              :      we identify paths in which a variable is conditionally uninitialized.  */
     551        62276 :   if (bv_a.get_kind () == kind::poisoned
     552        62276 :       || bv_b.get_kind () == kind::poisoned)
     553              :     return nullptr;
     554              : 
     555        61993 :   if (!merger->mergeable_bit_vector_p (bv_a))
     556              :     return nullptr;
     557        61198 :   if (!merger->mergeable_bit_vector_p (bv_b))
     558              :     return nullptr;
     559              : 
     560              :   /* If we don't have a type, but both bvs are built from svalues with
     561              :      the same underlying type, try to use that type.  */
     562        60179 :   if (!type)
     563         3899 :     if (auto *from_sval_a = bv_a.dyn_cast_bit_vector_from_svalue ())
     564          933 :       if (auto *from_sval_b = bv_b.dyn_cast_bit_vector_from_svalue ())
     565              :         {
     566          672 :           tree type_a = from_sval_a->get_svalue ().get_type ();
     567          672 :           tree type_b = from_sval_b->get_svalue ().get_type ();
     568          672 :           if (type_a == type_b)
     569         3899 :             type = type_a;
     570              :         }
     571              : 
     572         3899 :   if (type)
     573              :     {
     574        56944 :       auto &rmm = bv_mgr.get_node_manager ().get_svalue_manager ();
     575        56944 :       const svalue *sval_a = rmm.get_svalue_from_bit_vector (type, bv_a);
     576        56944 :       const svalue *sval_b = rmm.get_svalue_from_bit_vector (type, bv_b);
     577        56944 :       if (const svalue *merged_sval = sval_a->can_merge_p (sval_b, &rmm,
     578              :                                                            merger))
     579        43012 :         return &bv_mgr.get_bit_vector_from_svalue (*merged_sval);
     580              :       else
     581              :         /* svalues not mergeable; don't merge the bit vectors.  */
     582              :         return nullptr;
     583              :     }
     584              : 
     585         3235 :   return &bv_mgr.get_unknown_bits (bv_a.get_size ());
     586              : }
     587              : 
     588              : std::unique_ptr<json::object>
     589          184 : bit_vector::make_json_obj (const char *type_name) const
     590              : {
     591          184 :   auto obj = value_node::make_json_obj (type_name);
     592          184 :   obj->set ("size_in_bits", m_size_in_bits.to_json ());
     593          184 :   return obj;
     594              : }
     595              : 
     596              : 
     597              : static bool
     598        23874 : maybe_set_irange_bitmask_from_concrete_tristate_vector (const concrete_tristate_vector &ts_vec,
     599              :                                                         irange_bitmask *out)
     600              : {
     601        23874 :   unsigned HOST_WIDE_INT value = 0;
     602        23874 :   unsigned HOST_WIDE_INT mask = -1;
     603       812582 :   for (size_t i = 0; i < ts_vec.size (); ++i)
     604              :     {
     605       788708 :       tristate ts = ts_vec[i];
     606       788708 :       if (ts.is_known ())
     607              :         {
     608              :           /* Clear the mask for known bits.  */
     609          337 :           mask &= ~(1L << i);
     610              : 
     611              :           /* Set the value.  */
     612          337 :           if (ts.is_true ())
     613          107 :             value |= (1L << i);
     614              :         }
     615              :     }
     616        47748 :   *out = irange_bitmask (wi::uhwi (value, ts_vec.size ()),
     617        47748 :                          wi::uhwi (mask, ts_vec.size ()));
     618        23874 :   return true;
     619              : }
     620              : 
     621              : bool
     622        23886 : bit_vector::maybe_get_irange_bitmask (irange_bitmask *out) const
     623              : {
     624        23886 :   concrete_bit_size conc_size;
     625        23886 :   if (!maybe_get_concrete_size_in_bits (&conc_size))
     626              :     return false;
     627              : 
     628        23886 :   if (conc_size > 64_bits)
     629              :     return false;
     630              : 
     631        23870 :   out->set_unknown (conc_size.as_unsigned_long ());
     632        23870 :   concrete_tristate_vector ts_vec;
     633        23870 :   ts_vec.reserve (conc_size.as_unsigned_long ());
     634       836428 :   for (concrete_bit_offset i = 0_bits; i < conc_size; ++i)
     635              :     {
     636              :       /* TODO: this is a lot of vfuncs and sym to conc,
     637              :          and O(n^2) e.g. on concat_bit_vector
     638              :          We might want a bulk query interface that
     639              :          returns a concrete_tristate_vector.  */
     640       788688 :       tristate ts = get_tristate_at_offset (i);
     641       788688 :       ts_vec.push_back (ts);
     642        23870 :     }
     643        23870 :   return maybe_set_irange_bitmask_from_concrete_tristate_vector (ts_vec,
     644              :                                                                  out);
     645        23870 : }
     646              : 
     647              : /* Return true if this bit vector is the initial value of a region,
     648              :    or derived directly from such a value (e.g. by casting or cropping).  */
     649              : 
     650              : bool
     651         9296 : bit_vector::derived_from_initial_value_p () const
     652              : {
     653         9372 :   switch (get_kind ())
     654              :     {
     655              :     default:
     656              :       return false;
     657              : 
     658           76 :     case bit_vector::kind::cropped:
     659           76 :       {
     660           76 :         auto &cropped_bv = static_cast <const cropped_bit_vector &> (*this);
     661           76 :         return cropped_bv
     662           76 :           .get_uncropped_bit_vector ()
     663           76 :           .derived_from_initial_value_p ();
     664              :       }
     665              : 
     666           76 :     case bit_vector::kind::svalue:
     667           76 :       {
     668           76 :         auto &from_sval = static_cast <const bit_vector_from_svalue &> (*this);
     669           76 :         return from_sval.get_svalue ().derived_from_initial_value_p ();
     670              :       }
     671              :     }
     672              : }
     673              : 
     674              : // class concat_bit_vector : public bit_vector
     675              : 
     676              : bool
     677       213872 : concat_bit_vector::key::operator< (const key &other) const
     678              : {
     679       213872 :   if (m_bit_vectors.size () != other.m_bit_vectors.size ())
     680         3765 :     return m_bit_vectors.size () < other.m_bit_vectors.size ();
     681       357824 :   for (size_t i = 0; i < m_bit_vectors.size (); ++i)
     682       292314 :     if (m_bit_vectors[i] != other.m_bit_vectors[i])
     683       144597 :       return m_bit_vectors[i]->get_id () < other.m_bit_vectors[i]->get_id ();
     684              :   return false;
     685              : }
     686              : 
     687              : complexity
     688         4109 : concat_bit_vector::key::get_complexity () const
     689              : {
     690         4109 :   unsigned num_child_nodes = 0;
     691         4109 :   unsigned max_child_depth = 0;
     692        14015 :   for (auto iter : m_bit_vectors)
     693              :     {
     694         9906 :       const complexity &child_c = iter->get_complexity ();
     695         9906 :       num_child_nodes += child_c.m_num_nodes;
     696         9906 :       max_child_depth = std::max (max_child_depth, child_c.m_max_depth);
     697              :     }
     698         4109 :   return complexity (num_child_nodes + 1, max_child_depth + 1);
     699              : }
     700              : 
     701              : const symbolic_bit_size &
     702         4109 : concat_bit_vector::key::
     703              : get_size (scalar_manager<concrete_bit_size> &bit_mgr) const
     704              : {
     705         4109 :   const symbolic_bit_size *sum = &bit_mgr.get_concrete (0_bits);
     706        14015 :   for (auto iter : m_bit_vectors)
     707         9906 :     sum = &(*sum + iter->get_size ());
     708         4109 :   return *sum;
     709              : }
     710              : 
     711              : tristate
     712        10192 : concat_bit_vector::get_tristate_at_offset (const symbolic_bit_offset &bit) const
     713              : {
     714        10192 :   auto *remaining_offset = &bit;
     715        17031 :   for (auto child : m_bit_vectors)
     716              :     {
     717              :       /* Is the bit of interest within child?
     718              :          |    remaining_offset < child->get_size ()
     719              :          | => (remaining_offset - child->get_size ()) < 0  */
     720        17031 :       auto &diff = *remaining_offset - child->get_size ();
     721        17031 :       if (auto *conc_diff = diff.dyn_cast_concrete_scalar ())
     722              :         {
     723        17031 :           if (conc_diff->get_concrete () < 0_bits)
     724        10192 :             return child->get_tristate_at_offset (*remaining_offset);
     725              :           else
     726              :             {
     727              :               /* Skip this child.
     728              :                  | remaining_offset -= child_get_size
     729              :                  | ==> remaining_offset = remaining_offset - child_get_size
     730              :                  | ==> remaining_offset = diff  */
     731         6839 :               remaining_offset = &diff;
     732         6839 :               continue;
     733              :             }
     734              :         }
     735              :       else
     736              :         {
     737              :           /* We don't know whether we're in child or not.  */
     738            0 :           return tristate::unknown ();
     739              :         }
     740              :     }
     741            0 :   return tristate::unknown ();
     742              : }
     743              : 
     744         4109 : concat_bit_vector::concat_bit_vector (bit_vector_manager &bv_mgr,
     745              :                                       const key &k)
     746              : : bit_vector (bv_mgr,
     747              :               k.get_complexity (),
     748         4109 :               k.get_size (bv_mgr.get_node_manager ()
     749         4109 :                           .get_scalars ().get_bits ())),
     750         4109 :   m_bit_vectors (std::move (k.m_bit_vectors))
     751              : {
     752              :   /* The only empty bit_vector should be the singleton empty_bit_vector.  */
     753         4109 :   gcc_assert (!get_size ().is_zero_p ());
     754              : 
     755              :   /* After folding, we shouldn't have empty or single-element
     756              :      concatentations.  */
     757         4109 :   gcc_assert (m_bit_vectors.size () >= 2);
     758              : 
     759              :   if (CHECKING_P)
     760         9906 :     for (auto iter = m_bit_vectors.begin ();
     761        14015 :          iter != m_bit_vectors.end ();
     762         9906 :          ++iter)
     763              :       {
     764              :         /* No empty children.  */
     765         9906 :         gcc_assert (!(*iter)->get_size ().is_zero_p ());
     766              : 
     767              :         /* No nesting.  */
     768         9906 :         gcc_assert (!(*iter)->dyn_cast_concat_bit_vector ());
     769              : 
     770              :         /* Check that we folded away consecutive children.  */
     771         9906 :         auto next = iter;
     772         9906 :         ++next;
     773         9906 :         if (next != m_bit_vectors.end ())
     774              :           {
     775              :             /* Must not have the same bit_vector appearing
     776              :                consecutively as a child.  */
     777         5797 :             gcc_assert (*iter != *next);
     778              : 
     779              :             /* Must not have consecutive children that are the
     780              :                uniform_bit_vector with the same underlying bit.  */
     781         5797 :             if (auto *iter_poisoned = (*iter)->dyn_cast_poisoned_bit_vector ())
     782          106 :               if (auto *next_poisoned = (*next)->dyn_cast_poisoned_bit_vector ())
     783            4 :                 gcc_assert (iter_poisoned->get_poison_kind ()
     784              :                             != next_poisoned->get_poison_kind ());
     785         5797 :             if (auto *iter_tristate = (*iter)->dyn_cast_tristate_bit_vector ())
     786          581 :               if (auto *next_tristate = (*next)->dyn_cast_tristate_bit_vector ())
     787          105 :                 gcc_assert (iter_tristate->get_bit_value ()
     788              :                             != next_tristate->get_bit_value ());
     789              : 
     790              :             /* Must not have consecutive repetitions of the same bit vector,
     791              :                or a bit vector next to repetitions of that bit vector.  */
     792         5797 :             auto *iter_rep = (*iter)->dyn_cast_repeated_bit_vector ();
     793         5797 :             auto *next_rep = (*next)->dyn_cast_repeated_bit_vector ();
     794         5797 :             if (iter_rep)
     795              :               {
     796          184 :                 if (next_rep)
     797           45 :                   gcc_assert (&iter_rep->get_inner_bit_vector ()
     798              :                               != &next_rep->get_inner_bit_vector ());
     799              :                 else
     800          139 :                   gcc_assert (&iter_rep->get_inner_bit_vector () != (*next));
     801              :               }
     802         5613 :             else if (next_rep)
     803          100 :               gcc_assert ((*iter) != &next_rep->get_inner_bit_vector ());
     804              : 
     805              :             /* Must not have consecutive bit_vector_from_ubc taken from the
     806              :                same UBC at consecutive positions.  */
     807         5797 :             if (auto *iter_from_ubc = (*iter)->dyn_cast_bit_vector_from_ubc ())
     808          203 :               if (auto *next_from_ubc = (*next)->dyn_cast_bit_vector_from_ubc ())
     809           16 :                 if (&iter_from_ubc->get_bit_contents ()
     810           16 :                     == &next_from_ubc->get_bit_contents ())
     811            4 :                   gcc_assert
     812              :                     (&iter_from_ubc->get_bit_range ().get_next_offset ()
     813              :                      != &next_from_ubc->get_bit_range ().get_start_offset ());
     814              :           }
     815              :       }
     816         4109 : }
     817              : 
     818              : void
     819           14 : concat_bit_vector::
     820              : print_prefix_for_dump_widget_label (pretty_printer *pp) const
     821              : {
     822           14 :   pp_string (pp, "concat_bit_vector");
     823           14 : }
     824              : 
     825              : void
     826           14 : concat_bit_vector::add_dump_widget_children (text_art::tree_widget &w,
     827              :                                              node_dump_state &nds) const
     828              : {
     829           42 :   for (auto iter : m_bit_vectors)
     830           56 :     w.add_child (iter->make_dump_widget (nds, nullptr));
     831           14 : }
     832              : 
     833              : void
     834         3932 : concat_bit_vector::accept_node_visitor (node_visitor &v) const
     835              : {
     836         3932 :   if (!v.visit_bit_vector (*this))
     837              :     return;
     838        13291 :   for (auto iter : m_bit_vectors)
     839         9359 :     iter->accept_node_visitor (v);
     840              : }
     841              : 
     842              : std::unique_ptr<json::object>
     843            8 : concat_bit_vector::to_json () const
     844              : {
     845            8 :   auto obj = bit_vector::make_json_obj ("concat_bit_vector");
     846            8 :   auto arr = std::make_unique<json::array> ();
     847           32 :   for (auto iter : m_bit_vectors)
     848           24 :     arr->append (iter->to_json ());
     849            8 :   obj->set ("bit_vectors", std::move (arr));
     850           16 :   return obj;
     851            8 : }
     852              : 
     853              : std::unique_ptr<diagnostics::markup::node>
     854            0 : concat_bit_vector::make_markup_node (markup_context &) const
     855              : {
     856            0 :   return diagnostics::markup::make_text_node ("concat_bit_vector");
     857              : }
     858              : 
     859              : iter_result
     860            0 : concat_bit_vector::for_each_svalue (iter_result (*cb) (const svalue &sval,
     861              :                                                        void *user_data),
     862              :                                     void *user_data) const
     863              : {
     864            0 :   for (auto iter : m_bit_vectors)
     865            0 :     if (iter->for_each_svalue (cb, user_data) == iter_result::stop)
     866            0 :       return iter_result::stop;
     867              :   return iter_result::keep_going;
     868              : }
     869              : 
     870              : bool
     871           76 : concat_bit_vector::implicitly_live_p (liveness_context &liveness_ctxt) const
     872              : {
     873          143 :   for (auto iter : m_bit_vectors)
     874          143 :     if (!liveness_ctxt.node_live_p (*iter))
     875           76 :       return false;
     876              :   return true;
     877              : }
     878              : 
     879              : /* crop of concat e.g.:
     880              :    concat(X1, ... Xn)[a, b] --> concat(X1[...], ..., Xn[...])
     881              : */
     882              : const bit_vector *
     883         3145 : concat_bit_vector::
     884              : maybe_fold_crop (const symbolic_bit_range &sym_inner_bits_to_use) const
     885              : {
     886         3145 :   concrete_bit_range conc_inner_bits_to_use;
     887         3145 :   if (!concrete_from_symbolic (sym_inner_bits_to_use, &conc_inner_bits_to_use))
     888              :     return nullptr;
     889              : 
     890         3145 :   std::vector<const bit_vector *> vec_of_cropped;
     891         3145 :   concrete_bit_size leading_bits_to_ignore
     892         3145 :     = conc_inner_bits_to_use.get_start_offset ();
     893         3145 :   concrete_bit_size remaining_bits_to_add
     894         3145 :     = conc_inner_bits_to_use.get_size ();
     895        11459 :   for (auto iter : *this)
     896              :     {
     897        11459 :       auto &iter_size = iter->get_size ();
     898        11459 :       concrete_bit_size conc_iter_size;
     899        11459 :       if (!concrete_from_symbolic (iter_size, &conc_iter_size))
     900            0 :         return nullptr;
     901              : 
     902        11459 :       concrete_bit_size bits_to_use
     903        11459 :         = std::min (conc_iter_size - leading_bits_to_ignore,
     904        11459 :                     remaining_bits_to_add);
     905        11459 :       if (bits_to_use > 0_bits)
     906              :         {
     907         3313 :           auto &cropped_iter = iter->get_cropped_bits
     908         9939 :             (concrete_bit_range (leading_bits_to_ignore,
     909         9939 :                                  bits_to_use));
     910         3313 :           vec_of_cropped.push_back (&cropped_iter);
     911         3313 :           leading_bits_to_ignore = 0_bits;
     912         3313 :           remaining_bits_to_add -= bits_to_use;
     913              :         }
     914              :       else
     915         8146 :         leading_bits_to_ignore -= conc_iter_size;
     916              : 
     917        11459 :       if (remaining_bits_to_add <= 0_bits)
     918              :         break;
     919        11459 :     }
     920              : 
     921         3145 :   return &m_bv_mgr.get_concat_bits (std::move (vec_of_cropped));
     922         3145 : }
     923              : 
     924              : // class conjured_bit_vector : public bit_vector
     925              : 
     926              : bool
     927       345807 : conjured_bit_vector::key::operator< (const key &other) const
     928              : {
     929       345807 :   if (int c = m_stmt->uid - other.m_stmt->uid)
     930       275541 :     return c < 0;
     931        70266 :   if (int c = node::cmp (*m_id_reg, *other.m_id_reg))
     932        27716 :     return c < 0;
     933        42550 :   return m_idx < other.m_idx;
     934              : }
     935              : 
     936              : complexity
     937        14560 : conjured_bit_vector::key::get_complexity () const
     938              : {
     939        14560 :   return complexity (m_id_reg);
     940              : }
     941              : 
     942              : const symbolic_bit_size &
     943        14560 : conjured_bit_vector::key::get_size (scalar_manager<concrete_bit_size> &bit_mgr) const
     944              : {
     945        14560 :   auto size = m_id_reg->maybe_get_bit_size (bit_mgr);
     946        14560 :   if (!size)
     947         8894 :     size = &bit_mgr.get_unknown ();
     948        14560 :   return *size;
     949              : }
     950              : 
     951              : tristate
     952       535492 : conjured_bit_vector::get_tristate_at_offset (const symbolic_bit_offset &) const
     953              : {
     954       535492 :   return tristate::unknown ();
     955              : }
     956              : 
     957        14560 : conjured_bit_vector::conjured_bit_vector (bit_vector_manager &bv_mgr,
     958              :                                           const key &k)
     959              : : bit_vector (bv_mgr,
     960              :               k.get_complexity (),
     961        14560 :               k.get_size (bv_mgr.get_node_manager ()
     962        14560 :                           .get_scalars ().get_bits ())),
     963        14560 :   m_stmt (k.m_stmt),
     964        14560 :   m_id_reg (k.m_id_reg),
     965        14560 :   m_idx (k.m_idx)
     966              : {
     967              :   /* The only empty bit_vector should be the singleton empty_bit_vector.  */
     968        14560 :   gcc_assert (!get_size ().is_zero_p ());
     969        14560 : }
     970              : 
     971              : void
     972            0 : conjured_bit_vector::
     973              : print_prefix_for_dump_widget_label (pretty_printer *pp) const
     974              : {
     975            0 :   pp_printf (pp, "conjured_bit_vector (");
     976            0 :   pp_gimple_stmt_1 (pp, m_stmt, 0, (dump_flags_t)0);
     977            0 :   if (m_idx != 0)
     978            0 :     pp_printf (pp, ", %i", m_idx);
     979            0 :   pp_character (pp, ')');
     980            0 : }
     981              : 
     982              : void
     983            0 : conjured_bit_vector::add_dump_widget_children (text_art::tree_widget &w,
     984              :                                                node_dump_state &nds) const
     985              : {
     986            0 :   w.add_child (m_id_reg->make_dump_widget (nds, "id_reg"));
     987            0 : }
     988              : 
     989              : void
     990      1938812 : conjured_bit_vector::accept_node_visitor (node_visitor &v) const
     991              : {
     992      1938812 :   if (!v.visit_bit_vector (*this))
     993              :     return;
     994      1938812 :   m_id_reg->accept_node_visitor (v);
     995              : }
     996              : 
     997              : std::unique_ptr<json::object>
     998            0 : conjured_bit_vector::to_json () const
     999              : {
    1000            0 :   auto obj = bit_vector::make_json_obj ("conjured_bit_vector");
    1001              : 
    1002            0 :   {
    1003            0 :     pretty_printer pp;
    1004            0 :     pp_format_decoder (&pp) = default_tree_printer;
    1005            0 :     pp_gimple_stmt_1 (&pp, m_stmt, 0, (dump_flags_t)0);
    1006            0 :     obj->set_string ("stmt", pp_formatted_text (&pp));
    1007            0 :   }
    1008            0 :   obj->set ("id_reg", m_id_reg->to_json ());
    1009            0 :   obj->set_integer ("id", m_idx);
    1010              : 
    1011            0 :   return obj;
    1012              : }
    1013              : 
    1014              : std::unique_ptr<diagnostics::markup::node>
    1015           12 : conjured_bit_vector::make_markup_node (markup_context &markup_ctxt) const
    1016              : {
    1017           12 :   if (markup_ctxt.m_user_facing)
    1018           12 :     return m_id_reg->make_markup_node (markup_ctxt);
    1019              : 
    1020            0 :   auto markup = std::make_unique<diagnostics::markup::compound_node> ();
    1021            0 :   markup->add_child ("conjured_bit_vector(");
    1022            0 :   markup->add_child (")");
    1023            0 :   return markup;
    1024            0 : }
    1025              : 
    1026              : iter_result
    1027         1050 : conjured_bit_vector::for_each_svalue (iter_result (*) (const svalue &sval,
    1028              :                                                          void *user_data),
    1029              :                                       void *) const
    1030              : {
    1031         1050 :   return iter_result::keep_going;
    1032              : }
    1033              : 
    1034              : // class cropped_bit_vector : public bit_vector
    1035              : 
    1036              : bool
    1037       419753 : cropped_bit_vector::key::operator< (const key &other) const
    1038              : {
    1039       419753 :   if (int c = node::cmp (*m_uncropped_bv,
    1040       419753 :                          *other.m_uncropped_bv))
    1041       190612 :     return c < 0;
    1042       392959 :   return symbolic_bit_range::cmp (m_bits_to_use, other.m_bits_to_use) < 0;
    1043              : }
    1044              : 
    1045              : tristate
    1046         9672 : cropped_bit_vector::
    1047              : get_tristate_at_offset (const symbolic_bit_offset &bit) const
    1048              : {
    1049         9672 :   return m_uncropped_bv.get_tristate_at_offset
    1050         9672 :     (m_crop_start_bit_offset + bit);
    1051              : }
    1052              : 
    1053         7367 : cropped_bit_vector::cropped_bit_vector (bit_vector_manager &bv_mgr,
    1054              :                                         const key &k)
    1055              : : bit_vector (bv_mgr,
    1056         7367 :               complexity (*k.m_uncropped_bv),
    1057              :               k.get_size ()),
    1058         7367 :   m_uncropped_bv (*k.m_uncropped_bv),
    1059         7367 :   m_crop_start_bit_offset (k.m_bits_to_use.get_start_offset ())
    1060              : {
    1061              :   /* The only empty bit_vector should be the singleton empty_bit_vector.  */
    1062         7367 :   gcc_assert (!get_size ().is_zero_p ());
    1063              : 
    1064              :   /* No nesting.  */
    1065         7367 :   gcc_assert (!m_uncropped_bv.dyn_cast_cropped_bit_vector ());
    1066              : 
    1067              :   /* Cropping of a uniform_bit_vector should have been folded
    1068              :      before now.  */
    1069         7367 :   gcc_assert (!m_uncropped_bv.dyn_cast_uniform_bit_vector ());
    1070         7367 : }
    1071              : 
    1072              : void
    1073            7 : cropped_bit_vector::
    1074              : print_prefix_for_dump_widget_label (pretty_printer *pp) const
    1075              : {
    1076            7 :   pp_string (pp, "cropped_bit_vector");
    1077            7 : }
    1078              : 
    1079              : void
    1080            7 : cropped_bit_vector::
    1081              : print_any_suffix_for_dump_widget_label (pretty_printer *pp) const
    1082              : {
    1083            7 :   concrete_bit_range conc_bits;
    1084            7 :   if (concrete_from_symbolic (get_uncropped_bits_to_use (), &conc_bits))
    1085              :     {
    1086            7 :       pp_string (pp, ": ");
    1087            7 :       end_any_dump_color (pp);
    1088            7 :       m_size_in_bits.start_any_dump_color (pp);
    1089            7 :       conc_bits.dump_to_pp_pretty (pp);
    1090              :     }
    1091            7 : }
    1092              : 
    1093              : void
    1094            7 : cropped_bit_vector::add_dump_widget_children (text_art::tree_widget &w,
    1095              :                                               node_dump_state &nds) const
    1096              : {
    1097           14 :   w.add_child (m_uncropped_bv.make_dump_widget (nds, "uncropped"));
    1098            7 :   concrete_bit_range conc_bits;
    1099            7 :   if (!concrete_from_symbolic (get_uncropped_bits_to_use (), &conc_bits))
    1100            0 :     w.add_child (get_uncropped_bits_to_use ().make_dump_widget (nds,
    1101              :                                                                 "bits to use"));
    1102            7 : }
    1103              : 
    1104              : void
    1105        52670 : cropped_bit_vector::accept_node_visitor (node_visitor &v) const
    1106              : {
    1107        52670 :   if (!v.visit_bit_vector (*this))
    1108              :     return;
    1109          271 :   m_uncropped_bv.accept_node_visitor (v);
    1110              : }
    1111              : 
    1112              : std::unique_ptr<json::object>
    1113            4 : cropped_bit_vector::to_json () const
    1114              : {
    1115            4 :   auto obj = bit_vector::make_json_obj ("cropped_bit_vector");
    1116            4 :   obj->set ("crop_start_bit_offset", m_crop_start_bit_offset.to_json ());
    1117            4 :   obj->set ("uncropped_bv", m_uncropped_bv.to_json ());
    1118            4 :   return obj;
    1119              : }
    1120              : 
    1121              : std::unique_ptr<diagnostics::markup::node>
    1122            0 : cropped_bit_vector::make_markup_node (markup_context &markup_ctxt) const
    1123              : {
    1124            0 :   auto result = std::make_unique<diagnostics::markup::compound_node> ();
    1125            0 :   result->add_child ("cropped_bit_vector (start_bit_offset=");
    1126            0 :   result->add_child (m_crop_start_bit_offset.make_markup_node (markup_ctxt));
    1127            0 :   result->add_child (", uncropped_bv=");
    1128            0 :   result->add_child (m_uncropped_bv.make_markup_node (markup_ctxt));
    1129            0 :   result->add_child (")");
    1130            0 :   return result;
    1131            0 : }
    1132              : 
    1133              : iter_result
    1134           43 : cropped_bit_vector::for_each_svalue (iter_result (*) (const svalue &sval,
    1135              :                                                       void *user_data),
    1136              :                                      void *) const
    1137              : {
    1138           43 :   return iter_result::keep_going;
    1139              : }
    1140              : 
    1141              : bool
    1142          732 : cropped_bit_vector::implicitly_live_p (liveness_context &liveness_ctxt) const
    1143              : {
    1144          732 :   return m_uncropped_bv.implicitly_live_p (liveness_ctxt);
    1145              : }
    1146              : 
    1147              : /* Crop of crop: A[m..n][p..q] --> A[m + n .. m + n + sizeof(p..q)].  */
    1148              : 
    1149              : const bit_vector *
    1150         2173 : cropped_bit_vector::
    1151              : maybe_fold_crop (const symbolic_bit_range &bits_to_use) const
    1152              : {
    1153         2173 :   symbolic_bit_range bit_range_relative_to_grandchild
    1154         2173 :     ((get_uncropped_bits_to_use ().get_start_offset ()
    1155              :       + bits_to_use.get_start_offset ()),
    1156         2173 :      bits_to_use.get_size ());
    1157         2173 :   return &m_bv_mgr.get_cropped_bits (get_uncropped_bit_vector (),
    1158         2173 :                                      bit_range_relative_to_grandchild);
    1159              : }
    1160              : 
    1161              : // class named_test_bit_vector : public bit_vector
    1162              : 
    1163              : #if CHECKING_P
    1164              : 
    1165              : tristate
    1166            0 : named_test_bit_vector::
    1167              : get_tristate_at_offset (const symbolic_bit_offset &) const
    1168              : {
    1169            0 :   return tristate::unknown ();
    1170              : }
    1171              : 
    1172          128 : named_test_bit_vector::
    1173              : named_test_bit_vector (bit_vector_manager &bv_mgr,
    1174              :                        const symbolic_bit_size &size_in_bits,
    1175              :                        std::string label)
    1176          128 : : bit_vector (bv_mgr, complexity (1, 1), size_in_bits),
    1177          128 :   m_label (std::move (label))
    1178              : {
    1179          128 : }
    1180              : 
    1181              : void
    1182            8 : named_test_bit_vector::
    1183              : print_prefix_for_dump_widget_label (pretty_printer *pp) const
    1184              : {
    1185            8 :   pp_string (pp, "named_test_bit_vector");
    1186            8 : }
    1187              : 
    1188              : void
    1189            8 : named_test_bit_vector::
    1190              : print_any_suffix_for_dump_widget_label (pretty_printer *pp) const
    1191              : {
    1192            8 :   pp_printf (pp, ": %qs", m_label.c_str ());
    1193            8 : }
    1194              : 
    1195              : void
    1196            8 : named_test_bit_vector::add_dump_widget_children (text_art::tree_widget &,
    1197              :                                                  node_dump_state &) const
    1198              : {
    1199              :   // no-op
    1200            8 : }
    1201              : 
    1202              : void
    1203            0 : named_test_bit_vector::accept_node_visitor (node_visitor &v) const
    1204              : {
    1205            0 :   v.visit_bit_vector (*this);
    1206            0 : }
    1207              : 
    1208              : std::unique_ptr<json::object>
    1209           28 : named_test_bit_vector::to_json () const
    1210              : {
    1211           28 :   auto obj = bit_vector::make_json_obj ("named_test_bit_vector");
    1212           56 :   obj->set_string ("label", m_label);
    1213           28 :   return obj;
    1214              : }
    1215              : 
    1216              : std::unique_ptr<diagnostics::markup::node>
    1217            0 : named_test_bit_vector::make_markup_node (markup_context &) const
    1218              : {
    1219            0 :   return diagnostics::markup::make_text_node (m_label);
    1220              : }
    1221              : 
    1222              : iter_result
    1223            0 : named_test_bit_vector::for_each_svalue (iter_result (*) (const svalue &sval,
    1224              :                                                          void *user_data),
    1225              :                                         void *) const
    1226              : {
    1227            0 :   return iter_result::keep_going;
    1228              : }
    1229              : 
    1230              : #endif /* #if CHECKING_P */
    1231              : 
    1232              : // class empty_bit_vector : public bit_vector
    1233              : 
    1234              : tristate
    1235            0 : empty_bit_vector::get_tristate_at_offset (const symbolic_bit_offset &) const
    1236              : {
    1237              :   /* This should never be called; there are no bits to query.  */
    1238            0 :   gcc_unreachable ();
    1239              : }
    1240              : 
    1241         4409 : empty_bit_vector::empty_bit_vector (bit_vector_manager &bv_mgr)
    1242              : : uniform_bit_vector (bv_mgr,
    1243         4409 :                       complexity (1, 1),
    1244         4409 :                       (bv_mgr.get_node_manager ()
    1245         4409 :                        .get_scalars ().get_bits ().get_concrete (0_bits)))
    1246              : {
    1247         4409 : }
    1248              : 
    1249              : void
    1250            0 : empty_bit_vector::
    1251              : print_prefix_for_dump_widget_label (pretty_printer *pp) const
    1252              : {
    1253            0 :   pp_string (pp, "empty_bit_vector");
    1254            0 : }
    1255              : 
    1256              : void
    1257            0 : empty_bit_vector::add_dump_widget_children (text_art::tree_widget &,
    1258              :                                             node_dump_state &) const
    1259              : {
    1260              :   // No-op
    1261            0 : }
    1262              : 
    1263              : void
    1264           42 : empty_bit_vector::accept_node_visitor (node_visitor &v) const
    1265              : {
    1266           42 :   v.visit_bit_vector (*this);
    1267           42 : }
    1268              : 
    1269              : std::unique_ptr<json::object>
    1270            4 : empty_bit_vector::to_json () const
    1271              : {
    1272            4 :   return bit_vector::make_json_obj ("empty_bit_vector");
    1273              : }
    1274              : 
    1275              : std::unique_ptr<diagnostics::markup::node>
    1276            0 : empty_bit_vector::make_markup_node (markup_context &) const
    1277              : {
    1278            0 :   return diagnostics::markup::make_text_node ("empty_bit_vector");
    1279              : }
    1280              : 
    1281              : iter_result
    1282            0 : empty_bit_vector::for_each_svalue (iter_result (*) (const svalue &sval,
    1283              :                                                     void *user_data),
    1284              :                                    void *) const
    1285              : {
    1286            0 :   return iter_result::keep_going;
    1287              : }
    1288              : 
    1289              : // class poisoned_bit_vector : public bit_vector
    1290              : 
    1291              : bool
    1292      6410033 : poisoned_bit_vector::key::operator< (const key &other) const
    1293              : {
    1294      6410033 :   if (int c = node::cmp (m_size_in_bits, other.m_size_in_bits))
    1295      3104415 :     return c < 0;
    1296      3305618 :   return (int)m_poison_kind < (int)other.m_poison_kind;
    1297              : }
    1298              : 
    1299              : tristate
    1300        22647 : poisoned_bit_vector::get_tristate_at_offset (const symbolic_bit_offset &) const
    1301              : {
    1302        22647 :   return tristate::unknown ();
    1303              : }
    1304              : 
    1305        12436 : poisoned_bit_vector::poisoned_bit_vector (bit_vector_manager &bv_mgr,
    1306              :                                           const key &k)
    1307              : : uniform_bit_vector (bv_mgr,
    1308        12436 :                       complexity (1, 1),
    1309              :                       k.m_size_in_bits),
    1310        12436 :   m_poison_kind (k.m_poison_kind)
    1311              : {
    1312              :   /* The only empty bit_vector should be the singleton empty_bit_vector.  */
    1313        12436 :   gcc_assert (!get_size ().is_zero_p ());
    1314        12436 : }
    1315              : 
    1316              : void
    1317           20 : poisoned_bit_vector::
    1318              : print_prefix_for_dump_widget_label (pretty_printer *pp) const
    1319              : {
    1320           20 :   pp_string (pp, "poisoned_bit_vector");
    1321           20 : }
    1322              : 
    1323              : void
    1324           20 : poisoned_bit_vector::
    1325              : print_any_suffix_for_dump_widget_label (pretty_printer *pp) const
    1326              : {
    1327           20 :   pp_printf (pp, ": %s", poison_kind_to_str (m_poison_kind));
    1328           20 : }
    1329              : 
    1330              : void
    1331           20 : poisoned_bit_vector::add_dump_widget_children (text_art::tree_widget &,
    1332              :                                                node_dump_state &) const
    1333              : {
    1334              :   // no-op
    1335           20 : }
    1336              : 
    1337              : void
    1338        20520 : poisoned_bit_vector::accept_node_visitor (node_visitor &v) const
    1339              : {
    1340        20520 :   v.visit_bit_vector (*this);
    1341        20520 : }
    1342              : 
    1343              : std::unique_ptr<json::object>
    1344            8 : poisoned_bit_vector::to_json () const
    1345              : {
    1346            8 :   auto obj = bit_vector::make_json_obj ("poisoned_bit_vector");
    1347            8 :   obj->set_string ("poison_kind", poison_kind_to_str (m_poison_kind));
    1348            8 :   return obj;
    1349              : }
    1350              : 
    1351              : std::unique_ptr<diagnostics::markup::node>
    1352            0 : poisoned_bit_vector::make_markup_node (markup_context &) const
    1353              : {
    1354            0 :   return diagnostics::markup::make_text_node ("poisoned_bit_vector");
    1355              : }
    1356              : 
    1357              : iter_result
    1358           18 : poisoned_bit_vector::for_each_svalue (iter_result (*) (const svalue &sval,
    1359              :                                                        void *user_data),
    1360              :                                       void *) const
    1361              : {
    1362           18 :   return iter_result::keep_going;
    1363              : }
    1364              : 
    1365              : /* poisoned(x)[m..n] --> poisoned(x, sizeof(m..n)).  */
    1366              : 
    1367              : const bit_vector *
    1368        52766 : poisoned_bit_vector::
    1369              : maybe_fold_crop (const symbolic_bit_range &bits_to_use) const
    1370              : {
    1371        52766 :   return &m_bv_mgr.get_poisoned_bits (bits_to_use.get_size (),
    1372        52766 :                                       get_poison_kind ());
    1373              : }
    1374              : 
    1375              : // class repeated_bit_vector : public bit_vector
    1376              : 
    1377              : bool
    1378         2000 : repeated_bit_vector::key::operator< (const key &other) const
    1379              : {
    1380         2000 :   if (m_inner_bv != other.m_inner_bv)
    1381          834 :     return m_inner_bv->get_id () < other.m_inner_bv->get_id ();
    1382         1166 :   return m_repeat_count < other.m_repeat_count;
    1383              : }
    1384              : 
    1385          294 : repeated_bit_vector::repeated_bit_vector (bit_vector_manager &bv_mgr,
    1386              :                                           const key &k)
    1387              : : bit_vector (bv_mgr,
    1388          294 :               complexity (*k.m_inner_bv),
    1389              :               k.get_size ()),
    1390          294 :   m_inner_bv (*k.m_inner_bv),
    1391          588 :   m_repeat_count (*k.m_repeat_count)
    1392              : {
    1393          294 :   gcc_assert (!m_repeat_count.is_zero_p ());
    1394          294 :   gcc_assert (!m_repeat_count.is_one_p ());
    1395              : 
    1396              :   /* The only empty bit_vector should be the singleton empty_bit_vector.  */
    1397          294 :   gcc_assert (!get_size ().is_zero_p ());
    1398              : 
    1399              :   /* No nesting.  */
    1400          294 :   gcc_assert (!m_inner_bv.dyn_cast_repeated_bit_vector ());
    1401              : 
    1402              :   /* Repetition of a uniform_bit_vector should have been folded
    1403              :      before now.  */
    1404          294 :   gcc_assert (!m_inner_bv.dyn_cast_uniform_bit_vector ());
    1405          294 : }
    1406              : 
    1407              : void
    1408            0 : repeated_bit_vector::
    1409              : print_prefix_for_dump_widget_label (pretty_printer *pp) const
    1410              : {
    1411            0 :   pp_string (pp, "repeated_bit_vector");
    1412            0 : }
    1413              : 
    1414              : void
    1415            0 : repeated_bit_vector::add_dump_widget_children (text_art::tree_widget &w,
    1416              :                                                node_dump_state &nds) const
    1417              : {
    1418            0 :   w.add_child (m_inner_bv.make_dump_widget (nds, "m_inner_bv"));
    1419            0 :   w.add_child (m_repeat_count.make_dump_widget (nds, "m_repeat_count"));
    1420            0 : }
    1421              : 
    1422              : void
    1423       115631 : repeated_bit_vector::accept_node_visitor (node_visitor &v) const
    1424              : {
    1425       115631 :   if (!v.visit_bit_vector (*this))
    1426              :     return;
    1427       115631 :   m_inner_bv.accept_node_visitor (v);
    1428              : }
    1429              : 
    1430              : std::unique_ptr<json::object>
    1431            4 : repeated_bit_vector::to_json () const
    1432              : {
    1433            4 :   auto obj = bit_vector::make_json_obj ("repeated_bit_vector");
    1434            4 :   obj->set ("inner_bv", m_inner_bv.to_json ());
    1435            4 :   obj->set ("repeat_count", m_repeat_count.to_json ());
    1436            4 :   return obj;
    1437              : }
    1438              : 
    1439              : std::unique_ptr<diagnostics::markup::node>
    1440            0 : repeated_bit_vector::make_markup_node (markup_context &) const
    1441              : {
    1442            0 :   return diagnostics::markup::make_text_node ("repeated_bit_vector");
    1443              : }
    1444              : 
    1445              : iter_result
    1446          483 : repeated_bit_vector::for_each_svalue (iter_result (*cb) (const svalue &sval,
    1447              :                                                        void *user_data),
    1448              :                                     void *user_data) const
    1449              : {
    1450          483 :   return m_inner_bv.for_each_svalue (cb, user_data);
    1451              : }
    1452              : 
    1453              : const bit_vector *
    1454         2456 : repeated_bit_vector::
    1455              : maybe_fold_crop (const symbolic_bit_range &bits_to_use) const
    1456              : {
    1457         2456 :   concrete_bit_range conc_bits_to_use;
    1458         2456 :   if (!concrete_from_symbolic (bits_to_use, &conc_bits_to_use))
    1459              :     return nullptr;
    1460              : 
    1461         2456 :   concrete_bit_size conc_bit_size;
    1462         2456 :   if (!concrete_from_symbolic (get_size (), &conc_bit_size))
    1463              :     return nullptr;
    1464              : 
    1465         2456 :   concrete_bit_size conc_inner_bit_size;
    1466         2456 :   if (!concrete_from_symbolic (m_inner_bv.get_size (),
    1467              :                                &conc_inner_bit_size))
    1468              :     return nullptr;
    1469              : 
    1470         2456 :   concrete_bit_size remaining_bits_to_add = conc_bits_to_use.get_size ();
    1471              : 
    1472         2456 :   std::vector<const bit_vector *> vec_of_cropped;
    1473              : 
    1474              :   /* Do we have a leading fragment from one of the iterations?  */
    1475         2456 :   concrete_bit_offset bit_offset_within_repeat
    1476         2456 :     = conc_bits_to_use.get_start_offset ().floor_mod (conc_inner_bit_size);
    1477         2456 :   if (bit_offset_within_repeat > 0_bits)
    1478              :     {
    1479          796 :       concrete_bit_size leading_size
    1480          796 :         = std::min (conc_inner_bit_size - bit_offset_within_repeat,
    1481          796 :                     remaining_bits_to_add);
    1482          796 :       auto &leading_suffix = m_inner_bv.get_cropped_bits
    1483         1592 :         (concrete_bit_range (bit_offset_within_repeat,
    1484         2388 :                              leading_size));
    1485          796 :       vec_of_cropped.push_back (&leading_suffix);
    1486          796 :       remaining_bits_to_add -= leading_size;
    1487          796 :     }
    1488              : 
    1489              :   /* Do we have any full iterations of the inner bv?  */
    1490         2456 :   integer num_full_repeats
    1491         2456 :     = remaining_bits_to_add.floor_div (conc_inner_bit_size);
    1492         2456 :   if (num_full_repeats > 0)
    1493              :     {
    1494         1525 :       auto &full_repeats = m_bv_mgr.get_repeated_bits (m_inner_bv,
    1495              :                                                        num_full_repeats);
    1496         1525 :       vec_of_cropped.push_back (&full_repeats);
    1497         1525 :       remaining_bits_to_add -= (conc_inner_bit_size * num_full_repeats);
    1498              :     }
    1499              : 
    1500              :   /* Do we have a trailing suffix from one of the iterations?  */
    1501         2456 :   if (remaining_bits_to_add > 0_bits)
    1502              :     {
    1503          147 :       gcc_assert (remaining_bits_to_add < conc_inner_bit_size);
    1504          147 :       auto &trailing_prefix
    1505          147 :         = m_inner_bv.get_prefix (remaining_bits_to_add);
    1506          147 :       vec_of_cropped.push_back (&trailing_prefix);
    1507              :     }
    1508              : 
    1509         2456 :   return &m_bv_mgr.get_concat_bits (std::move (vec_of_cropped));
    1510         7368 : }
    1511              : 
    1512              : // class bit_vector_from_svalue : public bit_vector
    1513              : 
    1514              : bool
    1515     31578370 : bit_vector_from_svalue::key::operator< (const key &other) const
    1516              : {
    1517     31578370 :   if (m_sval != other.m_sval)
    1518     31004198 :     return m_sval->get_id () < other.m_sval->get_id ();
    1519              :   return false;
    1520              : }
    1521              : 
    1522              : const symbolic_bit_size &
    1523      1179793 : bit_vector_from_svalue::key::
    1524              : get_size (scalar_manager<concrete_bit_size> &bit_mgr) const
    1525              : {
    1526      1179793 :   concrete_bit_size conc_size;
    1527      1179793 :   bool has_size = m_sval->has_concrete_size_p (&conc_size,
    1528              :                                                bit_mgr);
    1529      1179793 :   gcc_assert (has_size);
    1530      1179793 :   return bit_mgr.get_concrete (conc_size);
    1531      1179793 : }
    1532              : 
    1533              : tristate
    1534        17280 : bit_vector_from_svalue::
    1535              : get_tristate_at_offset (const symbolic_bit_offset &bit) const
    1536              : {
    1537        17280 :   auto &bit_mgr = bit.get_mgr ();
    1538        17280 :   auto &cropped_bit
    1539        17280 :     = get_cropped_bits (symbolic_bit_range (bit, bit_mgr.get_concrete (1_bit)));
    1540        17280 :   if (auto *tristate_bit = cropped_bit.dyn_cast_tristate_bit_vector ())
    1541         8896 :     return tristate_bit->get_bit_value ();
    1542              : 
    1543         8384 :   return tristate::unknown ();
    1544              : }
    1545              : 
    1546      1179793 : bit_vector_from_svalue::bit_vector_from_svalue (bit_vector_manager &bv_mgr,
    1547              :                                                 const key &k)
    1548              : : bit_vector (bv_mgr,
    1549      1179793 :               complexity (*k.m_sval),
    1550      1179793 :               k.get_size (bv_mgr.get_node_manager ()
    1551      1179793 :                           .get_scalars ().get_bits ())),
    1552      2359586 :   m_sval (*k.m_sval)
    1553              : {
    1554              :   /* The only empty bit_vector should be the singleton empty_bit_vector.  */
    1555      1179793 :   gcc_assert (!get_size ().is_zero_p ());
    1556              : 
    1557              :   // No nesting
    1558      1179793 :   gcc_assert (!m_sval.dyn_cast_svalue_from_bit_vector ());
    1559      1179793 : }
    1560              : 
    1561              : void
    1562         1755 : bit_vector_from_svalue::
    1563              : print_prefix_for_dump_widget_label (pretty_printer *pp) const
    1564              : {
    1565         1755 :   pp_string (pp, "bit_vector_from_svalue");
    1566         1755 : }
    1567              : 
    1568              : void
    1569         1755 : bit_vector_from_svalue::
    1570              : add_dump_widget_children (text_art::tree_widget &w,
    1571              :                           node_dump_state &nds) const
    1572              : {
    1573         3510 :   w.add_child (m_sval.make_dump_widget (nds, "m_sval"));
    1574         1755 : }
    1575              : 
    1576              : bool
    1577            0 : bit_vector_from_svalue::
    1578              : maybe_print_for_user (pretty_printer *pp,
    1579              :                       const region_model &model,
    1580              :                       const symbolic::node *outer_node) const
    1581              : {
    1582            0 :   return m_sval.maybe_print_for_user (pp, model, nullptr);
    1583              : }
    1584              : 
    1585              : void
    1586      5190289 : bit_vector_from_svalue::accept_node_visitor (node_visitor &v) const
    1587              : {
    1588      5190289 :   if (!v.visit_bit_vector (*this))
    1589              :     return;
    1590      5190289 :   m_sval.accept_node_visitor (v);
    1591              : }
    1592              : 
    1593              : std::unique_ptr<json::object>
    1594           88 : bit_vector_from_svalue::to_json () const
    1595              : {
    1596           88 :   auto obj = bit_vector::make_json_obj ("bit_vector_from_svalue");
    1597           88 :   obj->set ("sval", m_sval.to_json ());
    1598           88 :   return obj;
    1599              : }
    1600              : 
    1601              : std::unique_ptr<diagnostics::markup::node>
    1602            0 : bit_vector_from_svalue::make_markup_node (markup_context &markup_ctxt) const
    1603              : {
    1604            0 :   return m_sval.make_markup_node (markup_ctxt);
    1605              : }
    1606              : 
    1607              : iter_result
    1608         6895 : bit_vector_from_svalue::for_each_svalue (iter_result (*cb) (const svalue &sval,
    1609              :                                                             void *user_data),
    1610              :                                          void *user_data) const
    1611              : {
    1612         6895 :   return m_sval.for_each_svalue (cb, user_data);
    1613              : }
    1614              : 
    1615              : const bit_vector *
    1616        25808 : bit_vector_from_svalue::
    1617              : maybe_fold_crop (const symbolic_bit_range &bits_to_use) const
    1618              : {
    1619        25808 :   concrete_bit_range conc_bits_to_use;
    1620        25808 :   if (!concrete_from_symbolic (bits_to_use, &conc_bits_to_use))
    1621              :     return nullptr;
    1622              : 
    1623        25808 :   if (auto *folded = maybe_fold_crop_from_cst (conc_bits_to_use))
    1624              :     return folded;
    1625              : 
    1626        12148 :   if (auto *folded = maybe_fold_crop_from_bitmask (conc_bits_to_use))
    1627              :     return folded;
    1628              : 
    1629              :   return nullptr;
    1630        25808 : }
    1631              : 
    1632              : const bit_vector *
    1633        25808 : bit_vector_from_svalue::
    1634              : maybe_fold_crop_from_cst (const concrete_bit_range &inner_bits_to_use) const
    1635              : {
    1636              :   /* Attempt to extract bytes from constants.  */
    1637        25808 :   tree tree_cst  = m_sval.maybe_get_constant ();
    1638        25808 :   if (!tree_cst)
    1639        12990 :     if (auto *init_sval = m_sval.dyn_cast_initial_svalue ())
    1640        12152 :       if (auto *string_reg
    1641        12152 :           = init_sval->get_region ()->dyn_cast_string_region ())
    1642         1160 :         tree_cst = string_reg->get_string_cst ();
    1643        12990 :   if (!tree_cst)
    1644              :     return nullptr;
    1645              : 
    1646        13978 :   concrete_byte_range conc_bytes_to_use;
    1647        13978 :   concrete_bit_offset bit_offset;
    1648        13978 :   get_smallest_enclosing_byte_range (inner_bits_to_use,
    1649              :                                      &conc_bytes_to_use,
    1650              :                                      &bit_offset);
    1651        13978 :   gcc_assert (bit_offset < 8_bits);
    1652        27956 :   if (auto p = m_bv_mgr.maybe_fold_bytes_within_constant (tree_cst,
    1653              :                                                        conc_bytes_to_use))
    1654              :     {
    1655        13660 :       auto effective_size = inner_bits_to_use.get_size ();
    1656        13660 :       if (p == this)
    1657              :         {
    1658              :           /* We're looking at bits within one of the m_cached_bytes
    1659              :              instances; we need to avoid infinite recursion.  */
    1660         9291 :           gcc_assert (TREE_TYPE (tree_cst) == unsigned_char_type_node);
    1661         9291 :           gcc_assert (effective_size < 8_bits);
    1662         9291 :           int byte_val = TREE_INT_CST_LOW (tree_cst);
    1663         9291 :           gcc_assert (this == &m_bv_mgr.get_uint8 (byte_val));
    1664         9291 :           std::vector<const symbolic::bit_vector *> raw_bits;
    1665         9291 :           int idx_after_bits
    1666         9291 :             = bit_offset.as_long () + effective_size.as_long ();
    1667         9291 :           for (int bit_idx = bit_offset.as_long ();
    1668        18582 :                bit_idx < idx_after_bits; ++bit_idx)
    1669              :             {
    1670              :               /* Add in LSB through MSB order.  */
    1671         9291 :               bool bit_val = byte_val & (1 << bit_idx);
    1672         9291 :               raw_bits.push_back
    1673        14091 :                 (&m_bv_mgr.get_tristate_bits (1_bit, tristate (bit_val)));
    1674              :             }
    1675         9291 :           return &m_bv_mgr.get_concat_bits (std::move (raw_bits));
    1676         9291 :         }
    1677              :       else
    1678         4369 :         return &p->get_cropped_bits
    1679        13107 :           (concrete_bit_range (bit_offset, effective_size));
    1680        13660 :     }
    1681              : 
    1682              :   return nullptr;
    1683        27956 : }
    1684              : 
    1685              : const bit_vector *
    1686        12148 : bit_vector_from_svalue::
    1687              : maybe_fold_crop_from_bitmask (const concrete_bit_range &inner_bits_to_use) const
    1688              : {
    1689        12148 :   if (inner_bits_to_use.get_next_offset () > 64_bits)
    1690              :     return nullptr;
    1691              : 
    1692         8209 :   value_range vr;
    1693         8209 :   if (!m_sval.maybe_get_value_range (vr))
    1694              :     return nullptr;
    1695              : 
    1696          885 :   irange_bitmask bitmask = vr.get_bitmask ();
    1697              : 
    1698              :   /* The unknown bits are those for which the mask is one.
    1699              :      Bail out if we have any unknown bits in the bit_range of interest.  */
    1700          885 :   unsigned HOST_WIDE_INT mask_for_bits
    1701              :     = wi::extract_uhwi
    1702          885 :         (bitmask.mask (),
    1703         1955 :          inner_bits_to_use.get_start_offset ().as_unsigned_long (),
    1704          885 :          inner_bits_to_use.get_size ().as_unsigned_long ());
    1705          885 :   if (mask_for_bits != 0)
    1706              :     return nullptr;
    1707              : 
    1708              :   // We have known bits; get their value.
    1709          456 :   unsigned HOST_WIDE_INT known_value
    1710              :     = wi::extract_uhwi
    1711          456 :         (bitmask.value (),
    1712          928 :          inner_bits_to_use.get_start_offset ().as_unsigned_long (),
    1713          456 :          inner_bits_to_use.get_size ().as_unsigned_long ());
    1714          456 :   if (inner_bits_to_use.get_size ().is_one_p ())
    1715          720 :     return &m_bv_mgr.get_tristate_bits (1_bit, known_value != 0);
    1716           32 :   else if (inner_bits_to_use.get_size () == 8_bits)
    1717           32 :     return &m_bv_mgr.get_uint8 (known_value);
    1718              :   else
    1719              :     return nullptr;
    1720         8209 : }
    1721              : 
    1722              : bool
    1723          704 : bit_vector_from_svalue::
    1724              : implicitly_live_p (symbolic::liveness_context &liveness_ctxt) const
    1725              : {
    1726          704 :   return liveness_ctxt.node_live_p (m_sval);
    1727              : }
    1728              : 
    1729              : // class bit_vector_from_ubc : public bit_vector
    1730              : 
    1731              : tristate
    1732       222076 : bit_vector_from_ubc::
    1733              : get_tristate_at_offset (const symbolic_bit_offset &) const
    1734              : {
    1735       222076 :   return tristate::unknown ();
    1736              : }
    1737              : 
    1738        14543 : bit_vector_from_ubc::
    1739              : bit_vector_from_ubc (const unfoldable_bit_contents &bc,
    1740              :                      symbolic_bit_range bit_range)
    1741        14543 : : bit_vector (bc.get_node_mgr ().get_bit_vector_manager (),
    1742              :               complexity::from_pair
    1743              :                 (bc.get_complexity (),
    1744        29086 :                  bit_range.get_children_complexity ()),
    1745              :               // FIXME: what about symbolic?
    1746        14543 :               bit_range.get_size ()),
    1747        14543 :   m_unfoldable_bit_contents (bc),
    1748        14543 :   m_bit_range (bit_range)
    1749              : {
    1750              :   /* The only empty bit_vector should be the singleton empty_bit_vector.  */
    1751        14543 :   gcc_assert (!get_size ().is_zero_p ());
    1752        14543 : }
    1753              : 
    1754              : void
    1755          587 : bit_vector_from_ubc::
    1756              : print_prefix_for_dump_widget_label (pretty_printer *pp) const
    1757              : {
    1758          587 :   pp_string (pp, "bit_vector_from_ubc");
    1759          587 : }
    1760              : 
    1761              : void
    1762          576 : bit_vector_from_ubc::
    1763              : add_dump_widget_children (text_art::tree_widget &w,
    1764              :                           node_dump_state &nds) const
    1765              : {
    1766          576 :   w.add_child
    1767         1152 :     (m_unfoldable_bit_contents.make_dump_widget (nds, "bit_contents"));
    1768         1152 :   w.add_child (m_bit_range.make_dump_widget (nds, "range"));
    1769          576 : }
    1770              : 
    1771              : void
    1772     14424718 : bit_vector_from_ubc::accept_node_visitor (node_visitor &v) const
    1773              : {
    1774     14424718 :   if (!v.visit_bit_vector (*this))
    1775              :     return;
    1776     14424718 :   m_unfoldable_bit_contents.accept_node_visitor (v);
    1777     14424718 :   m_bit_range.accept_node_visitor (v);
    1778              : }
    1779              : 
    1780              : bool
    1781       126343 : bit_vector_from_ubc::conjured_p () const
    1782              : {
    1783       126343 :   return m_unfoldable_bit_contents.conjured_p ();
    1784              : }
    1785              : 
    1786              : std::unique_ptr<json::object>
    1787            0 : bit_vector_from_ubc::to_json () const
    1788              : {
    1789            0 :   auto obj
    1790            0 :     = bit_vector::make_json_obj ("bit_vector_from_ubc");
    1791            0 :   obj->set ("bit_contents", m_unfoldable_bit_contents.to_json ());
    1792            0 :   obj->set ("bit_range", m_bit_range.to_json ());
    1793            0 :   return obj;
    1794              : }
    1795              : 
    1796              : std::unique_ptr<diagnostics::markup::node>
    1797            0 : bit_vector_from_ubc::make_markup_node (markup_context &) const
    1798              : {
    1799            0 :   return diagnostics::markup::make_text_node ("bit_vector_from_ubc");
    1800              : }
    1801              : 
    1802              : iter_result
    1803        14559 : bit_vector_from_ubc::for_each_svalue (iter_result (*) (const svalue &sval,
    1804              :                                                        void *user_data),
    1805              :                                       void *) const
    1806              : {
    1807        14559 :   return iter_result::keep_going;
    1808              : }
    1809              : 
    1810              : bool
    1811       287978 : bit_vector_from_ubc::
    1812              : implicitly_live_p (symbolic::liveness_context &liveness_ctxt) const
    1813              : {
    1814       287978 :   return liveness_ctxt.bits_live_p (*this);
    1815              : }
    1816              : 
    1817              : /* crop(bit_vector_from_ubc (UBC, RANGE), SUBRANGE)
    1818              :    --> bit_vector_from_ubc (UBC, SUBRANGE OF RANGE).  */
    1819              : 
    1820              : const bit_vector *
    1821        81571 : bit_vector_from_ubc::
    1822              : maybe_fold_crop (const symbolic_bit_range &bits_to_use) const
    1823              : {
    1824        81571 :   auto &result_size = bits_to_use.get_size ();
    1825        81571 :   symbolic_bit_range subrange
    1826        81571 :     (get_bit_range ().get_start_offset ()
    1827              :      + bits_to_use.get_start_offset (),
    1828        81571 :      result_size);
    1829        81571 :   return &get_bit_contents ().get_bits (subrange);
    1830              : }
    1831              : 
    1832              : // class tristate_bit_vector : public bit_vector
    1833              : 
    1834              : bool
    1835      2505688 : tristate_bit_vector::key::operator< (const key &other) const
    1836              : {
    1837      2505688 :   if (int c = node::cmp (m_size_in_bits, other.m_size_in_bits))
    1838       686638 :     return c < 0;
    1839      1819050 :   return (static_cast<int> (m_bit_value.get_value ())
    1840      1819050 :           < static_cast<int> (other.m_bit_value.get_value ()));
    1841              : }
    1842              : 
    1843              : tristate
    1844          633 : tristate_bit_vector::get_tristate_at_offset (const symbolic_bit_offset &) const
    1845              : {
    1846          633 :   return m_bit_value;
    1847              : }
    1848              : 
    1849        19441 : tristate_bit_vector::tristate_bit_vector (bit_vector_manager &bv_mgr,
    1850              :                                           const key &k)
    1851        19441 : : uniform_bit_vector (bv_mgr, complexity (1, 1), k.m_size_in_bits),
    1852        19441 :   m_bit_value (k.m_bit_value)
    1853              : {
    1854              :   /* The only empty bit_vector should be the singleton empty_bit_vector.  */
    1855        19441 :   gcc_assert (!get_size ().is_zero_p ());
    1856        19441 : }
    1857              : 
    1858              : void
    1859          363 : tristate_bit_vector::
    1860              : print_prefix_for_dump_widget_label (pretty_printer *pp) const
    1861              : {
    1862          363 :   pp_string (pp, "tristate_bit_vector");
    1863          363 : }
    1864              : 
    1865              : void
    1866          363 : tristate_bit_vector::
    1867              : print_any_suffix_for_dump_widget_label (pretty_printer *pp) const
    1868              : {
    1869          363 :   pp_string (pp, ": ");
    1870          363 :   if (m_size_in_bits.is_one_p ())
    1871           12 :     switch (m_bit_value.get_value ())
    1872              :       {
    1873            0 :       default:
    1874            0 :         gcc_unreachable ();
    1875            4 :       case tristate::TS_UNKNOWN:
    1876            4 :         pp_string (pp, "unknown bit");
    1877            4 :         break;
    1878            4 :       case tristate::TS_TRUE:
    1879            4 :         pp_string (pp, "true bit");
    1880            4 :         break;
    1881            4 :       case tristate::TS_FALSE:
    1882            4 :         pp_string (pp, "false bit");
    1883            4 :         break;
    1884              :       }
    1885              :   else
    1886          351 :     switch (m_bit_value.get_value ())
    1887              :       {
    1888            0 :       default:
    1889            0 :         gcc_unreachable ();
    1890          152 :       case tristate::TS_UNKNOWN:
    1891          152 :         pp_string (pp, "unknown bits");
    1892          152 :         break;
    1893           16 :       case tristate::TS_TRUE:
    1894           16 :         pp_string (pp, "true bits");
    1895           16 :         break;
    1896          183 :       case tristate::TS_FALSE:
    1897          183 :         pp_string (pp, "false bits");
    1898          183 :         break;
    1899              :       }
    1900          363 : }
    1901              : 
    1902              : void
    1903          363 : tristate_bit_vector::add_dump_widget_children (text_art::tree_widget &,
    1904              :                                                node_dump_state &) const
    1905              : {
    1906              :   // no-op
    1907          363 : }
    1908              : 
    1909              : void
    1910      1859495 : tristate_bit_vector::accept_node_visitor (node_visitor &v) const
    1911              : {
    1912      1859495 :   v.visit_bit_vector (*this);
    1913      1859495 : }
    1914              : 
    1915              : std::unique_ptr<json::object>
    1916           40 : tristate_bit_vector::to_json () const
    1917              : {
    1918           40 :   auto obj = bit_vector::make_json_obj ("tristate_bit_vector");
    1919           40 :   obj->set_string ("bit_value", m_bit_value.as_string ());
    1920           40 :   return obj;
    1921              : }
    1922              : 
    1923              : std::unique_ptr<diagnostics::markup::node>
    1924            0 : tristate_bit_vector::make_markup_node (markup_context &) const
    1925              : {
    1926            0 :   return diagnostics::markup::make_text_node ("tristate_bit_vector");
    1927              : }
    1928              : 
    1929              : iter_result
    1930         1925 : tristate_bit_vector::for_each_svalue (iter_result (*) (const svalue &sval,
    1931              :                                                        void *user_data),
    1932              :                                       void *) const
    1933              : {
    1934         1925 :   return iter_result::keep_going;
    1935              : }
    1936              : 
    1937              : /* tristate(x)[m..n] --> tristate(x, sizeof(m..n)).  */
    1938              : 
    1939              : const bit_vector *
    1940       252652 : tristate_bit_vector::
    1941              : maybe_fold_crop (const symbolic_bit_range &bits_to_use) const
    1942              : {
    1943       252652 :   return &m_bv_mgr.get_tristate_bits (bits_to_use.get_size (),
    1944       252652 :                                       get_bit_value ());
    1945              : }
    1946              : 
    1947              : /* symbolic::bit_vector consolidation.  */
    1948              : 
    1949         4409 : bit_vector_manager::bit_vector_manager (node_manager &node_mgr)
    1950         4409 : : m_node_mgr (node_mgr),
    1951         4409 :   m_empty_bv (*this)
    1952              : {
    1953              :   // Populate m_cached_bytes
    1954         4409 :   memset (m_cached_bytes, 0, sizeof (m_cached_bytes));
    1955         4409 :   m_cached_bytes[0x00] = &get_all_zeros (1_byte);
    1956      1124295 :   for (int i = 1; i < 255; ++i)
    1957              :     {
    1958      1119886 :       auto &rmm = node_mgr.get_region_model_manager ();
    1959      1119886 :       auto &sval = *rmm.get_or_create_int_cst (unsigned_char_type_node, i);
    1960      1119886 :       m_cached_bytes[i] = &get_bit_vector_from_svalue (sval);
    1961              :     }
    1962         4409 :   m_cached_bytes[0xff] = &get_all_ones (1_byte);
    1963         4409 : }
    1964              : 
    1965              : 
    1966              : const bit_vector &
    1967       634391 : bit_vector_manager::get_tristate_bits (const symbolic_bit_size &num_bits,
    1968              :                                        tristate bit_val)
    1969              : {
    1970       634391 :   if (num_bits.is_zero_p ())
    1971            4 :     return m_empty_bv;
    1972              : 
    1973       634387 :   const symbolic::tristate_bit_vector::key k {num_bits, bit_val};
    1974       634387 :   auto iter = m_tristate_map.find (k);
    1975       634387 :   if (iter != m_tristate_map.end ())
    1976       614946 :     return *(iter->second);
    1977        19441 :   auto bv_up = std::make_unique<symbolic::tristate_bit_vector> (*this, k);
    1978        19441 :   auto &result = *bv_up.get ();
    1979        19441 :   m_tristate_map.insert ({k, std::move (bv_up)});
    1980        19441 :   return result;
    1981        19441 : }
    1982              : 
    1983              : const bit_vector &
    1984       268758 : bit_vector_manager::get_tristate_bits (const concrete_bit_size &num_bits,
    1985              :                                        tristate bit_val)
    1986              : {
    1987       268758 :   return get_tristate_bits (symbolic_from_concrete (num_bits,
    1988              :                                                     get_bit_manager ()),
    1989       268758 :                             bit_val);
    1990              : }
    1991              : 
    1992              :   // Unknown bits of unknown length
    1993              : const bit_vector &
    1994          326 : bit_vector_manager::get_unknown_bits ()
    1995              : {
    1996          326 :   const symbolic_bit_size &unknown_size = get_bit_manager ().get_unknown ();
    1997          326 :   return get_tristate_bits (unknown_size, tristate::unknown ());
    1998              : }
    1999              : 
    2000              : static void
    2001      2275453 : append_canonically (std::vector<const bit_vector *> &canonical_bvs,
    2002              :                     const bit_vector &bv_to_add,
    2003              :                     bit_vector_manager &bv_mgr)
    2004              : {
    2005      2275453 :   if (bv_to_add.get_size ().is_zero_p ())
    2006              :     return;
    2007              : 
    2008              :   /* Flatten adding concat bit_vectors.  */
    2009      2275437 :   if (auto concat_bv = bv_to_add.dyn_cast_concat_bit_vector ())
    2010              :     {
    2011          184 :       for (auto iter : *concat_bv)
    2012          128 :         append_canonically (canonical_bvs, *iter, bv_mgr);
    2013              :       return;
    2014              :     }
    2015              : 
    2016      2275381 :   if (!canonical_bvs.empty ())
    2017              :     {
    2018              :       /* Check for merging opportunities.  */
    2019        41876 :       auto &back = canonical_bvs.back ();
    2020        41876 :       gcc_assert (back);
    2021              : 
    2022              :       /* A + A --> A * 2  */
    2023        41876 :       if (&bv_to_add == back)
    2024              :         {
    2025          821 :           back = &bv_mgr.get_repeated_bits (bv_to_add, 2);
    2026          821 :           return;
    2027              :         }
    2028              : 
    2029              :       /* (A * n) + A --> A * (n + 1).  */
    2030        41055 :       if (auto repeated_bv = back->dyn_cast_repeated_bit_vector ())
    2031          787 :         if (&repeated_bv->get_inner_bit_vector () == &bv_to_add)
    2032              :           {
    2033           17 :             auto &unitless_mgr
    2034           17 :               = bv_mgr.get_node_manager ().get_scalars ().get_unitless ();
    2035           34 :             back = &bv_mgr.get_repeated_bits
    2036           17 :               (repeated_bv->get_inner_bit_vector (),
    2037           17 :                (repeated_bv->get_repeat_count ()
    2038           17 :                 + unitless_mgr.get_concrete (1)));
    2039           17 :             return;
    2040              :           }
    2041              : 
    2042              :       /* A + (A * n) --> A * (n + 1).  */
    2043        41038 :       if (auto repeated_bv = bv_to_add.dyn_cast_repeated_bit_vector ())
    2044          708 :         if (back == &repeated_bv->get_inner_bit_vector ())
    2045              :           {
    2046            4 :             auto &unitless_mgr
    2047            4 :               = bv_mgr.get_node_manager ().get_scalars ().get_unitless ();
    2048            8 :             back = &bv_mgr.get_repeated_bits
    2049            4 :               (repeated_bv->get_inner_bit_vector (),
    2050            4 :                (repeated_bv->get_repeat_count ()
    2051            4 :                 + unitless_mgr.get_concrete (1)));
    2052            4 :             return;
    2053              :           }
    2054              : 
    2055              :       /* (A * m) + (A * n) --> A * (m + n).  */
    2056        41034 :       if (auto repeated_lhs = back->dyn_cast_repeated_bit_vector ())
    2057          770 :         if (auto repeated_rhs = bv_to_add.dyn_cast_repeated_bit_vector ())
    2058          166 :           if (&repeated_lhs->get_inner_bit_vector ()
    2059          166 :               == &repeated_rhs->get_inner_bit_vector ())
    2060              :             {
    2061            4 :               back = &bv_mgr.get_repeated_bits
    2062            4 :                 (repeated_lhs->get_inner_bit_vector (),
    2063            4 :                  (repeated_lhs->get_repeat_count ()
    2064            4 :                   + repeated_rhs->get_repeat_count ()));
    2065            4 :               return;
    2066              :             }
    2067              : 
    2068              :       /* concat(A[p, q], A[q, r]) --> A[p, r].  */
    2069        41030 :       if (auto cropped_lhs = back->dyn_cast_cropped_bit_vector ())
    2070          359 :         if (auto cropped_rhs = bv_to_add.dyn_cast_cropped_bit_vector ())
    2071           52 :           if ((&cropped_lhs->get_uncropped_bit_vector ()
    2072           52 :                == &cropped_rhs->get_uncropped_bit_vector ())
    2073           52 :               && (&cropped_lhs->get_uncropped_bits_to_use ().get_next_offset ()
    2074           17 :                   == &cropped_rhs->get_uncropped_bits_to_use ().get_start_offset ()))
    2075              :             {
    2076            9 :               symbolic_bit_range concat_bit_range
    2077            9 :                 (cropped_lhs->get_uncropped_bits_to_use ().get_start_offset (),
    2078            9 :                  cropped_lhs->get_size () + cropped_rhs->get_size ());
    2079            9 :               back = &bv_mgr.get_cropped_bits (cropped_lhs->get_uncropped_bit_vector (),
    2080              :                                                concat_bit_range);
    2081            9 :               return;
    2082              :             }
    2083              : 
    2084              :       /* poisoned(m, X) + poisoned(n, X) --> poisoned(m + n, X)
    2085              :          for same kind of poison.  */
    2086        41021 :       if (auto poisoned_lhs = back->dyn_cast_poisoned_bit_vector ())
    2087          421 :         if (auto poisoned_rhs = bv_to_add.dyn_cast_poisoned_bit_vector ())
    2088           47 :           if (poisoned_lhs->get_poison_kind () == poisoned_rhs->get_poison_kind ())
    2089              :             {
    2090           86 :               back = &bv_mgr.get_poisoned_bits
    2091           43 :                 ((poisoned_lhs->get_size ()
    2092           43 :                   + poisoned_rhs->get_size ()),
    2093              :                  poisoned_lhs->get_poison_kind ());
    2094           43 :               return;
    2095              :             }
    2096              : 
    2097              :       /* tristate(m, X) + tristate(n, X) --> tristate(m + n, X).  */
    2098        40978 :       if (auto tristate_lhs = back->dyn_cast_tristate_bit_vector ())
    2099         4302 :         if (auto tristate_rhs = bv_to_add.dyn_cast_tristate_bit_vector ())
    2100         1692 :           if (tristate_lhs->get_bit_value () == tristate_rhs->get_bit_value ())
    2101              :             {
    2102         1339 :               back = &bv_mgr.get_tristate_bits
    2103         1339 :                 ((tristate_lhs->get_size ()
    2104         1339 :                   + tristate_rhs->get_size ()),
    2105              :                  tristate_lhs->get_bit_value ());
    2106         1339 :               return;
    2107              :             }
    2108              : 
    2109              :       /* bits_from_ubc (BC, R1) + bits_from_ubc (BC, R2)
    2110              :          --> bits_from_ubc (BC, R1 + R2)
    2111              :          if it's the same BC and the ranges touch.  */
    2112        39639 :       if (auto from_ubc_lhs = back->dyn_cast_bit_vector_from_ubc ())
    2113          455 :         if (auto from_ubc_rhs = bv_to_add.dyn_cast_bit_vector_from_ubc ())
    2114           27 :           if (&from_ubc_lhs->get_bit_contents ()
    2115           27 :               == &from_ubc_rhs->get_bit_contents ())
    2116           15 :             if (&from_ubc_lhs->get_bit_range ().get_next_offset ()
    2117           15 :                 == &from_ubc_rhs->get_bit_range ().get_start_offset ())
    2118              :               {
    2119           11 :                 symbolic_bit_range combined_bit_range
    2120           11 :                   (from_ubc_lhs->get_bit_range ().get_start_offset (),
    2121           11 :                    (from_ubc_lhs->get_bit_range ().get_size ()
    2122           11 :                     + from_ubc_rhs->get_bit_range ().get_size ()));
    2123           11 :                 auto &ubc = from_ubc_lhs->get_bit_contents ();
    2124           11 :                 back = &ubc.get_bits (combined_bit_range);
    2125           11 :                 return;
    2126              :               }
    2127              :     }
    2128              : 
    2129      2273133 :   canonical_bvs.push_back (&bv_to_add);
    2130              : }
    2131              : 
    2132              : /* Simplify BIT_VECTORS into a canonical form.  */
    2133              : 
    2134              : std::vector<const bit_vector *>
    2135      2233509 : bit_vector_manager::
    2136              : canonicalize_concat_bits (const std::vector<const bit_vector *> &bvs)
    2137              : {
    2138      2233509 :   std::vector<const bit_vector *> result;
    2139      4508834 :   for (auto iter : bvs)
    2140      2275325 :     append_canonically (result, *iter, *this);
    2141      2233509 :   return result;
    2142              : }
    2143              : 
    2144              : const bit_vector *
    2145      2233505 : bit_vector_manager::
    2146              : maybe_fold_concat_bits (const std::vector<const bit_vector *> &canonical_bvs)
    2147              : {
    2148              :   /* Unwrap single element: concat(X) --> X.  */
    2149      2233505 :   if (canonical_bvs.size () == 1)
    2150      2196641 :     return canonical_bvs[0];
    2151              : 
    2152              :   return nullptr;
    2153              : }
    2154              : 
    2155              : const bit_vector &
    2156      2233512 : bit_vector_manager::
    2157              : get_concat_bits (std::vector<const bit_vector *> bvs)
    2158              : {
    2159      2233512 :   if (bvs.size () == 0)
    2160            3 :     return m_empty_bv;
    2161              : 
    2162              :   /* Simplify into a canonical form.  */
    2163      2233509 :   auto canonical_bvs = canonicalize_concat_bits (bvs);
    2164      2233509 :   if (canonical_bvs.size () == 0)
    2165            4 :     return m_empty_bv;
    2166              : 
    2167      2233505 :   if (auto *folded = maybe_fold_concat_bits (canonical_bvs))
    2168              :     return *folded;
    2169              : 
    2170        36864 :   const symbolic::concat_bit_vector::key k (std::move (canonical_bvs));
    2171        36864 :   auto iter = m_concat_map.find (k);
    2172        36864 :   if (iter != m_concat_map.end ())
    2173        32755 :     return *(iter->second);
    2174              : 
    2175         4109 :   auto bv_up = std::make_unique<symbolic::concat_bit_vector> (*this, k);
    2176         4109 :   auto &result = *bv_up.get ();
    2177         4109 :   m_concat_map.insert ({k, std::move (bv_up)});
    2178         4109 :   return result;
    2179      2274482 : }
    2180              : 
    2181              : const bit_vector &
    2182        26132 : bit_vector_manager::get_conjured_bits (const gimple *stmt,
    2183              :                                        const region *id_reg,
    2184              :                                        const conjured_purge &p,
    2185              :                                        unsigned idx)
    2186              : {
    2187        26132 :   const symbolic::conjured_bit_vector::key k (stmt, id_reg, idx);
    2188        26132 :   auto iter = m_conjured_map.find (k);
    2189        26132 :   if (iter != m_conjured_map.end ())
    2190              :     {
    2191        11572 :       auto &bv = iter->second;
    2192              :       /* We're reusing an existing conjured_bit_vector, perhaps from a different
    2193              :          state within this analysis, or perhaps from an earlier state on this
    2194              :          execution path.  For the latter, purge any state involving the "new"
    2195              :          bit_vector from the current program_state.  */
    2196        11572 :       p.purge (*bv);
    2197        11572 :       return *bv;
    2198              :     }
    2199        14560 :   auto bv_up = std::make_unique<symbolic::conjured_bit_vector> (*this, k);
    2200        14560 :   auto &result = *bv_up.get ();
    2201        14560 :   m_conjured_map.insert ({k, std::move (bv_up)});
    2202        14560 :   return result;
    2203        14560 : }
    2204              : 
    2205              : const bit_vector *
    2206      1338349 : bit_vector_manager::maybe_fold_bits_for_constant (tree tree_cst)
    2207              : {
    2208      1338349 :   gcc_assert (tree_cst);
    2209              : 
    2210      1338349 :   switch (TREE_CODE (tree_cst))
    2211              :     {
    2212              :     default:
    2213              :       break;
    2214              : 
    2215      1337082 :     case INTEGER_CST:
    2216      1337082 :       {
    2217      1337082 :         bit_size_t size;
    2218      1337082 :         bool got_size = int_size_in_bits (TREE_TYPE (tree_cst),  &size);
    2219      1337082 :         gcc_assert (got_size);
    2220              : 
    2221      1337082 :         integer_with_unit<units::bit> num_bits = convert_from_bit_size_t (size);
    2222              : 
    2223              :         /* Fold all-zeroes and all-ones.  */
    2224      1337082 :         if (zerop (tree_cst))
    2225       115716 :           return &get_all_zeros (num_bits);
    2226      1221366 :         if (integer_all_onesp (tree_cst))
    2227        10484 :           return &get_all_ones (num_bits);
    2228              : 
    2229              :         /* Fold bytes.  */
    2230      1210882 :         if (num_bits == 8_bits)
    2231              :           {
    2232      1120274 :             uint8_t val = TREE_INT_CST_LOW (tree_cst);
    2233      1120274 :             if (auto *b = m_cached_bytes[val])
    2234              :               return b;
    2235              :           }
    2236       130906 :       }
    2237      1206176 :       break;
    2238              : 
    2239           42 :     case RAW_DATA_CST:
    2240           42 :       if (RAW_DATA_LENGTH (tree_cst) == 0)
    2241            4 :         return &m_empty_bv;
    2242              :       break;
    2243              :     }
    2244              :   return nullptr;
    2245              : }
    2246              : 
    2247              : const bit_vector &
    2248          120 : bit_vector_manager::get_bits_for_constant (tree tree_cst)
    2249              : {
    2250          120 :   if (auto *folded = maybe_fold_bits_for_constant (tree_cst))
    2251              :     return *folded;
    2252              : 
    2253           48 :   const svalue *sval
    2254           48 :     = get_svalue_manager ().get_or_create_constant_svalue (tree_cst);
    2255           48 :   return get_bit_vector_from_svalue (*sval);
    2256              : }
    2257              : 
    2258              : const bit_vector *
    2259        13978 : bit_vector_manager::
    2260              : maybe_fold_bytes_within_constant (tree tree_cst,
    2261              :                                   concrete_byte_range conc_bytes)
    2262              : {
    2263        13978 :   gcc_assert (tree_cst);
    2264        13978 :   gcc_assert (CONSTANT_CLASS_P (tree_cst));
    2265        27956 :   gcc_assert (conc_bytes.get_start_offset () >= 0_bytes);
    2266              : 
    2267        13978 :   switch (TREE_CODE (tree_cst))
    2268              :     {
    2269              :     default:
    2270              :       return nullptr;
    2271              : 
    2272              :     /* Special-case these.  */
    2273         1821 :     case STRING_CST:
    2274         3642 :       return maybe_fold_bytes_within_string_cst (tree_cst, conc_bytes);
    2275          194 :     case RAW_DATA_CST:
    2276          388 :       return maybe_fold_bytes_within_raw_data_cst (tree_cst, conc_bytes);
    2277              : 
    2278              :     /* Handle the constants that native_encode_expr can.  */
    2279        11963 :     case INTEGER_CST:
    2280        11963 :     case REAL_CST:
    2281        11963 :     case FIXED_CST:
    2282        11963 :     case COMPLEX_CST:
    2283        11963 :     case VECTOR_CST:
    2284        11963 :     case CONSTRUCTOR:
    2285        11963 :       {
    2286              :         /* Use native_encode_expr and extract the pertinent byte(s).  */
    2287        11963 :         unsigned char buf[MAX_BITSIZE_MODE_ANY_MODE / BITS_PER_UNIT];
    2288        11963 :         int size = native_encode_expr (tree_cst, buf, sizeof buf, 0);
    2289        11963 :         if (size == 0)
    2290              :           return nullptr;
    2291              : 
    2292        23926 :         gcc_assert (conc_bytes.get_last_offset () < concrete_byte_size (size));
    2293              : 
    2294        11963 :         std::vector<const bit_vector *> vec_of_bytes;
    2295        11963 :         const concrete_byte_offset next_offset = conc_bytes.get_next_offset ();
    2296        11963 :         for (concrete_byte_offset conc_offset = conc_bytes.get_start_offset ();
    2297        24130 :              conc_offset < next_offset;
    2298        12167 :              conc_offset += 1_byte)
    2299        12167 :           vec_of_bytes.push_back
    2300        12167 :             (&get_uint8 (buf[conc_offset.as_unsigned_long ()]));
    2301              : 
    2302        11963 :         return &get_concat_bits (std::move (vec_of_bytes));
    2303        11963 :       }
    2304              :     }
    2305              : }
    2306              : 
    2307              : const bit_vector *
    2308         1821 : bit_vector_manager::
    2309              : maybe_fold_bytes_within_string_cst (tree string_cst,
    2310              :                                     concrete_byte_range conc_bytes)
    2311              : {
    2312         1821 :   gcc_assert (TREE_CODE (string_cst) == STRING_CST);
    2313              : 
    2314              :   /* Adapted from fold_read_from_constant_string.  */
    2315         1821 :   scalar_int_mode char_mode;
    2316         1821 :   if (!is_int_mode (TYPE_MODE (TREE_TYPE (TREE_TYPE (string_cst))),
    2317              :                     &char_mode))
    2318              :     return nullptr;
    2319         3642 :   if (GET_MODE_SIZE (char_mode) != 1)
    2320              :     return nullptr;
    2321              : 
    2322         3642 :   gcc_assert (conc_bytes.get_start_offset () >= 0_bytes);
    2323         3642 :   if (conc_bytes.get_start_offset ()
    2324         3642 :       < integer_with_unit<units::byte> (TREE_STRING_LENGTH (string_cst)))
    2325              :     {
    2326              :       /* We're within the area defined by TREE_STRING_POINTER.  */
    2327         1814 :       if (conc_bytes.get_size () == 1_byte)
    2328         1496 :         return &get_uint8
    2329         2992 :           (TREE_STRING_POINTER (string_cst)
    2330         3487 :            [conc_bytes.get_start_offset ().get_integer ().as_unsigned_long ()]);
    2331              :       else
    2332              :         return nullptr;
    2333              :     }
    2334              :   else
    2335              :     {
    2336              :       /* We're in the padding area of trailing zeroes.  */
    2337            7 :       return &get_all_zeros (conc_bytes.get_size ());
    2338              :     }
    2339              : }
    2340              : 
    2341              : const bit_vector *
    2342          194 : bit_vector_manager::
    2343              : maybe_fold_bytes_within_raw_data_cst (tree raw_data_cst,
    2344              :                                       concrete_byte_range conc_bytes)
    2345              : {
    2346          194 :   gcc_assert (TREE_CODE (raw_data_cst) == RAW_DATA_CST);
    2347              : 
    2348          194 :   if (conc_bytes.get_size () != 1_byte)
    2349              :     return nullptr;
    2350              : 
    2351          388 :   gcc_assert (conc_bytes.get_start_offset () >= 0_bytes);
    2352          388 :   gcc_assert
    2353              :     (conc_bytes.get_start_offset ()
    2354              :      < integer_with_unit<units::byte> (RAW_DATA_LENGTH (raw_data_cst)));
    2355              : 
    2356          194 :   size_t idx
    2357          230 :     = conc_bytes.get_start_offset ().get_integer ().as_unsigned_long ();
    2358          194 :   return &get_uint8 (RAW_DATA_UCHAR_ELT (raw_data_cst,  idx));
    2359              : }
    2360              : 
    2361              : const bit_vector &
    2362        22192 : bit_vector_manager::
    2363              : make_baseline_bit_vector (baseline_key k)
    2364              : {
    2365        22192 :   gcc_assert (k.m_base_reg->can_have_initial_svalue_p ());
    2366              : 
    2367        22192 :   auto &rmm = m_node_mgr.get_svalue_manager ();
    2368        22192 :   const svalue *sval = nullptr;
    2369        22192 :   switch (k.m_baseline_state)
    2370              :     {
    2371            0 :     default:
    2372            0 :       gcc_unreachable ();
    2373              : 
    2374          816 :     case baseline_state::main:
    2375          816 :       sval = k.m_base_reg->get_initial_value_at_main (&rmm);
    2376          816 :       break;
    2377              : 
    2378        21376 :     case baseline_state::after_main:
    2379        21376 :       sval = rmm.get_or_create_initial_value (k.m_base_reg);
    2380        21376 :       break;
    2381              :     }
    2382              : 
    2383        22192 :   gcc_assert (sval);
    2384        22192 :   return get_bit_vector_from_svalue (*sval);
    2385              : }
    2386              : 
    2387              : const bit_vector &
    2388        22192 : bit_vector_manager::
    2389              : get_baseline_bit_vector (const region &base_reg,
    2390              :                          baseline_state bs)
    2391              : {
    2392        22192 :   baseline_key k {&base_reg, bs};
    2393        22192 :   auto iter = m_baseline_map.find (k);
    2394        22192 :   if (iter != m_baseline_map.end ())
    2395            0 :     return iter->second;
    2396              : 
    2397        22192 :   auto &bc = make_baseline_bit_vector (k);
    2398        22192 :   m_baseline_map.insert ({k, bc});
    2399        22192 :   return bc;
    2400              : }
    2401              : 
    2402              : const bit_vector *
    2403      2662943 : bit_vector_manager::
    2404              : maybe_fold_cropped_bits (const bit_vector &inner_bv,
    2405              :                          const symbolic_bit_range &inner_bits_to_use)
    2406              : {
    2407      2662943 :   if (inner_bits_to_use.get_size ().is_zero_p ())
    2408            4 :     return &m_empty_bv;
    2409              : 
    2410              :   // x[0..size(x)] --> x.  */
    2411      2662939 :   if (inner_bits_to_use.get_start_offset ().is_zero_p ()
    2412      2662939 :       && &inner_bits_to_use.get_size () == &inner_bv.get_size ())
    2413              :     return &inner_bv;
    2414              : 
    2415       496449 :   if (auto folded = inner_bv.maybe_fold_crop (inner_bits_to_use))
    2416              :     return folded;
    2417              : 
    2418              :   return nullptr;
    2419              : }
    2420              : 
    2421              : const bit_vector &
    2422      2662943 : bit_vector_manager::
    2423              : get_cropped_bits (const bit_vector &inner_bv,
    2424              :                   const symbolic_bit_range &inner_bits_to_use)
    2425              : {
    2426      2662943 :   if (auto *folded = maybe_fold_cropped_bits (inner_bv, inner_bits_to_use))
    2427              :     return *folded;
    2428              : 
    2429        87570 :   const symbolic::cropped_bit_vector::key k {&inner_bv,
    2430        87570 :                                              inner_bits_to_use};
    2431        87570 :   auto iter = m_cropped_map.find (k);
    2432        87570 :   if (iter != m_cropped_map.end ())
    2433        80203 :     return *(iter->second);
    2434         7367 :   auto bv_up = std::make_unique<cropped_bit_vector> (*this, k);
    2435         7367 :   auto &result = *bv_up.get ();
    2436         7367 :   m_cropped_map.insert ({k, std::move (bv_up)});
    2437         7367 :   return result;
    2438         7367 : }
    2439              : 
    2440              : const bit_vector &
    2441       475598 : bit_vector_manager::
    2442              : get_cropped_bytes (const bit_vector &inner_bv,
    2443              :                    const symbolic_byte_range &inner_bytes_to_use)
    2444              : {
    2445       475598 :   return get_cropped_bits (inner_bv,
    2446       475598 :                            bits_from_bytes (inner_bytes_to_use));
    2447              : }
    2448              : 
    2449              : const bit_vector *
    2450         3144 : bit_vector_manager::
    2451              : maybe_fold_repeated_bits (const bit_vector &inner_bv,
    2452              :                           const symbolic_integer &repeat_count)
    2453              : {
    2454         3144 :   if (repeat_count.is_zero_p ())
    2455            4 :     return &m_empty_bv;
    2456              : 
    2457         3140 :   if (repeat_count.is_one_p ())
    2458              :     return &inner_bv;
    2459              : 
    2460         1643 :   if (auto poisoned_bv = inner_bv.dyn_cast_poisoned_bit_vector ())
    2461           42 :     return &get_poisoned_bits
    2462           42 :       (inner_bv.get_size () * repeat_count,
    2463           42 :        poisoned_bv->get_poison_kind ());
    2464              : 
    2465         1601 :   if (auto tristate_bv = inner_bv.dyn_cast_tristate_bit_vector ())
    2466          953 :     return &get_tristate_bits
    2467          953 :       (inner_bv.get_size () * repeat_count,
    2468          953 :        tristate_bv->get_bit_value ());
    2469              : 
    2470          648 :   if (auto repeated_bv = inner_bv.dyn_cast_repeated_bit_vector ())
    2471           11 :     return &get_repeated_bits (repeated_bv->get_inner_bit_vector (),
    2472           11 :                                (repeated_bv->get_repeat_count ()
    2473           11 :                                 * repeat_count));
    2474              : 
    2475              :   return nullptr;
    2476              : }
    2477              : 
    2478              : const bit_vector &
    2479         3144 : bit_vector_manager::
    2480              : get_repeated_bits (const bit_vector &inner_bv,
    2481              :                    const symbolic_integer &repeat_count)
    2482              : {
    2483         3144 :   if (auto *folded = maybe_fold_repeated_bits (inner_bv, repeat_count))
    2484              :     return *folded;
    2485              : 
    2486          637 :   const symbolic::repeated_bit_vector::key k {&inner_bv, &repeat_count};
    2487          637 :   auto iter = m_repeated_map.find (k);
    2488          637 :   if (iter != m_repeated_map.end ())
    2489          343 :     return *(iter->second);
    2490          294 :   auto bv_up = std::make_unique<repeated_bit_vector> (*this, k);
    2491          294 :   auto &result = *bv_up.get ();
    2492          294 :   m_repeated_map.insert ({k, std::move (bv_up)});
    2493          294 :   return result;
    2494          294 : }
    2495              : 
    2496              : const bit_vector &
    2497         2421 : bit_vector_manager::
    2498              : get_repeated_bits (const bit_vector &inner_bv,
    2499              :                    const concrete_integer &repeat_count)
    2500              : {
    2501         2421 :   auto &integer_mgr = get_node_manager ().get_scalars ().get_unitless ();
    2502         2421 :   return get_repeated_bits (inner_bv,
    2503         2421 :                             integer_mgr.get_concrete (repeat_count));
    2504              : }
    2505              : 
    2506              : /* Return true if TYPE_A and TYPE_B are known to be the same size.  */
    2507              : 
    2508              : static bool
    2509        14143 : types_are_same_size_p (const_tree type_a, const_tree type_b)
    2510              : {
    2511        14143 :   concrete_bit_size size_a;
    2512        14143 :   if (!get_type_size (type_a, &size_a))
    2513              :     return false;
    2514        14143 :   concrete_bit_size size_b;
    2515        14143 :   if (!get_type_size (type_b, &size_b))
    2516              :     return false;
    2517        14143 :   return size_a == size_b;
    2518        14143 : }
    2519              : 
    2520              : const bit_vector *
    2521      1806655 : bit_vector_manager::maybe_fold_bits_for_svalue (const svalue &sval)
    2522              : {
    2523      1806655 :   switch (sval.get_kind ())
    2524              :     {
    2525              :     default:
    2526              :       break;
    2527              : 
    2528      1338229 :     case SK_CONSTANT:
    2529      1338229 :       {
    2530      1338229 :         tree tree_cst = sval.maybe_get_constant ();
    2531      1338229 :         if (auto *folded = maybe_fold_bits_for_constant (tree_cst))
    2532       130860 :           return folded;
    2533              : 
    2534              :         /* Fold any 1-byte constants we missed.  */
    2535      1207391 :         auto &bit_mgr = get_node_manager ().get_scalars ().get_bits ();
    2536      1207391 :         concrete_bit_size conc_bit_size;
    2537      1207391 :         if (sval.has_concrete_size_p (&conc_bit_size, bit_mgr)
    2538      3622173 :             && conc_bit_size == 8_bits)
    2539              :           {
    2540      1115590 :             unsigned char buf[1];
    2541      1115590 :             int size = native_encode_expr (tree_cst, buf, sizeof buf, 0);
    2542      1115590 :             gcc_assert (size == 1);
    2543      1115590 :             unsigned char val = buf[0];
    2544      1115590 :             if (auto *b = m_cached_bytes[val])
    2545           22 :               return b;
    2546              :           }
    2547           22 :       }
    2548      1207369 :       break;
    2549              : 
    2550              :       /* TODO: re-enabling this will require a rewrite of parts of
    2551              :          access-diagram.cc which expect string regions, rather than
    2552              :          constant_svalue of string_cst.  */
    2553              : #if 0
    2554              :     case SK_INITIAL:
    2555              :       {
    2556              :         auto &init_sval = *as_a <const initial_svalue *> (&sval);
    2557              :         if (auto *string_reg
    2558              :               = init_sval.get_region ()->dyn_cast_string_region ())
    2559              :           return &get_bits_for_constant (string_reg->get_string_cst ());
    2560              :       }
    2561              :       break;
    2562              : #endif
    2563              : 
    2564        70446 :     case SK_BIT_VECTOR:
    2565        70446 :       {
    2566        70446 :         auto &bit_vector_sval = *as_a<const svalue_from_bit_vector *> (&sval);
    2567        70446 :         return &bit_vector_sval.get_bit_vector ();
    2568              :       }
    2569       119547 :       break;
    2570              : 
    2571       119547 :     case SK_UNKNOWN:
    2572       119547 :       {
    2573       119547 :         concrete_bit_size size;
    2574       119547 :         if (sval.has_concrete_size_p (&size, get_bit_manager ()))
    2575       119547 :           return &get_unknown_bits (size);
    2576              :         else
    2577            0 :           return &get_unknown_bits ();
    2578       119547 :       }
    2579        20753 :       break;
    2580              : 
    2581        20753 :     case SK_UNARYOP:
    2582        20753 :       {
    2583        20753 :         auto &unaryop_sval = *as_a<const unaryop_svalue *> (&sval);
    2584        20753 :         if (CONVERT_EXPR_CODE_P (unaryop_sval.get_op ()))
    2585              :           {
    2586              :             /* If we have a type conversion for which no instructions
    2587              :                are needed, they are presumably bit-for-bit identical,
    2588              :                or for which the sizes are identical.
    2589              :                Fold away the conversion, so e.g.
    2590              :                e.g. BIT_VECTOR_FOR (UNARY_OP(signed, NOP_EXPR, SVAL(unsigned)))
    2591              :                folds to BIT_VECTOR_FOR (SVAL(unsigned)).  */
    2592        19752 :             if (sval.get_type () == nullptr
    2593        19752 :                 || unaryop_sval.get_arg ()->get_type () == nullptr
    2594        19744 :                 || tree_nop_conversion_p (sval.get_type (),
    2595        19744 :                                           unaryop_sval.get_arg ()->get_type ())
    2596        33895 :                 || types_are_same_size_p (sval.get_type (),
    2597        14143 :                                           unaryop_sval.get_arg ()->get_type ()))
    2598         5622 :               return &get_bit_vector_from_svalue (*unaryop_sval.get_arg ());
    2599              :           }
    2600              :       }
    2601              :       break;
    2602              :     }
    2603              : 
    2604              :   return nullptr;
    2605              : }
    2606              : 
    2607              : const bit_vector &
    2608      1786178 : bit_vector_manager::get_bit_vector_from_svalue (const svalue &sval)
    2609              : {
    2610      1786178 :   if (auto *folded = maybe_fold_bits_for_svalue (sval))
    2611              :     return *folded;
    2612              : 
    2613              :   /* We need to be able to determine the size of SVAL.  */
    2614      1465860 :   concrete_bit_size conc_bit_size;
    2615      1465860 :   gcc_assert (sval.has_concrete_size_p (&conc_bit_size,
    2616              :                                         get_bit_manager ()));
    2617              : 
    2618      1465860 :   if (conc_bit_size == 0_bits)
    2619            0 :     return get_empty ();
    2620              : 
    2621      1465860 :   const symbolic::bit_vector_from_svalue::key k {&sval};
    2622      1465860 :   auto iter = m_svalue_to_bv_map.find (k);
    2623      1465860 :   if (iter != m_svalue_to_bv_map.end ())
    2624       286067 :     return *(iter->second);
    2625      1179793 :   auto bv_up = std::make_unique<symbolic::bit_vector_from_svalue> (*this, k);
    2626      1179793 :   auto &result = *bv_up.get ();
    2627      1179793 :   m_svalue_to_bv_map.insert ({k, std::move (bv_up)});
    2628      1179793 :   return result;
    2629      2645653 : }
    2630              : 
    2631              : const bit_vector *
    2632         1022 : bit_vector_manager::maybe_get_bit_vector_from_svalue (const svalue &sval)
    2633              : {
    2634         1022 :   if (auto *folded = maybe_fold_bits_for_svalue (sval))
    2635              :     return folded;
    2636              : 
    2637         1019 :   const symbolic::bit_vector_from_svalue::key k {&sval};
    2638         1019 :   auto iter = m_svalue_to_bv_map.find (k);
    2639         1019 :   if (iter != m_svalue_to_bv_map.end ())
    2640         1019 :     return iter->second.get ();
    2641              :   return nullptr;
    2642              : }
    2643              : 
    2644              : const bit_vector &
    2645      1664124 : bit_vector_manager::get_poisoned_bits (const symbolic_bit_size &num_bits,
    2646              :                                        enum poison_kind kind)
    2647              : {
    2648      1664124 :   if (num_bits.is_zero_p ())
    2649           23 :     return m_empty_bv;
    2650              : 
    2651      1664101 :   poisoned_bit_vector::key k {num_bits, kind};
    2652              : 
    2653      1664101 :   auto iter = m_poisoned_map.find (k);
    2654      1664101 :   if (iter != m_poisoned_map.end ())
    2655      1651665 :     return *(iter->second);
    2656              : 
    2657        12436 :   auto bv_up = std::make_unique<poisoned_bit_vector> (*this, k);
    2658        12436 :   auto &result = *bv_up.get ();
    2659        12436 :   m_poisoned_map.insert ({k, std::move (bv_up)});
    2660        12436 :   return result;
    2661        12436 : }
    2662              : 
    2663              : const bit_vector &
    2664           56 : bit_vector_manager::get_poisoned_bits (const concrete_bit_size &num_bits,
    2665              :                                        enum poison_kind kind)
    2666              : {
    2667           56 :   return get_poisoned_bits (symbolic_from_concrete (num_bits,
    2668              :                                                     get_bit_manager ()),
    2669           56 :                             kind);
    2670              : }
    2671              : 
    2672              : #if CHECKING_P
    2673              : 
    2674              : const bit_vector &
    2675          128 : bit_vector_manager::
    2676              : get_named_test_bit_vector (const symbolic_bit_size &size_in_bits,
    2677              :                            std::string label)
    2678              : {
    2679          128 :   auto bv_up = std::make_unique<named_test_bit_vector> (*this,
    2680              :                                                         size_in_bits,
    2681          128 :                                                         std::move (label));
    2682          128 :   auto &result = *bv_up.get ();
    2683          128 :   m_named_test_bvs.push_back (std::move (bv_up));
    2684          256 :   return result;
    2685          128 : }
    2686              : 
    2687              : const bit_vector &
    2688           12 : bit_vector_manager::
    2689              : get_named_test_bit_vector (const symbolic_byte_size &size_in_bytes,
    2690              :                            std::string label)
    2691              : {
    2692           12 :   auto &size_in_bits = bits_from_bytes (size_in_bytes);
    2693           12 :   return get_named_test_bit_vector (size_in_bits, std::move (label));
    2694              : }
    2695              : 
    2696              : const bit_vector &
    2697          116 : bit_vector_manager::
    2698              : get_named_test_bit_vector (const concrete_bit_size &conc_size_in_bits,
    2699              :                            std::string label)
    2700              : {
    2701          116 :   auto &bit_mgr = get_node_manager ().get_scalars ().get_bits ();
    2702          116 :   auto &sym_size_in_bits = symbolic_from_concrete (conc_size_in_bits, bit_mgr);
    2703          116 :   return get_named_test_bit_vector (sym_size_in_bits, std::move (label));
    2704              : }
    2705              : 
    2706              : const bit_vector &
    2707          100 : bit_vector_manager::
    2708              : get_named_test_bit_vector (const concrete_byte_size &conc_size_in_bytes,
    2709              :                            std::string label)
    2710              : {
    2711          100 :   concrete_bit_size conc_size_in_bits = bits_from_bytes (conc_size_in_bytes);
    2712          100 :   return get_named_test_bit_vector (conc_size_in_bits, std::move (label));
    2713          100 : }
    2714              : 
    2715              : #endif /* #if CHECKING_P */
    2716              : 
    2717              : } // namespace ana::symbolic
    2718              : 
    2719              : #if CHECKING_P
    2720              : 
    2721              : namespace selftest {
    2722              : 
    2723              : static void
    2724            4 : test_maybe_set_irange_bitmask_from_concrete_tristate_vector ()
    2725              : {
    2726              :   /* A combination of ones, zeros, and unknown, expressed in order
    2727              :      LSB through MSB.  */
    2728            4 :   concrete_tristate_vector ts_vec
    2729              :     ({tristate (true),
    2730              :       tristate (false),
    2731            4 :       tristate::unknown (),
    2732              :       tristate (true),
    2733            4 :       tristate (false)});
    2734              : 
    2735            4 :   irange_bitmask irange_bmask;
    2736            4 :   bool ok = symbolic::maybe_set_irange_bitmask_from_concrete_tristate_vector
    2737            4 :     (ts_vec, &irange_bmask);
    2738            4 :   ASSERT_TRUE (ok);
    2739            4 :   irange_bmask.verify_mask ();
    2740              : 
    2741              :   /* We expect:
    2742              :      index: [..., 4, 3, 2, 1, 0]
    2743              :      VALUE: [..., 0, 1, 0, 0, 1]
    2744              :      MASK:  [..., 0, 0, 1, 0, 0]
    2745              :      |            ^  ^  ^  ^  ^
    2746              :      |            |  |  |  |  bit 0: true
    2747              :      |            |  |  |  bit 1: false
    2748              :      |            |  |  bit 2: unknown
    2749              :      |            | bit 3: true
    2750              :      |            bit 4: false.  */
    2751            4 :   ASSERT_EQ (irange_bmask.value (), wi::uhwi (0b01001, 5));
    2752            4 : }
    2753              : 
    2754              : static void
    2755            4 : test_tristate ()
    2756              : {
    2757            4 :   symbolic::node_manager node_mgr;
    2758            4 :   auto &mgr = node_mgr.get_bit_vector_manager ();
    2759            4 :   auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
    2760              : 
    2761            4 :   auto &false_bit = mgr.get_all_zeros (1_bit);
    2762            4 :   ASSERT_SAME_SYMBOLIC_NODE (false_bit.get_size (),
    2763              :                              bit_mgr.get_concrete (1_bit));
    2764            4 :   ASSERT_SYMBOLIC_NODE_DUMP_EQ
    2765              :     (false_bit,
    2766              :      "tristate_bit_vector[size: 1 bit]: false bit\n");
    2767            4 :   false_bit.to_json ();
    2768            4 :   ASSERT_EQ (false_bit.get_tristate_at_offset (0_bits), tristate (false));
    2769              : 
    2770            4 :   auto &true_bit = mgr.get_tristate_bits (1_bit, tristate (true));
    2771            4 :   ASSERT_SAME_SYMBOLIC_NODE (true_bit.get_size (),
    2772              :                              bit_mgr.get_concrete (1_bit));
    2773            4 :   ASSERT_SYMBOLIC_NODE_DUMP_EQ
    2774              :     (true_bit,
    2775              :      "tristate_bit_vector[size: 1 bit]: true bit\n");
    2776            4 :   true_bit.to_json ();
    2777            4 :   ASSERT_EQ (true_bit.get_tristate_at_offset (0_bits), tristate (true));
    2778              : 
    2779            4 :   auto &unknown_bit = mgr.get_unknown_bits (1_bit);
    2780            4 :   ASSERT_SAME_SYMBOLIC_NODE (unknown_bit.get_size (),
    2781              :                              bit_mgr.get_concrete (1_bit));
    2782            4 :   ASSERT_SYMBOLIC_NODE_DUMP_EQ
    2783              :     (unknown_bit,
    2784              :      "tristate_bit_vector[size: 1 bit]: unknown bit\n");
    2785            4 :   unknown_bit.to_json ();
    2786            4 :   ASSERT_EQ (unknown_bit.get_tristate_at_offset (0_bits), tristate::unknown ());
    2787              : 
    2788            4 :   auto &three_zero_bits = mgr.get_all_zeros (3_bits);
    2789            4 :   ASSERT_SAME_SYMBOLIC_NODE (three_zero_bits.get_size (),
    2790              :                              bit_mgr.get_concrete (3_bits));
    2791            4 :   ASSERT_SYMBOLIC_NODE_DUMP_EQ
    2792              :     (three_zero_bits,
    2793              :      "tristate_bit_vector[size: 3 bits]: false bits\n");
    2794              : 
    2795            4 :   auto &byte_00 = mgr.get_all_zeros (1_byte);
    2796            4 :   ASSERT_SYMBOLIC_NODE_DUMP_EQ
    2797              :     (byte_00,
    2798              :      "tristate_bit_vector[size: 1 byte]: false bits\n");
    2799              : 
    2800            4 :   auto &byte_ff = mgr.get_tristate_bits (8_bits, tristate (true));
    2801            4 :   ASSERT_SYMBOLIC_NODE_DUMP_EQ
    2802              :     (byte_ff,
    2803              :      "tristate_bit_vector[size: 1 byte]: true bits\n");
    2804              : 
    2805            4 :   auto &unknown_32_bits = mgr.get_unknown_bits (32_bits);
    2806            4 :   ASSERT_SYMBOLIC_NODE_DUMP_EQ
    2807              :     (unknown_32_bits,
    2808              :      "tristate_bit_vector[size: 4 bytes]: unknown bits\n");
    2809            4 :   ASSERT_EQ (unknown_32_bits.get_tristate_at_offset (31_bits),
    2810              :              tristate::unknown ());
    2811              : 
    2812            4 :   auto &x = bit_mgr.get_named_test_scalar ("X");
    2813            4 :   auto &sym_sized_zeros = mgr.get_all_zeros (x);
    2814            4 :   ASSERT_SYMBOLIC_NODE_DUMP_EQ
    2815              :     (sym_sized_zeros,
    2816              :      "tristate_bit_vector[size: X bits]: false bits\n");
    2817            4 :   ASSERT_SAME_SYMBOLIC_NODE (sym_sized_zeros.get_size (),
    2818              :                              x);
    2819            4 :   sym_sized_zeros.to_json ();
    2820            4 :   ASSERT_EQ (sym_sized_zeros.get_tristate_at_offset (0_bits), tristate (false));
    2821            4 :   ASSERT_EQ (sym_sized_zeros.get_tristate_at_offset (x), tristate (false));
    2822              : 
    2823            4 :   ASSERT_SAME_SYMBOLIC_NODE (mgr.get_all_zeros (0_bits),
    2824              :                              mgr.get_empty ());
    2825            4 :   mgr.get_empty ().to_json ();
    2826              : 
    2827            4 :   {
    2828            4 :     pretty_printer pp;
    2829            4 :     hexdump_options hexdump_opts;
    2830            4 :     hexdump_opts.m_show_headings = true;
    2831            4 :     hexdump_opts.m_show_binary = true;
    2832            4 :     unknown_32_bits.hexdump_to_pp (&pp, hexdump_opts);
    2833            4 :     ASSERT_STREQ
    2834              :       (pp_formatted_text (&pp),
    2835              :        ("             +-----------------------------------+-----------+-----+\n"
    2836              :         "             |              Binary               |    Hex    |ASCII|\n"
    2837              :         "+------------+-----------------------------------+-----------+-----+\n"
    2838              :         "|[bytes 0..4)|???????? ???????? ???????? ????????|?? ?? ?? ??|???? |\n"
    2839              :         "+------------+-----------------------------------+-----------+-----+\n"));
    2840            4 :   }
    2841            4 :   {
    2842            4 :     pretty_printer pp;
    2843            4 :     hexdump_options hexdump_opts;
    2844            4 :     hexdump_opts.m_show_headings = false;
    2845            4 :     hexdump_opts.m_show_binary = true;
    2846            4 :     mgr.get_all_zeros (32_bits).hexdump_to_pp (&pp, hexdump_opts);
    2847            4 :     ASSERT_STREQ
    2848              :       (pp_formatted_text (&pp),
    2849              :        ("+------------+-----------------------------------+-----------+----+\n"
    2850              :         "|[bytes 0..4)|00000000 00000000 00000000 00000000|00 00 00 00|....|\n"
    2851              :         "+------------+-----------------------------------+-----------+----+\n"));
    2852            4 :   }
    2853            4 :   {
    2854            4 :     pretty_printer pp;
    2855            4 :     hexdump_options hexdump_opts;
    2856            4 :     hexdump_opts.m_show_headings = false;
    2857            4 :     hexdump_opts.m_show_binary = true;
    2858            4 :     mgr.get_all_ones (32_bits).hexdump_to_pp (&pp, hexdump_opts);
    2859            4 :     ASSERT_STREQ
    2860              :       (pp_formatted_text (&pp),
    2861              :        ("+------------+-----------------------------------+-----------+----+\n"
    2862              :         "|[bytes 0..4)|11111111 11111111 11111111 11111111|ff ff ff ff|....|\n"
    2863              :         "+------------+-----------------------------------+-----------+----+\n"));
    2864            4 :   }
    2865            4 : }
    2866              : 
    2867              : static void
    2868            4 : test_integer_constants ()
    2869              : {
    2870            4 :   symbolic::node_manager node_mgr;
    2871            4 :   auto &mgr = node_mgr.get_bit_vector_manager ();
    2872            4 :   auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
    2873              : 
    2874              :   // Verify that we fold all zeroes and all ones
    2875              : 
    2876            4 :   auto &char_0
    2877            4 :     = mgr.get_bits_for_constant (build_int_cst (char_type_node, 0));
    2878            4 :   ASSERT_SAME_SYMBOLIC_NODE (char_0.get_size (),
    2879              :                              bit_mgr.get_concrete (8_bits));
    2880            4 :   ASSERT_SYMBOLIC_NODE_DUMP_EQ
    2881              :     (char_0,
    2882              :      "tristate_bit_vector[size: 1 byte]: false bits\n");
    2883            4 :   char_0.to_json ();
    2884              : 
    2885            4 :   auto &char_0xff
    2886            4 :     = mgr.get_bits_for_constant (build_int_cst (unsigned_char_type_node,
    2887              :                                                 0xff));
    2888            4 :   ASSERT_SAME_SYMBOLIC_NODE (char_0xff.get_size (),
    2889              :                              bit_mgr.get_concrete (8_bits));
    2890            4 :   ASSERT_SYMBOLIC_NODE_DUMP_EQ
    2891              :     (char_0xff,
    2892              :      "tristate_bit_vector[size: 1 byte]: true bits\n");
    2893            4 :   char_0xff.to_json ();
    2894              : 
    2895              :   // Verify that we handle constants that we can't simplify
    2896              : 
    2897            4 :   auto &char_A
    2898            4 :     = mgr.get_bits_for_constant (build_int_cst (char_type_node,
    2899              :                                                 'A'));
    2900            4 :   ASSERT_SAME_SYMBOLIC_NODE (char_A.get_size (),
    2901              :                              bit_mgr.get_concrete (8_bits));
    2902            4 :   ASSERT_SYMBOLIC_NODE_DUMP_EQ
    2903              :     (char_A,
    2904              :      ("bit_vector_from_svalue[size: 1 byte]\n"
    2905              :       "`- m_sval: 'unsigned char': constant_svalue ('65')\n"));
    2906              : 
    2907            4 :   auto &int_42
    2908            4 :     = mgr.get_bits_for_constant (build_int_cst (uint32_type_node, 42));
    2909            4 :   ASSERT_SAME_SYMBOLIC_NODE (int_42.get_size (),
    2910              :                              bit_mgr.get_concrete (32_bits));
    2911            4 :   int_42.to_json ();
    2912              : 
    2913              :   // -1 is simplifiable to all ones...
    2914            4 :   auto &char_minus_one
    2915            4 :     = mgr.get_bits_for_constant (build_int_cst (signed_char_type_node, -1));
    2916            4 :   ASSERT_SAME_SYMBOLIC_NODE (char_minus_one.get_size (),
    2917              :                              bit_mgr.get_concrete (8_bits));
    2918            4 :   ASSERT_SYMBOLIC_NODE_DUMP_EQ
    2919              :     (char_minus_one,
    2920              :      "tristate_bit_vector[size: 1 byte]: true bits\n");
    2921              : 
    2922              :   // ...but -2 isn't
    2923            4 :   auto &char_minus_two
    2924            4 :     = mgr.get_bits_for_constant (build_int_cst (signed_char_type_node,
    2925              :                                                 -2));
    2926            4 :   ASSERT_SAME_SYMBOLIC_NODE (char_minus_two.get_size (),
    2927              :                              bit_mgr.get_concrete (8_bits));
    2928            4 :   ASSERT_SYMBOLIC_NODE_DUMP_EQ
    2929              :     (char_minus_two,
    2930              :      ("bit_vector_from_svalue[size: 1 byte]\n"
    2931              :       "`- m_sval: 'unsigned char': constant_svalue ('254')\n"));
    2932            4 :   ASSERT_SAME_SYMBOLIC_NODE
    2933              :     (char_minus_two,
    2934              :      mgr.get_bits_for_constant (build_int_cst (unsigned_char_type_node,
    2935              :                                                254)));
    2936            4 : }
    2937              : 
    2938              : static void
    2939            4 : test_bytes ()
    2940              : {
    2941            4 :   symbolic::node_manager node_mgr;
    2942            4 :   auto &mgr = node_mgr.get_bit_vector_manager ();
    2943            4 :   auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
    2944              : 
    2945            4 :   ASSERT_SAME_SYMBOLIC_NODE (mgr.get_uint8 (0),
    2946              :                       mgr.get_all_zeros (1_byte));
    2947         1020 :   for (int i = 0x01; i < 0xff; ++i)
    2948              :     {
    2949         1016 :       auto &b = mgr.get_uint8 (i);
    2950         1016 :       ASSERT_SAME_SYMBOLIC_NODE (b.get_size (),
    2951              :                                  bit_mgr.get_concrete (8_bits));
    2952              :     }
    2953            4 :   ASSERT_SAME_SYMBOLIC_NODE (mgr.get_uint8 (0xff),
    2954              :                              mgr.get_all_ones (1_byte));
    2955              : 
    2956         1024 :   for (int i = 0; i < 0xff; ++i)
    2957              :     {
    2958         1020 :       auto &bv = mgr.get_uint8 (i);
    2959         1020 :       uint8_t val;
    2960         1020 :       bool out = bv.maybe_as_uint8 (&val);
    2961         1020 :       ASSERT_TRUE (out);
    2962         1020 :       ASSERT_EQ (val, i);
    2963         9180 :       for (int bit_idx = 0; bit_idx < 8; ++bit_idx)
    2964        12256 :         ASSERT_EQ (bv.get_tristate_at_offset (concrete_bit_offset (bit_idx)),
    2965              :                    tristate (i & (1 << bit_idx)));
    2966              :     }
    2967            4 : }
    2968              : 
    2969              : static void
    2970            4 : test_string_constants ()
    2971              : {
    2972            4 :   tree string_cst_ptr = make_string_constant ("abc");
    2973              : 
    2974            4 :   symbolic::node_manager node_mgr;
    2975            4 :   auto &bv_mgr = node_mgr.get_bit_vector_manager ();
    2976            4 :   auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
    2977              : 
    2978            4 :   auto &abc0 = bv_mgr.get_bits_for_constant (string_cst_ptr);
    2979            4 :   ASSERT_SAME_SYMBOLIC_NODE (abc0.get_size (),
    2980              :                              bit_mgr.get_concrete (bits_from_bytes (4_bytes)));
    2981            4 :   abc0.to_json ();
    2982              : 
    2983            4 :   {
    2984            4 :     pretty_printer pp;
    2985            4 :     abc0.hexdump_to_pp (&pp, hexdump_options ());
    2986            4 :     ASSERT_STREQ
    2987              :       (pp_formatted_text (&pp),
    2988              :        ("+------------+-----------+----+\n"
    2989              :         "|[bytes 0..4)|61 62 63 00|abc.|\n"
    2990              :         "+------------+-----------+----+\n"));
    2991            4 :   }
    2992              : 
    2993              :   /* Verify accessing chars within a STRING_CST.  */
    2994            4 :   {
    2995            4 :     auto &a = abc0.get_byte_at_offset (0_bytes);
    2996            4 :     ASSERT_SAME_SYMBOLIC_NODE (a, bv_mgr.get_uint8 ('a'));
    2997              : 
    2998            4 :     auto &b = abc0.get_byte_at_offset (1_byte);
    2999            4 :     ASSERT_SAME_SYMBOLIC_NODE (b, bv_mgr.get_uint8 ('b'));
    3000              : 
    3001            4 :     auto &c = abc0.get_byte_at_offset (2_bytes);
    3002            4 :     ASSERT_SAME_SYMBOLIC_NODE (c, bv_mgr.get_uint8 ('c'));
    3003              : 
    3004            4 :     auto &term = abc0.get_byte_at_offset (3_bytes);
    3005            4 :     ASSERT_SAME_SYMBOLIC_NODE (term, bv_mgr.get_uint8 (0));
    3006              :   }
    3007              : 
    3008           24 :   for (concrete_byte_offset i = 0_bytes; i < 4_bytes; ++i)
    3009           16 :     ASSERT_EQ (abc0.scan_for_first_zero_byte (i),
    3010            4 :                string_scan::found_nul (3_bytes));
    3011              : 
    3012              :   /* Example of concatenating known string literals.  */
    3013            4 :   {
    3014            4 :     const char *hello = "hello";
    3015            4 :     const char *world = " world!";
    3016            4 :     tree t_hello = make_string_constant (hello);
    3017            4 :     tree t_world = make_string_constant (world);
    3018            4 :     auto &bv_hello = bv_mgr.get_bits_for_constant (t_hello);
    3019            4 :     auto &bv_world = bv_mgr.get_bits_for_constant (t_world);
    3020            4 :     auto &concat_bv = bv_mgr.get_concat_bits
    3021           12 :       ({&bv_hello.get_prefix (concrete_byte_size (strlen (hello))),
    3022            8 :         &bv_world.get_prefix (concrete_byte_size (strlen (world))),
    3023            4 :         &bv_mgr.get_uint8 (0)});
    3024            4 :     pretty_printer pp;
    3025            4 :     hexdump_options hexdump_opts;
    3026            4 :     hexdump_opts.m_bytes_per_line = 8_bytes;
    3027            4 :     concat_bv.hexdump_to_pp (&pp, hexdump_opts);
    3028            4 :     ASSERT_STREQ
    3029              :       (pp_formatted_text (&pp),
    3030              :        "+-------------+-----------------------+--------+\n"
    3031              :        "| [bytes 0..8)|68 65 6c 6c 6f 20 77 6f|hello wo|\n"
    3032              :        "+-------------+-----------------------+--------+\n"
    3033              :        "|[bytes 8..13)|72 6c 64 21 00         |rld!.   |\n"
    3034              :        "+-------------+-----------------------+--------+\n");
    3035           60 :     for (concrete_byte_offset i = 0_bytes; i < 13_bytes; ++i)
    3036           52 :       ASSERT_EQ (concat_bv.scan_for_first_zero_byte (i),
    3037            4 :                  string_scan::found_nul (12_bytes));
    3038            4 :   }
    3039            4 : }
    3040              : 
    3041              : static tree
    3042           12 : make_raw_data_constant (const char *buf, size_t size)
    3043              : {
    3044           12 :   tree node = make_node (RAW_DATA_CST);
    3045           12 :   TREE_TYPE (node) = integer_type_node;
    3046           12 :   RAW_DATA_LENGTH (node) = size;
    3047           12 :   RAW_DATA_POINTER (node) = buf;
    3048           12 :   return node;
    3049              : }
    3050              : 
    3051              : static void
    3052            4 : test_raw_data_constant_1 ()
    3053              : {
    3054            4 :   tree raw_data_cst_ptr = make_raw_data_constant ("abc", 3);
    3055              : 
    3056            4 :   symbolic::node_manager node_mgr;
    3057            4 :   auto &mgr = node_mgr.get_bit_vector_manager ();
    3058            4 :   auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
    3059              : 
    3060            4 :   auto &abc = mgr.get_bits_for_constant (raw_data_cst_ptr);
    3061            4 :   ASSERT_SAME_SYMBOLIC_NODE (abc.get_size (),
    3062              :                              bit_mgr.get_concrete (bits_from_bytes (3_bytes)));
    3063            4 :   abc.to_json ();
    3064              : 
    3065            4 :   {
    3066            4 :     pretty_printer pp;
    3067            4 :     abc.hexdump_to_pp (&pp, hexdump_options ());
    3068            4 :     ASSERT_STREQ
    3069              :       (pp_formatted_text (&pp),
    3070              :        ("+------------+--------+---+\n"
    3071              :         "|[bytes 0..3)|61 62 63|abc|\n"
    3072              :         "+------------+--------+---+\n"));
    3073            4 :   }
    3074              : 
    3075              :   /* Verify accessing chars within a RAW_DATA_CST.  */
    3076            4 :   {
    3077            4 :     auto &a = abc.get_byte_at_offset (0_bytes);
    3078            4 :     ASSERT_SAME_SYMBOLIC_NODE (a, mgr.get_uint8 ('a'));
    3079              : 
    3080            4 :     auto &b = abc.get_byte_at_offset (1_byte);
    3081            4 :     ASSERT_SAME_SYMBOLIC_NODE (b, mgr.get_uint8 ('b'));
    3082              : 
    3083            4 :     auto &c = abc.get_byte_at_offset (2_bytes);
    3084            4 :     ASSERT_SAME_SYMBOLIC_NODE (c, mgr.get_uint8 ('c'));
    3085              :   }
    3086            4 : }
    3087              : 
    3088              : /* Test of a raw data cst with multiple embedded zero bytes.  */
    3089              : 
    3090              : static void
    3091            4 : test_raw_data_constant_2 ()
    3092              : {
    3093            4 :   tree raw_data_cst_ptr = make_raw_data_constant ("a\0b\0c\0", 6);
    3094              : 
    3095            4 :   symbolic::node_manager node_mgr;
    3096            4 :   auto &mgr = node_mgr.get_bit_vector_manager ();
    3097            4 :   auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
    3098              : 
    3099            4 :   auto &a0b0c0 = mgr.get_bits_for_constant (raw_data_cst_ptr);
    3100            4 :   ASSERT_SAME_SYMBOLIC_NODE (a0b0c0.get_size (),
    3101              :                              bit_mgr.get_concrete (bits_from_bytes (6_bytes)));
    3102            4 :   a0b0c0.to_json ();
    3103              : 
    3104            4 :   {
    3105            4 :     pretty_printer pp;
    3106            4 :     a0b0c0.hexdump_to_pp (&pp, hexdump_options ());
    3107            4 :     ASSERT_STREQ
    3108              :       (pp_formatted_text (&pp),
    3109              :        ("+------------+-----------+----+\n"
    3110              :         "|[bytes 0..4)|61 00 62 00|a.b.|\n"
    3111              :         "+------------+-----------+----+\n"
    3112              :         "|[bytes 4..6)|63 00      |c.  |\n"
    3113              :         "+------------+-----------+----+\n"));
    3114            4 :   }
    3115              : 
    3116              :   /* Verify accessing chars within a RAW_DATA_CST.  */
    3117            4 :   {
    3118            4 :     ASSERT_SAME_SYMBOLIC_NODE (a0b0c0.get_byte_at_offset (0_bytes),
    3119              :                                mgr.get_uint8 ('a'));
    3120            4 :     ASSERT_SAME_SYMBOLIC_NODE (a0b0c0.get_byte_at_offset (1_byte),
    3121              :                                mgr.get_uint8 (0));
    3122            4 :     ASSERT_SAME_SYMBOLIC_NODE (a0b0c0.get_byte_at_offset (2_bytes),
    3123              :                                mgr.get_uint8 ('b'));
    3124            4 :     ASSERT_SAME_SYMBOLIC_NODE (a0b0c0.get_byte_at_offset (3_bytes),
    3125              :                                mgr.get_uint8 (0));
    3126            4 :     ASSERT_SAME_SYMBOLIC_NODE (a0b0c0.get_byte_at_offset (4_bytes),
    3127              :                                mgr.get_uint8 ('c'));
    3128            4 :     ASSERT_SAME_SYMBOLIC_NODE (a0b0c0.get_byte_at_offset (5_bytes),
    3129              :                                mgr.get_uint8 (0));
    3130              :   }
    3131              : 
    3132              :   /* String scans should locate the NUL bytes.  */
    3133            4 :   {
    3134            4 :     ASSERT_EQ (a0b0c0.scan_for_first_zero_byte (0_bytes),
    3135              :                string_scan::found_nul (1_byte));
    3136            4 :     ASSERT_EQ (a0b0c0.scan_for_first_zero_byte (1_byte),
    3137              :                string_scan::found_nul (1_byte));
    3138            4 :     ASSERT_EQ (a0b0c0.scan_for_first_zero_byte (2_bytes),
    3139              :                string_scan::found_nul (3_bytes));
    3140            4 :     ASSERT_EQ (a0b0c0.scan_for_first_zero_byte (3_bytes),
    3141              :                string_scan::found_nul (3_bytes));
    3142            4 :     ASSERT_EQ (a0b0c0.scan_for_first_zero_byte (4_bytes),
    3143              :                string_scan::found_nul (5_bytes));
    3144            4 :     ASSERT_EQ (a0b0c0.scan_for_first_zero_byte (5_bytes),
    3145              :                string_scan::found_nul (5_bytes));
    3146              :   }
    3147            4 : }
    3148              : 
    3149              : /* Test of an empty raw data cst.  */
    3150              : 
    3151              : static void
    3152            4 : test_raw_data_constant_empty ()
    3153              : {
    3154            4 :   tree raw_data_cst_ptr = make_raw_data_constant ("", 0);
    3155              : 
    3156            4 :   symbolic::node_manager node_mgr;
    3157            4 :   auto &mgr = node_mgr.get_bit_vector_manager ();
    3158            4 :   auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
    3159              : 
    3160            4 :   auto &bv = mgr.get_bits_for_constant (raw_data_cst_ptr);
    3161            4 :   ASSERT_SAME_SYMBOLIC_NODE (bv.get_size (),
    3162              :                              bit_mgr.get_concrete (bits_from_bytes (0_bytes)));
    3163            4 :   ASSERT_SAME_SYMBOLIC_NODE (bv,
    3164              :                              node_mgr.get_bit_vector_manager ().get_empty ());
    3165            4 : }
    3166              : 
    3167              : static void
    3168            4 : test_concat ()
    3169              : {
    3170            4 :   symbolic::node_manager node_mgr;
    3171            4 :   auto &mgr = node_mgr.get_bit_vector_manager ();
    3172            4 :   auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
    3173              : 
    3174            4 :   auto &char_a
    3175            4 :     = mgr.get_bits_for_constant (build_int_cst (char_type_node, 'a'));
    3176            4 :   auto &char_b
    3177            4 :     = mgr.get_bits_for_constant (build_int_cst (char_type_node, 'b'));
    3178            4 :   auto &char_x
    3179            4 :     = mgr.get_bits_for_constant (build_int_cst (char_type_node, 'x'));
    3180            4 :   auto &char_y
    3181            4 :     = mgr.get_bits_for_constant (build_int_cst (char_type_node, 'y'));
    3182              : 
    3183            4 :   auto &ab = mgr.get_concat_bits ({&char_a, &char_b});
    3184            4 :   ASSERT_SAME_SYMBOLIC_NODE (ab.get_size (),
    3185              :                              bit_mgr.get_concrete (bits_from_bytes (2_bytes)));
    3186            4 :   ab.to_json ();
    3187              : 
    3188            4 :   auto &xy
    3189            4 :     = mgr.get_concat_bits ({&char_x, &char_y});
    3190            4 :   ASSERT_SAME_SYMBOLIC_NODE (xy.get_size (),
    3191              :                              bit_mgr.get_concrete (bits_from_bytes (2_bytes)));
    3192           16 :   for (concrete_byte_offset i = 0_bytes; i < 2_bytes; ++i)
    3193            8 :     ASSERT_EQ (xy.scan_for_first_zero_byte (i),
    3194            4 :                string_scan::beyond_domain (2_bytes));
    3195              : 
    3196            4 :   auto &single_element
    3197            4 :     = mgr.get_concat_bits ({&char_a});
    3198            4 :   ASSERT_SAME_SYMBOLIC_NODE (single_element, char_a);
    3199              : 
    3200              :   /* Verity concat (empty, empty) --> empty.  */
    3201            4 :   ASSERT_SAME_SYMBOLIC_NODE
    3202              :     (mgr.get_concat_bits ({&mgr.get_empty (), &mgr.get_empty ()}),
    3203              :      mgr.get_empty ());
    3204              : 
    3205              :   /* Verity concat (a, empty) --> a.  */
    3206            4 :   ASSERT_SAME_SYMBOLIC_NODE (mgr.get_concat_bits ({&char_a, &mgr.get_empty ()}),
    3207              :                              char_a);
    3208            4 :   ASSERT_SAME_SYMBOLIC_NODE (mgr.get_concat_bits ({&mgr.get_empty (), &char_a}),
    3209              :                              char_a);
    3210              : 
    3211              :   /* Verify concat(a, a) --> a * 2.  */
    3212            4 :   auto &aa
    3213            4 :     = mgr.get_concat_bits ({&char_a, &char_a});
    3214            4 :   ASSERT_SAME_SYMBOLIC_NODE (aa.get_size (),
    3215              :                              bit_mgr.get_concrete (16_bits));
    3216            4 :   ASSERT_SAME_SYMBOLIC_NODE
    3217              :     (aa,
    3218              :      mgr.get_repeated_bits (char_a, 2));
    3219              : 
    3220              :   /* Verify concat(a, a, a) --> a * 3.  */
    3221            4 :   auto &aaa
    3222              :     = mgr.get_concat_bits
    3223            4 :     ({&char_a, &char_a, &char_a});
    3224            4 :   ASSERT_SAME_SYMBOLIC_NODE (aaa.get_size (),
    3225              :                              bit_mgr.get_concrete (24_bits));
    3226            4 :   ASSERT_SAME_SYMBOLIC_NODE
    3227              :     (aaa,
    3228              :      mgr.get_repeated_bits (char_a, 3));
    3229              : 
    3230              :   /* Verify concat(a * 2, a) --> a * 3.  */
    3231            4 :   {
    3232            4 :     auto &bits = mgr.get_concat_bits ({&aa, &char_a});
    3233            4 :     ASSERT_SAME_SYMBOLIC_NODE (bits, aaa);
    3234              :   }
    3235              : 
    3236              :   /* Verify concat(a, a * 2) --> a * 3.  */
    3237            4 :   {
    3238            4 :     auto &bits = mgr.get_concat_bits ({&char_a, &aa});
    3239            4 :     ASSERT_SAME_SYMBOLIC_NODE (bits, aaa);
    3240              :   }
    3241              : 
    3242              :   /* Verify concat(a * 2, a * 2) --> a * 4.  */
    3243            4 :   {
    3244            4 :     auto &bits = mgr.get_concat_bits ({&aa, &aa});
    3245            4 :     ASSERT_SAME_SYMBOLIC_NODE
    3246              :       (bits,
    3247              :        mgr.get_repeated_bits (char_a, 4));
    3248              :   }
    3249              : 
    3250              :   /* Verify concat(a * 2, a, a * 2) --> a * 5.  */
    3251            4 :   {
    3252            4 :     auto &bits = mgr.get_concat_bits ({&aa, &char_a, &aa});
    3253            4 :     ASSERT_SAME_SYMBOLIC_NODE
    3254              :       (bits,
    3255              :        mgr.get_repeated_bits (char_a, 5));
    3256              :   }
    3257              : 
    3258              :   /* Verify concat(a, a, b, b) --> concat(a * 2, b * 2).  */
    3259            4 :   {
    3260            4 :     auto &bits
    3261              :       = mgr.get_concat_bits
    3262            4 :       ({&char_a, &char_a, &char_b, &char_b});
    3263            4 :     ASSERT_SAME_SYMBOLIC_NODE
    3264              :       (bits,
    3265              :        mgr.get_concat_bits
    3266              :        ({&mgr.get_repeated_bits (char_a, 2),
    3267              :          &mgr.get_repeated_bits (char_b, 2)}));
    3268              :   }
    3269              : 
    3270              :   /* Verify concat of poisoneds.  */
    3271            4 :   {
    3272              :     /* Verify concat(poisoned(m), poisoned(n) --> poisoned(m + n)
    3273              :        for same kind of poison.  */
    3274            4 :     {
    3275            4 :       auto &bits = mgr.get_concat_bits
    3276            8 :         ({&mgr.get_poisoned_bits (2_bits, poison_kind::uninit),
    3277            8 :           &mgr.get_poisoned_bits (3_bits, poison_kind::uninit)});
    3278            4 :       ASSERT_SAME_SYMBOLIC_NODE
    3279              :         (bits,
    3280              :          mgr.get_poisoned_bits (5_bits, poison_kind::uninit));
    3281              :     }
    3282              : 
    3283              :     // Verify that we don't fold the concat of non-equal kinds of poison
    3284            4 :     {
    3285            4 :       auto &bits = mgr.get_concat_bits
    3286            8 :         ({&mgr.get_poisoned_bits (2_bits, poison_kind::uninit),
    3287            8 :           &mgr.get_poisoned_bits (3_bits, poison_kind::freed)});
    3288            4 :       ASSERT_SYMBOLIC_NODE_DUMP_EQ
    3289              :         (bits,
    3290              :          ("concat_bit_vector[size: 5 bits]\n"
    3291              :           "+- poisoned_bit_vector[size: 2 bits]: uninit\n"
    3292              :           "`- poisoned_bit_vector[size: 3 bits]: freed\n"));
    3293              :     }
    3294              :   }
    3295              : 
    3296              :   /* Verify concat of tristates.  */
    3297            4 :   {
    3298              :     /* Verify concat(tristate(m), tristate(n) --> tristate(m + n)
    3299              :        for same tristate.  */
    3300            4 :     {
    3301            4 :       auto &bits
    3302            8 :         = mgr.get_concat_bits ({&mgr.get_all_zeros (2_bits),
    3303            8 :                                 &mgr.get_all_zeros (3_bits)});
    3304            4 :       ASSERT_SAME_SYMBOLIC_NODE (bits, mgr.get_all_zeros (5_bits));
    3305              :     }
    3306              : 
    3307              :     // Verify that we don't fold the concat of non-equal tristates
    3308            4 :     {
    3309            4 :       auto &bits
    3310              :         = mgr.get_concat_bits
    3311            4 :         ({
    3312            4 :            &mgr.get_all_zeros (2_bits),
    3313            8 :            &mgr.get_all_ones (3_bits)
    3314              :          });
    3315            4 :       ASSERT_SYMBOLIC_NODE_DUMP_EQ
    3316              :         (bits,
    3317              :          ("concat_bit_vector[size: 5 bits]\n"
    3318              :           "+- tristate_bit_vector[size: 2 bits]: false bits\n"
    3319              :           "`- tristate_bit_vector[size: 3 bits]: true bits\n"));
    3320            4 :       ASSERT_EQ (bits.get_tristate_at_offset (0_bits), tristate (false));
    3321            4 :       ASSERT_EQ (bits.get_tristate_at_offset (1_bit), tristate (false));
    3322            4 :       ASSERT_EQ (bits.get_tristate_at_offset (2_bits), tristate (true));
    3323            4 :       ASSERT_EQ (bits.get_tristate_at_offset (3_bits), tristate (true));
    3324            4 :       ASSERT_EQ (bits.get_tristate_at_offset (4_bits), tristate (true));
    3325              : 
    3326            4 :       {
    3327            4 :         pretty_printer pp;
    3328            4 :         hexdump_options hexdump_opts;
    3329            4 :         hexdump_opts.m_show_binary = true;
    3330            4 :         hexdump_opts.m_show_hex = false;
    3331            4 :         hexdump_opts.m_show_ascii = false;
    3332            4 :         bits.hexdump_to_pp (&pp, hexdump_opts);
    3333            4 :         ASSERT_STREQ
    3334              :           (pp_formatted_text (&pp),
    3335              :            "+-----------+-----+\n"
    3336              :            "|[bits 0..5)|00111|\n"
    3337              :            "+-----------+-----+\n");
    3338            4 :       }
    3339              :     }
    3340              :   }
    3341              : 
    3342              :   /* Verify concat of concat --> concat.  */
    3343              :   /*
    3344              :      e.g.
    3345              :      concat(concat(A, B), concat(X, Y)) --> concat(A, B, X, Y);
    3346              :   */
    3347            4 :   auto &abxy
    3348            4 :     = mgr.get_concat_bits ({&ab, &xy});
    3349            4 :   ASSERT_SAME_SYMBOLIC_NODE (abxy.get_size (),
    3350              :                              bit_mgr.get_concrete (32_bits));
    3351            4 :   ASSERT_SAME_SYMBOLIC_NODE
    3352              :     (abxy,
    3353              :      mgr.get_concat_bits ({&char_a, &char_b, &char_x, &char_y}));
    3354            4 :   abxy.to_json ();
    3355           24 :   for (concrete_byte_offset i = 0_bytes; i < 4_bytes; ++i)
    3356           16 :     ASSERT_EQ (abxy.scan_for_first_zero_byte (i),
    3357            4 :                string_scan::beyond_domain (4_bytes));
    3358              : 
    3359              :   /* Verify concat of concat.
    3360              :      This doesn't repeat right now; it instead unwraps everything.  */
    3361            4 :   auto &abab
    3362            4 :     = mgr.get_concat_bits ({&ab, &ab});
    3363            4 :   ASSERT_SAME_SYMBOLIC_NODE (abab.get_size (),
    3364              :                              bit_mgr.get_concrete (32_bits));
    3365            4 :   ASSERT_SAME_SYMBOLIC_NODE
    3366              :     (abab,
    3367              :      mgr.get_concat_bits ({&char_a, &char_b, &char_a, &char_b}));
    3368           24 :   for (concrete_byte_offset i = 0_bytes; i < 4_bytes; ++i)
    3369           16 :     ASSERT_EQ (abab.scan_for_first_zero_byte (i),
    3370            4 :                string_scan::beyond_domain (4_bytes));
    3371            4 : }
    3372              : 
    3373              : static void
    3374            4 : test_cropped ()
    3375              : {
    3376            4 :   symbolic::node_manager node_mgr;
    3377            4 :   auto &bv_mgr = node_mgr.get_bit_vector_manager ();
    3378            4 :   auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
    3379              : 
    3380            4 :   auto &a = bv_mgr.get_named_test_bit_vector (10_bytes, "A");
    3381            4 :   auto &b = bv_mgr.get_named_test_bit_vector (10_bytes, "B");
    3382              : 
    3383            4 :   a.to_json ();
    3384              : 
    3385              :   /* Verify the "can't fold" case, and dumping.  */
    3386            4 :   {
    3387           12 :     auto &bits = a.get_cropped_bytes (concrete_byte_range (5_bytes, 2_bytes));
    3388            4 :     ASSERT_SAME_SYMBOLIC_NODE (bits.get_size (),
    3389              :                                bit_mgr.get_concrete (16_bits));
    3390            4 :     ASSERT_SYMBOLIC_NODE_DUMP_EQ
    3391              :       (bits,
    3392              :        ("cropped_bit_vector[size: 2 bytes]: [bytes 5..7)\n"
    3393              :         "`- uncropped: named_test_bit_vector[size: 10 bytes]: 'A'\n"));
    3394            4 :     bits.to_json ();
    3395           16 :     for (concrete_byte_offset i = 0_bytes; i < 2_bytes; ++i)
    3396            8 :       ASSERT_EQ (bits.scan_for_first_zero_byte (i),
    3397            4 :                  string_scan::cannot_scan (i));
    3398           20 :     for (concrete_byte_offset i = 2_bytes; i < 5_bytes; ++i)
    3399           12 :       ASSERT_EQ (bits.scan_for_first_zero_byte (i),
    3400            4 :                  string_scan::beyond_domain (i));
    3401              : 
    3402              :     // Verify that consolidation works
    3403           12 :     ASSERT_SAME_SYMBOLIC_NODE
    3404              :       (a.get_cropped_bytes (concrete_byte_range (5_bytes, 2_bytes)),
    3405              :        bits);
    3406              : 
    3407              :     // Verify that we don't erroneously consolidate...
    3408              :     // ...different inner bit_vector:
    3409           12 :     ASSERT_DIFFERENT_SYMBOLIC_NODE
    3410              :       (b.get_cropped_bytes (concrete_byte_range (2_bytes, 2_bytes)),
    3411              :        bits);
    3412              :     // ...different start offset:
    3413           12 :     ASSERT_DIFFERENT_SYMBOLIC_NODE
    3414              :       (a.get_cropped_bytes (concrete_byte_range (6_bytes, 2_bytes)),
    3415              :        bits);
    3416              :     // ...different size:
    3417           12 :     ASSERT_DIFFERENT_SYMBOLIC_NODE
    3418              :       (a.get_cropped_bytes (concrete_byte_range (5_bytes, 1_byte)),
    3419              :        bits);
    3420              :   }
    3421              : 
    3422              :   /* Verify that A[0..size(A)] --> A.  */
    3423            4 :   {
    3424           12 :     auto &bits = a.get_cropped_bytes (concrete_byte_range (0_bytes, 10_bytes));
    3425            4 :     ASSERT_SAME_SYMBOLIC_NODE (bits, a);
    3426              :   }
    3427              : 
    3428              :   /* Verify that A[(empty)] --> empty.  */
    3429            4 :   {
    3430           12 :     auto &bits = a.get_cropped_bytes (concrete_byte_range (0_bytes, 0_bytes));
    3431            4 :     ASSERT_SAME_SYMBOLIC_NODE (bits, bv_mgr.get_empty ());
    3432              :   }
    3433              : 
    3434              :   /* Verify that concat(A[p, q], A[q, r]) --> A[p, r].  */
    3435            4 :   {
    3436           12 :     auto &a35 = a.get_cropped_bytes (concrete_byte_range (3_bytes, 3_bytes));
    3437            4 :     ASSERT_SAME_SYMBOLIC_NODE
    3438              :       (a35.get_size (),
    3439              :        bit_mgr.get_concrete (bits_from_bytes (3_bytes)));
    3440           12 :     auto &a67 = a.get_cropped_bytes (concrete_byte_range (6_bytes, 2_bytes));
    3441            4 :     ASSERT_SAME_SYMBOLIC_NODE
    3442              :       (a67.get_size (),
    3443              :        bit_mgr.get_concrete (bits_from_bytes (2_bytes)));
    3444            4 :     auto &a35a67 = bv_mgr.get_concat_bits ({&a35, &a67});
    3445            4 :     ASSERT_SAME_SYMBOLIC_NODE
    3446              :       (a35a67.get_size (),
    3447              :        bit_mgr.get_concrete (bits_from_bytes (5_bytes)));
    3448           12 :     ASSERT_SAME_SYMBOLIC_NODE
    3449              :       (a35a67,
    3450              :        a.get_cropped_bytes (concrete_byte_range (3_bytes, 5_bytes)));
    3451              :   }
    3452              : 
    3453              :   /* Verify that concat(A[0, n], A[n, size(A)]) --> A.  */
    3454            4 :   {
    3455           12 :     auto &a06 = a.get_cropped_bytes (concrete_byte_range (0_bytes, 7_bytes));
    3456           12 :     auto &a79 = a.get_cropped_bytes (concrete_byte_range (7_bytes, 3_bytes));
    3457            4 :     auto &a06a79 = bv_mgr.get_concat_bits ({&a06, &a79});
    3458            4 :     ASSERT_SAME_SYMBOLIC_NODE (a06a79, a);
    3459              :   }
    3460              : 
    3461              :   /* Verify crop of crop: e.g. A[5..10][2..3] --> A[7..8].  */
    3462            4 :   {
    3463           12 :     auto &a59 = a.get_cropped_bytes (concrete_byte_range (5_bytes, 5_bytes));
    3464            4 :     auto &a59_23
    3465           12 :       = a59.get_cropped_bytes (concrete_byte_range (2_bytes, 2_bytes));
    3466           12 :     ASSERT_SAME_SYMBOLIC_NODE
    3467              :       (a59_23,
    3468              :        a.get_cropped_bytes (concrete_byte_range (7_bytes, 2_bytes)));
    3469              :   }
    3470              : 
    3471              :   // Verify poisoned(x)[m..n] --> poisoned(x, sizeof(m..n)).
    3472            4 :   {
    3473            4 :     auto &bits
    3474            8 :       = (bv_mgr.get_poisoned_bits (bits_from_bytes (10_bytes),
    3475              :                                    poison_kind::uninit)
    3476           12 :          .get_cropped_bytes (concrete_byte_range (5_bytes, 2_bytes)));
    3477            4 :     ASSERT_SAME_SYMBOLIC_NODE
    3478              :       (bits.get_size (),
    3479              :        bit_mgr.get_concrete (bits_from_bytes (2_bytes)));
    3480            4 :     ASSERT_SAME_SYMBOLIC_NODE
    3481              :       (bits,
    3482              :        bv_mgr.get_poisoned_bits (16_bits, poison_kind::uninit));
    3483              :   }
    3484              : 
    3485              :   // Verify tristate(x)[m..n] --> tristate(x, sizeof(m..n)).
    3486            4 :   {
    3487            4 :     auto &bits
    3488            4 :       = (bv_mgr.get_all_zeros (10_bytes)
    3489           12 :          .get_cropped_bytes (concrete_byte_range (5_bytes, 2_bytes)));
    3490            4 :     ASSERT_SAME_SYMBOLIC_NODE
    3491              :       (bits.get_size (),
    3492              :        bit_mgr.get_concrete (bits_from_bytes (2_bytes)));
    3493            4 :     ASSERT_SAME_SYMBOLIC_NODE (bits, bv_mgr.get_all_zeros (16_bits));
    3494              :   }
    3495              : 
    3496              :   /* crop of concat e.g.:
    3497              :        concat(X1, ... Xn)[a, b] --> concat(X1[...], ..., Xn[...])
    3498              :   */
    3499            4 :   {
    3500            4 :     auto &x = bv_mgr.get_named_test_bit_vector (1_byte, "X");
    3501            4 :     auto &y = bv_mgr.get_named_test_bit_vector (1_byte, "Y");
    3502            4 :     auto &z = bv_mgr.get_named_test_bit_vector (1_byte, "Z");
    3503            4 :     auto &xyz = bv_mgr.get_concat_bits ({&x, &y, &z});
    3504           12 :     ASSERT_SAME_SYMBOLIC_NODE
    3505              :       (xyz.get_cropped_bytes (concrete_byte_range (0_bytes, 1_byte)),
    3506              :        x);
    3507           12 :     ASSERT_SAME_SYMBOLIC_NODE
    3508              :       (xyz.get_cropped_bytes (concrete_byte_range (1_byte, 1_byte)),
    3509              :        y);
    3510           12 :     ASSERT_SAME_SYMBOLIC_NODE
    3511              :       (xyz.get_cropped_bytes (concrete_byte_range (2_bytes, 1_byte)),
    3512              :        z);
    3513           12 :     ASSERT_SAME_SYMBOLIC_NODE
    3514              :       (xyz.get_cropped_bytes (concrete_byte_range (0_bytes, 2_bytes)),
    3515              :        bv_mgr.get_concat_bits ({&x, &y}));
    3516           12 :     ASSERT_SAME_SYMBOLIC_NODE
    3517              :       (xyz.get_cropped_bits (concrete_bit_range (3_bits, 9_bits)),
    3518              :        bv_mgr.get_concat_bits
    3519              :        ({&x.get_suffix (5_bits), &y.get_prefix (4_bits)}));
    3520              :   }
    3521              : 
    3522            4 :   {
    3523              :     /* 20 bytes: 5 repeats of a 4 byte vector:
    3524              :        If x is [abcd] then we have bytes 0-19:
    3525              :        .           1111111111
    3526              :        . 01234567890123456789
    3527              :        . abcdabcdabcdabcdabcd  */
    3528            4 :     auto &x = bv_mgr.get_named_test_bit_vector (4_bytes, "X");
    3529            4 :     auto &x_times_5 = bv_mgr.get_repeated_bits (x, 5);
    3530           12 :     ASSERT_SAME_SYMBOLIC_NODE
    3531              :       (x_times_5.get_cropped_bytes (concrete_byte_range (0_bytes, 20_bytes)),
    3532              :        x_times_5);
    3533              : 
    3534              :     /* Getting individual bytes.  */
    3535           88 :     for (concrete_byte_offset i = 0_bytes; i < 20_bytes; ++i)
    3536           80 :       ASSERT_SAME_SYMBOLIC_NODE
    3537              :         (x_times_5.get_byte_at_offset (i),
    3538            4 :          x.get_byte_at_offset (i.floor_mod (4_bytes)));
    3539              : 
    3540              :     // Cropping on an exact boundary should give us X again:
    3541           12 :     ASSERT_SAME_SYMBOLIC_NODE
    3542              :       (x_times_5.get_cropped_bytes (concrete_byte_range (0_bytes, 4_bytes)),
    3543              :        x);
    3544           12 :     ASSERT_SAME_SYMBOLIC_NODE
    3545              :       (x_times_5.get_cropped_bytes (concrete_byte_range (4_bytes, 4_bytes)),
    3546              :        x);
    3547              : 
    3548              :     /* Cropping at awkward boundaries.  */
    3549              :     /* Bytes [3,5).  */
    3550           12 :     ASSERT_SAME_SYMBOLIC_NODE
    3551              :       (x_times_5.get_cropped_bytes (concrete_byte_range (3_bytes, 2_bytes)),
    3552              :        bv_mgr.get_concat_bits
    3553              :        ({&x.get_suffix (1_byte),
    3554              :          &x.get_prefix (1_byte)}));
    3555              : 
    3556              :     /* Bytes [3,19):
    3557              :        .           1111111111
    3558              :        . 01234567890123456789
    3559              :        . abcdabcdabcdabcdabcd
    3560              :        .   [PQQQQQQQQQQQQRRR]
    3561              :        should give us:
    3562              :        - P: the last byte of X
    3563              :        - Q: 3 repeats of X
    3564              :        - R: the first 3 bytes of X.  */
    3565           28 :     ASSERT_SAME_SYMBOLIC_NODE
    3566              :       (x_times_5.get_cropped_bytes (concrete_byte_range (3_bytes, 16_bytes)),
    3567              :        bv_mgr.get_concat_bits
    3568              :        ({&x.get_cropped_bytes (concrete_byte_range (3_bytes, 1_byte)),
    3569              :          &bv_mgr.get_repeated_bits (x, 3),
    3570              :          &x.get_cropped_bytes (concrete_byte_range (0_bytes, 3_bytes))}));
    3571              :   }
    3572            4 : }
    3573              : 
    3574              : static void
    3575            4 : test_named_test_bit_vector ()
    3576              : {
    3577            4 :   symbolic::node_manager node_mgr;
    3578            4 :   auto &bv_mgr = node_mgr.get_bit_vector_manager ();
    3579            4 :   auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
    3580              : 
    3581            4 :   auto &x = bv_mgr.get_named_test_bit_vector (1024_bytes, "X");
    3582            4 :   ASSERT_SAME_SYMBOLIC_NODE
    3583              :     (x.get_size (),
    3584              :      bit_mgr.get_concrete (bits_from_bytes (1024_bytes)));
    3585            4 :   ASSERT_SYMBOLIC_NODE_DUMP_EQ
    3586              :     (x,
    3587              :      "named_test_bit_vector[size: 1024 bytes]: 'X'\n");
    3588            4 :   x.to_json ();
    3589            4 : }
    3590              : 
    3591              : static void
    3592            4 : test_poisoned ()
    3593              : {
    3594            4 :   symbolic::node_manager node_mgr;
    3595            4 :   auto &mgr = node_mgr.get_bit_vector_manager ();
    3596            4 :   auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
    3597              : 
    3598            4 :   auto &uninit_bit = mgr.get_poisoned_bits (1_bit, poison_kind::uninit);
    3599              : 
    3600            4 :   ASSERT_SAME_SYMBOLIC_NODE (uninit_bit.get_size (),
    3601              :                              bit_mgr.get_concrete (1_bit));
    3602            4 :   ASSERT_SYMBOLIC_NODE_DUMP_EQ (uninit_bit,
    3603              :                                 "poisoned_bit_vector[size: 1 bit]: uninit\n");
    3604              : 
    3605            4 :   ASSERT_SAME_SYMBOLIC_NODE
    3606              :     (mgr.get_poisoned_bits (0_bits, poison_kind::uninit),
    3607              :      mgr.get_empty ());
    3608              : 
    3609            4 :   uninit_bit.to_json ();
    3610              : 
    3611            4 :   auto &freed_bit = mgr.get_poisoned_bits (1_bit, poison_kind::freed);
    3612            4 :   ASSERT_SAME_SYMBOLIC_NODE (freed_bit.get_size (),
    3613              :                              bit_mgr.get_concrete (1_bit));
    3614            4 :   ASSERT_SYMBOLIC_NODE_DUMP_EQ (freed_bit,
    3615              :                                 "poisoned_bit_vector[size: 1 bit]: freed\n");
    3616              : 
    3617            4 :   freed_bit.to_json ();
    3618              : 
    3619            4 :   auto &three_uninit_bits
    3620            4 :     = mgr.get_poisoned_bits (3_bits, poison_kind::uninit);
    3621            4 :   ASSERT_SAME_SYMBOLIC_NODE (three_uninit_bits.get_size (),
    3622              :                              bit_mgr.get_concrete (3_bits));
    3623            4 :   ASSERT_SYMBOLIC_NODE_DUMP_EQ (three_uninit_bits,
    3624              :                                 "poisoned_bit_vector[size: 3 bits]: uninit\n");
    3625            4 : }
    3626              : 
    3627              : static void
    3628            4 : test_repeated ()
    3629              : {
    3630            4 :   symbolic::node_manager node_mgr;
    3631            4 :   auto &mgr = node_mgr.get_bit_vector_manager ();
    3632              : 
    3633            4 :   auto &byte_00 = mgr.get_all_zeros (1_byte);
    3634            4 :   ASSERT_SYMBOLIC_NODE_DUMP_EQ
    3635              :     (byte_00,
    3636              :      "tristate_bit_vector[size: 1 byte]: false bits\n");
    3637              : 
    3638              :   /* Verify that repeats of tristate_bit_vector are folded to
    3639              :      tristate_bit_vector.  */
    3640            4 :   auto &kilobyte_of_zeros = mgr.get_repeated_bits (byte_00, 1024);
    3641            4 :   ASSERT_SAME_SYMBOLIC_NODE (kilobyte_of_zeros, mgr.get_all_zeros (1024_bytes));
    3642              : 
    3643            4 :   kilobyte_of_zeros.to_json ();
    3644              : 
    3645              :   // Verify that 0 repeats is the empty bit vector:
    3646            4 :   ASSERT_SAME_SYMBOLIC_NODE (mgr.get_repeated_bits (byte_00, 0),
    3647              :                              mgr.get_empty ());
    3648              : 
    3649              :   // Verify that we fold repeats of repeats into repeats:
    3650            4 :   auto &char_A
    3651            4 :     = mgr.get_bits_for_constant (build_int_cst (char_type_node, 'A'));
    3652            4 :   auto &ten_As = mgr.get_repeated_bits (char_A, 10);
    3653            4 :   auto &two_times_ten_As = mgr.get_repeated_bits (ten_As, 2);
    3654            4 :   ASSERT_SAME_SYMBOLIC_NODE
    3655              :     (two_times_ten_As,
    3656              :      mgr.get_repeated_bits (char_A, 20));
    3657              : 
    3658            4 :   {
    3659            4 :     pretty_printer pp;
    3660            4 :     hexdump_options hexdump_opts;
    3661            4 :     hexdump_opts.m_bytes_per_line = 10_bytes;
    3662            4 :     two_times_ten_As.hexdump_to_pp (&pp, hexdump_opts);
    3663            4 :     ASSERT_STREQ
    3664              :       (pp_formatted_text (&pp),
    3665              :        "+--------------+-----------------------------+----------+\n"
    3666              :        "| [bytes 0..10)|41 41 41 41 41 41 41 41 41 41|AAAAAAAAAA|\n"
    3667              :        "+--------------+-----------------------------+----------+\n"
    3668              :        "|[bytes 10..20)|41 41 41 41 41 41 41 41 41 41|AAAAAAAAAA|\n"
    3669              :        "+--------------+-----------------------------+----------+\n");
    3670            4 :   }
    3671            4 :   {
    3672            4 :     pretty_printer pp;
    3673            4 :     hexdump_options hexdump_opts;
    3674            4 :     hexdump_opts.m_show_binary = true;
    3675            4 :     two_times_ten_As.hexdump_to_pp (&pp, hexdump_opts);
    3676            4 :     ASSERT_STREQ
    3677              :       (pp_formatted_text (&pp),
    3678              :        ("+--------------+-----------------------------------+-----------+----+\n"
    3679              :         "|  [bytes 0..4)|10000010 10000010 10000010 10000010|41 41 41 41|AAAA|\n"
    3680              :         "+--------------+-----------------------------------+-----------+----+\n"
    3681              :         "|  [bytes 4..8)|10000010 10000010 10000010 10000010|41 41 41 41|AAAA|\n"
    3682              :         "+--------------+-----------------------------------+-----------+----+\n"
    3683              :         "| [bytes 8..12)|10000010 10000010 10000010 10000010|41 41 41 41|AAAA|\n"
    3684              :         "+--------------+-----------------------------------+-----------+----+\n"
    3685              :         "|[bytes 12..16)|10000010 10000010 10000010 10000010|41 41 41 41|AAAA|\n"
    3686              :         "+--------------+-----------------------------------+-----------+----+\n"
    3687              :         "|[bytes 16..20)|10000010 10000010 10000010 10000010|41 41 41 41|AAAA|\n"
    3688              :         "+--------------+-----------------------------------+-----------+----+\n"));
    3689            4 :   }
    3690              : 
    3691              :   // Verify that repeat(A, 1) --> A.
    3692            4 :   ASSERT_SAME_SYMBOLIC_NODE (mgr.get_repeated_bits (char_A, 1), char_A);
    3693            4 : }
    3694              : 
    3695              : static void
    3696            4 : test_bit_vector_from_svalue ()
    3697              : {
    3698            4 :   symbolic::node_manager node_mgr;
    3699            4 :   auto &bv_mgr = node_mgr.get_bit_vector_manager ();
    3700            4 :   auto &rmm = node_mgr.get_svalue_manager ();
    3701              : 
    3702            4 :   auto *unknown_char_sval
    3703            4 :     = rmm.get_or_create_unknown_svalue (unsigned_char_type_node);
    3704            4 :   ASSERT_SAME_SYMBOLIC_NODE
    3705              :     (bv_mgr.get_bit_vector_from_svalue (*unknown_char_sval),
    3706              :      bv_mgr.get_unknown_bits (8_bits));
    3707              : 
    3708            4 :   unknown_char_sval->to_json ();
    3709              : 
    3710              :   /* Verify that we remove redundant casts
    3711              :      e.g. BIT_VECTOR_FOR (UNARY_OP(signed, NOP_EXPR, SVAL(unsigned)))
    3712              :      folds to BIT_VECTOR_FOR (SVAL(unsigned)).  */
    3713            4 :   {
    3714            4 :     placeholder_svalue sval (node_mgr.alloc_node_id (),
    3715            4 :                              integer_type_node, "x");
    3716            4 :     auto *cast_sval = rmm.get_or_create_cast (unsigned_type_node, &sval);
    3717            4 :     ASSERT_DIFFERENT_SYMBOLIC_NODE (sval, *cast_sval);
    3718            4 :     ASSERT_SAME_SYMBOLIC_NODE (bv_mgr.get_bit_vector_from_svalue (sval),
    3719              :                                bv_mgr.get_bit_vector_from_svalue (*cast_sval));
    3720            4 :   }
    3721              : 
    3722              :   /* Make a bit_vector from bitwise "and" and "or" against a concrete mask to
    3723              :      verify what we "know" about individual bits and bytes (using the
    3724              :      irange_bitmask).  */
    3725            4 :   {
    3726            4 :     placeholder_svalue y (node_mgr.alloc_node_id (),
    3727            4 :                           uint32_type_node, "y");
    3728            4 :     auto *mask = rmm.get_or_create_int_cst (uint32_type_node, 0xff00ff00);
    3729              : 
    3730            4 :     hexdump_options hexdump_opts;
    3731            4 :     hexdump_opts.m_show_binary = true;
    3732            4 :     hexdump_opts.m_show_ascii = false;
    3733              : 
    3734            4 :     {
    3735            4 :       auto *bitwise_and = rmm.get_or_create_binop (uint32_type_node,
    3736              :                                                    BIT_AND_EXPR,
    3737              :                                                    &y,
    3738              :                                                    mask);
    3739            4 :       auto &bv = bv_mgr.get_bit_vector_from_svalue (*bitwise_and);
    3740              : 
    3741              :       // Check what we know about individual bits in the bit_vector
    3742           40 :       for (auto i = 0_bits; i < 8_bits; ++i)
    3743           32 :         ASSERT_EQ (bv.get_tristate_at_offset (i), tristate (false));
    3744           40 :       for (auto i = 8_bits; i < 16_bits; ++i)
    3745           32 :         ASSERT_EQ (bv.get_tristate_at_offset (i), tristate::unknown ());
    3746           40 :       for (auto i = 16_bits; i < 24_bits; ++i)
    3747           32 :         ASSERT_EQ (bv.get_tristate_at_offset (i), tristate (false));
    3748           40 :       for (auto i = 24_bits; i < 32_bits; ++i)
    3749           32 :         ASSERT_EQ (bv.get_tristate_at_offset (i), tristate::unknown ());
    3750              : 
    3751              :       // Check what we know about individual bytes in the bit_vector
    3752            4 :       ASSERT_SAME_SYMBOLIC_NODE (bv.get_byte_at_offset (0_bytes),
    3753              :                                  bv_mgr.get_uint8 (0));
    3754            4 :       ASSERT_SAME_SYMBOLIC_NODE (bv.get_byte_at_offset (2_bytes),
    3755              :                                  bv_mgr.get_uint8 (0));
    3756              : 
    3757            4 :       pretty_printer pp;
    3758            4 :       bv.hexdump_to_pp (&pp, hexdump_opts);
    3759            4 :       ASSERT_STREQ
    3760              :         (pp_formatted_text (&pp),
    3761              :          "+------------+-----------------------------------+-----------+\n"
    3762              :          "|[bytes 0..4)|00000000 ???????? 00000000 ????????|00 ?? 00 ??|\n"
    3763              :          "+------------+-----------------------------------+-----------+\n");
    3764            4 :     }
    3765            4 :     {
    3766            4 :       auto *bitwise_or = rmm.get_or_create_binop (uint32_type_node,
    3767              :                                                   BIT_IOR_EXPR,
    3768              :                                                   &y,
    3769              :                                                   mask);
    3770            4 :       auto &bv = bv_mgr.get_bit_vector_from_svalue (*bitwise_or);
    3771              : 
    3772              :       // Check what we know about individual bits in the bit_vector
    3773           40 :       for (auto i = 0_bits; i < 8_bits; ++i)
    3774           32 :         ASSERT_EQ (bv.get_tristate_at_offset (i), tristate::unknown ());
    3775           40 :       for (auto i = 8_bits; i < 16_bits; ++i)
    3776           32 :         ASSERT_EQ (bv.get_tristate_at_offset (i), tristate (true));
    3777           40 :       for (auto i = 16_bits; i < 24_bits; ++i)
    3778           32 :         ASSERT_EQ (bv.get_tristate_at_offset (i), tristate::unknown ());
    3779           40 :       for (auto i = 24_bits; i < 32_bits; ++i)
    3780           32 :         ASSERT_EQ (bv.get_tristate_at_offset (i), tristate (true));
    3781              : 
    3782              :       // Check what we know about individual bytes in the bit_vector
    3783            4 :       ASSERT_SAME_SYMBOLIC_NODE (bv.get_byte_at_offset (1_byte),
    3784              :                                  bv_mgr.get_uint8 (0xff));
    3785            4 :       ASSERT_SAME_SYMBOLIC_NODE (bv.get_byte_at_offset (3_bytes),
    3786              :                                  bv_mgr.get_uint8 (0xff));
    3787              : 
    3788            4 :       pretty_printer pp;
    3789            4 :       bv.hexdump_to_pp (&pp, hexdump_opts);
    3790            4 :       ASSERT_STREQ
    3791              :         (pp_formatted_text (&pp),
    3792              :          "+------------+-----------------------------------+-----------+\n"
    3793              :          "|[bytes 0..4)|???????? 11111111 ???????? 11111111|?? ff ?? ff|\n"
    3794              :          "+------------+-----------------------------------+-----------+\n");
    3795            4 :     }
    3796            4 :   }
    3797            4 : }
    3798              : 
    3799              : /* Consider this buggy C code (writing to a fixed-size buffer with no
    3800              :    size checks on inputs):
    3801              :    |   char buf[1024];
    3802              :    |   len_a = strlen (str_a);
    3803              :    |   len_b = strlen (str_b);
    3804              :    |   memcpy (buf, str_a, len_a);
    3805              :    |   memcpy (buf + len_a, str_b, len_b);
    3806              :    |   buf[len_a + len_b] = '\0';
    3807              :  */
    3808              : static void
    3809            4 : test_example_strcat ()
    3810              : {
    3811            4 :   symbolic::node_manager node_mgr;
    3812            4 :   auto &bv_mgr = node_mgr.get_bit_vector_manager ();
    3813            4 :   auto &byte_mgr = node_mgr.get_scalars ().get_bytes ();
    3814              : 
    3815            4 :   auto &strlen_a = byte_mgr.get_named_test_scalar ("strlen(a)");
    3816            4 :   auto &strlen_b = byte_mgr.get_named_test_scalar ("strlen(b)");
    3817            4 :   auto &a = bv_mgr.get_named_test_bit_vector (strlen_a + 1_byte, "a");
    3818            4 :   auto &b = bv_mgr.get_named_test_bit_vector (strlen_b + 1_byte, "b");
    3819              : 
    3820            4 :   auto &bv_for_buf = bv_mgr.get_concat_bits
    3821           12 :     ({&a.get_prefix (strlen_a),
    3822            4 :       &b.get_prefix (strlen_b),
    3823            4 :       &bv_mgr.get_uint8 (0)});
    3824              : 
    3825            4 :   ASSERT_SAME_SYMBOLIC_NODE
    3826              :     (bv_for_buf.get_size (),
    3827              :      bits_from_bytes (strlen_a + strlen_b + 1_byte));
    3828            4 :   ASSERT_SAME_SYMBOLIC_NODE
    3829              :     (*maybe_bytes_from_bits (bv_for_buf.get_size ()),
    3830              :      strlen_a + strlen_b + 1_byte);
    3831            4 : }
    3832              : 
    3833              : static void
    3834            4 : test_from_unfoldable_bit_contents ()
    3835              : {
    3836            4 :   symbolic::node_manager mgr;
    3837            4 :   auto &bv_mgr = mgr.get_bit_vector_manager ();
    3838            4 :   auto &bc_mgr = mgr.get_bit_contents_manager ();
    3839              : 
    3840            4 :   auto &ubc_a = bc_mgr.get_named_test_bit_contents ("A");
    3841            4 :   auto &ubc_b = bc_mgr.get_named_test_bit_contents ("B");
    3842              : 
    3843           12 :   ASSERT_SYMBOLIC_NODE_DUMP_EQ
    3844              :     (ubc_a.get_bytes (concrete_byte_range (0_bytes, 10_bytes)),
    3845              :      ("bit_vector_from_ubc[size: 10 bytes]\n"
    3846              :       "+- bit_contents: named_test_bit_contents: A\n"
    3847              :       "`- range: symbolic range\n"
    3848              :       "   +- start offset: concrete_scalar<bits>: 0\n"
    3849              :       "   `- size: concrete_scalar<bits>: 80\n"));
    3850              : 
    3851           20 :   ASSERT_SAME_SYMBOLIC_NODE
    3852              :     (ubc_a.get_bytes (concrete_byte_range (0_bytes, 10_bytes)),
    3853              :      ubc_a.get_bytes (concrete_byte_range (0_bytes, 10_bytes)));
    3854              : 
    3855           20 :   ASSERT_DIFFERENT_SYMBOLIC_NODE
    3856              :     (ubc_a.get_bytes (concrete_byte_range (0_bytes, 10_bytes)),
    3857              :      ubc_a.get_bytes (concrete_byte_range (0_bytes, 9_bytes)));
    3858              : 
    3859           20 :   ASSERT_DIFFERENT_SYMBOLIC_NODE
    3860              :     (ubc_a.get_bytes (concrete_byte_range (0_bytes, 10_bytes)),
    3861              :      ubc_b.get_bytes (concrete_byte_range (0_bytes, 10_bytes)));
    3862              : 
    3863              :   /* Concat of touching ranges from same bit contents should
    3864              :      be folded to a single range from that bit contents.  */
    3865           28 :   ASSERT_SAME_SYMBOLIC_NODE
    3866              :     (bv_mgr.get_concat_bits
    3867              :      ({&ubc_a.get_bytes (concrete_byte_range (0_bytes, 4_bytes)),
    3868              :        &ubc_a.get_bytes (concrete_byte_range (4_bytes, 6_bytes))}),
    3869              :      ubc_a.get_bytes (concrete_byte_range (0_bytes, 10_bytes)));
    3870              :   /* ...but not for those that don't touch:  */
    3871           28 :   ASSERT_DIFFERENT_SYMBOLIC_NODE
    3872              :     (bv_mgr.get_concat_bits
    3873              :      ({&ubc_a.get_bytes (concrete_byte_range (0_bytes, 4_bytes)),
    3874              :        &ubc_a.get_bytes (concrete_byte_range (5_bytes, 5_bytes))}),
    3875              :      ubc_a.get_bytes (concrete_byte_range (0_bytes, 10_bytes)));
    3876              :   /* ...but not for those from different bit contents:  */
    3877           28 :   ASSERT_DIFFERENT_SYMBOLIC_NODE
    3878              :     (bv_mgr.get_concat_bits
    3879              :      ({&ubc_a.get_bytes (concrete_byte_range (0_bytes, 4_bytes)),
    3880              :        &ubc_b.get_bytes (concrete_byte_range (4_bytes, 6_bytes))}),
    3881              :      ubc_a.get_bytes (concrete_byte_range (0_bytes, 10_bytes)));
    3882              : 
    3883              :   /* Cropping a range from a ubc should give the appropriate
    3884              :      subrange from the ubc.  */
    3885            4 :   auto &a_bytes_10_14
    3886           12 :     = ubc_a.get_bytes (concrete_byte_range (10_bytes, 5_bytes));
    3887           12 :   ASSERT_SAME_SYMBOLIC_NODE
    3888              :     (a_bytes_10_14.get_cropped_bytes (concrete_byte_range (0_bytes, 5_bytes)),
    3889              :      a_bytes_10_14);
    3890           20 :   ASSERT_SAME_SYMBOLIC_NODE
    3891              :     (a_bytes_10_14.get_cropped_bytes (concrete_byte_range (0_bytes, 1_byte)),
    3892              :      ubc_a.get_bytes (concrete_byte_range (10_bytes, 1_byte)));
    3893           20 :   ASSERT_SAME_SYMBOLIC_NODE
    3894              :     (a_bytes_10_14.get_cropped_bytes (concrete_byte_range (4_bytes, 1_byte)),
    3895              :      ubc_a.get_bytes (concrete_byte_range (14_bytes, 1_byte)));
    3896            4 : }
    3897              : 
    3898              : /* Test type-punning uint32_t to bytes, using the target's endianness.  */
    3899              : 
    3900              : static void
    3901            4 : test_uint32_t_to_bytes ()
    3902              : {
    3903            4 :   symbolic::node_manager mgr;
    3904            4 :   auto &bv_mgr = mgr.get_bit_vector_manager ();
    3905            4 :   auto &rmm = mgr.get_region_model_manager ();
    3906              : 
    3907            4 :   auto &uint32_0x12345678
    3908            4 :     = *rmm.get_or_create_int_cst (uint32_type_node, 0x12345678);
    3909            4 :   auto &bv_0x12345678 = bv_mgr.get_bit_vector_from_svalue (uint32_0x12345678);
    3910              : 
    3911            4 :   auto &uint8_0x12
    3912            4 :     = *rmm.get_or_create_int_cst (unsigned_char_type_node, 0x12);
    3913            4 :   auto &bv_0x12 = bv_mgr.get_bit_vector_from_svalue (uint8_0x12);
    3914              : 
    3915            4 :   auto &uint8_0x34
    3916            4 :     = *rmm.get_or_create_int_cst (unsigned_char_type_node, 0x34);
    3917            4 :   auto &bv_0x34 = bv_mgr.get_bit_vector_from_svalue (uint8_0x34);
    3918              : 
    3919            4 :   auto &uint8_0x56
    3920            4 :     = *rmm.get_or_create_int_cst (unsigned_char_type_node, 0x56);
    3921            4 :   auto &bv_0x56 = bv_mgr.get_bit_vector_from_svalue (uint8_0x56);
    3922              : 
    3923            4 :   auto &uint8_0x78
    3924            4 :     = *rmm.get_or_create_int_cst (unsigned_char_type_node, 0x78);
    3925            4 :   auto &bv_0x78 = bv_mgr.get_bit_vector_from_svalue (uint8_0x78);
    3926              : 
    3927            4 :   auto &bv_byte_0 = bv_0x12345678.get_byte_at_offset (0_bytes);
    3928            4 :   auto &bv_byte_1 = bv_0x12345678.get_byte_at_offset (1_byte);
    3929            4 :   auto &bv_byte_2 = bv_0x12345678.get_byte_at_offset (2_bytes);
    3930            4 :   auto &bv_byte_3 = bv_0x12345678.get_byte_at_offset (3_bytes);
    3931              : 
    3932            4 :   if (BYTES_BIG_ENDIAN)
    3933              :     {
    3934              :       ASSERT_SAME_SYMBOLIC_NODE (bv_byte_0, bv_0x12);
    3935              :       ASSERT_SAME_SYMBOLIC_NODE (bv_byte_1, bv_0x34);
    3936              :       ASSERT_SAME_SYMBOLIC_NODE (bv_byte_2, bv_0x56);
    3937              :       ASSERT_SAME_SYMBOLIC_NODE (bv_byte_3, bv_0x78);
    3938              :     }
    3939              :   else
    3940              :     {
    3941              :       /* Little-endian.  */
    3942            4 :       if (!WORDS_BIG_ENDIAN)
    3943              :         {
    3944            4 :           ASSERT_SAME_SYMBOLIC_NODE (bv_byte_0, bv_0x78);
    3945            4 :           ASSERT_SAME_SYMBOLIC_NODE (bv_byte_1, bv_0x56);
    3946            4 :           ASSERT_SAME_SYMBOLIC_NODE (bv_byte_2, bv_0x34);
    3947            4 :           ASSERT_SAME_SYMBOLIC_NODE (bv_byte_3, bv_0x12);
    3948              :         }
    3949              :     }
    3950            4 : }
    3951              : 
    3952              : /* Test type-punning bytes to uint32_t, using the target's endianness.  */
    3953              : 
    3954              : static void
    3955            4 : test_bytes_to_uint32_t ()
    3956              : {
    3957            4 :   symbolic::node_manager mgr;
    3958            4 :   auto &bv_mgr = mgr.get_bit_vector_manager ();
    3959            4 :   auto &rmm = mgr.get_region_model_manager ();
    3960              : 
    3961            4 :   auto &uint8_0x12
    3962            4 :     = *rmm.get_or_create_int_cst (unsigned_char_type_node, 0x12);
    3963            4 :   auto &bv_0x12 = bv_mgr.get_bit_vector_from_svalue (uint8_0x12);
    3964              : 
    3965            4 :   auto &uint8_0x34
    3966            4 :     = *rmm.get_or_create_int_cst (unsigned_char_type_node, 0x34);
    3967            4 :   auto &bv_0x34 = bv_mgr.get_bit_vector_from_svalue (uint8_0x34);
    3968              : 
    3969            4 :   auto &uint8_0x56
    3970            4 :     = *rmm.get_or_create_int_cst (unsigned_char_type_node, 0x56);
    3971            4 :   auto &bv_0x56 = bv_mgr.get_bit_vector_from_svalue (uint8_0x56);
    3972              : 
    3973            4 :   auto &uint8_0x78
    3974            4 :     = *rmm.get_or_create_int_cst (unsigned_char_type_node, 0x78);
    3975            4 :   auto &bv_0x78 = bv_mgr.get_bit_vector_from_svalue (uint8_0x78);
    3976              : 
    3977            4 :   auto &bytes
    3978            4 :     = bv_mgr.get_concat_bits  ({&bv_0x12, &bv_0x34, &bv_0x56, &bv_0x78});
    3979              : 
    3980            4 :   const svalue *sval = rmm.get_svalue_from_bit_vector (uint32_type_node, bytes);
    3981              : 
    3982            4 :   const uint32_t expected_uint32 = (BYTES_BIG_ENDIAN
    3983              :                                     ? 0x12345678
    3984              :                                     : (WORDS_BIG_ENDIAN
    3985              :                                        ? 0x34127856
    3986              :                                        : 0x78563412));
    3987            4 :   ASSERT_SAME_SYMBOLIC_NODE
    3988              :     (*sval,
    3989              :      *rmm.get_or_create_int_cst (uint32_type_node, expected_uint32));
    3990            4 : }
    3991              : 
    3992              : static void
    3993            4 : test_every_byte_value ()
    3994              : {
    3995            4 :   symbolic::node_manager mgr;
    3996            4 :   auto &bv_mgr = mgr.get_bit_vector_manager ();
    3997              : 
    3998            4 :   std::vector<const symbolic::bit_vector *> vec_of_every_byte_value;
    3999         1028 :   for (int i = 0; i < 256; ++i)
    4000         1024 :     vec_of_every_byte_value.push_back (&bv_mgr.get_uint8 (i));
    4001            4 :   auto &every_byte_value_bv
    4002            4 :     = bv_mgr.get_concat_bits (std::move (vec_of_every_byte_value));
    4003              : 
    4004            4 :   {
    4005            4 :     hexdump_options hexdump_opts;
    4006            4 :     hexdump_opts.m_show_binary = true;
    4007            4 :     hexdump_opts.m_show_hex = true;
    4008            4 :     hexdump_opts.m_show_ascii = false;
    4009              : 
    4010              :     /* Hexdump of first 8 bytes.  */
    4011            4 :     {
    4012            4 :       pretty_printer pp;
    4013            4 :       every_byte_value_bv
    4014           12 :         .get_cropped_bytes (concrete_byte_range (0_bytes, 8_bytes))
    4015            4 :         .hexdump_to_pp (&pp, hexdump_opts);
    4016            4 :       ASSERT_STREQ
    4017              :         (pp_formatted_text (&pp),
    4018              :          ("+------------+-----------------------------------+-----------+\n"
    4019              :           "|[bytes 0..4)|00000000 10000000 01000000 11000000|00 01 02 03|\n"
    4020              :           "+------------+-----------------------------------+-----------+\n"
    4021              :           "|[bytes 4..8)|00100000 10100000 01100000 11100000|04 05 06 07|\n"
    4022              :           "+------------+-----------------------------------+-----------+\n"));
    4023            4 :     }
    4024              : 
    4025              :     /* Hexdump of last 8 bytes.  */
    4026            4 :     {
    4027            4 :       pretty_printer pp;
    4028            4 :       every_byte_value_bv
    4029           12 :         .get_cropped_bytes (concrete_byte_range (248_bytes, 8_bytes))
    4030            4 :         .hexdump_to_pp (&pp, hexdump_opts);
    4031            4 :       ASSERT_STREQ
    4032              :         (pp_formatted_text (&pp),
    4033              :          ("+------------+-----------------------------------+-----------+\n"
    4034              :           "|[bytes 0..4)|00011111 10011111 01011111 11011111|f8 f9 fa fb|\n"
    4035              :           "+------------+-----------------------------------+-----------+\n"
    4036              :           "|[bytes 4..8)|00111111 10111111 01111111 11111111|fc fd fe ff|\n"
    4037              :           "+------------+-----------------------------------+-----------+\n"));
    4038            4 :     }
    4039            4 :   }
    4040            4 : }
    4041              : 
    4042              : /* Run all of the selftests within this file.  */
    4043              : 
    4044              : void
    4045            4 : analyzer_symbolic_bit_vectors_cc_tests ()
    4046              : {
    4047            4 :   test_maybe_set_irange_bitmask_from_concrete_tristate_vector ();
    4048            4 :   test_tristate ();
    4049            4 :   test_integer_constants ();
    4050            4 :   test_bytes ();
    4051            4 :   test_string_constants ();
    4052            4 :   test_raw_data_constant_1 ();
    4053            4 :   test_raw_data_constant_2 ();
    4054            4 :   test_raw_data_constant_empty ();
    4055            4 :   test_concat ();
    4056            4 :   test_cropped ();
    4057            4 :   test_named_test_bit_vector ();
    4058            4 :   test_poisoned ();
    4059            4 :   test_repeated ();
    4060            4 :   test_bit_vector_from_svalue ();
    4061            4 :   test_from_unfoldable_bit_contents ();
    4062            4 :   test_example_strcat ();
    4063            4 :   test_uint32_t_to_bytes ();
    4064            4 :   test_bytes_to_uint32_t ();
    4065            4 :   test_every_byte_value ();
    4066            4 : }
    4067              : 
    4068              : } // namespace selftest
    4069              : 
    4070              : #endif /* CHECKING_P */
    4071              : 
    4072              : } // namespace ana
    4073              : 
    4074              : #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.