[PATCH] Remove loop crossing restriction from the backward threader.

[PATCH] Remove loop crossing restriction from the backward threader.

[Aldy Hernandez]

We have much more thorough restrictions, that are shared between both
threader implementations, in the registry.  I've been meaning to
remove the backward threader one, since it's only purpose was reducing
the search space.  Previously there was a small time penalty for its
removal, but with the various patches in the past month, it looks like
the removal is a wash performance wise.

This catches 8 more jump threads in the backward threader in my suite.
Presumably, because we disallowed all loop crossing, whereas the
registry restrictions allow some crossing (if we exit the loop, etc).

OK pending tests on x86-64 Linux?

gcc/ChangeLog:

	* tree-ssa-threadbackward.c
	(back_threader_profitability::profitable_path_p): Remove loop
	crossing restriction.
---
 gcc/tree-ssa-threadbackward.c | 36 ++++++-----------------------------
 1 file changed, 6 insertions(+), 30 deletions(-)

diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index d067c470c38..61aee25d236 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -615,7 +615,6 @@ back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
   int n_insns = 0;
   gimple_stmt_iterator gsi;
   loop_p loop = m_path[0]->loop_father;
-  bool path_crosses_loops = false;
   bool threaded_through_latch = false;
   bool multiway_branch_in_path = false;
   bool threaded_multiway_branch = false;
