[PATCH 42/49] analyzer: new files: program-state.{cc|h}
David Malcolm
dmalcolm@redhat.com
Sat Nov 16 01:21:00 GMT 2019
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
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 */
--
1.8.5.3
More information about the Gcc-patches
mailing list