[PATCH] tree-optimization/103188 - avoid running ranger on not-up-to-date SSA

[PATCH] tree-optimization/103188 - avoid running ranger on not-up-to-date SSA

[Richard Biener]

The following splits loop header copying into an analysis phase
that uses ranger and a transform phase that can do without to avoid
running ranger on IL that has SSA form not updated.

Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.

2021-11-11  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/103188
	* tree-ssa-loop-ch.c (should_duplicate_loop_header_p):
	Remove query parameter, split out check for size
	optimization.
	(ch_base::m_ranger, cb_base::m_query): Remove.
	(ch_base::copy_headers): Split processing loop into
	analysis around which we allocate and use ranger and
	transform where we do not.
	(pass_ch::execute): Do not allocate/free ranger here.
	(pass_ch_vect::execute): Likewise.

	* gcc.dg/torture/pr103188.c: New testcase.
---
 gcc/testsuite/gcc.dg/torture/pr103188.c | 38 +++++++++++++
 gcc/tree-ssa-loop-ch.c                  | 72 ++++++++++++++-----------
 2 files changed, 78 insertions(+), 32 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/torture/pr103188.c

diff --git a/gcc/testsuite/gcc.dg/torture/pr103188.c b/gcc/testsuite/gcc.dg/torture/pr103188.c
new file mode 100644
index 00000000000..0412f6f9b79
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr103188.c
@@ -0,0 +1,38 @@
+/* { dg-do compile } */
+
+int a, b, c, d = 10, e = 1, f, g, h, i;
+int main()
+{
+  int j = -1;
+k:
+  h = c;
+l:
+  c = ~c;
+  if (e)
+  m:
+    a = 0;
+  if (j > 1)
+    goto m;
+  if (!e)
+    goto l;
+  if (c)
+    goto p;
+n:
+  goto m;
+o:
+  if (f) {
+    if (g)
+      goto k;
+    j = 0;
+  p:
+    if (d)
+      goto o;
+    goto n;
+  }
+  if (i)
+    goto l;
+  for (; a < 1; a++)
+    while (a > d)
+      b++;
+  return 0;
+}
diff --git a/gcc/tree-ssa-loop-ch.c b/gcc/tree-ssa-loop-ch.c
index c7d86d751d4..0cee38159fb 100644
--- a/gcc/tree-ssa-loop-ch.c
+++ b/gcc/tree-ssa-loop-ch.c
@@ -69,26 +69,12 @@ entry_loop_condition_is_static (class loop *l, path_range_query *query)
 
 static bool
 should_duplicate_loop_header_p (basic_block header, class loop *loop,
-				int *limit, path_range_query *query)
+				int *limit)
 {
   gimple_stmt_iterator bsi;
 
   gcc_assert (!header->aux);
 
-  /* Avoid loop header copying when optimizing for size unless we can
-     determine that the loop condition is static in the first
-     iteration.  */
-  if (optimize_loop_for_size_p (loop)
-      && !loop->force_vectorize
-      && !entry_loop_condition_is_static (loop, query))
-    {
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	fprintf (dump_file,
-		 "  Not duplicating bb %i: optimizing for size.\n",
-		 header->index);
-      return false;
-    }
-
   gcc_assert (EDGE_COUNT (header->succs) > 0);
   if (single_succ_p (header))
     {
@@ -223,8 +209,6 @@ should_duplicate_loop_header_p (basic_block header, class loop *loop,
       return false;
     }
 
-  if (dump_file && (dump_flags & TDF_DETAILS))
-    fprintf (dump_file, "    Will duplicate bb %i\n", header->index); 
   return true;
 }
 
@@ -289,9 +273,6 @@ class ch_base : public gimple_opt_pass
 
   /* Return true to copy headers of LOOP or false to skip.  */
   virtual bool process_loop_p (class loop *loop) = 0;
-
-  gimple_ranger *m_ranger = NULL;
-  path_range_query *m_query = NULL;
 };
 
 const pass_data pass_data_ch =
@@ -386,8 +367,11 @@ ch_base::copy_headers (function *fun)
   copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
   bbs_size = n_basic_blocks_for_fn (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);
   for (auto loop : loops_list (cfun, 0))
     {
       int initial_limit = param_max_loop_header_insns;
@@ -406,6 +390,37 @@ ch_base::copy_headers (function *fun)
 	  || !process_loop_p (loop))
 	continue;
 
