[3/4] Use RPO VN from unrolling

Message ID alpine.LSU.2.20.1808011630030.16707@zhemvz.fhfr.qr
State New
Headers show
Series
  • RPO style value-numbering
Related show

Commit Message

Richard Biener Aug. 1, 2018, 2:31 p.m.
This should be 4/4 but I have the main patch on top, so...

This uses the region-based VN from GIMPLE unrolling which means
we better approximate the effects optimizations on unrolled inner
loops when evaluating whether to unroll outer ones.

	* tree-ssa-loop-ivcanon.c: Include tree-ssa-sccvn.h.
	(propagate_constants_for_unrolling): Remove.
	(tree_unroll_loops_completely): Perform value-numbering
	on the unrolled bodies loop parent.

	* gfortran.dg/reassoc_4.f: Change max-completely-peeled-insns
	param to current default.
---
 gcc/testsuite/gfortran.dg/reassoc_4.f |  2 +-
 gcc/tree-ssa-loop-ivcanon.c           | 57 ++++++-----------------------------
 2 files changed, 10 insertions(+), 49 deletions(-)

-- 
2.13.7

Comments

Richard Sandiford Aug. 1, 2018, 2:58 p.m. | #1
Richard Biener <rguenther@suse.de> writes:
> This should be 4/4 but I have the main patch on top, so...

>

> This uses the region-based VN from GIMPLE unrolling which means

> we better approximate the effects optimizations on unrolled inner

> loops when evaluating whether to unroll outer ones.


Great!  Sounds like it should also fix cases where missed value-numbering
opportunities after unrolling prevented SLP vectorisation.  (Hit a few of
those, but don't have the testcases to hand unfortunately.)

Thanks,
Richard

>

> 	* tree-ssa-loop-ivcanon.c: Include tree-ssa-sccvn.h.

> 	(propagate_constants_for_unrolling): Remove.

> 	(tree_unroll_loops_completely): Perform value-numbering

> 	on the unrolled bodies loop parent.

>

> 	* gfortran.dg/reassoc_4.f: Change max-completely-peeled-insns

> 	param to current default.

> ---

>  gcc/testsuite/gfortran.dg/reassoc_4.f |  2 +-

>  gcc/tree-ssa-loop-ivcanon.c           | 57 ++++++-----------------------------

>  2 files changed, 10 insertions(+), 49 deletions(-)

>

> diff --git a/gcc/testsuite/gfortran.dg/reassoc_4.f b/gcc/testsuite/gfortran.dg/reassoc_4.f

> index b155cba768c..07b4affb2a4 100644

> --- a/gcc/testsuite/gfortran.dg/reassoc_4.f

> +++ b/gcc/testsuite/gfortran.dg/reassoc_4.f

> @@ -1,5 +1,5 @@

>  ! { dg-do compile }

> -! { dg-options "-O3 -ffast-math -fdump-tree-reassoc1 --param max-completely-peeled-insns=400" }

> +! { dg-options "-O3 -ffast-math -fdump-tree-reassoc1 --param max-completely-peeled-insns=200" }

>  ! { dg-additional-options "--param max-completely-peel-times=16" { target spu-*-* } }

>        subroutine anisonl(w,vo,anisox,s,ii1,jj1,weight)

>        integer ii1,jj1,i1,iii1,j1,jjj1,k1,l1,m1,n1

> diff --git a/gcc/tree-ssa-loop-ivcanon.c b/gcc/tree-ssa-loop-ivcanon.c

> index 326589f63c3..97c2ad94985 100644

> --- a/gcc/tree-ssa-loop-ivcanon.c

> +++ b/gcc/tree-ssa-loop-ivcanon.c

> @@ -63,6 +63,7 @@ along with GCC; see the file COPYING3.  If not see

>  #include "tree-inline.h"

>  #include "tree-cfgcleanup.h"

>  #include "builtins.h"

> +#include "tree-ssa-sccvn.h"

>  

>  /* Specifies types of loops that may be unrolled.  */

>  

> @@ -1318,50 +1319,6 @@ canonicalize_induction_variables (void)

>    return 0;

>  }

>  

> -/* Propagate constant SSA_NAMEs defined in basic block BB.  */

> -

