[PATCH] Cleanup back_threader::find_path_to_names.

[PATCH] Cleanup back_threader::find_path_to_names.

[Aldy Hernandez]

The main path discovery function was due for a cleanup.  First,
there's a nagging goto and second, my bitmap use was sloppy.  Hopefully
this makes the code easier for others to read.

Regstrapped on x86-64 Linux.  I also made sure there were no difference
in the number of threads with this patch.

No functional changes.

OK?

gcc/ChangeLog:

	* tree-ssa-threadbackward.c (back_threader::find_paths_to_names):
	Remove gotos and other cleanups.
---
 gcc/tree-ssa-threadbackward.c | 52 ++++++++++++++---------------------
 1 file changed, 20 insertions(+), 32 deletions(-)

diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index b7eaff94567..d6a5b0b8da2 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -402,26 +402,18 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting)
 
   m_path.safe_push (bb);
 
+  // Try to resolve the path without looking back.
   if (m_path.length () > 1
-      && !m_profit.profitable_path_p (m_path, m_name, NULL))
+      && (!m_profit.profitable_path_p (m_path, m_name, NULL)
+	  || maybe_register_path ()))
     {
       m_path.pop ();
       m_visited_bbs.remove (bb);
       return false;
     }
 
-  // Try to resolve the path without looking back.
-  if (m_path.length () > 1 && maybe_register_path ())
-    {
-      m_path.pop ();
-      m_visited_bbs.remove (bb);
-      return true;
-    }
-
   auto_bitmap processed;
-  unsigned i;
   bool done = false;
-
   // We use a worklist instead of iterating through the bitmap,
   // because we may add new items in-flight.
   auto_vec<tree> worklist (bitmap_count_bits (interesting));
@@ -433,34 +425,30 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting)
       basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
 
       // Process any names defined in this block.
-      if (def_bb == bb)
+      if (def_bb == bb
+	  && bitmap_set_bit (processed, i)
+	  && resolve_def (name, interesting, worklist))
 	{
-	  bitmap_set_bit (processed, i);
-
-	  if (resolve_def (name, interesting, worklist))
-	    {
-	      done = true;
-	      goto leave_bb;
-	    }
+	  done = true;
+	  break;
 	}
     }
-
   // If there are interesting names not yet processed, keep looking.
-  bitmap_and_compl_into (interesting, processed);
-  if (!bitmap_empty_p (interesting))
+  if (!done)
     {
-      edge_iterator iter;
-      edge e;
-      FOR_EACH_EDGE (e, iter, bb->preds)
-	if ((e->flags & EDGE_ABNORMAL) == 0)
-	  done |= find_paths_to_names (e->src, interesting);
+      bitmap_and_compl_into (interesting, processed);
+      if (!bitmap_empty_p (interesting))
+	{
+	  edge_iterator iter;
+	  edge e;
+	  FOR_EACH_EDGE (e, iter, bb->preds)
+	    if ((e->flags & EDGE_ABNORMAL) == 0)
+	      done |= find_paths_to_names (e->src, interesting);
+	}
     }
 
- leave_bb:
-  bitmap_iterator bi;
-  EXECUTE_IF_SET_IN_BITMAP (processed, 0, i, bi)
-    bitmap_set_bit (interesting, i);
-
+  // Reset things to their original state.
+  bitmap_ior_into (interesting, processed);
   m_path.pop ();
   m_visited_bbs.remove (bb);
   return done;
-- 
2.31.1

Re: [PATCH] Cleanup back_threader::find_path_to_names.

[Jeff Law]

On 11/5/2021 9:09 AM, Aldy Hernandez wrote:
> The main path discovery function was due for a cleanup.  First,
> there's a nagging goto and second, my bitmap use was sloppy.  Hopefully
> this makes the code easier for others to read.
>
> Regstrapped on x86-64 Linux.  I also made sure there were no difference
> in the number of threads with this patch.
>
> No functional changes.
>
> OK?
>
> gcc/ChangeLog:
>
> 	* tree-ssa-threadbackward.c (back_threader::find_paths_to_names):
> 	Remove gotos and other cleanups.
> ---
>   gcc/tree-ssa-threadbackward.c | 52 ++++++++++++++---------------------
>   1 file changed, 20 insertions(+), 32 deletions(-)
>
> diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
> index b7eaff94567..d6a5b0b8da2 100644
> --- a/gcc/tree-ssa-threadbackward.c
> +++ b/gcc/tree-ssa-threadbackward.c
> @@ -402,26 +402,18 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting)
>   
>     m_path.safe_push (bb);
>   
> +  // Try to resolve the path without looking back.
>     if (m_path.length () > 1
> -      && !m_profit.profitable_path_p (m_path, m_name, NULL))
> +      && (!m_profit.profitable_path_p (m_path, m_name, NULL)
> +	  || maybe_register_path ()))
>       {
>         m_path.pop ();
>         m_visited_bbs.remove (bb);
>         return false;
>       }
>   
> -  // Try to resolve the path without looking back.
> -  if (m_path.length () > 1 && maybe_register_path ())
> -    {
> -      m_path.pop ();
> -      m_visited_bbs.remove (bb);
> -      return true;
> -    }
Hmm, note the return values are different in these cases, which you've 
merged to always return false.    I was about to suggest you just kill 
the return value and the cleanups that would enable.  But I see your 
patch uses the return value where we didn't before.

