analyzer: rewrite of region and value-handling

This large patch reimplements how the analyzer tracks regions and
values.

Elimination of region_id and svalue_id
**************************************

The patch eliminates region_id and svalue_id in favor of simply
using pointers.  I'd hoped that the ID classes would make it easier
to compare states, avoiding having to compare long hexadecimal addresses
in favor of small integers.  Unfortunately it added lots of complexity,
with the need to remap IDs when comparing or purging states, and the
need to "canonicalize" when comparing states.

Various "state explosion" bugs in the old implementation were due to
failures in canonicalization, where two states that ought to be equal
were non-equal due to differences in ID ordering.  I spent a lot of
time trying to fix canonicalization bugs, and there always seemed to
be one more bug.  By eliminating IDs in this new implementation, lots
of tricky canonicalization goes away and no ID remapping should be
needed; almost all of the old validation code becomes redundant.
There's still some canonicalization in the new implementation, mostly
in constraint_manager, but much less than before.

Ownership of regions and svalues
********************************

In the old implementation, each region_model had its own copies of
regions and svalues, so there was heap bloat and churn as lots of
little objects were cloned when copying program_state instances.  In the
new implementation the regions and svalues are immutable and are shared
thoughout the analysis, rather than being per region_model.  They are
owned by a manager class, and are effectively singletons.  Region and
svalue instances can now be compared by pointer rather than by comparing
their fields (the manager class takes care of uniqueness).

This is a huge simplification, and (I hope) will avoid lots
of heap churn as states are copied; all mutable state from regions and
svalues is now stored in a "store" class in the region_model.

Changes to the meaning of a "region"
************************************

Region subclasses no longer represent internal structure, but instead
represent how the regions are reached.  So e.g. a global "struct coord
c;" is now a decl_region, rather than a struct_region.

In the old implementation, the values for each region were stored in the
region instances, but in the new implementation the regions are immutable.
Memory is now modeled in a new "store" class: a mapping from keys to
svalues, where the keys are both concrete bit-offsets from the start of
a "base region", and "symbolic" keys (thus hopefully making unions,
casts, aliasing etc easier to deal with).  So e.g. for assignments to
the fields of a struct, it records the mapping from bit-offsets of e.g.
field to the values; if that memory is cast to another type and written
to, the appropriate clobbering of the bound values can happen.

The concept of "what the current stack is" moves from the regions to
being a field within the region_model ("m_current_frame").

Bugs fixed by this patch
************************

PR analyzer/93032 (missing leak diagnostic for zlib/contrib/minizip/mztools.c)
PR analyzer/93938 (ICE in analyzer)
PR analyzer/94011 (ICE in analyzer)
PR analyzer/94099 (ICE in analyzer)
PR analyzer/94399 (leak false positive with __attribute__((cleanup())))
PR analyzer/94458 (leak false positive)
PR analyzer/94503 (ICE on C++ return-value-optimization)
PR analyzer/94640 (leak false positive)
PR analyzer/94688 (ICE in analyzer)
PR analyzer/94689 ("arrays of functions are not meaningful" error)
PR analyzer/94839 (leak false positive)
PR analyzer/95026 (leak false positive)
PR analyzer/95042 (ICE merging const and non-const C++ object instances)
PR analyzer/95240 (leak false positive)

gcc/ChangeLog:
	* Makefile.in (ANALYZER_OBJS): Add analyzer/region.o,
	analyzer/region-model-impl-calls.o,
	analyzer/region-model-manager.o,
	analyzer/region-model-reachability.o, analyzer/store.o, and
	analyzer/svalue.o.
	* doc/analyzer.texi: Update for changes to analyzer
	implementation.
	* tristate.h (tristate::get_value): New accessor.