> -static void

> -propagate_constants_for_unrolling (basic_block bb)

> -{

> -  /* Look for degenerate PHI nodes with constant argument.  */

> -  for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )

> -    {

> -      gphi *phi = gsi.phi ();

> -      tree result = gimple_phi_result (phi);

> -      tree arg = gimple_phi_arg_def (phi, 0);

> -

> -      if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (result)

> -	  && gimple_phi_num_args (phi) == 1

> -	  && CONSTANT_CLASS_P (arg))

> -	{

> -	  replace_uses_by (result, arg);

> -	  gsi_remove (&gsi, true);

> -	  release_ssa_name (result);

> -	}

> -      else

> -	gsi_next (&gsi);

> -    }

> -

> -  /* Look for assignments to SSA names with constant RHS.  */

> -  for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )

> -    {

> -      gimple *stmt = gsi_stmt (gsi);

> -      tree lhs;

> -

> -      if (is_gimple_assign (stmt)

> -	  && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_constant

> -	  && (lhs = gimple_assign_lhs (stmt), TREE_CODE (lhs) == SSA_NAME)

> -	  && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))

> -	{

> -	  replace_uses_by (lhs, gimple_assign_rhs1 (stmt));

> -	  gsi_remove (&gsi, true);

> -	  release_ssa_name (lhs);

> -	}

> -      else

> -	gsi_next (&gsi);

> -    }

> -}

> -

>  /* Process loops from innermost to outer, stopping at the innermost

>     loop we unrolled.  */

>  

> @@ -1512,10 +1469,14 @@ tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)

>  	  EXECUTE_IF_SET_IN_BITMAP (fathers, 0, i, bi)

>  	    {

>  	      loop_p father = get_loop (cfun, i);

> -	      basic_block *body = get_loop_body_in_dom_order (father);

> -	      for (unsigned j = 0; j < father->num_nodes; j++)

> -		propagate_constants_for_unrolling (body[j]);

> -	      free (body);

> +	      bitmap exit_bbs = BITMAP_ALLOC (NULL);

> +	      loop_exit *exit = father->exits->next;

> +	      while (exit->e)

> +		{

> +		  bitmap_set_bit (exit_bbs, exit->e->dest->index);

> +		  exit = exit->next;

> +		}

> +	      do_rpo_vn (cfun, loop_preheader_edge (father), exit_bbs);

>  	    }

>  	  BITMAP_FREE (fathers);
Richard Biener Aug. 1, 2018, 5:53 p.m. | #2
On August 1, 2018 4:58:09 PM GMT+02:00, Richard Sandiford <richard.sandiford@arm.com> wrote:
>Richard Biener <rguenther@suse.de> writes:

>> This should be 4/4 but I have the main patch on top, so...

>>

>> This uses the region-based VN from GIMPLE unrolling which means

>> we better approximate the effects optimizations on unrolled inner

>> loops when evaluating whether to unroll outer ones.

>

>Great!  Sounds like it should also fix cases where missed

>value-numbering

