[40/45] analyzer: new files: state-purge.{cc|h}

diff --git a/gcc/analyzer/state-purge.cc b/gcc/analyzer/state-purge.cc
new file mode 100644
index 000000000000..0cad07b7bfae
--- /dev/null
+++ b/gcc/analyzer/state-purge.cc
@@ -0,0 +1,525 @@ 
+/* Classes for purging state at function_points.
+   Copyright (C) 2019 Free Software Foundation, Inc.
+   Contributed by David Malcolm <dmalcolm@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tree.h"
+#include "timevar.h"
+#include "tree-ssa-alias.h"
+#include "function.h"
+#include "basic-block.h"
+#include "gimple.h"
+#include "stringpool.h"
+#include "tree-vrp.h"
+#include "gimple-ssa.h"
+#include "tree-ssanames.h"
+#include "tree-phinodes.h"
+#include "options.h"
+#include "ssa-iterators.h"
+#include "gimple-pretty-print.h"
+#include "analyzer/analyzer.h"
+#include "analyzer/state-purge.h"
+
+#if ENABLE_ANALYZER
+
+/* state_purge_map's ctor.  Walk all SSA names in all functions, building
+   a state_purge_per_ssa_name instance for each.  */
+
+state_purge_map::state_purge_map (const supergraph &sg,
+				  logger *logger)
+: log_user (logger), m_sg (sg)
+{
+  LOG_FUNC (logger);
+
+  auto_timevar tv (TV_ANALYZER_STATE_PURGE);
+
+  cgraph_node *node;
+  FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
+  {
+    function *fun = node->get_fun ();
+    if (logger)
+      log ("function: %s", function_name (fun));
+    //printf ("function: %s\n", function_name (fun));
+    tree name;
+    unsigned int i;;
+    FOR_EACH_SSA_NAME (i, name, fun)
+      {
+	/* For now, don't bother tracking the .MEM SSA names.  */
+	if (tree var = SSA_NAME_VAR (name))
+	  if (TREE_CODE (var) == VAR_DECL)
+	    if (VAR_DECL_IS_VIRTUAL_OPERAND (var))
+	      continue;
+	m_map.put (name, new state_purge_per_ssa_name (*this, name, fun));
+      }
+  }
+}
+
+/* state_purge_map's dtor.  */
+
+state_purge_map::~state_purge_map ()
+{
+  for (iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
+    delete (*iter).second;
+}
+
+/* state_purge_per_ssa_name's ctor.
+
+   Locate all uses of VAR within FUN.
+   Walk backwards from each use, marking program points, until
+   we reach the def stmt, populating m_points_needing_var.
+
+   We have to track program points rather than
+   just stmts since there could be empty basic blocks on the way.  */
+
+state_purge_per_ssa_name::state_purge_per_ssa_name (const state_purge_map &map,
+						    tree name,
+						    function *fun)
+: m_points_needing_name (), m_name (name), m_fun (fun)
+{
+  LOG_FUNC (map.get_logger ());
+
+  if (map.get_logger ())
+    {
+      map.log ("SSA name: %qE within %qD", name, fun->decl);
+
+      /* Show def stmt.  */
+      const gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+      pretty_printer pp;
+      pp_gimple_stmt_1 (&pp, def_stmt, 0, (dump_flags_t)0);
+      map.log ("def stmt: %s", pp_formatted_text (&pp));
+    }
+
+  auto_vec<function_point> worklist;
+
+  /* Add all immediate uses of name to the worklist.
+     Compare with debug_immediate_uses.  */
+  imm_use_iterator iter;
+  use_operand_p use_p;
+  FOR_EACH_IMM_USE_FAST (use_p, iter, name)
+    {
+      if (USE_STMT (use_p))
+	{
+	  const gimple *use_stmt = USE_STMT (use_p);
+	  if (map.get_logger ())
+	    {
+	      pretty_printer pp;
+	      pp_gimple_stmt_1 (&pp, use_stmt, 0, (dump_flags_t)0);
+	      map.log ("used by stmt: %s", pp_formatted_text (&pp));
+	    }
+
+	  const supernode *snode
+	    = map.get_sg ().get_supernode_for_stmt (use_stmt);
+
+	  /* If it's a use within a phi node, then we care about
+	     which in-edge we came from.  */
+	  if (use_stmt->code == GIMPLE_PHI)
+	    {
+	      for (gphi_iterator gpi
+		     = const_cast<supernode *> (snode)->start_phis ();
+		   !gsi_end_p (gpi); gsi_next (&gpi))
+		{
+		  gphi *phi = gpi.phi ();
+		  if (phi == use_stmt)
+		    {
+		      /* Find arguments (and thus in-edges) which use NAME.  */
+		      for (unsigned arg_idx = 0;
+			   arg_idx < gimple_phi_num_args (phi);
+			   ++arg_idx)
+			{
+			  if (name == gimple_phi_arg (phi, arg_idx)->def)
+			    {
+			      edge in_edge = gimple_phi_arg_edge (phi, arg_idx);
+			      const superedge *in_sedge
+				= map.get_sg ().get_edge_for_cfg_edge (in_edge);
+			      function_point point
+				= function_point::before_supernode
+				(snode, in_sedge);
+			      add_to_worklist (point, &worklist,
+					       map.get_logger ());
+			      m_points_needing_name.add (point);
+			    }
+			}
+		    }
+		}
+	    }
+	  else
+	    {
+	      function_point point = before_use_stmt (map, use_stmt);
+	      add_to_worklist (point, &worklist, map.get_logger ());
+	      m_points_needing_name.add (point);
+
+	      /* We also need to add uses for conditionals and switches,
+		 where the stmt "happens" at the after_supernode, for filtering
+		 the out-edges.  */
+	      if (use_stmt == snode->get_last_stmt ())
+		{
+		  if (map.get_logger ())
+		    map.log ("last stmt in BB");
+		  function_point point
+		    = function_point::after_supernode (snode);
+		  add_to_worklist (point, &worklist, map.get_logger ());
+		  m_points_needing_name.add (point);
+		}
+	      else
+		if (map.get_logger ())
+		  map.log ("not last stmt in BB");
+	    }
+	}
+    }
+
+  /* Process worklist by walking backwards until we reach the def stmt.  */
+  {
+    log_scope s (map.get_logger (), "processing worklist");
+    while (worklist.length () > 0)
+      {
+	function_point point = worklist.pop ();
+	process_point (point, &worklist, map);
+    }
+  }
+
+  if (map.get_logger ())
+    {
+      map.log ("%qE in %qD is needed to process:", name, fun->decl);
+      for (point_set_t::iterator iter = m_points_needing_name.begin ();
+	   iter != m_points_needing_name.end ();
+	   ++iter)
+	{
+	  map.start_log_line ();
+	  map.get_logger ()->log_partial ("  point: ");
+	  (*iter).print (map.get_logger ()->get_printer (), format (false));
+	  map.end_log_line ();
+	}
+    }
+}
+
+/* Return true if the SSA name is needed at POINT.  */
+
+bool
+state_purge_per_ssa_name::needed_at_point_p (const function_point &point) const
+{
+  return const_cast <point_set_t &> (m_points_needing_name).contains (point);
+}
+
+/* Get the function_point representing immediately before USE_STMT.
+   Subroutine of ctor.  */
+
+function_point
+state_purge_per_ssa_name::before_use_stmt (const state_purge_map &map,
+					   const gimple *use_stmt)
+{
+  gcc_assert (use_stmt->code != GIMPLE_PHI);
+
+  const supernode *supernode
+    = map.get_sg ().get_supernode_for_stmt (use_stmt);
+  unsigned int stmt_idx = supernode->get_stmt_index (use_stmt);
+  return function_point::before_stmt (supernode, stmt_idx);
+}
+
+/* Add POINT to *WORKLIST if the point has not already been seen.
+   Subroutine of ctor.  */
+
+void
+state_purge_per_ssa_name::add_to_worklist (const function_point &point,
+					   auto_vec<function_point> *worklist,
+					   logger *logger)
+{
+  LOG_FUNC (logger);
+  if (logger)
+    {
+      logger->start_log_line ();
+      logger->log_partial ("point: '");
+      point.print (logger->get_printer (), format (false));
+      logger->log_partial ("' for worklist for %qE", m_name);
+      logger->end_log_line ();
+    }
+
+  gcc_assert (point.get_function () == m_fun);
+  if (point.get_from_edge ())
+    gcc_assert (point.get_from_edge ()->get_kind () == SUPEREDGE_CFG_EDGE);
+
+  if (m_points_needing_name.contains (point))
+    {
+      if (logger)
+	logger->log ("already seen for %qE", m_name);
+    }
+  else
+    {
+      if (logger)
+	logger->log ("not seen; adding to worklist for %qE", m_name);
+      m_points_needing_name.add (point);
+      worklist->safe_push (point);
+    }
+}
+
+/* Process POINT, popped from WORKLIST.
+   Iterate over predecessors of POINT, adding to WORKLIST.  */
+
+void
+state_purge_per_ssa_name::process_point (const function_point &point,
+					 auto_vec<function_point> *worklist,
+					 const state_purge_map &map)
+{
+  logger *logger = map.get_logger ();
+  LOG_FUNC (logger);
+  if (logger)
+    {
+      logger->start_log_line ();
+      logger->log_partial ("considering point: '");
+      point.print (logger->get_printer (), format (false));
+      logger->log_partial ("' for %qE", m_name);
+      logger->end_log_line ();
+    }
+
+  gimple *def_stmt = SSA_NAME_DEF_STMT (m_name);
+
+  const supernode *snode = point.get_supernode ();
+
+  switch (point.get_kind ())
+    {
+    default:
+      gcc_unreachable ();
+
+    case PK_ORIGIN:
+      break;
+
+    case PK_BEFORE_SUPERNODE:
+      {
+	for (gphi_iterator gpi
+	       = const_cast<supernode *> (snode)->start_phis ();
+	     !gsi_end_p (gpi); gsi_next (&gpi))
+	  {
+	    gphi *phi = gpi.phi ();
+	    if (phi == def_stmt)
+	      {
+		if (logger)
+		  logger->log ("def stmt within phis; terminating");
+		return;
+	      }
+	  }
+
+	/* Add given pred to worklist.  */
+	if (point.get_from_edge ())
+	  {
+	    gcc_assert (point.get_from_edge ()->m_src);
+	    add_to_worklist
+	      (function_point::after_supernode (point.get_from_edge ()->m_src),
+	       worklist, logger);
+	  }
+	else
+	  {
+	    /* Add any intraprocedually edge for a call.  */
+	    if (snode->m_returning_call)
+	      {
+		cgraph_edge *cedge
+		  = supergraph_call_edge (snode->m_fun,
+					  snode->m_returning_call);
+		gcc_assert (cedge);
+		superedge *sedge
+		  = map.get_sg ().get_intraprocedural_edge_for_call (cedge);
+		gcc_assert (sedge);
+		add_to_worklist
+		  (function_point::after_supernode (sedge->m_src),
+		   worklist, logger);
+	      }
+	  }
+      }
+      break;
+
+    case PK_BEFORE_STMT:
+      {
+	if (def_stmt == point.get_stmt ())
+	  {
+	    if (logger)
+	      logger->log ("def stmt; terminating");
+	    return;
+	  }
+	if (point.get_stmt_idx () > 0)
+	  add_to_worklist (function_point::before_stmt
+			     (snode, point.get_stmt_idx () - 1),
+			   worklist, logger);
+	else
+	{
+	  /* Add before_supernode to worklist.  This captures the in-edge,
+	     so we have to do it once per in-edge.  */
+	  unsigned i;
+	  superedge *pred;
+	  FOR_EACH_VEC_ELT (snode->m_preds, i, pred)
+	    add_to_worklist (function_point::before_supernode (snode,
+							       pred),
+			     worklist, logger);
+	}
+      }
+      break;
+
+    case PK_AFTER_SUPERNODE:
+      {
+	if (snode->m_stmts.length ())
+	  add_to_worklist
+	    (function_point::before_stmt (snode,
+					  snode->m_stmts.length () - 1),
+	     worklist, logger);
+	else
+	  {
+	    /* Add before_supernode to worklist.  This captures the in-edge,
+	       so we have to do it once per in-edge.  */
+	    unsigned i;
+	    superedge *pred;
+	    FOR_EACH_VEC_ELT (snode->m_preds, i, pred)
+	      add_to_worklist (function_point::before_supernode (snode,
+								 pred),
+			       worklist, logger);
+	    /* If it's the initial BB, add it, to ensure that we
+	       have "before supernode" for the initial ENTRY block, and don't
+	       erroneously purge SSA names for initial values of parameters.  */
+	    if (snode->entry_p ())
+	      {
+		add_to_worklist
+		  (function_point::before_supernode (snode, NULL),
+		   worklist, logger);
+	      }
+	  }
+      }
+      break;
+    }
+}
+
+/* class state_purge_annotator : public dot_annotator.  */
+
+/* Implementation of dot_annotator::add_node_annotations vfunc for
+   state_purge_annotator.
+
+   Add an additional record showing which names are purged on entry
+   to the supernode N.  */
+
+void
+state_purge_annotator::add_node_annotations (graphviz_out *gv,
+					     const supernode &n) const
+{
+  if (m_map == NULL)
+    return;
+
+  pretty_printer *pp = gv->get_pp ();
+
+   pp_printf (pp, "annotation_for_node_%i", n.m_index);
+   pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
+	      "lightblue");
+   pp_write_text_to_stream (pp);
+
+   // FIXME: passing in a NULL in-edge means we get no hits
+   function_point before_supernode
+     (function_point::before_supernode (&n, NULL));
+
+   for (state_purge_map::iterator iter = m_map->begin ();
+	iter != m_map->end ();
+	++iter)
+     {
+       tree name = (*iter).first;
+       state_purge_per_ssa_name *per_name_data = (*iter).second;
+       if (per_name_data->get_function () == n.m_fun)
+	 {
+PUSH_IGNORE_WFORMAT
+	   if (per_name_data->needed_at_point_p (before_supernode))
+	     pp_printf (pp, "%qE needed here", name);
+	   else
+	     pp_printf (pp, "%qE not needed here", name);
+POP_IGNORE_WFORMAT
+	 }
+       pp_newline (pp);
+     }
+
+   pp_string (pp, "\"];\n\n");
+   pp_flush (pp);
+}
+
+/* Print V to GV as a comma-separated list in braces within a <TR>,
+   titling it with TITLE.
+
+   Subroutine of state_purge_annotator::add_stmt_annotations.  */
+
+static void
+print_vec_of_names (graphviz_out *gv, const char *title,
+		    const auto_vec<tree> &v)
+{
+  pretty_printer *pp = gv->get_pp ();
+  tree name;
+  unsigned i;
+  gv->begin_tr ();
+  pp_printf (pp, "%s: {", title);
+  FOR_EACH_VEC_ELT (v, i, name)
+    {
+      if (i > 0)
+	pp_string (pp, ", ");
+PUSH_IGNORE_WFORMAT
+      pp_printf (pp, "%qE", name);
+POP_IGNORE_WFORMAT
+    }
+  pp_printf (pp, "}");
+  pp_write_text_as_html_like_dot_to_stream (pp);
+  gv->end_tr ();
+  pp_newline (pp);
+}
+
+/* Implementation of dot_annotator::add_stmt_annotations for
+   state_purge_annotator.
+
+   Add text showing which names are purged at STMT.  */
+
+void
+state_purge_annotator::add_stmt_annotations (graphviz_out *gv,
+					     const gimple *stmt) const
+{
+  if (m_map == NULL)
+    return;
+
+  if (stmt->code == GIMPLE_PHI)
+    return;
+
+  pretty_printer *pp = gv->get_pp ();
+
+  pp_newline (pp);
+
+  const supernode *supernode = m_map->get_sg ().get_supernode_for_stmt (stmt);
+  unsigned int stmt_idx = supernode->get_stmt_index (stmt);
+  function_point before_stmt
+    (function_point::before_stmt (supernode, stmt_idx));
+
+  auto_vec<tree> needed;
+  auto_vec<tree> not_needed;
+  for (state_purge_map::iterator iter = m_map->begin ();
+       iter != m_map->end ();
+       ++iter)
+    {
+      tree name = (*iter).first;
+      state_purge_per_ssa_name *per_name_data = (*iter).second;
+      if (per_name_data->get_function () == supernode->m_fun)
+	{
+	  if (per_name_data->needed_at_point_p (before_stmt))
+	    needed.safe_push (name);
+	  else
+	    not_needed.safe_push (name);
+	}
+    }
+
+  print_vec_of_names (gv, "needed here", needed);
+  print_vec_of_names (gv, "not needed here", not_needed);
+}
+
+#endif /* #if ENABLE_ANALYZER */
diff --git a/gcc/analyzer/state-purge.h b/gcc/analyzer/state-purge.h
new file mode 100644
index 000000000000..a1f2793951c5
--- /dev/null
+++ b/gcc/analyzer/state-purge.h
@@ -0,0 +1,164 @@ 
+/* Classes for purging state at function_points.
+   Copyright (C) 2019 Free Software Foundation, Inc.
+   Contributed by David Malcolm <dmalcolm@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef GCC_ANALYZER_STATE_PURGE_H
+#define GCC_ANALYZER_STATE_PURGE_H
+
+#include "analyzer/analyzer-logging.h"
+#include "analyzer/program-point.h"
+
+/* Hash traits for function_point.  */
+
+template <> struct default_hash_traits<function_point>
+: public pod_hash_traits<function_point>
+{
+};
+
+template <>
+inline hashval_t
+pod_hash_traits<function_point>::hash (value_type v)
+{
+  return v.hash ();
+}
+
+template <>
+inline bool
+pod_hash_traits<function_point>::equal (const value_type &existing,
+                                 const value_type &candidate)
+{
+  return existing == candidate;
+}
+template <>
+inline void
+pod_hash_traits<function_point>::mark_deleted (value_type &v)
+{
+  v = function_point::deleted ();
+}
+template <>
+inline void
+pod_hash_traits<function_point>::mark_empty (value_type &v)
+{
+  v = function_point::empty ();
+}
+template <>
+inline bool
+pod_hash_traits<function_point>::is_deleted (value_type v)
+{
+  return v.get_kind () == PK_DELETED;
+}
+template <>
+inline bool
+pod_hash_traits<function_point>::is_empty (value_type v)
+{
+  return v.get_kind () == PK_EMPTY;
+}
+
+/* The result of analyzing which SSA names can be purged from state at
+   different points in the program, so that we can simplify program_state
+   objects, in the hope of reducing state-blowup.  */
+
+class state_purge_map : public log_user
+{
+public:
+  typedef ordered_hash_map<tree, state_purge_per_ssa_name *> map_t;
+  typedef map_t::iterator iterator;
+
+  state_purge_map (const supergraph &sg, logger *logger);
+  ~state_purge_map ();
+
+  const state_purge_per_ssa_name &get_data_for_ssa_name (tree name) const
+  {
+    gcc_assert (TREE_CODE (name) == SSA_NAME);
+    if (tree var = SSA_NAME_VAR (name))
+      if (TREE_CODE (var) == VAR_DECL)
+	gcc_assert (!VAR_DECL_IS_VIRTUAL_OPERAND (var));
+
+    state_purge_per_ssa_name **slot
+      = const_cast <map_t&> (m_map).get (name);
+    return **slot;
+  }
+
+  const supergraph &get_sg () const { return m_sg; }
+
+  iterator begin () const { return m_map.begin (); }
+  iterator end () const { return m_map.end (); }
+
+private:
+  DISABLE_COPY_AND_ASSIGN (state_purge_map);
+
+  const supergraph &m_sg;
+  map_t m_map;
+};
+
+/* The part of a state_purge_map relating to a specific SSA name.
+
+   The result of analyzing a given SSA name, recording which
+   function_points need to retain state information about it to handle
+   their successor states, so that we can simplify program_state objects,
+   in the hope of reducing state-blowup.  */
+
+class state_purge_per_ssa_name
+{
+public:
+  state_purge_per_ssa_name (const state_purge_map &map,
+			    tree name,
+			    function *fun);
+
+  bool needed_at_point_p (const function_point &point) const;
+
+  function *get_function () const { return m_fun; }
+
+private:
+  static function_point before_use_stmt (const state_purge_map &map,
+					 const gimple *use_stmt);
+
+  void add_to_worklist (const function_point &point,
+			auto_vec<function_point> *worklist,
+			logger *logger);
+
+  void process_point (const function_point &point,
+		      auto_vec<function_point> *worklist,
+		      const state_purge_map &map);
+
+  typedef hash_set<function_point> point_set_t;
+  point_set_t m_points_needing_name;
+  tree m_name;
+  function *m_fun;
+};
+
+/* Subclass of dot_annotator for use by -fdump-analyzer-state-purge.
+   Annotate the .dot output with state-purge information.  */
+
+class state_purge_annotator : public dot_annotator
+{
+public:
+  state_purge_annotator (const state_purge_map *map) : m_map (map) {}
+
+  void add_node_annotations (graphviz_out *gv, const supernode &n)
+    const FINAL OVERRIDE;
+
+  void add_stmt_annotations (graphviz_out *gv, const gimple *stmt)
+    const FINAL OVERRIDE;
+
+private:
+  const state_purge_map *m_map;
+};
+
+#endif /* GCC_ANALYZER_STATE_PURGE_H */