gcc/analyzer/ChangeLog:
	* analyzer-logging.cc: Ignore "-Wformat-diag".
	(logger::enter_scope): Use inc_indent in both overloads.
	(logger::exit_scope): Use dec_indent.
	* analyzer-logging.h (logger::inc_indent): New.
	(logger::dec_indent): New.
	* analyzer-selftests.cc (run_analyzer_selftests): Call
	analyzer_store_cc_tests.
	* analyzer-selftests.h (analyzer_store_cc_tests): New decl.
	* analyzer.cc (get_stmt_location): New function.
	* analyzer.h (class initial_svalue): New forward decl.
	(class unaryop_svalue): New forward decl.
	(class binop_svalue): New forward decl.
	(class sub_svalue): New forward decl.
	(class unmergeable_svalue): New forward decl.
	(class placeholder_svalue): New forward decl.
	(class widening_svalue): New forward decl.
	(class compound_svalue): New forward decl.
	(class conjured_svalue): New forward decl.
	(svalue_set): New typedef.
	(class map_region): Delete.
	(class array_region): Delete.
	(class frame_region): New forward decl.
	(class function_region): New forward decl.
	(class label_region): New forward decl.
	(class decl_region): New forward decl.
	(class element_region): New forward decl.
	(class offset_region): New forward decl.
	(class cast_region): New forward decl.
	(class field_region): New forward decl.
	(class string_region): New forward decl.
	(class region_model_manager): New forward decl.
	(class store_manager): New forward decl.
	(class store): New forward decl.
	(class call_details): New forward decl.
	(struct svalue_id_merger_mapping): Delete.
	(struct canonicalization): Delete.
	(class function_point): New forward decl.
	(class engine): New forward decl.
	(dump_tree): New function decl.
	(print_quoted_type): New function decl.
	(readability_comparator): New function decl.
	(tree_cmp): New function decl.
	(class path_var): Move here from region-model.h
	(bit_offset_t, bit_size_t, byte_size_t): New typedefs.
	(class region_offset): New class.
	(get_stmt_location): New decl.
	(struct member_function_hash_traits): New struct.
	(class consolidation_map): New class.
	Ignore "-Wformat-diag".
	* analyzer.opt (-param=analyzer-max-svalue-depth=): New param.
	(-param=analyzer-max-enodes-for-full-dump=): New param.
	* call-string.cc: Ignore -Wformat-diag.
	* checker-path.cc: Move includes of "analyzer/call-string.h" and
	"analyzer/program-point.h" to before "analyzer/region-model.h",
	and also include "analyzer/store.h" before it.
	(state_change_event::state_change_event): Replace "tree var" param
	with "const svalue *sval".  Convert "origin" param from tree to
	"const svalue *".
	(state_change_event::get_desc): Call get_representative_tree to
	convert the var and origin from const svalue * to tree.  Use
	svalue::get_desc rather than %qE when describing state changes.
	(checker_path::add_final_event): Use get_stmt_location.
	* checker-path.h (state_change_event::state_change_event): Port
	from tree to const svalue *.
	(state_change_event::get_lvalue): Delete.
	(state_change_event::get_dest_function): New.
	(state_change_event::m_var): Replace with...
	(state_change_event::m_sval): ...this.
	(state_change_event::m_origin): Convert from tree to
	const svalue *.
	* constraint-manager.cc: Include "analyzer/call-string.h",
	"analyzer/program-point.h", and "analyzer/store.h" before
	"analyzer/region-model.h".
	(struct bound, struct range): Move to constraint-manager.h.
	(compare_constants): New function.
	(range::dump): Rename to...
	(range::dump_to_pp): ...this.  Support NULL constants.
	(range::dump): Reintroduce for dumping to stderr.
	(range::constrained_to_single_element): Return result, rather than
	writing to *OUT.
	(range::eval_condition): New.
	(range::below_lower_bound): New.
	(range::above_upper_bound): New.
	(equiv_class::equiv_class): Port from svalue_id to const svalue *.
	(equiv_class::print): Likewise.
	(equiv_class::hash): Likewise.
	(equiv_class::operator==): Port from svalue_id to const svalue *.
	(equiv_class::add): Port from svalue_id to const svalue *. Drop
	"cm" param.
	(equiv_class::del): Port from svalue_id to const svalue *.
	(equiv_class::get_representative): Likewise.
	(equiv_class::remap_svalue_ids): Delete.
	(svalue_id_cmp_by_id): Rename to...
	(svalue_cmp_by_ptr): ...this, porting from svalue_id to
	const svalue *.
	(equiv_class::canonicalize): Update qsort comparator.
	(constraint::implied_by): New.
	(constraint_manager::constraint_manager): Copy m_mgr in copy ctor.
	(constraint_manager::dump_to_pp): Add "multiline" param
	(constraint_manager::dump): Pass "true" for "multiline".
	(constraint_manager::add_constraint): Port from svalue_id to
	const svalue *.  Split out second part into...
	(constraint_manager::add_unknown_constraint): ...this new
	function.  Remove self-constraints when merging equivalence
	classes.
	(constraint_manager::add_constraint_internal): Remove constraints
	that would be implied by the new constraint.  Port from svalue_id
	to const svalue *.
	(constraint_manager::get_equiv_class_by_sid): Rename to...
	(constraint_manager::get_equiv_class_by_svalue): ...this, porting
	from svalue_id to const svalue *.
	(constraint_manager::get_or_add_equiv_class): Port from svalue_id
	to const svalue *.
	(constraint_manager::eval_condition): Make const.  Call
	compare_constants and return early if it provides a known result.
	(constraint_manager::get_ec_bounds): New.
	(constraint_manager::eval_condition): New overloads.  Make
	existing one const, and use compare_constants.
	(constraint_manager::purge): Convert "p" param to a template
	rather that an abstract base class.  Port from svalue_id to
	const svalue *.
	(class dead_svalue_purger): New class.
	(constraint_manager::remap_svalue_ids): Delete.
	(constraint_manager::on_liveness_change): New.
	(equiv_class_cmp): Port from svalue_id to const svalue *.
	(constraint_manager::canonicalize): Likewise.  Combine with
	purging of redundant equivalence classes and constraints.
	(class cleaned_constraint_manager): Delete.
	(class merger_fact_visitor): Make "m_cm_b" const.  Add "m_merger"
	field.
	(merger_fact_visitor::fact): Port from svalue_id to const svalue *.
	Add special case for widening.
	(constraint_manager::merge): Port from svalue_id to const svalue *.
	(constraint_manager::clean_merger_input): Delete.
	(constraint_manager::for_each_fact): Port from svalue_id to
	const svalue *.
	(constraint_manager::validate): Likewise.
	(selftest::test_constraint_conditions): Provide a
	region_model_manager when creating region_model instances.
	Add test for self-equality not creating equivalence classes.
	(selftest::test_transitivity): Provide a region_model_manager when
	creating region_model instances.  Verify that EC-merging happens
	when constraints are implied.
	(selftest::test_constant_comparisons):  Provide a
	region_model_manager when creating region_model instances.
	(selftest::test_constraint_impl): Likewise.  Remove over-specified
	assertions.
	(selftest::test_equality): Provide a region_model_manager when
	creating region_model instances.
	(selftest::test_many_constants): Likewise.  Provide a
	program_point when testing merging.
	(selftest::run_constraint_manager_tests): Move call to
	test_constant_comparisons to outside the transitivity guard.
	* constraint-manager.h (struct bound): Move here from
	constraint-manager.cc.
	(struct range): Likewise.
	(struct::eval_condition): New decl.
	(struct::below_lower_bound): New decl.
	(struct::above_upper_bound): New decl.
	(equiv_class::add): Port from svalue_id to const svalue *.
	(equiv_class::del): Likewise.
	(equiv_class::get_representative): Likewise.
	(equiv_class::remap_svalue_ids): Drop.
	(equiv_class::m_cst_sid): Convert to..
	(equiv_class::m_cst_sval): ...this.
	(equiv_class::m_vars): Port from svalue_id to const svalue *.
	(constraint::bool implied_by): New decl.
	(fact_visitor::on_fact): Port from svalue_id to const svalue *.
	(constraint_manager::constraint_manager): Add mgr param.
	(constraint_manager::clone): Delete.
	(constraint_manager::maybe_get_constant): Delete.
	(constraint_manager::get_sid_for_constant): Delete.
	(constraint_manager::get_num_svalues): Delete.
	(constraint_manager::dump_to_pp): Add "multiline" param.
	(constraint_manager::get_equiv_class): Port from svalue_id to
	const svalue *.
	(constraint_manager::add_constraint):  Likewise.
	(constraint_manager::get_equiv_class_by_sid): Rename to...
	(constraint_manager::get_equiv_class_by_svalue): ...this, porting
	from svalue_id to const svalue *.
	(constraint_manager::add_unknown_constraint): New decl.
	(constraint_manager::get_or_add_equiv_class): Port from svalue_id
	to const svalue *.
	(constraint_manager::eval_condition): Likewise.  Add overloads.
	(constraint_manager::get_ec_bounds): New decl.
	(constraint_manager::purge): Convert to template.
	(constraint_manager::remap_svalue_ids): Delete.
	(constraint_manager::on_liveness_change): New decl.
	(constraint_manager::canonicalize): Drop param.
	(constraint_manager::clean_merger_input): Delete.
	(constraint_manager::m_mgr): New field.
	* diagnostic-manager.cc: Move includes of
	"analyzer/call-string.h" and "analyzer/program-point.h" to before
	"analyzer/region-model.h", and also include "analyzer/store.h"
	before it.
	(saved_diagnostic::saved_diagnostic): Add "sval" param.
	(diagnostic_manager::diagnostic_manager): Add engine param.
	(diagnostic_manager::add_diagnostic): Add "sval" param, passing it
	to saved_diagnostic ctor.  Update overload to pass NULL for it.
	(dedupe_winners::dedupe_winners): Add engine param.
	(dedupe_winners::add): Add "eg" param.  Pass m_engine to
	feasible_p.
	(dedupe_winner::m_engine): New field.
	(diagnostic_manager::emit_saved_diagnostics): Pass engine to
	dedupe_winners.  Pass &eg when adding candidates.  Pass svalue
	rather than tree to prune_path.  Use get_stmt_location to get
	primary location of diagnostic.
	(diagnostic_manager::emit_saved_diagnostic): Likewise.
	(get_any_origin): Drop.
	(state_change_event_creator::on_global_state_change): Pass NULL
	const svalue * rather than NULL_TREE trees to state_change_event
	ctor.
	(state_change_event_creator::on_state_change): Port from tree and
	svalue_id to const svalue *.
	(for_each_state_change): Port from svalue_id to const svalue *.
	(struct null_assignment_sm_context): New.
	(diagnostic_manager::add_events_for_eedge):  Add state change
	events for assignment to NULL.
	(diagnostic_manager::prune_path): Update param from tree to
	const svalue *.
	(diagnostic_manager::prune_for_sm_diagnostic): Port from tracking
	by tree to by const svalue *.
	* diagnostic-manager.h (saved_diagnostic::saved_diagnostic): Add sval
	param.
	(saved_diagnostic::m_sval): New field.
	(diagnostic_manager::diagnostic_manager): Add engine param.
	(diagnostic_manager::get_engine): New.
	(diagnostic_manager::add_diagnostic): Add "sval" param.
	(diagnostic_manager::prune_path): Likewise.
	(diagnostic_manager::prune_for_sm_diagnostic): New overload.
	(diagnostic_manager::m_eng): New field.
	* engine.cc: Move includes of "analyzer/call-string.h" and
	"analyzer/program-point.h" to before "analyzer/region-model.h",
	and also include "analyzer/store.h" before it.
	(impl_region_model_context::impl_region_model_context): Update for
	removal of m_change field.
	(impl_region_model_context::remap_svalue_ids): Delete.
	(impl_region_model_context::on_svalue_leak): New.
	(impl_region_model_context::on_svalue_purge): Delete.
	(impl_region_model_context::on_liveness_change): New.
	(impl_region_model_context::on_unknown_change): Update param
	from svalue_id to const svalue *.  Add is_mutable param.
	(setjmp_svalue::compare_fields): Delete.
	(setjmp_svalue::accept): New.
	(setjmp_svalue::add_to_hash): Delete.
	(setjmp_svalue::dump_to_pp): New.
	(setjmp_svalue::print_details): Delete.
	(impl_sm_context::impl_sm_context): Drop "change" param.
	(impl_sm_context::get_fndecl_for_call): Drop "m_change".
	(impl_sm_context::on_transition): Drop ATTRIBUTE_UNUSED from
	"stmt" param.  Drop m_change.  Port from svalue_id to
	const svalue *.
	(impl_sm_context::warn_for_state): Drop m_change.  Port from
	svalue_id to const svalue *.
	(impl_sm_context::get_readable_tree): Rename to...
	(impl_sm_context::get_diagnostic_tree): ...this.  Port from
	svalue_id to const svalue *.
	(impl_sm_context::is_zero_assignment): New.
	(impl_sm_context::m_change): Delete field.
	(leak_stmt_finder::find_stmt): Handle m_var being NULL.
	(readability):  Increase penalty for MEM_REF.  For SSA_NAMEs,
	slightly favor the underlying var over the SSA name.  Heavily
	penalize temporaries.  Handle RESULT_DECL.
	(readability_comparator): Make non-static.  Consider stack depths.
	(impl_region_model_context::on_state_leak): Convert from svalue_id
	to const svalue *, updating for region_model changes.  Use
	id_equal.
	(impl_region_model_context::on_inherited_svalue): Delete.
	(impl_region_model_context::on_cast): Delete.
	(impl_region_model_context::on_condition):  Drop m_change.
	(impl_region_model_context::on_phi): Likewise.
	(impl_region_model_context::on_unexpected_tree_code): Handle t
	being NULL.
	(point_and_state::validate): Update stack checking for
	region_model changes.
	(eg_traits::dump_args_t::show_enode_details_p): New.
	(exploded_node::exploded_node): Initialize m_num_processed_stmts.
	(exploded_node::get_processed_stmt): New function.
	(exploded_node::get_dot_fillcolor): Add more colors.
	(exploded_node::dump_dot): Guard the printing of the point and
	state with show_enode_details_p.  Print the processed stmts for
	this enode after the initial state.
	(exploded_node::dump_to_pp): Pass true for new multiline param
	of program_state::dump_to_pp.
	(exploded_node::on_stmt): Drop "change" param.  Log the stmt.
	Set input_location.  Implement __analyzer_describe.  Update
	implementation of __analyzer_dump and __analyzer_eval.
	Remove purging of sm-state for unknown fncalls from here.
	(exploded_node::on_edge): Drop "change" param.
	(exploded_node::on_longjmp): Port from region_id/svalue_id to
	const region */const svalue *.  Call program_state::detect_leaks.
	Drop state_change.
	(exploded_node::detect_leaks): Update for changes to region_model.
	Call program_state::detect_leaks.
	(exploded_edge::exploded_edge): Drop ext_state and change params.
	(exploded_edge::dump_dot): "args" is no longer used.  Drop dumping
	of m_change.
	(exploded_graph::exploded_graph): Pass engine to
	m_diagnostic_manager ctor.  Use program_point::origin.
	(exploded_graph::add_function_entry):  Drop ctxt.  Use
	program_state::push_frame.  Drop state_change.
	(exploded_graph::get_or_create_node): Drop "change" param.  Add
	"enode_for_diag" param.  Update dumping calls for API changes.
	Pass point to can_merge_with_p.  Show enode indices
	within -Wanalyzer-too-complex diagnostic for hitting the per-point
	limit.
	(exploded_graph::add_edge): Drop "change" param.  Log which nodes
	are being connected.  Update for changes to exploded_edge ctor.
	(exploded_graph::get_per_program_point_data): New.
	(exploded_graph::process_worklist): Pass point to
	can_merge_with_p.  Drop state_change.  Update dumping call for API
	change.
	(exploded_graph::process_node):  Drop state_change.  Split the
	node in-place if an sm-state-change occurs.  Update
	m_num_processed_stmts.  Update dumping calls for API change.
	(exploded_graph::log_stats): Call engine::log_stats.
	(exploded_graph::dump_states_for_supernode): Update dumping
	call.
	(exploded_path::feasible_p): Add "eng" and "eg" params.
	Rename "i" to "end_idx".  Pass the manager to the region_model
	ctor.  Update for every processed stmt in the enode, not just the
	first.  Keep track of which snodes have been visited, and call
	loop_replay_fixup when revisiting one.
	(enode_label::get_text): Update dump call for new param.
	(exploded_graph::dump_exploded_nodes): Likewise.
	(exploded_graph::get_node_by_index): New.
	(impl_run_checkers): Create engine instance and pass its address
	to extrinsic_state ctor.
	* exploded-graph.h
	(impl_region_model_context::impl_region_model_context): Drop
	"change" params.
	(impl_region_model_context::void remap_svalue_ids): Delete.
	(impl_region_model_context::on_svalue_purge): Delete.
	(impl_region_model_context::on_svalue_leak): New.
	(impl_region_model_context::on_liveness_change): New.
	(impl_region_model_context::on_state_leak): Update signature.
	(impl_region_model_context::on_inherited_svalue): Delete.
	(impl_region_model_context::on_cast): Delete.
	(impl_region_model_context::on_unknown_change): Update signature.
	(impl_region_model_context::m_change): Delete.
	(eg_traits::dump_args_t::show_enode_details_p): New.
	(exploded_node::on_stmt): Drop "change" param.
	(exploded_node::on_edge): Likewise.
	(exploded_node::get_processed_stmt): New decl.
	(exploded_node::m_num_processed_stmts): New field.
	(exploded_edge::exploded_edge): Drop ext_state and change params.
	(exploded_edge::m_change): Delete.
	(exploded_graph::get_engine): New accessor.
	(exploded_graph::get_or_create_node): Drop "change" param.  Add
	"enode_for_diag" param.
	(exploded_graph::add_edge): Drop "change" param.
	(exploded_graph::get_per_program_point_data): New decl.
	(exploded_graph::get_node_by_index): New decl.
	(exploded_path::feasible_p): Add "eng" and "eg" params.
	* program-point.cc: Include "analyzer/store.h" before including
	"analyzer/region-model.h".
	(function_point::function_point): Move here from
	program-point.h.
	(function_point::get_function): Likewise.
	(function_point::from_function_entry): Likewise.
	(function_point::before_supernode): Likewise.
	(function_point::next_stmt): New function.
	* program-point.h (function_point::function_point): Move
	implementation from here to program-point.cc.
	(function_point::get_function): Likewise.
	(function_point::from_function_entry): Likewise.
	(function_point::before_supernode): Likewise.
	(function_point::next_stmt): New decl.
	(program_point::operator!=): New.
	(program_point::origin): New.
	(program_point::next_stmt): New.
	(program_point::m_function_point): Make non-const.
	* program-state.cc: Move includes of "analyzer/call-string.h" and
	"analyzer/program-point.h" to before "analyzer/region-model.h",
	and also include "analyzer/store.h" before it.
	(extrinsic_state::get_model_manager): New.
	(sm_state_map::sm_state_map): Pass in sm and sm_idx to ctor,
	rather than pass the around.
	(sm_state_map::clone_with_remapping): Delete.
	(sm_state_map::print): Remove "sm" param in favor of "m_sm".  Add
	"simple" and "multiline" params and support multiline vs single
	line dumping.
	(sm_state_map::dump): Remove "sm" param in favor of "m_sm".  Add
	"simple" param.
	(sm_state_map::hash): Port from svalue_id to const svalue *.
	(sm_state_map::operator==): Likewise.
	(sm_state_map::get_state): Likewise.  Call canonicalize_svalue on
	input.  Handle inheritance of sm-state.  Call get_default_state.
	(sm_state_map::get_origin): Port from svalue_id to const svalue *.
	(sm_state_map::set_state): Likewise.  Pass in ext_state.  Reject
	attempts to set state on UNKNOWN.
	(sm_state_map::impl_set_state): Port from svalue_id to
	const svalue *.  Pass in ext_state.  Call canonicalize_svalue on
	input.
	(sm_state_map::purge_for_unknown_fncall): Delete.
	(sm_state_map::on_svalue_leak): New.
	(sm_state_map::remap_svalue_ids): Delete.
	(sm_state_map::on_liveness_change): New.
	(sm_state_map::on_unknown_change): Reimplement.
	(sm_state_map::on_svalue_purge): Delete.
	(sm_state_map::on_inherited_svalue): Delete.
	(sm_state_map::on_cast): Delete.
	(sm_state_map::validate): Delete.
	(sm_state_map::canonicalize_svalue): New.
	(program_state::program_state): Update to pass manager to
	region_model's ctor.  Constify num_states and pass state machine
	and index to sm_state_map ctor.
	(program_state::print): Update for changes to dump API.
	(program_state::dump_to_pp): Ignore the summarize param.  Add
	"multiline" param.
	(program_state::dump_to_file): Add "multiline" param.
	(program_state::dump): Pass "true" for new "multiline" param.
	(program_state::push_frame): New.
	(program_state::on_edge): Drop "change" param.  Call
	program_state::detect_leaks.
	(program_state::prune_for_point): Add enode_for_diag param.
	Reimplement based on store class.  Call detect_leaks
	(program_state::remap_svalue_ids): Delete.
	(program_state::get_representative_tree): Port from svalue_id to
	const svalue *.
	(program_state::can_merge_with_p): Add "point" param.  Add early
	reject for sm-differences.  Drop id remapping.
	(program_state::validate): Drop region model and sm_state_map
	validation.
	(state_change::sm_change::dump): Delete.
	(state_change::sm_change::remap_svalue_ids): Delete.
	(state_change::sm_change::on_svalue_purge): Delete.
	(log_set_of_svalues): New.
	(state_change::sm_change::validate): Delete.
	(state_change::state_change): Delete.
	(state_change::add_sm_change): Delete.
	(state_change::affects_p): Delete.
	(state_change::dump): Delete.
	(state_change::remap_svalue_ids): Delete.
	(state_change::on_svalue_purge): Delete.
	(state_change::validate): Delete.
	(selftest::assert_dump_eq): Delete.
	(ASSERT_DUMP_EQ): Delete.
	(selftest::test_sm_state_map): Update for changes to region_model
	and sm_state_map, porting from svalue_id to const svalue *.
	(selftest::test_program_state_dumping): Likewise.  Drop test of
	dumping, renaming to...
	(selftest::test_program_state_1): ...this.
	(selftest::test_program_state_dumping_2): Likewise, renaming to...
	(selftest::test_program_state_2): ...this.
	(selftest::test_program_state_merging): Update for changes to
	region_model.
	(selftest::test_program_state_merging_2): Likewise.
	(selftest::analyzer_program_state_cc_tests): Update for renamed
	tests.
	* program-state.h (extrinsic_state::extrinsic_state): Add logger
	and engine params.
	(extrinsic_state::get_logger): New accessor.
	(extrinsic_state::get_engine): New accessor.
	(extrinsic_state::get_model_manager): New accessor.
	(extrinsic_state::m_logger): New field.
	(extrinsic_state::m_engine): New field.
	(struct default_hash_traits<svalue_id>): Delete.
	(pod_hash_traits<svalue_id>::hash): Delete.
	(pod_hash_traits<svalue_id>::equal): Delete.
	(pod_hash_traits<svalue_id>::mark_deleted): Delete.
	(pod_hash_traits<svalue_id>::mark_empty): Delete.
	(pod_hash_traits<svalue_id>::is_deleted): Delete.
	(pod_hash_traits<svalue_id>::is_empty): Delete.
	(sm_state_map::entry_t::entry_t): Port from svalue_id to
	const svalue *.
	(sm_state_map::entry_t::m_origin): Likewise.
	(sm_state_map::map_t): Likewise.
	(sm_state_map::sm_state_map): Add state_machine and index params.
	(sm_state_map::clone_with_remapping): Delete.
	(sm_state_map::print):  Drop sm param; add simple and multiline
	params.
	(sm_state_map::dump): Drop sm param; add simple param.
	(sm_state_map::get_state): Port from svalue_id to const svalue *.
	Add ext_state param.
	(sm_state_map::get_origin): Likewise.
	(sm_state_map::set_state): Likewise.
	(sm_state_map::impl_set_state): Likewise.
	(sm_state_map::purge_for_unknown_fncall): Delete.
	(sm_state_map::remap_svalue_ids): Delete.
	(sm_state_map::on_svalue_purge): Delete.
	(sm_state_map::on_svalue_leak): New.
	(sm_state_map::on_liveness_change): New.
	(sm_state_map::on_inherited_svalue): Delete.
	(sm_state_map::on_cast): Delete.
	(sm_state_map::validate): Delete.
	(sm_state_map::on_unknown_change): Port from svalue_id to
	const svalue *.  Add is_mutable and ext_state params.
	(sm_state_map::canonicalize_svalue): New.
	(sm_state_map::m_sm): New field.
	(sm_state_map::m_sm_idx): New field.
	(program_state::operator=): Delete.
	(program_state::dump_to_pp): Drop "summarize" param, adding
	"simple" and "multiline".
	(program_state::dump_to_file): Likewise.
	(program_state::dump): Rename "summarize" to "simple".
	(program_state::push_frame): New.
	(program_state::get_current_function): New.
	(program_state::on_edge): Drop "change" param.
	(program_state::prune_for_point): Likewise.  Add enode_for_diag
	param.
	(program_state::remap_svalue_ids): Delete.
	(program_state::get_representative_tree): Port from svalue_id to
	const svalue *.
	(program_state::can_purge_p): Likewise.  Pass ext_state to get_state.
	(program_state::can_merge_with_p): Add point param.
	(program_state::detect_leaks): New.
	(state_change_visitor::on_state_change): Port from tree and
	svalue_id to a pair of const svalue *.
	(class state_change): Delete.
	* region.cc: New file.
	* region-model-impl-calls.cc: New file.
	* region-model-manager.cc: New file.
	* region-model-reachability.cc: New file.
	* region-model-reachability.h: New file.
	* region-model.cc: Include "analyzer/call-string.h",
	"analyzer/program-point.h", and "analyzer/store.h" before
	"analyzer/region-model.h".  Include
	"analyzer/region-model-reachability.h".
	(dump_tree): Make non-static.
	(dump_quoted_tree): Make non-static.
	(print_quoted_type): Make non-static.
	(path_var::dump): Delete.
	(dump_separator): Delete.
	(class impl_constraint_manager): Delete.
	(svalue_id::print): Delete.
	(svalue_id::dump_node_name_to_pp): Delete.
	(svalue_id::validate): Delete.
	(region_id::print): Delete.
	(region_id::dump_node_name_to_pp): Delete.
	(region_id::validate): Delete.
	(region_id_set::region_id_set): Delete.
	(svalue_id_set::svalue_id_set): Delete.
	(svalue::operator==): Delete.
	(svalue::hash): Delete.
	(svalue::print): Delete.
	(svalue::dump_dot_to_pp): Delete.
	(svalue::remap_region_ids): Delete.
	(svalue::walk_for_canonicalization): Delete.
	(svalue::get_child_sid): Delete.
	(svalue::maybe_get_constant): Delete.
	(region_svalue::compare_fields): Delete.
	(region_svalue::add_to_hash): Delete.
	(region_svalue::print_details): Delete.
	(region_svalue::dump_dot_to_pp): Delete.
	(region_svalue::remap_region_ids): Delete.
	(region_svalue::merge_values): Delete.
	(region_svalue::walk_for_canonicalization): Delete.
	(region_svalue::eval_condition): Delete.
	(constant_svalue::compare_fields): Delete.
	(constant_svalue::add_to_hash): Delete.
	(constant_svalue::merge_values): Delete.
	(constant_svalue::eval_condition): Move to svalue.cc.
	(constant_svalue::print_details): Delete.
	(constant_svalue::get_child_sid): Delete.
	(unknown_svalue::compare_fields): Delete.
	(unknown_svalue::add_to_hash): Delete.
	(unknown_svalue::print_details): Delete.
	(poison_kind_to_str): Move to svalue.cc.
	(poisoned_svalue::compare_fields): Delete.
	(poisoned_svalue::add_to_hash): Delete.
	(poisoned_svalue::print_details): Delete.
	(region_kind_to_str): Move to region.cc and reimplement.
	(region::operator==): Delete.
	(region::get_parent_region): Delete.
	(region::set_value): Delete.
	(region::become_active_view): Delete.
	(region::deactivate_any_active_view): Delete.
	(region::deactivate_view): Delete.
	(region::get_value): Delete.
	(region::get_inherited_child_sid): Delete.
	(region_model::copy_region): Delete.
	(region_model::copy_struct_region): Delete.
	(region_model::copy_union_region): Delete.
	(region_model::copy_array_region): Delete.
	(region::hash): Delete.
	(region::print): Delete.
	(region::dump_dot_to_pp): Delete.
	(region::dump_to_pp): Delete.
	(region::dump_child_label): Delete.
	(region::validate): Delete.
	(region::remap_svalue_ids): Delete.
	(region::remap_region_ids): Delete.
	(region::add_view): Delete.
	(region::get_view): Delete.
	(region::region): Move to region.cc.
	(region::add_to_hash): Delete.
	(region::print_fields): Delete.
	(region::non_null_p): Delete.
	(primitive_region::clone): Delete.
	(primitive_region::walk_for_canonicalization): Delete.
	(map_region::map_region): Delete.
	(map_region::compare_fields): Delete.
	(map_region::print_fields): Delete.
	(map_region::validate): Delete.
	(map_region::dump_dot_to_pp): Delete.
	(map_region::dump_child_label): Delete.
	(map_region::get_or_create): Delete.
	(map_region::get): Delete.
	(map_region::add_to_hash): Delete.
	(map_region::remap_region_ids): Delete.
	(map_region::unbind): Delete.
	(map_region::get_tree_for_child_region): Delete.
	(map_region::get_tree_for_child_region): Delete.
	(tree_cmp): Move to region.cc.
	(map_region::can_merge_p): Delete.
	(map_region::walk_for_canonicalization): Delete.
	(map_region::get_value_by_name): Delete.
	(struct_or_union_region::valid_key_p): Delete.
	(struct_or_union_region::compare_fields): Delete.
	(struct_region::clone): Delete.
	(struct_region::compare_fields): Delete.
	(union_region::clone): Delete.
	(union_region::compare_fields): Delete.
	(frame_region::compare_fields): Delete.
	(frame_region::clone): Delete.
	(frame_region::valid_key_p): Delete.
	(frame_region::print_fields): Delete.
	(frame_region::add_to_hash): Delete.
	(globals_region::compare_fields): Delete.
	(globals_region::clone): Delete.
	(globals_region::valid_key_p): Delete.
	(code_region::compare_fields): Delete.
	(code_region::clone): Delete.
	(code_region::valid_key_p): Delete.
	(array_region::array_region): Delete.
	(array_region::get_element): Delete.
	(array_region::clone): Delete.
	(array_region::compare_fields): Delete.
	(array_region::print_fields): Delete.
	(array_region::validate): Delete.
	(array_region::dump_dot_to_pp): Delete.
	(array_region::dump_child_label): Delete.
	(array_region::get_or_create): Delete.
	(array_region::get): Delete.
	(array_region::add_to_hash): Delete.
	(array_region::remap_region_ids): Delete.
	(array_region::get_key_for_child_region): Delete.
	(array_region::key_cmp): Delete.
	(array_region::walk_for_canonicalization): Delete.
	(array_region::key_from_constant): Delete.
	(array_region::constant_from_key): Delete.
	(function_region::compare_fields): Delete.
	(function_region::clone): Delete.
	(function_region::valid_key_p): Delete.
	(stack_region::stack_region): Delete.
	(stack_region::compare_fields): Delete.
	(stack_region::clone): Delete.
	(stack_region::print_fields): Delete.
	(stack_region::dump_child_label): Delete.
	(stack_region::validate): Delete.
	(stack_region::push_frame): Delete.
	(stack_region::get_current_frame_id): Delete.
	(stack_region::pop_frame): Delete.
	(stack_region::add_to_hash): Delete.
	(stack_region::remap_region_ids): Delete.
	(stack_region::can_merge_p): Delete.
	(stack_region::walk_for_canonicalization): Delete.
	(stack_region::get_value_by_name): Delete.
	(heap_region::heap_region): Delete.
	(heap_region::compare_fields): Delete.
	(heap_region::clone): Delete.
	(heap_region::walk_for_canonicalization): Delete.
	(root_region::root_region): Delete.
	(root_region::compare_fields): Delete.
	(root_region::clone): Delete.
	(root_region::print_fields): Delete.
	(root_region::validate): Delete.
	(root_region::dump_child_label): Delete.
	(root_region::push_frame): Delete.
	(root_region::get_current_frame_id): Delete.
	(root_region::pop_frame): Delete.
	(root_region::ensure_stack_region): Delete.
	(root_region::get_stack_region): Delete.
	(root_region::ensure_globals_region): Delete.
	(root_region::get_code_region): Delete.
	(root_region::ensure_code_region): Delete.
	(root_region::get_globals_region): Delete.
	(root_region::ensure_heap_region): Delete.
	(root_region::get_heap_region): Delete.
	(root_region::remap_region_ids): Delete.
	(root_region::can_merge_p): Delete.
	(root_region::add_to_hash): Delete.
	(root_region::walk_for_canonicalization): Delete.
	(root_region::get_value_by_name): Delete.
	(symbolic_region::symbolic_region): Delete.
	(symbolic_region::compare_fields): Delete.
	(symbolic_region::clone): Delete.
	(symbolic_region::walk_for_canonicalization): Delete.
	(symbolic_region::print_fields): Delete.
	(region_model::region_model): Add region_model_manager * param.
	Reimplement in terms of store, dropping impl_constraint_manager
	subclass.
	(region_model::operator=): Reimplement in terms of store
	(region_model::operator==): Likewise.
	(region_model::hash): Likewise.
	(region_model::print): Delete.
	(region_model::print_svalue): Delete.
	(region_model::dump_dot_to_pp): Delete.
	(region_model::dump_dot_to_file): Delete.
	(region_model::dump_dot): Delete.
	(region_model::dump_to_pp): Replace "summarize" param with
	"simple" and "multiline".  Port to store-based implementation.
	(region_model::dump): Replace "summarize" param with "simple" and
	"multiline".
	(dump_vec_of_tree): Delete.
	(region_model::dump_summary_of_rep_path_vars): Delete.
	(region_model::validate): Delete.
	(svalue_id_cmp_by_constant_svalue_model): Delete.
	(svalue_id_cmp_by_constant_svalue): Delete.
	(region_model::canonicalize): Drop "ctxt" param.  Reimplement in
	terms of store and constraints.
	(region_model::canonicalized_p): Remove NULL arg to canonicalize.
	(region_model::loop_replay_fixup): New.
	(poisoned_value_diagnostic::emit): Tweak wording of warnings.
	(region_model::check_for_poison): Delete.
	(region_model::get_gassign_result): New.
	(region_model::on_assignment): Port to store-based implementation.
	(region_model::on_call_pre): Delete calls to check_for_poison.
	Move implementations to region-model-impl-calls.c and port to
	store-based implementation.
	(region_model::on_call_post): Likewise.
	(class reachable_regions): Move to region-model-reachability.h/cc
	and port to store-based implementation.
	(region_model::handle_unrecognized_call): Port to store-based
	implementation.
	(region_model::get_reachable_svalues): New.
	(region_model::on_setjmp): Port to store-based implementation.
	(region_model::on_longjmp): Likewise.
	(region_model::handle_phi): Drop is_back_edge param and the logic
	using it.
	(region_model::get_lvalue_1): Port from region_id to const region *.
	(region_model::make_region_for_unexpected_tree_code): Delete.
	(assert_compat_types): If the check fails, use internal_error to
	show the types.
	(region_model::get_lvalue): Port from region_id to const region *.
	(region_model::get_rvalue_1): Port from svalue_id to const svalue *.
	(region_model::get_rvalue): Likewise.
	(region_model::get_or_create_ptr_svalue): Delete.
	(region_model::get_or_create_constant_svalue): Delete.
	(region_model::get_svalue_for_fndecl): Delete.
	(region_model::get_region_for_fndecl): Delete.
	(region_model::get_svalue_for_label): Delete.
	(region_model::get_region_for_label): Delete.
	(build_cast): Delete.
	(region_model::maybe_cast_1): Delete.
	(region_model::maybe_cast): Delete.
	(region_model::get_field_region): Delete.
	(region_model::get_store_value): New.
	(region_model::region_exists_p): New.
	(region_model::deref_rvalue): Port from svalue_id to const svalue *.
	(region_model::set_value): Likewise.
	(region_model::clobber_region): New.
	(region_model::purge_region): New.
	(region_model::zero_fill_region): New.
	(region_model::mark_region_as_unknown): New.
	(region_model::eval_condition): Port from svalue_id to
	const svalue *.
	(region_model::eval_condition_without_cm): Likewise.
	(region_model::compare_initial_and_pointer): New.
	(region_model::add_constraint): Port from svalue_id to
	const svalue *.
	(region_model::maybe_get_constant): Delete.
	(region_model::get_representative_path_var): New.
	(region_model::add_new_malloc_region): Delete.
	(region_model::get_representative_tree): Port to const svalue *.
	(region_model::get_representative_path_var): Port to
	const region *.
	(region_model::get_path_vars_for_svalue): Delete.
	(region_model::set_to_new_unknown_value): Delete.
	(region_model::update_for_phis): Don't pass is_back_edge to handle_phi.
	(region_model::update_for_call_superedge): Port from svalue_id to
	const svalue *.
	(region_model::update_for_return_superedge): Port to store-based
	implementation.
	(region_model::update_for_call_summary): Replace
	set_to_new_unknown_value with mark_region_as_unknown.
	(region_model::get_root_region): Delete.
	(region_model::get_stack_region_id): Delete.
	(region_model::push_frame): Delete.
	(region_model::get_current_frame_id): Delete.
	(region_model::get_current_function): Delete.
	(region_model::pop_frame): Delete.
	(region_model::on_top_level_param): New.
	(region_model::get_stack_depth): Delete.
	(region_model::get_function_at_depth): Delete.
	(region_model::get_globals_region_id): Delete.
	(region_model::add_svalue): Delete.
	(region_model::replace_svalue): Delete.
	(region_model::add_region): Delete.
	(region_model::get_svalue): Delete.
	(region_model::get_region): Delete.
	(make_region_for_type): Delete.
	(region_model::add_region_for_type): Delete.
	(region_model::on_top_level_param): New.
	(class restrict_to_used_svalues): Delete.
	(region_model::purge_unused_svalues): Delete.
	(region_model::push_frame): New.
	(region_model::remap_svalue_ids): Delete.
	(region_model::remap_region_ids): Delete.
	(region_model::purge_regions): Delete.
	(region_model::get_descendents): Delete.
	(region_model::delete_region_and_descendents): Delete.
	(region_model::poison_any_pointers_to_bad_regions): Delete.
	(region_model::can_merge_with_p): Delete.
	(region_model::get_current_function): New.
	(region_model::get_value_by_name): Delete.
	(region_model::convert_byte_offset_to_array_index): Delete.
	(region_model::pop_frame): New.
	(region_model::get_or_create_mem_ref): Delete.
	(region_model::get_stack_depth): New.
	(region_model::get_frame_at_index): New.
	(region_model::unbind_region_and_descendents): New.
	(struct bad_pointer_finder): New.
	(region_model::get_or_create_pointer_plus_expr): Delete.
	(region_model::poison_any_pointers_to_descendents): New.
	(region_model::get_or_create_view): Delete.
	(region_model::can_merge_with_p): New.
	(region_model::get_fndecl_for_call):  Port from svalue_id to
	const svalue *.
	(struct append_ssa_names_cb_data): New.
	(get_ssa_name_regions_for_current_frame): New.
	(region_model::append_ssa_names_cb): New.
	(model_merger::dump_to_pp): Add "simple" param.  Drop dumping of
	remappings.
	(model_merger::dump): Add "simple" param to both overloads.
	(model_merger::can_merge_values_p): Delete.
	(model_merger::record_regions): Delete.
	(model_merger::record_svalues): Delete.
	(svalue_id_merger_mapping::svalue_id_merger_mapping): Delete.
	(svalue_id_merger_mapping::dump_to_pp): Delete.
	(svalue_id_merger_mapping::dump): Delete.
	(region_model::create_region_for_heap_alloc): New.
	(region_model::create_region_for_alloca): New.
	(region_model::record_dynamic_extents): New.
	(canonicalization::canonicalization): Delete.
	(canonicalization::walk_rid): Delete.
	(canonicalization::walk_sid): Delete.
	(canonicalization::dump_to_pp): Delete.
	(canonicalization::dump): Delete.
	(inchash::add): Delete overloads for svalue_id and region_id.
	(engine::log_stats): New.
	(assert_condition): Add overload comparing svalues.
	(assert_dump_eq): Pass "true" for multiline.
	(selftest::test_dump): Update for rewrite of region_model.
	(selftest::test_dump_2): Rename to...
	(selftest::test_struct): ...this.  Provide a region_model_manager
	when creating region_model instance.  Remove dump test.  Add
	checks for get_offset.
	(selftest::test_dump_3): Rename to...
	(selftest::test_array_1): ...this.  Provide a region_model_manager
	when creating region_model instance.  Remove dump test.
	(selftest::test_get_representative_tree): Port from svalue_id to
	new API.  Add test coverage for various expressions.
	(selftest::test_unique_constants): Provide a region_model_manager
	for the region_model.  Add test coverage for comparing const vs
	non-const.
	(selftest::test_svalue_equality): Delete.
	(selftest::test_region_equality): Delete.
	(selftest::test_unique_unknowns): New.
	(class purge_all_svalue_ids): Delete.
	(class purge_one_svalue_id): Delete.
	(selftest::test_purging_by_criteria): Delete.
	(selftest::test_initial_svalue_folding): New.
	(selftest::test_unaryop_svalue_folding): New.
	(selftest::test_binop_svalue_folding): New.
	(selftest::test_sub_svalue_folding): New.
	(selftest::test_purge_unused_svalues): Delete.
	(selftest::test_descendent_of_p): New.
	(selftest::test_assignment): Provide a region_model_manager for
	the region_model.  Drop the dump test.
	(selftest::test_compound_assignment): Likewise.
	(selftest::test_stack_frames): Port to new implementation.
	(selftest::test_get_representative_path_var): Likewise.
	(selftest::test_canonicalization_1): Rename to...
	(selftest::test_equality_1): ...this.  Port to new API, and add
	(selftest::test_canonicalization_2): Provide a
	region_model_manager when creating region_model instances.
	Remove redundant canicalization.
	(selftest::test_canonicalization_3): Provide a
	region_model_manager when creating region_model instances.
	Remove param from calls to region_model::canonicalize.
	(selftest::test_canonicalization_4): Likewise.
	(selftest::assert_region_models_merge): Constify
	out_merged_svalue.  Port to new API.
	(selftest::test_state_merging): Provide a
	region_model_manager when creating region_model instances.
	Provide a program_point point when merging them.  Replace
	set_to_new_unknown_value with usage of placeholder_svalues.
	Drop get_value_by_name.  Port from svalue_id to const svalue *.
	Add test of heap allocation.
	(selftest::test_constraint_merging):  Provide a
	region_model_manager when creating region_model instances.
	Provide a program_point point when merging them.  Eliminate use
	of set_to_new_unknown_value.
	(selftest::test_widening_constraints): New.
	(selftest::test_iteration_1): New.
	(selftest::test_malloc_constraints): Port to store-based
	implementation.
	(selftest::test_var): New test.
	(selftest::test_array_2): New test.
	(selftest::test_mem_ref): New test.
	(selftest::test_POINTER_PLUS_EXPR_then_MEM_REF): New.
	(selftest::test_malloc): New.
	(selftest::test_alloca): New.
	(selftest::analyzer_region_model_cc_tests): Update for renamings.
	Call new functions.
	* region-model.h (class path_var): Move to analyzer.h.
	(class svalue_id): Delete.
	(class region_id): Delete.
	(class id_map): Delete.
	(svalue_id_map): Delete.
	(region_id_map): Delete.
	(id_map<T>::id_map): Delete.
	(id_map<T>::put): Delete.
	(id_map<T>::get_dst_for_src): Delete.
	(id_map<T>::get_src_for_dst): Delete.
	(id_map<T>::dump_to_pp): Delete.
	(id_map<T>::dump): Delete.
	(id_map<T>::update): Delete.
	(one_way_svalue_id_map): Delete.
	(one_way_region_id_map): Delete.
	(class region_id_set): Delete.
	(class svalue_id_set): Delete.
	(struct complexity): New.
	(class visitor): New.
	(enum svalue_kind): Add SK_SETJMP, SK_INITIAL, SK_UNARYOP,
	SK_BINOP, SK_SUB,SK_UNMERGEABLE, SK_PLACEHOLDER, SK_WIDENING,
	SK_COMPOUND, and SK_CONJURED.
	(svalue::operator==): Delete.
	(svalue::operator!=): Delete.
	(svalue::clone): Delete.
	(svalue::hash): Delete.
	(svalue::dump_dot_to_pp): Delete.
	(svalue::dump_to_pp): New.
	(svalue::dump): New.
	(svalue::get_desc): New.
	(svalue::dyn_cast_initial_svalue): New.
	(svalue::dyn_cast_unaryop_svalue): New.
	(svalue::dyn_cast_binop_svalue): New.
	(svalue::dyn_cast_sub_svalue): New.
	(svalue::dyn_cast_unmergeable_svalue): New.
	(svalue::dyn_cast_widening_svalue): New.
	(svalue::dyn_cast_compound_svalue): New.
	(svalue::dyn_cast_conjured_svalue): New.
	(svalue::maybe_undo_cast): New.
	(svalue::unwrap_any_unmergeable): New.
	(svalue::remap_region_ids): Delete
	(svalue::can_merge_p): New.
	(svalue::walk_for_canonicalization): Delete
	(svalue::get_complexity): New.
	(svalue::get_child_sid): Delete
	(svalue::accept): New.
	(svalue::live_p): New.
	(svalue::implicitly_live_p): New.
	(svalue::svalue): Add complexity param.
	(svalue::add_to_hash): Delete
	(svalue::print_details): Delete
	(svalue::m_complexity): New field.
	(region_svalue::key_t): New struct.
	(region_svalue::region_svalue): Port from region_id to
	const region_id *.  Add complexity.
	(region_svalue::compare_fields): Delete.
	(region_svalue::clone): Delete.
	(region_svalue::dump_dot_to_pp): Delete.
	(region_svalue::get_pointee): Port from region_id to
	const region_id *.
	(region_svalue::remap_region_ids): Delete.
	(region_svalue::merge_values): Delete.
	(region_svalue::dump_to_pp): New.
	(region_svalue::accept): New.
	(region_svalue::walk_for_canonicalization): Delete.
	(region_svalue::eval_condition): Make params const.
	(region_svalue::add_to_hash): Delete.
	(region_svalue::print_details): Delete.
	(region_svalue::m_rid): Replace with...
	(region_svalue::m_reg): ...this.
	(is_a_helper <region_svalue *>::test): Convert to...
	(is_a_helper <const region_svalue *>::test): ...this.
	(template <> struct default_hash_traits<region_svalue::key_t>):
	New.
	(constant_svalue::constant_svalue): Add complexity.
	(constant_svalue::compare_fields): Delete.
	(constant_svalue::clone): Delete.
	(constant_svalue::add_to_hash): Delete.
	(constant_svalue::dump_to_pp): New.
	(constant_svalue::accept): New.
	(constant_svalue::implicitly_live_p): New.
	(constant_svalue::merge_values): Delete.
	(constant_svalue::eval_condition): Make params const.
	(constant_svalue::get_child_sid): Delete.
	(constant_svalue::print_details): Delete.
	(is_a_helper <constant_svalue *>::test): Convert to...
	(is_a_helper <const constant_svalue *>::test): ...this.
	(class unknown_svalue): Update leading comment.
	(unknown_svalue::unknown_svalue): Add complexity.
	(unknown_svalue::compare_fields): Delete.
	(unknown_svalue::add_to_hash): Delete.
	(unknown_svalue::dyn_cast_unknown_svalue): Delete.
	(unknown_svalue::print_details): Delete.
	(unknown_svalue::dump_to_pp): New.
	(unknown_svalue::accept): New.
	(poisoned_svalue::key_t): New struct.
	(poisoned_svalue::poisoned_svalue): Add complexity.
	(poisoned_svalue::compare_fields): Delete.
	(poisoned_svalue::clone): Delete.
	(poisoned_svalue::add_to_hash): Delete.
	(poisoned_svalue::dump_to_pp): New.
	(poisoned_svalue::accept): New.
	(poisoned_svalue::print_details): Delete.
	(is_a_helper <poisoned_svalue *>::test): Convert to...
	(is_a_helper <const poisoned_svalue *>::test): ...this.
	(template <> struct default_hash_traits<poisoned_svalue::key_t>):
	New.
	(setjmp_record::add_to_hash): New.
	(setjmp_svalue::key_t): New struct.
	(setjmp_svalue::compare_fields): Delete.
	(setjmp_svalue::clone): Delete.
	(setjmp_svalue::add_to_hash): Delete.
	(setjmp_svalue::setjmp_svalue): Add complexity.
	(setjmp_svalue::dump_to_pp): New.
	(setjmp_svalue::accept): New.
	(setjmp_svalue::void print_details): Delete.
	(is_a_helper <const setjmp_svalue *>::test): New.
	(template <> struct default_hash_traits<setjmp_svalue::key_t>): New.
	(class initial_svalue : public svalue): New.
	(is_a_helper <const initial_svalue *>::test): New.
	(class unaryop_svalue): New.
	(is_a_helper <const unaryop_svalue *>::test): New.
	(template <> struct default_hash_traits<unaryop_svalue::key_t>): New.
	(class binop_svalue): New.
	(is_a_helper <const binop_svalue *>::test): New.
	(template <> struct default_hash_traits<binop_svalue::key_t>): New.
	(class sub_svalue): New.
	(is_a_helper <const sub_svalue *>::test): New.
	(template <> struct default_hash_traits<sub_svalue::key_t>): New.
	(class unmergeable_svalue): New.
	(is_a_helper <const unmergeable_svalue *>::test): New.
	(class placeholder_svalue): New.
	(is_a_helper <placeholder_svalue *>::test): New.
	(class widening_svalue): New.
	(is_a_helper <widening_svalue *>::test): New.
	(template <> struct default_hash_traits<widening_svalue::key_t>): New.
	(class compound_svalue): New.
	(is_a_helper <compound_svalue *>::test): New.
	(template <> struct default_hash_traits<compound_svalue::key_t>): New.
	(class conjured_svalue): New.
	(is_a_helper <conjured_svalue *>::test): New.
	(template <> struct default_hash_traits<conjured_svalue::key_t>): New.
	(enum region_kind): Delete RK_PRIMITIVE, RK_STRUCT, RK_UNION, and
	RK_ARRAY.  Add RK_LABEL, RK_DECL, RK_FIELD, RK_ELEMENT, RK_OFFSET,
	RK_CAST, RK_HEAP_ALLOCATED, RK_ALLOCA, RK_STRING, and RK_UNKNOWN.
	(region_kind_to_str): Delete.
	(region::~region): Move implementation to region.cc.
	(region::operator==): Delete.
	(region::operator!=): Delete.
	(region::clone): Delete.
	(region::get_id): New.
	(region::cmp_ids): New.
	(region::dyn_cast_map_region): Delete.
	(region::dyn_cast_array_region): Delete.
	(region::region_id get_parent): Delete.
	(region::get_parent_region): Convert to a simple accessor.
	(region::void set_value): Delete.
	(region::svalue_id get_value): Delete.
	(region::svalue_id get_value_direct): Delete.
	(region::svalue_id get_inherited_child_sid): Delete.
	(region::dyn_cast_frame_region): New.
	(region::dyn_cast_function_region): New.
	(region::dyn_cast_decl_region): New.
	(region::dyn_cast_field_region): New.
	(region::dyn_cast_element_region): New.
	(region::dyn_cast_offset_region): New.
	(region::dyn_cast_cast_region): New.
	(region::dyn_cast_string_region): New.
	(region::accept): New.
	(region::get_base_region): New.
	(region::base_region_p): New.
	(region::descendent_of_p): New.
	(region::maybe_get_frame_region): New.
	(region::maybe_get_decl): New.
	(region::hash): Delete.
	(region::rint): Delete.
	(region::dump_dot_to_pp): Delete.
	(region::get_desc): New.
	(region::dump_to_pp): Convert to vfunc, changing signature.
	(region::dump_child_label): Delete.
	(region::remap_svalue_ids): Delete.
	(region::remap_region_ids): Delete.
	(region::dump): New.
	(region::walk_for_canonicalization): Delete.
	(region::non_null_p): Drop region_model param.
	(region::add_view): Delete.
	(region::get_view): Delete.
	(region::get_active_view): Delete.
	(region::is_view_p): Delete.
	(region::cmp_ptrs): New.
	(region::validate): Delete.
	(region::get_offset): New.
	(region::get_byte_size): New.
	(region::get_bit_size): New.
	(region::get_subregions_for_binding): New.
	(region::region): Add complexity param.  Convert parent from
	region_id to const region *.  Drop svalue_id.  Drop copy ctor.
	(region::symbolic_for_unknown_ptr_p): New.
	(region::add_to_hash): Delete.
	(region::print_fields): Delete.
	(region::get_complexity): New accessor.
	(region::become_active_view): Delete.
	(region::deactivate_any_active_view): Delete.
	(region::deactivate_view): Delete.
	(region::calc_offset): New.
	(region::m_parent_rid): Delete.
	(region::m_sval_id): Delete.
	(region::m_complexity): New.
	(region::m_id): New.
	(region::m_parent): New.
	(region::m_view_rids): Delete.
	(region::m_is_view): Delete.
	(region::m_active_view_rid): Delete.
	(region::m_cached_offset): New.
	(is_a_helper <region *>::test): Convert to...
	(is_a_helper <const region *>::test): ... this.
	(class primitive_region): Delete.
	(class space_region): New.
	(class map_region): Delete.
	(is_a_helper <map_region *>::test): Delete.
	(class frame_region): Reimplement.
	(template <> struct default_hash_traits<frame_region::key_t>):
	New.
	(class globals_region): Reimplement.
	(is_a_helper <globals_region *>::test): Convert to...
	(is_a_helper <const globals_region *>::test): ...this.
	(class struct_or_union_region): Delete.
	(is_a_helper <struct_or_union_region *>::test): Delete.
	(class code_region): Reimplement.
	(is_a_helper <const code_region *>::test): New.
	(class struct_region): Delete.
	(is_a_helper <struct_region *>::test): Delete.
	(class function_region): Reimplement.
	(is_a_helper <function_region *>::test): Convert to...
	(is_a_helper <const function_region *>::test): ...this.
	(class union_region): Delete.
	(is_a_helper <union_region *>::test): Delete.
	(class label_region): New.
	(is_a_helper <const label_region *>::test): New.
	(class scope_region): Delete.
	(class stack_region): Reimplement.
	(is_a_helper <stack_region *>::test): Convert to...
	(is_a_helper <const stack_region *>::test): ...this.
	(class heap_region): Reimplement.
	(is_a_helper <heap_region *>::test): Convert to...
	(is_a_helper <const heap_region *>::test): ...this.
	(class root_region): Reimplement.
	(is_a_helper <root_region *>::test): Convert to...
	(is_a_helper <const root_region *>::test): ...this.
	(class symbolic_region): Reimplement.
	(is_a_helper <const symbolic_region *>::test): New.
	(template <> struct default_hash_traits<symbolic_region::key_t>):
	New.
	(class decl_region): New.
	(is_a_helper <const decl_region *>::test): New.
	(class field_region): New.
	(template <> struct default_hash_traits<field_region::key_t>): New.
	(class array_region): Delete.
	(class element_region): New.
	(is_a_helper <array_region *>::test): Delete.
	(is_a_helper <const element_region *>::test): New.
	(template <> struct default_hash_traits<element_region::key_t>):
	New.
	(class offset_region): New.
	(is_a_helper <const offset_region *>::test): New.
	(template <> struct default_hash_traits<offset_region::key_t>):
	New.
	(class cast_region): New.
	(is_a_helper <const cast_region *>::test): New.
	(template <> struct default_hash_traits<cast_region::key_t>): New.
	(class heap_allocated_region): New.
	(class alloca_region): New.
	(class string_region): New.
	(is_a_helper <const string_region *>::test): New.
	(class unknown_region): New.
	(class region_model_manager): New.
	(struct append_ssa_names_cb_data): New.
	(class call_details): New.
	(region_model::region_model): Add region_model_manager param.
	(region_model::print_svalue): Delete.
	(region_model::dump_dot_to_pp): Delete.
	(region_model::dump_dot_to_file): Delete.
	(region_model::dump_dot): Delete.
	(region_model::dump_to_pp): Drop summarize param in favor of
	simple and multiline.
	(region_model::dump): Likewise.
	(region_model::summarize_to_pp): Delete.
	(region_model::summarize): Delete.
	(region_model::void canonicalize): Drop ctxt param.
	(region_model::void check_for_poison): Delete.
	(region_model::get_gassign_result): New.
	(region_model::impl_call_alloca): New.
	(region_model::impl_call_analyzer_describe): New.
	(region_model::impl_call_analyzer_eval): New.
	(region_model::impl_call_builtin_expect): New.
	(region_model::impl_call_calloc): New.
	(region_model::impl_call_free): New.
	(region_model::impl_call_malloc): New.
	(region_model::impl_call_memset): New.
	(region_model::impl_call_strlen): New.
	(region_model::get_reachable_svalues): New.
	(region_model::handle_phi): Drop is_back_edge param.
	(region_model::region_id get_root_rid): Delete.
	(region_model::root_region *get_root_region): Delete.
	(region_model::region_id get_stack_region_id): Delete.
	(region_model::push_frame): Convert from region_id and svalue_id
	to const region * and const svalue *.
	(region_model::get_current_frame_id): Replace with...
	(region_model::get_current_frame): ...this.
	(region_model::pop_frame): Convert from region_id to
	const region *.  Drop purge and stats param.  Add out_result.
	(region_model::function *get_function_at_depth): Delete.
	(region_model::get_globals_region_id): Delete.
	(region_model::add_svalue): Delete.
	(region_model::replace_svalue): Delete.
	(region_model::add_region): Delete.
	(region_model::add_region_for_type): Delete.
	(region_model::get_svalue): Delete.
	(region_model::get_region): Delete.
	(region_model::get_lvalue): Convert from region_id to
	const region *.
	(region_model::get_rvalue): Convert from svalue_id to
	const svalue *.
	(region_model::get_or_create_ptr_svalue): Delete.
	(region_model::get_or_create_constant_svalue): Delete.
	(region_model::get_svalue_for_fndecl): Delete.
	(region_model::get_svalue_for_label): Delete.
	(region_model::get_region_for_fndecl): Delete.
	(region_model::get_region_for_label): Delete.
	(region_model::get_frame_at_index (int index) const;): New.
	(region_model::maybe_cast): Delete.
	(region_model::maybe_cast_1): Delete.
	(region_model::get_field_region): Delete.
	(region_model::id deref_rvalue): Convert from region_id and
	svalue_id to const region * and const svalue *.  Drop overload,
	passing in both a tree and an svalue.
	(region_model::set_value): Convert from region_id and svalue_id to
	const region * and const svalue *.
	(region_model::set_to_new_unknown_value): Delete.
	(region_model::clobber_region (const region *reg);): New.
	(region_model::purge_region (const region *reg);): New.
	(region_model::zero_fill_region (const region *reg);): New.
	(region_model::mark_region_as_unknown (const region *reg);): New.
	(region_model::copy_region): Convert from region_id to
	const region *.
	(region_model::eval_condition): Convert from svalue_id to
	const svalue *.
	(region_model::eval_condition_without_cm): Likewise.
	(region_model::compare_initial_and_pointer): New.
	(region_model:maybe_get_constant): Delete.
	(region_model::add_new_malloc_region): Delete.
	(region_model::get_representative_tree): Convert from svalue_id to
	const svalue *.
	(region_model::get_representative_path_var): Delete decl taking a
	region_id in favor of two decls, for svalue vs region, with an
	svalue_set to ensure termination.
	(region_model::get_path_vars_for_svalue): Delete.
	(region_model::create_region_for_heap_alloc): New.
	(region_model::create_region_for_alloca): New.
	(region_model::purge_unused_svalues): Delete.
	(region_model::remap_svalue_ids): Delete.
	(region_model::remap_region_ids): Delete.
	(region_model::purge_regions): Delete.
	(region_model::get_num_svalues): Delete.
	(region_model::get_num_regions): Delete.
	(region_model::get_descendents): Delete.
	(region_model::get_store): New.
	(region_model::delete_region_and_descendents): Delete.
	(region_model::get_manager): New.
	(region_model::unbind_region_and_descendents): New.
	(region_model::can_merge_with_p): Add point param.  Drop
	svalue_id_merger_mapping.
	(region_model::get_value_by_name): Delete.
	(region_model::convert_byte_offset_to_array_index): Delete.
	(region_model::get_or_create_mem_ref): Delete.
	(region_model::get_or_create_pointer_plus_expr): Delete.
	(region_model::get_or_create_view): Delete.
	(region_model::get_lvalue_1): Convert from region_id to
	const region *.
	(region_model::get_rvalue_1): Convert from svalue_id to
	const svalue *.
	(region_model::get_ssa_name_regions_for_current_frame): New.
	(region_model::append_ssa_names_cb): New.
	(region_model::get_store_value): New.
	(region_model::copy_struct_region): Delete.
	(region_model::copy_union_region): Delete.
	(region_model::copy_array_region): Delete.
	(region_model::region_exists_p): New.
	(region_model::make_region_for_unexpected_tree_code): Delete.
	(region_model::loop_replay_fixup): New.
	(region_model::poison_any_pointers_to_bad_regions): Delete.
	(region_model::poison_any_pointers_to_descendents): New.
	(region_model::dump_summary_of_rep_path_vars): Delete.
	(region_model::on_top_level_param): New.
	(region_model::record_dynamic_extents): New.
	(region_model::m_mgr;): New.
	(region_model::m_store;): New.
	(region_model::m_svalues;): Delete.
	(region_model::m_regions;): Delete.
	(region_model::m_root_rid;): Delete.
	(region_model::m_current_frame;): New.
	(region_model_context::remap_svalue_ids): Delete.
	(region_model_context::can_purge_p): Delete.
	(region_model_context::on_svalue_leak): New.
	(region_model_context::on_svalue_purge): Delete.
	(region_model_context::on_liveness_change): New.
	(region_model_context::on_inherited_svalue): Delete.
	(region_model_context::on_cast): Delete.
	(region_model_context::on_unknown_change): Convert from svalue_id to
	const svalue * and add is_mutable.
	(class noop_region_model_context): Update for region_model_context
	changes.
	(model_merger::model_merger): Add program_point.  Drop
	svalue_id_merger_mapping.
	(model_merger::dump_to_pp): Add "simple" param.
	(model_merger::dump): Likewise.
	(model_merger::get_region_a): Delete.
	(model_merger::get_region_b): Delete.
	(model_merger::can_merge_values_p): Delete.
	(model_merger::record_regions): Delete.
	(model_merger::record_svalues): Delete.
	(model_merger::m_point): New field.
	(model_merger::m_map_regions_from_a_to_m): Delete.
	(model_merger::m_map_regions_from_b_to_m): Delete.
	(model_merger::m_sid_mapping): Delete.
	(struct svalue_id_merger_mapping): Delete.
	(class engine): New.
	(struct canonicalization): Delete.
	(inchash::add): Delete decls for hashing svalue_id and region_id.
	(test_region_model_context::on_unexpected_tree_code): Require t to
	be non-NULL.
	(selftest::assert_condition): Add overload comparing a pair of
	const svalue *.
	* sm-file.cc: Include "tristate.h", "selftest.h",
	"analyzer/call-string.h", "analyzer/program-point.h",
	"analyzer/store.h", and "analyzer/region-model.h".
	(fileptr_state_machine::get_default_state): New.
	(fileptr_state_machine::on_stmt): Remove calls to
	get_readable_tree in favor of get_diagnostic_tree.
	* sm-malloc.cc: Include "tristate.h", "selftest.h",
	"analyzer/call-string.h", "analyzer/program-point.h",
	"analyzer/store.h", and "analyzer/region-model.h".
	(malloc_state_machine::get_default_state): New.
	(malloc_state_machine::reset_when_passed_to_unknown_fn_p): New.
	(malloc_diagnostic::describe_state_change): Handle change.m_expr
	being NULL.
	(null_arg::emit): Avoid printing "NULL '0'".
	(null_arg::describe_final_event): Avoid printing "(0) NULL".
	(malloc_leak::emit): Handle m_arg being NULL.
	(malloc_leak::describe_final_event): Handle ev.m_expr being NULL.
	(malloc_state_machine::on_stmt): Don't call get_readable_tree.
	Call get_diagnostic_tree when creating pending diagnostics.
	Update for is_zero_assignment becoming a member function of
	sm_ctxt.
	Don't transition to m_non_heap for ADDR_EXPR(MEM_REF()).
	(malloc_state_machine::reset_when_passed_to_unknown_fn_p): New
	vfunc implementation.
	* sm-sensitive.cc (sensitive_state_machine::warn_for_any_exposure): Call
	get_diagnostic_tree and pass the result to warn_for_state.
	* sm-signal.cc: Move includes of "analyzer/call-string.h" and
	"analyzer/program-point.h" to before "analyzer/region-model.h",
	and also include "analyzer/store.h" before it.
	(signal_unsafe_call::describe_state_change): Use
	get_dest_function to get handler.
	(update_model_for_signal_handler): Pass manager to region_model
	ctor.
	(register_signal_handler::impl_transition): Update for changes to
	get_or_create_node and add_edge.
	* sm-taint.cc (taint_state_machine::on_stmt): Remove calls to
	get_readable_tree, replacing them when calling warn_for_state with
	calls to get_diagnostic_tree.
	* sm.cc (is_zero_assignment): Delete.
	(any_pointer_p): Move to within namespace ana.
	* sm.h (is_zero_assignment): Remove decl.
	(any_pointer_p): Move decl to within namespace ana.
	(state_machine::get_default_state): New vfunc.
	(state_machine::reset_when_passed_to_unknown_fn_p): New vfunc.
	(sm_context::get_readable_tree): Rename to...
	(sm_context::get_diagnostic_tree): ...this.
	(sm_context::is_zero_assignment): New vfunc.
	* store.cc: New file.
	* store.h: New file.
	* svalue.cc: New file.

