[gcc r12-2532] Implement basic block path solver.

[gcc r12-2532] Implement basic block path solver.

[Aldy Hernandez]

https://gcc.gnu.org/g:fcc7c6369f7fbf293f502d3d207a90b76cc2c62f

commit r12-2532-gfcc7c6369f7fbf293f502d3d207a90b76cc2c62f
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Tue Jun 15 12:20:43 2021 +0200

    Implement basic block path solver.
    
    This is is the main basic block path solver for use in the ranger-based
    backwards threader.  Given a path of BBs, the class can solve the final
    conditional or any SSA name used in calculating the final conditional.
    
    gcc/ChangeLog:
    
            * Makefile.in (OBJS): Add gimple-range-path.o.
            * gimple-range-path.cc: New file.
            * gimple-range-path.h: New file.

Diff:
---
 gcc/Makefile.in          |   1 +
 gcc/gimple-range-path.cc | 329 +++++++++++++++++++++++++++++++++++++++++++++++
 gcc/gimple-range-path.h  |  85 ++++++++++++
 3 files changed, 415 insertions(+)

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 1666ef84d6a..29bd4edb4b7 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1650,6 +1650,7 @@ OBJS = \
 	tree-ssa-loop.o \
 	tree-ssa-math-opts.o \
 	tree-ssa-operands.o \
+	gimple-range-path.o \
 	tree-ssa-phiopt.o \
 	tree-ssa-phiprop.o \
 	tree-ssa-pre.o \
diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
new file mode 100644
index 00000000000..a8226a6810f
--- /dev/null
+++ b/gcc/gimple-range-path.cc
@@ -0,0 +1,329 @@
+/* Basic block path solver.
+   Copyright (C) 2021 Free Software Foundation, Inc.
+   Contributed by Aldy Hernandez <aldyh@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 "backend.h"
+#include "tree.h"
+#include "gimple.h"
+#include "cfganal.h"
+#include "value-range.h"
+#include "gimple-range.h"
+#include "tree-pretty-print.h"
+#include "gimple-range-path.h"
+#include "ssa.h"
+
+// Internal construct to help facilitate debugging of solver.
+#define DEBUG_SOLVER (0 && dump_file)
+
+path_range_query::path_range_query (gimple_ranger &ranger)
+  : m_ranger (ranger)
+{
+  m_cache = new ssa_global_cache;
+  m_has_cache_entry = BITMAP_ALLOC (NULL);
+  m_path = NULL;
+}
+
+path_range_query::~path_range_query ()
+{
+  BITMAP_FREE (m_has_cache_entry);
+  delete m_cache;
+}
+
+// Mark cache entry for NAME as unused.
+
+void
+path_range_query::clear_cache (tree name)
+{
+  unsigned v = SSA_NAME_VERSION (name);
+  bitmap_clear_bit (m_has_cache_entry, v);
+}
+
+// If NAME has a cache entry, return it in R, and return TRUE.
+
+inline bool
+path_range_query::get_cache (irange &r, tree name)
+{
+  if (!gimple_range_ssa_p (name))
+    return get_global_range_query ()->range_of_expr (r, name);
+
+  unsigned v = SSA_NAME_VERSION (name);
+  if (bitmap_bit_p (m_has_cache_entry, v))
+    return m_cache->get_global_range (r, name);
+
+  return false;
+}
+
+// Set the cache entry for NAME to R.
+
+void
+path_range_query::set_cache (const irange &r, tree name)
+{
+  unsigned v = SSA_NAME_VERSION (name);
+  bitmap_set_bit (m_has_cache_entry, v);
+  m_cache->set_global_range (name, r);
+}
+
+void
+path_range_query::dump (FILE *dump_file)
+{
+  if (m_path->is_empty ())
+    return;
+
+  unsigned i;
+  bitmap_iterator bi;
+  extern void dump_ranger (FILE *, const vec<basic_block> &);
+
+  fprintf (dump_file, "Path is:\n");
+  dump_ranger (dump_file, *m_path);
+
+  fprintf (dump_file, "Imports:\n");
+  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+    {
+      tree name = ssa_name (i);
+      print_generic_expr (dump_file, name, TDF_SLIM);
+      fprintf (dump_file, "\n");
+    }
+
+  m_cache->dump (dump_file);
+}
+
+void
+path_range_query::debug ()
+{
+  dump (stderr);
+}
+
+// Return the range of NAME at the end of the path being analyzed.
+
+bool
+path_range_query::range_of_expr (irange &r, tree name, gimple *stmt)
+{
+  if (!irange::supports_type_p (TREE_TYPE (name)))
+    return false;
+
+  if (get_cache (r, name))
+    return true;
+
+
+  basic_block bb = stmt ? gimple_bb (stmt) : exit_bb ();
+  if (stmt && range_defined_in_block (r, name, bb))
+    {
+      set_cache (r, name);
+      return true;
+    }
+
+  r.set_varying (TREE_TYPE (name));
+  return true;
+}
+
+// Return the range of STMT at the end of the path being analyzed.
+// Anything but the final conditional in a BB will return VARYING.
+
+bool
+path_range_query::range_of_stmt (irange &r, gimple *stmt, tree)
+{
+  tree type = gimple_range_type (stmt);
+
+  if (!irange::supports_type_p (type))
+    return false;
+
+  if (gimple_code (stmt) == GIMPLE_COND && fold_range (r, stmt, this))
+    return true;
+
+  r.set_varying (type);
+  return true;
+}
+
+// Initialize the current path to PATH.  The current block is set to
+// the entry block to the path.
+//
+// Note that the blocks are in reverse order, so the exit block is
+// path[0].
+
+void
+path_range_query::set_path (const vec<basic_block> &path)
+{
+  gcc_checking_assert (path.length () > 1);
+  m_path = &path;
+  m_pos = m_path->length () - 1;
+  bitmap_clear (m_has_cache_entry);
+}
+
+// Return the range of the result of PHI in R.
+
+void
+path_range_query::ssa_range_in_phi (irange &r, gphi *phi)
+{
+  tree name = gimple_phi_result (phi);
+  basic_block bb = gimple_bb (phi);
+
+  // We experimented with querying ranger's range_on_entry here, but
+  // the performance penalty was too high, for hardly any improvements.
+  if (at_entry ())
+    {
+      // Try fold just in case we can resolve simple things like PHI <5(99), 6(88)>.
+      if (!fold_range (r, phi, this))
+	r.set_varying (TREE_TYPE (name));
+
+      return;
+    }
+
+  basic_block prev = prev_bb ();
+  edge e_in = find_edge (prev, bb);
+  unsigned nargs = gimple_phi_num_args (phi);
+
+  for (size_t i = 0; i < nargs; ++i)
+    if (e_in == gimple_phi_arg_edge (phi, i))
+      {
+	tree arg = gimple_phi_arg_def (phi, i);
+
+	if (!get_cache (r, arg))
+	  r.set_varying (TREE_TYPE (name));
+
+	return;
+      }
+  gcc_unreachable ();
+}
+
+// If NAME is defined in BB, set R to the range of NAME, and return
+// TRUE.  Otherwise, return FALSE.
+
+bool
+path_range_query::range_defined_in_block (irange &r, tree name, basic_block bb)
+{
+  gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+  basic_block def_bb = gimple_bb (def_stmt);
+
+  if (def_bb != bb)
+    return false;
+
+  if (gimple_code (def_stmt) == GIMPLE_PHI)
+    ssa_range_in_phi (r, as_a<gphi *> (def_stmt));
+  else if (!fold_range (r, def_stmt, this))
+    r.set_varying (TREE_TYPE (name));
+
+  if (DEBUG_SOLVER)
+    {
+      fprintf (dump_file, "range_defined_in_block (BB%d) for ", bb->index);
+      print_generic_expr (dump_file, name, TDF_SLIM);
+      fprintf (dump_file, " is ");
+      r.dump (dump_file);
+      fprintf (dump_file, "\n");
+    }
+  return true;
+}
+
+// Precompute ranges defined in the current block, or ranges
+// that are exported on an edge to the next block.
+
+void
+path_range_query::precompute_ranges_in_block (basic_block bb)
+{
+  bitmap_iterator bi;
+  int_range_max r, cached_range;
+  unsigned i;
+
+  // Force recalculation of any names in the cache that are defined in
+  // this block.  This can happen on interdependent SSA/phis in loops.
+  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+    {
+      tree name = ssa_name (i);
+      gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+      basic_block def_bb = gimple_bb (def_stmt);
+
+      if (def_bb == bb)
+	clear_cache (name);
+    }
+
+  // Solve imports defined in this block.
+  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+    {
+      tree name = ssa_name (i);
+
+      if (range_defined_in_block (r, name, bb))
+	set_cache (r, name);
+    }
+
+  if (at_exit ())
+    return;
+
+  // Solve imports that are exported to the next block.
+  edge e = find_edge (bb, next_bb ());
+  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+    {
+      tree name = ssa_name (i);
+      gori_compute &g = m_ranger.gori ();
+      bitmap exports = g.exports (bb);
+
+      if (bitmap_bit_p (exports, i))
+	{
+	  if (g.outgoing_edge_range_p (r, e, name, *this))
+	    {
+	      if (get_cache (cached_range, name))
+		r.intersect (cached_range);
+
+	      set_cache (r, name);
+	      if (DEBUG_SOLVER)
+		{
+		  fprintf (dump_file, "outgoing_edge_range_p for ");
+		  print_generic_expr (dump_file, name, TDF_SLIM);
+		  fprintf (dump_file, " on edge %d->%d ",
+			   e->src->index, e->dest->index);
+		  fprintf (dump_file, "is ");
+		  r.dump (dump_file);
+		  fprintf (dump_file, "\n");
+		}
+	    }
+	}
+    }
+}
+
+// Precompute the ranges for IMPORTS along PATH.
+//
+// IMPORTS are the set of SSA names, any of which could potentially
+// change the value of the final conditional in PATH.
+
+void
+path_range_query::precompute_ranges (const vec<basic_block> &path,
+				     const bitmap_head *imports)
+{
+  set_path (path);
+  m_imports = imports;
+
+  if (DEBUG_SOLVER)
+    fprintf (dump_file, "path_range_query: precompute_ranges\n");
+
+  while (1)
+    {
+      basic_block bb = curr_bb ();
+
+      precompute_ranges_in_block (bb);
+
+      if (at_exit ())
+	break;
+
+      move_next ();
+    }
+
+  if (DEBUG_SOLVER)
+    dump (dump_file);
+}
diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
new file mode 100644
index 00000000000..43f0ec80286
--- /dev/null
+++ b/gcc/gimple-range-path.h
@@ -0,0 +1,85 @@
+/* Header file for jump threading path solver.
+   Copyright (C) 2021 Free Software Foundation, Inc.
+   Contributed by Aldy Hernandez <aldyh@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_TREE_SSA_THREADSOLVER_H
+#define GCC_TREE_SSA_THREADSOLVER_H
+
+// This class is a basic block path solver.  Given a set of BBs
+// indicating a path through the CFG, range_of_expr and range_of_stmt
+// will calculate the range of an SSA or STMT as if the BBs in the
+// path would have been executed in order.
+//
+// Only SSA names passed in IMPORTS are precomputed, and can be
+// queried.
+//
+// Note that the blocks are in reverse order, thus the exit block is
+// path[0].
+
+class path_range_query : public range_query
+{
+public:
+  path_range_query (class gimple_ranger &ranger);
+  virtual ~path_range_query ();
+  void precompute_ranges (const vec<basic_block> &path,
+			  const bitmap_head *imports);
+  bool range_of_expr (irange &r, tree name, gimple * = NULL) override;
+  bool range_of_stmt (irange &r, gimple *, tree name = NULL) override;
+  void dump (FILE *);
+  void debug ();
+
+private:
+  // Cache manipulation.
+  void set_cache (const irange &r, tree name);
+  bool get_cache (irange &r, tree name);
+  void clear_cache (tree name);
+
+  // Methods to precompute ranges for the given path.
+  bool range_defined_in_block (irange &, tree name, basic_block bb);
+  void precompute_ranges_in_block (basic_block bb);
+  void ssa_range_in_phi (irange &r, gphi *phi);
+
+  // Path navigation.
+  void set_path (const vec<basic_block> &);
+  basic_block entry_bb () { return (*m_path)[m_path->length () - 1]; }
+  basic_block exit_bb ()  { return (*m_path)[0]; }
+  basic_block curr_bb ()  { return (*m_path)[m_pos]; }
+  basic_block prev_bb ()  { return (*m_path)[m_pos + 1]; }
+  basic_block next_bb ()  { return (*m_path)[m_pos - 1]; }
+  bool at_entry ()	  { return m_pos == m_path->length () - 1; }
+  bool at_exit ()	  { return m_pos == 0; }
+  void move_next ()	  { --m_pos; }
+
+  // Range cache for SSA names.
+  ssa_global_cache *m_cache;
+
+  // Set for each SSA that has an active entry in the cache.
+  bitmap m_has_cache_entry;
+
+  // Path being analyzed.
+  const vec<basic_block> *m_path;
+
+  // Current path position.
+  unsigned m_pos;
+
+  const bitmap_head *m_imports;
+  gimple_ranger &m_ranger;
+};
+
+#endif // GCC_TREE_SSA_THREADSOLVER_H