>opportunities after unrolling prevented SLP vectorisation.  (Hit a few

>of

>those, but don't have the testcases to hand unfortunately.)


Yes though as before we do not value number the blocks if they are not contained inside a loop. That's of course easy to change. 

Richard. 

>Thanks,

>Richard

>

>>

>> 	* tree-ssa-loop-ivcanon.c: Include tree-ssa-sccvn.h.

>> 	(propagate_constants_for_unrolling): Remove.

>> 	(tree_unroll_loops_completely): Perform value-numbering

>> 	on the unrolled bodies loop parent.

>>

>> 	* gfortran.dg/reassoc_4.f: Change max-completely-peeled-insns

>> 	param to current default.

>> ---

>>  gcc/testsuite/gfortran.dg/reassoc_4.f |  2 +-

>>  gcc/tree-ssa-loop-ivcanon.c           | 57

>++++++-----------------------------

>>  2 files changed, 10 insertions(+), 49 deletions(-)

>>

>> diff --git a/gcc/testsuite/gfortran.dg/reassoc_4.f

>b/gcc/testsuite/gfortran.dg/reassoc_4.f

>> index b155cba768c..07b4affb2a4 100644

>> --- a/gcc/testsuite/gfortran.dg/reassoc_4.f

>> +++ b/gcc/testsuite/gfortran.dg/reassoc_4.f

>> @@ -1,5 +1,5 @@

>>  ! { dg-do compile }

>> -! { dg-options "-O3 -ffast-math -fdump-tree-reassoc1 --param

>max-completely-peeled-insns=400" }

>> +! { dg-options "-O3 -ffast-math -fdump-tree-reassoc1 --param

>max-completely-peeled-insns=200" }

>>  ! { dg-additional-options "--param max-completely-peel-times=16" {

>target spu-*-* } }

>>        subroutine anisonl(w,vo,anisox,s,ii1,jj1,weight)

>>        integer ii1,jj1,i1,iii1,j1,jjj1,k1,l1,m1,n1

>> diff --git a/gcc/tree-ssa-loop-ivcanon.c

>b/gcc/tree-ssa-loop-ivcanon.c

>> index 326589f63c3..97c2ad94985 100644

>> --- a/gcc/tree-ssa-loop-ivcanon.c

>> +++ b/gcc/tree-ssa-loop-ivcanon.c

>> @@ -63,6 +63,7 @@ along with GCC; see the file COPYING3.  If not see

>>  #include "tree-inline.h"

>>  #include "tree-cfgcleanup.h"

>>  #include "builtins.h"

>> +#include "tree-ssa-sccvn.h"

>>  

>>  /* Specifies types of loops that may be unrolled.  */

>>  

>> @@ -1318,50 +1319,6 @@ canonicalize_induction_variables (void)

>>    return 0;

>>  }

>>  

>> -/* Propagate constant SSA_NAMEs defined in basic block BB.  */

>> -

>> -static void

>> -propagate_constants_for_unrolling (basic_block bb)

>> -{

>> -  /* Look for degenerate PHI nodes with constant argument.  */

>> -  for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )

>> -    {

>> -      gphi *phi = gsi.phi ();

>> -      tree result = gimple_phi_result (phi);

>> -      tree arg = gimple_phi_arg_def (phi, 0);

>> -

>> -      if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (result)

>> -	  && gimple_phi_num_args (phi) == 1

>> -	  && CONSTANT_CLASS_P (arg))

>> -	{

>> -	  replace_uses_by (result, arg);

>> -	  gsi_remove (&gsi, true);

>> -	  release_ssa_name (result);

>> -	}

>> -      else

>> -	gsi_next (&gsi);

>> -    }

>> -

>> -  /* Look for assignments to SSA names with constant RHS.  */

>> -  for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p

>(gsi); )

>> -    {

>> -      gimple *stmt = gsi_stmt (gsi);

>> -      tree lhs;

>> -

>> -      if (is_gimple_assign (stmt)

>> -	  && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) ==

>tcc_constant

>> -	  && (lhs = gimple_assign_lhs (stmt), TREE_CODE (lhs) == SSA_NAME)

>> -	  && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))

>> -	{

>> -	  replace_uses_by (lhs, gimple_assign_rhs1 (stmt));

>> -	  gsi_remove (&gsi, true);

>> -	  release_ssa_name (lhs);

>> -	}

>> -      else

>> -	gsi_next (&gsi);

>> -    }

>> -}

>> -

>>  /* Process loops from innermost to outer, stopping at the innermost

>>     loop we unrolled.  */

>>  

>> @@ -1512,10 +1469,14 @@ tree_unroll_loops_completely (bool

>may_increase_size, bool unroll_outer)

>>  	  EXECUTE_IF_SET_IN_BITMAP (fathers, 0, i, bi)

>>  	    {

>>  	      loop_p father = get_loop (cfun, i);

>> -	      basic_block *body = get_loop_body_in_dom_order (father);

>> -	      for (unsigned j = 0; j < father->num_nodes; j++)

>> -		propagate_constants_for_unrolling (body[j]);

>> -	      free (body);

>> +	      bitmap exit_bbs = BITMAP_ALLOC (NULL);

>> +	      loop_exit *exit = father->exits->next;

>> +	      while (exit->e)

>> +		{

>> +		  bitmap_set_bit (exit_bbs, exit->e->dest->index);

>> +		  exit = exit->next;

>> +		}

>> +	      do_rpo_vn (cfun, loop_preheader_edge (father), exit_bbs);

>>  	    }