gcc/testsuite/ChangeLog:
	PR analyzer/93032
	PR analyzer/93938
	PR analyzer/94011
	PR analyzer/94099
	PR analyzer/94399
	PR analyzer/94458
	PR analyzer/94503
	PR analyzer/94640
	PR analyzer/94688
	PR analyzer/94689
	PR analyzer/94839
	PR analyzer/95026
	PR analyzer/95042
	PR analyzer/95240
	* g++.dg/analyzer/pr93212.C: Add dg-warning for dangling
	reference.
	* g++.dg/analyzer/pr93950.C: Remove xfail.
	* g++.dg/analyzer/pr94011.C: New test.
	* g++.dg/analyzer/pr94028.C: Remove leak false positives; mark as
	failing on C++98.
	* g++.dg/analyzer/pr94503.C: New test.
	* g++.dg/analyzer/pr95042.C: New test.
	* gcc.dg/analyzer/CVE-2005-1689-dedupe-issue-2.c: New test.
	* gcc.dg/analyzer/CVE-2005-1689-dedupe-issue.c: Add xfail.
	* gcc.dg/analyzer/CVE-2005-1689-minimal.c:
	Include "analyzer-decls.h".
	(test_4, test_5, test_6, test_7, test_8): New tests.
	* gcc.dg/analyzer/abs-1.c: New test.
	* gcc.dg/analyzer/aliasing-1.c: New test.
	* gcc.dg/analyzer/aliasing-2.c: New test.
	* gcc.dg/analyzer/analyzer-decls.h (__analyzer_describe): New
	decl.
	(__analyzer_dump_num_heap_regions): Remove.
	* gcc.dg/analyzer/attribute-nonnull.c: Add dg-warnings for cases
	where NULL is directly used as an argument.
	* gcc.dg/analyzer/bzero-1.c: New test.
	* gcc.dg/analyzer/casts-1.c: New test.
	* gcc.dg/analyzer/casts-2.c: New test.
	* gcc.dg/analyzer/compound-assignment-1.c
	(test_4): Remove xfail from leak false positive.
	(called_by_test_5a): Add "allocated here" expected message.
	(called_by_test_5b): Make expected leak message more precise.
	* gcc.dg/analyzer/compound-assignment-3.c: Update expected leak
	message.
	* gcc.dg/analyzer/compound-assignment-4.c: New test.
	* gcc.dg/analyzer/compound-assignment-5.c: New test.
	* gcc.dg/analyzer/conditionals-notrans.c: Remove xfails.
	* gcc.dg/analyzer/data-model-1.c (test_12d): Update expected
	results.
	(test_13): Remove xfail.
	(test_14): Remove xfail.
	(test_15): Remove xfail.
	(test_16): Remove xfails.  Add out-of-bounds access.
	(test_16_alt): Remove xfails.
	(test_23): Remove xfail.
	(test_24): Remove xfail.
	(test_25): Remove xfail.
	(test_26): Update expected result.  Remove xfail.  Add xfail.
	(test_27): Remove xfails.
	(test_29): Add __analyzer_eval pointer comparisons.
	(test_41): Generalize expected output for u.ptr comparison with
	NULL for targets where this could be known to be false.
	(test_42): Remove xfail.
	(test_51): Remove xfails.
	* gcc.dg/analyzer/data-model-13.c: Update for improvements to
	source location and wording of leak message.
	* gcc.dg/analyzer/data-model-14.c: Remove -fanalyzer-fine-grained.
	(test_1): Update for improvement to expected message.
	(test_2): Remove xfail.
	* gcc.dg/analyzer/data-model-18.c: Remove xfail.
	* gcc.dg/analyzer/data-model-20.c: New test.
	* gcc.dg/analyzer/data-model-5.c: Add dg-warning for deref of
	NULL.  Add xfailing false leak.
	* gcc.dg/analyzer/data-model-5b.c: Add xfailing false leak.
	* gcc.dg/analyzer/data-model-5c.c: Update xfailing false leak.
	* gcc.dg/analyzer/data-model-5d.c: Reimplement.
	* gcc.dg/analyzer/data-model-6.c: Delete test.
	* gcc.dg/analyzer/data-model-8.c: Remove xfail.
	* gcc.dg/analyzer/describe-1.c: New test.
	* gcc.dg/analyzer/dot-output.c: Remove xfail.
	* gcc.dg/analyzer/explode-1.c: Add expected leak warning.
	* gcc.dg/analyzer/explode-2.c: Add expected leak warnings.  Mark
	double-free warnings as xfail for now.
	* gcc.dg/analyzer/feasibility-1.c: New test.
	* gcc.dg/analyzer/first-field-1.c: New test.
	* gcc.dg/analyzer/first-field-2.c: New test.
	* gcc.dg/analyzer/init.c: New test.
	* gcc.dg/analyzer/leak-2.c: New test.
	* gcc.dg/analyzer/loop-0-up-to-n-by-1-with-iter-obj.c: New test.
	* gcc.dg/analyzer/loop-0-up-to-n-by-1.c: New test.
	* gcc.dg/analyzer/loop-2a.c: Update expected behavior.
	* gcc.dg/analyzer/loop-3.c: Mark use-after-free as xfail.  Add
	expected warning about deref of unchecked pointer.
	* gcc.dg/analyzer/loop-4.c: Remove -fno-analyzer-state-purge.
	Update expected behavior.
	* gcc.dg/analyzer/loop-n-down-to-1-by-1.c: New test.
	* gcc.dg/analyzer/loop-start-down-to-end-by-1.c: New test.
	* gcc.dg/analyzer/loop-start-down-to-end-by-step.c: New test.
	* gcc.dg/analyzer/loop-start-to-end-by-step.c: New test.
	* gcc.dg/analyzer/loop-start-up-to-end-by-1.c: New test.
	* gcc.dg/analyzer/loop.c: Remove -fno-analyzer-state-purge.
	Update expected behavior.
	* gcc.dg/analyzer/malloc-1.c: Remove xfails from leak false
	positives.  Update expected wording of global_link.m_ptr leak.
	(test_49): New test.
	* gcc.dg/analyzer/malloc-4.c: Remove leak false positive.  Update
	expected wording of leak warning.
	* gcc.dg/analyzer/malloc-in-loop.c: New test.
	* gcc.dg/analyzer/malloc-ipa-8-double-free.c: Update expected path
	to show call to wrapped_malloc.
	* gcc.dg/analyzer/malloc-ipa-8-unchecked.c: Remove
	-fanalyzer-verbose-state-changes.
	* gcc.dg/analyzer/malloc-paths-9.c: Remove comment about duplicate
	warnings.  Remove duplicate use-after-free paths.
	* gcc.dg/analyzer/malloc-vs-local-1a.c: Add dg-warning for deref
	of unchecked pointer.  Update expected number of enodes.
	* gcc.dg/analyzer/malloc-vs-local-2.c: Likewise.
	* gcc.dg/analyzer/malloc-vs-local-3.c: Add dg-warning for deref of
	unchecked pointer.  Update expected number of enodes.  Avoid
	overspecifying the leak message.
	* gcc.dg/analyzer/memset-1.c: New test.
	* gcc.dg/analyzer/paths-3.c: Update expected number of enodes.
	* gcc.dg/analyzer/paths-4.c: Likewise.
	* gcc.dg/analyzer/paths-6.c: Likewise.
	* gcc.dg/analyzer/paths-7.c: Likewise.
	* gcc.dg/analyzer/pr93032-mztools-simplified.c: New test.
	* gcc.dg/analyzer/pr93032-mztools.c: New test.
	* gcc.dg/analyzer/pr93382.c: Mark taint tests as failing.
	* gcc.dg/analyzer/pr93938.c: New test.
	* gcc.dg/analyzer/pr94099.c: Replace uninit dg-warning with
	dg-warning for NULL dereference.
	* gcc.dg/analyzer/pr94399.c: New test.
	* gcc.dg/analyzer/pr94447.c: Add dg-warning for NULL dereference.
	* gcc.dg/analyzer/pr94458.c: New test.
	* gcc.dg/analyzer/pr94640.c: New test.
	* gcc.dg/analyzer/pr94688.c: New test.
	* gcc.dg/analyzer/pr94689.c: New test.
	* gcc.dg/analyzer/pr94839.c: New test.
	* gcc.dg/analyzer/pr95026.c: New test.
	* gcc.dg/analyzer/pr95240.c: New test.
	* gcc.dg/analyzer/refcounting-1.c: New test.
	* gcc.dg/analyzer/single-field.c: New test.
	* gcc.dg/analyzer/stale-frame-1.c: New test.
	* gcc.dg/analyzer/symbolic-1.c: New test.
	* gcc.dg/analyzer/symbolic-2.c: New test.
	* gcc.dg/analyzer/symbolic-3.c: New test.
	* gcc.dg/analyzer/symbolic-4.c: New test.
	* gcc.dg/analyzer/symbolic-5.c: New test.
	* gcc.dg/analyzer/symbolic-6.c: New test.
	* gcc.dg/analyzer/taint-1.c: Mark the "gets unchecked value"
	events as failing for now.  Update dg-message directives to avoid
	relying on numbering.
	* gcc.dg/analyzer/torture/loop-inc-ptr-1.c: New test.
	* gcc.dg/analyzer/torture/loop-inc-ptr-2.c: New test.
	* gcc.dg/analyzer/torture/loop-inc-ptr-3.c: New test.
	* gcc.dg/analyzer/unknown-fns-2.c: New test.
	* gcc.dg/analyzer/unknown-fns-3.c: New test.
	* gcc.dg/analyzer/unknown-fns-4.c: New test.
	* gcc.dg/analyzer/unknown-fns.c: Update dg-warning to reflect fixed
	source location for leak diagnostic.
	* gcc.dg/analyzer/use-after-free.c: New test.
	* gcc.dg/analyzer/vla-1.c: New test.
	* gcc.dg/analyzer/zlib-4.c: Rewrite to avoid "exit" calls.  Add
	expected leak warnings.
	* gfortran.dg/analyzer/pr93993.f90: Remove leak of tm warning,
	which seems to have been a false positive.

