[42/49] analyzer: new files: program-state.{cc|h}
diff mbox series

Message ID 1573867416-55618-43-git-send-email-dmalcolm@redhat.com
State New
Headers show
Series
  • RFC: Add a static analysis framework to GCC
Related show

Commit Message

David Malcolm Nov. 16, 2019, 1:23 a.m. UTC
This patch introduces classes for tracking the state at a particular
path of analysis.

gcc/ChangeLog:
	* analyzer/program-state.cc: New file.
	* analyzer/program-state.h: New file.
---
 gcc/analyzer/program-state.cc | 1284 +++++++++++++++++++++++++++++++++++++++++
 gcc/analyzer/program-state.h  |  360 ++++++++++++
 2 files changed, 1644 insertions(+)
 create mode 100644 gcc/analyzer/program-state.cc
 create mode 100644 gcc/analyzer/program-state.h

Patch
diff mbox series

diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc
new file mode 100644
index 0000000..ae15795
--- /dev/null
+++ b/gcc/analyzer/program-state.cc
@@ -0,0 +1,1284 @@ 
+/* Classes for representing the state of interest at a given path of analysis.
+   Copyright (C) 2019 Free Software Foundation, Inc.
+   Contributed by David Malcolm <dmalcolm@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "gcc-plugin.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tree.h"
+#include "diagnostic.h"
+#include "analyzer/analyzer.h"
+#include "analyzer/program-state.h"
+#include "analyzer/constraint-manager.h"
+#include "analyzer/exploded-graph.h"
+#include "analyzer/state-purge.h"
+#include "analyzer/analyzer-selftests.h"
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class sm_state_map.  */
+
+/* Clone the sm_state_map.  */
+
+sm_state_map *
+sm_state_map::clone () const
+{
+  return new sm_state_map (*this);
+}
+
+/* Clone this sm_state_map, remapping all svalue_ids within it with ID_MAP.
+
+   Return NULL if there are any svalue_ids that have sm-state for which
+   ID_MAP maps them to svalue_id::null (and thus the clone would have lost
+   the sm-state information). */
+
+sm_state_map *
+sm_state_map::clone_with_remapping (const one_way_svalue_id_map &id_map) const
+{
+  sm_state_map *result = new sm_state_map ();
+  for (typename map_t::iterator iter = m_map.begin ();
+       iter != m_map.end ();
+       ++iter)
+    {
+      svalue_id sid = (*iter).first;
+      gcc_assert (!sid.null_p ());
+      entry_t e = (*iter).second;
+      /* TODO: what should we do if the origin maps from non-null to null?
+	 Is that loss of information acceptable?  */
+      id_map.update (&e.m_origin);
+
+      svalue_id new_sid = id_map.get_dst_for_src (sid);
+      if (new_sid.null_p ())
+	{
+	  delete result;
+	  return NULL;
+	}
+      result->m_map.put (new_sid, e);
+    }
+  return result;
+}
+
+/* Print this sm_state_map (for SM) to PP.  */
+
+void
+sm_state_map::print (const state_machine &sm, pretty_printer *pp) const
+{
+  pp_string (pp, "{");
+  for (typename map_t::iterator iter = m_map.begin ();
+       iter != m_map.end ();
+       ++iter)
+    {
+      if (iter != m_map.begin ())
+	pp_string (pp, ", ");
+      svalue_id sid = (*iter).first;
+      sid.print (pp);
+
+      entry_t e = (*iter).second;
+      pp_printf (pp, ": %s (origin: ",
+		 sm.get_state_name (e.m_state));
+      e.m_origin.print (pp);
+      pp_string (pp, ")");
+    }
+  pp_string (pp, "}");
+}
+
+/* Dump this object (for SM) to stderr.  */
+
+DEBUG_FUNCTION void
+sm_state_map::dump (const state_machine &sm) const
+{
+  pretty_printer pp;
+  pp_show_color (&pp) = pp_show_color (global_dc->printer);
+  pp.buffer->stream = stderr;
+  print (sm, &pp);
+  pp_newline (&pp);
+  pp_flush (&pp);
+}
+
+/* Return true if no states have been set within this map
+   (all expressions are for the start state).  */
+
+bool
+sm_state_map::is_empty_p () const
+{
+  return m_map.elements () == 0;
+}
+
+/* Generate a hash value for this sm_state_map.  */
+
+hashval_t
+sm_state_map::hash () const
+{
+  hashval_t result = 0;
+
+  /* Accumulate the result by xoring a hash for each slot, so that the
+     result doesn't depend on the ordering of the slots in the map.  */
+
+  for (typename map_t::iterator iter = m_map.begin ();
+       iter != m_map.end ();
+       ++iter)
+    {
+      inchash::hash hstate;
+      inchash::add ((*iter).first, hstate);
+      entry_t e = (*iter).second;
+      hstate.add_int (e.m_state);
+      inchash::add (e.m_origin, hstate);
+      result ^= hstate.end ();
+    }
+
+  return result;
+}
+
+/* Equality operator for sm_state_map.  */
+
+bool
+sm_state_map::operator== (const sm_state_map &other) const
+{
+  if (m_map.elements () != other.m_map.elements ())
+    return false;
+
+  for (typename map_t::iterator iter = m_map.begin ();
+       iter != m_map.end ();
+       ++iter)
+    {
+      svalue_id sid = (*iter).first;
+      entry_t e = (*iter).second;
+      entry_t *other_slot = const_cast <map_t &> (other.m_map).get (sid);
+      if (other_slot == NULL)
+	return false;
+      if (e != *other_slot)
+	return false;
+    }
+
+  gcc_checking_assert (hash () == other.hash ());
+
+  return true;
+}
+
+/* Get the state of SID within this object.
+   States default to the start state.  */
+
+state_machine::state_t
+sm_state_map::get_state (svalue_id sid) const
+{
+  gcc_assert (!sid.null_p ());
+
+  if (entry_t *slot
+      = const_cast <map_t &> (m_map).get (sid))
+    return slot->m_state;
+  else
+    return 0;
+}
+
+/* Get the "origin" svalue_id for any state of SID.  */
+
+svalue_id
+sm_state_map::get_origin (svalue_id sid) const
+{
+  gcc_assert (!sid.null_p ());
+
+  entry_t *slot
+    = const_cast <map_t &> (m_map).get (sid);
+  if (slot)
+    return slot->m_origin;
+  else
+    return svalue_id::null ();
+}
+
+/* Set the state of SID within MODEL to STATE, recording that
+   the state came from ORIGIN.  */
+
+void
+sm_state_map::set_state (region_model *model,
+			 svalue_id sid,
+			 state_machine::state_t state,
+			 svalue_id origin)
+{
+  if (model == NULL)
+    return;
+  equiv_class &ec = model->get_constraints ()->get_equiv_class (sid);
+  set_state (ec, state, origin);
+
+  /* Also do it for all svalues that are equal via non-cm, so that
+     e.g. (void *)&r and (foo *)&r transition together.  */
+  for (unsigned i = 0; i < model->get_num_svalues (); i++)
+    {
+      svalue_id other_sid = svalue_id::from_int (i);
+      if (other_sid == sid)
+	continue;
+
+      tristate eq = model->eval_condition_without_cm (sid, EQ_EXPR, other_sid);
+      if (eq.is_true ())
+	impl_set_state (other_sid, state, origin);
+    }
+}
+
+/* Set the state of EC to STATE, recording that the state came from
+   ORIGIN.  */
+
+void
+sm_state_map::set_state (const equiv_class &ec,
+			 state_machine::state_t state,
+			 svalue_id origin)
+{
+  int i;
+  svalue_id *sid;
+  FOR_EACH_VEC_ELT (ec.m_vars, i, sid)
+    impl_set_state (*sid, state, origin);
+}
+
+/* Set state of PV to STATE, bypassing equivalence classes.  */
+
+void
+sm_state_map::impl_set_state (svalue_id sid, state_machine::state_t state,
+			      svalue_id origin)
+{
+  /* Special-case state 0 as the default value.  */
+  if (state == 0)
+    {
+      if (m_map.get (sid))
+	m_map.remove (sid);
+      return;
+    }
+  gcc_assert (!sid.null_p ());
+  m_map.put (sid, entry_t (state, origin));
+}
+
+/* Handle CALL to unknown FNDECL with an unknown function body, which
+   could do anything to the states passed to it.
+   Clear any state for SM for the params and any LHS.
+   Note that the function might be known to other state machines, but
+   not to this one.  */
+
+void
+sm_state_map::purge_for_unknown_fncall (const exploded_graph &eg,
+					const state_machine &sm,
+					const gcall *call,
+					tree fndecl,
+					region_model *new_model)
+{
+  if (fndecl)
+    eg.log ("function %qE is unknown to checker %qs",
+	    fndecl, sm.get_name ());
+  else
+    eg.log ("unknown function pointer for checker %qs",
+	    sm.get_name ());
+
+  /* Purge any state for parms.  */
+  tree iter_param_types = NULL_TREE;
+  if (fndecl)
+    iter_param_types = TYPE_ARG_TYPES (TREE_TYPE (fndecl));
+  for (unsigned arg_idx = 0; arg_idx < gimple_call_num_args (call); arg_idx++)
+    {
+      /* Track expected param type, where available.  */
+      if (iter_param_types)
+	{
+	  tree param_type = TREE_VALUE (iter_param_types);
+	  gcc_assert (param_type);
+	  iter_param_types = TREE_CHAIN (iter_param_types);
+
+	  /* Don't purge state if it was passed as a const pointer
+	     e.g. for things like strlen (PTR).  */
+	  if (TREE_CODE (param_type) == POINTER_TYPE)
+	    if (TYPE_READONLY (TREE_TYPE (param_type)))
+	      continue;
+	}
+      tree parm = gimple_call_arg (call, arg_idx);
+      svalue_id parm_sid = new_model->get_rvalue (parm, NULL);
+      set_state (new_model, parm_sid, 0, svalue_id::null ());
+
+      /* Also clear sm-state from svalue_ids that are passed via a
+	 pointer.  */
+      if (TREE_CODE (parm) == ADDR_EXPR)
+	{
+	  tree pointee = TREE_OPERAND (parm, 0);
+	  svalue_id parm_sid = new_model->get_rvalue (pointee, NULL);
+	  set_state (new_model, parm_sid, 0, svalue_id::null ());
+	}
+    }
+
+  /* Purge any state for any LHS.  */
+  if (tree lhs = gimple_call_lhs (call))
+    {
+      svalue_id lhs_sid = new_model->get_rvalue (lhs, NULL);
+      set_state (new_model, lhs_sid, 0, svalue_id::null ());
+    }
+}
+
+/* Update this map based on MAP.  */
+
+void
+sm_state_map::remap_svalue_ids (const svalue_id_map &map)
+{
+  map_t tmp_map;
+
+  /* Build an intermediate map, using the new sids.  */
+  for (typename map_t::iterator iter = m_map.begin ();
+       iter != m_map.end ();
+       ++iter)
+    {
+      svalue_id sid = (*iter).first;
+      entry_t e = (*iter).second;
+
+      map.update (&sid);
+      map.update (&e.m_origin);
+      tmp_map.put (sid, e);
+    }
+
+  /* Clear the existing values.  */
+  m_map.empty ();
+
+  /* Copy over from intermediate map.  */
+  for (typename map_t::iterator iter = tmp_map.begin ();
+       iter != tmp_map.end ();
+       ++iter)
+    {
+      svalue_id sid = (*iter).first;
+      entry_t e = (*iter).second;
+
+      impl_set_state (sid, e.m_state, e.m_origin);
+    }
+}
+
+/* Purge any state for svalue_ids >= FIRST_UNUSED_SID.
+   If !SM::can_purge_p, then report the state as leaking,
+   using SM_IDX, CTXT, and MAP.
+   Return the number of states that were purged.  */
+
+int
+sm_state_map::on_svalue_purge (const state_machine &sm,
+			       int sm_idx,
+			       svalue_id first_unused_sid,
+			       const svalue_id_map &map,
+			       impl_region_model_context *ctxt)
+{
+  /* TODO: ideally remove the slot directly; for now
+     do it in two stages.  */
+  auto_vec<svalue_id> to_remove;
+  for (typename map_t::iterator iter = m_map.begin ();
+       iter != m_map.end ();
+       ++iter)
+    {
+      svalue_id dst_sid ((*iter).first);
+      if (dst_sid.as_int () >= first_unused_sid.as_int ())
+	{
+	  /* Complain about leaks here.  */
+	  entry_t e = (*iter).second;
+
+	  if (!sm.can_purge_p (e.m_state))
+	    ctxt->on_state_leak (sm, sm_idx, dst_sid, first_unused_sid,
+				 map, e.m_state);
+
+	  to_remove.safe_push (dst_sid);
+	}
+    }
+
+  int i;
+  svalue_id *dst_sid;
+  FOR_EACH_VEC_ELT (to_remove, i, dst_sid)
+    m_map.remove (*dst_sid);
+
+  return to_remove.length ();
+}
+
+/* Set the state of CHILD_SID to that of PARENT_SID.  */
+
+void
+sm_state_map::on_inherited_svalue (svalue_id parent_sid,
+				   svalue_id child_sid)
+{
+  state_machine::state_t state = get_state (parent_sid);
+  impl_set_state (child_sid, state, parent_sid);
+}
+
+/* Set the state of DST_SID to that of SRC_SID.  */
+
+void
+sm_state_map::on_cast (svalue_id src_sid,
+		       svalue_id dst_sid)
+{
+  state_machine::state_t state = get_state (src_sid);
+  impl_set_state (dst_sid, state, get_origin (src_sid));
+}
+
+/* Assert that this object is sane.  */
+
+void
+sm_state_map::validate (const state_machine &sm,
+			int num_svalues) const
+{
+  /* Skip this in a release build.  */
+#if !CHECKING_P
+  return;
+#endif
+
+  for (typename map_t::iterator iter = m_map.begin ();
+       iter != m_map.end ();
+       ++iter)
+    {
+      svalue_id sid = (*iter).first;
+      entry_t e = (*iter).second;
+
+      gcc_assert (sid.as_int () < num_svalues);
+      sm.validate (e.m_state);
+      gcc_assert (e.m_origin.as_int () < num_svalues);
+    }
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class program_state.  */
+
+/* program_state's ctor.  */
+
+program_state::program_state (const extrinsic_state &ext_state)
+: m_region_model (new region_model ()),
+  m_checker_states (ext_state.m_checkers.length ())
+{
+  int num_states = ext_state.m_checkers.length ();
+  for (int i = 0; i < num_states; i++)
+    m_checker_states.quick_push (new sm_state_map ());
+}
+
+/* program_state's copy ctor.  */
+
+program_state::program_state (const program_state &other)
+: m_region_model (new region_model (*other.m_region_model)),
+  m_checker_states (other.m_checker_states.length ())
+{
+  int i;
+  sm_state_map *smap;
+  FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
+    m_checker_states.quick_push (smap->clone ());
+}
+
+/* program_state's assignment operator.  */
+
+program_state&
+program_state::operator= (const program_state &other)
+{
+  delete m_region_model;
+  m_region_model = new region_model (*other.m_region_model);
+
+  int i;
+  sm_state_map *smap;
+  FOR_EACH_VEC_ELT (m_checker_states, i, smap)
+    delete smap;
+  m_checker_states.truncate (0);
+  gcc_assert (m_checker_states.space (other.m_checker_states.length ()));
+
+  FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
+    m_checker_states.quick_push (smap->clone ());
+
+  return *this;
+}
+
+#if __cplusplus >= 201103
+/* Move constructor for program_state (when building with C++11).  */
+program_state::program_state (program_state &&other)
+: m_region_model (other.m_region_model),
+  m_checker_states (other.m_checker_states.length ())
+{
+  other.m_region_model = NULL;
+
+  int i;
+  sm_state_map *smap;
+  FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
+    m_checker_states.quick_push (smap);
+  other.m_checker_states.truncate (0);
+}
+#endif
+
+/* program_state's dtor.  */
+
+program_state::~program_state ()
+{
+  delete m_region_model;
+}
+
+/* Generate a hash value for this program_state.  */
+
+hashval_t
+program_state::hash () const
+{
+  hashval_t result = m_region_model->hash ();
+
+  int i;
+  sm_state_map *smap;
+  FOR_EACH_VEC_ELT (m_checker_states, i, smap)
+    result ^= smap->hash ();
+  return result;
+}
+
+/* Equality operator for program_state.
+   All parts of the program_state (region model, checker states) must
+   equal their counterparts in OTHER for the two program_states to be
+   considered equal.  */
+
+bool
+program_state::operator== (const program_state &other) const
+{
+  if (!(*m_region_model == *other.m_region_model))
+    return false;
+
+  int i;
+  sm_state_map *smap;
+  FOR_EACH_VEC_ELT (m_checker_states, i, smap)
+    if (!(*smap == *other.m_checker_states[i]))
+      return false;
+
+  gcc_checking_assert (hash () == other.hash ());
+
+  return true;
+}
+
+/* Print a compact representation of this state to PP.  */
+
+void
+program_state::print (const extrinsic_state &ext_state,
+		      pretty_printer *pp) const
+{
+  pp_printf (pp, "rmodel: ");
+  m_region_model->print (pp);
+  pp_newline (pp);
+
+  int i;
+  sm_state_map *smap;
+  FOR_EACH_VEC_ELT (m_checker_states, i, smap)
+    {
+      if (!smap->is_empty_p ())
+	{
+	  pp_printf (pp, "%s: ", ext_state.get_name (i));
+	  smap->print (ext_state.get_sm (i), pp);
+	  pp_newline (pp);
+	}
+    }
+}
+
+/* Dump a multiline representation of this state to PP.  */
+
+void
+program_state::dump_to_pp (const extrinsic_state &ext_state,
+			   bool summarize,
+			   pretty_printer *pp) const
+{
+  pp_printf (pp, "rmodel: ");
+  m_region_model->dump_to_pp (pp, summarize);
+
+  int i;
+  sm_state_map *smap;
+  FOR_EACH_VEC_ELT (m_checker_states, i, smap)
+    {
+      if (!smap->is_empty_p ())
+	{
+	  pp_printf (pp, "%s: ", ext_state.get_name (i));
+	  smap->print (ext_state.get_sm (i), pp);
+	  pp_newline (pp);
+	}
+    }
+}
+
+/* Dump a multiline representation of this state to OUTF.  */
+
+void
+program_state::dump_to_file (const extrinsic_state &ext_state,
+			     bool summarize,
+			     FILE *outf) const
+{
+  pretty_printer pp;
+  pp_format_decoder (&pp) = default_tree_printer;
+  if (outf == stderr)
+    pp_show_color (&pp) = pp_show_color (global_dc->printer);
+  pp.buffer->stream = outf;
+  dump_to_pp (ext_state, summarize, &pp);
+  pp_flush (&pp);
+}
+
+/* Dump a multiline representation of this state to stderr.  */
+
+DEBUG_FUNCTION void
+program_state::dump (const extrinsic_state &ext_state,
+		     bool summarize) const
+{
+  dump_to_file (ext_state, summarize, stderr);
+}
+
+/* Determine if following edge SUCC from ENODE is valid within the graph EG
+   and update this state accordingly in-place.
+
+   Return true if the edge can be followed, or false otherwise.
+
+   Check for relevant conditionals and switch-values for conditionals
+   and switch statements, adding the relevant conditions to this state.
+   Push/pop frames for interprocedural edges and update params/returned
+   values.
+
+   This is the "state" half of exploded_node::on_edge.  */
+
+bool
+program_state::on_edge (exploded_graph &eg,
+			const exploded_node &enode,
+			const superedge *succ,
+			state_change *change)
+{
+  /* Update state.  */
+  const program_point &point = enode.get_point ();
+  const gimple *last_stmt = point.get_supernode ()->get_last_stmt ();
+
+  /* For conditionals and switch statements, add the
+     relevant conditions (for the specific edge) to new_state;
+     skip edges for which the resulting constraints
+     are impossible.
+     This also updates frame information for call/return superedges.
+     Adding the relevant conditions for the edge could also trigger
+     sm-state transitions (e.g. transitions due to ptrs becoming known
+     to be NULL or non-NULL) */
+
+  impl_region_model_context ctxt (eg, &enode,
+				  &enode.get_state (),
+				  this, change,
+				  last_stmt);
+  if (!m_region_model->maybe_update_for_edge (*succ,
+					      last_stmt,
+					      &ctxt))
+    {
+      eg.log ("edge to SN: %i is impossible due to region_model constraints",
+	      succ->m_dest->m_index);
+      return false;
+    }
+
+  return true;
+}
+
+/* Generate a simpler version of THIS, discarding state that's no longer
+   relevant at POINT.
+   The idea is that we're more likely to be able to consolidate
+   multiple (point, state) into single exploded_nodes if we discard
+   irrelevant state (e.g. at the end of functions).
+
+   Retain state affected by CHANGE, to make it easier to generate
+   state_change_events.  */
+
+program_state
+program_state::prune_for_point (exploded_graph &eg,
+				const program_point &point,
+				state_change *change) const
+{
+  LOG_SCOPE (eg.get_logger ());
+
+  function *fun = point.get_function ();
+  if (!fun)
+    return *this;
+
+  program_state new_state (*this);
+
+  purge_stats stats;
+
+  const state_purge_map *pm = eg.get_purge_map ();
+  if (pm)
+    {
+      region_id_set purgeable_ssa_regions (new_state.m_region_model);
+      region_id frame_rid
+	= new_state.m_region_model->get_current_frame_id ();
+      frame_region *frame
+	= new_state.m_region_model->get_region <frame_region>(frame_rid);
+
+      /* TODO: maybe move to a member of region_model?  */
+
+      auto_vec<tree> ssa_names_to_purge;
+      for (frame_region::map_t::iterator iter = frame->begin ();
+	   iter != frame->end ();
+	   ++iter)
+	{
+	  tree var = (*iter).first;
+	  region_id rid = (*iter).second;
+	  if (TREE_CODE (var) == SSA_NAME)
+	    {
+	      const state_purge_per_ssa_name &per_ssa
+		= pm->get_data_for_ssa_name (var);
+	      if (!per_ssa.needed_at_point_p (point.get_function_point ()))
+		{
+		  region *region
+		    = new_state.m_region_model->get_region (rid);
+		  svalue_id sid = region->get_value_direct ();
+		  if (!sid.null_p ())
+		    {
+		      if (!new_state.can_purge_p (eg.get_ext_state (), sid))
+			{
+			  /* (currently only state maps can keep things
+			     alive).  */
+			  eg.log ("not purging RID: %i for %qE"
+				  " (used by state map)",
+				  rid.as_int (), var);
+			  continue;
+			}
+
+		      /* Don't purge regions containing svalues that
+			 have a change of sm-state, to make it easier to
+			 generate state_change_event messages.  */
+		      if (change)
+			if (change->affects_p (sid))
+			  {
+			    eg.log ("not purging RID: %i for %qE"
+				    " (affected by change)",
+				    rid.as_int (), var);
+			    continue;
+			  }
+		    }
+		  purgeable_ssa_regions.add_region (rid);
+		  ssa_names_to_purge.safe_push (var);
+		  eg.log ("purging RID: %i for %qE", rid.as_int (), var);
+		  /* We also need to remove the region from the map.
+		     We're in mid-traversal, so the removal is done in
+		     unbind below.  */
+		}
+	    }
+	}
+
+      /* Unbind the regions from the frame's map of vars-to-regions.  */
+      unsigned i;
+      tree var;
+      FOR_EACH_VEC_ELT (ssa_names_to_purge, i, var)
+	frame->unbind (var);
+
+      /* Purge the regions.  Nothing should point to them, and they
+	 should have no children, as they are for SSA names.  */
+      new_state.m_region_model->purge_regions (purgeable_ssa_regions,
+					       &stats,
+					       eg.get_logger ());
+    }
+
+  /* Purge unused svalues.  */
+  // TODO: which enode to use, if any?
+  impl_region_model_context ctxt (eg, NULL,
+				  this,
+				  &new_state,
+				  change,
+				  NULL);
+  new_state.m_region_model->purge_unused_svalues (&stats, &ctxt);
+  eg.log ("num svalues purged: %i", stats.m_num_svalues);
+  eg.log ("num regions purged: %i", stats.m_num_regions);
+  eg.log ("num equiv_classes purged: %i", stats.m_num_equiv_classes);
+  eg.log ("num constraints purged: %i", stats.m_num_constraints);
+  eg.log ("num sm map items purged: %i", stats.m_num_client_items);
+
+  new_state.m_region_model->canonicalize (&ctxt);
+
+  return new_state;
+}
+
+/* Remap all svalue_ids in this state's m_checker_states according to MAP.
+   The svalues_ids in the region_model are assumed to already have been
+   remapped.  */
+
+void
+program_state::remap_svalue_ids (const svalue_id_map &map)
+{
+  int i;
+  sm_state_map *smap;
+  FOR_EACH_VEC_ELT (m_checker_states, i, smap)
+    smap->remap_svalue_ids (map);
+}
+
+/* Attempt to return a tree that represents SID, or return NULL_TREE.
+   Find the first region that stores the value (e.g. a local) and
+   generate a representative tree for it.  */
+
+tree
+program_state::get_representative_tree (svalue_id sid) const
+{
+  return m_region_model->get_representative_tree (sid);
+}
+
+/* Attempt to merge this state with OTHER, both using EXT_STATE.
+   Write the result to *OUT.
+   If the states were merged successfully, return true.  */
+
+bool
+program_state::can_merge_with_p (const program_state &other,
+				 const extrinsic_state &ext_state,
+				 program_state *out) const
+{
+  gcc_assert (out);
+
+  /* TODO:  initially I had an early reject here if there
+     are sm-differences between the states.  However, this was
+     falsely rejecting merger opportunities for states where the
+     only difference was in svalue_id ordering.  */
+
+  /* Attempt to merge the region_models.  */
+
+  svalue_id_merger_mapping sid_mapping (*m_region_model,
+					*other.m_region_model);
+  if (!m_region_model->can_merge_with_p (*other.m_region_model,
+					 out->m_region_model,
+					 &sid_mapping))
+    return false;
+
+  /* Copy m_checker_states to result, remapping svalue_ids using
+     sid_mapping.  */
+  int i;
+  sm_state_map *smap;
+  FOR_EACH_VEC_ELT (out->m_checker_states, i, smap)
+    delete smap;
+  out->m_checker_states.truncate (0);
+
+  /* Remap this and other's m_checker_states using sid_mapping.
+     Only merge states that have equality between the two end-results:
+     sm-state differences are likely to be interesting to end-users, and
+     hence are worth exploring as separate paths in the exploded graph.  */
+  FOR_EACH_VEC_ELT (m_checker_states, i, smap)
+    {
+      sm_state_map *other_smap = other.m_checker_states[i];
+
+      /* If clone_with_remapping returns NULL for one of the input smaps,
+	 then it has sm-state for an svalue_id where the svalue_id is
+	 being mapped to svalue_id::null in its sid_mapping, meaning that
+	 the svalue is to be dropped during the merger.  We don't want
+	 to lose sm-state during a state merger, so return false for these
+	 cases.  */
+      sm_state_map *remapped_a_smap
+	= smap->clone_with_remapping (sid_mapping.m_map_from_a_to_m);
+      if (!remapped_a_smap)
+	return false;
+      sm_state_map *remapped_b_smap
+	= other_smap->clone_with_remapping (sid_mapping.m_map_from_b_to_m);
+      if (!remapped_b_smap)
+	{
+	  delete remapped_a_smap;
+	  return false;
+	}
+
+      /* Both states have sm-state for the same values; now ensure that the
+	 states are equal.  */
+      if (*remapped_a_smap == *remapped_b_smap)
+	{
+	  out->m_checker_states.safe_push (remapped_a_smap);
+	  delete remapped_b_smap;
+	}
+      else
+	{
+	  /* Don't merge if there are sm-state differences.  */
+	  delete remapped_a_smap;
+	  delete remapped_b_smap;
+	  return false;
+	}
+    }
+
+  impl_region_model_context ctxt (out, NULL, ext_state);
+  out->m_region_model->canonicalize (&ctxt);
+
+  return true;
+}
+
+/* Assert that this object is valid.  */
+
+void
+program_state::validate (const extrinsic_state &ext_state) const
+{
+  /* Skip this in a release build.  */
+#if !CHECKING_P
+  return;
+#endif
+
+  m_region_model->validate ();
+  gcc_assert (m_checker_states.length () == ext_state.get_num_checkers ());
+  int sm_idx;
+  sm_state_map *smap;
+  FOR_EACH_VEC_ELT (m_checker_states, sm_idx, smap)
+    {
+      const state_machine &sm = ext_state.get_sm (sm_idx);
+      smap->validate (sm, m_region_model->get_num_svalues ());
+    }
+}
+
+/* Dump this sm_change to PP.  */
+
+void
+state_change::sm_change::dump (pretty_printer *pp,
+			       const extrinsic_state &ext_state) const
+{
+  const state_machine &sm = get_sm (ext_state);
+  pp_string (pp, "(");
+  m_new_sid.print (pp);
+  pp_printf (pp, ": %s: %qs -> %qs)",
+	     sm.get_name (),
+	     sm.get_state_name (m_old_state),
+	     sm.get_state_name (m_new_state));
+}
+
+/* Remap all svalue_ids in this change according to MAP.  */
+
+void
+state_change::sm_change::remap_svalue_ids (const svalue_id_map &map)
+{
+  map.update (&m_new_sid);
+}
+
+/* Purge any svalue_ids >= FIRST_UNUSED_SID.
+   Return the number of states that were purged.  */
+
+int
+state_change::sm_change::on_svalue_purge (svalue_id first_unused_sid)
+{
+  if (m_new_sid.as_int () >= first_unused_sid.as_int ())
+    {
+      m_new_sid = svalue_id::null ();
+      return 1;
+    }
+
+  return 0;
+}
+
+/* Assert that this object is sane.  */
+
+void
+state_change::sm_change::validate (const program_state &new_state) const
+{
+  m_new_sid.validate (*new_state.m_region_model);
+}
+
+/* state_change's ctor.  */
+
+state_change::state_change ()
+{
+}
+
+/* state_change's copy ctor.  */
+
+state_change::state_change (const state_change &other)
+: m_sm_changes (other.m_sm_changes.length ())
+{
+  unsigned i;
+  sm_change *change;
+  FOR_EACH_VEC_ELT (other.m_sm_changes, i, change)
+    m_sm_changes.quick_push (*change);
+}
+
+/* Record a state-machine state change.  */
+
+void
+state_change::add_sm_change (int sm_idx,
+			     svalue_id new_sid,
+			     state_machine::state_t old_state,
+			     state_machine::state_t new_state)
+{
+  m_sm_changes.safe_push (sm_change (sm_idx,
+				     new_sid,
+				     old_state, new_state));
+}
+
+/* Return true if SID (in the new state) was affected by any
+   sm-state changes.  */
+
+bool
+state_change::affects_p (svalue_id sid) const
+{
+  unsigned i;
+  sm_change *change;
+  FOR_EACH_VEC_ELT (m_sm_changes, i, change)
+    {
+      if (sid == change->m_new_sid)
+	return true;
+    }
+  return false;
+}
+
+/* Dump this state_change to PP.  */
+
+void
+state_change::dump (pretty_printer *pp,
+		    const extrinsic_state &ext_state) const
+{
+  unsigned i;
+  sm_change *change;
+  FOR_EACH_VEC_ELT (m_sm_changes, i, change)
+    {
+      if (i > 0)
+	pp_string (pp, ", ");
+      change->dump (pp, ext_state);
+    }
+}
+
+/* Dump this state_change to stderr.  */
+
+void
+state_change::dump (const extrinsic_state &ext_state) const
+{
+  pretty_printer pp;
+  pp_show_color (&pp) = pp_show_color (global_dc->printer);
+  pp.buffer->stream = stderr;
+  dump (&pp, ext_state);
+  pp_newline (&pp);
+  pp_flush (&pp);
+}
+
+/* Remap all svalue_ids in this state_change according to MAP.  */
+
+void
+state_change::remap_svalue_ids (const svalue_id_map &map)
+{
+  unsigned i;
+  sm_change *change;
+  FOR_EACH_VEC_ELT (m_sm_changes, i, change)
+    change->remap_svalue_ids (map);
+}
+
+/* Purge any svalue_ids >= FIRST_UNUSED_SID.
+   Return the number of states that were purged.  */
+
+int
+state_change::on_svalue_purge (svalue_id first_unused_sid)
+{
+  int result = 0;
+  unsigned i;
+  sm_change *change;
+  FOR_EACH_VEC_ELT (m_sm_changes, i, change)
+    result += change->on_svalue_purge (first_unused_sid);
+  return result;
+}
+
+/* Assert that this object is sane.  */
+
+void
+state_change::validate (const program_state &new_state) const
+{
+  /* Skip this in a release build.  */
+#if !CHECKING_P
+  return;
+#endif
+  unsigned i;
+  sm_change *change;
+  FOR_EACH_VEC_ELT (m_sm_changes, i, change)
+    change->validate (new_state);
+}
+
+#if CHECKING_P
+
+namespace selftest {
+
+/* Tests for sm_state_map.  */
+
+static void
+test_sm_state_map ()
+{
+  tree x = build_global_decl ("x", integer_type_node);
+  tree y = build_global_decl ("y", integer_type_node);
+  tree z = build_global_decl ("z", integer_type_node);
+
+  /* Test setting states on svalue_id instances directly.  */
+  {
+    region_model model;
+    svalue_id sid_x = model.get_rvalue (x, NULL);
+    svalue_id sid_y = model.get_rvalue (y, NULL);
+    svalue_id sid_z = model.get_rvalue (z, NULL);
+
+    sm_state_map map;
+    ASSERT_TRUE (map.is_empty_p ());
+    ASSERT_EQ (map.get_state (sid_x), 0);
+
+    map.impl_set_state (sid_x, 42, sid_z);
+    ASSERT_EQ (map.get_state (sid_x), 42);
+    ASSERT_EQ (map.get_origin (sid_x), sid_z);
+    ASSERT_EQ (map.get_state (sid_y), 0);
+    ASSERT_FALSE (map.is_empty_p ());
+
+    map.impl_set_state (sid_y, 0, sid_z);
+    ASSERT_EQ (map.get_state (sid_y), 0);
+
+    map.impl_set_state (sid_x, 0, sid_z);
+    ASSERT_EQ (map.get_state (sid_x), 0);
+    ASSERT_TRUE (map.is_empty_p ());
+  }
+
+  /* Test setting states via equivalence classes.  */
+  {
+    region_model model;
+    svalue_id sid_x = model.get_rvalue (x, NULL);
+    svalue_id sid_y = model.get_rvalue (y, NULL);
+    svalue_id sid_z = model.get_rvalue (z, NULL);
+
+    sm_state_map map;
+    ASSERT_TRUE (map.is_empty_p ());
+    ASSERT_EQ (map.get_state (sid_x), 0);
+    ASSERT_EQ (map.get_state (sid_y), 0);
+
+    model.add_constraint (x, EQ_EXPR, y, NULL);
+
+    /* Setting x to a state should also update y, as they
+       are in the same equivalence class.  */
+    map.set_state (&model, sid_x, 5, sid_z);
+    ASSERT_EQ (map.get_state (sid_x), 5);
+    ASSERT_EQ (map.get_state (sid_y), 5);
+    ASSERT_EQ (map.get_origin (sid_x), sid_z);
+    ASSERT_EQ (map.get_origin (sid_y), sid_z);
+  }
+
+  /* Test equality and hashing.  */
+  {
+    region_model model;
+    svalue_id sid_y = model.get_rvalue (y, NULL);
+    svalue_id sid_z = model.get_rvalue (z, NULL);
+
+    sm_state_map map0;
+    sm_state_map map1;
+    sm_state_map map2;
+
+    ASSERT_EQ (map0.hash (), map1.hash ());
+    ASSERT_EQ (map0, map1);
+
+    map1.impl_set_state (sid_y, 5, sid_z);
+    ASSERT_NE (map0.hash (), map1.hash ());
+    ASSERT_NE (map0, map1);
+
+    /* Make the same change to map2.  */
+    map2.impl_set_state (sid_y, 5, sid_z);
+    ASSERT_EQ (map1.hash (), map2.hash ());
+    ASSERT_EQ (map1, map2);
+  }
+
+  /* Equality and hashing shouldn't depend on ordering.  */
+  {
+    sm_state_map map0;
+    sm_state_map map1;
+    sm_state_map map2;
+
+    ASSERT_EQ (map0.hash (), map1.hash ());
+    ASSERT_EQ (map0, map1);
+
+    map1.impl_set_state (svalue_id::from_int (14), 2, svalue_id::null ());
+    map1.impl_set_state (svalue_id::from_int (16), 3, svalue_id::null ());
+    map1.impl_set_state (svalue_id::from_int (1), 2, svalue_id::null ());
+    map1.impl_set_state (svalue_id::from_int (9), 2, svalue_id::null ());
+
+    map2.impl_set_state (svalue_id::from_int (1), 2, svalue_id::null ());
+    map2.impl_set_state (svalue_id::from_int (16), 3, svalue_id::null ());
+    map2.impl_set_state (svalue_id::from_int (14), 2, svalue_id::null ());
+    map2.impl_set_state (svalue_id::from_int (9), 2, svalue_id::null ());
+
+    ASSERT_EQ (map1.hash (), map2.hash ());
+    ASSERT_EQ (map1, map2);
+  }
+
+  /* Test sm_state_map::remap_svalue_ids.  */
+  {
+    sm_state_map map;
+    svalue_id sid_0 = svalue_id::from_int (0);
+    svalue_id sid_1 = svalue_id::from_int (1);
+    svalue_id sid_2 = svalue_id::from_int (2);
+
+    map.impl_set_state (sid_0, 42, sid_2);
+    ASSERT_EQ (map.get_state (sid_0), 42);
+    ASSERT_EQ (map.get_origin (sid_0), sid_2);
+    ASSERT_EQ (map.get_state (sid_1), 0);
+    ASSERT_EQ (map.get_state (sid_2), 0);
+
+    /* Apply a remapping to the IDs.  */
+    svalue_id_map remapping (3);
+    remapping.put (sid_0, sid_1);
+    remapping.put (sid_1, sid_2);
+    remapping.put (sid_2, sid_0);
+    map.remap_svalue_ids (remapping);
+
+    /* Verify that the IDs have been remapped.  */
+    ASSERT_EQ (map.get_state (sid_1), 42);
+    ASSERT_EQ (map.get_origin (sid_1), sid_0);
+    ASSERT_EQ (map.get_state (sid_2), 0);
+    ASSERT_EQ (map.get_state (sid_0), 0);
+  }
+
+  // TODO: coverage for purging
+}
+
+/* Verify that program_states with identical sm-state can be merged,
+   and that the merged program_state preserves the sm-state.  */
+
+static void
+test_program_state_merging ()
+{
+  /* Create a program_state for a global ptr "p" that has
+     malloc sm-state, pointing to a region on the heap.  */
+  tree p = build_global_decl ("p", ptr_type_node);
+
+  auto_delete_vec <state_machine> checkers;
+  checkers.safe_push (make_malloc_state_machine (NULL));
+  extrinsic_state ext_state (checkers);
+
+  program_state s0 (ext_state);
+  impl_region_model_context ctxt (&s0, NULL, ext_state);
+
+  region_model *model0 = s0.m_region_model;
+  region_id new_rid = model0->add_new_malloc_region ();
+  svalue_id ptr_sid
+      = model0->get_or_create_ptr_svalue (ptr_type_node, new_rid);
+  model0->set_value (model0->get_lvalue (p, &ctxt),
+		     ptr_sid, &ctxt);
+  sm_state_map *smap = s0.m_checker_states[0];
+  const state_machine::state_t TEST_STATE = 3;
+  smap->impl_set_state (ptr_sid, TEST_STATE, svalue_id::null ());
+  ASSERT_EQ (smap->get_state (ptr_sid), TEST_STATE);
+
+  model0->canonicalize (&ctxt);
+
+  /* Verify that canonicalization preserves sm-state.  */
+  ASSERT_EQ (smap->get_state (model0->get_rvalue (p, NULL)), TEST_STATE);
+
+  /* Make a copy of the program_state.  */
+  program_state s1 (s0);
+  ASSERT_EQ (s0, s1);
+
+  /* We have two identical states with "p" pointing to a heap region
+     with the given sm-state.
+     They ought to be mergeable, preserving the sm-state.  */
+  program_state merged (ext_state);
+  ASSERT_TRUE (s0.can_merge_with_p (s1, ext_state, &merged));
+  merged.validate (ext_state);
+
+  /* Verify that the merged state has the sm-state for "p".  */
+  region_model *merged_model = merged.m_region_model;
+  sm_state_map *merged_smap = merged.m_checker_states[0];
+  ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, NULL)),
+	     TEST_STATE);
+
+  /* Try canonicalizing.  */
+  impl_region_model_context merged_ctxt (&merged, NULL, ext_state);
+  merged.m_region_model->canonicalize (&merged_ctxt);
+  merged.validate (ext_state);
+
+  /* Verify that the merged state still has the sm-state for "p".  */
+  ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, NULL)),
+	     TEST_STATE);
+
+  /* After canonicalization, we ought to have equality with the inputs.  */
+  ASSERT_EQ (s0, merged);
+}
+
+/* Run all of the selftests within this file.  */
+
+void
+analyzer_program_state_cc_tests ()
+{
+  test_sm_state_map ();
+  test_program_state_merging ();
+}
+
+} // namespace selftest
+
+#endif /* CHECKING_P */
diff --git a/gcc/analyzer/program-state.h b/gcc/analyzer/program-state.h
new file mode 100644
index 0000000..9c87c15
--- /dev/null
+++ b/gcc/analyzer/program-state.h
@@ -0,0 +1,360 @@ 
+/* Classes for representing the state of interest at a given path of analysis.
+   Copyright (C) 2019 Free Software Foundation, Inc.
+   Contributed by David Malcolm <dmalcolm@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef GCC_ANALYZER_PROGRAM_STATE_H
+#define GCC_ANALYZER_PROGRAM_STATE_H
+
+#include "analyzer/sm.h"
+#include "analyzer/region-model.h"
+
+////////////////////////////////////////////////////////////////////////////
+
+/* Data shared by all program_state instances.  */
+
+class extrinsic_state
+{
+public:
+  extrinsic_state (auto_delete_vec <state_machine> &checkers)
+  : m_checkers (checkers)
+  {
+  }
+
+  const state_machine &get_sm (int idx) const
+  {
+    return *m_checkers[idx];
+  }
+
+  const char *get_name (int idx) const
+  {
+    return m_checkers[idx]->get_name ();
+  }
+
+  unsigned get_num_checkers () const { return m_checkers.length (); }
+
+  /* The state machines.  */
+  auto_delete_vec <state_machine> &m_checkers;
+};
+
+////////////////////////////////////////////////////////////////////////////
+
+template <> struct default_hash_traits<svalue_id>
+: public pod_hash_traits<svalue_id>
+{
+};
+
+template <>
+inline hashval_t
+pod_hash_traits<svalue_id>::hash (value_type v)
+{
+  return v.as_int ();
+}
+
+template <>
+inline bool
+pod_hash_traits<svalue_id>::equal (const value_type &existing,
+				   const value_type &candidate)
+{
+  return existing == candidate;
+}
+template <>
+inline void
+pod_hash_traits<svalue_id>::mark_deleted (value_type &v)
+{
+  v = svalue_id::from_int (-2);
+}
+template <>
+inline void
+pod_hash_traits<svalue_id>::mark_empty (value_type &v)
+{
+  v = svalue_id::null ();
+}
+template <>
+inline bool
+pod_hash_traits<svalue_id>::is_deleted (value_type v)
+{
+  return v.as_int () == -2;
+}
+template <>
+inline bool
+pod_hash_traits<svalue_id>::is_empty (value_type v)
+{
+  return v.null_p ();
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* Map from svalue_id to state machine state, also capturing the origin of
+   each state.  */
+
+class sm_state_map
+{
+public:
+  /* An entry in the hash_map.  */
+  struct entry_t
+  {
+    /* Default ctor needed by hash_map::empty.  */
+    entry_t ()
+    : m_state (0), m_origin (svalue_id::null ())
+    {
+    }
+
+    entry_t (state_machine::state_t state,
+	     svalue_id origin)
+    : m_state (state), m_origin (origin)
+    {}
+
+    bool operator== (const entry_t &other) const
+    {
+      return (m_state == other.m_state
+	      && m_origin == other.m_origin);
+    }
+    bool operator!= (const entry_t &other) const
+    {
+      return !(*this == other);
+    }
+
+    state_machine::state_t m_state;
+    svalue_id m_origin;
+  };
+  typedef hash_map <svalue_id, entry_t> map_t;
+  typedef typename map_t::iterator iterator_t;
+
+  sm_state_map *clone () const;
+
+  sm_state_map *
+  clone_with_remapping (const one_way_svalue_id_map &id_map) const;
+
+  void print (const state_machine &sm, pretty_printer *pp) const;
+  void dump (const state_machine &sm) const;
+
+  bool is_empty_p () const;
+
+  hashval_t hash () const;
+
+  bool operator== (const sm_state_map &other) const;
+  bool operator!= (const sm_state_map &other) const
+  {
+    return !(*this == other);
+  }
+
+  state_machine::state_t get_state (svalue_id sid) const;
+  svalue_id get_origin (svalue_id sid) const;
+
+  void set_state (region_model *model,
+		  svalue_id sid,
+		  state_machine::state_t state,
+		  svalue_id origin);
+  void set_state (const equiv_class &ec,
+		  state_machine::state_t state,
+		  svalue_id origin);
+  void impl_set_state (svalue_id sid,
+		       state_machine::state_t state,
+		       svalue_id origin);
+
+  void purge_for_unknown_fncall (const exploded_graph &eg,
+				 const state_machine &sm,
+				 const gcall *call, tree fndecl,
+				 region_model *new_model);
+
+  void remap_svalue_ids (const svalue_id_map &map);
+
+  int on_svalue_purge (const state_machine &sm,
+		       int sm_idx,
+		       svalue_id first_unused_sid,
+		       const svalue_id_map &map,
+		       impl_region_model_context *ctxt);
+
+  void on_inherited_svalue (svalue_id parent_sid,
+			    svalue_id child_sid);
+
+  void on_cast (svalue_id src_sid,
+		svalue_id dst_sid);
+
+  void validate (const state_machine &sm, int num_svalues) const;
+
+  iterator_t begin () const { return m_map.begin (); }
+  iterator_t end () const { return m_map.end (); }
+
+private:
+  map_t m_map;
+};
+
+/* A class for representing the state of interest at a given path of
+   analysis.
+
+   Currently this is a combination of:
+   (a) a region_model, giving:
+      (a.1) a hierarchy of memory regions
+      (a.2) values for the regions
+      (a.3) inequalities between values
+   (b) sm_state_maps per state machine, giving a sparse mapping of
+       values to states.  */
+
+class program_state
+{
+public:
+  program_state (const extrinsic_state &ext_state);
+  program_state (const program_state &other);
+  program_state& operator= (const program_state &other);
+
+#if __cplusplus >= 201103
+  program_state (program_state &&other);
+  program_state& operator= (program_state &&other); // doesn't seem to be used
+#endif
+
+  ~program_state ();
+
+  hashval_t hash () const;
+  bool operator== (const program_state &other) const;
+  bool operator!= (const program_state &other) const
+  {
+    return !(*this == other);
+  }
+
+  void print (const extrinsic_state &ext_state,
+	      pretty_printer *pp) const;
+
+  void dump_to_pp (const extrinsic_state &ext_state, bool summarize,
+		   pretty_printer *pp) const;
+  void dump_to_file (const extrinsic_state &ext_state, bool summarize,
+		     FILE *outf) const;
+  void dump (const extrinsic_state &ext_state, bool summarize) const;
+
+  bool on_edge (exploded_graph &eg,
+		const exploded_node &enode,
+		const superedge *succ,
+		state_change *change);
+
+  program_state prune_for_point (exploded_graph &eg,
+				 const program_point &point,
+				 state_change *change) const;
+
+  void remap_svalue_ids (const svalue_id_map &map);
+
+  tree get_representative_tree (svalue_id sid) const;
+
+  bool can_purge_p (const extrinsic_state &ext_state,
+		    svalue_id sid)
+  {
+    /* Don't purge vars that have non-purgeable sm state, to avoid
+       generating false "leak" complaints.  */
+    int i;
+    sm_state_map *smap;
+    FOR_EACH_VEC_ELT (m_checker_states, i, smap)
+      {
+	const state_machine &sm = ext_state.get_sm (i);
+	if (!sm.can_purge_p (smap->get_state (sid)))
+	  return false;
+      }
+    return true;
+  }
+
+  bool can_merge_with_p (const program_state &other,
+			 const extrinsic_state &ext_state,
+			 program_state *out) const;
+
+  void validate (const extrinsic_state &ext_state) const;
+
+  /* TODO: lose the pointer here (const-correctness issues?).  */
+  region_model *m_region_model;
+  auto_delete_vec<sm_state_map> m_checker_states;
+};
+
+/* An abstract base class for use with for_each_state_change.  */
+
+class state_change_visitor
+{
+public:
+  virtual ~state_change_visitor () {}
+
+  /* Return true for early exit, false to keep iterating.  */
+  virtual bool on_state_change (const state_machine &sm,
+				state_machine::state_t src_sm_val,
+				state_machine::state_t dst_sm_val,
+				tree dst_rep,
+				svalue_id dst_origin_sid) = 0;
+};
+
+extern bool for_each_state_change (const program_state &src_state,
+				   const program_state &dst_state,
+				   const extrinsic_state &ext_state,
+				   state_change_visitor *visitor);
+
+/* A class for recording "interesting" state changes.
+   This is used for annotating edges in the GraphViz output of the
+   exploded_graph, and for recording sm-state-changes, so that
+   values that change aren't purged (to make it easier to generate
+   state_change_event instances in the diagnostic_path).  */
+
+class state_change
+{
+ public:
+  struct sm_change
+  {
+    sm_change (int sm_idx,
+	       svalue_id new_sid,
+	       state_machine::state_t old_state,
+	       state_machine::state_t new_state)
+    : m_sm_idx (sm_idx),
+      m_new_sid (new_sid),
+      m_old_state (old_state), m_new_state (new_state)
+    {}
+
+    const state_machine &get_sm (const extrinsic_state &ext_state) const
+    {
+      return ext_state.get_sm (m_sm_idx);
+    }
+
+    void dump (pretty_printer *pp, const extrinsic_state &ext_state) const;
+
+    void remap_svalue_ids (const svalue_id_map &map);
+    int on_svalue_purge (svalue_id first_unused_sid);
+
+    void validate (const program_state &new_state) const;
+
+    int m_sm_idx;
+    svalue_id m_new_sid;
+    state_machine::state_t m_old_state;
+    state_machine::state_t m_new_state;
+  };
+
+  state_change ();
+  state_change (const state_change &other);
+
+  void add_sm_change (int sm_idx,
+		      svalue_id new_sid,
+		      state_machine::state_t old_state,
+		      state_machine::state_t new_state);
+
+  bool affects_p (svalue_id sid) const;
+
+  void dump (pretty_printer *pp, const extrinsic_state &ext_state) const;
+  void dump (const extrinsic_state &ext_state) const;
+
+  void remap_svalue_ids (const svalue_id_map &map);
+  int on_svalue_purge (svalue_id first_unused_sid);
+
+  void validate (const program_state &new_state) const;
+
+ private:
+  auto_vec<sm_change> m_sm_changes;
+};
+
+#endif /* GCC_ANALYZER_PROGRAM_STATE_H */