This patch adds classes for tracking what state can be safely purged
at any given point in the program.
gcc/ChangeLog:
* analyzer/state-purge.cc: New file.
* analyzer/state-purge.h: New file.
---
gcc/analyzer/state-purge.cc | 516 ++++++++++++++++++++++++++++++++++++++++++++
gcc/analyzer/state-purge.h | 170 +++++++++++++++
2 files changed, 686 insertions(+)
create mode 100644 gcc/analyzer/state-purge.cc
create mode 100644 gcc/analyzer/state-purge.h
diff --git a/gcc/analyzer/state-purge.cc b/gcc/analyzer/state-purge.cc
new file mode 100644
index 0000000..caaa946
--- /dev/null
+++ b/gcc/analyzer/state-purge.cc
@@ -0,0 +1,516 @@
+/* Classes for purging state at function_points.
+ Copyright (C) 2019 Free Software Foundation, Inc.
+ Contributed by David Malcolm <dmalc...@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 "gcc-plugin.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tree.h"
+#include "timevar.h"
+#include "tree-ssa-alias.h"
+#include "gimple.h"
+#include "stringpool.h"
+#include "tree-vrp.h"
+#include "gimple-ssa.h"
+#include "tree-ssanames.h"
+#include "tree-phinodes.h"
+#include "ssa-iterators.h"
+#include "gimple-pretty-print.h"
+#include "analyzer/analyzer.h"
+#include "analyzer/state-purge.h"
+
+/* 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_client_timevar tv ("state_purge_map ctor");
+
+ 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 (pretty_printer *pp,
+ const supernode &n) const
+{
+ if (m_map == NULL)
+ return;
+
+ pp_printf (pp, "annotation_for_node_%i", n.m_index);
+ pp_printf (pp, " [shape=%s,style=filled,fillcolor=%s,label=\"",
+ "record", "lightblue");
+ pp_left_brace (pp);
+ 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_right_brace (pp);
+
+ pp_string (pp, "\"];\n\n");
+ pp_flush (pp);
+}
+
+/* Print V to PP as a comma-separated list in braces, titling it
+ with TITLE.
+
+ Subroutine of state_purge_annotator::add_stmt_annotations. */
+
+static void
+print_vec_of_names (pretty_printer *pp, const char *title,
+ const auto_vec<tree> &v)
+{
+ tree name;
+ unsigned i;
+ 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_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 (pretty_printer *pp,
+ const gimple *stmt) const
+{
+ if (m_map == NULL)
+ return;
+
+ if (stmt->code == GIMPLE_PHI)
+ return;
+
+ 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 (pp, "needed here", needed);
+ print_vec_of_names (pp, "not needed here", not_needed);
+}
diff --git a/gcc/analyzer/state-purge.h b/gcc/analyzer/state-purge.h
new file mode 100644
index 0000000..a86afc2
--- /dev/null
+++ b/gcc/analyzer/state-purge.h
@@ -0,0 +1,170 @@
+/* Classes for purging state at function_points.
+ Copyright (C) 2019 Free Software Foundation, Inc.
+ Contributed by David Malcolm <dmalc...@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:
+ 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 (pretty_printer *pp, const supernode &n)
+ const FINAL OVERRIDE;
+
+ void add_stmt_annotations (pretty_printer *pp,const gimple *stmt)
+ const FINAL OVERRIDE;
+
+private:
+ const state_purge_map *m_map;
+};
+
+#endif /* GCC_ANALYZER_STATE_PURGE_H */
--
1.8.5.3
