analyzer: extend state-purging to locals [PR104943]

The existing analyzer code attempts to purge the state of SSA names
where it can in order to minimize the size of program_state instances,
and to increase the chances of being able to reuse exploded_node
instances whilst exploring the user's code.

PR analyzer/104943 identifies that we fail to purge state of local
variables, based on behavior seen in PR analyzer/104954 when attempting
to profile slow performance of -fanalyzer on a particular file in the
Linux kernel, where that testcase has many temporary "boxed" values of
structs containing ints, which are never cleaned up, leading to bloat
of the program_state instances (specifically, of the store objects).

This patch generalizes the state purging from just being on SSA names
to also work on local variables.  Doing so requires that we detect where
addresses to a local variable (or within them) are taken; we assume that
once a pointer has been taken, it's not longer safe to purge the value
of that decl at any successor point within the function.

Doing so speeds up the PR analyzer/104954 Linux kernel analyzer testcase
from taking 254 seconds to "just" 186 seconds (and I have a followup
patch in development that seems to further reduce this to 37 seconds).

The patch may also help with scaling up taint-detection so that it can
eventually be turned on by default, but we're not quite there (this
is PR analyzer/103533).

gcc/analyzer/ChangeLog:
	PR analyzer/104943
	PR analyzer/104954
	PR analyzer/103533
	* analyzer.h (class state_purge_per_decl): New forward decl.
	* engine.cc (impl_run_checkers): Pass region_model_manager to
	state_purge_map ctor.
	* program-point.cc (function_point::final_stmt_p): New.
	(function_point::get_next): New.
	* program-point.h (function_point::final_stmt_p): New decl.
	(function_point::get_next): New decl.
	* program-state.cc (program_state::prune_for_point): Generalize to
	purge local decls as well as SSA names.
	(program_state::can_purge_base_region_p): New.
	* program-state.h (program_state::can_purge_base_region_p): New
	decl.
	* region-model.cc (struct append_ssa_names_cb_data): Rename to...
	(struct append_regions_cb_data): ...this.
	(region_model::get_ssa_name_regions_for_current_frame): Rename
	to...
	(region_model::get_regions_for_current_frame): ...this, updating
	for other renamings.
	(region_model::append_ssa_names_cb): Rename to...
	(region_model::append_regions_cb): ...this, and drop the requirement
	that the subregion be a SSA name.
	* region-model.h (struct append_ssa_names_cb_data): Rename decl
	to...
	(struct append_regions_cb_data): ...this.
	(region_model::get_ssa_name_regions_for_current_frame): Rename
	decl to...
	(region_model::get_regions_for_current_frame): ...this.
	(region_model::append_ssa_names_cb): Rename decl to...
	(region_model::append_regions_cb): ...this.
	* state-purge.cc: Include "tristate.h", "selftest.h",
	"analyzer/store.h", "analyzer/region-model.h", and
	"gimple-walk.h".
	(get_candidate_for_purging): New.
	(class gimple_op_visitor): New.
	(my_load_cb): New.
	(my_store_cb): New.
	(my_addr_cb): New.
	(state_purge_map::state_purge_map): Add "mgr" param.  Update for
	renamings.  Find uses of local variables.
	(state_purge_map::~state_purge_map): Update for renaming of m_map
	to m_ssa_map.  Clean up m_decl_map.
	(state_purge_map::get_or_create_data_for_decl): New.
	(state_purge_per_ssa_name::state_purge_per_ssa_name): Update for
	inheriting from state_purge_per_tree.
	(state_purge_per_ssa_name::add_to_worklist): Likewise.
	(state_purge_per_decl::state_purge_per_decl): New.
	(state_purge_per_decl::add_needed_at): New.
	(state_purge_per_decl::add_pointed_to_at): New.
	(state_purge_per_decl::process_worklists): New.
	(state_purge_per_decl::add_to_worklist): New.
	(same_binding_p): New.
	(fully_overwrites_p): New.
	(state_purge_per_decl::process_point_backwards): New.
	(state_purge_per_decl::process_point_forwards): New.
	(state_purge_per_decl::needed_at_point_p): New.
	(state_purge_annotator::print_needed): Generalize to print local
	decls as well as SSA names.
	* state-purge.h (class state_purge_map): Update leading comment.
	(state_purge_map::map_t): Rename to...
	(state_purge_map::ssa_map_t): ...this.
	(state_purge_map::iterator): Rename to...
	(state_purge_map::ssa_iterator): ...this.
	(state_purge_map::decl_map_t): New typedef.
	(state_purge_map::decl_iterator): New typedef.
	(state_purge_map::state_purge_map): Add "mgr" param.
	(state_purge_map::get_data_for_ssa_name): Update for renaming.
	(state_purge_map::get_any_data_for_decl): New.
	(state_purge_map::get_or_create_data_for_decl): New decl.
	(state_purge_map::begin): Rename to...
	(state_purge_map::begin_ssas): ...this.
	(state_purge_map::end): Rename to...
	(state_purge_map::end_ssa): ...this.
	(state_purge_map::begin_decls): New.
	(state_purge_map::end_decls): New.
	(state_purge_map::m_map): Rename to...
	(state_purge_map::m_ssa_map): ...this.
	(state_purge_map::m_decl_map): New field.
	(class state_purge_per_tree): New class.
	(class state_purge_per_ssa_name): Inherit from state_purge_per_tree.
	(state_purge_per_ssa_name::get_function): Move to base class.
	(state_purge_per_ssa_name::point_set_t): Likewise.
	(state_purge_per_ssa_name::m_fun): Likewise.
	(class state_purge_per_decl): New.