@@ -634,30 +633,15 @@ back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
 
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, " bb:%i", bb->index);
-      /* Remember, blocks in the path are stored in opposite order
-	 in the PATH array.  The last entry in the array represents
-	 the block with an outgoing edge that we will redirect to the
-	 jump threading path.  Thus we don't care about that block's
-	 loop father, nor how many statements are in that block because
-	 it will not be copied or whether or not it ends in a multiway
-	 branch.  */
+      /* Remember, blocks in the path are stored in opposite order in
+	 the PATH array.  The last entry in the array represents the
+	 block with an outgoing edge that we will redirect to the jump
+	 threading path.  Thus we don't care how many statements are
+	 in that block because it will not be copied or whether or not
+	 it ends in a multiway branch.  */
       if (j < m_path.length () - 1)
 	{
 	  int orig_n_insns = n_insns;
-	  if (bb->loop_father != loop)
-	    {
-	      path_crosses_loops = true;
-
-	      // Dump rest of blocks.
-	      if (dump_file && (dump_flags & TDF_DETAILS))
-		for (j++; j < m_path.length (); j++)
-		  {
-		    bb = m_path[j];
-		    fprintf (dump_file, " bb:%i", bb->index);
-		  }
-	      break;
-	    }
-
 	  /* PHIs in the path will create degenerate PHIS in the
 	     copied path which will then get propagated away, so
 	     looking at just the duplicate path the PHIs would
@@ -776,14 +760,6 @@ back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
 	*creates_irreducible_loop = true;
     }
 
-  if (path_crosses_loops)
-    {
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	fprintf (dump_file, "  FAIL: Jump-thread path not considered: "
-		 "the path crosses loops.\n");
-      return false;
-    }
-
   /* Threading is profitable if the path duplicated is hot but also
      in a case we separate cold path from hot path and permit optimization
      of the hot path later.  Be on the agressive side here. In some testcases,
-- 
2.31.1

[PATCH] Make ranger optional in path_range_query.

[Aldy Hernandez]

All users of path_range_query are currently allocating a gimple_ranger
only to pass it to the query object.  It's tidier to just do it from
path_range_query if no ranger was passed.

Will push pending tests on x86-64 Linux.

gcc/ChangeLog:

	* gimple-range-path.cc (path_range_query::path_range_query): New
	ctor without a ranger.
	(path_range_query::~path_range_query): Free ranger if necessary.
	(path_range_query::range_on_path_entry): Adjust m_ranger for pointer.
	(path_range_query::ssa_range_in_phi): Same.
	(path_range_query::compute_ranges_in_block): Same.
	(path_range_query::compute_imports): Same.
	(path_range_query::compute_ranges): Same.
	(path_range_query::range_of_stmt): Same.
	(path_range_query::compute_outgoing_relations): Same.
	* gimple-range-path.h (class path_range_query): New ctor.
	* tree-ssa-loop-ch.c (ch_base::copy_headers): Remove gimple_ranger
	as path_range_query allocates one.
	* tree-ssa-threadbackward.c (class back_threader): Remove m_ranger.
	(back_threader::~back_threader): Same.
---
 gcc/gimple-range-path.cc      | 43 +++++++++++++++++++++++------------
 gcc/gimple-range-path.h       |  9 ++++++--
 gcc/tree-ssa-loop-ch.c        |  4 +---
 gcc/tree-ssa-threadbackward.c |  5 +---
 4 files changed, 37 insertions(+), 24 deletions(-)

diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index 4843c133e62..b9aceaf2565 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -36,13 +36,24 @@ along with GCC; see the file COPYING3.  If not see
 // Internal construct to help facilitate debugging of solver.
 #define DEBUG_SOLVER (dump_file && (param_threader_debug == THREADER_DEBUG_ALL))
 
-path_range_query::path_range_query (gimple_ranger &ranger, bool resolve)
-  : m_ranger (ranger)
+path_range_query::path_range_query (gimple_ranger *ranger, bool resolve)
+  : m_cache (new ssa_global_cache),
+    m_has_cache_entry (BITMAP_ALLOC (NULL)),
+    m_ranger (ranger),
+    m_resolve (resolve),
+    m_alloced_ranger (false)
 {
-  m_cache = new ssa_global_cache;
-  m_has_cache_entry = BITMAP_ALLOC (NULL);
-  m_resolve = resolve;
-  m_oracle = new path_oracle (ranger.oracle ());
+  m_oracle = new path_oracle (ranger->oracle ());
+}
+
+path_range_query::path_range_query (bool resolve)
+  : m_cache (new ssa_global_cache),
+    m_has_cache_entry (BITMAP_ALLOC (NULL)),
+    m_ranger (new gimple_ranger),
+    m_resolve (resolve),
+    m_alloced_ranger (true)
+{
+  m_oracle = new path_oracle (m_ranger->oracle ());
 }
 
 path_range_query::~path_range_query ()
@@ -50,6 +61,8 @@ path_range_query::~path_range_query ()
   BITMAP_FREE (m_has_cache_entry);
   delete m_cache;
   delete m_oracle;
+  if (m_alloced_ranger)
+    delete m_ranger;
 }
 
 // Mark cache entry for NAME as unused.
@@ -140,7 +153,7 @@ path_range_query::range_on_path_entry (irange &r, tree name)
   gimple *last = last_stmt (entry);
   if (last)
     {
-      if (m_ranger.range_of_expr (r, name, last))
+      if (m_ranger->range_of_expr (r, name, last))
 	return;
       gcc_unreachable ();
     }
@@ -156,7 +169,7 @@ path_range_query::range_on_path_entry (irange &r, tree name)
     {
       edge e = EDGE_PRED (entry, i);
       if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
-	  && m_ranger.range_on_edge (tmp, e, name))
+	  && m_ranger->range_on_edge (tmp, e, name))
 	{
 	  r.union_ (tmp);
 	  changed = true;
@@ -244,7 +257,7 @@ path_range_query::ssa_range_in_phi (irange &r, gphi *phi)
 
   if (at_entry ())
     {
-      if (m_resolve && m_ranger.range_of_expr (r, name, phi))
+      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)>.
@@ -275,7 +288,7 @@ path_range_query::ssa_range_in_phi (irange &r, gphi *phi)
 		  range_on_path_entry (r, arg);
 		else
 		  r.set_varying (TREE_TYPE (name));
-		m_ranger.range_on_edge (tmp, e_in, arg);
+		m_ranger->range_on_edge (tmp, e_in, arg);
 		r.intersect (tmp);
 		return;
 	      }
@@ -370,7 +383,7 @@ path_range_query::compute_ranges_in_block (basic_block bb)
   EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
     {
       tree name = ssa_name (i);
-      gori_compute &g = m_ranger.gori ();
+      gori_compute &g = m_ranger->gori ();
       bitmap exports = g.exports (bb);
 
       if (bitmap_bit_p (exports, i))
@@ -452,7 +465,7 @@ void
 path_range_query::compute_imports (bitmap imports, basic_block exit)
 {
   // Start with the imports from the exit block...
-  bitmap r_imports = m_ranger.gori ().imports (exit);
+  bitmap r_imports = m_ranger->gori ().imports (exit);
   bitmap_copy (imports, r_imports);
 
   auto_vec<tree> worklist (bitmap_count_bits (imports));
@@ -539,7 +552,7 @@ path_range_query::compute_ranges (const vec<basic_block> &path,
 
       if (m_resolve)
 	{
-	  gori_compute &gori = m_ranger.gori ();
+	  gori_compute &gori = m_ranger->gori ();
 	  tree name;
 
 	  // Exported booleans along the path, may help conditionals.
@@ -659,7 +672,7 @@ path_range_query::range_of_stmt (irange &r, gimple *stmt, tree)
   if (m_resolve)
     {
       fold_using_range f;
-      jt_fur_source src (stmt, this, &m_ranger.gori (), m_path);
+      jt_fur_source src (stmt, this, &m_ranger->gori (), m_path);
       if (!f.fold_stmt (r, stmt, src))
 	r.set_varying (type);
     }
@@ -750,7 +763,7 @@ path_range_query::compute_outgoing_relations (basic_block bb, basic_block next)
       else
 	gcc_unreachable ();
 
-      jt_fur_source src (NULL, this, &m_ranger.gori (), m_path);
+      jt_fur_source src (NULL, this, &m_ranger->gori (), m_path);
       src.register_outgoing_edges (cond, r, e0, e1);
     }
 }
diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
index b5a054359ad..ea4864d35ef 100644
--- a/gcc/gimple-range-path.h
+++ b/gcc/gimple-range-path.h
@@ -32,7 +32,8 @@ along with GCC; see the file COPYING3.  If not see
 class path_range_query : public range_query
 {
 public:
-  path_range_query (class gimple_ranger &ranger, bool resolve);
+  path_range_query (class gimple_ranger *ranger, bool resolve = true);
+  path_range_query (bool resolve = true);
   virtual ~path_range_query ();
   void compute_ranges (const vec<basic_block> &, const bitmap_head *imports = NULL);
   void compute_ranges (edge e);
@@ -86,7 +87,7 @@ private:
   auto_vec<basic_block> m_path;
 
   auto_bitmap m_imports;
-  gimple_ranger &m_ranger;
+  gimple_ranger *m_ranger;
   non_null_ref m_non_null;
 
   // Current path position.
@@ -97,6 +98,10 @@ private:
 
   // Set if there were any undefined expressions while pre-calculating path.
   bool m_undefined_path;
+
+  // True if m_ranger was allocated in this class and must be freed at
+  // destruction.
+  bool m_alloced_ranger;
 };
 
 // Return TRUE if NAME is in the import bitmap.
diff --git a/gcc/tree-ssa-loop-ch.c b/gcc/tree-ssa-loop-ch.c
index b87361c3741..566cc275317 100644
--- a/gcc/tree-ssa-loop-ch.c
+++ b/gcc/tree-ssa-loop-ch.c
@@ -384,8 +384,7 @@ ch_base::copy_headers (function *fun)
   auto_vec<loop_p> candidates;
   auto_vec<std::pair<edge, loop_p> > copied;
 
-  gimple_ranger *ranger = new gimple_ranger;
-  path_range_query *query = new path_range_query (*ranger, /*resolve=*/true);
+  path_range_query *query = new path_range_query;
   for (auto loop : loops_list (cfun, 0))
     {
       int initial_limit = param_max_loop_header_insns;
@@ -423,7 +422,6 @@ ch_base::copy_headers (function *fun)
     }
   /* Do not use ranger after we change the IL and not have updated SSA.  */
   delete query;
