diff mbox

Try to avoid sorting on SSA_NAME_VERSION during reassoc (PR middle-end/60418)

Message ID 20140312153716.GN22862@tucnak.redhat.com
State New
Headers show

Commit Message

Jakub Jelinek March 12, 2014, 3:37 p.m. UTC 
Hi!

Apparently 435.gromacs benchmark is very sensitive (of course with
-ffast-math) to reassociation ordering.

We were sorting on SSA_NAME_VERSIONs, which has the disadvantage that we
reuse SSA_NAME_VERSIONs from SSA_NAMEs dropped by earlier optimization
passes and thus even minor changes in unrelated parts of function in
unrelated optimizations can have very big effects on reassociation
decisions.

As discussed on IRC and in bugzilla, this patch attempts to sort on
the ordering of SSA_NAME_DEF_STMT statements.  If they are in different
basic blocks, it uses bb_rank for sorting, if they are within the same
bb, it checks which stmt dominates the other one in the bb (using
gimple_uid).

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

2014-03-12  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/59025
	PR middle-end/60418
	* tree-ssa-reassoc.c (sort_by_operand_rank): For SSA_NAMEs with the
	same rank, sort by bb_rank and gimple_uid of SSA_NAME_DEF_STMT first.


	Jakub

Comments

Richard Biener March 13, 2014, 9:25 a.m. UTC | #1 
On Wed, 12 Mar 2014, Jakub Jelinek wrote:

> Hi!
> 
> Apparently 435.gromacs benchmark is very sensitive (of course with
> -ffast-math) to reassociation ordering.
> 
> We were sorting on SSA_NAME_VERSIONs, which has the disadvantage that we
> reuse SSA_NAME_VERSIONs from SSA_NAMEs dropped by earlier optimization
> passes and thus even minor changes in unrelated parts of function in
> unrelated optimizations can have very big effects on reassociation
> decisions.
> 
> As discussed on IRC and in bugzilla, this patch attempts to sort on
> the ordering of SSA_NAME_DEF_STMT statements.  If they are in different
> basic blocks, it uses bb_rank for sorting, if they are within the same
> bb, it checks which stmt dominates the other one in the bb (using
> gimple_uid).
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

Ok.  Does this also fix the PPC regression?

Thanks,
Richard.