gcc/testsuite/ChangeLog:
	PR analyzer/104943
	PR analyzer/104954
	PR analyzer/103533
	* gcc.dg/analyzer/torture/boxed-ptr-1.c: Update expected number
	of exploded nodes to reflect improvements in state purging.

Signed-off-by: David Malcolm <dmalcolm@redhat.com>

1 files changed, 94 insertions, 35 deletions

diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc
index 7501103..7ad581c 100644
--- a/gcc/analyzer/program-state.cc
+++ b/gcc/analyzer/program-state.cc
@@ -1122,52 +1122,90 @@ program_state::prune_for_point (exploded_graph &eg,
   if (pm)
     {
       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);
-      ssa_name_regs.qsort (region::cmp_ptr_ptr);
+      unsigned num_decls_purged = 0;
+      auto_vec<const decl_region *> regs;
+      new_state.m_region_model->get_regions_for_current_frame (&regs);
+      regs.qsort (region::cmp_ptr_ptr);
       unsigned i;
       const decl_region *reg;
-      FOR_EACH_VEC_ELT (ssa_name_regs, i, reg)
+      FOR_EACH_VEC_ELT (regs, i, reg)
 	{
-	  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 tree node = reg->get_decl ();
+	  if (TREE_CODE (node) == SSA_NAME)
 	    {
-	      /* 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, NULL);
-	      if (!new_state.can_purge_p (eg.get_ext_state (), sval)
-		  && SSA_NAME_VAR (ssa_name))
+	      const tree ssa_name = node;
+	      const state_purge_per_ssa_name &per_ssa
+		= pm->get_data_for_ssa_name (node);
+	      if (!per_ssa.needed_at_point_p (point.get_function_point ()))
 		{
-		  /* (currently only state maps can keep things
-		     alive).  */
-		  if (logger)
-		    logger->log ("not purging binding for %qE"
-				 " (used by state map)", ssa_name);
-		  continue;
+		  /* 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, NULL);
+		  if (!new_state.can_purge_p (eg.get_ext_state (), sval)
+		      && SSA_NAME_VAR (ssa_name))
+		    {
+		      /* (currently only state maps can keep things
+			 alive).  */
+		      if (logger)
+			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++;
 		}
-
-	      new_state.m_region_model->purge_region (reg);
-	      num_ssas_purged++;
+	    }
+	  else
+	    {
+	      const tree decl = node;
+	      gcc_assert (TREE_CODE (node) == VAR_DECL
+			  || TREE_CODE (node) == PARM_DECL
+			  || TREE_CODE (node) == RESULT_DECL);
+	      if (const state_purge_per_decl *per_decl
+		  = pm->get_any_data_for_decl (decl))
+		if (!per_decl->needed_at_point_p (point.get_function_point ()))
+		  {
+		    /* Don't purge bindings of decls if there are svalues
+		       that have unpurgable sm-state within the decl's cluster,
+		       so that leaks are reported at the end of the function,
+		       rather than at the last place that such a decl is
+		       referred to.  */
+		    if (!new_state.can_purge_base_region_p (eg.get_ext_state (),
+							    reg))
+		      {
+			/* (currently only state maps can keep things
+			   alive).  */
+			if (logger)
+			  logger->log ("not purging binding for %qE"
+				       " (value in binding used by state map)",
+				       decl);
+			continue;
+		      }
+
+		    new_state.m_region_model->purge_region (reg);
+		    num_decls_purged++;
+		  }
 	    }
 	}
 
-      if (num_ssas_purged > 0)
+      if (num_ssas_purged > 0 || num_decls_purged > 0)
 	{
 	  if (logger)
-	    logger->log ("num_ssas_purged: %i", num_ssas_purged);
+	    {
+	      logger->log ("num_ssas_purged: %i", num_ssas_purged);
+	      logger->log ("num_decl_purged: %i", num_decls_purged);
+	    }
 	  impl_region_model_context ctxt (eg, enode_for_diag,
 					  this,
 					  &new_state,
@@ -1182,6 +1220,27 @@ program_state::prune_for_point (exploded_graph &eg,
   return new_state;
 }
 
+/* Return true if there are no unpurgeable bindings within BASE_REG. */
+
+bool
+program_state::can_purge_base_region_p (const extrinsic_state &ext_state,
+					const region *base_reg) const
+{
+  binding_cluster *cluster
+    = m_region_model->get_store ()->get_cluster (base_reg);
+  if (!cluster)
+    return true;
+
+  for (auto iter : *cluster)
+    {
+      const svalue *sval = iter.second;
+      if (!can_purge_p (ext_state, sval))
+	return false;
+    }
+
+  return true;
+}
+
 /* Get a representative tree to use for describing SVAL.  */
 
 tree