-  delete ranger;
 
   for (auto loop : candidates)
     {
diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index 61aee25d236..71989c288a7 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -100,7 +100,6 @@ private:
 
   back_threader_registry m_registry;
   back_threader_profitability m_profit;
-  gimple_ranger *m_ranger;
   path_range_query *m_solver;
 
   // Current path being analyzed.
@@ -143,15 +142,13 @@ back_threader::back_threader (function *fun, unsigned flags, bool first)
 
   m_fun = fun;
   m_flags = flags;
-  m_ranger = new gimple_ranger;
-  m_solver = new path_range_query (*m_ranger, flags & BT_RESOLVE);
+  m_solver = new path_range_query (flags & BT_RESOLVE);
   m_last_stmt = NULL;
 }
 
 back_threader::~back_threader ()
 {
   delete m_solver;
-  delete m_ranger;
 
   loop_optimizer_finalize ();
 }
-- 
2.31.1

Re: [PATCH] Remove loop crossing restriction from the backward threader.

[Jeff Law]

On 11/11/2021 10:24 AM, Aldy Hernandez wrote:
> We have much more thorough restrictions, that are shared between both
> threader implementations, in the registry.  I've been meaning to
> remove the backward threader one, since it's only purpose was reducing
> the search space.  Previously there was a small time penalty for its
> removal, but with the various patches in the past month, it looks like
> the removal is a wash performance wise.
>
> This catches 8 more jump threads in the backward threader in my suite.
> Presumably, because we disallowed all loop crossing, whereas the
> registry restrictions allow some crossing (if we exit the loop, etc).
>
> OK pending tests on x86-64 Linux?
>
> gcc/ChangeLog:
>
> 	* tree-ssa-threadbackward.c
> 	(back_threader_profitability::profitable_path_p): Remove loop
> 	crossing restriction.
OK
jeff