1 files changed, 490 insertions, 781 deletions

diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc
index 1a5843b..ede20a7 100644
--- a/gcc/analyzer/program-state.cc
+++ b/gcc/analyzer/program-state.cc
@@ -33,13 +33,15 @@ along with GCC; see the file COPYING3.  If not see
 #include "tristate.h"
 #include "ordered-hash-map.h"
 #include "selftest.h"
+#include "analyzer/call-string.h"
+#include "analyzer/program-point.h"
+#include "analyzer/store.h"
 #include "analyzer/region-model.h"
 #include "analyzer/program-state.h"
 #include "analyzer/constraint-manager.h"
 #include "alloc-pool.h"
 #include "fibonacci_heap.h"
 #include "shortest-paths.h"
-#include "analyzer/constraint-manager.h"
 #include "diagnostic-event-id.h"
 #include "analyzer/pending-diagnostic.h"
 #include "analyzer/diagnostic-manager.h"
@@ -50,8 +52,6 @@ along with GCC; see the file COPYING3.  If not see
 #include "cgraph.h"
 #include "digraph.h"
 #include "analyzer/supergraph.h"
-#include "analyzer/call-string.h"
-#include "analyzer/program-point.h"
 #include "analyzer/program-state.h"
 #include "analyzer/exploded-graph.h"
 #include "analyzer/state-purge.h"
