[PATCH] Return NULL for maybe_register_path when unprofitable.

[PATCH] Return NULL for maybe_register_path when unprofitable.

[Aldy Hernandez]

This is a minor cleanup for maybe_register_path to return NULL when
the path is unprofitable.  It is needed for a follow-up patch to
generate better dumps from the threader.

There is no change in behavior, since the only call to this function
bails on !profitable_path_p.

Tested on x86-64 Linux.

OK?

gcc/ChangeLog:

	* tree-ssa-threadbackward.c (back_threader::maybe_register_path):
	Return NULL when unprofitable.
---
 gcc/tree-ssa-threadbackward.c | 38 ++++++++++++++++++-----------------
 1 file changed, 20 insertions(+), 18 deletions(-)

diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index f9485bf9046..84249544760 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -186,11 +186,10 @@ back_threader::debug_counter ()
   return true;
 }
 
-// Register the current path for jump threading if it's profitable to
-// do so.
 //
-// Return the known taken edge out of the path, even if the path was
-// not registered, or NULL if the taken edge could not be determined.
+// Return NULL if it is unprofitable to thread this path, or the
+// outgoing edge is unknown.  Return UNREACHABLE_EDGE if the path is
+// unreachable.
 
 edge
 back_threader::maybe_register_path ()
@@ -199,23 +198,26 @@ back_threader::maybe_register_path ()
 
   if (taken_edge && taken_edge != UNREACHABLE_EDGE)
     {
-      // Avoid circular paths.
       if (m_visited_bbs.contains (taken_edge->dest))
-	return UNREACHABLE_EDGE;
-
-      bool irreducible = false;
-      bool profitable
-	= m_profit.profitable_path_p (m_path, m_name, taken_edge, &irreducible);
-
-      if (profitable)
 	{
-	  if (!debug_counter ())
-	    return NULL;
-
-	  m_registry.register_path (m_path, taken_edge);
+	  // Avoid circular paths by indicating there is nothing to
+	  // see in this direction.
+	  taken_edge = UNREACHABLE_EDGE;
+	}
+      else
+	{
+	  bool irreducible = false;
+	  if (m_profit.profitable_path_p (m_path, m_name, taken_edge,
+					  &irreducible)
+	      && debug_counter ())
+	    {
+	      m_registry.register_path (m_path, taken_edge);
 
-	  if (irreducible)
-	    vect_free_loop_info_assumptions (m_path[0]->loop_father);
+	      if (irreducible)
+		vect_free_loop_info_assumptions (m_path[0]->loop_father);
+	    }
+	  else
+	    taken_edge = NULL;
 	}
     }
   return taken_edge;
-- 
2.31.1

[PATCH] Dump details of an attempt to register a jump threading path.

[Aldy Hernandez]

The goal with these sets of patches is to improve the detailed dumps for
the threader, as I hope we eventually reach the point when I'm not
the only one looking at these dumps ;-).

This patch adds candidate paths to the detailed threading dumps to make it
easier to see the decisions the threader makes.  With it we can now
grep for the discovery logic in action:

$ grep ^path: a.ii.*thread*
a.ii.034t.ethread:path: 4->5->xx REJECTED
a.ii.034t.ethread:path: 3->5->8 SUCCESS
a.ii.034t.ethread:path: 4->5->6 SUCCESS
a.ii.034t.ethread:path: 0->2->xx REJECTED
a.ii.034t.ethread:path: 0->2->xx REJECTED
...
...
a.ii.111t.threadfull1:path: 14->22->23->xx REJECTED (unreachable)
a.ii.111t.threadfull1:path: 15->22->23->xx REJECTED (unreachable)
a.ii.111t.threadfull1:path: 16->22->23->xx REJECTED (unreachable)

In addition to this, if --param=threader-debug=all is used, one can see
the entire chain of events leading up to the ultimate threading
decision:

==============================================
path_range_query: compute_ranges for path: 2->5
 Registering killing_def (path_oracle) _3
 Registering killing_def (path_oracle) _1
range_defined_in_block (BB2) for _1 is _Bool VARYING
 Registering killing_def (path_oracle) _2
range_defined_in_block (BB2) for _2 is _Bool VARYING
range_defined_in_block (BB2) for _3 is _Bool VARYING
outgoing_edge_range_p for b_10(D) on edge 2->5 is int VARYING
...
... [BBs and gimple along path]
...
path: 2->5->xx REJECTED

Tested on x86-64 Linux.

OK?

gcc/ChangeLog:

	* tree-ssa-threadbackward.c
	(back_threader::maybe_register_path_dump): New.
	(back_threader::maybe_register_path): Call maybe_register_path_dump.