+      /* Avoid loop header copying when optimizing for size unless we can
+	 determine that the loop condition is static in the first
+	 iteration.  */
+      if (optimize_loop_for_size_p (loop)
+	  && !loop->force_vectorize
+	  && !entry_loop_condition_is_static (loop, query))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file,
+		     "  Not duplicating bb %i: optimizing for size.\n",
+		     header->index);
+	  continue;
+	}
+
+      if (should_duplicate_loop_header_p (header, loop, &remaining_limit))
+	candidates.safe_push (loop);
+    }
+  /* Do not use ranger after we change the IL and not have updated SSA.  */
+  delete query;
+  delete ranger;
+
+  for (auto loop : candidates)
+    {
+      int initial_limit = param_max_loop_header_insns;
+      int remaining_limit = initial_limit;
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,
+		 "Copying headers of loop %i\n", loop->num);
+
+      header = loop->header;
+
       /* Iterate the header copying up to limit; this takes care of the cases
 	 like while (a && b) {...}, where we want to have both of the conditions
 	 copied.  TODO -- handle while (a || b) - like cases, by not requiring
@@ -414,9 +429,11 @@ ch_base::copy_headers (function *fun)
 
       exit = NULL;
       n_bbs = 0;
-      while (should_duplicate_loop_header_p (header, loop, &remaining_limit,
-					     m_query))
+      while (should_duplicate_loop_header_p (header, loop, &remaining_limit))
 	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "    Will duplicate bb %i\n", header->index);
+
 	  /* Find a successor of header that is inside a loop; i.e. the new
 	     header after the condition is copied.  */
 	  if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
@@ -552,13 +569,9 @@ pass_ch::execute (function *fun)
   loop_optimizer_init (LOOPS_HAVE_PREHEADERS
 		       | LOOPS_HAVE_SIMPLE_LATCHES
 		       | LOOPS_HAVE_RECORDED_EXITS);
-  m_ranger = new gimple_ranger;
-  m_query = new path_range_query (*m_ranger, /*resolve=*/true);
 
   unsigned int res = copy_headers (fun);
 
-  delete m_query;
-  delete m_ranger;
   loop_optimizer_finalize ();
   return res;
 }
@@ -570,12 +583,7 @@ pass_ch::execute (function *fun)
 unsigned int
 pass_ch_vect::execute (function *fun)
 {
-  m_ranger = new gimple_ranger;
-  m_query = new path_range_query (*m_ranger, /*resolve=*/true);
-  unsigned int res = copy_headers (fun);
-  delete m_query;
-  delete m_ranger;
-  return res;
+  return copy_headers (fun);
 }
 
 /* Apply header copying according to a very simple test of do-while shape.  */
-- 
2.31.1

Re: [PATCH] tree-optimization/103188 - avoid running ranger on not-up-to-date SSA

[Aldy Hernandez]

Thanks for doing this!

>
> +  gimple_ranger *ranger = new gimple_ranger;
> +  path_range_query *query = new path_range_query (*ranger, /*resolve=*/true);

Hmmm, it looks like both clients are now instantiating a gimple_ranger
just so they can pass it down to the path_range_query.  Maybe we
should  have another ctor with just:

path_range_query (bool resolve);

...and have it allocate its own ranger.

Does this seem like a useful improvement?  For that matter, resolve
should default to true.  The option is only there so the backward
threader can run in a "light" mode (early threading, etc).

Aldy

Re: [PATCH] tree-optimization/103188 - avoid running ranger on not-up-to-date SSA

[Richard Biener]

On November 11, 2021 5:43:48 PM GMT+01:00, Aldy Hernandez <aldyh@redhat.com> wrote:
>Thanks for doing this!
>
>>
>> +  gimple_ranger *ranger = new gimple_ranger;
>> +  path_range_query *query = new path_range_query (*ranger, /*resolve=*/true);
>
>Hmmm, it looks like both clients are now instantiating a gimple_ranger
>just so they can pass it down to the path_range_query.  Maybe we
>should  have another ctor with just:
>
>path_range_query (bool resolve);
>
>...and have it allocate its own ranger.
>
>Does this seem like a useful improvement?  For that matter, resolve
>should default to true.  The option is only there so the backward
>threader can run in a "light" mode (early threading, etc).

I've just copied from the two duplicate instances of this, so I don't know nothing here ;) 

Richard. 
>
>Aldy
>

Re: [PATCH] tree-optimization/103188 - avoid running ranger on not-up-to-date SSA

[Aldy Hernandez]

[-- Attachment #1: Type: text/plain, Size: 823 bytes --]

Like this.  It simplifies both loop-ch and the threader.

I'll push this pending tests unless someone objects.

On Thu, Nov 11, 2021 at 5:43 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> Thanks for doing this!
>
> >
> > +  gimple_ranger *ranger = new gimple_ranger;
> > +  path_range_query *query = new path_range_query (*ranger, /*resolve=*/true);
>
> Hmmm, it looks like both clients are now instantiating a gimple_ranger
> just so they can pass it down to the path_range_query.  Maybe we
> should  have another ctor with just:
>
> path_range_query (bool resolve);
>
> ...and have it allocate its own ranger.
>
> Does this seem like a useful improvement?  For that matter, resolve
> should default to true.  The option is only there so the backward
> threader can run in a "light" mode (early threading, etc).
>
> Aldy

[-- Attachment #2: 0002-Make-ranger-optional-in-path_range_query.patch --]
[-- Type: text/x-patch, Size: 8552 bytes --]

From c446a8c3110b6629e6dc6897028312ed760440df Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <aldyh@redhat.com>
Date: Thu, 11 Nov 2021 18:06:50 +0100
Subject: [PATCH] Make ranger optional in path_range_query.

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.

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