>>  	  BITMAP_FREE (fathers);

Patch

diff --git a/gcc/testsuite/gfortran.dg/reassoc_4.f b/gcc/testsuite/gfortran.dg/reassoc_4.f
index b155cba768c..07b4affb2a4 100644
--- a/gcc/testsuite/gfortran.dg/reassoc_4.f
+++ b/gcc/testsuite/gfortran.dg/reassoc_4.f
@@ -1,5 +1,5 @@ 
 ! { dg-do compile }
-! { dg-options "-O3 -ffast-math -fdump-tree-reassoc1 --param max-completely-peeled-insns=400" }
+! { dg-options "-O3 -ffast-math -fdump-tree-reassoc1 --param max-completely-peeled-insns=200" }
 ! { dg-additional-options "--param max-completely-peel-times=16" { target spu-*-* } }
       subroutine anisonl(w,vo,anisox,s,ii1,jj1,weight)
       integer ii1,jj1,i1,iii1,j1,jjj1,k1,l1,m1,n1
diff --git a/gcc/tree-ssa-loop-ivcanon.c b/gcc/tree-ssa-loop-ivcanon.c
index 326589f63c3..97c2ad94985 100644
--- a/gcc/tree-ssa-loop-ivcanon.c
+++ b/gcc/tree-ssa-loop-ivcanon.c
@@ -63,6 +63,7 @@  along with GCC; see the file COPYING3.  If not see
 #include "tree-inline.h"
 #include "tree-cfgcleanup.h"
 #include "builtins.h"
+#include "tree-ssa-sccvn.h"
 
 /* Specifies types of loops that may be unrolled.  */
 
@@ -1318,50 +1319,6 @@  canonicalize_induction_variables (void)
   return 0;
 }
 
-/* Propagate constant SSA_NAMEs defined in basic block BB.  */
-
-static void
-propagate_constants_for_unrolling (basic_block bb)
-{
-  /* Look for degenerate PHI nodes with constant argument.  */
-  for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
-    {
-      gphi *phi = gsi.phi ();
-      tree result = gimple_phi_result (phi);
-      tree arg = gimple_phi_arg_def (phi, 0);
-
-      if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (result)
-	  && gimple_phi_num_args (phi) == 1
-	  && CONSTANT_CLASS_P (arg))
-	{
-	  replace_uses_by (result, arg);
-	  gsi_remove (&gsi, true);
-	  release_ssa_name (result);
-	}
-      else
-	gsi_next (&gsi);
-    }
-
-  /* Look for assignments to SSA names with constant RHS.  */
-  for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
-    {
-      gimple *stmt = gsi_stmt (gsi);
-      tree lhs;
-
-      if (is_gimple_assign (stmt)
-	  && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_constant
-	  && (lhs = gimple_assign_lhs (stmt), TREE_CODE (lhs) == SSA_NAME)
-	  && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
-	{
-	  replace_uses_by (lhs, gimple_assign_rhs1 (stmt));
-	  gsi_remove (&gsi, true);
-	  release_ssa_name (lhs);
-	}
-      else
-	gsi_next (&gsi);
-    }
-}
-
 /* Process loops from innermost to outer, stopping at the innermost
    loop we unrolled.  */
 
@@ -1512,10 +1469,14 @@  tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
 	  EXECUTE_IF_SET_IN_BITMAP (fathers, 0, i, bi)
 	    {
 	      loop_p father = get_loop (cfun, i);
-	      basic_block *body = get_loop_body_in_dom_order (father);
-	      for (unsigned j = 0; j < father->num_nodes; j++)
-		propagate_constants_for_unrolling (body[j]);
-	      free (body);
+	      bitmap exit_bbs = BITMAP_ALLOC (NULL);
+	      loop_exit *exit = father->exits->next;
+	      while (exit->e)
+		{
+		  bitmap_set_bit (exit_bbs, exit->e->dest->index);
+		  exit = exit->next;
+		}
+	      do_rpo_vn (cfun, loop_preheader_edge (father), exit_bbs);
 	    }
 	  BITMAP_FREE (fathers);