More backwards/FSM jump thread refactoring and extension

More backwards/FSM jump thread refactoring and extension

[Jeff Law]

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

Here's the next patch which does a bit more refactoring in the backwards 
jump threader and extends the backwards jump threader to handle simple 
copies and constant initializations.

The extension isn't all that useful right now -- while it does fire 
often during bootstraps, its doing so for cases that would be caught 
slightly later (within the same pass).  As a result there's no changes 
in the testsuite.

The extension becomes useful in an upcoming patch where the backwards 
threader is disentangled from DOM/VRP entirely.  In that mode the 
threader can't depend on cprop to have eliminated the copies and 
propagated as many constants as possible into PHI arguments.

Bootstrapped and regression tested on x86_64 linux.  Installing on the 
trunk.

Jeff




[-- Attachment #2: P --]
[-- Type: text/plain, Size: 6014 bytes --]

commit 913a4b1f209105a774789311094e90986db322fb
Author: Jeff Law <law@torsion.usersys.redhat.com>
Date:   Tue May 24 11:56:50 2016 -0400

    	* tree-ssa-threadbackwards.c (convert_and_register_jump_thread_path):
    	New function, extracted from...
    	(fsm_find_control_statement_thread_paths): Here.  Use the new function.
    	Allow simple copies and constant initializations in the SSA chain.

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 2b20cc8..9442109 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,10 @@
+2016-05-24  Jeff Law  <law@redhat.com>
+
+	* tree-ssa-threadbackwards.c (convert_and_register_jump_thread_path):
+	New function, extracted from...
+	(fsm_find_control_statement_thread_paths): Here.  Use the new function.
+	Allow simple copies and constant initializations in the SSA chain.
+
 2016-05-24  Marek Polacek  <polacek@redhat.com>
 
 	PR c/71249
diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index 73ab4ea..4d0fd9c 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -356,6 +356,44 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
   return taken_edge;
 }
 
+/* PATH is vector of blocks forming a jump threading path in reverse
+   order.  TAKEN_EDGE is the edge taken from path[0].
+
+   Convert that path into the form used by register_jump_thread and
+   register the path.   */
+
+static void
+convert_and_register_jump_thread_path (vec<basic_block, va_gc> *&path,
+				       edge taken_edge)
+{
+  vec<jump_thread_edge *> *jump_thread_path = new vec<jump_thread_edge *> ();
+
+  /* Record the edges between the blocks in PATH.  */
+  for (unsigned int j = 0; j < path->length () - 1; j++)
+    {
+      basic_block bb1 = (*path)[path->length () - j - 1];
+      basic_block bb2 = (*path)[path->length () - j - 2];
+      if (bb1 == bb2)
+	continue;
+
+      edge e = find_edge (bb1, bb2);
+      gcc_assert (e);
+      jump_thread_edge *x = new jump_thread_edge (e, EDGE_FSM_THREAD);
+      jump_thread_path->safe_push (x);
+    }
+
+  /* Add the edge taken when the control variable has value ARG.  */
+  jump_thread_edge *x
+    = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
+  jump_thread_path->safe_push (x);
+
+  register_jump_thread (jump_thread_path);
+  --max_threaded_paths;
+
+  /* Remove BBI from the path.  */
+  path->pop ();
+}
+
 /* We trace the value of the SSA_NAME NAME back through any phi nodes looking
    for places where it gets a constant value and save the path.  Stop after
    having recorded MAX_PATHS jump threading paths.  */
