[7/7] path solver: Use ranger to solve unknowns.

Message ID 20210921165350.414593-8-aldyh@redhat.com
State Committed
Commit 97cfb54c3ff15b9691fd1c12a29de56966bf8e0d
Headers
Series Add ability to resolve unknowns to path solver. |

Commit Message

Aldy Hernandez Sept. 21, 2021, 4:53 p.m. UTC
  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.

Committed.

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.
---
 gcc/gimple-range-path.cc | 89 ++++++++++++++++++++++++++++++++++++++--
 gcc/gimple-range-path.h  |  3 ++
 2 files changed, 88 insertions(+), 4 deletions(-)
  

Patch

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);