[PATCH 1/2] Implement basic block path solver.

[Aldy Hernandez <aldyh@redhat.com>]

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.

The main API is:

// This class is a basic block path solver.  Given a set of BBs
// indicating a path through the CFG, range_in_path() will return the
// range of an SSA 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_solver
{
public:
  path_solver (gimple_ranger &ranger);
  virtual ~path_solver ();
  void precompute_ranges (const vec<basic_block> *path,
			  const bitmap_head *imports);
  void range_in_path (irange &, tree name);
  void range_in_path (irange &, gimple *);
};

gcc/ChangeLog:

        * Makefile.in (OBJS): Add tree-ssa-path-solver.o.
	* tree-ssa-path-solver.cc: New file.
	* tree-ssa-path-solver.h: New file.
---
 gcc/Makefile.in             |   1 +
 gcc/tree-ssa-path-solver.cc | 310 ++++++++++++++++++++++++++++++++++++
 gcc/tree-ssa-path-solver.h  |  85 ++++++++++
 3 files changed, 396 insertions(+)
 create mode 100644 gcc/tree-ssa-path-solver.cc
 create mode 100644 gcc/tree-ssa-path-solver.h

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index ebf26442992..66cc5f9529e 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1644,6 +1644,7 @@ OBJS = \
 	tree-ssa-loop.o \
 	tree-ssa-math-opts.o \
 	tree-ssa-operands.o \
+	tree-ssa-path-solver.o \
 	tree-ssa-phiopt.o \
 	tree-ssa-phiprop.o \
 	tree-ssa-pre.o \
diff --git a/gcc/tree-ssa-path-solver.cc b/gcc/tree-ssa-path-solver.cc
new file mode 100644
index 00000000000..1e2c37cff78
--- /dev/null
+++ b/gcc/tree-ssa-path-solver.cc
@@ -0,0 +1,310 @@
+/* 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 "tree-ssa-path-solver.h"
+#include "ssa.h"
+
+// Internal construct to help facilitate debugging of solver.
+#define DEBUG_SOLVER getenv("DEBUG")
+
+path_solver::path_solver (gimple_ranger &ranger)
+  : m_ranger (ranger)
+{
+  m_cache = new ssa_global_cache;
+  m_has_cache_entry = BITMAP_ALLOC (NULL);
+  m_path = NULL;
+}
+
+path_solver::~path_solver ()
+{
+  BITMAP_FREE (m_has_cache_entry);
+  delete m_cache;
+}
+
+// Mark cache entry for NAME as unused.
+
+void
+path_solver::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_solver::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_solver::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);
+}
+
+bool
+path_solver::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;
+
+  if (stmt && range_defined_in_block (r, name, gimple_bb (stmt)))
+    {
+      set_cache (r, name);
+      return true;
+    }
+
+  // Otherwise return varying.
+  r.set_varying (TREE_TYPE (name));
+  // ?? Is this set_cache necessary?
+  set_cache (r, name);
+  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_solver::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_solver::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 ())
+    {
+      r.set_varying (TREE_TYPE (name));
+      return;
+    }
+
+  basic_block prev = prev_bb ();
+  edge e_in = find_edge (prev, bb);
+  for (size_t i = 0; i < gimple_phi_num_args (phi); ++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));
+
+	// ?? Is this set_cache necessary?
+	set_cache (r, 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_solver::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 (stderr, "range_defined_in_block (BB%d) for ", bb->index);
+      print_generic_expr (stderr, name, TDF_SLIM);
+      fprintf (stderr, " is ");
+      r.dump (stderr);
+      fprintf (stderr, "\n");
+    }
+  return true;
+}
+
+// Precompute ranges defined in the current block, or ranges
+// that are exported on an edge to the next block.  The cache is
+// updated accordingly.
+
+void
+path_solver::precompute_ranges_in_block ()
+{
+  basic_block bb = curr_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 (stderr, "outgoing_edge_range_p for ");
+		  print_generic_expr (stderr, name, TDF_SLIM);
+		  fprintf (stderr, " on edge %d->%d ",
+			   e->src->index, e->dest->index);
+		  fprintf (stderr, "is ");
+		  r.dump (stderr);
+		  fprintf (stderr, "\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_solver::precompute_ranges (const vec<basic_block> *path,
+				const bitmap_head *imports)
+{
+  set_path (path);
+  m_imports = imports;
+
+  if (DEBUG_SOLVER)
+    {
+      extern void debug (vec<basic_block> *);
+      extern void debug (const bitmap_head *);
+      fprintf (stderr, "\nPATH is:\n");
+      debug (const_cast <vec<basic_block> *> (path));
+      fprintf (stderr, "imports: ");
+      debug (imports);
+    }
+
+  while (1)
+    {
+      precompute_ranges_in_block ();
+      if (at_exit ())
+	break;
+      move_next ();
+    }
+}
+
+// Return the range of NAME as it would be seen at the end of the path
+// being analyzed.
+
+void
+path_solver::range_in_path (irange &r, tree name)
+{
+  basic_block bb = exit_bb ();
+
+  if (get_cache (r, name))
+    return;
+
+  if (range_defined_in_block (r, name, bb))
+    return;
+
+  // The path may not be deep enough to resolve NAME.
+  r.set_varying (TREE_TYPE (name));
+}
+
+// Return the range of STMT as it would be seen at the end of the path
+// being analyzed.  Anything but the final conditional in a BB will
+// return VARYING.
+
+void
+path_solver::range_in_path (irange &r, gimple *stmt)
+{
+  if (gimple_code (stmt) == GIMPLE_COND && fold_range (r, stmt, this))
+    return;
+
+  r.set_varying (gimple_expr_type (stmt));
+}
diff --git a/gcc/tree-ssa-path-solver.h b/gcc/tree-ssa-path-solver.h
new file mode 100644
index 00000000000..c07265d4510
--- /dev/null
+++ b/gcc/tree-ssa-path-solver.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_in_path() will return the
+// range of an SSA 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_solver : private range_query
+{
+public:
+  path_solver (gimple_ranger &ranger);
+  virtual ~path_solver ();
+  void precompute_ranges (const vec<basic_block> *path,
+			  const bitmap_head *imports);
+  void range_in_path (irange &, tree name);
+  void range_in_path (irange &, gimple *);
+
+private:
+  bool range_of_expr (irange &r, tree name, gimple * = NULL) override;
+
+  // 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 ();
+  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
-- 
2.31.1