analyzer: support "bifurcation"; reimplement realloc [PR99260]

Most of the state-management code in the analyzer involves
modifying state objects in-place, which implies a single outcome.
(I originally implemented in-place modification because I wanted
to avoid having to create copies of state objects, and it's now
very difficult to change this aspect of the analyzer's design)

However, there are various special-cases such as "realloc" for which
it's best to split the state into multiple outcomes.

This patch adds a mechanism for "bifurcating" the analysis in places
where there isn't a split in the CFG, and uses it to implement realloc,
in this case treating it as having 3 possible outcomes:
- failure, returning NULL
- success, growing the buffer in-place without moving it
- success, allocating a new buffer, copying the content of the old
  buffer to it, and freeing the old buffer.

gcc/ChangeLog:
	PR analyzer/99260
	* Makefile.in (ANALYZER_OBJS): Add analyzer/call-info.o.

gcc/analyzer/ChangeLog:
	PR analyzer/99260
	* analyzer.h (class custom_edge_info): New class, adapted from
	exploded_edge::custom_info_t.  Make member functions const.
	Make update_model return bool, converting edge param from
	reference to a pointer, and adding a ctxt param.
	(class path_context): New class.
	* call-info.cc: New file.
	* call-info.h: New file.
	* engine.cc: Include "analyzer/call-info.h" and <memory>.
	(impl_region_model_context::impl_region_model_context): Update for
	new m_path_ctxt field.
	(impl_region_model_context::bifurcate): New.
	(impl_region_model_context::terminate_path): New.
	(impl_region_model_context::get_malloc_map): New.
	(impl_sm_context::impl_sm_context): Update for new m_path_ctxt
	field.
	(impl_sm_context::get_fndecl_for_call): Likewise.
	(impl_sm_context::set_next_state): Likewise.
	(impl_sm_context::warn): Likewise.
	(impl_sm_context::is_zero_assignment): Likewise.
	(impl_sm_context::get_path_context): New.
	(impl_sm_context::m_path_ctxt): New.
	(impl_region_model_context::on_condition): Update for new
	path_ctxt param.  Handle m_enode_for_diag being NULL.
	(impl_region_model_context::on_phi): Update for new path_ctxt
	param.
	(exploded_node::on_stmt): Add path_ctxt param, updating ctor calls
	to use it as necessary.  Use it to bail out after sm-handling,
	if needed.
	(exploded_node::detect_leaks): Update for new path_ctxt param.
	(dynamic_call_info_t::update_model): Update for conversion of
	exploded_edge::custom_info_t to custom_edge_info.
	(dynamic_call_info_t::add_events_to_path): Likewise.
	(rewind_info_t::update_model): Likewise.
	(rewind_info_t::add_events_to_path): Likewise.
	(exploded_edge::exploded_edge): Likewise.
	(exploded_graph::add_edge): Likewise.
	(exploded_graph::maybe_process_run_of_before_supernode_enodes):
	Update for new path_ctxt param.
	(class impl_path_context): New.
	(exploded_graph::process_node): Update for new path_ctxt param.
	Create an impl_path_context and pass it to exploded_node::on_stmt.
	Use it to terminate iterating stmts if terminate_path is called
	on it.  After processing a run of stmts, query path_ctxt to
	potentially terminate the analysis path, and/or to "bifurcate" the
	analysis into multiple additional paths.
	(feasibility_state::maybe_update_for_edge): Update for new
	update_model ctxt param.
	* exploded-graph.h
	(impl_region_model_context::impl_region_model_context): Add
	path_ctxt param.
	(impl_region_model_context::bifurcate): New.
	(impl_region_model_context::terminate_path): New
	(impl_region_model_context::get_ext_state): New.
	(impl_region_model_context::get_malloc_map): New.
	(impl_region_model_context::m_path_ctxt): New field.
	(exploded_node::on_stmt): Add path_ctxt param.
	(class exploded_edge::custom_info_t): Move to analyzer.h, renaming
	to custom_edge_info, and making the changes as noted in analyzer.h
	above.
	(exploded_edge::exploded_edge): Update for these changes to
	exploded_edge::custom_info_t.
	(exploded_edge::m_custom_info): Likewise.
	(class dynamic_call_info_t): Likewise.
	(class rewind_info_t): Likewise.
	(exploded_graph::add_edge): Likewise.
	* program-state.cc (program_state::on_edge): Update for new
	path_ctxt param.
	(program_state::push_call): Likewise.
	(program_state::returning_call): Likewise.
	(program_state::prune_for_point): Likewise.
	* region-model-impl-calls.cc: Include "analyzer/call-info.h".
	(call_details::get_fndecl_for_call): New.
	(region_model::impl_call_realloc): Reimplement.
	* region-model.cc (region_model::on_call_pre): Move call to
	impl_call_realloc to...
	(region_model::on_call_post): ...here.  Consolidate creation
	of call_details instance.
	(noop_region_model_context::bifurcate): New.
	(noop_region_model_context::terminate_path): New.
	* region-model.h (call_details::get_call_stmt): New.
	(call_details::get_fndecl_for_call): New.
	(region_model::on_realloc_with_move): New.
	(region_model_context::bifurcate): New.
	(region_model_context::terminate_path): New.
	(region_model_context::get_ext_state): New.
	(region_model_context::get_malloc_map): New.
	(noop_region_model_context::bifurcate): New.
	(noop_region_model_context::terminate_path): New.
	(noop_region_model_context::get_ext_state): New.
	(noop_region_model_context::get_malloc_map): New.
	* sm-malloc.cc: Include "analyzer/program-state.h".
	(malloc_state_machine::on_realloc_call): Reimplement.
	(malloc_state_machine::on_realloc_with_move): New.
	(region_model::on_realloc_with_move): New.
	* sm-signal.cc (class signal_delivery_edge_info_t): Update for
	conversion from exploded_edge::custom_info_t to custom_edge_info.
	* sm.h (sm_context::get_path_context): New.
	* svalue.cc (svalue::maybe_get_constant): Call
	unwrap_any_unmergeable.

gcc/testsuite/ChangeLog:
	PR analyzer/99260
	* gcc.dg/analyzer/capacity-2.c: Update for changes to realloc
	analysis.
	* gcc.dg/analyzer/pr99193-1.c: Likewise.
	* gcc.dg/analyzer/pr99193-3.c: Likewise.
	* gcc.dg/analyzer/realloc-1.c: Likewise.  Add test coverage for
	realloc of non-heap pointer, realloc from mismatching allocator,
	and realloc on a freed pointer.
	* gcc.dg/analyzer/realloc-2.c: New test.

1 files changed, 4 insertions, 2 deletions

diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc
index ea53c61..c1ff0d8 100644
--- a/gcc/analyzer/program-state.cc
+++ b/gcc/analyzer/program-state.cc
@@ -1013,7 +1013,7 @@ program_state::on_edge (exploded_graph &eg,
   impl_region_model_context ctxt (eg, enode,
 				  &enode->get_state (),
 				  this,
-				  uncertainty,
+				  uncertainty, NULL,
 				  last_stmt);
   if (!m_region_model->maybe_update_for_edge (*succ,
 					      last_stmt,
@@ -1052,6 +1052,7 @@ program_state::push_call (exploded_graph &eg,
                                   &enode->get_state (),
                                   this,
                                   uncertainty,
+				  NULL,
                                   last_stmt);
   m_region_model->update_for_gcall (call_stmt, &ctxt);
 }
@@ -1074,6 +1075,7 @@ program_state::returning_call (exploded_graph &eg,
                                   &enode->get_state (),
                                   this,
                                   uncertainty,
+				  NULL,
                                   last_stmt);
   m_region_model->update_for_return_gcall (call_stmt, &ctxt);
 }
@@ -1152,7 +1154,7 @@ program_state::prune_for_point (exploded_graph &eg,
 	  impl_region_model_context ctxt (eg, enode_for_diag,
 					  this,
 					  &new_state,
-					  uncertainty,
+					  uncertainty, NULL,
 					  point.get_stmt ());
 	  detect_leaks (*this, new_state, NULL, eg.get_ext_state (), &ctxt);
 	}