@@ -377,24 +415,30 @@ fsm_find_control_statement_thread_paths (tree name,
   if (var_bb == NULL)
     return;
 
-  /* For the moment we assume that an SSA chain only contains phi nodes, and
-     eventually one of the phi arguments will be an integer constant.  In the
-     future, this could be extended to also handle simple assignments of
-     arithmetic operations.  */
+  /* We allow the SSA chain to contains PHIs and simple copies and constant
+     initializations.  */
   if (gimple_code (def_stmt) != GIMPLE_PHI
-      || (gimple_phi_num_args (def_stmt)
+      && gimple_code (def_stmt) != GIMPLE_ASSIGN)
+    return;
+
+  if (gimple_code (def_stmt) == GIMPLE_PHI
+      && (gimple_phi_num_args (def_stmt)
 	  >= (unsigned) PARAM_VALUE (PARAM_FSM_MAXIMUM_PHI_ARGUMENTS)))
     return;
 
+  if (gimple_code (def_stmt) == GIMPLE_ASSIGN
+      && gimple_assign_rhs_code (def_stmt) != INTEGER_CST
+      && gimple_assign_rhs_code (def_stmt) != SSA_NAME)
+    return;
+
   /* Avoid infinite recursion.  */
   if (visited_bbs->add (var_bb))
     return;
 
-  gphi *phi = as_a <gphi *> (def_stmt);
   int next_path_length = 0;
   basic_block last_bb_in_path = path->last ();
 
-  if (loop_containing_stmt (phi)->header == gimple_bb (phi))
+  if (loop_containing_stmt (def_stmt)->header == gimple_bb (def_stmt))
     {
       /* Do not walk through more than one loop PHI node.  */
       if (seen_loop_phi)
@@ -469,9 +513,9 @@ fsm_find_control_statement_thread_paths (tree name,
 
   /* Iterate over the arguments of PHI.  */
   unsigned int i;
-  if (gimple_phi_num_args (phi)
-      < (unsigned) PARAM_VALUE (PARAM_FSM_MAXIMUM_PHI_ARGUMENTS))
+  if (gimple_code (def_stmt) == GIMPLE_PHI)
     {
+      gphi *phi = as_a <gphi *> (def_stmt);
       for (i = 0; i < gimple_phi_num_args (phi); i++)
 	{
 	  tree arg = gimple_phi_arg_def (phi, i);
@@ -500,32 +544,23 @@ fsm_find_control_statement_thread_paths (tree name,
 	     into the canonical form and register it.  */
 	  edge taken_edge = profitable_jump_thread_path (path, bbi, name, arg);
 	  if (taken_edge)
-	    {
-	      vec<jump_thread_edge *> *jump_thread_path
-		= new vec<jump_thread_edge *> ();
-
-	      /* Record the edges between the blocks in PATH.  */
-	      for (unsigned int j = 0; j < path->length () - 1; j++)
-		{
-		  edge e = find_edge ((*path)[path->length () - j - 1],
-				      (*path)[path->length () - j - 2]);
-		  gcc_assert (e);
-		  jump_thread_edge *x
-		    = new jump_thread_edge (e, EDGE_FSM_THREAD);
-		  jump_thread_path->safe_push (x);
-		}
-
-	      /* Add the edge taken when the control variable has value ARG.  */
-	      jump_thread_edge *x
-		= new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
-	      jump_thread_path->safe_push (x);
+	    convert_and_register_jump_thread_path (path, taken_edge);
+	}
+    }
+  else if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
+    {
+      tree arg = gimple_assign_rhs1 (def_stmt);
 
-	      register_jump_thread (jump_thread_path);
-	      --max_threaded_paths;
+      if (TREE_CODE (arg) == SSA_NAME)
+	fsm_find_control_statement_thread_paths (arg, visited_bbs,
+						 path, seen_loop_phi);
 
-	      /* Remove BBI from the path.  */
-	      path->pop ();
-	    }
+      else
+	{
+	  edge taken_edge = profitable_jump_thread_path (path, var_bb,
+						     name, arg);
+	  if (taken_edge)
+	    convert_and_register_jump_thread_path (path, taken_edge);
 	}
     }
 

Re: More backwards/FSM jump thread refactoring and extension

[Trevor Saunders]

On Tue, May 24, 2016 at 10:58:18AM -0600, Jeff Law wrote:
> --- a/gcc/tree-ssa-threadbackward.c
> +++ b/gcc/tree-ssa-threadbackward.c
> @@ -356,6 +356,44 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
>    return taken_edge;
>  }
>  
> +/* PATH is vector of blocks forming a jump threading path in reverse
> +   order.  TAKEN_EDGE is the edge taken from path[0].
> +
> +   Convert that path into the form used by register_jump_thread and
> +   register the path.   */
> +
> +static void
> +convert_and_register_jump_thread_path (vec<basic_block, va_gc> *&path,

is there a reason that isn't vec<basic_block, va_gc> * instead of
vec<basic_block> *&? It seems like that's just useless indirection, and
allowing this function to be able to change more than it needs.

> +				       edge taken_edge)
> +{
> +  vec<jump_thread_edge *> *jump_thread_path = new vec<jump_thread_edge *> ();

Its not new, but I'm always a little sad to see something that's only
sizeof(void *) big be malloced on its own.

Trev

Re: More backwards/FSM jump thread refactoring and extension

[Jeff Law]

On 05/24/2016 06:03 PM, Trevor Saunders wrote:
> On Tue, May 24, 2016 at 10:58:18AM -0600, Jeff Law wrote:
>> --- a/gcc/tree-ssa-threadbackward.c
>> +++ b/gcc/tree-ssa-threadbackward.c
>> @@ -356,6 +356,44 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
>>    return taken_edge;
>>  }
>>
>> +/* PATH is vector of blocks forming a jump threading path in reverse
>> +   order.  TAKEN_EDGE is the edge taken from path[0].
>> +
>> +   Convert that path into the form used by register_jump_thread and
>> +   register the path.   */
>> +
>> +static void
>> +convert_and_register_jump_thread_path (vec<basic_block, va_gc> *&path,
>
> is there a reason that isn't vec<basic_block, va_gc> * instead of
> vec<basic_block> *&? It seems like that's just useless indirection, and
> allowing this function to be able to change more than it needs.
I didn't try to clean up anything of that nature.  It's a good follow-up 
item though.  Thanks for pointing it out.

>
>> +				       edge taken_edge)
>> +{
>> +  vec<jump_thread_edge *> *jump_thread_path = new vec<jump_thread_edge *> ();
>
> Its not new, but I'm always a little sad to see something that's only
> sizeof(void *) big be malloced on its own.
I wouldn't be terribly surprised if the backwards/FSM threader drops the 
jump_thread_edge representation after I pull it out of the main threader 
into its own pass.

jeff