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

[Richard Biener]

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
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend"orffer