analyzer: fix leak false +ves due to maybe-clobbered regions [PR99042,PR99774]

Prior to this patch, program_state::detect_leaks worked by finding all
live svalues in the old state and in the new state, and calling
on_svalue_leak for each svalue that has changed from being live to
not being live.

PR analyzer/99042 and PR analyzer/99774 both describe false leak
diagnostics from -fanalyzer (a false FILE * leak in git, and a false
malloc leak in qemu, respectively).

In both cases the root cause of the false leak diagnostic relates to
svalues no longer being explicitly bound in the store due to regions
being conservatively clobbered, due to an unknown function being
called, or due to a write through a pointer that could alias the
region, respectively.

We have a transition from an svalue being explicitly live to not
being explicitly live - but only because the store is being
conservative, clobbering the binding.  The leak detection is looking
for transitions from "definitely live" to "not definitely live",
when it should be looking for transitions from "definitely live"
to "definitely not live".

This patch introduces a new class to temporarily capture information
about svalues that were explicitly live, but for which a region bound
to them got clobbered for conservative reasons.  This new
"uncertainty_t" class is passed around to capture the data long enough
for use in program_state::detect_leaks, where it is used to only
complain about svalues that were definitely live and are now both
not definitely live *or* possibly-live i.e. definitely not-live.

The class also captures for which svalues we can't meaningfully track
sm-state anymore, and resets the svalues back to the "start" state.

Together, these changes fix the false leak reports.

gcc/analyzer/ChangeLog:
	PR analyzer/99042
	PR analyzer/99774
	* engine.cc
	(impl_region_model_context::impl_region_model_context): Add
	uncertainty param and use it to initialize m_uncertainty.
	(impl_region_model_context::get_uncertainty): New.
	(impl_sm_context::get_fndecl_for_call): Add NULL for new
	uncertainty param when constructing impl_region_model_context.
	(impl_sm_context::get_state): Likewise.
	(impl_sm_context::set_next_state): Likewise.
	(impl_sm_context::warn): Likewise.
	(exploded_node::on_stmt): Add uncertainty param
	and use it when constructing impl_region_model_context.
	(exploded_node::on_edge): Add uncertainty param and pass
	to on_edge call.
	(exploded_node::detect_leaks): Create uncertainty_t and pass to
	impl_region_model_context.
	(exploded_graph::get_or_create_node): Create uncertainty_t and
	pass to prune_for_point.
	(maybe_process_run_of_before_supernode_enodes): Create
	uncertainty_t and pass to impl_region_model_context.
	(exploded_graph::process_node): Create uncertainty_t instances and
	pass around as needed.
	* exploded-graph.h
	(impl_region_model_context::impl_region_model_context): Add
	uncertainty param.
	(impl_region_model_context::get_uncertainty): New decl.
	(impl_region_model_context::m_uncertainty): New field.
	(exploded_node::on_stmt): Add uncertainty param.
	(exploded_node::on_edge): Likewise.
	* program-state.cc (sm_state_map::on_liveness_change): Get
	uncertainty from context and use it to unset sm-state from
	svalues as appropriate.
	(program_state::on_edge): Add uncertainty param and use it when
	constructing impl_region_model_context.  Fix indentation.
	(program_state::prune_for_point): Add uncertainty param and use it
	when constructing impl_region_model_context.
	(program_state::detect_leaks): Get any uncertainty from ctxt and
	use it to get maybe-live svalues for dest_state, rather than
	definitely-live ones; use this when determining which svalues
	have leaked.
	(selftest::test_program_state_merging): Create uncertainty_t and
	pass to impl_region_model_context.
	* program-state.h (program_state::on_edge): Add uncertainty param.
	(program_state::prune_for_point): Likewise.
	* region-model-impl-calls.cc (call_details::get_uncertainty): New.
	(region_model::impl_call_memcpy): Pass uncertainty to
	mark_region_as_unknown call.
	(region_model::impl_call_memset): Likewise.
	(region_model::impl_call_strcpy): Likewise.
	* region-model-reachability.cc (reachable_regions::handle_sval):
	Also add sval to m_mutable_svals.
	* region-model.cc (region_model::on_assignment): Pass any
	uncertainty from ctxt to the store::set_value call.
	(region_model::handle_unrecognized_call): Get any uncertainty from
	ctxt and use it to record mutable svalues at the unknown call.
	(region_model::get_reachable_svalues): Add uncertainty param and
	use it to mark any maybe-bound svalues as being reachable.
	(region_model::set_value): Pass any uncertainty from ctxt to the
	store::set_value call.
	(region_model::mark_region_as_unknown): Add uncertainty param and
	pass it on to the store::mark_region_as_unknown call.
	(region_model::update_for_call_summary): Add uncertainty param and
	pass it on to the region_model::mark_region_as_unknown call.
	* region-model.h (call_details::get_uncertainty): New decl.
	(region_model::get_reachable_svalues): Add uncertainty param.
	(region_model::mark_region_as_unknown): Add uncertainty param.
	(region_model_context::get_uncertainty): New vfunc.
	(noop_region_model_context::get_uncertainty): New vfunc
	implementation.
	* store.cc (dump_svalue_set): New.
	(uncertainty_t::dump_to_pp): New.
	(uncertainty_t::dump): New.
	(binding_cluster::clobber_region): Pass NULL for uncertainty to
	remove_overlapping_bindings.
	(binding_cluster::mark_region_as_unknown): Add uncertainty param
	and pass it to remove_overlapping_bindings.
	(binding_cluster::remove_overlapping_bindings): Add uncertainty param.
	Use it to record any svalues that were in clobbered bindings.
	(store::set_value): Add uncertainty param.  Pass it to
	binding_cluster::mark_region_as_unknown when handling symbolic
	regions.
	(store::mark_region_as_unknown): Add uncertainty param and pass it
	to binding_cluster::mark_region_as_unknown.
	(store::remove_overlapping_bindings): Add uncertainty param and
	pass it to binding_cluster::remove_overlapping_bindings.
	* store.h (binding_cluster::mark_region_as_unknown): Add
	uncertainty param.
	(binding_cluster::remove_overlapping_bindings): Likewise.
	(store::set_value): Likewise.
	(store::mark_region_as_unknown): Likewise.

