[COMMITTED] path solver: Only compute relations for imports.

[COMMITTED] path solver: Only compute relations for imports.

[Aldy Hernandez]

We are currently calculating implicit PHI relations for all PHI
arguments.  This creates unecessary work, as we only care about SSA
names in the import bitmap.  Similarly for inter-path relationals.  We
can avoid things not in the bitmap.

Tested on x86-64 and ppc64le Linux with the usual regstrap.  I also
verified that the before and after number of threads was the same
in a suite of .ii files from a bootstrap.

gcc/ChangeLog:

	PR tree-optimization/102943
	* gimple-range-path.cc (path_range_query::compute_phi_relations):
	Only compute relations for SSA names in the import list.
	(path_range_query::compute_outgoing_relations): Same.
	* gimple-range-path.h (path_range_query::import_p): New.
---
 gcc/gimple-range-path.cc |  7 ++++++-
 gcc/gimple-range-path.h  | 10 ++++++++++
 2 files changed, 16 insertions(+), 1 deletion(-)

diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index d8c2a9b6a86..42309886c94 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -678,8 +678,12 @@ path_range_query::compute_phi_relations (basic_block bb, basic_block prev)
        gsi_next (&iter))
     {
       gphi *phi = iter.phi ();
+      tree result = gimple_phi_result (phi);
       unsigned nargs = gimple_phi_num_args (phi);
 
+      if (!import_p (result))
+	continue;
+
       for (size_t i = 0; i < nargs; ++i)
 	if (e_in == gimple_phi_arg_edge (phi, i))
 	  {
@@ -701,7 +705,8 @@ path_range_query::compute_outgoing_relations (basic_block bb, basic_block next)
 
   if (stmt
       && gimple_code (stmt) == GIMPLE_COND
-      && irange::supports_type_p (TREE_TYPE (gimple_cond_lhs (stmt))))
+      && (import_p (gimple_cond_lhs (stmt))
+	  || import_p (gimple_cond_rhs (stmt))))
     {
       int_range<2> r;
       gcond *cond = as_a<gcond *> (stmt);
diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
index 541613956e1..f21d07f71c4 100644
--- a/gcc/gimple-range-path.h
+++ b/gcc/gimple-range-path.h
@@ -62,6 +62,7 @@ private:
   void maybe_register_phi_relation (gphi *, tree arg);
   void add_copies_to_imports ();
   bool add_to_imports (tree name, bitmap imports);
+  inline bool import_p (tree name);
 
   // Path navigation.
   void set_path (const vec<basic_block> &);
@@ -97,4 +98,13 @@ private:
   bool m_undefined_path;
 };
 
+// Return TRUE if NAME is in the import bitmap.
+
+bool
+path_range_query::import_p (tree name)
+{
+  return (TREE_CODE (name) == SSA_NAME
+	  && bitmap_bit_p (m_imports, SSA_NAME_VERSION (name)));
+}
+
 #endif // GCC_TREE_SSA_THREADSOLVER_H
-- 
2.31.1

[COMMITTED] Avoid repeating calculations in threader.

[Aldy Hernandez]

We already attempt to resolve the current path on entry to
find_paths_to_name(), so there's no need to do so again for each
exported range since nothing has changed.

Removing this redundant calculation avoids 22% of calls into the path
solver.

Tested on x86-64 and ppc64le Linux with the usual regstrap.  I also
verified that the before and after number of threads was the same
in a suite of .ii files from a bootstrap.

gcc/ChangeLog:

	PR tree-optimization/102943
	* tree-ssa-threadbackward.c (back_threader::find_paths_to_names):
	Avoid duplicate calculation of paths.
---
 gcc/tree-ssa-threadbackward.c | 12 ------------
 1 file changed, 12 deletions(-)

diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index 29e9d6a3f90..b7eaff94567 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -443,18 +443,6 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting)
 	      goto leave_bb;
 	    }
 	}
-      // Examine blocks that define or export an interesting SSA,
-      // since they may compute a range which resolve this path.
-      if ((def_bb == bb
-	   || bitmap_bit_p (m_ranger->gori ().exports (bb), i))
-	  && m_path.length () > 1)
-	{
-	  if (maybe_register_path ())
-	    {
-	      done = true;
-	      goto leave_bb;
-	    }
-	}
     }
 
   // If there are interesting names not yet processed, keep looking.
-- 
2.31.1

[COMMITTED] path solver: Prefer range_of_expr instead of range_on_edge.

[Aldy Hernandez]

The range_of_expr method provides better caching than range_on_edge.
If we have a statement, we can just it and avoid the range_on_edge
dance.  Plus we can use all the range_of_expr fanciness.

Tested on x86-64 and ppc64le Linux with the usual regstrap.  I also
verified that the before and after number of threads was the same or
greater in a suite of .ii files from a bootstrap.

gcc/ChangeLog:

	PR tree-optimization/102943
	* gimple-range-path.cc (path_range_query::range_on_path_entry):
	Prefer range_of_expr unless there are no statements in the BB.
---
 gcc/gimple-range-path.cc | 18 ++++++++++++++++--
 1 file changed, 16 insertions(+), 2 deletions(-)

diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index 42309886c94..9175651e896 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -135,10 +135,24 @@ void
 path_range_query::range_on_path_entry (irange &r, tree name)
 {
   gcc_checking_assert (defined_outside_path (name));
-  int_range_max tmp;
   basic_block entry = entry_bb ();
-  bool changed = false;
 
+  // Prefer to use range_of_expr if we have a statement to look at,
+  // since it has better caching than range_on_edge.
+  gimple *last = last_stmt (entry);
+  if (last)
+    {
+      if (m_ranger.range_of_expr (r, name, last))
+	return;
+      gcc_unreachable ();
+    }
+
+  // If we have no statement, look at all the incoming ranges to the
+  // block.  This can happen when we're querying a block with only an
+  // outgoing edge (no statement but the fall through edge), but for
+  // which we can determine a range on entry to the block.
+  int_range_max tmp;
+  bool changed = false;
   r.set_undefined ();
   for (unsigned i = 0; i < EDGE_COUNT (entry->preds); ++i)
     {
-- 
2.31.1