LCOV - code coverage report
Current view: top level - gcc/analyzer - store.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 83.2 % 1698 1413
Test Date: 2024-11-30 13:30:02 Functions: 85.8 % 134 115
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* Classes for modeling the state of memory.
       2                 :             :    Copyright (C) 2020-2024 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 "config.h"
      22                 :             : #define INCLUDE_VECTOR
      23                 :             : #include "system.h"
      24                 :             : #include "coretypes.h"
      25                 :             : #include "tree.h"
      26                 :             : #include "function.h"
      27                 :             : #include "basic-block.h"
      28                 :             : #include "gimple.h"
      29                 :             : #include "gimple-iterator.h"
      30                 :             : #include "diagnostic-core.h"
      31                 :             : #include "graphviz.h"
      32                 :             : #include "options.h"
      33                 :             : #include "cgraph.h"
      34                 :             : #include "tree-dfa.h"
      35                 :             : #include "stringpool.h"
      36                 :             : #include "convert.h"
      37                 :             : #include "target.h"
      38                 :             : #include "fold-const.h"
      39                 :             : #include "tree-pretty-print.h"
      40                 :             : #include "diagnostic-color.h"
      41                 :             : #include "bitmap.h"
      42                 :             : #include "selftest.h"
      43                 :             : #include "analyzer/analyzer.h"
      44                 :             : #include "analyzer/analyzer-logging.h"
      45                 :             : #include "ordered-hash-map.h"
      46                 :             : #include "options.h"
      47                 :             : #include "cfg.h"
      48                 :             : #include "analyzer/supergraph.h"
      49                 :             : #include "sbitmap.h"
      50                 :             : #include "analyzer/call-string.h"
      51                 :             : #include "analyzer/program-point.h"
      52                 :             : #include "analyzer/store.h"
      53                 :             : #include "analyzer/region-model.h"
      54                 :             : #include "analyzer/call-summary.h"
      55                 :             : #include "analyzer/analyzer-selftests.h"
      56                 :             : #include "stor-layout.h"
      57                 :             : #include "text-art/tree-widget.h"
      58                 :             : #include "make-unique.h"
      59                 :             : 
      60                 :             : #if ENABLE_ANALYZER
      61                 :             : 
      62                 :             : namespace ana {
      63                 :             : 
      64                 :             : /* Dump SVALS to PP, sorting them to ensure determinism.  */
      65                 :             : 
      66                 :             : static void
      67                 :         496 : dump_svalue_set (const hash_set <const svalue *> &svals,
      68                 :             :                  pretty_printer *pp, bool simple)
      69                 :             : {
      70                 :         496 :   auto_vec <const svalue *> v;
      71                 :         496 :   for (hash_set<const svalue *>::iterator iter = svals.begin ();
      72                 :         560 :        iter != svals.end (); ++iter)
      73                 :             :     {
      74                 :          32 :       v.safe_push (*iter);
      75                 :             :     }
      76                 :         496 :   v.qsort (svalue::cmp_ptr_ptr);
      77                 :             : 
      78                 :         496 :   pp_character (pp, '{');
      79                 :         496 :   const svalue *sval;
      80                 :         496 :   unsigned i;
      81                 :        1024 :   FOR_EACH_VEC_ELT (v, i, sval)
      82                 :             :     {
      83                 :          32 :       if (i > 0)
      84                 :          19 :         pp_string (pp, ", ");
      85                 :          32 :       sval->dump_to_pp (pp, simple);
      86                 :             :     }
      87                 :         496 :   pp_character (pp, '}');
      88                 :         496 : }
      89                 :             : 
      90                 :             : /* class uncertainty_t.  */
      91                 :             : 
      92                 :             : /* Dump this object to PP.  */
      93                 :             : 
      94                 :             : void
      95                 :         248 : uncertainty_t::dump_to_pp (pretty_printer *pp, bool simple) const
      96                 :             : {
      97                 :         248 :   pp_string (pp, "{m_maybe_bound_svals: ");
      98                 :         248 :   dump_svalue_set (m_maybe_bound_svals, pp, simple);
      99                 :             : 
     100                 :         248 :   pp_string (pp, ", m_mutable_at_unknown_call_svals: ");
     101                 :         248 :   dump_svalue_set (m_mutable_at_unknown_call_svals, pp, simple);
     102                 :         248 :   pp_string (pp, "}");
     103                 :         248 : }
     104                 :             : 
     105                 :             : /* Dump this object to stderr.  */
     106                 :             : 
     107                 :             : DEBUG_FUNCTION void
     108                 :           0 : uncertainty_t::dump (bool simple) const
     109                 :             : {
     110                 :           0 :   tree_dump_pretty_printer pp (stderr);
     111                 :           0 :   dump_to_pp (&pp, simple);
     112                 :           0 :   pp_newline (&pp);
     113                 :           0 : }
     114                 :             : 
     115                 :             : /* class binding_key.  */
     116                 :             : 
     117                 :             : const binding_key *
     118                 :     3457227 : binding_key::make (store_manager *mgr, const region *r)
     119                 :             : {
     120                 :     3457227 :   region_offset offset = r->get_offset (mgr->get_svalue_manager ());
     121                 :     3457227 :   if (offset.symbolic_p ())
     122                 :       36591 :     return mgr->get_symbolic_binding (r);
     123                 :             :   else
     124                 :             :     {
     125                 :     3420636 :       bit_size_t bit_size;
     126                 :     3420636 :       if (r->get_bit_size (&bit_size))
     127                 :             :         {
     128                 :             :           /* Must be non-empty.  */
     129                 :     2169063 :           gcc_assert (bit_size > 0);
     130                 :     2169063 :           return mgr->get_concrete_binding (offset.get_bit_offset (),
     131                 :     2169063 :                                             bit_size);
     132                 :             :         }
     133                 :             :       else
     134                 :     1251573 :         return mgr->get_symbolic_binding (r);
     135                 :             :     }
     136                 :             : }
     137                 :             : 
     138                 :             : /* Dump this binding_key to stderr.  */
     139                 :             : 
     140                 :             : DEBUG_FUNCTION void
     141                 :           0 : binding_key::dump (bool simple) const
     142                 :             : {
     143                 :           0 :   tree_dump_pretty_printer pp (stderr);
     144                 :           0 :   dump_to_pp (&pp, simple);
     145                 :           0 :   pp_newline (&pp);
     146                 :           0 : }
     147                 :             : 
     148                 :             : /* Get a description of this binding_key.  */
     149                 :             : 
     150                 :             : label_text
     151                 :           0 : binding_key::get_desc (bool simple) const
     152                 :             : {
     153                 :           0 :   pretty_printer pp;
     154                 :           0 :   pp_format_decoder (&pp) = default_tree_printer;
     155                 :           0 :   dump_to_pp (&pp, simple);
     156                 :           0 :   return label_text::take (xstrdup (pp_formatted_text (&pp)));
     157                 :           0 : }
     158                 :             : 
     159                 :             : /* qsort callback.  */
     160                 :             : 
     161                 :             : int
     162                 :        4524 : binding_key::cmp_ptrs (const void *p1, const void *p2)
     163                 :             : {
     164                 :        4524 :   const binding_key * const *pk1 = (const binding_key * const *)p1;
     165                 :        4524 :   const binding_key * const *pk2 = (const binding_key * const *)p2;
     166                 :        4524 :   return cmp (*pk1, *pk2);
     167                 :             : }
     168                 :             : 
     169                 :             : /* Comparator for binding_keys.  */
     170                 :             : 
     171                 :             : int
     172                 :        4524 : binding_key::cmp (const binding_key *k1, const binding_key *k2)
     173                 :             : {
     174                 :        4524 :   int concrete1 = k1->concrete_p ();
     175                 :        4524 :   int concrete2 = k2->concrete_p ();
     176                 :        4524 :   if (int concrete_cmp = concrete1 - concrete2)
     177                 :             :     return concrete_cmp;
     178                 :        4524 :   if (concrete1)
     179                 :             :     {
     180                 :        4524 :       const concrete_binding *b1 = (const concrete_binding *)k1;
     181                 :        4524 :       const concrete_binding *b2 = (const concrete_binding *)k2;
     182                 :        4524 :       if (int start_cmp = wi::cmp (b1->get_start_bit_offset (),
     183                 :        4524 :                                    b2->get_start_bit_offset (),
     184                 :             :                                    SIGNED))
     185                 :             :         return start_cmp;
     186                 :        1536 :       return wi::cmp (b1->get_next_bit_offset (), b2->get_next_bit_offset (),
     187                 :             :                       SIGNED);
     188                 :             :     }
     189                 :             :   else
     190                 :             :     {
     191                 :           0 :       const symbolic_binding *s1 = (const symbolic_binding *)k1;
     192                 :           0 :       const symbolic_binding *s2 = (const symbolic_binding *)k2;
     193                 :           0 :       if (s1 > s2)
     194                 :             :         return 1;
     195                 :           0 :       if (s1 < s2)
     196                 :             :         return -1;
     197                 :           0 :       return 0;
     198                 :             :     }
     199                 :             : }
     200                 :             : 
     201                 :             : /* struct bit_range.  */
     202                 :             : 
     203                 :             : void
     204                 :        2313 : bit_range::dump_to_pp (pretty_printer *pp) const
     205                 :             : {
     206                 :        2313 :   byte_range bytes (0, 0);
     207                 :        2313 :   if (as_byte_range (&bytes))
     208                 :        2313 :     bytes.dump_to_pp (pp);
     209                 :             :   else
     210                 :             :     {
     211                 :           0 :       pp_string (pp, "start: ");
     212                 :           0 :       pp_wide_int (pp, m_start_bit_offset, SIGNED);
     213                 :           0 :       pp_string (pp, ", size: ");
     214                 :           0 :       pp_wide_int (pp, m_size_in_bits, SIGNED);
     215                 :           0 :       pp_string (pp, ", next: ");
     216                 :           0 :       pp_wide_int (pp, get_next_bit_offset (), SIGNED);
     217                 :             :     }
     218                 :        2313 : }
     219                 :             : 
     220                 :             : /* Dump this object to stderr.  */
     221                 :             : 
     222                 :             : DEBUG_FUNCTION void
     223                 :           0 : bit_range::dump () const
     224                 :             : {
     225                 :           0 :   tree_dump_pretty_printer pp (stderr);
     226                 :           0 :   dump_to_pp (&pp);
     227                 :           0 :   pp_newline (&pp);
     228                 :           0 : }
     229                 :             : 
     230                 :             : /* Generate a JSON value for this bit_range.
     231                 :             :    This is intended for debugging the analyzer rather
     232                 :             :    than serialization.  */
     233                 :             : 
     234                 :             : std::unique_ptr<json::object>
     235                 :           4 : bit_range::to_json () const
     236                 :             : {
     237                 :           4 :   auto obj = ::make_unique<json::object> ();
     238                 :           4 :   obj->set ("start_bit_offset",
     239                 :           4 :             bit_offset_to_json (m_start_bit_offset));
     240                 :           4 :   obj->set ("size_in_bits",
     241                 :           4 :             bit_offset_to_json (m_size_in_bits));
     242                 :           4 :   return obj;
     243                 :             : }
     244                 :             : 
     245                 :             : /* If OTHER is a subset of this, return true and, if OUT is
     246                 :             :    non-null, write to *OUT the relative range of OTHER within this.
     247                 :             :    Otherwise return false.  */
     248                 :             : 
     249                 :             : bool
     250                 :       40077 : bit_range::contains_p (const bit_range &other, bit_range *out) const
     251                 :             : {
     252                 :       40077 :   if (contains_p (other.get_start_bit_offset ())
     253                 :       40077 :       && contains_p (other.get_last_bit_offset ()))
     254                 :             :     {
     255                 :       27035 :       if (out)
     256                 :             :         {
     257                 :       27035 :           out->m_start_bit_offset = other.m_start_bit_offset - m_start_bit_offset;
     258                 :       27035 :           out->m_size_in_bits = other.m_size_in_bits;
     259                 :             :         }
     260                 :       27035 :       return true;
     261                 :             :     }
     262                 :             :   else
     263                 :       13042 :     return false;
     264                 :             : }
     265                 :             : 
     266                 :             : /* If OTHER intersects this, return true and write
     267                 :             :    the relative range of OTHER within THIS to *OUT_THIS,
     268                 :             :    and the relative range of THIS within OTHER to *OUT_OTHER.
     269                 :             :    Otherwise return false.  */
     270                 :             : 
     271                 :             : bool
     272                 :          84 : bit_range::intersects_p (const bit_range &other,
     273                 :             :                          bit_range *out_this,
     274                 :             :                          bit_range *out_other) const
     275                 :             : {
     276                 :          84 :   if (get_start_bit_offset () < other.get_next_bit_offset ()
     277                 :         168 :       && other.get_start_bit_offset () < get_next_bit_offset ())
     278                 :             :     {
     279                 :          84 :       bit_offset_t overlap_start
     280                 :          84 :         = MAX (get_start_bit_offset (),
     281                 :             :                other.get_start_bit_offset ());
     282                 :          84 :       bit_offset_t overlap_next
     283                 :          84 :         = MIN (get_next_bit_offset (),
     284                 :             :                other.get_next_bit_offset ());
     285                 :          84 :       if (overlap_next <= overlap_start)
     286                 :             :         /* If this has happened, some kind of overflow has happened in
     287                 :             :            our arithmetic.  For now, reject such cases.  */
     288                 :             :         return false;
     289                 :          84 :       bit_range abs_overlap_bits (overlap_start, overlap_next - overlap_start);
     290                 :          84 :       *out_this = abs_overlap_bits - get_start_bit_offset ();
     291                 :          84 :       *out_other = abs_overlap_bits - other.get_start_bit_offset ();
     292                 :          84 :       return true;
     293                 :             :     }
     294                 :             :   else
     295                 :           0 :     return false;
     296                 :             : }
     297                 :             : 
     298                 :             : /* Return true if THIS and OTHER intersect and write the number
     299                 :             :    of bits both buffers overlap to *OUT_NUM_OVERLAP_BITS.
     300                 :             : 
     301                 :             :    Otherwise return false.  */
     302                 :             : 
     303                 :             : bool
     304                 :           0 : bit_range::intersects_p (const bit_range &other,
     305                 :             :                          bit_size_t *out_num_overlap_bits) const
     306                 :             : {
     307                 :           0 :   if (get_start_bit_offset () < other.get_next_bit_offset ()
     308                 :           0 :       && other.get_start_bit_offset () < get_next_bit_offset ())
     309                 :             :     {
     310                 :           0 :       bit_offset_t overlap_start = MAX (get_start_bit_offset (),
     311                 :             :                                          other.get_start_bit_offset ());
     312                 :           0 :       bit_offset_t overlap_next = MIN (get_next_bit_offset (),
     313                 :             :                                         other.get_next_bit_offset ());
     314                 :           0 :       if (overlap_next <= overlap_start)
     315                 :             :         /* If this has happened, some kind of overflow has happened in
     316                 :             :            our arithmetic.  For now, reject such cases.  */
     317                 :             :         return false;
     318                 :           0 :       *out_num_overlap_bits = overlap_next - overlap_start;
     319                 :           0 :       return true;
     320                 :             :     }
     321                 :             :   else
     322                 :           0 :     return false;
     323                 :             : }
     324                 :             : 
     325                 :             : /* Return true if THIS exceeds OTHER and write the overhanging
     326                 :             :    bit range to OUT_OVERHANGING_BIT_RANGE.  */
     327                 :             : 
     328                 :             : bool
     329                 :      631647 : bit_range::exceeds_p (const bit_range &other,
     330                 :             :                       bit_range *out_overhanging_bit_range) const
     331                 :             : {
     332                 :      631647 :   gcc_assert (!empty_p ());
     333                 :             : 
     334                 :      631647 :   if (other.get_next_bit_offset () < get_next_bit_offset ())
     335                 :             :     {
     336                 :             :       /* THIS definitely exceeds OTHER.  */
     337                 :         456 :       bit_offset_t start = MAX (get_start_bit_offset (),
     338                 :             :                                  other.get_next_bit_offset ());
     339                 :         456 :       bit_offset_t size = get_next_bit_offset () - start;
     340                 :         456 :       if (size <= 0)
     341                 :             :         /* If this has happened, some kind of overflow has happened in
     342                 :             :            our arithmetic.  For now, reject such cases.  */
     343                 :             :         return false;
     344                 :         436 :       out_overhanging_bit_range->m_start_bit_offset = start;
     345                 :         436 :       out_overhanging_bit_range->m_size_in_bits = size;
     346                 :         436 :       return true;
     347                 :             :     }
     348                 :             :   else
     349                 :             :     return false;
     350                 :             : }
     351                 :             : 
     352                 :             : /* Return true if THIS falls short of OFFSET and write the
     353                 :             :    bit range fallen short to OUT_FALL_SHORT_BITS.  */
     354                 :             : 
     355                 :             : bool
     356                 :      634622 : bit_range::falls_short_of_p (bit_offset_t offset,
     357                 :             :                              bit_range *out_fall_short_bits) const
     358                 :             : {
     359                 :      634622 :   gcc_assert (!empty_p ());
     360                 :             : 
     361                 :      634622 :   if (get_start_bit_offset () < offset)
     362                 :             :     {
     363                 :             :       /* THIS falls short of OFFSET.  */
     364                 :         184 :       bit_offset_t start = get_start_bit_offset ();
     365                 :         184 :       bit_offset_t size = MIN (offset, get_next_bit_offset ()) - start;
     366                 :         184 :       if (size <= 0)
     367                 :             :         /* If this has happened, some kind of overflow has happened in
     368                 :             :            our arithmetic.  For now, reject such cases.  */
     369                 :             :         return false;
     370                 :         164 :       out_fall_short_bits->m_start_bit_offset = start;
     371                 :         164 :       out_fall_short_bits->m_size_in_bits = size;
     372                 :         164 :       return true;
     373                 :             :     }
     374                 :             :   else
     375                 :             :     return false;
     376                 :             : }
     377                 :             : 
     378                 :             : int
     379                 :         304 : bit_range::cmp (const bit_range &br1, const bit_range &br2)
     380                 :             : {
     381                 :         304 :   if (int start_cmp = wi::cmps (br1.m_start_bit_offset,
     382                 :         304 :                                 br2.m_start_bit_offset))
     383                 :             :     return start_cmp;
     384                 :             : 
     385                 :          12 :   return wi::cmpu (br1.m_size_in_bits, br2.m_size_in_bits);
     386                 :             : }
     387                 :             : 
     388                 :             : /* Offset this range by OFFSET.  */
     389                 :             : 
     390                 :             : bit_range
     391                 :         168 : bit_range::operator- (bit_offset_t offset) const
     392                 :             : {
     393                 :         168 :   return bit_range (m_start_bit_offset - offset, m_size_in_bits);
     394                 :             : }
     395                 :             : 
     396                 :             : /* If MASK is a contiguous range of set bits, write them
     397                 :             :    to *OUT and return true.
     398                 :             :    Otherwise return false.  */
     399                 :             : 
     400                 :             : bool
     401                 :         144 : bit_range::from_mask (unsigned HOST_WIDE_INT mask, bit_range *out)
     402                 :             : {
     403                 :         144 :   unsigned iter_bit_idx = 0;
     404                 :         144 :   unsigned HOST_WIDE_INT iter_bit_mask = 1;
     405                 :             : 
     406                 :             :   /* Find the first contiguous run of set bits in MASK.  */
     407                 :             : 
     408                 :             :   /* Find first set bit in MASK.  */
     409                 :         780 :   while (iter_bit_idx < HOST_BITS_PER_WIDE_INT)
     410                 :             :     {
     411                 :         776 :       if (mask & iter_bit_mask)
     412                 :             :         break;
     413                 :         636 :       iter_bit_idx++;
     414                 :         636 :       iter_bit_mask <<= 1;
     415                 :             :     }
     416                 :         144 :   if (iter_bit_idx == HOST_BITS_PER_WIDE_INT)
     417                 :             :     /* MASK is zero.  */
     418                 :             :     return false;
     419                 :             : 
     420                 :         140 :   unsigned first_set_iter_bit_idx = iter_bit_idx;
     421                 :         140 :   unsigned num_set_bits = 1;
     422                 :         140 :   iter_bit_idx++;
     423                 :         140 :   iter_bit_mask <<= 1;
     424                 :             : 
     425                 :             :   /* Find next unset bit in MASK.  */
     426                 :         396 :   while (iter_bit_idx < HOST_BITS_PER_WIDE_INT)
     427                 :             :     {
     428                 :         396 :       if (!(mask & iter_bit_mask))
     429                 :             :         break;
     430                 :         256 :       num_set_bits++;
     431                 :         256 :       iter_bit_idx++;
     432                 :         256 :       iter_bit_mask <<= 1;
     433                 :             :     }
     434                 :         140 :   if (iter_bit_idx == HOST_BITS_PER_WIDE_INT)
     435                 :             :     {
     436                 :           0 :       *out = bit_range (first_set_iter_bit_idx, num_set_bits);
     437                 :           0 :       return true;
     438                 :             :     }
     439                 :             : 
     440                 :             :   /* We now have the first contiguous run of set bits in MASK.
     441                 :             :      Fail if any other bits are set.  */
     442                 :        7892 :   while (iter_bit_idx < HOST_BITS_PER_WIDE_INT)
     443                 :             :     {
     444                 :        7760 :       if (mask & iter_bit_mask)
     445                 :             :         return false;
     446                 :        7752 :       iter_bit_idx++;
     447                 :        7752 :       iter_bit_mask <<= 1;
     448                 :             :     }
     449                 :             : 
     450                 :         132 :   *out = bit_range (first_set_iter_bit_idx, num_set_bits);
     451                 :         132 :   return true;
     452                 :             : }
     453                 :             : 
     454                 :             : /* Attempt to convert this bit_range to a byte_range.
     455                 :             :    Return true if it is possible, writing the result to *OUT.
     456                 :             :    Otherwise return false.  */
     457                 :             : 
     458                 :             : bool
     459                 :        7572 : bit_range::as_byte_range (byte_range *out) const
     460                 :             : {
     461                 :        7572 :   if (m_start_bit_offset % BITS_PER_UNIT == 0
     462                 :        7572 :       && m_size_in_bits % BITS_PER_UNIT == 0)
     463                 :             :     {
     464                 :        7555 :       out->m_start_byte_offset = m_start_bit_offset / BITS_PER_UNIT;
     465                 :        7555 :       out->m_size_in_bytes = m_size_in_bits / BITS_PER_UNIT;
     466                 :        7555 :       return true;
     467                 :             :     }
     468                 :             :   return false;
     469                 :             : }
     470                 :             : 
     471                 :             : /* Dump this object to PP.  */
     472                 :             : 
     473                 :             : void
     474                 :        2313 : byte_range::dump_to_pp (pretty_printer *pp) const
     475                 :             : {
     476                 :        2313 :   if (m_size_in_bytes == 0)
     477                 :             :     {
     478                 :           0 :       pp_string (pp, "empty");
     479                 :             :     }
     480                 :        2313 :   else if (m_size_in_bytes == 1)
     481                 :             :     {
     482                 :        1595 :       pp_string (pp, "byte ");
     483                 :        1595 :       pp_wide_int (pp, m_start_byte_offset, SIGNED);
     484                 :             :     }
     485                 :             :   else
     486                 :             :     {
     487                 :         718 :       pp_string (pp, "bytes ");
     488                 :         718 :       pp_wide_int (pp, m_start_byte_offset, SIGNED);
     489                 :         718 :       pp_string (pp, "-");
     490                 :         718 :       pp_wide_int (pp, get_last_byte_offset (), SIGNED);
     491                 :             :     }
     492                 :        2313 : }
     493                 :             : 
     494                 :             : /* Dump this object to stderr.  */
     495                 :             : 
     496                 :             : DEBUG_FUNCTION void
     497                 :           0 : byte_range::dump () const
     498                 :             : {
     499                 :           0 :   tree_dump_pretty_printer pp (stderr);
     500                 :           0 :   dump_to_pp (&pp);
     501                 :           0 :   pp_newline (&pp);
     502                 :           0 : }
     503                 :             : 
     504                 :             : /* Generate a JSON value for this byte_range.
     505                 :             :    This is intended for debugging the analyzer rather
     506                 :             :    than serialization.  */
     507                 :             : 
     508                 :             : std::unique_ptr<json::object>
     509                 :           4 : byte_range::to_json () const
     510                 :             : {
     511                 :           4 :   auto obj = ::make_unique<json::object> ();
     512                 :           4 :   obj->set ("start_byte_offset",
     513                 :           4 :             byte_offset_to_json (m_start_byte_offset));
     514                 :           4 :   obj->set ("size_in_bytes",
     515                 :           4 :             byte_offset_to_json (m_size_in_bytes));
     516                 :           4 :   return obj;
     517                 :             : }
     518                 :             : 
     519                 :             : /* If OTHER is a subset of this, return true and write
     520                 :             :    to *OUT the relative range of OTHER within this.
     521                 :             :    Otherwise return false.  */
     522                 :             : 
     523                 :             : bool
     524                 :         628 : byte_range::contains_p (const byte_range &other, byte_range *out) const
     525                 :             : {
     526                 :         628 :   if (contains_p (other.get_start_byte_offset ())
     527                 :         628 :       && contains_p (other.get_last_byte_offset ()))
     528                 :             :     {
     529                 :         321 :       out->m_start_byte_offset = other.m_start_byte_offset - m_start_byte_offset;
     530                 :         321 :       out->m_size_in_bytes = other.m_size_in_bytes;
     531                 :         321 :       return true;
     532                 :             :     }
     533                 :             :   else
     534                 :         307 :     return false;
     535                 :             : }
     536                 :             : 
     537                 :             : /* qsort comparator for byte ranges.  */
     538                 :             : 
     539                 :             : int
     540                 :         571 : byte_range::cmp (const byte_range &br1, const byte_range &br2)
     541                 :             : {
     542                 :             :   /* Order first by offset.  */
     543                 :         571 :   if (int start_cmp = wi::cmps (br1.m_start_byte_offset,
     544                 :         571 :                                 br2.m_start_byte_offset))
     545                 :             :     return start_cmp;
     546                 :             : 
     547                 :             :   /* ...then by size.  */
     548                 :           0 :   return wi::cmpu (br1.m_size_in_bytes, br2.m_size_in_bytes);
     549                 :             : }
     550                 :             : 
     551                 :             : /* class concrete_binding : public binding_key.  */
     552                 :             : 
     553                 :             : /* Implementation of binding_key::dump_to_pp vfunc for concrete_binding.  */
     554                 :             : 
     555                 :             : void
     556                 :        1648 : concrete_binding::dump_to_pp (pretty_printer *pp, bool) const
     557                 :             : {
     558                 :        1648 :   m_bit_range.dump_to_pp (pp);
     559                 :        1648 : }
     560                 :             : 
     561                 :             : /* Return true if this binding overlaps with OTHER.  */
     562                 :             : 
     563                 :             : bool
     564                 :      106007 : concrete_binding::overlaps_p (const concrete_binding &other) const
     565                 :             : {
     566                 :      106007 :   if (get_start_bit_offset () < other.get_next_bit_offset ()
     567                 :      106007 :       && get_next_bit_offset () > other.get_start_bit_offset ())
     568                 :       65360 :     return true;
     569                 :             :   return false;
     570                 :             : }
     571                 :             : 
     572                 :             : /* If this is expressible as a concrete byte range, return true
     573                 :             :    and write it to *OUT.  Otherwise return false.  */
     574                 :             : 
     575                 :             : bool
     576                 :         683 : concrete_binding::get_byte_range (byte_range *out) const
     577                 :             : {
     578                 :         683 :   return m_bit_range.as_byte_range (out);
     579                 :             : }
     580                 :             : 
     581                 :             : /* Comparator for use by vec<const concrete_binding *>::qsort.  */
     582                 :             : 
     583                 :             : int
     584                 :          48 : concrete_binding::cmp_ptr_ptr (const void *p1, const void *p2)
     585                 :             : {
     586                 :          48 :   const concrete_binding *b1 = *(const concrete_binding * const *)p1;
     587                 :          48 :   const concrete_binding *b2 = *(const concrete_binding * const *)p2;
     588                 :             : 
     589                 :          48 :   return bit_range::cmp (b1->m_bit_range, b2->m_bit_range);
     590                 :             : }
     591                 :             : 
     592                 :             : /* class symbolic_binding : public binding_key.  */
     593                 :             : 
     594                 :             : void
     595                 :           2 : symbolic_binding::dump_to_pp (pretty_printer *pp, bool simple) const
     596                 :             : {
     597                 :             :   //binding_key::dump_to_pp (pp, simple);
     598                 :           2 :   pp_string (pp, "region: ");
     599                 :           2 :   m_region->dump_to_pp (pp, simple);
     600                 :           2 : }
     601                 :             : 
     602                 :             : /* Comparator for use by vec<const symbolic_binding *>::qsort.  */
     603                 :             : 
     604                 :             : int
     605                 :           4 : symbolic_binding::cmp_ptr_ptr (const void *p1, const void *p2)
     606                 :             : {
     607                 :           4 :   const symbolic_binding *b1 = *(const symbolic_binding * const *)p1;
     608                 :           4 :   const symbolic_binding *b2 = *(const symbolic_binding * const *)p2;
     609                 :             : 
     610                 :           4 :   return region::cmp_ids (b1->get_region (), b2->get_region ());
     611                 :             : }
     612                 :             : 
     613                 :             : /* The store is oblivious to the types of the svalues bound within
     614                 :             :    it: any type can get bound at any location.
     615                 :             :    Simplify any casts before binding.
     616                 :             : 
     617                 :             :    For example, if we have:
     618                 :             :      struct big { int ia[1024]; };
     619                 :             :      struct big src, dst;
     620                 :             :      memcpy (&dst, &src, sizeof (struct big));
     621                 :             :    this reaches us in gimple form as:
     622                 :             :      MEM <unsigned char[4096]> [(char * {ref-all})&dst]
     623                 :             :        = MEM <unsigned char[4096]> [(char * {ref-all})&src];
     624                 :             :    Using cast_region when handling the MEM_REF would give us:
     625                 :             :      INIT_VAL(CAST_REG(unsigned char[4096], src))
     626                 :             :    as rhs_sval, but we can fold that into a cast svalue:
     627                 :             :      CAST(unsigned char[4096], INIT_VAL(src))
     628                 :             :    We can discard that cast from the svalue when binding it in
     629                 :             :    the store for "dst", and simply store:
     630                 :             :      cluster for: dst
     631                 :             :        key:   {kind: direct, start: 0, size: 32768, next: 32768}
     632                 :             :        value: ‘struct big’ {INIT_VAL(src)}.  */
     633                 :             : 
     634                 :             : static const svalue *
     635                 :      382902 : simplify_for_binding (const svalue *sval)
     636                 :             : {
     637                 :      382902 :   if (const svalue *cast_sval = sval->maybe_undo_cast ())
     638                 :           0 :     sval = cast_sval;
     639                 :       61002 :   return sval;
     640                 :             : }
     641                 :             : 
     642                 :             : /* class binding_map.  */
     643                 :             : 
     644                 :             : /* binding_map's copy ctor.  */
     645                 :             : 
     646                 :    23860888 : binding_map::binding_map (const binding_map &other)
     647                 :    23860888 : : m_map (other.m_map)
     648                 :             : {
     649                 :    23860888 : }
     650                 :             : 
     651                 :             : /* binding_map's assignment operator.  */
     652                 :             : 
     653                 :             : binding_map&
     654                 :           0 : binding_map::operator=(const binding_map &other)
     655                 :             : {
     656                 :             :   /* For now, assume we only ever copy to an empty cluster.  */
     657                 :           0 :   gcc_assert (m_map.elements () == 0);
     658                 :           0 :   for (map_t::iterator iter = other.m_map.begin (); iter != other.m_map.end ();
     659                 :           0 :        ++iter)
     660                 :             :     {
     661                 :           0 :       const binding_key *key = (*iter).first;
     662                 :           0 :       const svalue *sval = (*iter).second;
     663                 :           0 :       m_map.put (key, sval);
     664                 :             :     }
     665                 :           0 :   return *this;
     666                 :             : }
     667                 :             : 
     668                 :             : /* binding_map's equality operator.  */
     669                 :             : 
     670                 :             : bool
     671                 :     1968316 : binding_map::operator== (const binding_map &other) const
     672                 :             : {
     673                 :     1968316 :   if (m_map.elements () != other.m_map.elements ())
     674                 :             :     return false;
     675                 :             : 
     676                 :     5940370 :   for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
     677                 :             :     {
     678                 :     2029754 :       const binding_key *key = (*iter).first;
     679                 :     2029754 :       const svalue *sval = (*iter).second;
     680                 :     2029754 :       const svalue **other_slot
     681                 :     2029754 :         = const_cast <map_t &> (other.m_map).get (key);
     682                 :     2029754 :       if (other_slot == NULL)
     683                 :       35687 :         return false;
     684                 :     2022903 :       if (sval != *other_slot)
     685                 :             :         return false;
     686                 :             :     }
     687                 :     1916549 :   gcc_checking_assert (hash () == other.hash ());
     688                 :             :   return true;
     689                 :             : }
     690                 :             : 
     691                 :             : /* Generate a hash value for this binding_map.  */
     692                 :             : 
     693                 :             : hashval_t
     694                 :    17416389 : binding_map::hash () const
     695                 :             : {
     696                 :    17416389 :   hashval_t result = 0;
     697                 :    35456830 :   for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
     698                 :             :     {
     699                 :             :       /* Use a new hasher for each key to avoid depending on the ordering
     700                 :             :          of keys when accumulating the result.  */
     701                 :    18040441 :       inchash::hash hstate;
     702                 :    18040441 :       hstate.add_ptr ((*iter).first);
     703                 :    18040441 :       hstate.add_ptr ((*iter).second);
     704                 :    18040441 :       result ^= hstate.end ();
     705                 :             :     }
     706                 :    17416389 :   return result;
     707                 :             : }
     708                 :             : 
     709                 :             : /* Dump a representation of this binding_map to PP.
     710                 :             :    SIMPLE controls how values and regions are to be printed.
     711                 :             :    If MULTILINE, then split the dump over multiple lines and
     712                 :             :    use whitespace for readability, otherwise put all on one line.  */
     713                 :             : 
     714                 :             : void
     715                 :        2173 : binding_map::dump_to_pp (pretty_printer *pp, bool simple,
     716                 :             :                          bool multiline) const
     717                 :             : {
     718                 :        2173 :   auto_vec <const binding_key *> binding_keys;
     719                 :        3816 :   for (map_t::iterator iter = m_map.begin ();
     720                 :        5459 :        iter != m_map.end (); ++iter)
     721                 :             :     {
     722                 :        1643 :       const binding_key *key = (*iter).first;
     723                 :        1643 :       binding_keys.safe_push (key);
     724                 :             :     }
     725                 :        2173 :   binding_keys.qsort (binding_key::cmp_ptrs);
     726                 :             : 
     727                 :             :   const binding_key *key;
     728                 :             :   unsigned i;
     729                 :        4745 :   FOR_EACH_VEC_ELT (binding_keys, i, key)
     730                 :             :     {
     731                 :        1643 :       const svalue *value = *const_cast <map_t &> (m_map).get (key);
     732                 :        1643 :       if (multiline)
     733                 :             :         {
     734                 :         328 :           pp_string (pp, "    key:   {");
     735                 :         328 :           key->dump_to_pp (pp, simple);
     736                 :         328 :           pp_string (pp, "}");
     737                 :         328 :           pp_newline (pp);
     738                 :         328 :           pp_string (pp, "    value: ");
     739                 :         328 :           if (tree t = value->get_type ())
     740                 :         328 :             dump_quoted_tree (pp, t);
     741                 :         328 :           pp_string (pp, " {");
     742                 :         328 :           value->dump_to_pp (pp, simple);
     743                 :         328 :           pp_string (pp, "}");
     744                 :         328 :           pp_newline (pp);
     745                 :             :         }
     746                 :             :       else
     747                 :             :         {
     748                 :        1315 :           if (i > 0)
     749                 :         566 :             pp_string (pp, ", ");
     750                 :        1315 :           pp_string (pp, "binding key: {");
     751                 :        1315 :           key->dump_to_pp (pp, simple);
     752                 :        1315 :           pp_string (pp, "}, value: {");
     753                 :        1315 :           value->dump_to_pp (pp, simple);
     754                 :        1315 :           pp_string (pp, "}");
     755                 :             :         }
     756                 :             :     }
     757                 :        2173 : }
     758                 :             : 
     759                 :             : /* Dump a multiline representation of this binding_map to stderr.  */
     760                 :             : 
     761                 :             : DEBUG_FUNCTION void
     762                 :           0 : binding_map::dump (bool simple) const
     763                 :             : {
     764                 :           0 :   tree_dump_pretty_printer pp (stderr);
     765                 :           0 :   dump_to_pp (&pp, simple, true);
     766                 :           0 :   pp_newline (&pp);
     767                 :           0 : }
     768                 :             : 
     769                 :             : /* Return a new json::object of the form
     770                 :             :    {KEY_DESC : SVALUE_DESC,
     771                 :             :     ...for the various key/value pairs in this binding_map}.  */
     772                 :             : 
     773                 :             : std::unique_ptr<json::object>
     774                 :           0 : binding_map::to_json () const
     775                 :             : {
     776                 :           0 :   auto map_obj = ::make_unique<json::object> ();
     777                 :             : 
     778                 :           0 :   auto_vec <const binding_key *> binding_keys;
     779                 :           0 :   for (map_t::iterator iter = m_map.begin ();
     780                 :           0 :        iter != m_map.end (); ++iter)
     781                 :             :     {
     782                 :           0 :       const binding_key *key = (*iter).first;
     783                 :           0 :       binding_keys.safe_push (key);
     784                 :             :     }
     785                 :           0 :   binding_keys.qsort (binding_key::cmp_ptrs);
     786                 :             : 
     787                 :             :   const binding_key *key;
     788                 :             :   unsigned i;
     789                 :           0 :   FOR_EACH_VEC_ELT (binding_keys, i, key)
     790                 :             :     {
     791                 :           0 :       const svalue *value = *const_cast <map_t &> (m_map).get (key);
     792                 :           0 :       label_text key_desc = key->get_desc ();
     793                 :           0 :       map_obj->set (key_desc.get (), value->to_json ());
     794                 :           0 :     }
     795                 :             : 
     796                 :           0 :   return map_obj;
     797                 :           0 : }
     798                 :             : 
     799                 :             : /* Add a child to PARENT_WIDGET expressing a binding between
     800                 :             :    KEY and SVAL.  */
     801                 :             : 
     802                 :             : static void
     803                 :           0 : add_binding_to_tree_widget (text_art::tree_widget &parent_widget,
     804                 :             :                             const text_art::dump_widget_info &dwi,
     805                 :             :                             const binding_key *key,
     806                 :             :                             const svalue *sval)
     807                 :             : {
     808                 :           0 :   pretty_printer the_pp;
     809                 :           0 :   pretty_printer * const pp = &the_pp;
     810                 :           0 :   pp_format_decoder (pp) = default_tree_printer;
     811                 :           0 :   pp_show_color (pp) = true;
     812                 :           0 :   const bool simple = true;
     813                 :             : 
     814                 :           0 :   key->dump_to_pp (pp, simple);
     815                 :           0 :   pp_string (pp, ": ");
     816                 :           0 :   if (tree t = sval->get_type ())
     817                 :           0 :     dump_quoted_tree (pp, t);
     818                 :           0 :   pp_string (pp, " {");
     819                 :           0 :   sval->dump_to_pp (pp, simple);
     820                 :           0 :   pp_string (pp, "}");
     821                 :             : 
     822                 :           0 :   parent_widget.add_child (text_art::tree_widget::make (dwi, pp));
     823                 :           0 : }
     824                 :             : 
     825                 :             : void
     826                 :           0 : binding_map::add_to_tree_widget (text_art::tree_widget &parent_widget,
     827                 :             :                                  const text_art::dump_widget_info &dwi) const
     828                 :             : {
     829                 :           0 :   auto_vec <const binding_key *> binding_keys;
     830                 :           0 :   for (map_t::iterator iter = m_map.begin ();
     831                 :           0 :        iter != m_map.end (); ++iter)
     832                 :             :     {
     833                 :           0 :       const binding_key *key = (*iter).first;
     834                 :           0 :       binding_keys.safe_push (key);
     835                 :             :     }
     836                 :           0 :   binding_keys.qsort (binding_key::cmp_ptrs);
     837                 :             : 
     838                 :             :   const binding_key *key;
     839                 :             :   unsigned i;
     840                 :           0 :   FOR_EACH_VEC_ELT (binding_keys, i, key)
     841                 :             :     {
     842                 :           0 :       const svalue *sval = *const_cast <map_t &> (m_map).get (key);
     843                 :           0 :       add_binding_to_tree_widget (parent_widget, dwi,
     844                 :             :                                   key, sval);
     845                 :             :     }
     846                 :           0 : }
     847                 :             : 
     848                 :             : 
     849                 :             : /* Comparator for imposing an order on binding_maps.  */
     850                 :             : 
     851                 :             : int
     852                 :           0 : binding_map::cmp (const binding_map &map1, const binding_map &map2)
     853                 :             : {
     854                 :           0 :   if (int count_cmp = map1.elements () - map2.elements ())
     855                 :             :     return count_cmp;
     856                 :             : 
     857                 :           0 :   auto_vec <const binding_key *> keys1 (map1.elements ());
     858                 :           0 :   for (map_t::iterator iter = map1.begin ();
     859                 :           0 :        iter != map1.end (); ++iter)
     860                 :           0 :     keys1.quick_push ((*iter).first);
     861                 :           0 :   keys1.qsort (binding_key::cmp_ptrs);
     862                 :             : 
     863                 :           0 :   auto_vec <const binding_key *> keys2 (map2.elements ());
     864                 :           0 :   for (map_t::iterator iter = map2.begin ();
     865                 :           0 :        iter != map2.end (); ++iter)
     866                 :           0 :     keys2.quick_push ((*iter).first);
     867                 :           0 :   keys2.qsort (binding_key::cmp_ptrs);
     868                 :             : 
     869                 :           0 :   for (size_t i = 0; i < keys1.length (); i++)
     870                 :             :     {
     871                 :           0 :       const binding_key *k1 = keys1[i];
     872                 :           0 :       const binding_key *k2 = keys2[i];
     873                 :           0 :       if (int key_cmp = binding_key::cmp (k1, k2))
     874                 :             :         return key_cmp;
     875                 :           0 :       gcc_assert (k1 == k2);
     876                 :           0 :       if (int sval_cmp = svalue::cmp_ptr (map1.get (k1), map2.get (k2)))
     877                 :             :         return sval_cmp;
     878                 :             :     }
     879                 :             : 
     880                 :             :   return 0;
     881                 :           0 : }
     882                 :             : 
     883                 :             : /* Get the child region of PARENT_REG based upon INDEX within a
     884                 :             :    CONSTRUCTOR.   */
     885                 :             : 
     886                 :             : static const region *
     887                 :         441 : get_subregion_within_ctor (const region *parent_reg, tree index,
     888                 :             :                            region_model_manager *mgr)
     889                 :             : {
     890                 :         441 :   switch (TREE_CODE (index))
     891                 :             :     {
     892                 :           0 :     default:
     893                 :           0 :       gcc_unreachable ();
     894                 :         387 :     case INTEGER_CST:
     895                 :         387 :       {
     896                 :         387 :         const svalue *index_sval
     897                 :         387 :           = mgr->get_or_create_constant_svalue (index);
     898                 :         387 :         return mgr->get_element_region (parent_reg,
     899                 :         387 :                                         TREE_TYPE (parent_reg->get_type ()),
     900                 :         387 :                                         index_sval);
     901                 :             :       }
     902                 :          54 :       break;
     903                 :          54 :     case FIELD_DECL:
     904                 :          54 :       return mgr->get_field_region (parent_reg, index);
     905                 :             :     }
     906                 :             : }
     907                 :             : 
     908                 :             : /* Get the svalue for VAL, a non-CONSTRUCTOR value within a CONSTRUCTOR.  */
     909                 :             : 
     910                 :             : static const svalue *
     911                 :         402 : get_svalue_for_ctor_val (tree val, region_model_manager *mgr)
     912                 :             : {
     913                 :             :   /* Reuse the get_rvalue logic from region_model.  */
     914                 :         402 :   region_model m (mgr);
     915                 :         402 :   return m.get_rvalue (path_var (val, 0), NULL);
     916                 :         402 : }
     917                 :             : 
     918                 :             : /* Bind values from CONSTRUCTOR to this map, relative to
     919                 :             :    PARENT_REG's relationship to its base region.
     920                 :             :    Return true if successful, false if there was a problem (e.g. due
     921                 :             :    to hitting a complexity limit).  */
     922                 :             : 
     923                 :             : bool
     924                 :         144 : binding_map::apply_ctor_to_region (const region *parent_reg, tree ctor,
     925                 :             :                                    region_model_manager *mgr)
     926                 :             : {
     927                 :         144 :   gcc_assert (parent_reg);
     928                 :         144 :   gcc_assert (TREE_CODE (ctor) == CONSTRUCTOR);
     929                 :             : 
     930                 :         144 :   unsigned ix;
     931                 :         144 :   tree index;
     932                 :         144 :   tree val;
     933                 :         144 :   tree parent_type = parent_reg->get_type ();
     934                 :         144 :   tree field;
     935                 :         144 :   if (TREE_CODE (parent_type) == RECORD_TYPE)
     936                 :          48 :     field = TYPE_FIELDS (parent_type);
     937                 :             :   else
     938                 :             :     field = NULL_TREE;
     939                 :         584 :   FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), ix, index, val)
     940                 :             :     {
     941                 :         441 :       if (!index)
     942                 :             :         {
     943                 :             :           /* If index is NULL, then iterate through the fields for
     944                 :             :              a RECORD_TYPE, or use an INTEGER_CST otherwise.
     945                 :             :              Compare with similar logic in output_constructor.  */
     946                 :         135 :           if (field)
     947                 :             :             {
     948                 :           0 :               index = field;
     949                 :           0 :               field = DECL_CHAIN (field);
     950                 :             :             }
     951                 :             :           else
     952                 :         135 :             index = build_int_cst (integer_type_node, ix);
     953                 :             :         }
     954                 :         306 :       else if (TREE_CODE (index) == RANGE_EXPR)
     955                 :             :         {
     956                 :           0 :           tree min_index = TREE_OPERAND (index, 0);
     957                 :           0 :           tree max_index = TREE_OPERAND (index, 1);
     958                 :           0 :           if (min_index == max_index)
     959                 :             :             {
     960                 :           0 :               if (!apply_ctor_pair_to_child_region (parent_reg, mgr,
     961                 :             :                                                     min_index, val))
     962                 :             :                 return false;
     963                 :             :             }
     964                 :             :           else
     965                 :             :             {
     966                 :           0 :               if (!apply_ctor_val_to_range (parent_reg, mgr,
     967                 :             :                                             min_index, max_index, val))
     968                 :             :                 return false;
     969                 :             :             }
     970                 :           0 :           continue;
     971                 :           0 :         }
     972                 :         441 :       if (!apply_ctor_pair_to_child_region (parent_reg, mgr, index, val))
     973                 :             :         return false;
     974                 :             :     }
     975                 :             :   return true;
     976                 :             : }
     977                 :             : 
     978                 :             : /* Bind the value VAL into the range of elements within PARENT_REF
     979                 :             :    from MIN_INDEX to MAX_INDEX (including endpoints).
     980                 :             :    For use in handling RANGE_EXPR within a CONSTRUCTOR.
     981                 :             :    Return true if successful, false if there was a problem (e.g. due
     982                 :             :    to hitting a complexity limit).  */
     983                 :             : 
     984                 :             : bool
     985                 :           0 : binding_map::apply_ctor_val_to_range (const region *parent_reg,
     986                 :             :                                       region_model_manager *mgr,
     987                 :             :                                       tree min_index, tree max_index,
     988                 :             :                                       tree val)
     989                 :             : {
     990                 :           0 :   gcc_assert (TREE_CODE (min_index) == INTEGER_CST);
     991                 :           0 :   gcc_assert (TREE_CODE (max_index) == INTEGER_CST);
     992                 :             : 
     993                 :             :   /* Generate a binding key for the range.  */
     994                 :           0 :   const region *min_element
     995                 :           0 :     = get_subregion_within_ctor (parent_reg, min_index, mgr);
     996                 :           0 :   const region *max_element
     997                 :           0 :     = get_subregion_within_ctor (parent_reg, max_index, mgr);
     998                 :           0 :   region_offset min_offset = min_element->get_offset (mgr);
     999                 :           0 :   if (min_offset.symbolic_p ())
    1000                 :             :     return false;
    1001                 :           0 :   bit_offset_t start_bit_offset = min_offset.get_bit_offset ();
    1002                 :           0 :   store_manager *smgr = mgr->get_store_manager ();
    1003                 :           0 :   if (max_element->empty_p ())
    1004                 :             :     return false;
    1005                 :           0 :   const binding_key *max_element_key = binding_key::make (smgr, max_element);
    1006                 :           0 :   if (max_element_key->symbolic_p ())
    1007                 :             :     return false;
    1008                 :           0 :   const concrete_binding *max_element_ckey
    1009                 :           0 :     = max_element_key->dyn_cast_concrete_binding ();
    1010                 :           0 :   bit_size_t range_size_in_bits
    1011                 :           0 :     = max_element_ckey->get_next_bit_offset () - start_bit_offset;
    1012                 :           0 :   const concrete_binding *range_key
    1013                 :           0 :     = smgr->get_concrete_binding (start_bit_offset, range_size_in_bits);
    1014                 :           0 :   if (range_key->symbolic_p ())
    1015                 :             :     return false;
    1016                 :             : 
    1017                 :             :   /* Get the value.  */
    1018                 :           0 :   if (TREE_CODE (val) == CONSTRUCTOR)
    1019                 :             :     return false;
    1020                 :           0 :   const svalue *sval = get_svalue_for_ctor_val (val, mgr);
    1021                 :             : 
    1022                 :             :   /* Bind the value to the range.  */
    1023                 :           0 :   put (range_key, sval);
    1024                 :           0 :   return true;
    1025                 :             : }
    1026                 :             : 
    1027                 :             : /* Bind the value VAL into INDEX within PARENT_REF.
    1028                 :             :    For use in handling a pair of entries within a CONSTRUCTOR.
    1029                 :             :    Return true if successful, false if there was a problem (e.g. due
    1030                 :             :    to hitting a complexity limit).  */
    1031                 :             : 
    1032                 :             : bool
    1033                 :         441 : binding_map::apply_ctor_pair_to_child_region (const region *parent_reg,
    1034                 :             :                                               region_model_manager *mgr,
    1035                 :             :                                               tree index, tree val)
    1036                 :             : {
    1037                 :         441 :   const region *child_reg
    1038                 :         441 :     = get_subregion_within_ctor (parent_reg, index, mgr);
    1039                 :         441 :   if (TREE_CODE (val) == CONSTRUCTOR)
    1040                 :          39 :     return apply_ctor_to_region (child_reg, val, mgr);
    1041                 :             :   else
    1042                 :             :     {
    1043                 :         402 :       const svalue *sval = get_svalue_for_ctor_val (val, mgr);
    1044                 :         402 :       if (child_reg->empty_p ())
    1045                 :             :         return false;
    1046                 :         402 :       const binding_key *k
    1047                 :         402 :         = binding_key::make (mgr->get_store_manager (), child_reg);
    1048                 :             :       /* Handle the case where we have an unknown size for child_reg
    1049                 :             :          (e.g. due to it being a trailing field with incomplete array
    1050                 :             :          type.  */
    1051                 :         402 :       if (!k->concrete_p ())
    1052                 :             :         {
    1053                 :             :           /* Assume that sval has a well-defined size for this case.  */
    1054                 :           5 :           tree sval_type = sval->get_type ();
    1055                 :           5 :           gcc_assert (sval_type);
    1056                 :           5 :           HOST_WIDE_INT sval_byte_size = int_size_in_bytes (sval_type);
    1057                 :           5 :           gcc_assert (sval_byte_size != -1);
    1058                 :           5 :           bit_size_t sval_bit_size = sval_byte_size * BITS_PER_UNIT;
    1059                 :             :           /* Get offset of child relative to base region.  */
    1060                 :           5 :           region_offset child_base_offset = child_reg->get_offset (mgr);
    1061                 :           5 :           if (child_base_offset.symbolic_p ())
    1062                 :           1 :             return false;
    1063                 :             :           /* Convert to an offset relative to the parent region.  */
    1064                 :           4 :           region_offset parent_base_offset = parent_reg->get_offset (mgr);
    1065                 :           4 :           gcc_assert (!parent_base_offset.symbolic_p ());
    1066                 :           4 :           bit_offset_t child_parent_offset
    1067                 :           4 :             = (child_base_offset.get_bit_offset ()
    1068                 :           4 :                - parent_base_offset.get_bit_offset ());
    1069                 :             :           /* Create a concrete key for the child within the parent.  */
    1070                 :           4 :           k = mgr->get_store_manager ()->get_concrete_binding
    1071                 :           4 :             (child_parent_offset, sval_bit_size);
    1072                 :             :         }
    1073                 :         401 :       gcc_assert (k->concrete_p ());
    1074                 :         401 :       put (k, sval);
    1075                 :         401 :       return true;
    1076                 :             :     }
    1077                 :             : }
    1078                 :             : 
    1079                 :             : /* Populate OUT with all bindings within this map that overlap KEY.  */
    1080                 :             : 
    1081                 :             : void
    1082                 :       41403 : binding_map::get_overlapping_bindings (const binding_key *key,
    1083                 :             :                                        auto_vec<const binding_key *> *out)
    1084                 :             : {
    1085                 :      194587 :   for (auto iter : *this)
    1086                 :             :     {
    1087                 :       76592 :       const binding_key *iter_key = iter.first;
    1088                 :      153184 :       if (const concrete_binding *ckey
    1089                 :       76592 :             = key->dyn_cast_concrete_binding ())
    1090                 :             :         {
    1091                 :      147994 :           if (const concrete_binding *iter_ckey
    1092                 :       73997 :               = iter_key->dyn_cast_concrete_binding ())
    1093                 :             :             {
    1094                 :       73231 :               if (ckey->overlaps_p (*iter_ckey))
    1095                 :       32624 :                 out->safe_push (iter_key);
    1096                 :             :             }
    1097                 :             :           else
    1098                 :             :             {
    1099                 :             :               /* Assume overlap.  */
    1100                 :         766 :               out->safe_push (iter_key);
    1101                 :             :             }
    1102                 :             :         }
    1103                 :             :       else
    1104                 :             :         {
    1105                 :             :           /* Assume overlap.  */
    1106                 :        2595 :           out->safe_push (iter_key);
    1107                 :             :         }
    1108                 :             :     }
    1109                 :       41403 : }
    1110                 :             : 
    1111                 :             : /* Remove, truncate, and/or split any bindings within this map that
    1112                 :             :    overlap DROP_KEY.
    1113                 :             : 
    1114                 :             :    For example, if we have:
    1115                 :             : 
    1116                 :             :      +------------------------------------+
    1117                 :             :      |             old binding            |
    1118                 :             :      +------------------------------------+
    1119                 :             : 
    1120                 :             :    which is to be overwritten with:
    1121                 :             : 
    1122                 :             :      .......+----------------------+.......
    1123                 :             :      .......|      new binding     |.......
    1124                 :             :      .......+----------------------+.......
    1125                 :             : 
    1126                 :             :    this function "cuts a hole" out of the old binding:
    1127                 :             : 
    1128                 :             :      +------+......................+------+
    1129                 :             :      |prefix| hole for new binding |suffix|
    1130                 :             :      +------+......................+------+
    1131                 :             : 
    1132                 :             :    into which the new binding can be added without
    1133                 :             :    overlapping the prefix or suffix.
    1134                 :             : 
    1135                 :             :    The prefix and suffix (if added) will be bound to the pertinent
    1136                 :             :    parts of the value of the old binding.
    1137                 :             : 
    1138                 :             :    For example, given:
    1139                 :             :      struct s5
    1140                 :             :      {
    1141                 :             :        char arr[8];
    1142                 :             :      };
    1143                 :             :      void test_5 (struct s5 *p)
    1144                 :             :      {
    1145                 :             :        struct s5 f = *p;
    1146                 :             :        f.arr[3] = 42;
    1147                 :             :      }
    1148                 :             :    then after the "f = *p;" we have:
    1149                 :             :      cluster for: f: INIT_VAL((*INIT_VAL(p_33(D))))
    1150                 :             :    and at the "f.arr[3] = 42;" we remove the bindings overlapping
    1151                 :             :    "f.arr[3]", replacing it with a prefix (bytes 0-2) and suffix (bytes 4-7)
    1152                 :             :    giving:
    1153                 :             :      cluster for: f
    1154                 :             :        key:   {bytes 0-2}
    1155                 :             :        value:  {BITS_WITHIN(bytes 0-2, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
    1156                 :             :        key:   {bytes 4-7}
    1157                 :             :        value:  {BITS_WITHIN(bytes 4-7, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
    1158                 :             :    punching a hole into which the new value can be written at byte 3:
    1159                 :             :      cluster for: f
    1160                 :             :        key:   {bytes 0-2}
    1161                 :             :        value:  {BITS_WITHIN(bytes 0-2, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
    1162                 :             :        key:   {byte 3}
    1163                 :             :        value: 'char' {(char)42}
    1164                 :             :        key:   {bytes 4-7}
    1165                 :             :        value:  {BITS_WITHIN(bytes 4-7, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
    1166                 :             : 
    1167                 :             :    If UNCERTAINTY is non-NULL, use it to record any svalues that
    1168                 :             :    were removed, as being maybe-bound.
    1169                 :             : 
    1170                 :             :    If MAYBE_LIVE_VALUES is non-NULL, then use it to record any svalues that
    1171                 :             :    were removed as being maybe-live.
    1172                 :             : 
    1173                 :             :    If ALWAYS_OVERLAP, then assume that DROP_KEY can overlap anything
    1174                 :             :    in the map, due to one or both of the underlying clusters being
    1175                 :             :    symbolic (but not the same symbolic region).  Hence even if DROP_KEY is a
    1176                 :             :    concrete binding it could actually be referring to the same memory as
    1177                 :             :    distinct concrete bindings in the map.  Remove all bindings, but
    1178                 :             :    register any svalues with *UNCERTAINTY.  */
    1179                 :             : 
    1180                 :             : void
    1181                 :      103263 : binding_map::remove_overlapping_bindings (store_manager *mgr,
    1182                 :             :                                           const binding_key *drop_key,
    1183                 :             :                                           uncertainty_t *uncertainty,
    1184                 :             :                                           svalue_set *maybe_live_values,
    1185                 :             :                                           bool always_overlap)
    1186                 :             : {
    1187                 :             :   /* Get the bindings of interest within this map.  */
    1188                 :      103263 :   auto_vec<const binding_key *> bindings;
    1189                 :      103263 :   if (always_overlap)
    1190                 :      186487 :     for (auto iter : *this)
    1191                 :       62767 :       bindings.safe_push (iter.first); /* Add all bindings.  */
    1192                 :             :   else
    1193                 :             :     /* Just add overlapping bindings.  */
    1194                 :       41403 :     get_overlapping_bindings (drop_key, &bindings);
    1195                 :             : 
    1196                 :             :   unsigned i;
    1197                 :             :   const binding_key *iter_binding;
    1198                 :      293409 :   FOR_EACH_VEC_ELT (bindings, i, iter_binding)
    1199                 :             :     {
    1200                 :             :       /* Record any svalues that were removed to *UNCERTAINTY as being
    1201                 :             :          maybe-bound, provided at least some part of the binding is symbolic.
    1202                 :             : 
    1203                 :             :          Specifically, if at least one of the bindings is symbolic, or we
    1204                 :             :          have ALWAYS_OVERLAP for the case where we have possibly aliasing
    1205                 :             :          regions, then we don't know that the svalue has been overwritten,
    1206                 :             :          and should record that to *UNCERTAINTY.
    1207                 :             : 
    1208                 :             :          However, if we have concrete keys accessing within the same symbolic
    1209                 :             :          region, then we *know* that the symbolic region has been overwritten,
    1210                 :             :          so we don't record it to *UNCERTAINTY, as this could be a genuine
    1211                 :             :          leak.  */
    1212                 :       98752 :       const svalue *old_sval = get (iter_binding);
    1213                 :       98752 :       if (uncertainty
    1214                 :      128189 :           && (drop_key->symbolic_p ()
    1215                 :       27132 :               || iter_binding->symbolic_p ()
    1216                 :       23178 :               || always_overlap))
    1217                 :       25559 :         uncertainty->on_maybe_bound_sval (old_sval);
    1218                 :             : 
    1219                 :             :       /* Record any svalues that were removed to *MAYBE_LIVE_VALUES as being
    1220                 :             :          maybe-live. */
    1221                 :       98752 :       if (maybe_live_values)
    1222                 :       62767 :         maybe_live_values->add (old_sval);
    1223                 :             : 
    1224                 :             :       /* Begin by removing the old binding. */
    1225                 :       98752 :       m_map.remove (iter_binding);
    1226                 :             : 
    1227                 :             :       /* Don't attempt to handle prefixes/suffixes for the
    1228                 :             :          "always_overlap" case; everything's being removed.  */
    1229                 :       98752 :       if (always_overlap)
    1230                 :       62767 :         continue;
    1231                 :             : 
    1232                 :             :       /* Now potentially add the prefix and suffix.  */
    1233                 :       71970 :       if (const concrete_binding *drop_ckey
    1234                 :       35985 :           = drop_key->dyn_cast_concrete_binding ())
    1235                 :       66780 :         if (const concrete_binding *iter_ckey
    1236                 :       33390 :               = iter_binding->dyn_cast_concrete_binding ())
    1237                 :             :           {
    1238                 :       32624 :             gcc_assert (drop_ckey->overlaps_p (*iter_ckey));
    1239                 :             : 
    1240                 :       32624 :             const bit_range &drop_bits = drop_ckey->get_bit_range ();
    1241                 :       32624 :             const bit_range &iter_bits = iter_ckey->get_bit_range ();
    1242                 :             : 
    1243                 :       32624 :             if (iter_bits.get_start_bit_offset ()
    1244                 :       32624 :                   < drop_bits.get_start_bit_offset ())
    1245                 :             :               {
    1246                 :             :                 /* We have a truncated prefix.  */
    1247                 :        5790 :                 bit_range prefix_bits (iter_bits.get_start_bit_offset (),
    1248                 :       11580 :                                        (drop_bits.get_start_bit_offset ()
    1249                 :        5790 :                                         - iter_bits.get_start_bit_offset ()));
    1250                 :        5790 :                 const concrete_binding *prefix_key
    1251                 :        5790 :                   = mgr->get_concrete_binding (prefix_bits);
    1252                 :        5790 :                 bit_range rel_prefix (0, prefix_bits.m_size_in_bits);
    1253                 :        5790 :                 const svalue *prefix_sval
    1254                 :        5790 :                   = old_sval->extract_bit_range (NULL_TREE,
    1255                 :             :                                                  rel_prefix,
    1256                 :        5790 :                                                  mgr->get_svalue_manager ());
    1257                 :        5790 :                 m_map.put (prefix_key, prefix_sval);
    1258                 :             :               }
    1259                 :             : 
    1260                 :       65248 :             if (iter_bits.get_next_bit_offset ()
    1261                 :       65248 :                   > drop_bits.get_next_bit_offset ())
    1262                 :             :               {
    1263                 :             :                 /* We have a truncated suffix.  */
    1264                 :        7276 :                 bit_range suffix_bits (drop_bits.get_next_bit_offset (),
    1265                 :        7276 :                                        (iter_bits.get_next_bit_offset ()
    1266                 :       14552 :                                         - drop_bits.get_next_bit_offset ()));
    1267                 :        7276 :                 const concrete_binding *suffix_key
    1268                 :        7276 :                   = mgr->get_concrete_binding (suffix_bits);
    1269                 :        7276 :                 bit_range rel_suffix (drop_bits.get_next_bit_offset ()
    1270                 :        7276 :                                         - iter_bits.get_start_bit_offset (),
    1271                 :        7276 :                                       suffix_bits.m_size_in_bits);
    1272                 :        7276 :                 const svalue *suffix_sval
    1273                 :        7276 :                   = old_sval->extract_bit_range (NULL_TREE,
    1274                 :             :                                                  rel_suffix,
    1275                 :        7276 :                                                  mgr->get_svalue_manager ());
    1276                 :        7276 :                 m_map.put (suffix_key, suffix_sval);
    1277                 :             :               }
    1278                 :             :           }
    1279                 :             :     }
    1280                 :      103263 : }
    1281                 :             : 
    1282                 :             : /* class binding_cluster.  */
    1283                 :             : 
    1284                 :     1458518 : binding_cluster::binding_cluster (const region *base_region)
    1285                 :     1458518 : : m_base_region (base_region), m_map (),
    1286                 :     1458518 :   m_escaped (false), m_touched (false)
    1287                 :             : {
    1288                 :     1458518 : }
    1289                 :             : 
    1290                 :             : /* binding_cluster's copy ctor.  */
    1291                 :             : 
    1292                 :    23860263 : binding_cluster::binding_cluster (const binding_cluster &other)
    1293                 :    23860263 : : m_base_region (other.m_base_region), m_map (other.m_map),
    1294                 :    23860263 :   m_escaped (other.m_escaped), m_touched (other.m_touched)
    1295                 :             : {
    1296                 :    23860263 : }
    1297                 :             : 
    1298                 :             : /* binding_cluster's assignment operator.  */
    1299                 :             : 
    1300                 :             : binding_cluster&
    1301                 :           0 : binding_cluster::operator= (const binding_cluster &other)
    1302                 :             : {
    1303                 :           0 :   gcc_assert (m_base_region == other.m_base_region);
    1304                 :           0 :   m_map = other.m_map;
    1305                 :           0 :   m_escaped = other.m_escaped;
    1306                 :           0 :   m_touched = other.m_touched;
    1307                 :           0 :   return *this;
    1308                 :             : }
    1309                 :             : 
    1310                 :             : /* binding_cluster's equality operator.  */
    1311                 :             : 
    1312                 :             : bool
    1313                 :     1941424 : binding_cluster::operator== (const binding_cluster &other) const
    1314                 :             : {
    1315                 :     1941424 :   if (m_map != other.m_map)
    1316                 :             :     return false;
    1317                 :             : 
    1318                 :     1911163 :   if (m_base_region != other.m_base_region)
    1319                 :             :     return false;
    1320                 :             : 
    1321                 :     1911163 :   if (m_escaped != other.m_escaped)
    1322                 :             :     return false;
    1323                 :             : 
    1324                 :     1910456 :   if (m_touched != other.m_touched)
    1325                 :             :     return false;
    1326                 :             : 
    1327                 :     1909064 :   gcc_checking_assert (hash () == other.hash ());
    1328                 :             : 
    1329                 :             :   return true;
    1330                 :             : }
    1331                 :             : 
    1332                 :             : /* Generate a hash value for this binding_cluster.  */
    1333                 :             : 
    1334                 :             : hashval_t
    1335                 :    13583291 : binding_cluster::hash () const
    1336                 :             : {
    1337                 :    13583291 :   return m_map.hash ();
    1338                 :             : }
    1339                 :             : 
    1340                 :             : /* Return true if this binding_cluster is symbolic
    1341                 :             :    i.e. its base region is symbolic.  */
    1342                 :             : 
    1343                 :             : bool
    1344                 :     7609043 : binding_cluster::symbolic_p () const
    1345                 :             : {
    1346                 :     7609043 :   return m_base_region->get_kind () == RK_SYMBOLIC;
    1347                 :             : }
    1348                 :             : 
    1349                 :             : /* Dump a representation of this binding_cluster to PP.
    1350                 :             :    SIMPLE controls how values and regions are to be printed.
    1351                 :             :    If MULTILINE, then split the dump over multiple lines and
    1352                 :             :    use whitespace for readability, otherwise put all on one line.  */
    1353                 :             : 
    1354                 :             : void
    1355                 :        2173 : binding_cluster::dump_to_pp (pretty_printer *pp, bool simple,
    1356                 :             :                              bool multiline) const
    1357                 :             : {
    1358                 :        2173 :   if (m_escaped)
    1359                 :             :     {
    1360                 :        1422 :       if (multiline)
    1361                 :             :         {
    1362                 :        1240 :           pp_string (pp, "    ESCAPED");
    1363                 :        1240 :           pp_newline (pp);
    1364                 :             :         }
    1365                 :             :       else
    1366                 :         182 :         pp_string (pp, "(ESCAPED)");
    1367                 :             :     }
    1368                 :        2173 :   if (m_touched)
    1369                 :             :     {
    1370                 :         306 :       if (multiline)
    1371                 :             :         {
    1372                 :         124 :           pp_string (pp, "    TOUCHED");
    1373                 :         124 :           pp_newline (pp);
    1374                 :             :         }
    1375                 :             :       else
    1376                 :         182 :         pp_string (pp, "(TOUCHED)");
    1377                 :             :     }
    1378                 :             : 
    1379                 :        2173 :   m_map.dump_to_pp (pp, simple, multiline);
    1380                 :        2173 : }
    1381                 :             : 
    1382                 :             : /* Dump a multiline representation of this binding_cluster to stderr.  */
    1383                 :             : 
    1384                 :             : DEBUG_FUNCTION void
    1385                 :           0 : binding_cluster::dump (bool simple) const
    1386                 :             : {
    1387                 :           0 :   tree_dump_pretty_printer pp (stderr);
    1388                 :           0 :   pp_string (&pp, "  cluster for: ");
    1389                 :           0 :   m_base_region->dump_to_pp (&pp, simple);
    1390                 :           0 :   pp_string (&pp, ": ");
    1391                 :           0 :   pp_newline (&pp);
    1392                 :           0 :   dump_to_pp (&pp, simple, true);
    1393                 :           0 :   pp_newline (&pp);
    1394                 :           0 : }
    1395                 :             : 
    1396                 :             : /* Assert that this object is valid.  */
    1397                 :             : 
    1398                 :             : void
    1399                 :     8831837 : binding_cluster::validate () const
    1400                 :             : {
    1401                 :     8831837 :   int num_symbolic = 0;
    1402                 :     8831837 :   int num_concrete = 0;
    1403                 :    27174765 :   for (auto iter : m_map)
    1404                 :             :     {
    1405                 :     9171464 :       if (iter.first->symbolic_p ())
    1406                 :      849806 :         num_symbolic++;
    1407                 :             :       else
    1408                 :     8321658 :         num_concrete++;
    1409                 :             :     }
    1410                 :             :   /* We shouldn't have more than one symbolic key per cluster
    1411                 :             :      (or one would have clobbered the other).  */
    1412                 :     8831837 :   gcc_assert (num_symbolic < 2);
    1413                 :             :   /* We can't have both concrete and symbolic keys.  */
    1414                 :     8831837 :   gcc_assert (num_concrete == 0 || num_symbolic == 0);
    1415                 :     8831837 : }
    1416                 :             : 
    1417                 :             : /* Return a new json::object of the form
    1418                 :             :    {"escaped": true/false,
    1419                 :             :     "touched": true/false,
    1420                 :             :     "map" : object for the binding_map.  */
    1421                 :             : 
    1422                 :             : std::unique_ptr<json::object>
    1423                 :           0 : binding_cluster::to_json () const
    1424                 :             : {
    1425                 :           0 :   auto cluster_obj = ::make_unique<json::object> ();
    1426                 :             : 
    1427                 :           0 :   cluster_obj->set_bool ("escaped", m_escaped);
    1428                 :           0 :   cluster_obj->set_bool ("touched", m_touched);
    1429                 :           0 :   cluster_obj->set ("map", m_map.to_json ());
    1430                 :             : 
    1431                 :           0 :   return cluster_obj;
    1432                 :             : }
    1433                 :             : 
    1434                 :             : std::unique_ptr<text_art::tree_widget>
    1435                 :           0 : binding_cluster::make_dump_widget (const text_art::dump_widget_info &dwi,
    1436                 :             :                                    store_manager *mgr) const
    1437                 :             : {
    1438                 :           0 :   pretty_printer the_pp;
    1439                 :           0 :   pretty_printer * const pp = &the_pp;
    1440                 :           0 :   pp_format_decoder (pp) = default_tree_printer;
    1441                 :           0 :   pp_show_color (pp) = true;
    1442                 :           0 :   const bool simple = true;
    1443                 :             : 
    1444                 :           0 :   m_base_region->dump_to_pp (pp, simple);
    1445                 :           0 :   pp_string (pp, ": ");
    1446                 :             : 
    1447                 :           0 :   if (const svalue *sval = maybe_get_simple_value (mgr))
    1448                 :             :     {
    1449                 :             :       /* Special-case to simplify dumps for the common case where
    1450                 :             :          we just have one value directly bound to the whole of a
    1451                 :             :          region.  */
    1452                 :           0 :       sval->dump_to_pp (pp, simple);
    1453                 :           0 :       if (escaped_p ())
    1454                 :           0 :         pp_string (pp, " (ESCAPED)");
    1455                 :           0 :       if (touched_p ())
    1456                 :           0 :         pp_string (pp, " (TOUCHED)");
    1457                 :             : 
    1458                 :           0 :       return text_art::tree_widget::make (dwi, pp);
    1459                 :             :     }
    1460                 :             :   else
    1461                 :             :     {
    1462                 :           0 :       if (escaped_p ())
    1463                 :           0 :         pp_string (pp, " (ESCAPED)");
    1464                 :           0 :       if (touched_p ())
    1465                 :           0 :         pp_string (pp, " (TOUCHED)");
    1466                 :             : 
    1467                 :           0 :       std::unique_ptr<text_art::tree_widget> cluster_widget
    1468                 :           0 :         (text_art::tree_widget::make (dwi, pp));
    1469                 :             : 
    1470                 :           0 :       m_map.add_to_tree_widget (*cluster_widget, dwi);
    1471                 :             : 
    1472                 :           0 :       return cluster_widget;
    1473                 :           0 :     }
    1474                 :           0 : }
    1475                 :             : 
    1476                 :             : /* Add a binding of SVAL of kind KIND to REG, unpacking SVAL if it is a
    1477                 :             :    compound_sval.  */
    1478                 :             : 
    1479                 :             : void
    1480                 :      417264 : binding_cluster::bind (store_manager *mgr,
    1481                 :             :                        const region *reg, const svalue *sval)
    1482                 :             : {
    1483                 :      834528 :   if (const compound_svalue *compound_sval
    1484                 :      417264 :         = sval->dyn_cast_compound_svalue ())
    1485                 :             :     {
    1486                 :         855 :       bind_compound_sval (mgr, reg, compound_sval);
    1487                 :         855 :       return;
    1488                 :             :     }
    1489                 :             : 
    1490                 :      416409 :   if (reg->empty_p ())
    1491                 :             :     return;
    1492                 :      416409 :   const binding_key *binding = binding_key::make (mgr, reg);
    1493                 :      416409 :   bind_key (binding, sval);
    1494                 :             : }
    1495                 :             : 
    1496                 :             : /* Bind SVAL to KEY.
    1497                 :             :    Unpacking of compound_svalues should already have been done by the
    1498                 :             :    time this is called.  */
    1499                 :             : 
    1500                 :             : void
    1501                 :      420644 : binding_cluster::bind_key (const binding_key *key, const svalue *sval)
    1502                 :             : {
    1503                 :      420644 :   gcc_assert (sval->get_kind () != SK_COMPOUND);
    1504                 :             : 
    1505                 :      420644 :   m_map.put (key, sval);
    1506                 :      420644 :   if (key->symbolic_p ())
    1507                 :       30051 :     m_touched = true;
    1508                 :      420644 : }
    1509                 :             : 
    1510                 :             : /* Subroutine of binding_cluster::bind.
    1511                 :             :    Unpack compound_svals when binding them, so that we bind them
    1512                 :             :    element-wise.  */
    1513                 :             : 
    1514                 :             : void
    1515                 :         855 : binding_cluster::bind_compound_sval (store_manager *mgr,
    1516                 :             :                                      const region *reg,
    1517                 :             :                                      const compound_svalue *compound_sval)
    1518                 :             : {
    1519                 :         855 :   region_offset reg_offset
    1520                 :         855 :     = reg->get_offset (mgr->get_svalue_manager ());
    1521                 :         855 :   if (reg_offset.symbolic_p ())
    1522                 :             :     {
    1523                 :           4 :       m_touched = true;
    1524                 :           4 :       clobber_region (mgr, reg);
    1525                 :           4 :       return;
    1526                 :             :     }
    1527                 :             : 
    1528                 :        3267 :   for (map_t::iterator iter = compound_sval->begin ();
    1529                 :        6534 :        iter != compound_sval->end (); ++iter)
    1530                 :             :     {
    1531                 :        2416 :       const binding_key *iter_key = (*iter).first;
    1532                 :        2416 :       const svalue *iter_sval = (*iter).second;
    1533                 :             : 
    1534                 :        4832 :       if (const concrete_binding *concrete_key
    1535                 :        2416 :           = iter_key->dyn_cast_concrete_binding ())
    1536                 :             :         {
    1537                 :        2416 :           bit_offset_t effective_start
    1538                 :        2416 :             = (concrete_key->get_start_bit_offset ()
    1539                 :        2416 :                + reg_offset.get_bit_offset ());
    1540                 :        2416 :           const concrete_binding *effective_concrete_key
    1541                 :        2416 :             = mgr->get_concrete_binding (effective_start,
    1542                 :             :                                          concrete_key->get_size_in_bits ());
    1543                 :        2416 :           bind_key (effective_concrete_key, iter_sval);
    1544                 :             :         }
    1545                 :             :       else
    1546                 :           0 :         gcc_unreachable ();
    1547                 :             :     }
    1548                 :             : }
    1549                 :             : 
    1550                 :             : /* Remove all bindings overlapping REG within this cluster.  */
    1551                 :             : 
    1552                 :             : void
    1553                 :        6355 : binding_cluster::clobber_region (store_manager *mgr, const region *reg)
    1554                 :             : {
    1555                 :        6355 :   remove_overlapping_bindings (mgr, reg, NULL, NULL);
    1556                 :        6355 : }
    1557                 :             : 
    1558                 :             : /* Remove any bindings for REG within this cluster.  */
    1559                 :             : 
    1560                 :             : void
    1561                 :      178736 : binding_cluster::purge_region (store_manager *mgr, const region *reg)
    1562                 :             : {
    1563                 :      178736 :   gcc_assert (reg->get_kind () == RK_DECL);
    1564                 :      178736 :   if (reg->empty_p ())
    1565                 :             :     return;
    1566                 :      178736 :   const binding_key *binding
    1567                 :      178736 :     = binding_key::make (mgr, const_cast<region *> (reg));
    1568                 :      178736 :   m_map.remove (binding);
    1569                 :             : }
    1570                 :             : 
    1571                 :             : /* Clobber REG and fill it with repeated copies of SVAL.  */
    1572                 :             : 
    1573                 :             : void
    1574                 :        1439 : binding_cluster::fill_region (store_manager *mgr,
    1575                 :             :                               const region *reg,
    1576                 :             :                               const svalue *sval)
    1577                 :             : {
    1578                 :        1439 :   clobber_region (mgr, reg);
    1579                 :             : 
    1580                 :        1439 :   region_model_manager *sval_mgr = mgr->get_svalue_manager ();
    1581                 :        1439 :   const svalue *byte_size_sval = reg->get_byte_size_sval (sval_mgr);
    1582                 :        1439 :   const svalue *fill_sval
    1583                 :        1439 :     = sval_mgr->get_or_create_repeated_svalue (reg->get_type (),
    1584                 :             :                                                byte_size_sval, sval);
    1585                 :        1439 :   bind (mgr, reg, fill_sval);
    1586                 :        1439 : }
    1587                 :             : 
    1588                 :             : /* Clobber REG within this cluster and fill it with zeroes.  */
    1589                 :             : 
    1590                 :             : void
    1591                 :          33 : binding_cluster::zero_fill_region (store_manager *mgr, const region *reg)
    1592                 :             : {
    1593                 :          33 :   region_model_manager *sval_mgr = mgr->get_svalue_manager ();
    1594                 :          33 :   const svalue *zero_sval = sval_mgr->get_or_create_int_cst (char_type_node, 0);
    1595                 :          33 :   fill_region (mgr, reg, zero_sval);
    1596                 :          33 : }
    1597                 :             : 
    1598                 :             : /* Mark REG_TO_BIND within this cluster as being unknown.
    1599                 :             : 
    1600                 :             :    Remove any bindings overlapping REG_FOR_OVERLAP.
    1601                 :             :    If UNCERTAINTY is non-NULL, use it to record any svalues that
    1602                 :             :    had bindings to them removed, as being maybe-bound.
    1603                 :             :    If MAYBE_LIVE_VALUES is non-NULL, use it to record any svalues that
    1604                 :             :    had bindings to them removed, as being maybe-live.
    1605                 :             : 
    1606                 :             :    REG_TO_BIND and REG_FOR_OVERLAP are the same for
    1607                 :             :    store::mark_region_as_unknown, but are different in
    1608                 :             :    store::set_value's alias handling, for handling the case where
    1609                 :             :    we have a write to a symbolic REG_FOR_OVERLAP. */
    1610                 :             : 
    1611                 :             : void
    1612                 :       62149 : binding_cluster::mark_region_as_unknown (store_manager *mgr,
    1613                 :             :                                          const region *reg_to_bind,
    1614                 :             :                                          const region *reg_for_overlap,
    1615                 :             :                                          uncertainty_t *uncertainty,
    1616                 :             :                                          svalue_set *maybe_live_values)
    1617                 :             : {
    1618                 :       62149 :   if (reg_to_bind->empty_p ())
    1619                 :             :     return;
    1620                 :             : 
    1621                 :       62149 :   remove_overlapping_bindings (mgr, reg_for_overlap, uncertainty,
    1622                 :             :                                maybe_live_values);
    1623                 :             : 
    1624                 :             :   /* Add a default binding to "unknown".  */
    1625                 :       62149 :   region_model_manager *sval_mgr = mgr->get_svalue_manager ();
    1626                 :       62149 :   const svalue *sval
    1627                 :       62149 :     = sval_mgr->get_or_create_unknown_svalue (reg_to_bind->get_type ());
    1628                 :       62149 :   bind (mgr, reg_to_bind, sval);
    1629                 :             : }
    1630                 :             : 
    1631                 :             : /* Purge state involving SVAL.  */
    1632                 :             : 
    1633                 :             : void
    1634                 :      562005 : binding_cluster::purge_state_involving (const svalue *sval,
    1635                 :             :                                         region_model_manager *sval_mgr)
    1636                 :             : {
    1637                 :      562005 :   auto_vec<const binding_key *> to_remove;
    1638                 :      562005 :   auto_vec<std::pair<const binding_key *, tree> > to_make_unknown;
    1639                 :     1689083 :   for (auto iter : m_map)
    1640                 :             :     {
    1641                 :      563539 :       const binding_key *iter_key = iter.first;
    1642                 :     1127078 :       if (const symbolic_binding *symbolic_key
    1643                 :      563539 :             = iter_key->dyn_cast_symbolic_binding ())
    1644                 :             :         {
    1645                 :       65581 :           const region *reg = symbolic_key->get_region ();
    1646                 :       65581 :           if (reg->involves_p (sval))
    1647                 :           0 :             to_remove.safe_push (iter_key);
    1648                 :             :         }
    1649                 :      563539 :       const svalue *iter_sval = iter.second;
    1650                 :      563539 :       if (iter_sval->involves_p (sval))
    1651                 :        4279 :         to_make_unknown.safe_push (std::make_pair(iter_key,
    1652                 :        4279 :                                                   iter_sval->get_type ()));
    1653                 :             :     }
    1654                 :      562005 :   for (auto iter : to_remove)
    1655                 :             :     {
    1656                 :           0 :       m_map.remove (iter);
    1657                 :           0 :       m_touched = true;
    1658                 :             :     }
    1659                 :      574842 :   for (auto iter : to_make_unknown)
    1660                 :             :     {
    1661                 :        4279 :       const svalue *new_sval
    1662                 :        4279 :         = sval_mgr->get_or_create_unknown_svalue (iter.second);
    1663                 :        4279 :       m_map.put (iter.first, new_sval);
    1664                 :             :     }
    1665                 :      562005 : }
    1666                 :             : 
    1667                 :             : /* Get any SVAL bound to REG within this cluster via kind KIND,
    1668                 :             :    without checking parent regions of REG.  */
    1669                 :             : 
    1670                 :             : const svalue *
    1671                 :     1398618 : binding_cluster::get_binding (store_manager *mgr,
    1672                 :             :                               const region *reg) const
    1673                 :             : {
    1674                 :     1398618 :   if (reg->empty_p ())
    1675                 :             :     return NULL;
    1676                 :     1398618 :   const binding_key *reg_binding = binding_key::make (mgr, reg);
    1677                 :     1398618 :   const svalue *sval = m_map.get (reg_binding);
    1678                 :     1398618 :   if (sval)
    1679                 :             :     {
    1680                 :             :       /* If we have a struct with a single field, then the binding of
    1681                 :             :          the field will equal that of the struct, and looking up e.g.
    1682                 :             :          PARENT_REG.field within:
    1683                 :             :             cluster for PARENT_REG: INIT_VAL(OTHER_REG)
    1684                 :             :          will erroneously return INIT_VAL(OTHER_REG), rather than
    1685                 :             :            SUB_VALUE(INIT_VAL(OTHER_REG), FIELD) == INIT_VAL(OTHER_REG.FIELD).
    1686                 :             :          Fix this issue by iterating upwards whilst the bindings are equal,
    1687                 :             :          expressing the lookups as subvalues.
    1688                 :             :          We have to gather a list of subregion accesses, then walk it
    1689                 :             :          in reverse to get the subvalues.  */
    1690                 :     1093431 :       auto_vec<const region *> regions;
    1691                 :     1103095 :       while (const region *parent_reg = reg->get_parent_region ())
    1692                 :             :         {
    1693                 :     1103095 :           const binding_key *parent_reg_binding
    1694                 :     1103095 :             = binding_key::make (mgr, parent_reg);
    1695                 :     1103095 :           if (parent_reg_binding == reg_binding
    1696                 :       12313 :               && sval->get_type ()
    1697                 :       12301 :               && reg->get_type ()
    1698                 :     1115396 :               && sval->get_type () != reg->get_type ())
    1699                 :             :             {
    1700                 :        9664 :               regions.safe_push (reg);
    1701                 :        9664 :               reg = parent_reg;
    1702                 :             :             }
    1703                 :             :           else
    1704                 :             :             break;
    1705                 :        9664 :         }
    1706                 :     1093431 :       if (sval->get_type ()
    1707                 :     1084414 :           && reg->get_type ()
    1708                 :     2177020 :           && sval->get_type () == reg->get_type ())
    1709                 :             :         {
    1710                 :      902593 :           unsigned i;
    1711                 :      902593 :           const region *iter_reg;
    1712                 :     1120810 :           FOR_EACH_VEC_ELT_REVERSE (regions, i, iter_reg)
    1713                 :             :             {
    1714                 :        9159 :               region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
    1715                 :        9159 :               sval = rmm_mgr->get_or_create_sub_svalue (iter_reg->get_type (),
    1716                 :             :                                                         sval, iter_reg);
    1717                 :             :             }
    1718                 :             :         }
    1719                 :     1093431 :     }
    1720                 :             :   return sval;
    1721                 :             : }
    1722                 :             : 
    1723                 :             : /* Get any SVAL bound to REG within this cluster,
    1724                 :             :    either directly for REG, or recursively checking for bindings within
    1725                 :             :    parent regions and extracting subvalues if need be.  */
    1726                 :             : 
    1727                 :             : const svalue *
    1728                 :     1398618 : binding_cluster::get_binding_recursive (store_manager *mgr,
    1729                 :             :                                         const region *reg) const
    1730                 :             : {
    1731                 :     1398618 :   if (const svalue *sval = get_binding (mgr, reg))
    1732                 :             :     return sval;
    1733                 :      305187 :   if (reg != m_base_region)
    1734                 :      178751 :     if (const region *parent_reg = reg->get_parent_region ())
    1735                 :      357502 :       if (const svalue *parent_sval
    1736                 :      178751 :           = get_binding_recursive (mgr, parent_reg))
    1737                 :             :         {
    1738                 :             :           /* Extract child svalue from parent svalue.  */
    1739                 :       53463 :           region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
    1740                 :       53463 :           return rmm_mgr->get_or_create_sub_svalue (reg->get_type (),
    1741                 :       53463 :                                                     parent_sval, reg);
    1742                 :             :         }
    1743                 :             :   return NULL;
    1744                 :             : }
    1745                 :             : 
    1746                 :             : /* Get any value bound for REG within this cluster.  */
    1747                 :             : 
    1748                 :             : const svalue *
    1749                 :     1219867 : binding_cluster::get_any_binding (store_manager *mgr,
    1750                 :             :                                   const region *reg) const
    1751                 :             : {
    1752                 :             :   /* Look for a direct binding.  */
    1753                 :     2439734 :   if (const svalue *direct_sval
    1754                 :     1219867 :       = get_binding_recursive (mgr, reg))
    1755                 :             :     return direct_sval;
    1756                 :             : 
    1757                 :             :   /* If we had a write to a cluster of unknown size, we might
    1758                 :             :      have a self-binding of the whole base region with an svalue,
    1759                 :             :      where the base region is symbolic.
    1760                 :             :      Handle such cases by returning sub_svalue instances.  */
    1761                 :      126436 :   if (const svalue *cluster_sval = maybe_get_simple_value (mgr))
    1762                 :             :     {
    1763                 :             :       /* Extract child svalue from parent svalue.  */
    1764                 :           0 :       region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
    1765                 :           0 :       return rmm_mgr->get_or_create_sub_svalue (reg->get_type (),
    1766                 :           0 :                                                 cluster_sval, reg);
    1767                 :             :     }
    1768                 :             : 
    1769                 :             :   /* If this cluster has been touched by a symbolic write, then the content
    1770                 :             :      of any subregion not currently specifically bound is "UNKNOWN".  */
    1771                 :      126436 :   if (m_touched)
    1772                 :             :     {
    1773                 :        4525 :       region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
    1774                 :        4525 :       return rmm_mgr->get_or_create_unknown_svalue (reg->get_type ());
    1775                 :             :     }
    1776                 :             : 
    1777                 :             :   /* Alternatively, if this is a symbolic read and the cluster has any bindings,
    1778                 :             :      then we don't know if we're reading those values or not, so the result
    1779                 :             :      is also "UNKNOWN".  */
    1780                 :      121911 :   if (reg->get_offset (mgr->get_svalue_manager ()).symbolic_p ()
    1781                 :      121911 :       && m_map.elements () > 0)
    1782                 :             :     {
    1783                 :         574 :       region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
    1784                 :         574 :       return rmm_mgr->get_or_create_unknown_svalue (reg->get_type ());
    1785                 :             :     }
    1786                 :             : 
    1787                 :      121337 :   if (const svalue *compound_sval = maybe_get_compound_binding (mgr, reg))
    1788                 :             :     return compound_sval;
    1789                 :             : 
    1790                 :             :   /* Otherwise, the initial value, or uninitialized.  */
    1791                 :             :   return NULL;
    1792                 :             : }
    1793                 :             : 
    1794                 :             : /* Attempt to get a compound_svalue for the bindings within the cluster
    1795                 :             :    affecting REG (which could be the base region itself).
    1796                 :             : 
    1797                 :             :    Create a compound_svalue with the subset of bindings the affect REG,
    1798                 :             :    offsetting them so that the offsets are relative to the start of REG
    1799                 :             :    within the cluster.
    1800                 :             : 
    1801                 :             :    For example, REG could be one element within an array of structs.
    1802                 :             : 
    1803                 :             :    Return the resulting compound_svalue, or NULL if there's a problem.  */
    1804                 :             : 
    1805                 :             : const svalue *
    1806                 :      121337 : binding_cluster::maybe_get_compound_binding (store_manager *mgr,
    1807                 :             :                                              const region *reg) const
    1808                 :             : {
    1809                 :      121337 :   region_offset cluster_offset
    1810                 :      121337 :     = m_base_region->get_offset (mgr->get_svalue_manager ());
    1811                 :      121337 :   if (cluster_offset.symbolic_p ())
    1812                 :             :     return NULL;
    1813                 :      121337 :   region_offset reg_offset = reg->get_offset (mgr->get_svalue_manager ());
    1814                 :      121337 :   if (reg_offset.symbolic_p ())
    1815                 :             :     return NULL;
    1816                 :             : 
    1817                 :       96779 :   if (reg->empty_p ())
    1818                 :             :     return NULL;
    1819                 :             : 
    1820                 :       96779 :   region_model_manager *sval_mgr = mgr->get_svalue_manager ();
    1821                 :             : 
    1822                 :             :   /* We will a build the result map in two parts:
    1823                 :             :      (a) result_map, holding the concrete keys from this cluster,
    1824                 :             : 
    1825                 :             :      (b) default_map, holding the initial values for the region
    1826                 :             :      (e.g. uninitialized, initializer values, or zero), unless this
    1827                 :             :      cluster has been touched.
    1828                 :             : 
    1829                 :             :      We will populate (a), and as we do, clobber (b), trimming and
    1830                 :             :      splitting its bindings as necessary.
    1831                 :             :      Finally, we will merge (b) into (a), giving a concrete map
    1832                 :             :      that merges both the initial values and the bound values from
    1833                 :             :      the binding_cluster.
    1834                 :             :      Doing it this way reduces N for the O(N^2) intersection-finding,
    1835                 :             :      perhaps we should have a spatial-organized data structure for
    1836                 :             :      concrete keys, though.  */
    1837                 :             : 
    1838                 :       96779 :   binding_map result_map;
    1839                 :       96779 :   binding_map default_map;
    1840                 :             : 
    1841                 :             :   /* Set up default values in default_map.  */
    1842                 :       96779 :   const svalue *default_sval;
    1843                 :       96779 :   if (m_touched)
    1844                 :           0 :     default_sval = sval_mgr->get_or_create_unknown_svalue (reg->get_type ());
    1845                 :             :   else
    1846                 :       96779 :     default_sval = sval_mgr->get_or_create_initial_value (reg);
    1847                 :       96779 :   const binding_key *default_key = binding_key::make (mgr, reg);
    1848                 :             : 
    1849                 :             :   /* Express the bit-range of the default key for REG relative to REG,
    1850                 :             :      rather than to the base region.  */
    1851                 :       96779 :   const concrete_binding *concrete_default_key
    1852                 :       96779 :     = default_key->dyn_cast_concrete_binding ();
    1853                 :       96779 :   if (!concrete_default_key)
    1854                 :             :     return nullptr;
    1855                 :       95888 :   const concrete_binding *default_key_relative_to_reg
    1856                 :       95888 :      = mgr->get_concrete_binding (0, concrete_default_key->get_size_in_bits ());
    1857                 :       95888 :   default_map.put (default_key_relative_to_reg, default_sval);
    1858                 :             : 
    1859                 :      284124 :   for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
    1860                 :             :     {
    1861                 :      107008 :       const binding_key *key = (*iter).first;
    1862                 :      107008 :       const svalue *sval = (*iter).second;
    1863                 :             : 
    1864                 :      214016 :       if (const concrete_binding *concrete_key
    1865                 :      107008 :           = key->dyn_cast_concrete_binding ())
    1866                 :             :         {
    1867                 :      107008 :           const bit_range &bound_range = concrete_key->get_bit_range ();
    1868                 :             : 
    1869                 :      107008 :           bit_size_t reg_bit_size;
    1870                 :      107008 :           if (!reg->get_bit_size (&reg_bit_size))
    1871                 :       12890 :             return NULL;
    1872                 :             : 
    1873                 :      107008 :           bit_range reg_range (reg_offset.get_bit_offset (),
    1874                 :      107008 :                                reg_bit_size);
    1875                 :             : 
    1876                 :             :           /* Skip bindings that are outside the bit range of REG.  */
    1877                 :      107008 :           if (!bound_range.intersects_p (reg_range))
    1878                 :       79897 :             continue;
    1879                 :             : 
    1880                 :             :           /* We shouldn't have an exact match; that should have been
    1881                 :             :              handled already.  */
    1882                 :       27111 :           gcc_assert (!(reg_range == bound_range));
    1883                 :             : 
    1884                 :       27111 :           bit_range subrange (0, 0);
    1885                 :       27111 :           if (reg_range.contains_p (bound_range, &subrange))
    1886                 :             :             {
    1887                 :             :               /* We have a bound range fully within REG.
    1888                 :             :                  Add it to map, offsetting accordingly.  */
    1889                 :             : 
    1890                 :             :               /* Get offset of KEY relative to REG, rather than to
    1891                 :             :                  the cluster.  */
    1892                 :       14145 :               const concrete_binding *offset_concrete_key
    1893                 :       14145 :                 = mgr->get_concrete_binding (subrange);
    1894                 :       14145 :               result_map.put (offset_concrete_key, sval);
    1895                 :             : 
    1896                 :             :               /* Clobber default_map, removing/trimming/spliting where
    1897                 :             :                  it overlaps with offset_concrete_key.  */
    1898                 :       14145 :               default_map.remove_overlapping_bindings (mgr,
    1899                 :             :                                                        offset_concrete_key,
    1900                 :             :                                                        NULL, NULL, false);
    1901                 :             :             }
    1902                 :       12966 :           else if (bound_range.contains_p (reg_range, &subrange))
    1903                 :             :             {
    1904                 :             :               /* REG is fully within the bound range, but
    1905                 :             :                  is not equal to it; we're extracting a subvalue.  */
    1906                 :       12890 :               return sval->extract_bit_range (reg->get_type (),
    1907                 :             :                                               subrange,
    1908                 :       12890 :                                               mgr->get_svalue_manager ());
    1909                 :             :             }
    1910                 :             :           else
    1911                 :             :             {
    1912                 :             :               /* REG and the bound range partially overlap.  */
    1913                 :          76 :               bit_range reg_subrange (0, 0);
    1914                 :          76 :               bit_range bound_subrange (0, 0);
    1915                 :          76 :               reg_range.intersects_p (bound_range,
    1916                 :             :                                       &reg_subrange, &bound_subrange);
    1917                 :             : 
    1918                 :             :               /* Get the bits from the bound value for the bits at the
    1919                 :             :                  intersection (relative to the bound value).  */
    1920                 :          76 :               const svalue *overlap_sval
    1921                 :          76 :                 = sval->extract_bit_range (NULL_TREE,
    1922                 :             :                                            bound_subrange,
    1923                 :             :                                            mgr->get_svalue_manager ());
    1924                 :             : 
    1925                 :             :               /* Get key for overlap, relative to the REG.  */
    1926                 :          76 :               const concrete_binding *overlap_concrete_key
    1927                 :          76 :                 = mgr->get_concrete_binding (reg_subrange);
    1928                 :          76 :               result_map.put (overlap_concrete_key, overlap_sval);
    1929                 :             : 
    1930                 :             :               /* Clobber default_map, removing/trimming/spliting where
    1931                 :             :                  it overlaps with overlap_concrete_key.  */
    1932                 :          76 :               default_map.remove_overlapping_bindings (mgr,
    1933                 :             :                                                        overlap_concrete_key,
    1934                 :             :                                                        NULL, NULL, false);
    1935                 :             :             }
    1936                 :             :         }
    1937                 :             :       else
    1938                 :             :         /* Can't handle symbolic bindings.  */
    1939                 :             :         return NULL;
    1940                 :             :     }
    1941                 :             : 
    1942                 :       82998 :   if (result_map.elements () == 0)
    1943                 :             :     return NULL;
    1944                 :             : 
    1945                 :             :   /* Merge any bindings from default_map into result_map.  */
    1946                 :        5751 :   for (auto iter : default_map)
    1947                 :             :     {
    1948                 :         368 :       const binding_key *key = iter.first;
    1949                 :         368 :       const svalue *sval = iter.second;
    1950                 :         368 :       result_map.put (key, sval);
    1951                 :             :     }
    1952                 :             : 
    1953                 :        5383 :   return sval_mgr->get_or_create_compound_svalue (reg->get_type (), result_map);
    1954                 :       96779 : }
    1955                 :             : 
    1956                 :             : /* Remove, truncate, and/or split any bindings within this map that
    1957                 :             :    could overlap REG.
    1958                 :             : 
    1959                 :             :    If REG's base region or this cluster is symbolic and they're different
    1960                 :             :    base regions, then remove everything in this cluster's map, on the
    1961                 :             :    grounds that REG could be referring to the same memory as anything
    1962                 :             :    in the map.
    1963                 :             : 
    1964                 :             :    If UNCERTAINTY is non-NULL, use it to record any svalues that
    1965                 :             :    were removed, as being maybe-bound.
    1966                 :             : 
    1967                 :             :    If MAYBE_LIVE_VALUES is non-NULL, use it to record any svalues that
    1968                 :             :    were removed, as being maybe-live.  */
    1969                 :             : 
    1970                 :             : void
    1971                 :       89042 : binding_cluster::remove_overlapping_bindings (store_manager *mgr,
    1972                 :             :                                               const region *reg,
    1973                 :             :                                               uncertainty_t *uncertainty,
    1974                 :             :                                               svalue_set *maybe_live_values)
    1975                 :             : {
    1976                 :       89042 :   if (reg->empty_p ())
    1977                 :             :     return;
    1978                 :       89042 :   const binding_key *reg_binding = binding_key::make (mgr, reg);
    1979                 :             : 
    1980                 :       89042 :   const region *cluster_base_reg = get_base_region ();
    1981                 :       89042 :   const region *other_base_reg = reg->get_base_region ();
    1982                 :             :   /* If at least one of the base regions involved is symbolic, and they're
    1983                 :             :      not the same base region, then consider everything in the map as
    1984                 :             :      potentially overlapping with reg_binding (even if it's a concrete
    1985                 :             :      binding and things in the map are concrete - they could be referring
    1986                 :             :      to the same memory when the symbolic base regions are taken into
    1987                 :             :      account).  */
    1988                 :       89042 :   bool always_overlap = (cluster_base_reg != other_base_reg
    1989                 :       89042 :                          && (cluster_base_reg->get_kind () == RK_SYMBOLIC
    1990                 :       28159 :                              || other_base_reg->get_kind () == RK_SYMBOLIC));
    1991                 :       89042 :   m_map.remove_overlapping_bindings (mgr, reg_binding, uncertainty,
    1992                 :             :                                      maybe_live_values,
    1993                 :             :                                      always_overlap);
    1994                 :             : }
    1995                 :             : 
    1996                 :             : /* Attempt to merge CLUSTER_A and CLUSTER_B into OUT_CLUSTER, using
    1997                 :             :    MGR and MERGER.
    1998                 :             :    Return true if they can be merged, false otherwise.  */
    1999                 :             : 
    2000                 :             : bool
    2001                 :     1138084 : binding_cluster::can_merge_p (const binding_cluster *cluster_a,
    2002                 :             :                               const binding_cluster *cluster_b,
    2003                 :             :                               binding_cluster *out_cluster,
    2004                 :             :                               store *out_store,
    2005                 :             :                               store_manager *mgr,
    2006                 :             :                               model_merger *merger)
    2007                 :             : {
    2008                 :     1138084 :   gcc_assert (out_cluster);
    2009                 :             : 
    2010                 :             :   /* Merge flags ("ESCAPED" and "TOUCHED") by setting the merged flag to
    2011                 :             :      true if either of the inputs is true.  */
    2012                 :     1138084 :   if ((cluster_a && cluster_a->m_escaped)
    2013                 :      729257 :       || (cluster_b && cluster_b->m_escaped))
    2014                 :        3880 :     out_cluster->m_escaped = true;
    2015                 :     1138084 :   if ((cluster_a && cluster_a->m_touched)
    2016                 :      793250 :       || (cluster_b && cluster_b->m_touched))
    2017                 :        9402 :     out_cluster->m_touched = true;
    2018                 :             : 
    2019                 :             :   /* At least one of CLUSTER_A and CLUSTER_B are non-NULL, but either
    2020                 :             :      could be NULL.  Handle these cases.  */
    2021                 :     1138084 :   if (cluster_a == NULL)
    2022                 :             :     {
    2023                 :       20738 :       gcc_assert (cluster_b != NULL);
    2024                 :       20738 :       gcc_assert (cluster_b->m_base_region == out_cluster->m_base_region);
    2025                 :       20738 :       out_cluster->make_unknown_relative_to (cluster_b, out_store, mgr);
    2026                 :       20738 :       return true;
    2027                 :             :     }
    2028                 :     1117346 :   if (cluster_b == NULL)
    2029                 :             :     {
    2030                 :       77136 :       gcc_assert (cluster_a != NULL);
    2031                 :       77136 :       gcc_assert (cluster_a->m_base_region == out_cluster->m_base_region);
    2032                 :       77136 :       out_cluster->make_unknown_relative_to (cluster_a, out_store, mgr);
    2033                 :       77136 :       return true;
    2034                 :             :     }
    2035                 :             : 
    2036                 :             :   /* The "both inputs are non-NULL" case.  */
    2037                 :     1040210 :   gcc_assert (cluster_a != NULL && cluster_b != NULL);
    2038                 :     1040210 :   gcc_assert (cluster_a->m_base_region == out_cluster->m_base_region);
    2039                 :     1040210 :   gcc_assert (cluster_b->m_base_region == out_cluster->m_base_region);
    2040                 :             : 
    2041                 :     1040210 :   hash_set<const binding_key *> keys;
    2042                 :     2219878 :   for (map_t::iterator iter_a = cluster_a->m_map.begin ();
    2043                 :     3399546 :        iter_a != cluster_a->m_map.end (); ++iter_a)
    2044                 :             :     {
    2045                 :     1179668 :       const binding_key *key_a = (*iter_a).first;
    2046                 :     1179668 :       keys.add (key_a);
    2047                 :             :     }
    2048                 :     2203271 :   for (map_t::iterator iter_b = cluster_b->m_map.begin ();
    2049                 :     3366332 :        iter_b != cluster_b->m_map.end (); ++iter_b)
    2050                 :             :     {
    2051                 :     1163061 :       const binding_key *key_b = (*iter_b).first;
    2052                 :     1163061 :       keys.add (key_b);
    2053                 :             :     }
    2054                 :     1040210 :   int num_symbolic_keys = 0;
    2055                 :     1040210 :   int num_concrete_keys = 0;
    2056                 :     2115764 :   for (hash_set<const binding_key *>::iterator iter = keys.begin ();
    2057                 :     3191318 :        iter != keys.end (); ++iter)
    2058                 :             :     {
    2059                 :     1160671 :       region_model_manager *sval_mgr = mgr->get_svalue_manager ();
    2060                 :     1160671 :       const binding_key *key = *iter;
    2061                 :     1160671 :       const svalue *sval_a = cluster_a->get_any_value (key);
    2062                 :     1160671 :       const svalue *sval_b = cluster_b->get_any_value (key);
    2063                 :             : 
    2064                 :     1160671 :       if (key->symbolic_p ())
    2065                 :      109881 :         num_symbolic_keys++;
    2066                 :             :       else
    2067                 :     1050790 :         num_concrete_keys++;
    2068                 :             : 
    2069                 :     1160671 :       if (sval_a == sval_b)
    2070                 :             :         {
    2071                 :      890121 :           gcc_assert (sval_a);
    2072                 :      890121 :           out_cluster->m_map.put (key, sval_a);
    2073                 :      890121 :           continue;
    2074                 :             :         }
    2075                 :      270550 :       else if (sval_a && sval_b)
    2076                 :             :         {
    2077                 :      524976 :           if (const svalue *merged_sval
    2078                 :      190852 :               = sval_a->can_merge_p (sval_b, sval_mgr, merger))
    2079                 :             :             {
    2080                 :      143272 :               out_cluster->m_map.put (key, merged_sval);
    2081                 :      143272 :               continue;
    2082                 :             :             }
    2083                 :             :           /* Merger of the svalues failed.  Reject merger of the cluster.   */
    2084                 :       85117 :           return false;
    2085                 :             :         }
    2086                 :             : 
    2087                 :             :       /* If we get here, then one cluster binds this key and the other
    2088                 :             :          doesn't; merge them as "UNKNOWN".  */
    2089                 :       79698 :       gcc_assert (sval_a || sval_b);
    2090                 :             : 
    2091                 :       79698 :       const svalue *bound_sval = sval_a ? sval_a : sval_b;
    2092                 :       79698 :       tree type = bound_sval->get_type ();
    2093                 :       79698 :       const svalue *unknown_sval
    2094                 :       79698 :         = mgr->get_svalue_manager ()->get_or_create_unknown_svalue (type);
    2095                 :             : 
    2096                 :             :       /* ...but reject the merger if this sval shouldn't be mergeable
    2097                 :             :          (e.g. reject merging svalues that have non-purgable sm-state,
    2098                 :             :          to avoid falsely reporting memory leaks by merging them
    2099                 :             :          with something else).  */
    2100                 :       79698 :       if (!bound_sval->can_merge_p (unknown_sval, sval_mgr, merger))
    2101                 :             :         return false;
    2102                 :             : 
    2103                 :       42161 :       out_cluster->m_map.put (key, unknown_sval);
    2104                 :             :     }
    2105                 :             : 
    2106                 :             :   /* We can only have at most one symbolic key per cluster,
    2107                 :             :      and if we do, we can't have any concrete keys.
    2108                 :             :      If this happens, mark the cluster as touched, with no keys.  */
    2109                 :      955093 :   if (num_symbolic_keys >= 2
    2110                 :      954603 :       || (num_concrete_keys > 0 && num_symbolic_keys > 0))
    2111                 :             :     {
    2112                 :        1679 :       out_cluster->m_touched = true;
    2113                 :     1041889 :       out_cluster->m_map.empty ();
    2114                 :             :     }
    2115                 :             : 
    2116                 :             :   /* We don't handle other kinds of overlaps yet.  */
    2117                 :             : 
    2118                 :             :   return true;
    2119                 :     1040210 : }
    2120                 :             : 
    2121                 :             : /* Update this cluster to reflect an attempt to merge OTHER where there
    2122                 :             :    is no other cluster to merge with, and so we're notionally merging the
    2123                 :             :    bound values in OTHER with the initial value of the relevant regions.
    2124                 :             : 
    2125                 :             :    Any bound keys in OTHER should be bound to unknown in this.  */
    2126                 :             : 
    2127                 :             : void
    2128                 :       97874 : binding_cluster::make_unknown_relative_to (const binding_cluster *other,
    2129                 :             :                                            store *out_store,
    2130                 :             :                                            store_manager *mgr)
    2131                 :             : {
    2132                 :      197613 :   for (map_t::iterator iter = other->m_map.begin ();
    2133                 :      297352 :        iter != other->m_map.end (); ++iter)
    2134                 :             :     {
    2135                 :       99739 :       const binding_key *iter_key = (*iter).first;
    2136                 :       99739 :       const svalue *iter_sval = (*iter).second;
    2137                 :       99739 :       const svalue *unknown_sval
    2138                 :             :         = mgr->get_svalue_manager ()->get_or_create_unknown_svalue
    2139                 :       99739 :           (iter_sval->get_type ());
    2140                 :       99739 :       m_map.put (iter_key, unknown_sval);
    2141                 :             : 
    2142                 :             :       /* For any pointers in OTHER, the merger means that the
    2143                 :             :          concrete pointer becomes an unknown value, which could
    2144                 :             :          show up as a false report of a leak when considering what
    2145                 :             :          pointers are live before vs after.
    2146                 :             :          Avoid this by marking the base regions they point to as having
    2147                 :             :          escaped.  */
    2148                 :      199478 :       if (const region_svalue *region_sval
    2149                 :       99739 :           = iter_sval->dyn_cast_region_svalue ())
    2150                 :             :         {
    2151                 :        5731 :           const region *base_reg
    2152                 :        5731 :             = region_sval->get_pointee ()->get_base_region ();
    2153                 :        5731 :           if (base_reg->tracked_p ()
    2154                 :        5731 :               && !base_reg->symbolic_for_unknown_ptr_p ())
    2155                 :             :             {
    2156                 :        5692 :               binding_cluster *c = out_store->get_or_create_cluster (base_reg);
    2157                 :        5692 :               c->mark_as_escaped ();
    2158                 :             :             }
    2159                 :             :         }
    2160                 :             :     }
    2161                 :       97874 : }
    2162                 :             : 
    2163                 :             : /* Mark this cluster as having escaped.  */
    2164                 :             : 
    2165                 :             : void
    2166                 :       45166 : binding_cluster::mark_as_escaped ()
    2167                 :             : {
    2168                 :       45166 :   m_escaped = true;
    2169                 :       45166 : }
    2170                 :             : 
    2171                 :             : /* If this cluster has escaped (by this call, or by an earlier one, or
    2172                 :             :    by being an external param), then unbind all values and mark it
    2173                 :             :    as "touched", so that it has a conjured value, rather than an
    2174                 :             :    initial_svalue.
    2175                 :             :    Use P to purge state involving conjured_svalues.  */
    2176                 :             : 
    2177                 :             : void
    2178                 :      163821 : binding_cluster::on_unknown_fncall (const gcall *call,
    2179                 :             :                                     store_manager *mgr,
    2180                 :             :                                     const conjured_purge &p)
    2181                 :             : {
    2182                 :      163821 :   if (m_escaped)
    2183                 :             :     {
    2184                 :       27251 :       m_map.empty ();
    2185                 :             : 
    2186                 :       27251 :       if (!m_base_region->empty_p ())
    2187                 :             :         {
    2188                 :             :           /* Bind it to a new "conjured" value using CALL.  */
    2189                 :       27251 :           const svalue *sval
    2190                 :             :             = mgr->get_svalue_manager ()->get_or_create_conjured_svalue
    2191                 :       27251 :             (m_base_region->get_type (), call, m_base_region, p);
    2192                 :       27251 :           bind (mgr, m_base_region, sval);
    2193                 :             :         }
    2194                 :             : 
    2195                 :       27251 :       m_touched = true;
    2196                 :             :     }
    2197                 :      163821 : }
    2198                 :             : 
    2199                 :             : /* Mark this cluster as having been clobbered by STMT.
    2200                 :             :    Use P to purge state involving conjured_svalues.  */
    2201                 :             : 
    2202                 :             : void
    2203                 :         522 : binding_cluster::on_asm (const gasm *stmt,
    2204                 :             :                          store_manager *mgr,
    2205                 :             :                          const conjured_purge &p)
    2206                 :             : {
    2207                 :         522 :   m_map.empty ();
    2208                 :             : 
    2209                 :             :   /* Bind it to a new "conjured" value using CALL.  */
    2210                 :         522 :   const svalue *sval
    2211                 :             :     = mgr->get_svalue_manager ()->get_or_create_conjured_svalue
    2212                 :         522 :     (m_base_region->get_type (), stmt, m_base_region, p);
    2213                 :         522 :   bind (mgr, m_base_region, sval);
    2214                 :             : 
    2215                 :         522 :   m_touched = true;
    2216                 :         522 : }
    2217                 :             : 
    2218                 :             : /* Return true if this cluster has escaped.  */
    2219                 :             : 
    2220                 :             : bool
    2221                 :     8274788 : binding_cluster::escaped_p () const
    2222                 :             : {
    2223                 :             :   /* Consider the "errno" region to always have escaped.  */
    2224                 :     8274788 :   if (m_base_region->get_kind () == RK_ERRNO)
    2225                 :             :     return true;
    2226                 :     8244107 :   return m_escaped;
    2227                 :             : }
    2228                 :             : 
    2229                 :             : /* Return true if this binding_cluster has no information
    2230                 :             :    i.e. if there are no bindings, and it hasn't been marked as having
    2231                 :             :    escaped, or touched symbolically.  */
    2232                 :             : 
    2233                 :             : bool
    2234                 :      183648 : binding_cluster::redundant_p () const
    2235                 :             : {
    2236                 :      183648 :   return (m_map.elements () == 0
    2237                 :      175931 :           && !m_escaped
    2238                 :      358508 :           && !m_touched);
    2239                 :             : }
    2240                 :             : 
    2241                 :             : /* Add PV to OUT_PVS, casting it to TYPE if it is not already of that type.  */
    2242                 :             : 
    2243                 :             : static void
    2244                 :        8348 : append_pathvar_with_type (path_var pv,
    2245                 :             :                           tree type,
    2246                 :             :                           auto_vec<path_var> *out_pvs)
    2247                 :             : {
    2248                 :        8348 :   gcc_assert (pv.m_tree);
    2249                 :             : 
    2250                 :        8348 :   if (TREE_TYPE (pv.m_tree) != type)
    2251                 :         509 :     pv.m_tree = build1 (NOP_EXPR, type, pv.m_tree);
    2252                 :             : 
    2253                 :        8348 :   out_pvs->safe_push (pv);
    2254                 :        8348 : }
    2255                 :             : 
    2256                 :             : /* Find representative path_vars for SVAL within this binding of BASE_REG,
    2257                 :             :    appending the results to OUT_PVS.  */
    2258                 :             : 
    2259                 :             : void
    2260                 :       61002 : binding_cluster::get_representative_path_vars (const region_model *model,
    2261                 :             :                                                svalue_set *visited,
    2262                 :             :                                                const region *base_reg,
    2263                 :             :                                                const svalue *sval,
    2264                 :             :                                                logger *logger,
    2265                 :             :                                                auto_vec<path_var> *out_pvs)
    2266                 :             :   const
    2267                 :             : {
    2268                 :       61002 :   sval = simplify_for_binding (sval);
    2269                 :             : 
    2270                 :      175932 :   for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
    2271                 :             :     {
    2272                 :       57465 :       const binding_key *key = (*iter).first;
    2273                 :       57465 :       const svalue *bound_sval = (*iter).second;
    2274                 :       57465 :       if (bound_sval == sval)
    2275                 :             :         {
    2276                 :       17528 :           if (const concrete_binding *ckey
    2277                 :        8764 :                 = key->dyn_cast_concrete_binding ())
    2278                 :             :             {
    2279                 :        8700 :               auto_vec <const region *> subregions;
    2280                 :        8700 :               base_reg->get_subregions_for_binding
    2281                 :        8700 :                 (model->get_manager (),
    2282                 :             :                  ckey->get_start_bit_offset (),
    2283                 :             :                  ckey->get_size_in_bits (),
    2284                 :             :                  sval->get_type (),
    2285                 :             :                  &subregions);
    2286                 :        8700 :               unsigned i;
    2287                 :        8700 :               const region *subregion;
    2288                 :       25284 :               FOR_EACH_VEC_ELT (subregions, i, subregion)
    2289                 :             :                 {
    2290                 :       16584 :                   if (path_var pv
    2291                 :        8292 :                       = model->get_representative_path_var (subregion,
    2292                 :             :                                                             visited,
    2293                 :        8292 :                                                             logger))
    2294                 :        8284 :                     append_pathvar_with_type (pv, sval->get_type (), out_pvs);
    2295                 :             :                 }
    2296                 :        8700 :             }
    2297                 :             :           else
    2298                 :             :             {
    2299                 :          64 :               const symbolic_binding *skey = (const symbolic_binding *)key;
    2300                 :         128 :               if (path_var pv
    2301                 :          64 :                   = model->get_representative_path_var (skey->get_region (),
    2302                 :             :                                                         visited,
    2303                 :          64 :                                                         logger))
    2304                 :          64 :                 append_pathvar_with_type (pv, sval->get_type (), out_pvs);
    2305                 :             :             }
    2306                 :             :         }
    2307                 :             :     }
    2308                 :       61002 : }
    2309                 :             : 
    2310                 :             : /* Get any svalue bound to KEY, or NULL.  */
    2311                 :             : 
    2312                 :             : const svalue *
    2313                 :     2490817 : binding_cluster::get_any_value (const binding_key *key) const
    2314                 :             : {
    2315                 :     2490817 :   return m_map.get (key);
    2316                 :             : }
    2317                 :             : 
    2318                 :             : /* If this cluster has a single direct binding for the whole of the region,
    2319                 :             :    return it.
    2320                 :             :    For use in simplifying dumps.  */
    2321                 :             : 
    2322                 :             : const svalue *
    2323                 :      360911 : binding_cluster::maybe_get_simple_value (store_manager *mgr) const
    2324                 :             : {
    2325                 :             :   /* Fail gracefully if MGR is NULL to make it easier to dump store
    2326                 :             :      instances in the debugger.  */
    2327                 :      360911 :   if (mgr == NULL)
    2328                 :             :     return NULL;
    2329                 :             : 
    2330                 :      360911 :   if (m_map.elements () != 1)
    2331                 :             :     return NULL;
    2332                 :             : 
    2333                 :      169475 :   if (m_base_region->empty_p ())
    2334                 :             :     return NULL;
    2335                 :             : 
    2336                 :      169475 :   const binding_key *key = binding_key::make (mgr, m_base_region);
    2337                 :      169475 :   return get_any_value (key);
    2338                 :             : }
    2339                 :             : 
    2340                 :             : /* class store_manager.  */
    2341                 :             : 
    2342                 :             : logger *
    2343                 :      329201 : store_manager::get_logger () const
    2344                 :             : {
    2345                 :      329201 :   return m_mgr->get_logger ();
    2346                 :             : }
    2347                 :             : 
    2348                 :             : /* binding consolidation.  */
    2349                 :             : 
    2350                 :             : const concrete_binding *
    2351                 :     2294926 : store_manager::get_concrete_binding (bit_offset_t start_bit_offset,
    2352                 :             :                                      bit_offset_t size_in_bits)
    2353                 :             : {
    2354                 :     2294926 :   concrete_binding b (start_bit_offset, size_in_bits);
    2355                 :     4578321 :   if (concrete_binding *existing = m_concrete_binding_key_mgr.get (b))
    2356                 :             :     return existing;
    2357                 :             : 
    2358                 :       11531 :   concrete_binding *to_save = new concrete_binding (b);
    2359                 :       11531 :   m_concrete_binding_key_mgr.put (b, to_save);
    2360                 :       11531 :   return to_save;
    2361                 :     2294926 : }
    2362                 :             : 
    2363                 :             : const symbolic_binding *
    2364                 :     1288164 : store_manager::get_symbolic_binding (const region *reg)
    2365                 :             : {
    2366                 :     1288164 :   symbolic_binding b (reg);
    2367                 :     2558196 :   if (symbolic_binding *existing = m_symbolic_binding_key_mgr.get (b))
    2368                 :             :     return existing;
    2369                 :             : 
    2370                 :       18132 :   symbolic_binding *to_save = new symbolic_binding (b);
    2371                 :       18132 :   m_symbolic_binding_key_mgr.put (b, to_save);
    2372                 :       18132 :   return to_save;
    2373                 :     1288164 : }
    2374                 :             : 
    2375                 :             : /* class store.  */
    2376                 :             : 
    2377                 :             : /* store's default ctor.  */
    2378                 :             : 
    2379                 :      338548 : store::store ()
    2380                 :      338548 : : m_called_unknown_fn (false)
    2381                 :             : {
    2382                 :      338548 : }
    2383                 :             : 
    2384                 :             : /* store's copy ctor.  */
    2385                 :             : 
    2386                 :     3527289 : store::store (const store &other)
    2387                 :     3527289 : : m_cluster_map (other.m_cluster_map.elements ()),
    2388                 :     3527289 :   m_called_unknown_fn (other.m_called_unknown_fn)
    2389                 :             : {
    2390                 :     3527289 :   for (cluster_map_t::iterator iter = other.m_cluster_map.begin ();
    2391                 :    27259498 :        iter != other.m_cluster_map.end ();
    2392                 :    23732209 :        ++iter)
    2393                 :             :     {
    2394                 :    23732209 :       const region *reg = (*iter).first;
    2395                 :           0 :       gcc_assert (reg);
    2396                 :    23732209 :       binding_cluster *c = (*iter).second;
    2397                 :    23732209 :       gcc_assert (c);
    2398                 :    23732209 :       m_cluster_map.put (reg, new binding_cluster (*c));
    2399                 :             :     }
    2400                 :     3527289 : }
    2401                 :             : 
    2402                 :             : /* store's dtor.  */
    2403                 :             : 
    2404                 :     3865837 : store::~store ()
    2405                 :             : {
    2406                 :    28832092 :   for (cluster_map_t::iterator iter = m_cluster_map.begin ();
    2407                 :    28832092 :        iter != m_cluster_map.end ();
    2408                 :    24966255 :        ++iter)
    2409                 :    24966255 :     delete (*iter).second;
    2410                 :     3865837 : }
    2411                 :             : 
    2412                 :             : /* store's assignment operator.  */
    2413                 :             : 
    2414                 :             : store &
    2415                 :       17527 : store::operator= (const store &other)
    2416                 :             : {
    2417                 :             :   /* Delete existing cluster map.  */
    2418                 :      132344 :   for (cluster_map_t::iterator iter = m_cluster_map.begin ();
    2419                 :      132344 :        iter != m_cluster_map.end ();
    2420                 :      114817 :        ++iter)
    2421                 :      229634 :     delete (*iter).second;
    2422                 :       17527 :   m_cluster_map.empty ();
    2423                 :             : 
    2424                 :       17527 :   m_called_unknown_fn = other.m_called_unknown_fn;
    2425                 :             : 
    2426                 :       17527 :   for (cluster_map_t::iterator iter = other.m_cluster_map.begin ();
    2427                 :      145581 :        iter != other.m_cluster_map.end ();
    2428                 :      128054 :        ++iter)
    2429                 :             :     {
    2430                 :      128054 :       const region *reg = (*iter).first;
    2431                 :      128054 :       gcc_assert (reg);
    2432                 :      128054 :       binding_cluster *c = (*iter).second;
    2433                 :      128054 :       gcc_assert (c);
    2434                 :      128054 :       m_cluster_map.put (reg, new binding_cluster (*c));
    2435                 :             :     }
    2436                 :       17527 :   return *this;
    2437                 :             : }
    2438                 :             : 
    2439                 :             : /* store's equality operator.  */
    2440                 :             : 
    2441                 :             : bool
    2442                 :      431154 : store::operator== (const store &other) const
    2443                 :             : {
    2444                 :      431154 :   if (m_called_unknown_fn != other.m_called_unknown_fn)
    2445                 :             :     return false;
    2446                 :             : 
    2447                 :      428239 :   if (m_cluster_map.elements () != other.m_cluster_map.elements ())
    2448                 :             :     return false;
    2449                 :             : 
    2450                 :     2314262 :   for (cluster_map_t::iterator iter = m_cluster_map.begin ();
    2451                 :     2314262 :        iter != m_cluster_map.end ();
    2452                 :     1909064 :        ++iter)
    2453                 :             :     {
    2454                 :     1942584 :       const region *reg = (*iter).first;
    2455                 :     1942584 :       binding_cluster *c = (*iter).second;
    2456                 :     1942584 :       binding_cluster **other_slot
    2457                 :     1942584 :         = const_cast <cluster_map_t &> (other.m_cluster_map).get (reg);
    2458                 :     1942584 :       if (other_slot == NULL)
    2459                 :       33520 :         return false;
    2460                 :     1941424 :       if (*c != **other_slot)
    2461                 :             :         return false;
    2462                 :             :     }
    2463                 :             : 
    2464                 :      371678 :   gcc_checking_assert (hash () == other.hash ());
    2465                 :             : 
    2466                 :             :   return true;
    2467                 :             : }
    2468                 :             : 
    2469                 :             : /* Get a hash value for this store.  */
    2470                 :             : 
    2471                 :             : hashval_t
    2472                 :     1908168 : store::hash () const
    2473                 :             : {
    2474                 :     1908168 :   hashval_t result = 0;
    2475                 :     1908168 :   for (cluster_map_t::iterator iter = m_cluster_map.begin ();
    2476                 :    11673331 :        iter != m_cluster_map.end ();
    2477                 :     9765163 :        ++iter)
    2478                 :     9765163 :     result ^= (*iter).second->hash ();
    2479                 :     1908168 :   return result;
    2480                 :             : }
    2481                 :             : 
    2482                 :             : /* Populate OUT with a sorted list of parent regions for the regions in IN,
    2483                 :             :    removing duplicate parents.  */
    2484                 :             : 
    2485                 :             : static void
    2486                 :        1960 : get_sorted_parent_regions (auto_vec<const region *> *out,
    2487                 :             :                            auto_vec<const region *> &in)
    2488                 :             : {
    2489                 :             :   /* Get the set of parent regions.  */
    2490                 :        1960 :   hash_set<const region *> parent_regions;
    2491                 :        1960 :   const region *iter_reg;
    2492                 :        1960 :   unsigned i;
    2493                 :        9843 :   FOR_EACH_VEC_ELT (in, i, iter_reg)
    2494                 :             :     {
    2495                 :        7883 :       const region *parent_reg = iter_reg->get_parent_region ();
    2496                 :        7883 :       gcc_assert (parent_reg);
    2497                 :        7883 :       parent_regions.add (parent_reg);
    2498                 :             :     }
    2499                 :             : 
    2500                 :             :   /* Write to OUT.  */
    2501                 :        1960 :   for (hash_set<const region *>::iterator iter = parent_regions.begin();
    2502                 :       10214 :        iter != parent_regions.end(); ++iter)
    2503                 :        4127 :     out->safe_push (*iter);
    2504                 :             : 
    2505                 :             :   /* Sort OUT.  */
    2506                 :        3747 :   out->qsort (region::cmp_ptr_ptr);
    2507                 :        1960 : }
    2508                 :             : 
    2509                 :             : /* Dump a representation of this store to PP, using SIMPLE to control how
    2510                 :             :    svalues and regions are printed.
    2511                 :             :    MGR is used for simplifying dumps if non-NULL, but can also be NULL
    2512                 :             :    (to make it easier to use from the debugger).  */
    2513                 :             : 
    2514                 :             : void
    2515                 :        1952 : store::dump_to_pp (pretty_printer *pp, bool simple, bool multiline,
    2516                 :             :                    store_manager *mgr) const
    2517                 :             : {
    2518                 :             :   /* Sort into some deterministic order.  */
    2519                 :        1952 :   auto_vec<const region *> base_regions;
    2520                 :        9835 :   for (cluster_map_t::iterator iter = m_cluster_map.begin ();
    2521                 :       17718 :        iter != m_cluster_map.end (); ++iter)
    2522                 :             :     {
    2523                 :        7883 :       const region *base_reg = (*iter).first;
    2524                 :        7883 :       base_regions.safe_push (base_reg);
    2525                 :             :     }
    2526                 :        1952 :   base_regions.qsort (region::cmp_ptr_ptr);
    2527                 :             : 
    2528                 :             :   /* Gather clusters, organize by parent region, so that we can group
    2529                 :             :      together locals, globals, etc.  */
    2530                 :        1952 :   auto_vec<const region *> parent_regions;
    2531                 :        1952 :   get_sorted_parent_regions (&parent_regions, base_regions);
    2532                 :             : 
    2533                 :        1952 :   const region *parent_reg;
    2534                 :        1952 :   unsigned i;
    2535                 :        6079 :   FOR_EACH_VEC_ELT (parent_regions, i, parent_reg)
    2536                 :             :     {
    2537                 :        4127 :       gcc_assert (parent_reg);
    2538                 :        4127 :       pp_string (pp, "clusters within ");
    2539                 :        4127 :       parent_reg->dump_to_pp (pp, simple);
    2540                 :        4127 :       if (multiline)
    2541                 :        1640 :         pp_newline (pp);
    2542                 :             :       else
    2543                 :        2487 :         pp_string (pp, " {");
    2544                 :             : 
    2545                 :             :       const region *base_reg;
    2546                 :             :       unsigned j;
    2547                 :       23791 :       FOR_EACH_VEC_ELT (base_regions, j, base_reg)
    2548                 :             :         {
    2549                 :             :           /* This is O(N * M), but N ought to be small.  */
    2550                 :       19664 :           if (base_reg->get_parent_region () != parent_reg)
    2551                 :       11781 :             continue;
    2552                 :        7883 :           binding_cluster *cluster
    2553                 :        7883 :             = *const_cast<cluster_map_t &> (m_cluster_map).get (base_reg);
    2554                 :        7883 :           if (!multiline)
    2555                 :             :             {
    2556                 :        4151 :               if (j > 0)
    2557                 :        3152 :                 pp_string (pp, ", ");
    2558                 :             :             }
    2559                 :        7883 :           if (const svalue *sval = cluster->maybe_get_simple_value (mgr))
    2560                 :             :             {
    2561                 :             :               /* Special-case to simplify dumps for the common case where
    2562                 :             :                  we just have one value directly bound to the whole of a
    2563                 :             :                  region.  */
    2564                 :        5710 :               if (multiline)
    2565                 :             :                 {
    2566                 :        2308 :                   pp_string (pp, "  cluster for: ");
    2567                 :        2308 :                   base_reg->dump_to_pp (pp, simple);
    2568                 :        2308 :                   pp_string (pp, ": ");
    2569                 :        2308 :                   sval->dump_to_pp (pp, simple);
    2570                 :        2308 :                   if (cluster->escaped_p ())
    2571                 :         144 :                     pp_string (pp, " (ESCAPED)");
    2572                 :        2308 :                   if (cluster->touched_p ())
    2573                 :           0 :                     pp_string (pp, " (TOUCHED)");
    2574                 :        2308 :                   pp_newline (pp);
    2575                 :             :                 }
    2576                 :             :               else
    2577                 :             :                 {
    2578                 :        3402 :                   pp_string (pp, "region: {");
    2579                 :        3402 :                   base_reg->dump_to_pp (pp, simple);
    2580                 :        3402 :                   pp_string (pp, ", value: ");
    2581                 :        3402 :                   sval->dump_to_pp (pp, simple);
    2582                 :        3402 :                   if (cluster->escaped_p ())
    2583                 :         813 :                     pp_string (pp, " (ESCAPED)");
    2584                 :        3402 :                   if (cluster->touched_p ())
    2585                 :         813 :                     pp_string (pp, " (TOUCHED)");
    2586                 :        3402 :                   pp_string (pp, "}");
    2587                 :             :                 }
    2588                 :             :             }
    2589                 :        2173 :           else if (multiline)
    2590                 :             :             {
    2591                 :        1424 :               pp_string (pp, "  cluster for: ");
    2592                 :        1424 :               base_reg->dump_to_pp (pp, simple);
    2593                 :        1424 :               pp_newline (pp);
    2594                 :        1424 :               cluster->dump_to_pp (pp, simple, multiline);
    2595                 :             :             }
    2596                 :             :           else
    2597                 :             :             {
    2598                 :         749 :               pp_string (pp, "base region: {");
    2599                 :         749 :               base_reg->dump_to_pp (pp, simple);
    2600                 :         749 :               pp_string (pp, "} has cluster: {");
    2601                 :         749 :               cluster->dump_to_pp (pp, simple, multiline);
    2602                 :         749 :               pp_string (pp, "}");
    2603                 :             :             }
    2604                 :             :         }
    2605                 :        4127 :       if (!multiline)
    2606                 :        2487 :         pp_string (pp, "}");
    2607                 :             :     }
    2608                 :        1952 :   pp_printf (pp, "m_called_unknown_fn: %s",
    2609                 :        1952 :              m_called_unknown_fn ? "TRUE" : "FALSE");
    2610                 :        1952 :   if (multiline)
    2611                 :         856 :     pp_newline (pp);
    2612                 :        1952 : }
    2613                 :             : 
    2614                 :             : /* Dump a multiline representation of this store to stderr.  */
    2615                 :             : 
    2616                 :             : DEBUG_FUNCTION void
    2617                 :           0 : store::dump (bool simple) const
    2618                 :             : {
    2619                 :           0 :   tree_dump_pretty_printer pp (stderr);
    2620                 :           0 :   dump_to_pp (&pp, simple, true, NULL);
    2621                 :           0 :   pp_newline (&pp);
    2622                 :           0 : }
    2623                 :             : 
    2624                 :             : /* Assert that this object is valid.  */
    2625                 :             : 
    2626                 :             : void
    2627                 :     1644532 : store::validate () const
    2628                 :             : {
    2629                 :    10476369 :   for (auto iter : m_cluster_map)
    2630                 :     8831837 :     iter.second->validate ();
    2631                 :     1644532 : }
    2632                 :             : 
    2633                 :             : /* Return a new json::object of the form
    2634                 :             :    {PARENT_REGION_DESC: {BASE_REGION_DESC: object for binding_map,
    2635                 :             :                          ... for each cluster within parent region},
    2636                 :             :     ...for each parent region,
    2637                 :             :     "called_unknown_fn": true/false}.  */
    2638                 :             : 
    2639                 :             : std::unique_ptr<json::object>
    2640                 :           4 : store::to_json () const
    2641                 :             : {
    2642                 :           4 :   auto store_obj = ::make_unique<json::object> ();
    2643                 :             : 
    2644                 :             :   /* Sort into some deterministic order.  */
    2645                 :           4 :   auto_vec<const region *> base_regions;
    2646                 :           4 :   for (cluster_map_t::iterator iter = m_cluster_map.begin ();
    2647                 :           4 :        iter != m_cluster_map.end (); ++iter)
    2648                 :             :     {
    2649                 :           0 :       const region *base_reg = (*iter).first;
    2650                 :           0 :       base_regions.safe_push (base_reg);
    2651                 :             :     }
    2652                 :           4 :   base_regions.qsort (region::cmp_ptr_ptr);
    2653                 :             : 
    2654                 :             :   /* Gather clusters, organize by parent region, so that we can group
    2655                 :             :      together locals, globals, etc.  */
    2656                 :           4 :   auto_vec<const region *> parent_regions;
    2657                 :           4 :   get_sorted_parent_regions (&parent_regions, base_regions);
    2658                 :             : 
    2659                 :           4 :   const region *parent_reg;
    2660                 :           4 :   unsigned i;
    2661                 :           4 :   FOR_EACH_VEC_ELT (parent_regions, i, parent_reg)
    2662                 :             :     {
    2663                 :           0 :       gcc_assert (parent_reg);
    2664                 :             : 
    2665                 :           0 :       auto clusters_in_parent_reg_obj = ::make_unique<json::object> ();
    2666                 :             : 
    2667                 :           0 :       const region *base_reg;
    2668                 :           0 :       unsigned j;
    2669                 :           0 :       FOR_EACH_VEC_ELT (base_regions, j, base_reg)
    2670                 :             :         {
    2671                 :             :           /* This is O(N * M), but N ought to be small.  */
    2672                 :           0 :           if (base_reg->get_parent_region () != parent_reg)
    2673                 :           0 :             continue;
    2674                 :           0 :           binding_cluster *cluster
    2675                 :           0 :             = *const_cast<cluster_map_t &> (m_cluster_map).get (base_reg);
    2676                 :           0 :           label_text base_reg_desc = base_reg->get_desc ();
    2677                 :           0 :           clusters_in_parent_reg_obj->set (base_reg_desc.get (),
    2678                 :           0 :                                            cluster->to_json ());
    2679                 :           0 :         }
    2680                 :           0 :       label_text parent_reg_desc = parent_reg->get_desc ();
    2681                 :           0 :       store_obj->set (parent_reg_desc.get (),
    2682                 :             :                       std::move (clusters_in_parent_reg_obj));
    2683                 :           0 :     }
    2684                 :             : 
    2685                 :           4 :   store_obj->set_bool ("called_unknown_fn", m_called_unknown_fn);
    2686                 :             : 
    2687                 :           4 :   return store_obj;
    2688                 :           4 : }
    2689                 :             : 
    2690                 :             : std::unique_ptr<text_art::tree_widget>
    2691                 :           4 : store::make_dump_widget (const text_art::dump_widget_info &dwi,
    2692                 :             :                          store_manager *mgr) const
    2693                 :             : {
    2694                 :           4 :   std::unique_ptr<text_art::tree_widget> store_widget
    2695                 :           4 :     (text_art::tree_widget::make (dwi, "Store"));
    2696                 :             : 
    2697                 :           4 :   store_widget->add_child
    2698                 :           8 :     (text_art::tree_widget::from_fmt (dwi, nullptr,
    2699                 :             :                                       "m_called_unknown_fn: %s",
    2700                 :           4 :                                       m_called_unknown_fn ? "true" : "false"));
    2701                 :             : 
    2702                 :             :     /* Sort into some deterministic order.  */
    2703                 :           4 :   auto_vec<const region *> base_regions;
    2704                 :           4 :   for (cluster_map_t::iterator iter = m_cluster_map.begin ();
    2705                 :           4 :        iter != m_cluster_map.end (); ++iter)
    2706                 :             :     {
    2707                 :           0 :       const region *base_reg = (*iter).first;
    2708                 :           0 :       base_regions.safe_push (base_reg);
    2709                 :             :     }
    2710                 :           4 :   base_regions.qsort (region::cmp_ptr_ptr);
    2711                 :             : 
    2712                 :             :   /* Gather clusters, organize by parent region, so that we can group
    2713                 :             :      together locals, globals, etc.  */
    2714                 :           4 :   auto_vec<const region *> parent_regions;
    2715                 :           4 :   get_sorted_parent_regions (&parent_regions, base_regions);
    2716                 :             : 
    2717                 :           4 :   const region *parent_reg;
    2718                 :           4 :   unsigned i;
    2719                 :           4 :   FOR_EACH_VEC_ELT (parent_regions, i, parent_reg)
    2720                 :             :     {
    2721                 :           0 :       gcc_assert (parent_reg);
    2722                 :             : 
    2723                 :           0 :       pretty_printer the_pp;
    2724                 :           0 :       pretty_printer * const pp = &the_pp;
    2725                 :           0 :       pp_format_decoder (pp) = default_tree_printer;
    2726                 :           0 :       pp_show_color (pp) = true;
    2727                 :           0 :       const bool simple = true;
    2728                 :             : 
    2729                 :           0 :       parent_reg->dump_to_pp (pp, simple);
    2730                 :             : 
    2731                 :           0 :       std::unique_ptr<text_art::tree_widget> parent_reg_widget
    2732                 :           0 :         (text_art::tree_widget::make (dwi, pp));
    2733                 :             : 
    2734                 :           0 :       const region *base_reg;
    2735                 :           0 :       unsigned j;
    2736                 :           0 :       FOR_EACH_VEC_ELT (base_regions, j, base_reg)
    2737                 :             :         {
    2738                 :             :           /* This is O(N * M), but N ought to be small.  */
    2739                 :           0 :           if (base_reg->get_parent_region () != parent_reg)
    2740                 :           0 :             continue;
    2741                 :           0 :           binding_cluster *cluster
    2742                 :           0 :             = *const_cast<cluster_map_t &> (m_cluster_map).get (base_reg);
    2743                 :           0 :           parent_reg_widget->add_child
    2744                 :           0 :             (cluster->make_dump_widget (dwi, mgr));
    2745                 :             :         }
    2746                 :           0 :       store_widget->add_child (std::move (parent_reg_widget));
    2747                 :           0 :     }
    2748                 :             : 
    2749                 :           4 :   return store_widget;
    2750                 :           4 : }
    2751                 :             : 
    2752                 :             : /* Get any svalue bound to REG, or NULL.  */
    2753                 :             : 
    2754                 :             : const svalue *
    2755                 :     3718282 : store::get_any_binding (store_manager *mgr, const region *reg) const
    2756                 :             : {
    2757                 :     3718282 :   const region *base_reg = reg->get_base_region ();
    2758                 :     3718282 :   binding_cluster **cluster_slot
    2759                 :     3718282 :     = const_cast <cluster_map_t &> (m_cluster_map).get (base_reg);
    2760                 :     3718282 :   if (!cluster_slot)
    2761                 :             :     return NULL;
    2762                 :     1219692 :   return (*cluster_slot)->get_any_binding (mgr, reg);
    2763                 :             : }
    2764                 :             : 
    2765                 :             : /* Set the value of LHS_REG to RHS_SVAL.  */
    2766                 :             : 
    2767                 :             : void
    2768                 :      329201 : store::set_value (store_manager *mgr, const region *lhs_reg,
    2769                 :             :                   const svalue *rhs_sval,
    2770                 :             :                   uncertainty_t *uncertainty)
    2771                 :             : {
    2772                 :      329201 :   logger *logger = mgr->get_logger ();
    2773                 :      329201 :   LOG_SCOPE (logger);
    2774                 :             : 
    2775                 :      329201 :   remove_overlapping_bindings (mgr, lhs_reg, uncertainty);
    2776                 :             : 
    2777                 :      329201 :   if (lhs_reg->get_type ())
    2778                 :      321900 :     rhs_sval = simplify_for_binding (rhs_sval);
    2779                 :             :   /* ...but if we have no type for the region, retain any cast.  */
    2780                 :             : 
    2781                 :      329201 :   const region *lhs_base_reg = lhs_reg->get_base_region ();
    2782                 :      329201 :   binding_cluster *lhs_cluster;
    2783                 :      329201 :   if (lhs_base_reg->symbolic_for_unknown_ptr_p ())
    2784                 :             :     {
    2785                 :             :       /* Reject attempting to bind values into a symbolic region
    2786                 :             :          for an unknown ptr; merely invalidate values below.  */
    2787                 :        3394 :       lhs_cluster = NULL;
    2788                 :             : 
    2789                 :             :       /* The LHS of the write is *UNKNOWN.  If the RHS is a pointer,
    2790                 :             :          then treat the region being pointed to as having escaped.  */
    2791                 :        3394 :       if (const region_svalue *ptr_sval = rhs_sval->dyn_cast_region_svalue ())
    2792                 :             :         {
    2793                 :         161 :           const region *ptr_dst = ptr_sval->get_pointee ();
    2794                 :         161 :           const region *ptr_base_reg = ptr_dst->get_base_region ();
    2795                 :         161 :           mark_as_escaped (ptr_base_reg);
    2796                 :             :         }
    2797                 :        3394 :       if (uncertainty)
    2798                 :        1571 :         uncertainty->on_maybe_bound_sval (rhs_sval);
    2799                 :             :     }
    2800                 :      325807 :   else if (lhs_base_reg->tracked_p ())
    2801                 :             :     {
    2802                 :      325728 :       lhs_cluster = get_or_create_cluster (lhs_base_reg);
    2803                 :      325728 :       lhs_cluster->bind (mgr, lhs_reg, rhs_sval);
    2804                 :             :     }
    2805                 :             :   else
    2806                 :             :     {
    2807                 :             :       /* Reject attempting to bind values into an untracked region;
    2808                 :             :          merely invalidate values below.  */
    2809                 :             :       lhs_cluster = NULL;
    2810                 :             :     }
    2811                 :             : 
    2812                 :             :   /* Bindings to a cluster can affect other clusters if a symbolic
    2813                 :             :      base region is involved.
    2814                 :             :      Writes to concrete clusters can't affect other concrete clusters,
    2815                 :             :      but can affect symbolic clusters.
    2816                 :             :      Writes to symbolic clusters can affect both concrete and symbolic
    2817                 :             :      clusters.
    2818                 :             :      Invalidate our knowledge of other clusters that might have been
    2819                 :             :      affected by the write.
    2820                 :             :      Gather the set of all svalues that might still be live even if
    2821                 :             :      the store doesn't refer to them.  */
    2822                 :      329201 :   svalue_set maybe_live_values;
    2823                 :     4555771 :   for (cluster_map_t::iterator iter = m_cluster_map.begin ();
    2824                 :     8782341 :        iter != m_cluster_map.end (); ++iter)
    2825                 :             :     {
    2826                 :     4226570 :       const region *iter_base_reg = (*iter).first;
    2827                 :     4226570 :       binding_cluster *iter_cluster = (*iter).second;
    2828                 :     4226570 :       if (iter_base_reg != lhs_base_reg
    2829                 :     4226570 :           && (lhs_cluster == NULL
    2830                 :     3844851 :               || lhs_cluster->symbolic_p ()
    2831                 :     3764192 :               || iter_cluster->symbolic_p ()))
    2832                 :             :         {
    2833                 :      568654 :           tristate t_alias = eval_alias (lhs_base_reg, iter_base_reg);
    2834                 :      568654 :           switch (t_alias.get_value ())
    2835                 :             :             {
    2836                 :           0 :             default:
    2837                 :           0 :               gcc_unreachable ();
    2838                 :             : 
    2839                 :       61860 :             case tristate::TS_UNKNOWN:
    2840                 :       61860 :               if (logger)
    2841                 :             :                 {
    2842                 :           7 :                   pretty_printer *pp = logger->get_printer ();
    2843                 :           7 :                   logger->start_log_line ();
    2844                 :           7 :                   logger->log_partial ("possible aliasing of ");
    2845                 :           7 :                   iter_base_reg->dump_to_pp (pp, true);
    2846                 :           7 :                   logger->log_partial (" when writing SVAL: ");
    2847                 :           7 :                   rhs_sval->dump_to_pp (pp, true);
    2848                 :           7 :                   logger->log_partial (" to LHS_REG: ");
    2849                 :           7 :                   lhs_reg->dump_to_pp (pp, true);
    2850                 :           7 :                   logger->end_log_line ();
    2851                 :             :                 }
    2852                 :             :               /* Mark all of iter_cluster's iter_base_reg as unknown,
    2853                 :             :                  using LHS_REG when considering overlaps, to handle
    2854                 :             :                  symbolic vs concrete issues.  */
    2855                 :       61860 :               iter_cluster->mark_region_as_unknown
    2856                 :       61860 :                 (mgr,
    2857                 :             :                  iter_base_reg, /* reg_to_bind */
    2858                 :             :                  lhs_reg, /* reg_for_overlap */
    2859                 :             :                  uncertainty,
    2860                 :             :                  &maybe_live_values);
    2861                 :       61860 :               break;
    2862                 :             : 
    2863                 :           0 :             case tristate::TS_TRUE:
    2864                 :           0 :               gcc_unreachable ();
    2865                 :             :               break;
    2866                 :             : 
    2867                 :             :             case tristate::TS_FALSE:
    2868                 :             :               /* If they can't be aliases, then don't invalidate this
    2869                 :             :                  cluster.  */
    2870                 :             :               break;
    2871                 :             :             }
    2872                 :             :         }
    2873                 :             :     }
    2874                 :             :   /* Given the set of svalues that might still be live, process them
    2875                 :             :      (e.g. marking regions as escaped).
    2876                 :             :      We do this after the iteration to avoid potentially changing
    2877                 :             :      m_cluster_map whilst iterating over it.  */
    2878                 :      329201 :   on_maybe_live_values (maybe_live_values);
    2879                 :      329201 : }
    2880                 :             : 
    2881                 :             : /* Determine if BASE_REG_A could be an alias of BASE_REG_B.  */
    2882                 :             : 
    2883                 :             : tristate
    2884                 :      569209 : store::eval_alias (const region *base_reg_a,
    2885                 :             :                    const region *base_reg_b) const
    2886                 :             : {
    2887                 :             :   /* SSA names can't alias.  */
    2888                 :      569209 :   tree decl_a = base_reg_a->maybe_get_decl ();
    2889                 :      569209 :   if (decl_a && TREE_CODE (decl_a) == SSA_NAME)
    2890                 :      375028 :     return tristate::TS_FALSE;
    2891                 :      194181 :   tree decl_b = base_reg_b->maybe_get_decl ();
    2892                 :      194181 :   if (decl_b && TREE_CODE (decl_b) == SSA_NAME)
    2893                 :       64824 :     return tristate::TS_FALSE;
    2894                 :             : 
    2895                 :             :   /* Try both ways, for symmetry.  */
    2896                 :      129357 :   tristate ts_ab = eval_alias_1 (base_reg_a, base_reg_b);
    2897                 :      129357 :   if (ts_ab.is_false ())
    2898                 :       23976 :     return tristate::TS_FALSE;
    2899                 :      105381 :   tristate ts_ba = eval_alias_1 (base_reg_b, base_reg_a);
    2900                 :      105381 :   if (ts_ba.is_false ())
    2901                 :       43261 :     return tristate::TS_FALSE;
    2902                 :       62120 :   return tristate::TS_UNKNOWN;
    2903                 :             : }
    2904                 :             : 
    2905                 :             : /* Half of store::eval_alias; called twice for symmetry.  */
    2906                 :             : 
    2907                 :             : tristate
    2908                 :      234738 : store::eval_alias_1 (const region *base_reg_a,
    2909                 :             :                      const region *base_reg_b) const
    2910                 :             : {
    2911                 :             :   /* If they're in different memory spaces, they can't alias.  */
    2912                 :      234738 :   {
    2913                 :      234738 :     enum memory_space memspace_a = base_reg_a->get_memory_space ();
    2914                 :      234738 :     if (memspace_a != MEMSPACE_UNKNOWN)
    2915                 :             :       {
    2916                 :       80205 :         enum memory_space memspace_b = base_reg_b->get_memory_space ();
    2917                 :       80205 :         if (memspace_b != MEMSPACE_UNKNOWN
    2918                 :       80205 :             && memspace_a != memspace_b)
    2919                 :         249 :           return tristate::TS_FALSE;
    2920                 :             :       }
    2921                 :             :   }
    2922                 :             : 
    2923                 :      468978 :   if (const symbolic_region *sym_reg_a
    2924                 :      234489 :       = base_reg_a->dyn_cast_symbolic_region ())
    2925                 :             :     {
    2926                 :      148699 :       const svalue *sval_a = sym_reg_a->get_pointer ();
    2927                 :      148699 :       if (tree decl_b = base_reg_b->maybe_get_decl ())
    2928                 :             :         {
    2929                 :       76074 :           if (!may_be_aliased (decl_b))
    2930                 :       44294 :             return tristate::TS_FALSE;
    2931                 :       31780 :           if (sval_a->get_kind () == SK_INITIAL)
    2932                 :       19084 :             if (!is_global_var (decl_b))
    2933                 :             :               {
    2934                 :             :                 /* The initial value of a pointer can't point to a local.  */
    2935                 :       13033 :                 return tristate::TS_FALSE;
    2936                 :             :               }
    2937                 :             :         }
    2938                 :       91372 :       if (sval_a->get_kind () == SK_INITIAL
    2939                 :       91372 :           && base_reg_b->get_kind () == RK_HEAP_ALLOCATED)
    2940                 :             :         {
    2941                 :             :           /* The initial value of a pointer can't point to a
    2942                 :             :              region that was allocated on the heap after the beginning of the
    2943                 :             :              path.  */
    2944                 :        9366 :           return tristate::TS_FALSE;
    2945                 :             :         }
    2946                 :      164012 :       if (const widening_svalue *widening_sval_a
    2947                 :       82006 :           = sval_a->dyn_cast_widening_svalue ())
    2948                 :             :         {
    2949                 :        3579 :           const svalue *base = widening_sval_a->get_base_svalue ();
    2950                 :        7158 :           if (const region_svalue *region_sval
    2951                 :        3579 :                 = base->dyn_cast_region_svalue ())
    2952                 :             :             {
    2953                 :         555 :               const region *pointee = region_sval->get_pointee ();
    2954                 :             :               /* If we have sval_a is WIDENING(&REGION, OP), and
    2955                 :             :                  B can't alias REGION, then B can't alias A either.
    2956                 :             :                  For example, A might arise from
    2957                 :             :                    for (ptr = &REGION; ...; ptr++)
    2958                 :             :                  where sval_a is ptr in the 2nd iteration of the loop.
    2959                 :             :                  We want to ensure that "*ptr" can only clobber things
    2960                 :             :                  within REGION's base region.  */
    2961                 :         555 :               tristate ts = eval_alias (pointee->get_base_region (),
    2962                 :             :                                         base_reg_b);
    2963                 :         555 :               if (ts.is_false ())
    2964                 :         295 :                 return tristate::TS_FALSE;
    2965                 :             :             }
    2966                 :             :         }
    2967                 :             :     }
    2968                 :      167501 :   return tristate::TS_UNKNOWN;
    2969                 :             : }
    2970                 :             : 
    2971                 :             : /* Record all of the values in MAYBE_LIVE_VALUES as being possibly live.  */
    2972                 :             : 
    2973                 :             : void
    2974                 :      329490 : store::on_maybe_live_values (const svalue_set &maybe_live_values)
    2975                 :             : {
    2976                 :      412402 :   for (auto sval : maybe_live_values)
    2977                 :             :     {
    2978                 :       41456 :       if (const region_svalue *ptr_sval = sval->dyn_cast_region_svalue ())
    2979                 :             :         {
    2980                 :         295 :           const region *base_reg = ptr_sval->get_pointee ()->get_base_region ();
    2981                 :         295 :           mark_as_escaped (base_reg);
    2982                 :             :         }
    2983                 :             :     }
    2984                 :      329490 : }
    2985                 :             : 
    2986                 :             : /* Remove all bindings overlapping REG within this store.  */
    2987                 :             : 
    2988                 :             : void
    2989                 :        6152 : store::clobber_region (store_manager *mgr, const region *reg)
    2990                 :             : {
    2991                 :        6152 :   const region *base_reg = reg->get_base_region ();
    2992                 :        6152 :   binding_cluster **slot = m_cluster_map.get (base_reg);
    2993                 :        6152 :   if (!slot)
    2994                 :        1240 :     return;
    2995                 :        4912 :   binding_cluster *cluster = *slot;
    2996                 :        4912 :   cluster->clobber_region (mgr, reg);
    2997                 :        4912 :   if (cluster->redundant_p ())
    2998                 :             :     {
    2999                 :        3214 :       delete cluster;
    3000                 :        3214 :       m_cluster_map.remove (base_reg);
    3001                 :             :     }
    3002                 :             : }
    3003                 :             : 
    3004                 :             : /* Remove any bindings for REG within this store.  */
    3005                 :             : 
    3006                 :             : void
    3007                 :      178736 : store::purge_region (store_manager *mgr, const region *reg)
    3008                 :             : {
    3009                 :      178736 :   const region *base_reg = reg->get_base_region ();
    3010                 :      178736 :   binding_cluster **slot = m_cluster_map.get (base_reg);
    3011                 :      178736 :   if (!slot)
    3012                 :           0 :     return;
    3013                 :      178736 :   binding_cluster *cluster = *slot;
    3014                 :      178736 :   cluster->purge_region (mgr, reg);
    3015                 :      178736 :   if (cluster->redundant_p ())
    3016                 :             :     {
    3017                 :      170708 :       delete cluster;
    3018                 :      170708 :       m_cluster_map.remove (base_reg);
    3019                 :             :     }
    3020                 :             : }
    3021                 :             : 
    3022                 :             : /* Fill REG with SVAL.  */
    3023                 :             : 
    3024                 :             : void
    3025                 :        1440 : store::fill_region (store_manager *mgr, const region *reg, const svalue *sval)
    3026                 :             : {
    3027                 :             :   /* Filling an empty region is a no-op.  */
    3028                 :        1440 :   if (reg->empty_p ())
    3029                 :             :     return;
    3030                 :             : 
    3031                 :        1412 :   const region *base_reg = reg->get_base_region ();
    3032                 :        1412 :   if (base_reg->symbolic_for_unknown_ptr_p ()
    3033                 :        1412 :       || !base_reg->tracked_p ())
    3034                 :           6 :     return;
    3035                 :        1406 :   binding_cluster *cluster = get_or_create_cluster (base_reg);
    3036                 :        1406 :   cluster->fill_region (mgr, reg, sval);
    3037                 :             : }
    3038                 :             : 
    3039                 :             : /* Zero-fill REG.  */
    3040                 :             : 
    3041                 :             : void
    3042                 :         777 : store::zero_fill_region (store_manager *mgr, const region *reg)
    3043                 :             : {
    3044                 :         777 :   region_model_manager *sval_mgr = mgr->get_svalue_manager ();
    3045                 :         777 :   const svalue *zero_sval = sval_mgr->get_or_create_int_cst (char_type_node, 0);
    3046                 :         777 :   fill_region (mgr, reg, zero_sval);
    3047                 :         777 : }
    3048                 :             : 
    3049                 :             : /* Mark REG as having unknown content.  */
    3050                 :             : 
    3051                 :             : void
    3052                 :         289 : store::mark_region_as_unknown (store_manager *mgr, const region *reg,
    3053                 :             :                                uncertainty_t *uncertainty,
    3054                 :             :                                svalue_set *maybe_live_values)
    3055                 :             : {
    3056                 :         289 :   const region *base_reg = reg->get_base_region ();
    3057                 :         289 :   if (base_reg->symbolic_for_unknown_ptr_p ()
    3058                 :         289 :       || !base_reg->tracked_p ())
    3059                 :           0 :     return;
    3060                 :         289 :   binding_cluster *cluster = get_or_create_cluster (base_reg);
    3061                 :         289 :   cluster->mark_region_as_unknown (mgr, reg, reg, uncertainty,
    3062                 :             :                                    maybe_live_values);
    3063                 :             : }
    3064                 :             : 
    3065                 :             : /* Purge state involving SVAL.  */
    3066                 :             : 
    3067                 :             : void
    3068                 :       34405 : store::purge_state_involving (const svalue *sval,
    3069                 :             :                               region_model_manager *sval_mgr)
    3070                 :             : {
    3071                 :       34405 :   auto_vec <const region *> base_regs_to_purge;
    3072                 :     1158779 :   for (auto iter : m_cluster_map)
    3073                 :             :     {
    3074                 :      562187 :       const region *base_reg = iter.first;
    3075                 :      562187 :       if (base_reg->involves_p (sval))
    3076                 :         182 :         base_regs_to_purge.safe_push (base_reg);
    3077                 :             :       else
    3078                 :             :         {
    3079                 :      562005 :           binding_cluster *cluster = iter.second;
    3080                 :      562005 :           cluster->purge_state_involving (sval, sval_mgr);
    3081                 :             :         }
    3082                 :             :     }
    3083                 :             : 
    3084                 :       34951 :   for (auto iter : base_regs_to_purge)
    3085                 :         182 :     purge_cluster (iter);
    3086                 :       34405 : }
    3087                 :             : 
    3088                 :             : /* Get the cluster for BASE_REG, or NULL (const version).  */
    3089                 :             : 
    3090                 :             : const binding_cluster *
    3091                 :     2419586 : store::get_cluster (const region *base_reg) const
    3092                 :             : {
    3093                 :     2419586 :   gcc_assert (base_reg);
    3094                 :     2419586 :   gcc_assert (base_reg->get_base_region () == base_reg);
    3095                 :     4839172 :   if (binding_cluster **slot
    3096                 :     2419586 :         = const_cast <cluster_map_t &> (m_cluster_map).get (base_reg))
    3097                 :     2299636 :     return *slot;
    3098                 :             :   else
    3099                 :             :     return NULL;
    3100                 :             : }
    3101                 :             : 
    3102                 :             : /* Get the cluster for BASE_REG, or NULL (non-const version).  */
    3103                 :             : 
    3104                 :             : binding_cluster *
    3105                 :     9065521 : store::get_cluster (const region *base_reg)
    3106                 :             : {
    3107                 :     9065521 :   gcc_assert (base_reg);
    3108                 :     9065521 :   gcc_assert (base_reg->get_base_region () == base_reg);
    3109                 :     9065521 :   if (binding_cluster **slot = m_cluster_map.get (base_reg))
    3110                 :     7693898 :     return *slot;
    3111                 :             :   else
    3112                 :             :     return NULL;
    3113                 :             : }
    3114                 :             : 
    3115                 :             : /* Get the cluster for BASE_REG, creating it if doesn't already exist.  */
    3116                 :             : 
    3117                 :             : binding_cluster *
    3118                 :     1513835 : store::get_or_create_cluster (const region *base_reg)
    3119                 :             : {
    3120                 :     1513835 :   gcc_assert (base_reg);
    3121                 :     1513835 :   gcc_assert (base_reg->get_base_region () == base_reg);
    3122                 :             : 
    3123                 :             :   /* We shouldn't create clusters for dereferencing an UNKNOWN ptr.  */
    3124                 :     1513835 :   gcc_assert (!base_reg->symbolic_for_unknown_ptr_p ());
    3125                 :             : 
    3126                 :             :   /* We shouldn't create clusters for base regions that aren't trackable.  */
    3127                 :     1513835 :   gcc_assert (base_reg->tracked_p ());
    3128                 :             : 
    3129                 :     1513835 :   if (binding_cluster **slot = m_cluster_map.get (base_reg))
    3130                 :       55525 :     return *slot;
    3131                 :             : 
    3132                 :     1458310 :   binding_cluster *cluster = new binding_cluster (base_reg);
    3133                 :     1458310 :   m_cluster_map.put (base_reg, cluster);
    3134                 :             : 
    3135                 :     1458310 :   return cluster;
    3136                 :             : }
    3137                 :             : 
    3138                 :             : /* Remove any cluster for BASE_REG, for use by
    3139                 :             :    region_model::unbind_region_and_descendents
    3140                 :             :    when popping stack frames and handling deleted heap regions.  */
    3141                 :             : 
    3142                 :             : void
    3143                 :       32816 : store::purge_cluster (const region *base_reg)
    3144                 :             : {
    3145                 :       32816 :   gcc_assert (base_reg->get_base_region () == base_reg);
    3146                 :       32816 :   binding_cluster **slot = m_cluster_map.get (base_reg);
    3147                 :       32816 :   if (!slot)
    3148                 :             :     return;
    3149                 :       32816 :   binding_cluster *cluster = *slot;
    3150                 :       65632 :   delete cluster;
    3151                 :       32816 :   m_cluster_map.remove (base_reg);
    3152                 :             : }
    3153                 :             : 
    3154                 :             : /* Attempt to merge STORE_A and STORE_B into OUT_STORE.
    3155                 :             :    Return true if successful, or false if the stores can't be merged.  */
    3156                 :             : 
    3157                 :             : bool
    3158                 :      151668 : store::can_merge_p (const store *store_a, const store *store_b,
    3159                 :             :                     store *out_store, store_manager *mgr,
    3160                 :             :                     model_merger *merger)
    3161                 :             : {
    3162                 :      151668 :   if (store_a->m_called_unknown_fn || store_b->m_called_unknown_fn)
    3163                 :       60383 :     out_store->m_called_unknown_fn = true;
    3164                 :             : 
    3165                 :             :   /* Get the union of all base regions for STORE_A and STORE_B.  */
    3166                 :      151668 :   hash_set<const region *> base_regions;
    3167                 :     1656738 :   for (cluster_map_t::iterator iter_a = store_a->m_cluster_map.begin ();
    3168                 :     3161808 :        iter_a != store_a->m_cluster_map.end (); ++iter_a)
    3169                 :             :     {
    3170                 :     1505070 :       const region *base_reg_a = (*iter_a).first;
    3171                 :     1505070 :       base_regions.add (base_reg_a);
    3172                 :             :     }
    3173                 :     1589123 :   for (cluster_map_t::iterator iter_b = store_b->m_cluster_map.begin ();
    3174                 :     3026578 :        iter_b != store_b->m_cluster_map.end (); ++iter_b)
    3175                 :             :     {
    3176                 :     1437455 :       const region *base_reg_b = (*iter_b).first;
    3177                 :     1437455 :       base_regions.add (base_reg_b);
    3178                 :             :     }
    3179                 :             : 
    3180                 :             :   /* Sort the base regions before considering them.  This ought not to
    3181                 :             :      affect the results, but can affect which types UNKNOWN_REGIONs are
    3182                 :             :      created for in a run; sorting them thus avoids minor differences
    3183                 :             :      in logfiles.  */
    3184                 :      151668 :   auto_vec<const region *> vec_base_regions (base_regions.elements ());
    3185                 :      151668 :   for (hash_set<const region *>::iterator iter = base_regions.begin ();
    3186                 :     3243008 :        iter != base_regions.end (); ++iter)
    3187                 :     1545670 :     vec_base_regions.quick_push (*iter);
    3188                 :      151668 :   vec_base_regions.qsort (region::cmp_ptr_ptr);
    3189                 :             :   unsigned i;
    3190                 :             :   const region *base_reg;
    3191                 :     1355333 :   FOR_EACH_VEC_ELT (vec_base_regions, i, base_reg)
    3192                 :             :     {
    3193                 :     1138084 :       const binding_cluster *cluster_a = store_a->get_cluster (base_reg);
    3194                 :     1138084 :       const binding_cluster *cluster_b = store_b->get_cluster (base_reg);
    3195                 :             :       /* At least one of cluster_a and cluster_b must be non-NULL.  */
    3196                 :     1138084 :       binding_cluster *out_cluster
    3197                 :     1138084 :         = out_store->get_or_create_cluster (base_reg);
    3198                 :     1138084 :       if (!binding_cluster::can_merge_p (cluster_a, cluster_b,
    3199                 :             :                                          out_cluster, out_store, mgr, merger))
    3200                 :             :         return false;
    3201                 :             :     }
    3202                 :             :   return true;
    3203                 :      151668 : }
    3204                 :             : 
    3205                 :             : /* Mark the cluster for BASE_REG as having escaped.
    3206                 :             :    For use when handling an unrecognized function call, and
    3207                 :             :    for params to "top-level" calls.
    3208                 :             :    Further unknown function calls could touch it, even if the cluster
    3209                 :             :    isn't reachable from args of those calls.  */
    3210                 :             : 
    3211                 :             : void
    3212                 :       41640 : store::mark_as_escaped (const region *base_reg)
    3213                 :             : {
    3214                 :       41640 :   gcc_assert (base_reg);
    3215                 :       41640 :   gcc_assert (base_reg->get_base_region () == base_reg);
    3216                 :             : 
    3217                 :       41640 :   if (base_reg->symbolic_for_unknown_ptr_p ()
    3218                 :       41640 :       || !base_reg->tracked_p ())
    3219                 :        5035 :     return;
    3220                 :             : 
    3221                 :       36605 :   binding_cluster *cluster = get_or_create_cluster (base_reg);
    3222                 :       36605 :   cluster->mark_as_escaped ();
    3223                 :             : }
    3224                 :             : 
    3225                 :             : /* Handle an unknown fncall by updating any clusters that have escaped
    3226                 :             :    (either in this fncall, or in a prior one).  */
    3227                 :             : 
    3228                 :             : void
    3229                 :       18527 : store::on_unknown_fncall (const gcall *call, store_manager *mgr,
    3230                 :             :                           const conjured_purge &p)
    3231                 :             : {
    3232                 :       18527 :   m_called_unknown_fn = true;
    3233                 :             : 
    3234                 :      182348 :   for (cluster_map_t::iterator iter = m_cluster_map.begin ();
    3235                 :      346169 :        iter != m_cluster_map.end (); ++iter)
    3236                 :      163821 :     (*iter).second->on_unknown_fncall (call, mgr, p);
    3237                 :       18527 : }
    3238                 :             : 
    3239                 :             : /* Return true if a non-const pointer to BASE_REG (or something within it)
    3240                 :             :    has escaped to code outside of the TU being analyzed.  */
    3241                 :             : 
    3242                 :             : bool
    3243                 :     7770093 : store::escaped_p (const region *base_reg) const
    3244                 :             : {
    3245                 :     7770093 :   gcc_assert (base_reg);
    3246                 :     7770093 :   gcc_assert (base_reg->get_base_region () == base_reg);
    3247                 :             : 
    3248                 :             :   /* "errno" can always be modified by external code.  */
    3249                 :     7770093 :   if (base_reg->get_kind () == RK_ERRNO)
    3250                 :             :     return true;
    3251                 :             : 
    3252                 :    15335660 :   if (binding_cluster **cluster_slot
    3253                 :     7667830 :       = const_cast <cluster_map_t &>(m_cluster_map).get (base_reg))
    3254                 :     7667830 :     return (*cluster_slot)->escaped_p ();
    3255                 :             :   return false;
    3256                 :             : }
    3257                 :             : 
    3258                 :             : /* Populate OUT_PVS with a list of path_vars for describing SVAL based on
    3259                 :             :    this store, using VISITED to ensure the traversal terminates.  */
    3260                 :             : 
    3261                 :             : void
    3262                 :       14167 : store::get_representative_path_vars (const region_model *model,
    3263                 :             :                                      svalue_set *visited,
    3264                 :             :                                      const svalue *sval,
    3265                 :             :                                      logger *logger,
    3266                 :             :                                      auto_vec<path_var> *out_pvs) const
    3267                 :             : {
    3268                 :       14167 :   gcc_assert (sval);
    3269                 :             : 
    3270                 :             :   /* Find all bindings that reference SVAL.  */
    3271                 :       75169 :   for (cluster_map_t::iterator iter = m_cluster_map.begin ();
    3272                 :      136171 :        iter != m_cluster_map.end (); ++iter)
    3273                 :             :     {
    3274                 :       61002 :       const region *base_reg = (*iter).first;
    3275                 :       61002 :       binding_cluster *cluster = (*iter).second;
    3276                 :       61002 :       cluster->get_representative_path_vars (model, visited, base_reg, sval,
    3277                 :             :                                              logger,
    3278                 :             :                                              out_pvs);
    3279                 :             :     }
    3280                 :             : 
    3281                 :       14167 :   if (const initial_svalue *init_sval = sval->dyn_cast_initial_svalue ())
    3282                 :             :     {
    3283                 :        2573 :       const region *reg = init_sval->get_region ();
    3284                 :        2573 :       if (path_var pv = model->get_representative_path_var (reg,
    3285                 :             :                                                             visited,
    3286                 :        2573 :                                                             logger))
    3287                 :        2451 :         out_pvs->safe_push (pv);
    3288                 :             :     }
    3289                 :       14167 : }
    3290                 :             : 
    3291                 :             : /* Remove all bindings overlapping REG within this store, removing
    3292                 :             :    any clusters that become redundant.
    3293                 :             : 
    3294                 :             :    If UNCERTAINTY is non-NULL, use it to record any svalues that
    3295                 :             :    were removed, as being maybe-bound.  */
    3296                 :             : 
    3297                 :             : void
    3298                 :      329201 : store::remove_overlapping_bindings (store_manager *mgr, const region *reg,
    3299                 :             :                                     uncertainty_t *uncertainty)
    3300                 :             : {
    3301                 :      329201 :   const region *base_reg = reg->get_base_region ();
    3302                 :      329201 :   if (binding_cluster **cluster_slot = m_cluster_map.get (base_reg))
    3303                 :             :     {
    3304                 :       51301 :       binding_cluster *cluster = *cluster_slot;
    3305                 :       51301 :       if (reg == base_reg && !escaped_p (base_reg))
    3306                 :             :         {
    3307                 :             :           /* Remove whole cluster.  */
    3308                 :       30763 :           m_cluster_map.remove (base_reg);
    3309                 :       61526 :           delete cluster;
    3310                 :       30763 :           return;
    3311                 :             :         }
    3312                 :             :       /* Pass NULL for the maybe_live_values here, as we don't want to
    3313                 :             :          record the old svalues as being maybe-bound.  */
    3314                 :       20538 :       cluster->remove_overlapping_bindings (mgr, reg, uncertainty, NULL);
    3315                 :             :     }
    3316                 :             : }
    3317                 :             : 
    3318                 :             : /* Subclass of visitor that accumulates a hash_set of the regions that
    3319                 :             :    were visited.  */
    3320                 :             : 
    3321                 :     2039190 : struct region_finder : public visitor
    3322                 :             : {
    3323                 :    18066351 :   void visit_region (const region *reg) final override
    3324                 :             :   {
    3325                 :    18066351 :     m_regs.add (reg);
    3326                 :    18066351 :   }
    3327                 :             : 
    3328                 :             :   hash_set<const region *> m_regs;
    3329                 :             : };
    3330                 :             : 
    3331                 :             : /* Canonicalize this store, to maximize the chance of equality between
    3332                 :             :    instances.  */
    3333                 :             : 
    3334                 :             : void
    3335                 :     1019595 : store::canonicalize (store_manager *mgr)
    3336                 :             : {
    3337                 :             :   /* If we have e.g.:
    3338                 :             :          cluster for: HEAP_ALLOCATED_REGION(543)
    3339                 :             :            ESCAPED
    3340                 :             :            TOUCHED
    3341                 :             :      where the heap region is empty and unreferenced, then purge that
    3342                 :             :      cluster, to avoid unbounded state chains involving these.  */
    3343                 :             : 
    3344                 :             :   /* Find regions that are referenced by bound values in the store.  */
    3345                 :     1019595 :   region_finder s;
    3346                 :     1019595 :   for (cluster_map_t::iterator iter = m_cluster_map.begin ();
    3347                 :    12431719 :        iter != m_cluster_map.end (); ++iter)
    3348                 :             :     {
    3349                 :     5706062 :       binding_cluster *cluster = (*iter).second;
    3350                 :    11698846 :       for (binding_cluster::iterator_t bind_iter = cluster->m_map.begin ();
    3351                 :    23397692 :            bind_iter != cluster->m_map.end (); ++bind_iter)
    3352                 :     5992784 :         (*bind_iter).second->accept (&s);
    3353                 :             :     }
    3354                 :             : 
    3355                 :             :   /* Locate heap-allocated regions that have empty bindings that weren't
    3356                 :             :      found above.  */
    3357                 :     1019595 :   hash_set<const region *> purgeable_regions;
    3358                 :     6725657 :   for (cluster_map_t::iterator iter = m_cluster_map.begin ();
    3359                 :    12431719 :        iter != m_cluster_map.end (); ++iter)
    3360                 :             :     {
    3361                 :     5706062 :       const region *base_reg = (*iter).first;
    3362                 :     5706062 :       binding_cluster *cluster = (*iter).second;
    3363                 :     5706062 :       if (base_reg->get_kind () == RK_HEAP_ALLOCATED)
    3364                 :             :         {
    3365                 :             :           /* Don't purge a heap-allocated region that's been marked as
    3366                 :             :              escaping, since this could be recording that a ptr to it
    3367                 :             :              was written to an unknown symbolic region along this
    3368                 :             :              path, and so we don't know whether it's referenced or
    3369                 :             :              not, and hence should report it as leaking
    3370                 :             :              (PR analyzer/106473).  */
    3371                 :      478112 :           if (cluster->escaped_p ())
    3372                 :      251520 :             continue;
    3373                 :             : 
    3374                 :      226592 :           if (cluster->empty_p ())
    3375                 :         612 :             if (!s.m_regs.contains (base_reg))
    3376                 :           0 :               purgeable_regions.add (base_reg);
    3377                 :             : 
    3378                 :             :           /* Also cover the UNKNOWN case.  */
    3379                 :      226592 :           if (const svalue *sval = cluster->maybe_get_simple_value (mgr))
    3380                 :       44408 :             if (sval->get_kind () == SK_UNKNOWN)
    3381                 :       32311 :               if (!s.m_regs.contains (base_reg))
    3382                 :          36 :                 purgeable_regions.add (base_reg);
    3383                 :             :         }
    3384                 :             :     }
    3385                 :             : 
    3386                 :             :   /* Purge them.  */
    3387                 :     1019631 :   for (hash_set<const region *>::iterator iter = purgeable_regions.begin ();
    3388                 :     2039262 :        iter != purgeable_regions.end (); ++iter)
    3389                 :             :     {
    3390                 :          36 :       const region *base_reg = *iter;
    3391                 :          36 :       purge_cluster (base_reg);
    3392                 :             :     }
    3393                 :     1019595 : }
    3394                 :             : 
    3395                 :             : /* Subroutine for use by exploded_path::feasible_p.
    3396                 :             : 
    3397                 :             :    We need to deal with state differences between:
    3398                 :             :    (a) when the exploded_graph is being initially constructed and
    3399                 :             :    (b) when replaying the state changes along a specific path in
    3400                 :             :    in exploded_path::feasible_p.
    3401                 :             : 
    3402                 :             :    In (a), state merging happens, so when exploring a loop
    3403                 :             :      for (i = 0; i < 1024; i++)
    3404                 :             :    on successive iterations we have i == 0, then i == WIDENING.
    3405                 :             : 
    3406                 :             :    In (b), no state merging happens, so naively replaying the path
    3407                 :             :    that goes twice through the loop then exits it
    3408                 :             :    would lead to i == 0, then i == 1, and then a (i >= 1024) eedge
    3409                 :             :    that exits the loop, which would be found to be infeasible as i == 1,
    3410                 :             :    and the path would be rejected.
    3411                 :             : 
    3412                 :             :    We need to fix up state during replay.  This subroutine is
    3413                 :             :    called whenever we enter a supernode that we've already
    3414                 :             :    visited along this exploded_path, passing in OTHER_STORE
    3415                 :             :    from the destination enode's state.
    3416                 :             : 
    3417                 :             :    Find bindings to widening values in OTHER_STORE.
    3418                 :             :    For all that are found, update the binding in this store to UNKNOWN.  */
    3419                 :             : 
    3420                 :             : void
    3421                 :        9119 : store::loop_replay_fixup (const store *other_store,
    3422                 :             :                           region_model_manager *mgr)
    3423                 :             : {
    3424                 :        9119 :   gcc_assert (other_store);
    3425                 :        9119 :   for (cluster_map_t::iterator iter = other_store->m_cluster_map.begin ();
    3426                 :      155993 :        iter != other_store->m_cluster_map.end (); ++iter)
    3427                 :             :     {
    3428                 :       73437 :       const region *base_reg = (*iter).first;
    3429                 :       73437 :       binding_cluster *cluster = (*iter).second;
    3430                 :      157917 :       for (binding_cluster::iterator_t bind_iter = cluster->m_map.begin ();
    3431                 :      315834 :            bind_iter != cluster->m_map.end (); ++bind_iter)
    3432                 :             :         {
    3433                 :       84480 :           const binding_key *key = (*bind_iter).first;
    3434                 :       84480 :           const svalue *sval = (*bind_iter).second;
    3435                 :       84480 :           if (sval->get_kind () == SK_WIDENING)
    3436                 :             :             {
    3437                 :        1819 :               binding_cluster *this_cluster
    3438                 :        1819 :                 = get_or_create_cluster (base_reg);
    3439                 :        1819 :               const svalue *unknown
    3440                 :        1819 :                 = mgr->get_or_create_unknown_svalue (sval->get_type ());
    3441                 :        1819 :               this_cluster->bind_key (key, unknown);
    3442                 :             :             }
    3443                 :             :         }
    3444                 :             :     }
    3445                 :        9119 : }
    3446                 :             : 
    3447                 :             : /* Use R to replay the bindings from SUMMARY into this object.  */
    3448                 :             : 
    3449                 :             : void
    3450                 :        1598 : store::replay_call_summary (call_summary_replay &r,
    3451                 :             :                             const store &summary)
    3452                 :             : {
    3453                 :        1598 :   if (summary.m_called_unknown_fn)
    3454                 :             :     {
    3455                 :             :       /* A call to an external function occurred in the summary.
    3456                 :             :          Hence we need to invalidate our knownledge of globals,
    3457                 :             :          escaped regions, etc.  */
    3458                 :          67 :       on_unknown_fncall (r.get_call_stmt (),
    3459                 :             :                          r.get_store_manager (),
    3460                 :          67 :                          conjured_purge (r.get_caller_model (),
    3461                 :          67 :                                          r.get_ctxt ()));
    3462                 :             :     }
    3463                 :             : 
    3464                 :        1598 :   auto_vec<const region *> keys (summary.m_cluster_map.elements ());
    3465                 :       16038 :   for (auto kv : summary.m_cluster_map)
    3466                 :       14440 :     keys.quick_push (kv.first);
    3467                 :        1598 :   keys.qsort (region::cmp_ptr_ptr);
    3468                 :       19178 :   for (auto base_reg : keys)
    3469                 :       14440 :     replay_call_summary_cluster (r, summary, base_reg);
    3470                 :        1598 : }
    3471                 :             : 
    3472                 :             : /* Use R and SUMMARY to replay the bindings in SUMMARY_CLUSTER
    3473                 :             :    into this object.  */
    3474                 :             : 
    3475                 :             : void
    3476                 :       14440 : store::replay_call_summary_cluster (call_summary_replay &r,
    3477                 :             :                                     const store &summary,
    3478                 :             :                                     const region *summary_base_reg)
    3479                 :             : {
    3480                 :       14440 :   const call_details &cd = r.get_call_details ();
    3481                 :       14440 :   region_model_manager *reg_mgr = r.get_manager ();
    3482                 :       14440 :   store_manager *mgr = reg_mgr->get_store_manager ();
    3483                 :       14440 :   const binding_cluster *summary_cluster
    3484                 :       14440 :     = summary.get_cluster (summary_base_reg);
    3485                 :             : 
    3486                 :             :   /* Handle "ESCAPED" and "TOUCHED" flags.  */
    3487                 :       14440 :   if (summary_cluster->escaped_p () || summary_cluster->touched_p ())
    3488                 :        9458 :     if (const region *caller_reg
    3489                 :        4729 :         = r.convert_region_from_summary (summary_base_reg))
    3490                 :             :       {
    3491                 :        4720 :         const region *caller_base_reg = caller_reg->get_base_region ();
    3492                 :        4720 :         if (caller_base_reg->tracked_p ()
    3493                 :        4720 :             && !caller_base_reg->symbolic_for_unknown_ptr_p ())
    3494                 :             :           {
    3495                 :        3690 :             binding_cluster *caller_cluster
    3496                 :        3690 :               = get_or_create_cluster (caller_base_reg);
    3497                 :        3690 :             if (summary_cluster->escaped_p ())
    3498                 :        2869 :               caller_cluster->mark_as_escaped ();
    3499                 :        3690 :             if (summary_cluster->touched_p ())
    3500                 :        2266 :               caller_cluster->m_touched = true;
    3501                 :             :           }
    3502                 :             :       }
    3503                 :             : 
    3504                 :       14440 :   switch (summary_base_reg->get_kind ())
    3505                 :             :     {
    3506                 :             :     /* Top-level regions.  */
    3507                 :           0 :     case RK_FRAME:
    3508                 :           0 :     case RK_GLOBALS:
    3509                 :           0 :     case RK_CODE:
    3510                 :           0 :     case RK_STACK:
    3511                 :           0 :     case RK_HEAP:
    3512                 :           0 :     case RK_THREAD_LOCAL:
    3513                 :           0 :     case RK_ROOT:
    3514                 :             :     /* Child regions.  */
    3515                 :           0 :     case RK_FIELD:
    3516                 :           0 :     case RK_ELEMENT:
    3517                 :           0 :     case RK_OFFSET:
    3518                 :           0 :     case RK_SIZED:
    3519                 :           0 :     case RK_CAST:
    3520                 :           0 :     case RK_BIT_RANGE:
    3521                 :             :     /* Other regions.  */
    3522                 :           0 :     case RK_VAR_ARG:
    3523                 :           0 :     case RK_UNKNOWN:
    3524                 :             :       /* These should never be the base region of a binding cluster.  */
    3525                 :           0 :       gcc_unreachable ();
    3526                 :             :       break;
    3527                 :             : 
    3528                 :             :     case RK_FUNCTION:
    3529                 :             :     case RK_LABEL:
    3530                 :             :     case RK_STRING:
    3531                 :             :       /* These can be marked as escaping.  */
    3532                 :             :       break;
    3533                 :             : 
    3534                 :        3321 :     case RK_SYMBOLIC:
    3535                 :        3321 :       {
    3536                 :        3321 :         const symbolic_region *summary_symbolic_reg
    3537                 :        3321 :           = as_a <const symbolic_region *> (summary_base_reg);
    3538                 :        3321 :         const svalue *summary_ptr_sval = summary_symbolic_reg->get_pointer ();
    3539                 :        3321 :         const svalue *caller_ptr_sval
    3540                 :        3321 :           = r.convert_svalue_from_summary (summary_ptr_sval);
    3541                 :        3321 :         if (!caller_ptr_sval)
    3542                 :             :           return;
    3543                 :        2776 :         const region *caller_dest_reg
    3544                 :        2776 :           = cd.get_model ()->deref_rvalue (caller_ptr_sval,
    3545                 :             :                                            NULL_TREE,
    3546                 :             :                                            cd.get_ctxt ());
    3547                 :        2776 :         const svalue *summary_sval
    3548                 :        2776 :           = summary.get_any_binding (mgr, summary_base_reg);
    3549                 :        2776 :         if (!summary_sval)
    3550                 :             :           return;
    3551                 :        2508 :         const svalue *caller_sval
    3552                 :        2508 :           = r.convert_svalue_from_summary (summary_sval);
    3553                 :        2508 :         if (!caller_sval)
    3554                 :           2 :           caller_sval =
    3555                 :           2 :             reg_mgr->get_or_create_unknown_svalue (summary_sval->get_type ());
    3556                 :        2508 :         set_value (mgr, caller_dest_reg,
    3557                 :             :                    caller_sval, NULL /* uncertainty_t * */);
    3558                 :             :       }
    3559                 :        2508 :       break;
    3560                 :             : 
    3561                 :       11114 :     case RK_HEAP_ALLOCATED:
    3562                 :       11114 :     case RK_DECL:
    3563                 :       11114 :     case RK_ERRNO:
    3564                 :       11114 :     case RK_PRIVATE:
    3565                 :       11114 :       {
    3566                 :       11114 :         const region *caller_dest_reg
    3567                 :       11114 :           = r.convert_region_from_summary (summary_base_reg);
    3568                 :       11114 :         if (!caller_dest_reg)
    3569                 :             :           return;
    3570                 :       10885 :         const svalue *summary_sval
    3571                 :       10885 :           = summary.get_any_binding (mgr, summary_base_reg);
    3572                 :       10885 :         if (!summary_sval)
    3573                 :         206 :           summary_sval = reg_mgr->get_or_create_compound_svalue
    3574                 :         206 :             (summary_base_reg->get_type (),
    3575                 :             :              summary_cluster->get_map ());
    3576                 :       10885 :         const svalue *caller_sval
    3577                 :       10885 :           = r.convert_svalue_from_summary (summary_sval);
    3578                 :       10885 :         if (!caller_sval)
    3579                 :           2 :           caller_sval =
    3580                 :           2 :             reg_mgr->get_or_create_unknown_svalue (summary_sval->get_type ());
    3581                 :       10885 :         set_value (mgr, caller_dest_reg,
    3582                 :             :                    caller_sval, NULL /* uncertainty_t * */);
    3583                 :             :       }
    3584                 :       10885 :       break;
    3585                 :             : 
    3586                 :             :     case RK_ALLOCA:
    3587                 :             :       /* Ignore bindings of alloca regions in the summary.  */
    3588                 :             :       break;
    3589                 :             :     }
    3590                 :             : }
    3591                 :             : 
    3592                 :             : #if CHECKING_P
    3593                 :             : 
    3594                 :             : namespace selftest {
    3595                 :             : 
    3596                 :             : /* Verify that bit_range::intersects_p works as expected.  */
    3597                 :             : 
    3598                 :             : static void
    3599                 :           4 : test_bit_range_intersects_p ()
    3600                 :             : {
    3601                 :           4 :   bit_range b0 (0, 1);
    3602                 :           4 :   bit_range b1 (1, 1);
    3603                 :           4 :   bit_range b2 (2, 1);
    3604                 :           4 :   bit_range b3 (3, 1);
    3605                 :           4 :   bit_range b4 (4, 1);
    3606                 :           4 :   bit_range b5 (5, 1);
    3607                 :           4 :   bit_range b6 (6, 1);
    3608                 :           4 :   bit_range b7 (7, 1);
    3609                 :           4 :   bit_range b1_to_6 (1, 6);
    3610                 :           4 :   bit_range b0_to_7 (0, 8);
    3611                 :           4 :   bit_range b3_to_5 (3, 3);
    3612                 :           4 :   bit_range b6_to_7 (6, 2);
    3613                 :             : 
    3614                 :             :   /* self-intersection is true.  */
    3615                 :           4 :   ASSERT_TRUE (b0.intersects_p (b0));
    3616                 :           4 :   ASSERT_TRUE (b7.intersects_p (b7));
    3617                 :           4 :   ASSERT_TRUE (b1_to_6.intersects_p (b1_to_6));
    3618                 :           4 :   ASSERT_TRUE (b0_to_7.intersects_p (b0_to_7));
    3619                 :             : 
    3620                 :           4 :   ASSERT_FALSE (b0.intersects_p (b1));
    3621                 :           4 :   ASSERT_FALSE (b1.intersects_p (b0));
    3622                 :           4 :   ASSERT_FALSE (b0.intersects_p (b7));
    3623                 :           4 :   ASSERT_FALSE (b7.intersects_p (b0));
    3624                 :             : 
    3625                 :           4 :   ASSERT_TRUE (b0_to_7.intersects_p (b0));
    3626                 :           4 :   ASSERT_TRUE (b0_to_7.intersects_p (b7));
    3627                 :           4 :   ASSERT_TRUE (b0.intersects_p (b0_to_7));
    3628                 :           4 :   ASSERT_TRUE (b7.intersects_p (b0_to_7));
    3629                 :             : 
    3630                 :           4 :   ASSERT_FALSE (b0.intersects_p (b1_to_6));
    3631                 :           4 :   ASSERT_FALSE (b1_to_6.intersects_p (b0));
    3632                 :           4 :   ASSERT_TRUE (b1.intersects_p (b1_to_6));
    3633                 :           4 :   ASSERT_TRUE (b1_to_6.intersects_p (b1));
    3634                 :           4 :   ASSERT_TRUE (b1_to_6.intersects_p (b6));
    3635                 :           4 :   ASSERT_FALSE (b1_to_6.intersects_p (b7));
    3636                 :             : 
    3637                 :           4 :   ASSERT_TRUE (b1_to_6.intersects_p (b0_to_7));
    3638                 :           4 :   ASSERT_TRUE (b0_to_7.intersects_p (b1_to_6));
    3639                 :             : 
    3640                 :           4 :   ASSERT_FALSE (b3_to_5.intersects_p (b6_to_7));
    3641                 :           4 :   ASSERT_FALSE (b6_to_7.intersects_p (b3_to_5));
    3642                 :             : 
    3643                 :           4 :   bit_range r1 (0,0);
    3644                 :           4 :   bit_range r2 (0,0);
    3645                 :           4 :   ASSERT_TRUE (b1_to_6.intersects_p (b0_to_7, &r1, &r2));
    3646                 :           4 :   ASSERT_EQ (r1.get_start_bit_offset (), 0);
    3647                 :           4 :   ASSERT_EQ (r1.m_size_in_bits, 6);
    3648                 :           4 :   ASSERT_EQ (r2.get_start_bit_offset (), 1);
    3649                 :           4 :   ASSERT_EQ (r2.m_size_in_bits, 6);
    3650                 :             : 
    3651                 :           4 :   ASSERT_TRUE (b0_to_7.intersects_p (b1_to_6, &r1, &r2));
    3652                 :           4 :   ASSERT_EQ (r1.get_start_bit_offset (), 1);
    3653                 :           4 :   ASSERT_EQ (r1.m_size_in_bits, 6);
    3654                 :           4 :   ASSERT_EQ (r2.get_start_bit_offset (), 0);
    3655                 :           4 :   ASSERT_EQ (r2.m_size_in_bits, 6);
    3656                 :           4 : }
    3657                 :             : 
    3658                 :             : /* Implementation detail of ASSERT_BIT_RANGE_FROM_MASK_EQ.  */
    3659                 :             : 
    3660                 :             : static void
    3661                 :          76 : assert_bit_range_from_mask_eq (const location &loc,
    3662                 :             :                                unsigned HOST_WIDE_INT mask,
    3663                 :             :                                const bit_range &expected)
    3664                 :             : {
    3665                 :          76 :   bit_range actual (0, 0);
    3666                 :          76 :   bool ok = bit_range::from_mask (mask, &actual);
    3667                 :          76 :   ASSERT_TRUE_AT (loc, ok);
    3668                 :          76 :   ASSERT_EQ_AT (loc, actual, expected);
    3669                 :          76 : }
    3670                 :             : 
    3671                 :             : /* Assert that bit_range::from_mask (MASK) returns true, and writes
    3672                 :             :    out EXPECTED_BIT_RANGE.  */
    3673                 :             : 
    3674                 :             : #define ASSERT_BIT_RANGE_FROM_MASK_EQ(MASK, EXPECTED_BIT_RANGE) \
    3675                 :             :   SELFTEST_BEGIN_STMT                                                   \
    3676                 :             :   assert_bit_range_from_mask_eq (SELFTEST_LOCATION, MASK,               \
    3677                 :             :                                  EXPECTED_BIT_RANGE);                   \
    3678                 :             :   SELFTEST_END_STMT
    3679                 :             : 
    3680                 :             : /* Implementation detail of ASSERT_NO_BIT_RANGE_FROM_MASK.  */
    3681                 :             : 
    3682                 :             : static void
    3683                 :          12 : assert_no_bit_range_from_mask_eq (const location &loc,
    3684                 :             :                                   unsigned HOST_WIDE_INT mask)
    3685                 :             : {
    3686                 :          12 :   bit_range actual (0, 0);
    3687                 :          12 :   bool ok = bit_range::from_mask (mask, &actual);
    3688                 :          12 :   ASSERT_FALSE_AT (loc, ok);
    3689                 :          12 : }
    3690                 :             : 
    3691                 :             : /* Assert that bit_range::from_mask (MASK) returns false.  */
    3692                 :             : 
    3693                 :             : #define ASSERT_NO_BIT_RANGE_FROM_MASK(MASK) \
    3694                 :             :   SELFTEST_BEGIN_STMT                                                   \
    3695                 :             :   assert_no_bit_range_from_mask_eq (SELFTEST_LOCATION, MASK);           \
    3696                 :             :   SELFTEST_END_STMT
    3697                 :             : 
    3698                 :             : /* Verify that bit_range::from_mask works as expected.  */
    3699                 :             : 
    3700                 :             : static void
    3701                 :           4 : test_bit_range_from_mask ()
    3702                 :             : {
    3703                 :             :   /* Should fail on zero.  */
    3704                 :           4 :   ASSERT_NO_BIT_RANGE_FROM_MASK (0);
    3705                 :             : 
    3706                 :             :   /* Verify 1-bit masks.  */
    3707                 :           4 :   ASSERT_BIT_RANGE_FROM_MASK_EQ (1, bit_range (0, 1));
    3708                 :           4 :   ASSERT_BIT_RANGE_FROM_MASK_EQ (2, bit_range (1, 1));
    3709                 :           4 :   ASSERT_BIT_RANGE_FROM_MASK_EQ (4, bit_range (2, 1));
    3710                 :           4 :   ASSERT_BIT_RANGE_FROM_MASK_EQ (8, bit_range (3, 1));
    3711                 :           4 :   ASSERT_BIT_RANGE_FROM_MASK_EQ (16, bit_range (4, 1));
    3712                 :           4 :   ASSERT_BIT_RANGE_FROM_MASK_EQ (32, bit_range (5, 1));
    3713                 :           4 :   ASSERT_BIT_RANGE_FROM_MASK_EQ (64, bit_range (6, 1));
    3714                 :           4 :   ASSERT_BIT_RANGE_FROM_MASK_EQ (128, bit_range (7, 1));
    3715                 :             : 
    3716                 :             :   /* Verify N-bit masks starting at bit 0.  */
    3717                 :           4 :   ASSERT_BIT_RANGE_FROM_MASK_EQ (3, bit_range (0, 2));
    3718                 :           4 :   ASSERT_BIT_RANGE_FROM_MASK_EQ (7, bit_range (0, 3));
    3719                 :           4 :   ASSERT_BIT_RANGE_FROM_MASK_EQ (15, bit_range (0, 4));
    3720                 :           4 :   ASSERT_BIT_RANGE_FROM_MASK_EQ (31, bit_range (0, 5));
    3721                 :           4 :   ASSERT_BIT_RANGE_FROM_MASK_EQ (63, bit_range (0, 6));
    3722                 :           4 :   ASSERT_BIT_RANGE_FROM_MASK_EQ (127, bit_range (0, 7));
    3723                 :           4 :   ASSERT_BIT_RANGE_FROM_MASK_EQ (255, bit_range (0, 8));
    3724                 :           4 :   ASSERT_BIT_RANGE_FROM_MASK_EQ (0xffff, bit_range (0, 16));
    3725                 :             : 
    3726                 :             :   /* Various other tests. */
    3727                 :           4 :   ASSERT_BIT_RANGE_FROM_MASK_EQ (0x30, bit_range (4, 2));
    3728                 :           4 :   ASSERT_BIT_RANGE_FROM_MASK_EQ (0x700, bit_range (8, 3));
    3729                 :           4 :   ASSERT_BIT_RANGE_FROM_MASK_EQ (0x600, bit_range (9, 2));
    3730                 :             : 
    3731                 :             :   /* Multiple ranges of set bits should fail.  */
    3732                 :           4 :   ASSERT_NO_BIT_RANGE_FROM_MASK (0x101);
    3733                 :           4 :   ASSERT_NO_BIT_RANGE_FROM_MASK (0xf0f0f0f0);
    3734                 :           4 : }
    3735                 :             : 
    3736                 :             : /* Implementation detail of ASSERT_OVERLAP.  */
    3737                 :             : 
    3738                 :             : static void
    3739                 :          56 : assert_overlap (const location &loc,
    3740                 :             :                 const concrete_binding *b1,
    3741                 :             :                 const concrete_binding *b2)
    3742                 :             : {
    3743                 :          56 :   ASSERT_TRUE_AT (loc, b1->overlaps_p (*b2));
    3744                 :          56 :   ASSERT_TRUE_AT (loc, b2->overlaps_p (*b1));
    3745                 :          56 : }
    3746                 :             : 
    3747                 :             : /* Implementation detail of ASSERT_DISJOINT.  */
    3748                 :             : 
    3749                 :             : static void
    3750                 :          20 : assert_disjoint (const location &loc,
    3751                 :             :                  const concrete_binding *b1,
    3752                 :             :                  const concrete_binding *b2)
    3753                 :             : {
    3754                 :          20 :   ASSERT_FALSE_AT (loc, b1->overlaps_p (*b2));
    3755                 :          20 :   ASSERT_FALSE_AT (loc, b2->overlaps_p (*b1));
    3756                 :          20 : }
    3757                 :             : 
    3758                 :             : /* Assert that B1 and B2 overlap, checking both ways.  */
    3759                 :             : 
    3760                 :             : #define ASSERT_OVERLAP(B1, B2) \
    3761                 :             :   SELFTEST_BEGIN_STMT                           \
    3762                 :             :   assert_overlap (SELFTEST_LOCATION, B1, B2);   \
    3763                 :             :   SELFTEST_END_STMT
    3764                 :             : 
    3765                 :             : /* Assert that B1 and B2 do not overlap, checking both ways.  */
    3766                 :             : 
    3767                 :             : #define ASSERT_DISJOINT(B1, B2) \
    3768                 :             :   SELFTEST_BEGIN_STMT                           \
    3769                 :             :   assert_disjoint (SELFTEST_LOCATION, B1, B2);  \
    3770                 :             :   SELFTEST_END_STMT
    3771                 :             : 
    3772                 :             : /* Verify that concrete_binding::overlaps_p works as expected.  */
    3773                 :             : 
    3774                 :             : static void
    3775                 :           4 : test_binding_key_overlap ()
    3776                 :             : {
    3777                 :           4 :   store_manager mgr (NULL);
    3778                 :             : 
    3779                 :             :   /* Various 8-bit bindings.  */
    3780                 :           4 :   const concrete_binding *cb_0_7 = mgr.get_concrete_binding (0, 8);
    3781                 :           4 :   const concrete_binding *cb_8_15 = mgr.get_concrete_binding (8, 8);
    3782                 :           4 :   const concrete_binding *cb_16_23 = mgr.get_concrete_binding (16, 8);
    3783                 :           4 :   const concrete_binding *cb_24_31 = mgr.get_concrete_binding (24, 8);
    3784                 :             : 
    3785                 :             :   /* 16-bit bindings.  */
    3786                 :           4 :   const concrete_binding *cb_0_15 = mgr.get_concrete_binding (0, 16);
    3787                 :           4 :   const concrete_binding *cb_8_23 = mgr.get_concrete_binding (8, 16);
    3788                 :           4 :   const concrete_binding *cb_16_31 = mgr.get_concrete_binding (16, 16);
    3789                 :             : 
    3790                 :             :   /* 32-bit binding.  */
    3791                 :           4 :   const concrete_binding *cb_0_31 = mgr.get_concrete_binding (0, 32);
    3792                 :             : 
    3793                 :             :   /* Everything should self-overlap.  */
    3794                 :           4 :   ASSERT_OVERLAP (cb_0_7, cb_0_7);
    3795                 :           4 :   ASSERT_OVERLAP (cb_8_15, cb_8_15);
    3796                 :           4 :   ASSERT_OVERLAP (cb_16_23, cb_16_23);
    3797                 :           4 :   ASSERT_OVERLAP (cb_24_31, cb_24_31);
    3798                 :           4 :   ASSERT_OVERLAP (cb_0_15, cb_0_15);
    3799                 :           4 :   ASSERT_OVERLAP (cb_8_23, cb_8_23);
    3800                 :           4 :   ASSERT_OVERLAP (cb_16_31, cb_16_31);
    3801                 :           4 :   ASSERT_OVERLAP (cb_0_31, cb_0_31);
    3802                 :             : 
    3803                 :             :   /* Verify the 8-bit bindings that don't overlap each other.  */
    3804                 :           4 :   ASSERT_DISJOINT (cb_0_7, cb_8_15);
    3805                 :           4 :   ASSERT_DISJOINT (cb_8_15, cb_16_23);
    3806                 :             : 
    3807                 :             :   /* Check for overlap of differently-sized bindings.  */
    3808                 :           4 :   ASSERT_OVERLAP (cb_0_7, cb_0_31);
    3809                 :             :   /* ...and with differing start points.  */
    3810                 :           4 :   ASSERT_OVERLAP (cb_8_15, cb_0_31);
    3811                 :           4 :   ASSERT_DISJOINT (cb_8_15, cb_16_31);
    3812                 :           4 :   ASSERT_OVERLAP (cb_16_23, cb_0_31);
    3813                 :           4 :   ASSERT_OVERLAP (cb_16_31, cb_0_31);
    3814                 :             : 
    3815                 :           4 :   ASSERT_DISJOINT (cb_0_7, cb_8_23);
    3816                 :           4 :   ASSERT_OVERLAP (cb_8_23, cb_16_23);
    3817                 :           4 :   ASSERT_OVERLAP (cb_8_23, cb_16_31);
    3818                 :           4 :   ASSERT_DISJOINT (cb_8_23, cb_24_31);
    3819                 :           4 : }
    3820                 :             : 
    3821                 :             : /* Run all of the selftests within this file.  */
    3822                 :             : 
    3823                 :             : void
    3824                 :           4 : analyzer_store_cc_tests ()
    3825                 :             : {
    3826                 :           4 :   test_bit_range_intersects_p ();
    3827                 :           4 :   test_bit_range_from_mask ();
    3828                 :           4 :   test_binding_key_overlap ();
    3829                 :           4 : }
    3830                 :             : 
    3831                 :             : } // namespace selftest
    3832                 :             : 
    3833                 :             : #endif /* CHECKING_P */
    3834                 :             : 
    3835                 :             : } // namespace ana
    3836                 :             : 
    3837                 :             : #endif /* #if ENABLE_ANALYZER */
        

Generated by: LCOV version 2.1-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.