---
 gcc/tree-ssa-threadbackward.c | 34 ++++++++++++++++++++++++++++++++++
 1 file changed, 34 insertions(+)

diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index 84249544760..74b5f361f45 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -89,6 +89,7 @@ private:
   void find_paths (basic_block bb, tree name);
   bool debug_counter ();
   edge maybe_register_path ();
+  void maybe_register_path_dump (edge taken_edge);
   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);
@@ -186,6 +187,35 @@ back_threader::debug_counter ()
   return true;
 }
 
+// Dump details of an attempt to register a path.
+
+void
+back_threader::maybe_register_path_dump (edge taken)
+{
+  if (m_path.is_empty ())
+    return;
+
+  fprintf (dump_file, "path: ");
+
+  for (unsigned i = m_path.length (); i > 0; --i)
+    {
+      basic_block bb = m_path[i - 1];
+      fprintf (dump_file, "%d", bb->index);
+      if (i > 1)
+	fprintf (dump_file, "->");
+    }
+  fprintf (dump_file, "->");
+
+  if (taken == UNREACHABLE_EDGE)
+    fprintf (dump_file, "xx REJECTED (unreachable)\n");
+  else if (taken)
+    fprintf (dump_file, "%d SUCCESS\n", taken->dest->index);
+  else
+    fprintf (dump_file, "xx REJECTED\n");
+}
+
+// If an outgoing edge can be determined out of the current path,
+// register it for jump threading and return the taken edge.
 //
 // Return NULL if it is unprofitable to thread this path, or the
 // outgoing edge is unknown.  Return UNREACHABLE_EDGE if the path is
@@ -220,6 +250,10 @@ back_threader::maybe_register_path ()
 	    taken_edge = NULL;
 	}
     }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    maybe_register_path_dump (taken_edge);
+
   return taken_edge;
 }
 
-- 
2.31.1

Re: [PATCH] Dump details of an attempt to register a jump threading path.

[Jeff Law]

On 11/9/2021 4:15 AM, Aldy Hernandez wrote:
> The goal with these sets of patches is to improve the detailed dumps for
> the threader, as I hope we eventually reach the point when I'm not
> the only one looking at these dumps ;-).
>
> This patch adds candidate paths to the detailed threading dumps to make it
> easier to see the decisions the threader makes.  With it we can now
> grep for the discovery logic in action:
>
> $ grep ^path: a.ii.*thread*
> a.ii.034t.ethread:path: 4->5->xx REJECTED
> a.ii.034t.ethread:path: 3->5->8 SUCCESS
> a.ii.034t.ethread:path: 4->5->6 SUCCESS
> a.ii.034t.ethread:path: 0->2->xx REJECTED
> a.ii.034t.ethread:path: 0->2->xx REJECTED
> ...
> ...
> a.ii.111t.threadfull1:path: 14->22->23->xx REJECTED (unreachable)
> a.ii.111t.threadfull1:path: 15->22->23->xx REJECTED (unreachable)
> a.ii.111t.threadfull1:path: 16->22->23->xx REJECTED (unreachable)
>
> In addition to this, if --param=threader-debug=all is used, one can see
> the entire chain of events leading up to the ultimate threading
> decision:
>
> ==============================================
> path_range_query: compute_ranges for path: 2->5
>   Registering killing_def (path_oracle) _3
>   Registering killing_def (path_oracle) _1
> range_defined_in_block (BB2) for _1 is _Bool VARYING
>   Registering killing_def (path_oracle) _2
> range_defined_in_block (BB2) for _2 is _Bool VARYING
> range_defined_in_block (BB2) for _3 is _Bool VARYING
> outgoing_edge_range_p for b_10(D) on edge 2->5 is int VARYING
> ...
> ... [BBs and gimple along path]
> ...
> path: 2->5->xx REJECTED
>
> Tested on x86-64 Linux.
>
> OK?
>
> gcc/ChangeLog:
>
> 	* tree-ssa-threadbackward.c
> 	(back_threader::maybe_register_path_dump): New.
> 	(back_threader::maybe_register_path): Call maybe_register_path_dump.
OK
jeff

Re: [PATCH] Return NULL for maybe_register_path when unprofitable.

[Jeff Law]

On 11/9/2021 4:15 AM, Aldy Hernandez wrote:
> This is a minor cleanup for maybe_register_path to return NULL when
> the path is unprofitable.  It is needed for a follow-up patch to
> generate better dumps from the threader.
>
> There is no change in behavior, since the only call to this function
> bails on !profitable_path_p.
>
> Tested on x86-64 Linux.
>
> OK?
>
> gcc/ChangeLog:
>
> 	* tree-ssa-threadbackward.c (back_threader::maybe_register_path):
> 	Return NULL when unprofitable.
OK
jeff