So I think that raises the question, for the recursive calls which set 
"done", does the change in return value, particularly when 
maybe_register_path returns true impact anything?

jeff

Re: [PATCH] Cleanup back_threader::find_path_to_names.

[Aldy Hernandez]

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

On Fri, Nov 5, 2021 at 9:06 PM Jeff Law <jeffreyalaw@gmail.com> wrote:
>
>
>
> On 11/5/2021 9:09 AM, Aldy Hernandez wrote:
> > The main path discovery function was due for a cleanup.  First,
> > there's a nagging goto and second, my bitmap use was sloppy.  Hopefully
> > this makes the code easier for others to read.
> >
> > Regstrapped on x86-64 Linux.  I also made sure there were no difference
> > in the number of threads with this patch.
> >
> > No functional changes.
> >
> > OK?
> >
> > gcc/ChangeLog:
> >
> >       * tree-ssa-threadbackward.c (back_threader::find_paths_to_names):
> >       Remove gotos and other cleanups.
> > ---
> >   gcc/tree-ssa-threadbackward.c | 52 ++++++++++++++---------------------
> >   1 file changed, 20 insertions(+), 32 deletions(-)
> >
> > diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
> > index b7eaff94567..d6a5b0b8da2 100644
> > --- a/gcc/tree-ssa-threadbackward.c
> > +++ b/gcc/tree-ssa-threadbackward.c
> > @@ -402,26 +402,18 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting)
> >
> >     m_path.safe_push (bb);
> >
> > +  // Try to resolve the path without looking back.
> >     if (m_path.length () > 1
> > -      && !m_profit.profitable_path_p (m_path, m_name, NULL))
> > +      && (!m_profit.profitable_path_p (m_path, m_name, NULL)
> > +       || maybe_register_path ()))
> >       {
> >         m_path.pop ();
> >         m_visited_bbs.remove (bb);
> >         return false;
> >       }
> >
> > -  // Try to resolve the path without looking back.
> > -  if (m_path.length () > 1 && maybe_register_path ())
> > -    {
> > -      m_path.pop ();
> > -      m_visited_bbs.remove (bb);
> > -      return true;
> > -    }
> Hmm, note the return values are different in these cases, which you've
> merged to always return false.    I was about to suggest you just kill
> the return value and the cleanups that would enable.  But I see your
> patch uses the return value where we didn't before.

Woah, good catch.

It looks like the return value is no longer needed, so it can indeed
be killed.  This was left over from when resolve_phi() didn't resolve
all incoming paths, but that's no longer the case.  Once we exit
find_path_to_names, all paths have been explored and there's nothing
to do.

OK pending tests?
Aldy

>
> So I think that raises the question, for the recursive calls which set
> "done", does the change in return value, particularly when
> maybe_register_path returns true impact anything?
>
> jeff
>

