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, 106 insertions, 30 deletions

diff --git a/gcc/analyzer/sm-malloc.cc b/gcc/analyzer/sm-malloc.cc
index 74c6fee..bf5e3c3 100644
--- a/gcc/analyzer/sm-malloc.cc
+++ b/gcc/analyzer/sm-malloc.cc
@@ -45,6 +45,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "stringpool.h"
 #include "attribs.h"
 #include "analyzer/function-set.h"
+#include "analyzer/program-state.h"
 
 #if ENABLE_ANALYZER
 
@@ -387,6 +388,12 @@ public:
 
   static bool unaffected_by_call_p (tree fndecl);
 
+  void on_realloc_with_move (region_model *model,
+			     sm_state_map *smap,
+			     const svalue *old_ptr_sval,
+			     const svalue *new_ptr_sval,
+			     const extrinsic_state &ext_state) const;
+
   standard_deallocator_set m_free;
   standard_deallocator_set m_scalar_delete;
   standard_deallocator_set m_vector_delete;
@@ -1836,54 +1843,65 @@ malloc_state_machine::on_deallocator_call (sm_context *sm_ctxt,
     }
 }
 
-/* Implementation of realloc(3):
-
-     void *realloc(void *ptr, size_t size);
-
-   realloc(3) is awkward.
+/* Handle a call to "realloc".
+   Check for free of non-heap or mismatching allocators,
+   transitioning to the "stop" state for such cases.
 
-   We currently don't have a way to express multiple possible outcomes
-   from a function call, "bifurcating" the state such as:
-   - success: non-NULL is returned
-   - failure: NULL is returned, existing buffer is not freed.
-   or even an N-way state split e.g.:
-   - buffer grew successfully in-place
-   - buffer was successfully moved to a larger allocation
-   - buffer was successfully contracted
-   - realloc failed, returning NULL, without freeing existing buffer.
-   (PR analyzer/99260 tracks this)
-
-   Given that we can currently only express one outcome, eliminate
-   false positives by dropping state from the buffer.  */
+   Otherwise, region_model::impl_call_realloc will later
+   get called (which will handle other sm-state transitions
+   when the state is bifurcated).  */
 
 void
 malloc_state_machine::on_realloc_call (sm_context *sm_ctxt,
-				       const supernode *node ATTRIBUTE_UNUSED,
+				       const supernode *node,
 				       const gcall *call) const
 {
-  tree ptr = gimple_call_arg (call, 0);
+  const unsigned argno = 0;
+  const deallocator *d = &m_realloc;
+
+  tree arg = gimple_call_arg (call, argno);
 
-  state_t state = sm_ctxt->get_state (call, ptr);
+  state_t state = sm_ctxt->get_state (call, arg);
 
-  /* Detect mismatches.  */
   if (unchecked_p (state) || nonnull_p (state))
     {
       const allocation_state *astate = as_a_allocation_state (state);
       gcc_assert (astate->m_deallocators);
-      if (astate->m_deallocators != &m_free)
+      if (!astate->m_deallocators->contains_p (&m_free.m_deallocator))
 	{
 	  /* Wrong allocator.  */
-	  tree diag_ptr = sm_ctxt->get_diagnostic_tree (ptr);
+	  tree diag_arg = sm_ctxt->get_diagnostic_tree (arg);
 	  pending_diagnostic *pd
-	    = new mismatching_deallocation (*this, diag_ptr,
+	    = new mismatching_deallocation (*this, diag_arg,
 					    astate->m_deallocators,
-					    &m_realloc);
-	  sm_ctxt->warn (node, call, ptr, pd);
+					    d);
+	  sm_ctxt->warn (node, call, arg, pd);
+	  sm_ctxt->set_next_state (call, arg, m_stop);
+	  if (path_context *path_ctxt = sm_ctxt->get_path_context ())
+	    path_ctxt->terminate_path ();
 	}
     }
-
-  /* Transition ptr to "stop" state.  */
-  sm_ctxt->set_next_state (call, ptr, m_stop);
+  else if (state == m_free.m_deallocator.m_freed)
+    {
+      /* freed -> stop, with warning.  */
+      tree diag_arg = sm_ctxt->get_diagnostic_tree (arg);
+      sm_ctxt->warn (node, call, arg,
+		     new double_free (*this, diag_arg, "free"));
+      sm_ctxt->set_next_state (call, arg, m_stop);
+      if (path_context *path_ctxt = sm_ctxt->get_path_context ())
+	path_ctxt->terminate_path ();
+    }
+  else if (state == m_non_heap)
+    {
+      /* non-heap -> stop, with warning.  */
+      tree diag_arg = sm_ctxt->get_diagnostic_tree (arg);
+      sm_ctxt->warn (node, call, arg,
+		     new free_of_non_heap (*this, diag_arg,
+					   d->m_name));
+      sm_ctxt->set_next_state (call, arg, m_stop);
+      if (path_context *path_ctxt = sm_ctxt->get_path_context ())
+	path_ctxt->terminate_path ();
+    }
 }
 
 /* Implementation of state_machine::on_phi vfunc for malloc_state_machine.  */
@@ -2015,6 +2033,30 @@ malloc_state_machine::on_zero_assignment (sm_context *sm_ctxt,
     sm_ctxt->set_next_state (stmt, lhs, m_null);
 }
 
+/* Special-case hook for handling realloc, for the "success with move to
+   a new buffer" case, marking OLD_PTR_SVAL as freed and NEW_PTR_SVAL as
+   non-null.
+
+   This is similar to on_deallocator_call and on_allocator_call,
+   but the checks happen in on_realloc_call, and by splitting the states.  */
+
+void
+malloc_state_machine::
+on_realloc_with_move (region_model *model,
+		      sm_state_map *smap,
+		      const svalue *old_ptr_sval,
+		      const svalue *new_ptr_sval,
+		      const extrinsic_state &ext_state) const
+{
+  smap->set_state (model, old_ptr_sval,
+		   m_free.m_deallocator.m_freed,
+		   NULL, ext_state);
+
+  smap->set_state (model, new_ptr_sval,
+		   m_free.m_nonnull,
+		   NULL, ext_state);
+}
+
 } // anonymous namespace
 
 /* Internal interface to this file. */
@@ -2025,6 +2067,40 @@ make_malloc_state_machine (logger *logger)
   return new malloc_state_machine (logger);
 }
 
+/* Specialcase hook for handling realloc, for use by
+   region_model::impl_call_realloc::success_with_move::update_model.  */
+
+void
+region_model::on_realloc_with_move (const call_details &cd,
+				    const svalue *old_ptr_sval,
+				    const svalue *new_ptr_sval)
+{
+  region_model_context *ctxt = cd.get_ctxt ();
+  if (!ctxt)
+    return;
+  const extrinsic_state *ext_state = ctxt->get_ext_state ();
+  if (!ext_state)
+    return;
+
+  sm_state_map *smap;
+  const state_machine *sm;
+  unsigned sm_idx;
+  if (!ctxt->get_malloc_map (&smap, &sm, &sm_idx))
+    return;
+
+  gcc_assert (smap);
+  gcc_assert (sm);
+
+  const malloc_state_machine &malloc_sm
+    = (const malloc_state_machine &)*sm;
+
+  malloc_sm.on_realloc_with_move (this,
+				  smap,
+				  old_ptr_sval,
+				  new_ptr_sval,
+				  *ext_state);
+}
+
 } // namespace ana
 
 #endif /* #if ENABLE_ANALYZER */