LCOV - code coverage report
Current view: top level - gcc/analyzer - store.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 81.8 % 1098 898
Test Date: 2026-11-14 16:39:50 Functions: 81.4 % 102 83
Legend: Lines:     hit not hit

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

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.