[gcc r12-3763] path solver: Use ranger to solve unknowns.

[gcc r12-3763] path solver: Use ranger to solve unknowns.

[Aldy Hernandez]

https://gcc.gnu.org/g:97cfb54c3ff15b9691fd1c12a29de56966bf8e0d

commit r12-3763-g97cfb54c3ff15b9691fd1c12a29de56966bf8e0d
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Tue Sep 21 09:24:12 2021 +0200

    path solver: Use ranger to solve unknowns.
    
    The default behavior for the path solver is to resort to VARYING when
    the range for an unknown SSA is outside the given path.  This is both
    cheap and fast, but fails to get a significant amount of ranges that
    traditionally the DOM and VRP threaders could get.
    
    This patch uses the ranger to resolve any unknown names upon entry to
    the path.  It also uses equivalences to improve ranges.
    
    gcc/ChangeLog:
    
            * gimple-range-path.cc (path_range_query::defined_outside_path):
            New.
            (path_range_query::range_on_path_entry): New.
            (path_range_query::internal_range_of_expr): Resolve unknowns
            with ranger.
            (path_range_query::improve_range_with_equivs): New.
            (path_range_query::ssa_range_in_phi): Resolve unknowns with
            ranger.
            * gimple-range-path.h (class path_range_query): Add
            defined_outside_path, range_on_path_entry, and
            improve_range_with_equivs.

Diff:
---
 gcc/gimple-range-path.cc | 89 +++++++++++++++++++++++++++++++++++++++++++++---
 gcc/gimple-range-path.h  |  3 ++
 2 files changed, 88 insertions(+), 4 deletions(-)

diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index a8ead3da4dc..e65c7996bb7 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -121,6 +121,34 @@ path_range_query::debug ()
   dump (stderr);
 }
 
+// Return TRUE if NAME is defined outside the current path.
+
+bool
+path_range_query::defined_outside_path (tree name)
+{
+  gimple *def = SSA_NAME_DEF_STMT (name);
+  basic_block bb = gimple_bb (def);
+
+  return !bb || !m_path->contains (bb);
+}
+
+// Return the range of NAME on entry to the path.
+
+void
+path_range_query::range_on_path_entry (irange &r, tree name)
+{
+  int_range_max tmp;
+  basic_block entry = entry_bb ();
+  r.set_undefined ();
+  for (unsigned i = 0; i < EDGE_COUNT (entry->preds); ++i)
+    {
+      edge e = EDGE_PRED (entry, i);
+      if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
+	  && m_ranger.range_on_edge (tmp, e, name))
+	r.union_ (tmp);
+    }
+}
+
 // Return the range of NAME at the end of the path being analyzed.
 
 bool
@@ -132,6 +160,16 @@ path_range_query::internal_range_of_expr (irange &r, tree name, gimple *stmt)
   if (get_cache (r, name))
     return true;
 
+  if (m_resolve && defined_outside_path (name))
+    {
+      range_on_path_entry (r, name);
+
+      if (r.varying_p ())
+	improve_range_with_equivs (r, name);
+
+      set_cache (r, name);
+      return true;
+    }
 
   basic_block bb = stmt ? gimple_bb (stmt) : exit_bb ();
   if (stmt && range_defined_in_block (r, name, bb))
@@ -139,6 +177,9 @@ path_range_query::internal_range_of_expr (irange &r, tree name, gimple *stmt)
       if (TREE_CODE (name) == SSA_NAME)
 	r.intersect (gimple_range_global (name));
 
+      if (m_resolve && r.varying_p ())
+	improve_range_with_equivs (r, name);
+
       set_cache (r, name);
       return true;
     }
@@ -160,6 +201,33 @@ path_range_query::range_of_expr (irange &r, tree name, gimple *stmt)
   return false;
 }
 
+// Improve the range of NAME with the range of any of its equivalences.
+
+void
+path_range_query::improve_range_with_equivs (irange &r, tree name)
+{
+  if (TREE_CODE (name) != SSA_NAME)
+    return;
+
+  basic_block entry = entry_bb ();
+  relation_oracle *oracle = m_ranger.oracle ();
+
+  if (const bitmap_head *equivs = oracle->equiv_set (name, entry))
+    {
+      int_range_max t;
+      bitmap_iterator bi;
+      unsigned i;
+
+      EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi)
+	if (i != SSA_NAME_VERSION (name) && r.varying_p ())
+	  {
+	    tree equiv = ssa_name (i);
+	    range_on_path_entry (t, equiv);
+	    r.intersect (t);
+	  }
+    }
+}
+
 bool
 path_range_query::unreachable_path_p ()
 {
@@ -189,10 +257,11 @@ 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 ())
     {
+      if (m_resolve && m_ranger.range_of_expr (r, name, phi))
+	return;
+
       // 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));
@@ -210,8 +279,20 @@ path_range_query::ssa_range_in_phi (irange &r, gphi *phi)
 	tree arg = gimple_phi_arg_def (phi, i);
 
 	if (!get_cache (r, arg))
-	  r.set_varying (TREE_TYPE (name));
-
+	  {
+	    if (m_resolve)
+	      {
+		int_range_max tmp;
+		// Using both the range on entry to the path, and the
+		// range on this edge yields significantly better
+		// results.
+		range_on_path_entry (r, arg);
+		m_ranger.range_on_edge (tmp, e_in, arg);
+		r.intersect (tmp);
+		return;
+	      }
+	    r.set_varying (TREE_TYPE (name));
+	  }
 	return;
       }
   gcc_unreachable ();
diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
index f23cce18391..6f81f21d42f 100644
--- a/gcc/gimple-range-path.h
+++ b/gcc/gimple-range-path.h
@@ -48,6 +48,8 @@ public:
 
 private:
   bool internal_range_of_expr (irange &r, tree name, gimple *);
+  bool defined_outside_path (tree name);
+  void range_on_path_entry (irange &r, tree name);
 
   // Cache manipulation.
   void set_cache (const irange &r, tree name);
@@ -61,6 +63,7 @@ private:
   void ssa_range_in_phi (irange &r, gphi *phi);
   void precompute_relations (const vec<basic_block> &);
   void precompute_phi_relations (basic_block bb, basic_block prev);
+  void improve_range_with_equivs (irange &r, tree name);
   void add_copies_to_imports ();
   bool add_to_imports (tree name, bitmap imports);