@@ -99,12 +99,23 @@ extrinsic_state::dump () const
   dump_to_file (stderr);
 }
 
+/* Get the region_model_manager for this extrinsic_state.  */
+
+region_model_manager *
+extrinsic_state::get_model_manager () const
+{
+  if (m_engine)
+    return m_engine->get_model_manager ();
+  else
+    return NULL; /* for selftests.  */
+}
+
 /* class sm_state_map.  */
 
 /* sm_state_map's ctor.  */
 
-sm_state_map::sm_state_map ()
-: m_map (), m_global_state (0)
+sm_state_map::sm_state_map (const state_machine &sm, int sm_idx)
+: m_sm (sm), m_sm_idx (sm_idx), m_map (), m_global_state (0)
 {
 }
 
@@ -116,77 +127,56 @@ 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 ();
-  result->m_global_state = m_global_state;
-  for (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.
+/* Print this sm_state_map to PP.
    If MODEL is non-NULL, print representative tree values where
    available.  */
 
 void
-sm_state_map::print (const state_machine &sm, const region_model *model,
-		     pretty_printer *pp) const
+sm_state_map::print (const region_model *model,
+		      bool simple, bool multiline,
+		      pretty_printer *pp) const
 {
   bool first = true;
-  pp_string (pp, "{");
+  if (!multiline)
+    pp_string (pp, "{");
   if (m_global_state != 0)
     {
-      pp_printf (pp, "global: %s", sm.get_state_name (m_global_state));
+      if (multiline)
+	pp_string (pp, "  ");
+      pp_printf (pp, "global: %s", m_sm.get_state_name (m_global_state));
+      if (multiline)
+	pp_newline (pp);
       first = false;
     }
   for (map_t::iterator iter = m_map.begin ();
        iter != m_map.end ();
        ++iter)
     {
-      if (!first)
+      if (multiline)
+	pp_string (pp, "  ");
+      else if (!first)
 	pp_string (pp, ", ");
       first = false;
-      svalue_id sid = (*iter).first;
-      sid.print (pp);
+      const svalue *sval = (*iter).first;
+      pp_pointer (pp, sval);
+      pp_string (pp, ": ");
+      sval->dump_to_pp (pp, simple);
 
       entry_t e = (*iter).second;
-      pp_printf (pp, ": %s", sm.get_state_name (e.m_state));
+      pp_printf (pp, ": %s", m_sm.get_state_name (e.m_state));
       if (model)
-	if (tree rep = model->get_representative_tree (sid))
+	if (tree rep = model->get_representative_tree (sval))
 	  {
 	    pp_string (pp, " (");
 	    dump_quoted_tree (pp, rep);
 	    pp_character (pp, ')');
 	  }
-      if (!e.m_origin.null_p ())
+      if (e.m_origin)
 	{
 	  pp_string (pp, " (origin: ");
-	  e.m_origin.print (pp);
+	  pp_pointer (pp, e.m_origin);
+	  pp_string (pp, ": ");
+	  e.m_origin->dump_to_pp (pp, simple);
 	  if (model)
 	    if (tree rep = model->get_representative_tree (e.m_origin))
 	      {
@@ -196,19 +186,22 @@ sm_state_map::print (const state_machine &sm, const region_model *model,
 	      }
 	  pp_string (pp, ")");
 	}
+      if (multiline)
+	pp_newline (pp);
     }
-  pp_string (pp, "}");
+  if (!multiline)
+    pp_string (pp, "}");
 }
 
-/* Dump this object (for SM) to stderr.  */
+/* Dump this object to stderr.  */
 
 DEBUG_FUNCTION void
-sm_state_map::dump (const state_machine &sm) const
+sm_state_map::dump (bool simple) const
 {
   pretty_printer pp;
   pp_show_color (&pp) = pp_show_color (global_dc->printer);
   pp.buffer->stream = stderr;
-  print (sm, NULL, &pp);
+  print (NULL, simple, true, &pp);
   pp_newline (&pp);
   pp_flush (&pp);
 }
@@ -237,10 +230,10 @@ sm_state_map::hash () const
        ++iter)
     {
       inchash::hash hstate;
-      inchash::add ((*iter).first, hstate);
+      hstate.add_ptr ((*iter).first);
       entry_t e = (*iter).second;
       hstate.add_int (e.m_state);
-      inchash::add (e.m_origin, hstate);
+      hstate.add_ptr (e.m_origin);
       result ^= hstate.end ();
     }
   result ^= m_global_state;
@@ -263,9 +256,9 @@ sm_state_map::operator== (const sm_state_map &other) const
        iter != m_map.end ();
        ++iter)
     {
-      svalue_id sid = (*iter).first;
+      const svalue *sval = (*iter).first;
       entry_t e = (*iter).second;
-      entry_t *other_slot = const_cast <map_t &> (other.m_map).get (sid);
+      entry_t *other_slot = const_cast <map_t &> (other.m_map).get (sval);
       if (other_slot == NULL)
 	return false;
       if (e != *other_slot)
@@ -277,34 +270,63 @@ sm_state_map::operator== (const sm_state_map &other) const
   return true;
 }
 
