LCOV - code coverage report
Current view: top level - gcc/analyzer - program-state.cc (source / functions) Hit Total Coverage
Test: gcc.info Lines: 617 709 87.0 %
Date: 2020-03-28 11:57:23 Functions: 54 62 87.1 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Classes for representing the state of interest at a given path of analysis.
       2                 :            :    Copyright (C) 2019-2020 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                 :            : #include "system.h"
      23                 :            : #include "coretypes.h"
      24                 :            : #include "tree.h"
      25                 :            : #include "diagnostic-core.h"
      26                 :            : #include "diagnostic.h"
      27                 :            : #include "function.h"
      28                 :            : #include "analyzer/analyzer.h"
      29                 :            : #include "analyzer/analyzer-logging.h"
      30                 :            : #include "analyzer/sm.h"
      31                 :            : #include "sbitmap.h"
      32                 :            : #include "tristate.h"
      33                 :            : #include "ordered-hash-map.h"
      34                 :            : #include "selftest.h"
      35                 :            : #include "analyzer/region-model.h"
      36                 :            : #include "analyzer/program-state.h"
      37                 :            : #include "analyzer/constraint-manager.h"
      38                 :            : #include "alloc-pool.h"
      39                 :            : #include "fibonacci_heap.h"
      40                 :            : #include "shortest-paths.h"
      41                 :            : #include "analyzer/constraint-manager.h"
      42                 :            : #include "diagnostic-event-id.h"
      43                 :            : #include "analyzer/pending-diagnostic.h"
      44                 :            : #include "analyzer/diagnostic-manager.h"
      45                 :            : #include "cfg.h"
      46                 :            : #include "basic-block.h"
      47                 :            : #include "gimple.h"
      48                 :            : #include "gimple-iterator.h"
      49                 :            : #include "cgraph.h"
      50                 :            : #include "digraph.h"
      51                 :            : #include "analyzer/supergraph.h"
      52                 :            : #include "analyzer/call-string.h"
      53                 :            : #include "analyzer/program-point.h"
      54                 :            : #include "analyzer/program-state.h"
      55                 :            : #include "analyzer/exploded-graph.h"
      56                 :            : #include "analyzer/state-purge.h"
      57                 :            : #include "analyzer/analyzer-selftests.h"
      58                 :            : 
      59                 :            : #if ENABLE_ANALYZER
      60                 :            : 
      61                 :            : namespace ana {
      62                 :            : 
      63                 :            : /* class extrinsic_state.  */
      64                 :            : 
      65                 :            : /* Dump a multiline representation of this state to PP.  */
      66                 :            : 
      67                 :            : void
      68                 :          0 : extrinsic_state::dump_to_pp (pretty_printer *pp) const
      69                 :            : {
      70                 :          0 :   pp_printf (pp, "extrinsic_state: %i checker(s)\n", get_num_checkers ());
      71                 :          0 :   unsigned i;
      72                 :          0 :   state_machine *checker;
      73                 :          0 :   FOR_EACH_VEC_ELT (m_checkers, i, checker)
      74                 :            :     {
      75                 :          0 :       pp_printf (pp, "m_checkers[%i]: %qs\n", i, checker->get_name ());
      76                 :          0 :       checker->dump_to_pp (pp);
      77                 :            :     }
      78                 :          0 : }
      79                 :            : 
      80                 :            : /* Dump a multiline representation of this state to OUTF.  */
      81                 :            : 
      82                 :            : void
      83                 :          0 : extrinsic_state::dump_to_file (FILE *outf) const
      84                 :            : {
      85                 :          0 :   pretty_printer pp;
      86                 :          0 :   if (outf == stderr)
      87                 :          0 :     pp_show_color (&pp) = pp_show_color (global_dc->printer);
      88                 :          0 :   pp.buffer->stream = outf;
      89                 :          0 :   dump_to_pp (&pp);
      90                 :          0 :   pp_flush (&pp);
      91                 :          0 : }
      92                 :            : 
      93                 :            : /* Dump a multiline representation of this state to stderr.  */
      94                 :            : 
      95                 :            : DEBUG_FUNCTION void
      96                 :          0 : extrinsic_state::dump () const
      97                 :            : {
      98                 :          0 :   dump_to_file (stderr);
      99                 :          0 : }
     100                 :            : 
     101                 :            : /* class sm_state_map.  */
     102                 :            : 
     103                 :            : /* sm_state_map's ctor.  */
     104                 :            : 
     105                 :     924364 : sm_state_map::sm_state_map ()
     106                 :     924364 : : m_map (), m_global_state (0)
     107                 :            : {
     108                 :     924364 : }
     109                 :            : 
     110                 :            : /* Clone the sm_state_map.  */
     111                 :            : 
     112                 :            : sm_state_map *
     113                 :     533367 : sm_state_map::clone () const
     114                 :            : {
     115                 :     533367 :   return new sm_state_map (*this);
     116                 :            : }
     117                 :            : 
     118                 :            : /* Clone this sm_state_map, remapping all svalue_ids within it with ID_MAP.
     119                 :            : 
     120                 :            :    Return NULL if there are any svalue_ids that have sm-state for which
     121                 :            :    ID_MAP maps them to svalue_id::null (and thus the clone would have lost
     122                 :            :    the sm-state information). */
     123                 :            : 
     124                 :            : sm_state_map *
     125                 :     226777 : sm_state_map::clone_with_remapping (const one_way_svalue_id_map &id_map) const
     126                 :            : {
     127                 :     226777 :   sm_state_map *result = new sm_state_map ();
     128                 :     226777 :   result->m_global_state = m_global_state;
     129                 :     846982 :   for (map_t::iterator iter = m_map.begin ();
     130                 :     999309 :        iter != m_map.end ();
     131                 :     423491 :        ++iter)
     132                 :            :     {
     133                 :     349041 :       svalue_id sid = (*iter).first;
     134                 :     349041 :       gcc_assert (!sid.null_p ());
     135                 :     349041 :       entry_t e = (*iter).second;
     136                 :            :       /* TODO: what should we do if the origin maps from non-null to null?
     137                 :            :          Is that loss of information acceptable?  */
     138                 :     349041 :       id_map.update (&e.m_origin);
     139                 :            : 
     140                 :     349041 :       svalue_id new_sid = id_map.get_dst_for_src (sid);
     141                 :     349041 :       if (new_sid.null_p ())
     142                 :            :         {
     143                 :     152327 :           delete result;
     144                 :     152327 :           return NULL;
     145                 :            :         }
     146                 :     196714 :       result->m_map.put (new_sid, e);
     147                 :            :     }
     148                 :            :   return result;
     149                 :            : }
     150                 :            : 
     151                 :            : /* Print this sm_state_map (for SM) to PP.
     152                 :            :    If MODEL is non-NULL, print representative tree values where
     153                 :            :    available.  */
     154                 :            : 
     155                 :            : void
     156                 :         84 : sm_state_map::print (const state_machine &sm, const region_model *model,
     157                 :            :                      pretty_printer *pp) const
     158                 :            : {
     159                 :         84 :   bool first = true;
     160                 :         84 :   pp_string (pp, "{");
     161                 :         84 :   if (m_global_state != 0)
     162                 :            :     {
     163                 :          0 :       pp_printf (pp, "global: %s", sm.get_state_name (m_global_state));
     164                 :          0 :       first = false;
     165                 :            :     }
     166                 :        336 :   for (map_t::iterator iter = m_map.begin ();
     167                 :        336 :        iter != m_map.end ();
     168                 :        168 :        ++iter)
     169                 :            :     {
     170                 :         84 :       if (!first)
     171                 :          0 :         pp_string (pp, ", ");
     172                 :         84 :       first = false;
     173                 :         84 :       svalue_id sid = (*iter).first;
     174                 :         84 :       sid.print (pp);
     175                 :            : 
     176                 :         84 :       entry_t e = (*iter).second;
     177                 :         84 :       pp_printf (pp, ": %s", sm.get_state_name (e.m_state));
     178                 :         84 :       if (model)
     179                 :         84 :         if (tree rep = model->get_representative_tree (sid))
     180                 :            :           {
     181                 :         84 :             pp_string (pp, " (");
     182                 :         84 :             dump_quoted_tree (pp, rep);
     183                 :         84 :             pp_character (pp, ')');
     184                 :            :           }
     185                 :         84 :       if (!e.m_origin.null_p ())
     186                 :            :         {
     187                 :          0 :           pp_string (pp, " (origin: ");
     188                 :          0 :           e.m_origin.print (pp);
     189                 :          0 :           if (model)
     190                 :          0 :             if (tree rep = model->get_representative_tree (e.m_origin))
     191                 :            :               {
     192                 :          0 :                 pp_string (pp, " (");
     193                 :          0 :                 dump_quoted_tree (pp, rep);
     194                 :          0 :                 pp_character (pp, ')');
     195                 :            :               }
     196                 :          0 :           pp_string (pp, ")");
     197                 :            :         }
     198                 :            :     }
     199                 :         84 :   pp_string (pp, "}");
     200                 :         84 : }
     201                 :            : 
     202                 :            : /* Dump this object (for SM) to stderr.  */
     203                 :            : 
     204                 :            : DEBUG_FUNCTION void
     205                 :          0 : sm_state_map::dump (const state_machine &sm) const
     206                 :            : {
     207                 :          0 :   pretty_printer pp;
     208                 :          0 :   pp_show_color (&pp) = pp_show_color (global_dc->printer);
     209                 :          0 :   pp.buffer->stream = stderr;
     210                 :          0 :   print (sm, NULL, &pp);
     211                 :          0 :   pp_newline (&pp);
     212                 :          0 :   pp_flush (&pp);
     213                 :          0 : }
     214                 :            : 
     215                 :            : /* Return true if no states have been set within this map
     216                 :            :    (all expressions are for the start state).  */
     217                 :            : 
     218                 :            : bool
     219                 :        628 : sm_state_map::is_empty_p () const
     220                 :            : {
     221                 :        628 :   return m_map.elements () == 0 && m_global_state == 0;
     222                 :            : }
     223                 :            : 
     224                 :            : /* Generate a hash value for this sm_state_map.  */
     225                 :            : 
     226                 :            : hashval_t
     227                 :     378667 : sm_state_map::hash () const
     228                 :            : {
     229                 :     378667 :   hashval_t result = 0;
     230                 :            : 
     231                 :            :   /* Accumulate the result by xoring a hash for each slot, so that the
     232                 :            :      result doesn't depend on the ordering of the slots in the map.  */
     233                 :            : 
     234                 :    1085140 :   for (map_t::iterator iter = m_map.begin ();
     235                 :    1085140 :        iter != m_map.end ();
     236                 :     542568 :        ++iter)
     237                 :            :     {
     238                 :     163901 :       inchash::hash hstate;
     239                 :     163901 :       inchash::add ((*iter).first, hstate);
     240                 :     163901 :       entry_t e = (*iter).second;
     241                 :     163901 :       hstate.add_int (e.m_state);
     242                 :     163901 :       inchash::add (e.m_origin, hstate);
     243                 :     163901 :       result ^= hstate.end ();
     244                 :            :     }
     245                 :     378667 :   result ^= m_global_state;
     246                 :            : 
     247                 :     378667 :   return result;
     248                 :            : }
     249                 :            : 
     250                 :            : /* Equality operator for sm_state_map.  */
     251                 :            : 
     252                 :            : bool
     253                 :      95682 : sm_state_map::operator== (const sm_state_map &other) const
     254                 :            : {
     255                 :      95682 :   if (m_global_state != other.m_global_state)
     256                 :            :     return false;
     257                 :            : 
     258                 :      95665 :   if (m_map.elements () != other.m_map.elements ())
     259                 :            :     return false;
     260                 :            : 
     261                 :     211443 :   for (map_t::iterator iter = m_map.begin ();
     262                 :     240150 :        iter != m_map.end ();
     263                 :     120075 :        ++iter)
     264                 :            :     {
     265                 :      34060 :       svalue_id sid = (*iter).first;
     266                 :      34060 :       entry_t e = (*iter).second;
     267                 :      34060 :       entry_t *other_slot = const_cast <map_t &> (other.m_map).get (sid);
     268                 :      31688 :       if (other_slot == NULL)
     269                 :       5353 :         return false;
     270                 :      62767 :       if (e != *other_slot)
     271                 :            :         return false;
     272                 :            :     }
     273                 :            : 
     274                 :      86015 :   gcc_checking_assert (hash () == other.hash ());
     275                 :            : 
     276                 :            :   return true;
     277                 :            : }
     278                 :            : 
     279                 :            : /* Get the state of SID within this object.
     280                 :            :    States default to the start state.  */
     281                 :            : 
     282                 :            : state_machine::state_t
     283                 :     205030 : sm_state_map::get_state (svalue_id sid) const
     284                 :            : {
     285                 :     205030 :   gcc_assert (!sid.null_p ());
     286                 :            : 
     287                 :     205030 :   if (entry_t *slot
     288                 :     205030 :       = const_cast <map_t &> (m_map).get (sid))
     289                 :      22891 :     return slot->m_state;
     290                 :            :   else
     291                 :            :     return 0;
     292                 :            : }
     293                 :            : 
     294                 :            : /* Get the "origin" svalue_id for any state of SID.  */
     295                 :            : 
     296                 :            : svalue_id
     297                 :       7197 : sm_state_map::get_origin (svalue_id sid) const
     298                 :            : {
     299                 :       7197 :   gcc_assert (!sid.null_p ());
     300                 :            : 
     301                 :       7197 :   entry_t *slot
     302                 :       7197 :     = const_cast <map_t &> (m_map).get (sid);
     303                 :        117 :   if (slot)
     304                 :        117 :     return slot->m_origin;
     305                 :            :   else
     306                 :       7080 :     return svalue_id::null ();
     307                 :            : }
     308                 :            : 
     309                 :            : /* Set the state of SID within MODEL to STATE, recording that
     310                 :            :    the state came from ORIGIN.  */
     311                 :            : 
     312                 :            : void
     313                 :      14834 : sm_state_map::set_state (region_model *model,
     314                 :            :                          svalue_id sid,
     315                 :            :                          state_machine::state_t state,
     316                 :            :                          svalue_id origin)
     317                 :            : {
     318                 :      14834 :   if (model == NULL)
     319                 :            :     return;
     320                 :      14834 :   equiv_class &ec = model->get_constraints ()->get_equiv_class (sid);
     321                 :      14834 :   if (!set_state (ec, state, origin))
     322                 :            :     return;
     323                 :            : 
     324                 :            :   /* Also do it for all svalues that are equal via non-cm, so that
     325                 :            :      e.g. (void *)&r and (foo *)&r transition together.  */
     326                 :      28470 :   for (unsigned i = 0; i < model->get_num_svalues (); i++)
     327                 :            :     {
     328                 :      12718 :       svalue_id other_sid = svalue_id::from_int (i);
     329                 :      12718 :       if (other_sid == sid)
     330                 :       1517 :         continue;
     331                 :            : 
     332                 :      11201 :       tristate eq = model->eval_condition_without_cm (sid, EQ_EXPR, other_sid);
     333                 :      11201 :       if (eq.is_true ())
     334                 :         99 :         impl_set_state (other_sid, state, origin);
     335                 :            :     }
     336                 :            : }
     337                 :            : 
     338                 :            : /* Set the state of EC to STATE, recording that the state came from
     339                 :            :    ORIGIN.
     340                 :            :    Return true if any states of svalue_ids within EC changed.  */
     341                 :            : 
     342                 :            : bool
     343                 :      14834 : sm_state_map::set_state (const equiv_class &ec,
     344                 :            :                          state_machine::state_t state,
     345                 :            :                          svalue_id origin)
     346                 :            : {
     347                 :      14834 :   int i;
     348                 :      14834 :   svalue_id *sid;
     349                 :      14834 :   bool any_changed = false;
     350                 :      30008 :   FOR_EACH_VEC_ELT (ec.m_vars, i, sid)
     351                 :      15174 :     any_changed |= impl_set_state (*sid, state, origin);
     352                 :      14834 :   return any_changed;
     353                 :            : }
     354                 :            : 
     355                 :            : /* Set state of SID to STATE, bypassing equivalence classes.
     356                 :            :    Return true if the state changed.  */
     357                 :            : 
     358                 :            : bool
     359                 :      92076 : sm_state_map::impl_set_state (svalue_id sid, state_machine::state_t state,
     360                 :            :                               svalue_id origin)
     361                 :            : {
     362                 :      92076 :   if (get_state (sid) == state)
     363                 :            :     return false;
     364                 :            : 
     365                 :            :   /* Special-case state 0 as the default value.  */
     366                 :      63393 :   if (state == 0)
     367                 :            :     {
     368                 :        100 :       if (m_map.get (sid))
     369                 :        100 :         m_map.remove (sid);
     370                 :        100 :       return true;
     371                 :            :     }
     372                 :      63293 :   gcc_assert (!sid.null_p ());
     373                 :      63293 :   m_map.put (sid, entry_t (state, origin));
     374                 :      63293 :   return true;
     375                 :            : }
     376                 :            : 
     377                 :            : /* Set the "global" state within this state map to STATE.  */
     378                 :            : 
     379                 :            : void
     380                 :         11 : sm_state_map::set_global_state (state_machine::state_t state)
     381                 :            : {
     382                 :         11 :   m_global_state = state;
     383                 :         11 : }
     384                 :            : 
     385                 :            : /* Get the "global" state within this state map.  */
     386                 :            : 
     387                 :            : state_machine::state_t
     388                 :      47882 : sm_state_map::get_global_state () const
     389                 :            : {
     390                 :      47882 :   return m_global_state;
     391                 :            : }
     392                 :            : 
     393                 :            : /* Handle CALL to unknown FNDECL with an unknown function body, which
     394                 :            :    could do anything to the states passed to it.
     395                 :            :    Clear any state for SM for the params and any LHS.
     396                 :            :    Note that the function might be known to other state machines, but
     397                 :            :    not to this one.  */
     398                 :            : 
     399                 :            : void
     400                 :      11325 : sm_state_map::purge_for_unknown_fncall (const exploded_graph &eg,
     401                 :            :                                         const state_machine &sm,
     402                 :            :                                         const gcall *call,
     403                 :            :                                         tree fndecl,
     404                 :            :                                         region_model *new_model,
     405                 :            :                                         region_model_context *ctxt)
     406                 :            : {
     407                 :      11325 :   logger * const logger = eg.get_logger ();
     408                 :      11325 :   if (logger)
     409                 :            :     {
     410                 :          0 :       if (fndecl)
     411                 :          0 :         logger->log ("function %qE is unknown to checker %qs",
     412                 :            :                      fndecl, sm.get_name ());
     413                 :            :       else
     414                 :          0 :         logger->log ("unknown function pointer for checker %qs",
     415                 :            :                      sm.get_name ());
     416                 :            :     }
     417                 :            : 
     418                 :            :   /* Purge any state for parms.  */
     419                 :      11325 :   tree iter_param_types = NULL_TREE;
     420                 :      11325 :   if (fndecl)
     421                 :      11261 :     iter_param_types = TYPE_ARG_TYPES (TREE_TYPE (fndecl));
     422                 :      21747 :   for (unsigned arg_idx = 0; arg_idx < gimple_call_num_args (call); arg_idx++)
     423                 :            :     {
     424                 :            :       /* Track expected param type, where available.  */
     425                 :      10422 :       if (iter_param_types)
     426                 :            :         {
     427                 :      10145 :           tree param_type = TREE_VALUE (iter_param_types);
     428                 :      10145 :           gcc_assert (param_type);
     429                 :      10145 :           iter_param_types = TREE_CHAIN (iter_param_types);
     430                 :            : 
     431                 :            :           /* Don't purge state if it was passed as a const pointer
     432                 :            :              e.g. for things like strlen (PTR).  */
     433                 :      10145 :           if (TREE_CODE (param_type) == POINTER_TYPE)
     434                 :       4476 :             if (TYPE_READONLY (TREE_TYPE (param_type)))
     435                 :        924 :               continue;
     436                 :            :         }
     437                 :       9498 :       tree parm = gimple_call_arg (call, arg_idx);
     438                 :       9498 :       svalue_id parm_sid = new_model->get_rvalue (parm, ctxt);
     439                 :       9498 :       set_state (new_model, parm_sid, 0, svalue_id::null ());
     440                 :            : 
     441                 :            :       /* Also clear sm-state from svalue_ids that are passed via a
     442                 :            :          pointer.  */
     443                 :       9498 :       if (TREE_CODE (parm) == ADDR_EXPR)
     444                 :            :         {
     445                 :        403 :           tree pointee = TREE_OPERAND (parm, 0);
     446                 :        403 :           svalue_id parm_sid = new_model->get_rvalue (pointee, ctxt);
     447                 :        403 :           set_state (new_model, parm_sid, 0, svalue_id::null ());
     448                 :            :         }
     449                 :            :     }
     450                 :            : 
     451                 :            :   /* Purge any state for any LHS.  */
     452                 :      11325 :   if (tree lhs = gimple_call_lhs (call))
     453                 :            :     {
     454                 :       3423 :       svalue_id lhs_sid = new_model->get_rvalue (lhs, ctxt);
     455                 :       3423 :       set_state (new_model, lhs_sid, 0, svalue_id::null ());
     456                 :            :     }
     457                 :      11325 : }
     458                 :            : 
     459                 :            : /* Update this map based on MAP.  */
     460                 :            : 
     461                 :            : void
     462                 :     247010 : sm_state_map::remap_svalue_ids (const svalue_id_map &map)
     463                 :            : {
     464                 :     247010 :   map_t tmp_map;
     465                 :            : 
     466                 :            :   /* Build an intermediate map, using the new sids.  */
     467                 :     617048 :   for (map_t::iterator iter = m_map.begin ();
     468                 :     617048 :        iter != m_map.end ();
     469                 :     308524 :        ++iter)
     470                 :            :     {
     471                 :      61514 :       svalue_id sid = (*iter).first;
     472                 :      61514 :       entry_t e = (*iter).second;
     473                 :            : 
     474                 :      61514 :       map.update (&sid);
     475                 :      61514 :       map.update (&e.m_origin);
     476                 :      61514 :       tmp_map.put (sid, e);
     477                 :            :     }
     478                 :            : 
     479                 :            :   /* Clear the existing values.  */
     480                 :     247010 :   m_map.empty ();
     481                 :            : 
     482                 :            :   /* Copy over from intermediate map.  */
     483                 :     617048 :   for (map_t::iterator iter = tmp_map.begin ();
     484                 :     247010 :        iter != tmp_map.end ();
     485                 :     308524 :        ++iter)
     486                 :            :     {
     487                 :      61514 :       svalue_id sid = (*iter).first;
     488                 :      61514 :       entry_t e = (*iter).second;
     489                 :            : 
     490                 :      61514 :       impl_set_state (sid, e.m_state, e.m_origin);
     491                 :            :     }
     492                 :     247010 : }
     493                 :            : 
     494                 :            : /* Purge any state for svalue_ids >= FIRST_UNUSED_SID.
     495                 :            :    If !SM::can_purge_p, then report the state as leaking,
     496                 :            :    using SM_IDX, CTXT, and MAP.
     497                 :            :    Return the number of states that were purged.  */
     498                 :            : 
     499                 :            : int
     500                 :     117307 : sm_state_map::on_svalue_purge (const state_machine &sm,
     501                 :            :                                int sm_idx,
     502                 :            :                                svalue_id first_unused_sid,
     503                 :            :                                const svalue_id_map &map,
     504                 :            :                                impl_region_model_context *ctxt)
     505                 :            : {
     506                 :            :   /* TODO: ideally remove the slot directly; for now
     507                 :            :      do it in two stages.  */
     508                 :     117307 :   auto_vec<svalue_id> to_remove;
     509                 :     292362 :   for (map_t::iterator iter = m_map.begin ();
     510                 :     294392 :        iter != m_map.end ();
     511                 :     146181 :        ++iter)
     512                 :            :     {
     513                 :      28874 :       svalue_id dst_sid ((*iter).first);
     514                 :      28874 :       if (dst_sid.as_int () >= first_unused_sid.as_int ())
     515                 :            :         {
     516                 :            :           /* Complain about leaks here.  */
     517                 :       2030 :           entry_t e = (*iter).second;
     518                 :            : 
     519                 :       2030 :           if (!sm.can_purge_p (e.m_state))
     520                 :        251 :             ctxt->on_state_leak (sm, sm_idx, dst_sid, first_unused_sid,
     521                 :            :                                  map, e.m_state);
     522                 :            : 
     523                 :       2030 :           to_remove.safe_push (dst_sid);
     524                 :            :         }
     525                 :      26844 :       else if ((*iter).second.m_origin.as_int () >= first_unused_sid.as_int ())
     526                 :            :         {
     527                 :            :           /* If the origin svalue is being purged, then reset it to null.  */
     528                 :         10 :           (*iter).second.m_origin = svalue_id::null ();
     529                 :            :         }
     530                 :            :     }
     531                 :            : 
     532                 :            :   int i;
     533                 :            :   svalue_id *dst_sid;
     534                 :     119337 :   FOR_EACH_VEC_ELT (to_remove, i, dst_sid)
     535                 :       2030 :     m_map.remove (*dst_sid);
     536                 :            : 
     537                 :     119247 :   return to_remove.length ();
     538                 :            : }
     539                 :            : 
     540                 :            : /* Set the state of CHILD_SID to that of PARENT_SID.  */
     541                 :            : 
     542                 :            : void
     543                 :       1966 : sm_state_map::on_inherited_svalue (svalue_id parent_sid,
     544                 :            :                                    svalue_id child_sid)
     545                 :            : {
     546                 :       1966 :   state_machine::state_t state = get_state (parent_sid);
     547                 :       1966 :   impl_set_state (child_sid, state, parent_sid);
     548                 :       1966 : }
     549                 :            : 
     550                 :            : /* Set the state of DST_SID to that of SRC_SID.  */
     551                 :            : 
     552                 :            : void
     553                 :       7187 : sm_state_map::on_cast (svalue_id src_sid,
     554                 :            :                        svalue_id dst_sid)
     555                 :            : {
     556                 :       7187 :   state_machine::state_t state = get_state (src_sid);
     557                 :       7187 :   impl_set_state (dst_sid, state, get_origin (src_sid));
     558                 :       7187 : }
     559                 :            : 
     560                 :            : /* Purge state from SID (in response to a call to an unknown function).  */
     561                 :            : 
     562                 :            : void
     563                 :       6104 : sm_state_map::on_unknown_change (svalue_id sid)
     564                 :            : {
     565                 :       6104 :   impl_set_state (sid, (state_machine::state_t)0, svalue_id::null ());
     566                 :       6104 : }
     567                 :            : 
     568                 :            : /* Assert that this object is sane.  */
     569                 :            : 
     570                 :            : void
     571                 :     443152 : sm_state_map::validate (const state_machine &sm,
     572                 :            :                         int num_svalues) const
     573                 :            : {
     574                 :            :   /* Skip this in a release build.  */
     575                 :            : #if !CHECKING_P
     576                 :            :   return;
     577                 :            : #endif
     578                 :            : 
     579                 :    1092120 :   for (map_t::iterator iter = m_map.begin ();
     580                 :    1092120 :        iter != m_map.end ();
     581                 :     546058 :        ++iter)
     582                 :            :     {
     583                 :     102906 :       svalue_id sid = (*iter).first;
     584                 :     102906 :       entry_t e = (*iter).second;
     585                 :            : 
     586                 :     102906 :       gcc_assert (sid.as_int () < num_svalues);
     587                 :     102906 :       sm.validate (e.m_state);
     588                 :     102906 :       gcc_assert (e.m_origin.as_int () < num_svalues);
     589                 :            :     }
     590                 :     443152 : }
     591                 :            : 
     592                 :            : /* class program_state.  */
     593                 :            : 
     594                 :            : /* program_state's ctor.  */
     595                 :            : 
     596                 :     174647 : program_state::program_state (const extrinsic_state &ext_state)
     597                 :     174647 : : m_region_model (new region_model ()),
     598                 :     174647 :   m_checker_states (ext_state.get_num_checkers ()),
     599                 :     174647 :   m_valid (true)
     600                 :            : {
     601                 :     174647 :   int num_states = ext_state.get_num_checkers ();
     602                 :     872216 :   for (int i = 0; i < num_states; i++)
     603                 :     697569 :     m_checker_states.quick_push (new sm_state_map ());
     604                 :     174647 : }
     605                 :            : 
     606                 :            : /* program_state's copy ctor.  */
     607                 :            : 
     608                 :     131354 : program_state::program_state (const program_state &other)
     609                 :     131354 : : m_region_model (new region_model (*other.m_region_model)),
     610                 :     131354 :   m_checker_states (other.m_checker_states.length ()),
     611                 :     131354 :   m_valid (true)
     612                 :            : {
     613                 :     131354 :   int i;
     614                 :     131354 :   sm_state_map *smap;
     615                 :     647791 :   FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
     616                 :     516437 :     m_checker_states.quick_push (smap->clone ());
     617                 :     131354 : }
     618                 :            : 
     619                 :            : /* program_state's assignment operator.  */
     620                 :            : 
     621                 :            : program_state&
     622                 :       4237 : program_state::operator= (const program_state &other)
     623                 :            : {
     624                 :       4237 :   delete m_region_model;
     625                 :       4237 :   m_region_model = new region_model (*other.m_region_model);
     626                 :            : 
     627                 :       4237 :   int i;
     628                 :       4237 :   sm_state_map *smap;
     629                 :      21167 :   FOR_EACH_VEC_ELT (m_checker_states, i, smap)
     630                 :      33860 :     delete smap;
     631                 :       4237 :   m_checker_states.truncate (0);
     632                 :      12711 :   gcc_assert (m_checker_states.space (other.m_checker_states.length ()));
     633                 :            : 
     634                 :      21167 :   FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
     635                 :      16930 :     m_checker_states.quick_push (smap->clone ());
     636                 :            : 
     637                 :       4237 :   m_valid = other.m_valid;
     638                 :            : 
     639                 :       4237 :   return *this;
     640                 :            : }
     641                 :            : 
     642                 :            : #if __cplusplus >= 201103
     643                 :            : /* Move constructor for program_state (when building with C++11).  */
     644                 :      28260 : program_state::program_state (program_state &&other)
     645                 :      28260 : : m_region_model (other.m_region_model),
     646                 :      28260 :   m_checker_states (other.m_checker_states.length ())
     647                 :            : {
     648                 :      28260 :   other.m_region_model = NULL;
     649                 :            : 
     650                 :      28260 :   int i;
     651                 :      28260 :   sm_state_map *smap;
     652                 :     139359 :   FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
     653                 :     111099 :     m_checker_states.quick_push (smap);
     654                 :      28260 :   other.m_checker_states.truncate (0);
     655                 :            : 
     656                 :      28260 :   m_valid = other.m_valid;
     657                 :      28260 : }
     658                 :            : #endif
     659                 :            : 
     660                 :            : /* program_state's dtor.  */
     661                 :            : 
     662                 :     334261 : program_state::~program_state ()
     663                 :            : {
     664                 :     334261 :   delete m_region_model;
     665                 :     334261 : }
     666                 :            : 
     667                 :            : /* Generate a hash value for this program_state.  */
     668                 :            : 
     669                 :            : hashval_t
     670                 :      36510 : program_state::hash () const
     671                 :            : {
     672                 :      36510 :   hashval_t result = m_region_model->hash ();
     673                 :            : 
     674                 :      36510 :   int i;
     675                 :      36510 :   sm_state_map *smap;
     676                 :     180513 :   FOR_EACH_VEC_ELT (m_checker_states, i, smap)
     677                 :     144003 :     result ^= smap->hash ();
     678                 :      36510 :   return result;
     679                 :            : }
     680                 :            : 
     681                 :            : /* Equality operator for program_state.
     682                 :            :    All parts of the program_state (region model, checker states) must
     683                 :            :    equal their counterparts in OTHER for the two program_states to be
     684                 :            :    considered equal.  */
     685                 :            : 
     686                 :            : bool
     687                 :      13070 : program_state::operator== (const program_state &other) const
     688                 :            : {
     689                 :      13070 :   if (!(*m_region_model == *other.m_region_model))
     690                 :            :     return false;
     691                 :            : 
     692                 :            :   int i;
     693                 :            :   sm_state_map *smap;
     694                 :       9134 :   FOR_EACH_VEC_ELT (m_checker_states, i, smap)
     695                 :       7316 :     if (!(*smap == *other.m_checker_states[i]))
     696                 :            :       return false;
     697                 :            : 
     698                 :       1818 :   gcc_checking_assert (hash () == other.hash ());
     699                 :            : 
     700                 :            :   return true;
     701                 :            : }
     702                 :            : 
     703                 :            : /* Print a compact representation of this state to PP.  */
     704                 :            : 
     705                 :            : void
     706                 :          0 : program_state::print (const extrinsic_state &ext_state,
     707                 :            :                       pretty_printer *pp) const
     708                 :            : {
     709                 :          0 :   pp_printf (pp, "rmodel: ");
     710                 :          0 :   m_region_model->print (pp);
     711                 :          0 :   pp_newline (pp);
     712                 :            : 
     713                 :          0 :   int i;
     714                 :          0 :   sm_state_map *smap;
     715                 :          0 :   FOR_EACH_VEC_ELT (m_checker_states, i, smap)
     716                 :            :     {
     717                 :          0 :       if (!smap->is_empty_p ())
     718                 :            :         {
     719                 :          0 :           pp_printf (pp, "%s: ", ext_state.get_name (i));
     720                 :          0 :           smap->print (ext_state.get_sm (i), m_region_model, pp);
     721                 :          0 :           pp_newline (pp);
     722                 :            :         }
     723                 :            :     }
     724                 :          0 :   if (!m_valid)
     725                 :            :     {
     726                 :          0 :       pp_printf (pp, "invalid state");
     727                 :          0 :       pp_newline (pp);
     728                 :            :     }
     729                 :          0 : }
     730                 :            : 
     731                 :            : /* Dump a representation of this state to PP.
     732                 :            :    If SUMMARIZE is true, print a one-line summary;
     733                 :            :    if false, print a detailed multiline representation.  */
     734                 :            : 
     735                 :            : void
     736                 :         85 : program_state::dump_to_pp (const extrinsic_state &ext_state,
     737                 :            :                            bool summarize,
     738                 :            :                            pretty_printer *pp) const
     739                 :            : {
     740                 :         85 :   pp_printf (pp, "rmodel: ");
     741                 :         85 :   m_region_model->dump_to_pp (pp, summarize);
     742                 :            : 
     743                 :         85 :   int i;
     744                 :         85 :   sm_state_map *smap;
     745                 :        397 :   FOR_EACH_VEC_ELT (m_checker_states, i, smap)
     746                 :            :     {
     747                 :        312 :       if (!smap->is_empty_p ())
     748                 :            :         {
     749                 :         44 :           if (summarize)
     750                 :         42 :             pp_space (pp);
     751                 :         44 :           pp_printf (pp, "%s: ", ext_state.get_name (i));
     752                 :         44 :           smap->print (ext_state.get_sm (i), m_region_model, pp);
     753                 :         44 :           if (!summarize)
     754                 :          2 :             pp_newline (pp);
     755                 :            :         }
     756                 :            :     }
     757                 :            : 
     758                 :         85 :   if (!m_valid)
     759                 :            :     {
     760                 :          0 :       if (summarize)
     761                 :          0 :         pp_space (pp);
     762                 :          0 :       pp_printf (pp, "invalid state");
     763                 :          0 :       if (!summarize)
     764                 :          0 :         pp_newline (pp);
     765                 :            :     }
     766                 :         85 : }
     767                 :            : 
     768                 :            : /* Dump a multiline representation of this state to OUTF.  */
     769                 :            : 
     770                 :            : void
     771                 :          0 : program_state::dump_to_file (const extrinsic_state &ext_state,
     772                 :            :                              bool summarize,
     773                 :            :                              FILE *outf) const
     774                 :            : {
     775                 :          0 :   pretty_printer pp;
     776                 :          0 :   pp_format_decoder (&pp) = default_tree_printer;
     777                 :          0 :   if (outf == stderr)
     778                 :          0 :     pp_show_color (&pp) = pp_show_color (global_dc->printer);
     779                 :          0 :   pp.buffer->stream = outf;
     780                 :          0 :   dump_to_pp (ext_state, summarize, &pp);
     781                 :          0 :   pp_flush (&pp);
     782                 :          0 : }
     783                 :            : 
     784                 :            : /* Dump a multiline representation of this state to stderr.  */
     785                 :            : 
     786                 :            : DEBUG_FUNCTION void
     787                 :          0 : program_state::dump (const extrinsic_state &ext_state,
     788                 :            :                      bool summarize) const
     789                 :            : {
     790                 :          0 :   dump_to_file (ext_state, summarize, stderr);
     791                 :          0 : }
     792                 :            : 
     793                 :            : /* Determine if following edge SUCC from ENODE is valid within the graph EG
     794                 :            :    and update this state accordingly in-place.
     795                 :            : 
     796                 :            :    Return true if the edge can be followed, or false otherwise.
     797                 :            : 
     798                 :            :    Check for relevant conditionals and switch-values for conditionals
     799                 :            :    and switch statements, adding the relevant conditions to this state.
     800                 :            :    Push/pop frames for interprocedural edges and update params/returned
     801                 :            :    values.
     802                 :            : 
     803                 :            :    This is the "state" half of exploded_node::on_edge.  */
     804                 :            : 
     805                 :            : bool
     806                 :      10461 : program_state::on_edge (exploded_graph &eg,
     807                 :            :                         const exploded_node &enode,
     808                 :            :                         const superedge *succ,
     809                 :            :                         state_change *change)
     810                 :            : {
     811                 :            :   /* Update state.  */
     812                 :      10461 :   const program_point &point = enode.get_point ();
     813                 :      10461 :   const gimple *last_stmt = point.get_supernode ()->get_last_stmt ();
     814                 :            : 
     815                 :            :   /* For conditionals and switch statements, add the
     816                 :            :      relevant conditions (for the specific edge) to new_state;
     817                 :            :      skip edges for which the resulting constraints
     818                 :            :      are impossible.
     819                 :            :      This also updates frame information for call/return superedges.
     820                 :            :      Adding the relevant conditions for the edge could also trigger
     821                 :            :      sm-state transitions (e.g. transitions due to ptrs becoming known
     822                 :            :      to be NULL or non-NULL) */
     823                 :            : 
     824                 :      10461 :   impl_region_model_context ctxt (eg, &enode,
     825                 :      10461 :                                   &enode.get_state (),
     826                 :            :                                   this, change,
     827                 :      10461 :                                   last_stmt);
     828                 :      10461 :   if (!m_region_model->maybe_update_for_edge (*succ,
     829                 :            :                                               last_stmt,
     830                 :            :                                               &ctxt))
     831                 :            :     {
     832                 :        345 :       logger * const logger = eg.get_logger ();
     833                 :        345 :       if (logger)
     834                 :          0 :         logger->log ("edge to SN: %i is impossible"
     835                 :            :                      " due to region_model constraints",
     836                 :          0 :                      succ->m_dest->m_index);
     837                 :        345 :       return false;
     838                 :            :     }
     839                 :            : 
     840                 :            :   return true;
     841                 :            : }
     842                 :            : 
     843                 :            : /* Generate a simpler version of THIS, discarding state that's no longer
     844                 :            :    relevant at POINT.
     845                 :            :    The idea is that we're more likely to be able to consolidate
     846                 :            :    multiple (point, state) into single exploded_nodes if we discard
     847                 :            :    irrelevant state (e.g. at the end of functions).
     848                 :            : 
     849                 :            :    Retain state affected by CHANGE, to make it easier to generate
     850                 :            :    state_change_events.  */
     851                 :            : 
     852                 :            : program_state
     853                 :      28637 : program_state::prune_for_point (exploded_graph &eg,
     854                 :            :                                 const program_point &point,
     855                 :            :                                 state_change *change) const
     856                 :            : {
     857                 :      28637 :   logger * const logger = eg.get_logger ();
     858                 :      57274 :   LOG_SCOPE (logger);
     859                 :            : 
     860                 :      28637 :   function *fun = point.get_function ();
     861                 :      28260 :   if (!fun)
     862                 :        377 :     return *this;
     863                 :            : 
     864                 :      28260 :   program_state new_state (*this);
     865                 :            : 
     866                 :      28260 :   purge_stats stats;
     867                 :            : 
     868                 :      28260 :   const state_purge_map *pm = eg.get_purge_map ();
     869                 :      28260 :   if (pm)
     870                 :            :     {
     871                 :      56142 :       region_id_set purgeable_ssa_regions (new_state.m_region_model);
     872                 :      28071 :       region_id frame_rid
     873                 :      28071 :         = new_state.m_region_model->get_current_frame_id ();
     874                 :      28071 :       frame_region *frame
     875                 :      28071 :         = new_state.m_region_model->get_region <frame_region>(frame_rid);
     876                 :            : 
     877                 :            :       /* TODO: maybe move to a member of region_model?  */
     878                 :            : 
     879                 :      56142 :       auto_vec<tree> ssa_names_to_purge;
     880                 :     255923 :       for (frame_region::map_t::iterator iter = frame->begin ();
     881                 :     168229 :            iter != frame->end ();
     882                 :     168229 :            ++iter)
     883                 :            :         {
     884                 :     140158 :           tree var = (*iter).first;
     885                 :     140158 :           region_id rid = (*iter).second;
     886                 :     140158 :           if (TREE_CODE (var) == SSA_NAME)
     887                 :            :             {
     888                 :      84528 :               const state_purge_per_ssa_name &per_ssa
     889                 :      84528 :                 = pm->get_data_for_ssa_name (var);
     890                 :      84528 :               if (!per_ssa.needed_at_point_p (point.get_function_point ()))
     891                 :            :                 {
     892                 :      29278 :                   region *region
     893                 :      29278 :                     = new_state.m_region_model->get_region (rid);
     894                 :      29278 :                   svalue_id sid = region->get_value_direct ();
     895                 :      29278 :                   if (!sid.null_p ())
     896                 :            :                     {
     897                 :      29274 :                       if (!new_state.can_purge_p (eg.get_ext_state (), sid))
     898                 :            :                         {
     899                 :            :                           /* (currently only state maps can keep things
     900                 :            :                              alive).  */
     901                 :      10977 :                           if (logger)
     902                 :          0 :                             logger->log ("not purging RID: %i for %qE"
     903                 :            :                                          " (used by state map)",
     904                 :            :                                          rid.as_int (), var);
     905                 :      11383 :                           continue;
     906                 :            :                         }
     907                 :            : 
     908                 :            :                       /* Don't purge regions containing svalues that
     909                 :            :                          have a change of sm-state, to make it easier to
     910                 :            :                          generate state_change_event messages.  */
     911                 :      18297 :                       if (change)
     912                 :      18291 :                         if (change->affects_p (sid))
     913                 :            :                           {
     914                 :        406 :                             if (logger)
     915                 :          0 :                               logger->log ("not purging RID: %i for %qE"
     916                 :            :                                            " (affected by change)",
     917                 :            :                                            rid.as_int (), var);
     918                 :        406 :                             continue;
     919                 :            :                           }
     920                 :            :                     }
     921                 :      17895 :                   purgeable_ssa_regions.add_region (rid);
     922                 :      17895 :                   ssa_names_to_purge.safe_push (var);
     923                 :      17895 :                   if (logger)
     924                 :          0 :                     logger->log ("purging RID: %i for %qE", rid.as_int (), var);
     925                 :            :                   /* We also need to remove the region from the map.
     926                 :            :                      We're in mid-traversal, so the removal is done in
     927                 :            :                      unbind below.  */
     928                 :            :                 }
     929                 :            :             }
     930                 :            :         }
     931                 :            : 
     932                 :            :       /* Unbind the regions from the frame's map of vars-to-regions.  */
     933                 :      28071 :       unsigned i;
     934                 :      28071 :       tree var;
     935                 :      45966 :       FOR_EACH_VEC_ELT (ssa_names_to_purge, i, var)
     936                 :      17895 :         frame->unbind (var);
     937                 :            : 
     938                 :            :       /* Purge the regions.  Nothing should point to them, and they
     939                 :            :          should have no children, as they are for SSA names.  */
     940                 :      28071 :       new_state.m_region_model->purge_regions (purgeable_ssa_regions,
     941                 :            :                                                &stats,
     942                 :            :                                                eg.get_logger ());
     943                 :            :     }
     944                 :            : 
     945                 :            :   /* Purge unused svalues.  */
     946                 :            :   // TODO: which enode to use, if any?
     947                 :      28260 :   impl_region_model_context ctxt (eg, NULL,
     948                 :            :                                   this,
     949                 :            :                                   &new_state,
     950                 :            :                                   change,
     951                 :      56520 :                                   NULL);
     952                 :      28260 :   new_state.m_region_model->purge_unused_svalues (&stats, &ctxt);
     953                 :      28260 :   if (logger)
     954                 :            :     {
     955                 :          0 :       logger->log ("num svalues purged: %i", stats.m_num_svalues);
     956                 :          0 :       logger->log ("num regions purged: %i", stats.m_num_regions);
     957                 :          0 :       logger->log ("num equiv_classes purged: %i", stats.m_num_equiv_classes);
     958                 :          0 :       logger->log ("num constraints purged: %i", stats.m_num_constraints);
     959                 :          0 :       logger->log ("num sm map items purged: %i", stats.m_num_client_items);
     960                 :            :     }
     961                 :            : 
     962                 :      28260 :   new_state.m_region_model->canonicalize (&ctxt);
     963                 :            : 
     964                 :      28260 :   return new_state;
     965                 :            : }
     966                 :            : 
     967                 :            : /* Remap all svalue_ids in this state's m_checker_states according to MAP.
     968                 :            :    The svalues_ids in the region_model are assumed to already have been
     969                 :            :    remapped.  */
     970                 :            : 
     971                 :            : void
     972                 :      62772 : program_state::remap_svalue_ids (const svalue_id_map &map)
     973                 :            : {
     974                 :      62772 :   int i;
     975                 :      62772 :   sm_state_map *smap;
     976                 :     309780 :   FOR_EACH_VEC_ELT (m_checker_states, i, smap)
     977                 :     247008 :     smap->remap_svalue_ids (map);
     978                 :      62772 : }
     979                 :            : 
     980                 :            : /* Attempt to return a tree that represents SID, or return NULL_TREE.
     981                 :            :    Find the first region that stores the value (e.g. a local) and
     982                 :            :    generate a representative tree for it.  */
     983                 :            : 
     984                 :            : tree
     985                 :        807 : program_state::get_representative_tree (svalue_id sid) const
     986                 :            : {
     987                 :        807 :   return m_region_model->get_representative_tree (sid);
     988                 :            : }
     989                 :            : 
     990                 :            : /* Attempt to merge this state with OTHER, both using EXT_STATE.
     991                 :            :    Write the result to *OUT.
     992                 :            :    If the states were merged successfully, return true.  */
     993                 :            : 
     994                 :            : bool
     995                 :     173343 : program_state::can_merge_with_p (const program_state &other,
     996                 :            :                                  const extrinsic_state &ext_state,
     997                 :            :                                  program_state *out) const
     998                 :            : {
     999                 :     173343 :   gcc_assert (out);
    1000                 :            : 
    1001                 :            :   /* TODO:  initially I had an early reject here if there
    1002                 :            :      are sm-differences between the states.  However, this was
    1003                 :            :      falsely rejecting merger opportunities for states where the
    1004                 :            :      only difference was in svalue_id ordering.  */
    1005                 :            : 
    1006                 :            :   /* Attempt to merge the region_models.  */
    1007                 :            : 
    1008                 :     173343 :   svalue_id_merger_mapping sid_mapping (*m_region_model,
    1009                 :     173343 :                                         *other.m_region_model);
    1010                 :     173343 :   if (!m_region_model->can_merge_with_p (*other.m_region_model,
    1011                 :            :                                          out->m_region_model,
    1012                 :            :                                          &sid_mapping))
    1013                 :            :     return false;
    1014                 :            : 
    1015                 :            :   /* Copy m_checker_states to result, remapping svalue_ids using
    1016                 :            :      sid_mapping.  */
    1017                 :            :   int i;
    1018                 :            :   sm_state_map *smap;
    1019                 :     826117 :   FOR_EACH_VEC_ELT (out->m_checker_states, i, smap)
    1020                 :    1321770 :     delete smap;
    1021                 :     165233 :   out->m_checker_states.truncate (0);
    1022                 :            : 
    1023                 :            :   /* Remap this and other's m_checker_states using sid_mapping.
    1024                 :            :      Only merge states that have equality between the two end-results:
    1025                 :            :      sm-state differences are likely to be interesting to end-users, and
    1026                 :            :      hence are worth exploring as separate paths in the exploded graph.  */
    1027                 :     184032 :   FOR_EACH_VEC_ELT (m_checker_states, i, smap)
    1028                 :            :     {
    1029                 :     179372 :       sm_state_map *other_smap = other.m_checker_states[i];
    1030                 :            : 
    1031                 :            :       /* If clone_with_remapping returns NULL for one of the input smaps,
    1032                 :            :          then it has sm-state for an svalue_id where the svalue_id is
    1033                 :            :          being mapped to svalue_id::null in its sid_mapping, meaning that
    1034                 :            :          the svalue is to be dropped during the merger.  We don't want
    1035                 :            :          to lose sm-state during a state merger, so return false for these
    1036                 :            :          cases.  */
    1037                 :     179372 :       sm_state_map *remapped_a_smap
    1038                 :     179372 :         = smap->clone_with_remapping (sid_mapping.m_map_from_a_to_m);
    1039                 :     179372 :       if (!remapped_a_smap)
    1040                 :     160573 :         return false;
    1041                 :      47405 :       sm_state_map *remapped_b_smap
    1042                 :      47405 :         = other_smap->clone_with_remapping (sid_mapping.m_map_from_b_to_m);
    1043                 :      47405 :       if (!remapped_b_smap)
    1044                 :            :         {
    1045                 :      40720 :           delete remapped_a_smap;
    1046                 :      20360 :           return false;
    1047                 :            :         }
    1048                 :            : 
    1049                 :            :       /* Both states have sm-state for the same values; now ensure that the
    1050                 :            :          states are equal.  */
    1051                 :      27045 :       if (*remapped_a_smap == *remapped_b_smap)
    1052                 :            :         {
    1053                 :      18799 :           out->m_checker_states.safe_push (remapped_a_smap);
    1054                 :      18799 :           delete remapped_b_smap;
    1055                 :            :         }
    1056                 :            :       else
    1057                 :            :         {
    1058                 :            :           /* Don't merge if there are sm-state differences.  */
    1059                 :      16492 :           delete remapped_a_smap;
    1060                 :       8246 :           delete remapped_b_smap;
    1061                 :       8246 :           return false;
    1062                 :            :         }
    1063                 :            :     }
    1064                 :            : 
    1065                 :     178003 :   impl_region_model_context ctxt (out, NULL, ext_state);
    1066                 :       4660 :   out->m_region_model->canonicalize (&ctxt);
    1067                 :            : 
    1068                 :       4660 :   return true;
    1069                 :            : }
    1070                 :            : 
    1071                 :            : /* Assert that this object is valid.  */
    1072                 :            : 
    1073                 :            : void
    1074                 :     112750 : program_state::validate (const extrinsic_state &ext_state) const
    1075                 :            : {
    1076                 :            :   /* Skip this in a release build.  */
    1077                 :            : #if !CHECKING_P
    1078                 :            :   return;
    1079                 :            : #endif
    1080                 :            : 
    1081                 :     112750 :   m_region_model->validate ();
    1082                 :     338250 :   gcc_assert (m_checker_states.length () == ext_state.get_num_checkers ());
    1083                 :            :   int sm_idx;
    1084                 :            :   sm_state_map *smap;
    1085                 :     555902 :   FOR_EACH_VEC_ELT (m_checker_states, sm_idx, smap)
    1086                 :            :     {
    1087                 :     443152 :       const state_machine &sm = ext_state.get_sm (sm_idx);
    1088                 :     880344 :       smap->validate (sm, m_region_model->get_num_svalues ());
    1089                 :            :     }
    1090                 :     112750 : }
    1091                 :            : 
    1092                 :            : /* Dump this sm_change to PP.  */
    1093                 :            : 
    1094                 :            : void
    1095                 :          1 : state_change::sm_change::dump (pretty_printer *pp,
    1096                 :            :                                const extrinsic_state &ext_state) const
    1097                 :            : {
    1098                 :          1 :   const state_machine &sm = get_sm (ext_state);
    1099                 :          1 :   pp_string (pp, "(");
    1100                 :          1 :   m_new_sid.print (pp);
    1101                 :          1 :   pp_printf (pp, ": %s: %qs -> %qs)",
    1102                 :            :              sm.get_name (),
    1103                 :          1 :              sm.get_state_name (m_old_state),
    1104                 :          1 :              sm.get_state_name (m_new_state));
    1105                 :          1 : }
    1106                 :            : 
    1107                 :            : /* Remap all svalue_ids in this change according to MAP.  */
    1108                 :            : 
    1109                 :            : void
    1110                 :       3086 : state_change::sm_change::remap_svalue_ids (const svalue_id_map &map)
    1111                 :            : {
    1112                 :       3086 :   map.update (&m_new_sid);
    1113                 :       3086 : }
    1114                 :            : 
    1115                 :            : /* Purge any svalue_ids >= FIRST_UNUSED_SID.
    1116                 :            :    Return the number of states that were purged.  */
    1117                 :            : 
    1118                 :            : int
    1119                 :       1671 : state_change::sm_change::on_svalue_purge (svalue_id first_unused_sid)
    1120                 :            : {
    1121                 :       1671 :   if (m_new_sid.as_int () >= first_unused_sid.as_int ())
    1122                 :            :     {
    1123                 :         89 :       m_new_sid = svalue_id::null ();
    1124                 :         89 :       return 1;
    1125                 :            :     }
    1126                 :            : 
    1127                 :            :   return 0;
    1128                 :            : }
    1129                 :            : 
    1130                 :            : /* Assert that this object is sane.  */
    1131                 :            : 
    1132                 :            : void
    1133                 :       1494 : state_change::sm_change::validate (const program_state &new_state,
    1134                 :            :                                    const extrinsic_state &ext_state) const
    1135                 :            : {
    1136                 :       2988 :   gcc_assert ((unsigned)m_sm_idx < ext_state.get_num_checkers ());
    1137                 :       1494 :   const state_machine &sm = ext_state.get_sm (m_sm_idx);
    1138                 :       1494 :   sm.validate (m_old_state);
    1139                 :       1494 :   sm.validate (m_new_state);
    1140                 :       1494 :   m_new_sid.validate (*new_state.m_region_model);
    1141                 :       1494 : }
    1142                 :            : 
    1143                 :            : /* state_change's ctor.  */
    1144                 :            : 
    1145                 :      33315 : state_change::state_change ()
    1146                 :            : {
    1147                 :      33315 : }
    1148                 :            : 
    1149                 :            : /* state_change's copy ctor.  */
    1150                 :            : 
    1151                 :      28362 : state_change::state_change (const state_change &other)
    1152                 :      28362 : : m_sm_changes (other.m_sm_changes.length ())
    1153                 :            : {
    1154                 :            :   unsigned i;
    1155                 :            :   sm_change *change;
    1156                 :      29856 :   FOR_EACH_VEC_ELT (other.m_sm_changes, i, change)
    1157                 :       1494 :     m_sm_changes.quick_push (*change);
    1158                 :      28362 : }
    1159                 :            : 
    1160                 :            : /* Record a state-machine state change.  */
    1161                 :            : 
    1162                 :            : void
    1163                 :       1508 : state_change::add_sm_change (int sm_idx,
    1164                 :            :                              svalue_id new_sid,
    1165                 :            :                              state_machine::state_t old_state,
    1166                 :            :                              state_machine::state_t new_state)
    1167                 :            : {
    1168                 :       1508 :   m_sm_changes.safe_push (sm_change (sm_idx,
    1169                 :            :                                      new_sid,
    1170                 :            :                                      old_state, new_state));
    1171                 :       1508 : }
    1172                 :            : 
    1173                 :            : /* Return true if SID (in the new state) was affected by any
    1174                 :            :    sm-state changes.  */
    1175                 :            : 
    1176                 :            : bool
    1177                 :      18291 : state_change::affects_p (svalue_id sid) const
    1178                 :            : {
    1179                 :      18291 :   unsigned i;
    1180                 :      18291 :   sm_change *change;
    1181                 :      18767 :   FOR_EACH_VEC_ELT (m_sm_changes, i, change)
    1182                 :            :     {
    1183                 :        882 :       if (sid == change->m_new_sid)
    1184                 :            :         return true;
    1185                 :            :     }
    1186                 :            :   return false;
    1187                 :            : }
    1188                 :            : 
    1189                 :            : /* Dump this state_change to PP.  */
    1190                 :            : 
    1191                 :            : void
    1192                 :         79 : state_change::dump (pretty_printer *pp,
    1193                 :            :                     const extrinsic_state &ext_state) const
    1194                 :            : {
    1195                 :         79 :   unsigned i;
    1196                 :         79 :   sm_change *change;
    1197                 :         80 :   FOR_EACH_VEC_ELT (m_sm_changes, i, change)
    1198                 :            :     {
    1199                 :          1 :       if (i > 0)
    1200                 :          0 :         pp_string (pp, ", ");
    1201                 :          1 :       change->dump (pp, ext_state);
    1202                 :            :     }
    1203                 :         79 : }
    1204                 :            : 
    1205                 :            : /* Dump this state_change to stderr.  */
    1206                 :            : 
    1207                 :            : void
    1208                 :          0 : state_change::dump (const extrinsic_state &ext_state) const
    1209                 :            : {
    1210                 :          0 :   pretty_printer pp;
    1211                 :          0 :   pp_show_color (&pp) = pp_show_color (global_dc->printer);
    1212                 :          0 :   pp.buffer->stream = stderr;
    1213                 :          0 :   dump (&pp, ext_state);
    1214                 :          0 :   pp_newline (&pp);
    1215                 :          0 :   pp_flush (&pp);
    1216                 :          0 : }
    1217                 :            : 
    1218                 :            : /* Remap all svalue_ids in this state_change according to MAP.  */
    1219                 :            : 
    1220                 :            : void
    1221                 :      55244 : state_change::remap_svalue_ids (const svalue_id_map &map)
    1222                 :            : {
    1223                 :      55244 :   unsigned i;
    1224                 :      55244 :   sm_change *change;
    1225                 :      58330 :   FOR_EACH_VEC_ELT (m_sm_changes, i, change)
    1226                 :       3086 :     change->remap_svalue_ids (map);
    1227                 :      55244 : }
    1228                 :            : 
    1229                 :            : /* Purge any svalue_ids >= FIRST_UNUSED_SID.
    1230                 :            :    Return the number of states that were purged.  */
    1231                 :            : 
    1232                 :            : int
    1233                 :      32132 : state_change::on_svalue_purge (svalue_id first_unused_sid)
    1234                 :            : {
    1235                 :      32132 :   int result = 0;
    1236                 :      32132 :   unsigned i;
    1237                 :      32132 :   sm_change *change;
    1238                 :      33803 :   FOR_EACH_VEC_ELT (m_sm_changes, i, change)
    1239                 :       1671 :     result += change->on_svalue_purge (first_unused_sid);
    1240                 :      32132 :   return result;
    1241                 :            : }
    1242                 :            : 
    1243                 :            : /* Assert that this object is sane.  */
    1244                 :            : 
    1245                 :            : void
    1246                 :      28362 : state_change::validate (const program_state &new_state,
    1247                 :            :                         const extrinsic_state &ext_state) const
    1248                 :            : {
    1249                 :            :   /* Skip this in a release build.  */
    1250                 :            : #if !CHECKING_P
    1251                 :            :   return;
    1252                 :            : #endif
    1253                 :      28362 :   unsigned i;
    1254                 :      28362 :   sm_change *change;
    1255                 :      29856 :   FOR_EACH_VEC_ELT (m_sm_changes, i, change)
    1256                 :       1494 :     change->validate (new_state, ext_state);
    1257                 :      28362 : }
    1258                 :            : 
    1259                 :            : #if CHECKING_P
    1260                 :            : 
    1261                 :            : namespace selftest {
    1262                 :            : 
    1263                 :            : /* Implementation detail of ASSERT_DUMP_EQ.  */
    1264                 :            : 
    1265                 :            : static void
    1266                 :          8 : assert_dump_eq (const location &loc,
    1267                 :            :                 const program_state &state,
    1268                 :            :                 const extrinsic_state &ext_state,
    1269                 :            :                 bool summarize,
    1270                 :            :                 const char *expected)
    1271                 :            : {
    1272                 :         16 :   auto_fix_quotes sentinel;
    1273                 :         16 :   pretty_printer pp;
    1274                 :          8 :   pp_format_decoder (&pp) = default_tree_printer;
    1275                 :          8 :   state.dump_to_pp (ext_state, summarize, &pp);
    1276                 :          8 :   ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected);
    1277                 :          8 : }
    1278                 :            : 
    1279                 :            : /* Assert that STATE.dump_to_pp (SUMMARIZE) is EXPECTED.  */
    1280                 :            : 
    1281                 :            : #define ASSERT_DUMP_EQ(STATE, EXT_STATE, SUMMARIZE, EXPECTED)           \
    1282                 :            :   SELFTEST_BEGIN_STMT                                                   \
    1283                 :            :   assert_dump_eq ((SELFTEST_LOCATION), (STATE), (EXT_STATE), (SUMMARIZE), \
    1284                 :            :                   (EXPECTED));                                          \
    1285                 :            :   SELFTEST_END_STMT
    1286                 :            : 
    1287                 :            : /* Tests for sm_state_map.  */
    1288                 :            : 
    1289                 :            : static void
    1290                 :          2 : test_sm_state_map ()
    1291                 :            : {
    1292                 :          2 :   tree x = build_global_decl ("x", integer_type_node);
    1293                 :          2 :   tree y = build_global_decl ("y", integer_type_node);
    1294                 :          2 :   tree z = build_global_decl ("z", integer_type_node);
    1295                 :            : 
    1296                 :            :   /* Test setting states on svalue_id instances directly.  */
    1297                 :          2 :   {
    1298                 :          2 :     region_model model;
    1299                 :          2 :     svalue_id sid_x = model.get_rvalue (x, NULL);
    1300                 :          2 :     svalue_id sid_y = model.get_rvalue (y, NULL);
    1301                 :          2 :     svalue_id sid_z = model.get_rvalue (z, NULL);
    1302                 :            : 
    1303                 :          4 :     sm_state_map map;
    1304                 :          2 :     ASSERT_TRUE (map.is_empty_p ());
    1305                 :          2 :     ASSERT_EQ (map.get_state (sid_x), 0);
    1306                 :            : 
    1307                 :          2 :     map.impl_set_state (sid_x, 42, sid_z);
    1308                 :          2 :     ASSERT_EQ (map.get_state (sid_x), 42);
    1309                 :          2 :     ASSERT_EQ (map.get_origin (sid_x), sid_z);
    1310                 :          2 :     ASSERT_EQ (map.get_state (sid_y), 0);
    1311                 :          2 :     ASSERT_FALSE (map.is_empty_p ());
    1312                 :            : 
    1313                 :          2 :     map.impl_set_state (sid_y, 0, sid_z);
    1314                 :          2 :     ASSERT_EQ (map.get_state (sid_y), 0);
    1315                 :            : 
    1316                 :          2 :     map.impl_set_state (sid_x, 0, sid_z);
    1317                 :          2 :     ASSERT_EQ (map.get_state (sid_x), 0);
    1318                 :          2 :     ASSERT_TRUE (map.is_empty_p ());
    1319                 :            :   }
    1320                 :            : 
    1321                 :            :   /* Test setting states via equivalence classes.  */
    1322                 :          2 :   {
    1323                 :          2 :     region_model model;
    1324                 :          2 :     svalue_id sid_x = model.get_rvalue (x, NULL);
    1325                 :          2 :     svalue_id sid_y = model.get_rvalue (y, NULL);
    1326                 :          2 :     svalue_id sid_z = model.get_rvalue (z, NULL);
    1327                 :            : 
    1328                 :          4 :     sm_state_map map;
    1329                 :          2 :     ASSERT_TRUE (map.is_empty_p ());
    1330                 :          2 :     ASSERT_EQ (map.get_state (sid_x), 0);
    1331                 :          2 :     ASSERT_EQ (map.get_state (sid_y), 0);
    1332                 :            : 
    1333                 :          2 :     model.add_constraint (x, EQ_EXPR, y, NULL);
    1334                 :            : 
    1335                 :            :     /* Setting x to a state should also update y, as they
    1336                 :            :        are in the same equivalence class.  */
    1337                 :          2 :     map.set_state (&model, sid_x, 5, sid_z);
    1338                 :          2 :     ASSERT_EQ (map.get_state (sid_x), 5);
    1339                 :          2 :     ASSERT_EQ (map.get_state (sid_y), 5);
    1340                 :          2 :     ASSERT_EQ (map.get_origin (sid_x), sid_z);
    1341                 :          2 :     ASSERT_EQ (map.get_origin (sid_y), sid_z);
    1342                 :            :   }
    1343                 :            : 
    1344                 :            :   /* Test equality and hashing.  */
    1345                 :          2 :   {
    1346                 :          2 :     region_model model;
    1347                 :          2 :     svalue_id sid_y = model.get_rvalue (y, NULL);
    1348                 :          2 :     svalue_id sid_z = model.get_rvalue (z, NULL);
    1349                 :            : 
    1350                 :          4 :     sm_state_map map0;
    1351                 :          4 :     sm_state_map map1;
    1352                 :          4 :     sm_state_map map2;
    1353                 :            : 
    1354                 :          2 :     ASSERT_EQ (map0.hash (), map1.hash ());
    1355                 :          2 :     ASSERT_EQ (map0, map1);
    1356                 :            : 
    1357                 :          2 :     map1.impl_set_state (sid_y, 5, sid_z);
    1358                 :          2 :     ASSERT_NE (map0.hash (), map1.hash ());
    1359                 :          2 :     ASSERT_NE (map0, map1);
    1360                 :            : 
    1361                 :            :     /* Make the same change to map2.  */
    1362                 :          2 :     map2.impl_set_state (sid_y, 5, sid_z);
    1363                 :          2 :     ASSERT_EQ (map1.hash (), map2.hash ());
    1364                 :          2 :     ASSERT_EQ (map1, map2);
    1365                 :            :   }
    1366                 :            : 
    1367                 :            :   /* Equality and hashing shouldn't depend on ordering.  */
    1368                 :          2 :   {
    1369                 :          2 :     sm_state_map map0;
    1370                 :          4 :     sm_state_map map1;
    1371                 :          4 :     sm_state_map map2;
    1372                 :            : 
    1373                 :          2 :     ASSERT_EQ (map0.hash (), map1.hash ());
    1374                 :          2 :     ASSERT_EQ (map0, map1);
    1375                 :            : 
    1376                 :          2 :     map1.impl_set_state (svalue_id::from_int (14), 2, svalue_id::null ());
    1377                 :          2 :     map1.impl_set_state (svalue_id::from_int (16), 3, svalue_id::null ());
    1378                 :          2 :     map1.impl_set_state (svalue_id::from_int (1), 2, svalue_id::null ());
    1379                 :          2 :     map1.impl_set_state (svalue_id::from_int (9), 2, svalue_id::null ());
    1380                 :            : 
    1381                 :          2 :     map2.impl_set_state (svalue_id::from_int (1), 2, svalue_id::null ());
    1382                 :          2 :     map2.impl_set_state (svalue_id::from_int (16), 3, svalue_id::null ());
    1383                 :          2 :     map2.impl_set_state (svalue_id::from_int (14), 2, svalue_id::null ());
    1384                 :          2 :     map2.impl_set_state (svalue_id::from_int (9), 2, svalue_id::null ());
    1385                 :            : 
    1386                 :          2 :     ASSERT_EQ (map1.hash (), map2.hash ());
    1387                 :          2 :     ASSERT_EQ (map1, map2);
    1388                 :            :   }
    1389                 :            : 
    1390                 :            :   /* Test sm_state_map::remap_svalue_ids.  */
    1391                 :          2 :   {
    1392                 :          2 :     sm_state_map map;
    1393                 :          2 :     svalue_id sid_0 = svalue_id::from_int (0);
    1394                 :          2 :     svalue_id sid_1 = svalue_id::from_int (1);
    1395                 :          2 :     svalue_id sid_2 = svalue_id::from_int (2);
    1396                 :            : 
    1397                 :          2 :     map.impl_set_state (sid_0, 42, sid_2);
    1398                 :          2 :     ASSERT_EQ (map.get_state (sid_0), 42);
    1399                 :          2 :     ASSERT_EQ (map.get_origin (sid_0), sid_2);
    1400                 :          2 :     ASSERT_EQ (map.get_state (sid_1), 0);
    1401                 :          2 :     ASSERT_EQ (map.get_state (sid_2), 0);
    1402                 :            : 
    1403                 :            :     /* Apply a remapping to the IDs.  */
    1404                 :          4 :     svalue_id_map remapping (3);
    1405                 :          2 :     remapping.put (sid_0, sid_1);
    1406                 :          2 :     remapping.put (sid_1, sid_2);
    1407                 :          2 :     remapping.put (sid_2, sid_0);
    1408                 :          2 :     map.remap_svalue_ids (remapping);
    1409                 :            : 
    1410                 :            :     /* Verify that the IDs have been remapped.  */
    1411                 :          2 :     ASSERT_EQ (map.get_state (sid_1), 42);
    1412                 :          2 :     ASSERT_EQ (map.get_origin (sid_1), sid_0);
    1413                 :          2 :     ASSERT_EQ (map.get_state (sid_2), 0);
    1414                 :          2 :     ASSERT_EQ (map.get_state (sid_0), 0);
    1415                 :            :   }
    1416                 :            : 
    1417                 :            :   // TODO: coverage for purging
    1418                 :          2 : }
    1419                 :            : 
    1420                 :            : /* Verify that program_state::dump_to_pp works as expected.  */
    1421                 :            : 
    1422                 :            : static void
    1423                 :          2 : test_program_state_dumping ()
    1424                 :            : {
    1425                 :            :   /* Create a program_state for a global ptr "p" that has
    1426                 :            :      malloc sm-state, pointing to a region on the heap.  */
    1427                 :          2 :   tree p = build_global_decl ("p", ptr_type_node);
    1428                 :            : 
    1429                 :          2 :   state_machine *sm = make_malloc_state_machine (NULL);
    1430                 :          2 :   const state_machine::state_t UNCHECKED_STATE
    1431                 :          2 :     = sm->get_state_by_name ("unchecked");
    1432                 :          4 :   auto_delete_vec <state_machine> checkers;
    1433                 :          2 :   checkers.safe_push (sm);
    1434                 :          2 :   extrinsic_state ext_state (checkers);
    1435                 :            : 
    1436                 :          2 :   program_state s (ext_state);
    1437                 :          2 :   region_model *model = s.m_region_model;
    1438                 :          2 :   region_id new_rid = model->add_new_malloc_region ();
    1439                 :          2 :   svalue_id ptr_sid
    1440                 :          2 :       = model->get_or_create_ptr_svalue (ptr_type_node, new_rid);
    1441                 :          2 :   model->set_value (model->get_lvalue (p, NULL),
    1442                 :            :                     ptr_sid, NULL);
    1443                 :          2 :   sm_state_map *smap = s.m_checker_states[0];
    1444                 :            : 
    1445                 :          2 :   smap->impl_set_state (ptr_sid, UNCHECKED_STATE, svalue_id::null ());
    1446                 :          2 :   ASSERT_EQ (smap->get_state (ptr_sid), UNCHECKED_STATE);
    1447                 :            : 
    1448                 :          2 :   ASSERT_DUMP_EQ
    1449                 :            :     (s, ext_state, false,
    1450                 :            :      "rmodel: r0: {kind: `root', parent: null, sval: null}\n"
    1451                 :            :      "|-heap: r1: {kind: `heap', parent: r0, sval: sv0}\n"
    1452                 :            :      "|  |: sval: sv0: {poisoned: uninit}\n"
    1453                 :            :      "|  `-r2: {kind: `symbolic', parent: r1, sval: null, possibly_null: true}\n"
    1454                 :            :      "`-globals: r3: {kind: `globals', parent: r0, sval: null, map: {`p': r4}}\n"
    1455                 :            :      "  `-`p': r4: {kind: `primitive', parent: r3, sval: sv1, type: `void *'}\n"
    1456                 :            :      "    |: sval: sv1: {type: `void *', &r2}\n"
    1457                 :            :      "    |: type: `void *'\n"
    1458                 :            :      "svalues:\n"
    1459                 :            :      "  sv0: {poisoned: uninit}\n"
    1460                 :            :      "  sv1: {type: `void *', &r2}\n"
    1461                 :            :      "constraint manager:\n"
    1462                 :            :      "  equiv classes:\n"
    1463                 :            :      "  constraints:\n"
    1464                 :            :      "malloc: {sv1: unchecked (`p')}\n");
    1465                 :            : 
    1466                 :          2 :   ASSERT_DUMP_EQ (s, ext_state, true,
    1467                 :            :                   "rmodel: p: &r2 malloc: {sv1: unchecked (`p')}");
    1468                 :          2 : }
    1469                 :            : 
    1470                 :            : /* Verify that program_state::dump_to_pp works for string literals.  */
    1471                 :            : 
    1472                 :            : static void
    1473                 :          2 : test_program_state_dumping_2 ()
    1474                 :            : {
    1475                 :            :     /* Create a program_state for a global ptr "p" that points to
    1476                 :            :        a string constant.  */
    1477                 :          2 :   tree p = build_global_decl ("p", ptr_type_node);
    1478                 :            : 
    1479                 :          2 :   tree string_cst_ptr = build_string_literal (4, "foo");
    1480                 :            : 
    1481                 :          4 :   auto_delete_vec <state_machine> checkers;
    1482                 :          2 :   extrinsic_state ext_state (checkers);
    1483                 :            : 
    1484                 :          2 :   program_state s (ext_state);
    1485                 :          2 :   region_model *model = s.m_region_model;
    1486                 :          2 :   region_id p_rid = model->get_lvalue (p, NULL);
    1487                 :          2 :   svalue_id str_sid = model->get_rvalue (string_cst_ptr, NULL);
    1488                 :          2 :   model->set_value (p_rid, str_sid, NULL);
    1489                 :            : 
    1490                 :          2 :   ASSERT_DUMP_EQ
    1491                 :            :     (s, ext_state, false,
    1492                 :            :      "rmodel: r0: {kind: `root', parent: null, sval: null}\n"
    1493                 :            :      "|-globals: r1: {kind: `globals', parent: r0, sval: null, map: {`p': r2}}\n"
    1494                 :            :      "|  `-`p': r2: {kind: `primitive', parent: r1, sval: sv3, type: `void *'}\n"
    1495                 :            :      "|    |: sval: sv3: {type: `void *', &r4}\n"
    1496                 :            :      "|    |: type: `void *'\n"
    1497                 :            :      "`-r3: {kind: `array', parent: r0, sval: sv0, type: `const char[4]', array: {[0]: r4}}\n"
    1498                 :            :      "  |: sval: sv0: {type: `const char[4]', `\"foo\"'}\n"
    1499                 :            :      "  |: type: `const char[4]'\n"
    1500                 :            :      "  `-[0]: r4: {kind: `primitive', parent: r3, sval: null, type: `const char'}\n"
    1501                 :            :      "    |: type: `const char'\n"
    1502                 :            :      "svalues:\n"
    1503                 :            :      "  sv0: {type: `const char[4]', `\"foo\"'}\n"
    1504                 :            :      "  sv1: {type: `int', `0'}\n"
    1505                 :            :      "  sv2: {type: `const char *', &r4}\n"
    1506                 :            :      "  sv3: {type: `void *', &r4}\n"
    1507                 :            :      "constraint manager:\n"
    1508                 :            :      "  equiv classes:\n"
    1509                 :            :      "  constraints:\n");
    1510                 :            : 
    1511                 :          2 :   ASSERT_DUMP_EQ (s, ext_state, true,
    1512                 :            :                   "rmodel: p: &\"foo\"[0]");
    1513                 :          2 : }
    1514                 :            : 
    1515                 :            : /* Verify that program_states with identical sm-state can be merged,
    1516                 :            :    and that the merged program_state preserves the sm-state.  */
    1517                 :            : 
    1518                 :            : static void
    1519                 :          2 : test_program_state_merging ()
    1520                 :            : {
    1521                 :            :   /* Create a program_state for a global ptr "p" that has
    1522                 :            :      malloc sm-state, pointing to a region on the heap.  */
    1523                 :          2 :   tree p = build_global_decl ("p", ptr_type_node);
    1524                 :            : 
    1525                 :          4 :   auto_delete_vec <state_machine> checkers;
    1526                 :          2 :   checkers.safe_push (make_malloc_state_machine (NULL));
    1527                 :          2 :   extrinsic_state ext_state (checkers);
    1528                 :            : 
    1529                 :          2 :   program_state s0 (ext_state);
    1530                 :          4 :   impl_region_model_context ctxt (&s0, NULL, ext_state);
    1531                 :            : 
    1532                 :          2 :   region_model *model0 = s0.m_region_model;
    1533                 :          2 :   region_id new_rid = model0->add_new_malloc_region ();
    1534                 :          2 :   svalue_id ptr_sid
    1535                 :          2 :       = model0->get_or_create_ptr_svalue (ptr_type_node, new_rid);
    1536                 :          2 :   model0->set_value (model0->get_lvalue (p, &ctxt),
    1537                 :            :                      ptr_sid, &ctxt);
    1538                 :          2 :   sm_state_map *smap = s0.m_checker_states[0];
    1539                 :          2 :   const state_machine::state_t TEST_STATE = 3;
    1540                 :          2 :   smap->impl_set_state (ptr_sid, TEST_STATE, svalue_id::null ());
    1541                 :          2 :   ASSERT_EQ (smap->get_state (ptr_sid), TEST_STATE);
    1542                 :            : 
    1543                 :          2 :   model0->canonicalize (&ctxt);
    1544                 :            : 
    1545                 :            :   /* Verify that canonicalization preserves sm-state.  */
    1546                 :          2 :   ASSERT_EQ (smap->get_state (model0->get_rvalue (p, NULL)), TEST_STATE);
    1547                 :            : 
    1548                 :            :   /* Make a copy of the program_state.  */
    1549                 :          4 :   program_state s1 (s0);
    1550                 :          2 :   ASSERT_EQ (s0, s1);
    1551                 :            : 
    1552                 :            :   /* We have two identical states with "p" pointing to a heap region
    1553                 :            :      with the given sm-state.
    1554                 :            :      They ought to be mergeable, preserving the sm-state.  */
    1555                 :          2 :   program_state merged (ext_state);
    1556                 :          2 :   ASSERT_TRUE (s0.can_merge_with_p (s1, ext_state, &merged));
    1557                 :          2 :   merged.validate (ext_state);
    1558                 :            : 
    1559                 :            :   /* Verify that the merged state has the sm-state for "p".  */
    1560                 :          2 :   region_model *merged_model = merged.m_region_model;
    1561                 :          2 :   sm_state_map *merged_smap = merged.m_checker_states[0];
    1562                 :          2 :   ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, NULL)),
    1563                 :            :              TEST_STATE);
    1564                 :            : 
    1565                 :            :   /* Try canonicalizing.  */
    1566                 :          4 :   impl_region_model_context merged_ctxt (&merged, NULL, ext_state);
    1567                 :          2 :   merged.m_region_model->canonicalize (&merged_ctxt);
    1568                 :          2 :   merged.validate (ext_state);
    1569                 :            : 
    1570                 :            :   /* Verify that the merged state still has the sm-state for "p".  */
    1571                 :          2 :   ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, NULL)),
    1572                 :            :              TEST_STATE);
    1573                 :            : 
    1574                 :            :   /* After canonicalization, we ought to have equality with the inputs.  */
    1575                 :          2 :   ASSERT_EQ (s0, merged);
    1576                 :          2 : }
    1577                 :            : 
    1578                 :            : /* Verify that program_states with different global-state in an sm-state
    1579                 :            :    can't be merged.  */
    1580                 :            : 
    1581                 :            : static void
    1582                 :          2 : test_program_state_merging_2 ()
    1583                 :            : {
    1584                 :          4 :   auto_delete_vec <state_machine> checkers;
    1585                 :          2 :   checkers.safe_push (make_signal_state_machine (NULL));
    1586                 :          2 :   extrinsic_state ext_state (checkers);
    1587                 :            : 
    1588                 :          4 :   program_state s0 (ext_state);
    1589                 :          2 :   {
    1590                 :          2 :     sm_state_map *smap0 = s0.m_checker_states[0];
    1591                 :          2 :     const state_machine::state_t TEST_STATE_0 = 0;
    1592                 :          2 :     smap0->set_global_state (TEST_STATE_0);
    1593                 :          2 :     ASSERT_EQ (smap0->get_global_state (), TEST_STATE_0);
    1594                 :            :   }
    1595                 :            : 
    1596                 :          4 :   program_state s1 (ext_state);
    1597                 :          2 :   {
    1598                 :          2 :     sm_state_map *smap1 = s1.m_checker_states[0];
    1599                 :          2 :     const state_machine::state_t TEST_STATE_1 = 1;
    1600                 :          2 :     smap1->set_global_state (TEST_STATE_1);
    1601                 :          2 :     ASSERT_EQ (smap1->get_global_state (), TEST_STATE_1);
    1602                 :            :   }
    1603                 :            : 
    1604                 :          2 :   ASSERT_NE (s0, s1);
    1605                 :            : 
    1606                 :            :   /* They ought to not be mergeable.  */
    1607                 :          2 :   program_state merged (ext_state);
    1608                 :          2 :   ASSERT_FALSE (s0.can_merge_with_p (s1, ext_state, &merged));
    1609                 :          2 : }
    1610                 :            : 
    1611                 :            : /* Run all of the selftests within this file.  */
    1612                 :            : 
    1613                 :            : void
    1614                 :          2 : analyzer_program_state_cc_tests ()
    1615                 :            : {
    1616                 :          2 :   test_sm_state_map ();
    1617                 :          2 :   test_program_state_dumping ();
    1618                 :          2 :   test_program_state_dumping_2 ();
    1619                 :          2 :   test_program_state_merging ();
    1620                 :          2 :   test_program_state_merging_2 ();
    1621                 :          2 : }
    1622                 :            : 
    1623                 :            : } // namespace selftest
    1624                 :            : 
    1625                 :            : #endif /* CHECKING_P */
    1626                 :            : 
    1627                 :            : } // namespace ana
    1628                 :            : 
    1629                 :            : #endif /* #if ENABLE_ANALYZER */

Generated by: LCOV version 1.0

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 --enable-host-shared. GCC test suite is run with the built compiler.