> 2014-03-12  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR tree-optimization/59025
> 	PR middle-end/60418
> 	* tree-ssa-reassoc.c (sort_by_operand_rank): For SSA_NAMEs with the
> 	same rank, sort by bb_rank and gimple_uid of SSA_NAME_DEF_STMT first.
> 
> --- gcc/tree-ssa-reassoc.c.jj	2014-03-10 18:12:30.782215912 +0100
> +++ gcc/tree-ssa-reassoc.c	2014-03-12 10:09:03.341757696 +0100
> @@ -219,6 +219,7 @@ static struct pointer_map_t *operand_ran
>  
>  /* Forward decls.  */
>  static long get_rank (tree);
> +static bool reassoc_stmt_dominates_stmt_p (gimple, gimple);
>  
>  
>  /* Bias amount for loop-carried phis.  We want this to be larger than
> @@ -506,11 +507,37 @@ sort_by_operand_rank (const void *pa, co
>      }
>  
>    /* Lastly, make sure the versions that are the same go next to each
> -     other.  We use SSA_NAME_VERSION because it's stable.  */
> +     other.  */
>    if ((oeb->rank - oea->rank == 0)
>        && TREE_CODE (oea->op) == SSA_NAME
>        && TREE_CODE (oeb->op) == SSA_NAME)
>      {
> +      /* As SSA_NAME_VERSION is assigned pretty randomly, because we reuse
> +	 versions of removed SSA_NAMEs, so if possible, prefer to sort
> +	 based on basic block and gimple_uid of the SSA_NAME_DEF_STMT.
> +	 See PR60418.  */
> +      if (!SSA_NAME_IS_DEFAULT_DEF (oea->op)
> +	  && !SSA_NAME_IS_DEFAULT_DEF (oeb->op)
> +	  && SSA_NAME_VERSION (oeb->op) != SSA_NAME_VERSION (oea->op))
> +	{
> +	  gimple stmta = SSA_NAME_DEF_STMT (oea->op);
> +	  gimple stmtb = SSA_NAME_DEF_STMT (oeb->op);
> +	  basic_block bba = gimple_bb (stmta);
> +	  basic_block bbb = gimple_bb (stmtb);
> +	  if (bbb != bba)
> +	    {
> +	      if (bb_rank[bbb->index] != bb_rank[bba->index])
> +		return bb_rank[bbb->index] - bb_rank[bba->index];
> +	    }
> +	  else
> +	    {
> +	      bool da = reassoc_stmt_dominates_stmt_p (stmta, stmtb);
> +	      bool db = reassoc_stmt_dominates_stmt_p (stmtb, stmta);
> +	      if (da != db)
> +		return da ? 1 : -1;
> +	    }
> +	}
> +
>        if (SSA_NAME_VERSION (oeb->op) != SSA_NAME_VERSION (oea->op))
>  	return SSA_NAME_VERSION (oeb->op) - SSA_NAME_VERSION (oea->op);
>        else
> 
> 	Jakub
> 
>
Jakub Jelinek March 13, 2014, 9:30 a.m. UTC | #2 
On Thu, Mar 13, 2014 at 10:25:57AM +0100, Richard Biener wrote:
> > Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
> 
> Ok.  Does this also fix the PPC regression?

That is a question for Peter, if we can ask him to test it.
From what I understood, the bug no longer reproduces on the trunk on ppc*,
and Peter tested an earlier version of this patch on top of an old revision
where it still reproduced.

> > 2014-03-12  Jakub Jelinek  <jakub@redhat.com>
> > 
> > 	PR tree-optimization/59025
> > 	PR middle-end/60418
> > 	* tree-ssa-reassoc.c (sort_by_operand_rank): For SSA_NAMEs with the
> > 	same rank, sort by bb_rank and gimple_uid of SSA_NAME_DEF_STMT first.

	Jakub
Peter Bergner March 13, 2014, 11:43 a.m. UTC | #3 
On Thu, 2014-03-13 at 10:30 +0100, Jakub Jelinek wrote:
> On Thu, Mar 13, 2014 at 10:25:57AM +0100, Richard Biener wrote:
> > > Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
> > 
> > Ok.  Does this also fix the PPC regression?
> 
> That is a question for Peter, if we can ask him to test it.
> From what I understood, the bug no longer reproduces on the trunk on ppc*,
> and Peter tested an earlier version of this patch on top of an old revision
> where it still reproduced.

Actually, I think it was Pat who did the testing earlier.
Pat, can you confirm Jakub's patch fixes the PPC regression?

Peter


> > > 2014-03-12  Jakub Jelinek  <jakub@redhat.com>
> > > 
> > > 	PR tree-optimization/59025
> > > 	PR middle-end/60418
> > > 	* tree-ssa-reassoc.c (sort_by_operand_rank): For SSA_NAMEs with the
> > > 	same rank, sort by bb_rank and gimple_uid of SSA_NAME_DEF_STMT first.
Pat Haugen March 13, 2014, 2:53 p.m. UTC | #4 
On 03/13/2014 06:43 AM, Peter Bergner wrote:
> On Thu, 2014-03-13 at 10:30 +0100, Jakub Jelinek wrote:
>> >On Thu, Mar 13, 2014 at 10:25:57AM +0100, Richard Biener wrote:
>>>> > > >Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
>>> > >
>>> > >Ok.  Does this also fix the PPC regression?
>> >
>> >That is a question for Peter, if we can ask him to test it.
>> > From what I understood, the bug no longer reproduces on the trunk on ppc*,
>> >and Peter tested an earlier version of this patch on top of an old revision
>> >where it still reproduced.
> Actually, I think it was Pat who did the testing earlier.
> Pat, can you confirm Jakub's patch fixes the PPC regression?
Yes, this latest version of the patch also fixes the PPC regression on 
r204348 (last known revision to fail for PPC).
Jakub Jelinek March 13, 2014, 2:55 p.m. UTC | #5 
On Thu, Mar 13, 2014 at 09:53:47AM -0500, Pat Haugen wrote:
> On 03/13/2014 06:43 AM, Peter Bergner wrote:
> >On Thu, 2014-03-13 at 10:30 +0100, Jakub Jelinek wrote:
> >>>On Thu, Mar 13, 2014 at 10:25:57AM +0100, Richard Biener wrote:
> >>>>> > >Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
> >>>> >
> >>>> >Ok.  Does this also fix the PPC regression?
> >>>
> >>>That is a question for Peter, if we can ask him to test it.
> >>> From what I understood, the bug no longer reproduces on the trunk on ppc*,
> >>>and Peter tested an earlier version of this patch on top of an old revision
> >>>where it still reproduced.
> >Actually, I think it was Pat who did the testing earlier.
> >Pat, can you confirm Jakub's patch fixes the PPC regression?
> Yes, this latest version of the patch also fixes the PPC regression
> on r204348 (last known revision to fail for PPC).

Thanks.

	Jakub
diff mbox

Patch

--- gcc/tree-ssa-reassoc.c.jj	2014-03-10 18:12:30.782215912 +0100
+++ gcc/tree-ssa-reassoc.c	2014-03-12 10:09:03.341757696 +0100
@@ -219,6 +219,7 @@  static struct pointer_map_t *operand_ran
 
 /* Forward decls.  */
 static long get_rank (tree);
+static bool reassoc_stmt_dominates_stmt_p (gimple, gimple);
 
 
 /* Bias amount for loop-carried phis.  We want this to be larger than
@@ -506,11 +507,37 @@  sort_by_operand_rank (const void *pa, co
     }
 
   /* Lastly, make sure the versions that are the same go next to each
-     other.  We use SSA_NAME_VERSION because it's stable.  */
+     other.  */
   if ((oeb->rank - oea->rank == 0)
       && TREE_CODE (oea->op) == SSA_NAME
       && TREE_CODE (oeb->op) == SSA_NAME)
     {
+      /* As SSA_NAME_VERSION is assigned pretty randomly, because we reuse
+	 versions of removed SSA_NAMEs, so if possible, prefer to sort
+	 based on basic block and gimple_uid of the SSA_NAME_DEF_STMT.
+	 See PR60418.  */
+      if (!SSA_NAME_IS_DEFAULT_DEF (oea->op)
+	  && !SSA_NAME_IS_DEFAULT_DEF (oeb->op)
+	  && SSA_NAME_VERSION (oeb->op) != SSA_NAME_VERSION (oea->op))
+	{
+	  gimple stmta = SSA_NAME_DEF_STMT (oea->op);
+	  gimple stmtb = SSA_NAME_DEF_STMT (oeb->op);
+	  basic_block bba = gimple_bb (stmta);
+	  basic_block bbb = gimple_bb (stmtb);
+	  if (bbb != bba)
+	    {
+	      if (bb_rank[bbb->index] != bb_rank[bba->index])
+		return bb_rank[bbb->index] - bb_rank[bba->index];
+	    }
+	  else
+	    {
+	      bool da = reassoc_stmt_dominates_stmt_p (stmta, stmtb);
+	      bool db = reassoc_stmt_dominates_stmt_p (stmtb, stmta);
+	      if (da != db)
+		return da ? 1 : -1;
+	    }
+	}
+
       if (SSA_NAME_VERSION (oeb->op) != SSA_NAME_VERSION (oea->op))
 	return SSA_NAME_VERSION (oeb->op) - SSA_NAME_VERSION (oea->op);
       else