gcc/testsuite/ChangeLog:
	PR analyzer/99042
	PR analyzer/99774
	* gcc.dg/analyzer/pr99042.c: New test.
	* gcc.dg/analyzer/pr99774-1.c: New test.
	* gcc.dg/analyzer/pr99774-2.c: New test.

1 files changed, 48 insertions, 22 deletions

diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc
index 347cb29..f809462 100644
--- a/gcc/analyzer/program-state.cc
+++ b/gcc/analyzer/program-state.cc
@@ -516,6 +516,7 @@ sm_state_map::on_liveness_change (const svalue_set &live_svalues,
 				  impl_region_model_context *ctxt)
 {
   svalue_set svals_to_unset;
+  uncertainty_t *uncertainty = ctxt->get_uncertainty ();
 
   auto_vec<const svalue *> leaked_svals (m_map.elements ());
   for (map_t::iterator iter = m_map.begin ();
@@ -530,6 +531,9 @@ sm_state_map::on_liveness_change (const svalue_set &live_svalues,
 	  if (!m_sm.can_purge_p (e.m_state))
 	    leaked_svals.quick_push (iter_sval);
 	}
+      if (uncertainty)
+	if (uncertainty->unknown_sm_state_p (iter_sval))
+	  svals_to_unset.add (iter_sval);
     }
 
   leaked_svals.qsort (svalue::cmp_ptr_ptr);
@@ -960,7 +964,8 @@ program_state::get_current_function () const
 bool
 program_state::on_edge (exploded_graph &eg,
 			exploded_node *enode,
-			const superedge *succ)
+			const superedge *succ,
+			uncertainty_t *uncertainty)
 {
   /* Update state.  */
   const program_point &point = enode->get_point ();
@@ -978,6 +983,7 @@ program_state::on_edge (exploded_graph &eg,
   impl_region_model_context ctxt (eg, enode,
 				  &enode->get_state (),
 				  this,
+				  uncertainty,
 				  last_stmt);
   if (!m_region_model->maybe_update_for_edge (*succ,
 					      last_stmt,
@@ -992,8 +998,8 @@ program_state::on_edge (exploded_graph &eg,
     }
 
   program_state::detect_leaks (enode->get_state (), *this,
-				NULL, eg.get_ext_state (),
-				&ctxt);
+			       NULL, eg.get_ext_state (),
+			       &ctxt);
 
   return true;
 }
@@ -1007,7 +1013,8 @@ program_state::on_edge (exploded_graph &eg,
 program_state
 program_state::prune_for_point (exploded_graph &eg,
 				const program_point &point,
-				exploded_node *enode_for_diag) const
+				exploded_node *enode_for_diag,
+				uncertainty_t *uncertainty) const
 {
   logger * const logger = eg.get_logger ();
   LOG_SCOPE (logger);
@@ -1071,6 +1078,7 @@ program_state::prune_for_point (exploded_graph &eg,
 	  impl_region_model_context ctxt (eg, enode_for_diag,
 					  this,
 					  &new_state,
+					  uncertainty,
 					  point.get_stmt ());
 	  detect_leaks (*this, new_state, NULL, eg.get_ext_state (), &ctxt);
 	}
@@ -1189,6 +1197,7 @@ program_state::detect_leaks (const program_state &src_state,
 {
   logger *logger = ext_state.get_logger ();
   LOG_SCOPE (logger);
+  const uncertainty_t *uncertainty = ctxt->get_uncertainty ();
   if (logger)
     {
       pretty_printer *pp = logger->get_printer ();
@@ -1207,31 +1216,46 @@ program_state::detect_leaks (const program_state &src_state,
 	  extra_sval->dump_to_pp (pp, true);
 	  logger->end_log_line ();
 	}
+      if (uncertainty)
+	{
+	  logger->start_log_line ();
+	  pp_string (pp, "uncertainty: ");
+	  uncertainty->dump_to_pp (pp, true);
+	  logger->end_log_line ();
+	}
     }
 
-  /* 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);
+  /* Get svalues reachable from each of src_state and dest_state.
+     Get svalues *known* to be reachable in src_state.
+     Pass in uncertainty for dest_state so that we additionally get svalues that
+     *might* still be reachable in dst_state.  */
+  svalue_set known_src_svalues;
+  src_state.m_region_model->get_reachable_svalues (&known_src_svalues,
+						   NULL, NULL);
+  svalue_set maybe_dest_svalues;
+  dest_state.m_region_model->get_reachable_svalues (&maybe_dest_svalues,
+						    extra_sval, uncertainty);
 
   if (logger)
     {
-      log_set_of_svalues (logger, "src_state reachable svalues:", src_svalues);
-      log_set_of_svalues (logger, "dest_state reachable svalues:",
-			  dest_svalues);
+      log_set_of_svalues (logger, "src_state known reachable svalues:",
+			  known_src_svalues);
+      log_set_of_svalues (logger, "dest_state maybe reachable svalues:",
+			  maybe_dest_svalues);
     }
 
-  auto_vec <const svalue *> dead_svals (src_svalues.elements ());
-  for (svalue_set::iterator iter = src_svalues.begin ();
-       iter != src_svalues.end (); ++iter)
+  auto_vec <const svalue *> dead_svals (known_src_svalues.elements ());
+  for (svalue_set::iterator iter = known_src_svalues.begin ();
+       iter != known_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.
-	 Record those that have ceased to be live.  */
-      if (!sval->live_p (&dest_svalues, dest_state.m_region_model))
+	 live in DEST_STATE: either explicitly reachable, implicitly
+	 live based on the set of explicitly reachable svalues,
+	 or possibly reachable as recorded in uncertainty.
+	 Record those that have ceased to be live i.e. were known
+	 to be live, and are now not known to be even possibly-live.  */
+      if (!sval->live_p (&maybe_dest_svalues, dest_state.m_region_model))
 	dead_svals.quick_push (sval);
     }
 
@@ -1244,11 +1268,12 @@ program_state::detect_leaks (const program_state &src_state,
     ctxt->on_svalue_leak (sval);
 
   /* Purge dead svals from sm-state.  */
-  ctxt->on_liveness_change (dest_svalues, dest_state.m_region_model);
+  ctxt->on_liveness_change (maybe_dest_svalues,
+			    dest_state.m_region_model);
 
   /* Purge dead svals from constraints.  */
   dest_state.m_region_model->get_constraints ()->on_liveness_change
-    (dest_svalues, dest_state.m_region_model);
+    (maybe_dest_svalues, dest_state.m_region_model);
 }
 
 #if CHECKING_P
@@ -1456,7 +1481,8 @@ test_program_state_merging ()
   region_model_manager *mgr = eng.get_model_manager ();
 
   program_state s0 (ext_state);
-  impl_region_model_context ctxt (&s0, ext_state);
+  uncertainty_t uncertainty;
+  impl_region_model_context ctxt (&s0, ext_state, &uncertainty);
 
   region_model *model0 = s0.m_region_model;
   const svalue *size_in_bytes