-/* Get the state of SID within this object.
+/* Get the state of SVAL within this object.
    States default to the start state.  */
 
 state_machine::state_t
-sm_state_map::get_state (svalue_id sid) const
+sm_state_map::get_state (const svalue *sval,
+			  const extrinsic_state &ext_state) const
 {
-  gcc_assert (!sid.null_p ());
+  gcc_assert (sval);
+
+  sval = canonicalize_svalue (sval, ext_state);
 
   if (entry_t *slot
-      = const_cast <map_t &> (m_map).get (sid))
+      = const_cast <map_t &> (m_map).get (sval))
     return slot->m_state;
-  else
-    return 0;
+
+  /* SVAL has no explicit sm-state.
+     If this sm allows for state inheritance, then SVAL might have implicit
+     sm-state inherited via a parent.
+     For example INIT_VAL(foo.field) might inherit taintedness state from
+     INIT_VAL(foo).  */
+  if (m_sm.inherited_state_p ())
+    if (region_model_manager *mgr = ext_state.get_model_manager ())
+      if (const initial_svalue *init_sval = sval->dyn_cast_initial_svalue ())
+	{
+	  const region *reg = init_sval->get_region ();
+	  /* Try recursing upwards (up to the base region for the cluster).  */
+	  if (!reg->base_region_p ())
+	    if (const region *parent_reg = reg->get_parent_region ())
+	      {
+		const svalue *parent_init_sval
+		  = mgr->get_or_create_initial_value (parent_reg);
+		state_machine::state_t parent_state
+		  = get_state (parent_init_sval, ext_state);
+		if (parent_state)
+		  return parent_state;
+	      }
+	}
+
+  return m_sm.get_default_state (sval);
 }
 
-/* Get the "origin" svalue_id for any state of SID.  */
+/* Get the "origin" svalue for any state of SVAL.  */
 
-svalue_id
-sm_state_map::get_origin (svalue_id sid) const
+const svalue *
+sm_state_map::get_origin (const svalue *sval,
+			   const extrinsic_state &ext_state) const
 {
-  gcc_assert (!sid.null_p ());
+  gcc_assert (sval);
+
+  sval = canonicalize_svalue (sval, ext_state);
 
   entry_t *slot
-    = const_cast <map_t &> (m_map).get (sid);
+    = const_cast <map_t &> (m_map).get (sval);
   if (slot)
     return slot->m_origin;
   else
-    return svalue_id::null ();
+    return NULL;
 }
 
 /* Set the state of SID within MODEL to STATE, recording that
@@ -312,28 +334,21 @@ sm_state_map::get_origin (svalue_id sid) const
 
 void
 sm_state_map::set_state (region_model *model,
-			 svalue_id sid,
+			 const svalue *sval,
 			 state_machine::state_t state,
-			 svalue_id origin)
+			 const svalue *origin,
+			 const extrinsic_state &ext_state)
 {
   if (model == NULL)
     return;
-  equiv_class &ec = model->get_constraints ()->get_equiv_class (sid);
-  if (!set_state (ec, state, origin))
-    return;
 
-  /* 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;
+  /* Reject attempts to set state on UNKNOWN.  */
+  if (sval->get_kind () == SK_UNKNOWN)
+    return;
 
-      tristate eq = model->eval_condition_without_cm (sid, EQ_EXPR, other_sid);
-      if (eq.is_true ())
-	impl_set_state (other_sid, state, origin);
-    }
+  equiv_class &ec = model->get_constraints ()->get_equiv_class (sval);
+  if (!set_state (ec, state, origin, ext_state))
+    return;
 }
 
 /* Set the state of EC to STATE, recording that the state came from
@@ -343,35 +358,40 @@ sm_state_map::set_state (region_model *model,
 bool
 sm_state_map::set_state (const equiv_class &ec,
 			 state_machine::state_t state,
-			 svalue_id origin)
+			 const svalue *origin,
+			 const extrinsic_state &ext_state)
 {
   int i;
-  svalue_id *sid;
+  const svalue *sval;
   bool any_changed = false;
-  FOR_EACH_VEC_ELT (ec.m_vars, i, sid)
-    any_changed |= impl_set_state (*sid, state, origin);
+  FOR_EACH_VEC_ELT (ec.m_vars, i, sval)
+    any_changed |= impl_set_state (sval, state, origin, ext_state);
   return any_changed;
 }
 
-/* Set state of SID to STATE, bypassing equivalence classes.
+/* Set state of SVAL to STATE, bypassing equivalence classes.
    Return true if the state changed.  */
 
 bool
-sm_state_map::impl_set_state (svalue_id sid, state_machine::state_t state,
-			      svalue_id origin)
+sm_state_map::impl_set_state (const svalue *sval,
+			      state_machine::state_t state,
+			      const svalue *origin,
+			      const extrinsic_state &ext_state)
 {
-  if (get_state (sid) == state)
+  sval = canonicalize_svalue (sval, ext_state);
+
+  if (get_state (sval, ext_state) == state)
     return false;
 
   /* Special-case state 0 as the default value.  */
   if (state == 0)
     {
-      if (m_map.get (sid))
-	m_map.remove (sid);
+      if (m_map.get (sval))
+	m_map.remove (sval);
       return true;
     }
-  gcc_assert (!sid.null_p ());
-  m_map.put (sid, entry_t (state, origin));
+  gcc_assert (sval);
+  m_map.put (sval, entry_t (state, origin));
   return true;
 }
 
@@ -391,203 +411,105 @@ sm_state_map::get_global_state () const
   return m_global_state;
 }
 
-/* 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.  */
+/* Purge any state for SVAL.
+   If !SM::can_purge_p, then report the state as leaking,
+   using CTXT.  */
 
 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,
-					region_model_context *ctxt)
+sm_state_map::on_svalue_leak (const svalue *sval,
+			      impl_region_model_context *ctxt)
 {
-  logger * const logger = eg.get_logger ();
-  if (logger)
+  if (state_machine::state_t state = get_state (sval, ctxt->m_ext_state))
     {
-      if (fndecl)
-	logger->log ("function %qE is unknown to checker %qs",
-		     fndecl, sm.get_name ());
-      else
-	logger->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, ctxt);
-      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, ctxt);
-	  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, ctxt);
-      set_state (new_model, lhs_sid, 0, svalue_id::null ());
+      if (!m_sm.can_purge_p (state))
+	ctxt->on_state_leak (m_sm, sval, state);
+      m_map.remove (sval);
     }
 }
 
-/* Update this map based on MAP.  */
+/* Purge any state for svalues that aren't live with respect to LIVE_SVALUES
+   and MODEL.  */
 
 void
-sm_state_map::remap_svalue_ids (const svalue_id_map &map)
+sm_state_map::on_liveness_change (const svalue_set &live_svalues,
+				  const region_model *model,
+				  impl_region_model_context *ctxt)
 {
-  map_t tmp_map;
+  svalue_set svals_to_unset;
 
-  /* Build an intermediate map, using the new sids.  */
   for (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 (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 (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 ())
+      const svalue *iter_sval = (*iter).first;
+      if (!iter_sval->live_p (live_svalues, model))
 	{
-	  /* Complain about leaks here.  */
+	  svals_to_unset.add (iter_sval);
 	  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);
-	}
-      else if ((*iter).second.m_origin.as_int () >= first_unused_sid.as_int ())
-	{
-	  /* If the origin svalue is being purged, then reset it to null.  */
-	  (*iter).second.m_origin = svalue_id::null ();
+	  if (!m_sm.can_purge_p (e.m_state))
+	    ctxt->on_state_leak (m_sm, iter_sval, e.m_state);
 	}
     }
 
-  int i;
-  svalue_id *dst_sid;
-  FOR_EACH_VEC_ELT (to_remove, i, dst_sid)
-    m_map.remove (*dst_sid);
-
-  return to_remove.length ();
+  for (svalue_set::iterator iter = svals_to_unset.begin ();
+       iter != svals_to_unset.end (); ++iter)
+    m_map.remove (*iter);
 }
 
-/* Set the state of CHILD_SID to that of PARENT_SID.  */
+/* Purge state from SVAL (in response to a call to an unknown function).  */
 
 void
-sm_state_map::on_inherited_svalue (svalue_id parent_sid,
-				   svalue_id child_sid)
+sm_state_map::on_unknown_change (const svalue *sval,
+				 bool is_mutable,
+				 const extrinsic_state &ext_state)
 {
-  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));
-}
-
-/* Purge state from SID (in response to a call to an unknown function).  */
-
-void
-sm_state_map::on_unknown_change (svalue_id sid)
-{
-  impl_set_state (sid, (state_machine::state_t)0, svalue_id::null ());
-}
-
-/* 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
+  svalue_set svals_to_unset;
 
   for (map_t::iterator iter = m_map.begin ();
        iter != m_map.end ();
        ++iter)
     {
-      svalue_id sid = (*iter).first;
+      const svalue *key = (*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);
+      /* We only want to purge state for some states when things
+	 are mutable.  For example, in sm-malloc.cc, an on-stack ptr
+	 doesn't stop being stack-allocated when passed to an unknown fn.  */
+      if (!m_sm.reset_when_passed_to_unknown_fn_p (e.m_state, is_mutable))
+	continue;
+      if (key == sval)
+	svals_to_unset.add (key);
+      /* If we have INIT_VAL(BASE_REG), then unset any INIT_VAL(REG)
+	 for REG within BASE_REG.  */
+      if (const initial_svalue *init_sval = sval->dyn_cast_initial_svalue ())
+	if (const initial_svalue *init_key = key->dyn_cast_initial_svalue ())
+	  {
+	    const region *changed_reg = init_sval->get_region ();
+	    const region *changed_key = init_key->get_region ();
+	    if (changed_key->get_base_region () == changed_reg)
+	      svals_to_unset.add (key);
+	  }
     }
