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

[Jakub Jelinek]

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  <ja...@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