[-- Attachment #2: 0001-Cleanup-back_threader-find_path_to_names.patch --]
[-- Type: text/x-patch, Size: 4335 bytes --]

From 332495ab6bf364bac59d968dfdfe7d8d6a9f5dcf Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <aldyh@redhat.com>
Date: Thu, 4 Nov 2021 19:44:15 +0100
Subject: [PATCH] Cleanup back_threader::find_path_to_names.

The main path discovery function was due for a cleanup.  First,
there's a nagging goto and second, my bitmap use was sloppy.  Hopefully
this makes the code easier for others to read.

Regstrapped on x86-64 Linux.  I also made sure there were no difference
in the number of threads with this patch.

No functional changes.

gcc/ChangeLog:

	* tree-ssa-threadbackward.c (back_threader::find_paths_to_names):
	Remove gotos and other cleanups.
---
 gcc/tree-ssa-threadbackward.c | 65 +++++++++++++----------------------
 1 file changed, 24 insertions(+), 41 deletions(-)

diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index b7eaff94567..0085ad01cdc 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -89,7 +89,7 @@ private:
   void find_paths (basic_block bb, tree name);
   bool debug_counter ();
   edge maybe_register_path ();
-  bool find_paths_to_names (basic_block bb, bitmap imports);
+  void find_paths_to_names (basic_block bb, bitmap imports);
   bool resolve_def (tree name, bitmap interesting, vec<tree> &worklist);
   void resolve_phi (gphi *phi, bitmap imports);
   edge find_taken_edge (const vec<basic_block> &path);
@@ -388,40 +388,28 @@ back_threader::resolve_def (tree name, bitmap interesting, vec<tree> &worklist)
 // Find jump threading paths to any of the SSA names in the
 // INTERESTING bitmap, and register any such paths.
 //
-// Return TRUE if no further processing past this block is necessary.
-// This is because we've either registered a path, or because there is
-// nothing of interesting beyond this block.
-//
 // BB is the current path being processed.
 
-bool
+void
 back_threader::find_paths_to_names (basic_block bb, bitmap interesting)
 {
   if (m_visited_bbs.add (bb))
-    return true;
+    return;
 
   m_path.safe_push (bb);
 
-  if (m_path.length () > 1
-      && !m_profit.profitable_path_p (m_path, m_name, NULL))
-    {
-      m_path.pop ();
-      m_visited_bbs.remove (bb);
-      return false;
-    }
-
   // Try to resolve the path without looking back.
-  if (m_path.length () > 1 && maybe_register_path ())
+  if (m_path.length () > 1
+      && (!m_profit.profitable_path_p (m_path, m_name, NULL)
+	  || maybe_register_path ()))
     {
       m_path.pop ();
       m_visited_bbs.remove (bb);
-      return true;
+      return;
     }
 
   auto_bitmap processed;
-  unsigned i;
   bool done = false;
-
   // We use a worklist instead of iterating through the bitmap,
   // because we may add new items in-flight.
   auto_vec<tree> worklist (bitmap_count_bits (interesting));
@@ -433,37 +421,32 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting)
       basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
 
       // Process any names defined in this block.
-      if (def_bb == bb)
+      if (def_bb == bb
+	  && bitmap_set_bit (processed, i)
+	  && resolve_def (name, interesting, worklist))
 	{
-	  bitmap_set_bit (processed, i);
-
-	  if (resolve_def (name, interesting, worklist))
-	    {
-	      done = true;
-	      goto leave_bb;
-	    }
+	  done = true;
+	  break;
 	}
     }
-
   // If there are interesting names not yet processed, keep looking.
-  bitmap_and_compl_into (interesting, processed);
-  if (!bitmap_empty_p (interesting))
+  if (!done)
     {
-      edge_iterator iter;
-      edge e;
-      FOR_EACH_EDGE (e, iter, bb->preds)
-	if ((e->flags & EDGE_ABNORMAL) == 0)
-	  done |= find_paths_to_names (e->src, interesting);
+      bitmap_and_compl_into (interesting, processed);
+      if (!bitmap_empty_p (interesting))
+	{
+	  edge_iterator iter;
+	  edge e;
+	  FOR_EACH_EDGE (e, iter, bb->preds)
+	    if ((e->flags & EDGE_ABNORMAL) == 0)
+	      find_paths_to_names (e->src, interesting);
+	}
     }
 
- leave_bb:
-  bitmap_iterator bi;
-  EXECUTE_IF_SET_IN_BITMAP (processed, 0, i, bi)
-    bitmap_set_bit (interesting, i);
-
+  // Reset things to their original state.
+  bitmap_ior_into (interesting, processed);
   m_path.pop ();
   m_visited_bbs.remove (bb);
-  return done;
 }
 
 // Search backwards from BB looking for paths where the final
-- 
2.31.1

Re: [PATCH] Cleanup back_threader::find_path_to_names.

[Jeff Law]

On 11/5/2021 2:44 PM, Aldy Hernandez wrote:
> On Fri, Nov 5, 2021 at 9:06 PM Jeff Law <jeffreyalaw@gmail.com> wrote:
>>
>>
>> On 11/5/2021 9:09 AM, Aldy Hernandez wrote:
>>> The main path discovery function was due for a cleanup.  First,
>>> there's a nagging goto and second, my bitmap use was sloppy.  Hopefully
>>> this makes the code easier for others to read.
>>>
>>> Regstrapped on x86-64 Linux.  I also made sure there were no difference
>>> in the number of threads with this patch.
>>>
>>> No functional changes.
>>>
>>> OK?
>>>
>>> gcc/ChangeLog:
>>>
>>>        * tree-ssa-threadbackward.c (back_threader::find_paths_to_names):
>>>        Remove gotos and other cleanups.
I should have looked closer.  The recursive call happens after you have 
already tested "done", so yea, removing the return value is trivial.

V2 is OK for the turnk.


Jeff