+
+  for (svalue_set::iterator iter = svals_to_unset.begin ();
+       iter != svals_to_unset.end (); ++iter)
+    impl_set_state (*iter, (state_machine::state_t)0, NULL, ext_state);
+}
+
+/* Canonicalize SVAL before getting/setting it within the map.
+   Convert all NULL pointers to (void *) to avoid state explosions
+   involving all of the various (foo *)NULL vs (bar *)NULL.  */
+
+const svalue *
+sm_state_map::canonicalize_svalue (const svalue *sval,
+				   const extrinsic_state &ext_state)
+{
+  region_model_manager *mgr = ext_state.get_model_manager ();
+  if (mgr && sval->get_type () && POINTER_TYPE_P (sval->get_type ()))
+    if (tree cst = sval->maybe_get_constant ())
+      if (zerop (cst))
+	return mgr->get_or_create_constant_svalue (null_pointer_node);
+
+  return sval;
 }
 
 /* class program_state.  */
@@ -595,13 +517,19 @@ sm_state_map::validate (const state_machine &sm,
 /* program_state's ctor.  */
 
 program_state::program_state (const extrinsic_state &ext_state)
-: m_region_model (new region_model ()),
+: m_region_model (NULL),
   m_checker_states (ext_state.get_num_checkers ()),
   m_valid (true)
 {
-  int num_states = ext_state.get_num_checkers ();
+  engine *eng = ext_state.get_engine ();
+  region_model_manager *mgr = eng->get_model_manager ();
+  m_region_model = new region_model (mgr);
+  const int num_states = ext_state.get_num_checkers ();
   for (int i = 0; i < num_states; i++)
-    m_checker_states.quick_push (new sm_state_map ());
+    {
+      sm_state_map *sm = new sm_state_map (ext_state.get_sm (i), i);
+      m_checker_states.quick_push (sm);
+    }
 }
 
 /* program_state's copy ctor.  */
@@ -708,7 +636,7 @@ program_state::print (const extrinsic_state &ext_state,
 		      pretty_printer *pp) const
 {
   pp_printf (pp, "rmodel: ");
-  m_region_model->print (pp);
+  m_region_model->dump_to_pp (pp, true, false);
   pp_newline (pp);
 
   int i;
@@ -718,7 +646,7 @@ program_state::print (const extrinsic_state &ext_state,
       if (!smap->is_empty_p ())
 	{
 	  pp_printf (pp, "%s: ", ext_state.get_name (i));
-	  smap->print (ext_state.get_sm (i), m_region_model, pp);
+	  smap->print (m_region_model, true, false, pp);
 	  pp_newline (pp);
 	}
     }
@@ -729,17 +657,25 @@ program_state::print (const extrinsic_state &ext_state,
     }
 }
 
-/* Dump a representation of this state to PP.
-   If SUMMARIZE is true, print a one-line summary;
-   if false, print a detailed multiline representation.  */
+/* Dump a representation of this state to PP.  */
 
 void
 program_state::dump_to_pp (const extrinsic_state &ext_state,
-			   bool summarize,
+			   bool /*summarize*/, bool multiline,
 			   pretty_printer *pp) const
 {
-  pp_printf (pp, "rmodel: ");
-  m_region_model->dump_to_pp (pp, summarize);
+  if (!multiline)
+    pp_string (pp, "{");
+  {
+    pp_printf (pp, "rmodel:");
+    if (multiline)
+      pp_newline (pp);
+    else
+      pp_string (pp, " {");
+    m_region_model->dump_to_pp (pp, true, multiline);
+    if (!multiline)
+      pp_string (pp, "}");
+  }
 
   int i;
   sm_state_map *smap;
@@ -747,30 +683,34 @@ program_state::dump_to_pp (const extrinsic_state &ext_state,
     {
       if (!smap->is_empty_p ())
 	{
-	  if (summarize)
-	    pp_space (pp);
+	  if (!multiline)
+	    pp_string (pp, " {");
 	  pp_printf (pp, "%s: ", ext_state.get_name (i));
-	  smap->print (ext_state.get_sm (i), m_region_model, pp);
-	  if (!summarize)
+	  if (multiline)
 	    pp_newline (pp);
+	  smap->print (m_region_model, true, multiline, pp);
+	  if (!multiline)
+	    pp_string (pp, "}");
 	}
     }
 
   if (!m_valid)
     {
-      if (summarize)
+      if (!multiline)
 	pp_space (pp);
       pp_printf (pp, "invalid state");
-      if (!summarize)
+      if (multiline)
 	pp_newline (pp);
     }
+  if (!multiline)
+    pp_string (pp, "}");
 }
 
-/* Dump a multiline representation of this state to OUTF.  */
+/* Dump a representation of this state to OUTF.  */
 
 void
 program_state::dump_to_file (const extrinsic_state &ext_state,
-			     bool summarize,
+			     bool summarize, bool multiline,
 			     FILE *outf) const
 {
   pretty_printer pp;
@@ -778,7 +718,7 @@ program_state::dump_to_file (const extrinsic_state &ext_state,
   if (outf == stderr)
     pp_show_color (&pp) = pp_show_color (global_dc->printer);
   pp.buffer->stream = outf;
-  dump_to_pp (ext_state, summarize, &pp);
+  dump_to_pp (ext_state, summarize, multiline, &pp);
   pp_flush (&pp);
 }
 
@@ -788,7 +728,25 @@ DEBUG_FUNCTION void
 program_state::dump (const extrinsic_state &ext_state,
 		     bool summarize) const
 {
-  dump_to_file (ext_state, summarize, stderr);
+  dump_to_file (ext_state, summarize, true, stderr);
+}
+
+/* Update this program_state to reflect a top-level call to FUN.
+   The params will have initial_svalues.  */
+
+void
+program_state::push_frame (const extrinsic_state &ext_state ATTRIBUTE_UNUSED,
+			   function *fun)
+{
+  m_region_model->push_frame (fun, NULL, NULL);
+}
+
+/* Get the current function of this state.  */
+
+function *
+program_state::get_current_function () const
+{
+  return m_region_model->get_current_function ();
 }
 
 /* Determine if following edge SUCC from ENODE is valid within the graph EG
@@ -806,8 +764,7 @@ program_state::dump (const extrinsic_state &ext_state,
 bool
 program_state::on_edge (exploded_graph &eg,
 			const exploded_node &enode,
-			const superedge *succ,
-			state_change *change)
+			const superedge *succ)
 {
   /* Update state.  */
   const program_point &point = enode.get_point ();
@@ -824,7 +781,7 @@ program_state::on_edge (exploded_graph &eg,
 
   impl_region_model_context ctxt (eg, &enode,
 				  &enode.get_state (),
-				  this, change,
+				  this,
 				  last_stmt);
   if (!m_region_model->maybe_update_for_edge (*succ,
 					      last_stmt,
@@ -838,6 +795,10 @@ program_state::on_edge (exploded_graph &eg,
       return false;
     }
 
+  program_state::detect_leaks (enode.get_state (), *this,
+				NULL, eg.get_ext_state (),
+				&ctxt);
+
   return true;
 }
 
@@ -845,15 +806,12 @@ program_state::on_edge (exploded_graph &eg,
    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.  */
+   irrelevant state (e.g. at the end of functions).  */
 
 program_state
 program_state::prune_for_point (exploded_graph &eg,
 				const program_point &point,
-				state_change *change) const
+				const exploded_node *enode_for_diag) const
 {
   logger * const logger = eg.get_logger ();
   LOG_SCOPE (logger);
@@ -864,207 +822,110 @@ program_state::prune_for_point (exploded_graph &eg,
 
   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)
+      unsigned num_ssas_purged = 0;
+      auto_vec<const decl_region *> ssa_name_regs;
+      new_state.m_region_model->get_ssa_name_regions_for_current_frame
+	(&ssa_name_regs);
+      unsigned i;
+      const decl_region *reg;
+      FOR_EACH_VEC_ELT (ssa_name_regs, i, reg)
 	{
-	  tree var = (*iter).first;
-	  region_id rid = (*iter).second;
-	  if (TREE_CODE (var) == SSA_NAME)
+	  tree ssa_name = reg->get_decl ();
+	  const state_purge_per_ssa_name &per_ssa
+	    = pm->get_data_for_ssa_name (ssa_name);
+	  if (!per_ssa.needed_at_point_p (point.get_function_point ()))
 	    {
-	      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 ()))
+	      /* Don't purge bindings of SSA names to svalues
+		 that have unpurgable sm-state, so that leaks are
+		 reported at the end of the function, rather than
+		 at the last place that such an SSA name is referred to.
+
+		 But do purge them for temporaries (when SSA_NAME_VAR is
+		 NULL), so that we report for cases where a leak happens when
+		 a variable is overwritten with another value, so that the leak
+		 is reported at the point of overwrite, rather than having
+		 temporaries keep the value reachable until the frame is
+		 popped.  */
+	      const svalue *sval
+		= new_state.m_region_model->get_store_value (reg);
+	      if (!new_state.can_purge_p (eg.get_ext_state (), sval)
+		  && SSA_NAME_VAR (ssa_name))
 		{
-		  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).  */
-			  if (logger)
-			    logger->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))
-			  {
-			    if (logger)
-			      logger->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);
+		  /* (currently only state maps can keep things
+		     alive).  */
 		  if (logger)
-		    logger->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.  */
+		    logger->log ("not purging binding for %qE"
+				 " (used by state map)", ssa_name);
+		  continue;
 		}
+
+	      new_state.m_region_model->purge_region (reg);
+	      num_ssas_purged++;
 	    }
 	}
 
-      /* 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);
-  if (logger)
-    {
-      logger->log ("num svalues purged: %i", stats.m_num_svalues);
-      logger->log ("num regions purged: %i", stats.m_num_regions);
-      logger->log ("num equiv_classes purged: %i", stats.m_num_equiv_classes);
-      logger->log ("num constraints purged: %i", stats.m_num_constraints);
-      logger->log ("num sm map items purged: %i", stats.m_num_client_items);
+      if (num_ssas_purged > 0)
+	{
+	  if (logger)
+	    logger->log ("num_ssas_purged: %i", num_ssas_purged);
+	  impl_region_model_context ctxt (eg, enode_for_diag,
+					  this,
+					  &new_state,
+					  point.get_stmt ());
+	  detect_leaks (*this, new_state, NULL, eg.get_ext_state (), &ctxt);
+	}
     }
 
-  new_state.m_region_model->canonicalize (&ctxt);
+  new_state.m_region_model->canonicalize ();
 
   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.  */
+/* Get a representative tree to use for describing SVAL.  */
 
 tree
-program_state::get_representative_tree (svalue_id sid) const
+program_state::get_representative_tree (const svalue *sval) const
 {
-  return m_region_model->get_representative_tree (sid);
+  gcc_assert (m_region_model);
+  return m_region_model->get_representative_tree (sval);
 }
 
-/* Attempt to merge this state with OTHER, both using EXT_STATE.
+/* Attempt to merge this state with OTHER, both at POINT.
    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,
+				 const program_point &point,
 				 program_state *out) const
 {
   gcc_assert (out);
+  gcc_assert (m_region_model);
 
-  /* 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.  */
+  /* Early reject if there are sm-differences between the states.  */
+  int i;
+  sm_state_map *smap;
+  FOR_EACH_VEC_ELT (out->m_checker_states, i, smap)
+    if (*m_checker_states[i] != *other.m_checker_states[i])
+      return false;
 
   /* 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))
+					  point,
+					  out->m_region_model))
     return false;
 
-  /* Copy m_checker_states to result, remapping svalue_ids using
-     sid_mapping.  */
-  int i;
-  sm_state_map *smap;
+  /* Copy m_checker_states to OUT.  */
   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;
-	}
+      delete smap;
+      out->m_checker_states[i] = m_checker_states[i]->clone ();
     }
 
-  impl_region_model_context ctxt (out, NULL, ext_state);
-  out->m_region_model->canonicalize (&ctxt);
+  out->m_region_model->canonicalize ();
 
   return true;
 }
@@ -1079,212 +940,107 @@ program_state::validate (const extrinsic_state &ext_state) const
   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)
+static void
+log_set_of_svalues (logger *logger, const char *name,
+		     const svalue_set &set)
 {
-  if (m_new_sid.as_int () >= first_unused_sid.as_int ())
+  logger->log (name);
+  logger->inc_indent ();
+  for (svalue_set::iterator iter = set.begin ();
+       iter != set.end (); ++iter)
     {
-      m_new_sid = svalue_id::null ();
-      return 1;
+      logger->start_log_line ();
+      pretty_printer *pp = logger->get_printer ();
+      const svalue *sval = (*iter);
+      pp_pointer (pp, sval);
+      pp_string (pp, ": ");
+      sval->dump_to_pp (pp, false);
+      logger->end_log_line ();
     }
-
-  return 0;
-}
-
-/* Assert that this object is sane.  */
-
-void
-state_change::sm_change::validate (const program_state &new_state,
-				   const extrinsic_state &ext_state) const
-{
-  gcc_assert ((unsigned)m_sm_idx < ext_state.get_num_checkers ());
-  const state_machine &sm = ext_state.get_sm (m_sm_idx);
-  sm.validate (m_old_state);
-  sm.validate (m_new_state);
-  m_new_sid.validate (*new_state.m_region_model);
-}
-
-/* state_change's ctor.  */
-
-state_change::state_change ()
-{
+  logger->dec_indent ();
 }
 
-/* state_change's copy ctor.  */
+/* Compare the sets of svalues reachable from each of SRC_STATE and DEST_STATE.
+   For all svalues that are reachable in SRC_STATE and are not live in
+   DEST_STATE (whether explicitly reachable in DEST_STATE, or implicitly live
+   based on the former set), call CTXT->on_svalue_leak for them.
 
-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);
-}
+   Call on_liveness_change on both the CTXT and on the DEST_STATE's
+   constraint_manager, purging dead svalues from sm-state and from
+   constraints, respectively.
 
-/* Record a state-machine state change.  */
+   This function should be called at each fine-grained state change, not
+   just at exploded edges.  */
 
 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
+program_state::detect_leaks (const program_state &src_state,
+			     const program_state &dest_state,
+			     const svalue *extra_sval,
+			     const extrinsic_state &ext_state,
+			     region_model_context *ctxt)
 {
-  unsigned i;
-  sm_change *change;
-  FOR_EACH_VEC_ELT (m_sm_changes, i, change)
+  logger *logger = ext_state.get_logger ();
+  LOG_SCOPE (logger);
+  if (logger)
     {
-      if (sid == change->m_new_sid)
-	return true;
+      pretty_printer *pp = logger->get_printer ();
+      logger->start_log_line ();
+      pp_string (pp, "src_state: ");
+      src_state.dump_to_pp (ext_state, true, false, pp);
+      logger->end_log_line ();
+      logger->start_log_line ();
+      pp_string (pp, "dest_state: ");
+      dest_state.dump_to_pp (ext_state, true, false, pp);
+      logger->end_log_line ();
+      if (extra_sval)
+	{
+	  logger->start_log_line ();
+	  pp_string (pp, "extra_sval: ");
+	  extra_sval->dump_to_pp (pp, true);
+	  logger->end_log_line ();
+	}
     }
-  return false;
-}
 
-/* Dump this state_change to PP.  */
+  /* Get svalues reachable from each of src_state and dst_state.  */
+  svalue_set src_svalues;
+  svalue_set dest_svalues;
+  src_state.m_region_model->get_reachable_svalues (&src_svalues, NULL);
+  dest_state.m_region_model->get_reachable_svalues (&dest_svalues, extra_sval);
 
-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 (logger)
     {
-      if (i > 0)
-	pp_string (pp, ", ");
-      change->dump (pp, ext_state);
+      log_set_of_svalues (logger, "src_state reachable svalues:", src_svalues);
+      log_set_of_svalues (logger, "dest_state reachable svalues:",
+			  dest_svalues);
     }
-}
-
-/* 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;
-}
+  for (svalue_set::iterator iter = src_svalues.begin ();
+       iter != src_svalues.end (); ++iter)
+    {
+      const svalue *sval = (*iter);
+      /* For each sval reachable from SRC_STATE, determine if it is
+	 live in DEST_STATE: either explicitly reachable, or implicitly
+	 live based on the set of explicitly reachable svalues.
+	 Call CTXT->on_svalue_leak on those that have ceased to be live.  */
+      if (!sval->live_p (dest_svalues, dest_state.m_region_model))
+	ctxt->on_svalue_leak (sval);
+    }
 
-/* Assert that this object is sane.  */
+  /* Purge dead svals from sm-state.  */
+  ctxt->on_liveness_change (dest_svalues, dest_state.m_region_model);
 
-void
-state_change::validate (const program_state &new_state,
-			const extrinsic_state &ext_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, ext_state);
+  /* Purge dead svals from constraints.  */
+  dest_state.m_region_model->get_constraints ()->on_liveness_change
+    (dest_svalues, dest_state.m_region_model);
 }
 
 #if CHECKING_P
 
 namespace selftest {
 
-/* Implementation detail of ASSERT_DUMP_EQ.  */
-
-static void
-assert_dump_eq (const location &loc,
-		const program_state &state,
-		const extrinsic_state &ext_state,
-		bool summarize,
-		const char *expected)
-{
-  auto_fix_quotes sentinel;
-  pretty_printer pp;
-  pp_format_decoder (&pp) = default_tree_printer;
-  state.dump_to_pp (ext_state, summarize, &pp);
-  ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected);
-}
-
-/* Assert that STATE.dump_to_pp (SUMMARIZE) is EXPECTED.  */
-
-#define ASSERT_DUMP_EQ(STATE, EXT_STATE, SUMMARIZE, EXPECTED)		\
-  SELFTEST_BEGIN_STMT							\
-  assert_dump_eq ((SELFTEST_LOCATION), (STATE), (EXT_STATE), (SUMMARIZE), \
-		  (EXPECTED));						\
-  SELFTEST_END_STMT
-
 /* Tests for sm_state_map.  */
 
 static void
@@ -1294,134 +1050,119 @@ test_sm_state_map ()
   tree y = build_global_decl ("y", integer_type_node);
   tree z = build_global_decl ("z", integer_type_node);
 
+  state_machine *sm = make_malloc_state_machine (NULL);
+  auto_delete_vec <state_machine> checkers;
+  checkers.safe_push (sm);
+  extrinsic_state ext_state (checkers);
+
   /* 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);
+    region_model_manager mgr;
+    region_model model (&mgr);
+    const svalue *x_sval = model.get_rvalue (x, NULL);
+    const svalue *y_sval = model.get_rvalue (y, NULL);
+    const svalue *z_sval = model.get_rvalue (z, NULL);
 
-    sm_state_map map;
+    sm_state_map map (*sm, 0);
     ASSERT_TRUE (map.is_empty_p ());
-    ASSERT_EQ (map.get_state (sid_x), 0);
+    ASSERT_EQ (map.get_state (x_sval, ext_state), 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);
+    map.impl_set_state (x_sval, 42, z_sval, ext_state);
+    ASSERT_EQ (map.get_state (x_sval, ext_state), 42);
+    ASSERT_EQ (map.get_origin (x_sval, ext_state), z_sval);
+    ASSERT_EQ (map.get_state (y_sval, ext_state), 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 (y_sval, 0, z_sval, ext_state);
+    ASSERT_EQ (map.get_state (y_sval, ext_state), 0);
 
-    map.impl_set_state (sid_x, 0, sid_z);
-    ASSERT_EQ (map.get_state (sid_x), 0);
+    map.impl_set_state (x_sval, 0, z_sval, ext_state);
+    ASSERT_EQ (map.get_state (x_sval, ext_state), 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);
+    region_model_manager mgr;
+    region_model model (&mgr);
+    const svalue *x_sval = model.get_rvalue (x, NULL);
+    const svalue *y_sval = model.get_rvalue (y, NULL);
+    const svalue *z_sval = model.get_rvalue (z, NULL);
 
-    sm_state_map map;
+    sm_state_map map (*sm, 0);
     ASSERT_TRUE (map.is_empty_p ());
-    ASSERT_EQ (map.get_state (sid_x), 0);
-    ASSERT_EQ (map.get_state (sid_y), 0);
+    ASSERT_EQ (map.get_state (x_sval, ext_state), 0);
+    ASSERT_EQ (map.get_state (y_sval, ext_state), 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);
+    map.set_state (&model, x_sval, 5, z_sval, ext_state);
+    ASSERT_EQ (map.get_state (x_sval, ext_state), 5);
+    ASSERT_EQ (map.get_state (y_sval, ext_state), 5);
+    ASSERT_EQ (map.get_origin (x_sval, ext_state), z_sval);
+    ASSERT_EQ (map.get_origin (y_sval, ext_state), z_sval);
   }
 
   /* 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);
+    region_model_manager mgr;
+    region_model model (&mgr);
+    const svalue *y_sval = model.get_rvalue (y, NULL);
+    const svalue *z_sval = model.get_rvalue (z, NULL);
 
-    sm_state_map map0;
-    sm_state_map map1;
-    sm_state_map map2;
+    sm_state_map map0 (*sm, 0);
+    sm_state_map map1 (*sm, 0);
+    sm_state_map map2 (*sm, 0);
 
     ASSERT_EQ (map0.hash (), map1.hash ());
     ASSERT_EQ (map0, map1);
 
-    map1.impl_set_state (sid_y, 5, sid_z);
+    map1.impl_set_state (y_sval, 5, z_sval, ext_state);
     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);
+    map2.impl_set_state (y_sval, 5, z_sval, ext_state);
     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;
+    sm_state_map map0 (*sm, 0);
+    sm_state_map map1 (*sm, 0);
+    sm_state_map map2 (*sm, 0);
 
     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 ());
+    region_model_manager mgr;
+    region_model model (&mgr);
+    const svalue *x_sval = model.get_rvalue (x, NULL);
+    const svalue *y_sval = model.get_rvalue (y, NULL);
+    const svalue *z_sval = model.get_rvalue (z, 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 ());
+    map1.impl_set_state (x_sval, 2, NULL, ext_state);
+    map1.impl_set_state (y_sval, 3, NULL, ext_state);
+    map1.impl_set_state (z_sval, 2, NULL, ext_state);
+
+    map2.impl_set_state (z_sval, 2, NULL, ext_state);
+    map2.impl_set_state (y_sval, 3, NULL, ext_state);
+    map2.impl_set_state (x_sval, 2, NULL, ext_state);
 
     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_state::dump_to_pp works as expected.  */
+/* Check program_state works as expected.  */
 
 static void
-test_program_state_dumping ()
+test_program_state_1 ()
 {
   /* Create a program_state for a global ptr "p" that has
      malloc sm-state, pointing to a region on the heap.  */
@@ -1432,83 +1173,44 @@ test_program_state_dumping ()
     = sm->get_state_by_name ("unchecked");
   auto_delete_vec <state_machine> checkers;
   checkers.safe_push (sm);
-  extrinsic_state ext_state (checkers);
 
+  engine eng;
+  extrinsic_state ext_state (checkers, NULL, &eng);
+  region_model_manager *mgr = eng.get_model_manager ();
   program_state s (ext_state);
   region_model *model = s.m_region_model;
-  region_id new_rid = model->add_new_malloc_region ();
-  svalue_id ptr_sid
-      = model->get_or_create_ptr_svalue (ptr_type_node, new_rid);
+  const svalue *size_in_bytes
+    = mgr->get_or_create_unknown_svalue (integer_type_node);
+  const region *new_reg = model->create_region_for_heap_alloc (size_in_bytes);
+  const svalue *ptr_sval = mgr->get_ptr_svalue (ptr_type_node, new_reg);
   model->set_value (model->get_lvalue (p, NULL),
-		    ptr_sid, NULL);
+		    ptr_sval, NULL);
   sm_state_map *smap = s.m_checker_states[0];
 
-  smap->impl_set_state (ptr_sid, UNCHECKED_STATE, svalue_id::null ());
-  ASSERT_EQ (smap->get_state (ptr_sid), UNCHECKED_STATE);
-
-  ASSERT_DUMP_EQ
-    (s, ext_state, false,
-     "rmodel: r0: {kind: `root', parent: null, sval: null}\n"
-     "|-heap: r1: {kind: `heap', parent: r0, sval: null}\n"
-     "|  `-r2: {kind: `symbolic', parent: r1, sval: null, possibly_null: true}\n"
-     "`-globals: r3: {kind: `globals', parent: r0, sval: null, map: {`p': r4}}\n"
-     "  `-`p': r4: {kind: `primitive', parent: r3, sval: sv0, type: `void *'}\n"
-     "    |: sval: sv0: {type: `void *', &r2}\n"
-     "    |: type: `void *'\n"
-     "svalues:\n"
-     "  sv0: {type: `void *', &r2}\n"
-     "constraint manager:\n"
-     "  equiv classes:\n"
-     "  constraints:\n"
-     "malloc: {sv0: unchecked (`p')}\n");
-
-  ASSERT_DUMP_EQ (s, ext_state, true,
-		  "rmodel: p: &r2 malloc: {sv0: unchecked (`p')}");
+  smap->impl_set_state (ptr_sval, UNCHECKED_STATE, NULL, ext_state);
+  ASSERT_EQ (smap->get_state (ptr_sval, ext_state), UNCHECKED_STATE);
 }
 
-/* Verify that program_state::dump_to_pp works for string literals.  */
+/* Check that program_state works for string literals.  */
 
 static void
-test_program_state_dumping_2 ()
+test_program_state_2 ()
 {
-    /* Create a program_state for a global ptr "p" that points to
-       a string constant.  */
+  /* Create a program_state for a global ptr "p" that points to
+     a string constant.  */
   tree p = build_global_decl ("p", ptr_type_node);
 
   tree string_cst_ptr = build_string_literal (4, "foo");
 
   auto_delete_vec <state_machine> checkers;
-  extrinsic_state ext_state (checkers);
+  engine eng;
+  extrinsic_state ext_state (checkers, NULL, &eng);
 
   program_state s (ext_state);
   region_model *model = s.m_region_model;
-  region_id p_rid = model->get_lvalue (p, NULL);
-  svalue_id str_sid = model->get_rvalue (string_cst_ptr, NULL);
-  model->set_value (p_rid, str_sid, NULL);
-
-  ASSERT_DUMP_EQ
-    (s, ext_state, false,
-     "rmodel: r0: {kind: `root', parent: null, sval: null}\n"
-     "|-globals: r1: {kind: `globals', parent: r0, sval: null, map: {`p': r2}}\n"
-     "|  `-`p': r2: {kind: `primitive', parent: r1, sval: sv3, type: `void *'}\n"
-     "|    |: sval: sv3: {type: `void *', &r4}\n"
-     "|    |: type: `void *'\n"
-     "`-r3: {kind: `array', parent: r0, sval: sv0, type: `const char[4]', array: {[0]: r4}}\n"
-     "  |: sval: sv0: {type: `const char[4]', `\"foo\"'}\n"
-     "  |: type: `const char[4]'\n"
-     "  `-[0]: r4: {kind: `primitive', parent: r3, sval: null, type: `const char'}\n"
-     "    |: type: `const char'\n"
-     "svalues:\n"
-     "  sv0: {type: `const char[4]', `\"foo\"'}\n"
-     "  sv1: {type: `int', `0'}\n"
-     "  sv2: {type: `const char *', &r4}\n"
-     "  sv3: {type: `void *', &r4}\n"
-     "constraint manager:\n"
-     "  equiv classes:\n"
-     "  constraints:\n");
-
-  ASSERT_DUMP_EQ (s, ext_state, true,
-		  "rmodel: p: &\"foo\"[0]");
+  const region *p_reg = model->get_lvalue (p, NULL);
+  const svalue *str_sval = model->get_rvalue (string_cst_ptr, NULL);
+  model->set_value (p_reg, str_sval, NULL);
 }
 
 /* Verify that program_states with identical sm-state can be merged,
@@ -1521,28 +1223,33 @@ test_program_state_merging ()
      malloc sm-state, pointing to a region on the heap.  */
   tree p = build_global_decl ("p", ptr_type_node);
 
+  program_point point (program_point::origin ());
   auto_delete_vec <state_machine> checkers;
   checkers.safe_push (make_malloc_state_machine (NULL));
-  extrinsic_state ext_state (checkers);
+  engine eng;
+  extrinsic_state ext_state (checkers, NULL, &eng);
+  region_model_manager *mgr = eng.get_model_manager ();
 
   program_state s0 (ext_state);
-  impl_region_model_context ctxt (&s0, NULL, ext_state);
+  impl_region_model_context ctxt (&s0, 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);
+  const svalue *size_in_bytes
+    = mgr->get_or_create_unknown_svalue (integer_type_node);
+  const region *new_reg = model0->create_region_for_heap_alloc (size_in_bytes);
+  const svalue *ptr_sval = mgr->get_ptr_svalue (ptr_type_node, new_reg);
   model0->set_value (model0->get_lvalue (p, &ctxt),
-		     ptr_sid, &ctxt);
+		     ptr_sval, &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);
+  smap->impl_set_state (ptr_sval, TEST_STATE, NULL, ext_state);
+  ASSERT_EQ (smap->get_state (ptr_sval, ext_state), TEST_STATE);
 
-  model0->canonicalize (&ctxt);
+  model0->canonicalize ();
 
   /* Verify that canonicalization preserves sm-state.  */
-  ASSERT_EQ (smap->get_state (model0->get_rvalue (p, NULL)), TEST_STATE);
+  ASSERT_EQ (smap->get_state (model0->get_rvalue (p, NULL), ext_state),
+	     TEST_STATE);
 
   /* Make a copy of the program_state.  */
   program_state s1 (s0);
@@ -1552,22 +1259,23 @@ test_program_state_merging ()
      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));
+  ASSERT_TRUE (s0.can_merge_with_p (s1, point, &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)),
+  ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, NULL),
+				     ext_state),
 	     TEST_STATE);
 
   /* Try canonicalizing.  */
-  impl_region_model_context merged_ctxt (&merged, NULL, ext_state);
-  merged.m_region_model->canonicalize (&merged_ctxt);
+  merged.m_region_model->canonicalize ();
   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)),
+  ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, NULL),
+				     ext_state),
 	     TEST_STATE);
 
   /* After canonicalization, we ought to have equality with the inputs.  */
@@ -1580,6 +1288,7 @@ test_program_state_merging ()
 static void
 test_program_state_merging_2 ()
 {
+  program_point point (program_point::origin ());
   auto_delete_vec <state_machine> checkers;
   checkers.safe_push (make_signal_state_machine (NULL));
   extrinsic_state ext_state (checkers);
@@ -1604,7 +1313,7 @@ test_program_state_merging_2 ()
 
   /* They ought to not be mergeable.  */
   program_state merged (ext_state);
-  ASSERT_FALSE (s0.can_merge_with_p (s1, ext_state, &merged));
+  ASSERT_FALSE (s0.can_merge_with_p (s1, point, &merged));
 }
 
 /* Run all of the selftests within this file.  */
@@ -1613,8 +1322,8 @@ void
 analyzer_program_state_cc_tests ()
 {
   test_sm_state_map ();
-  test_program_state_dumping ();
-  test_program_state_dumping_2 ();
+  test_program_state_1 ();
+  test_program_state_2 ();
   test_program_state_merging ();
   test_program_state_merging_2 ();
 }