[Bug tree-optimization/53774] New: Reassociator generates non-canonical addition

[Bug tree-optimization/53774] New: Reassociator generates non-canonical addition

[wschmidt at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53774

             Bug #: 53774
           Summary: Reassociator generates non-canonical addition
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: wschmidt@gcc.gnu.org
                CC: bergner@vnet.ibm.com, rguenther@suse.de


There is one test in the regression testsuite for which the reassociator
generates a GIMPLE addition that is not canonical.  Specifically, it generates
an add where rhs1 is a constant and rhs2 is an SSA name.  The test is:

gcc.c-torture/compiler/pr41634.c

The generated GIMPLE includes:

  D.1393_7 = 4294967293 + fp_6(D);

Probably best just to run this test from the testsuite to reproduce, but here
is the command I used.

/home/wschmidt/gcc/build/gcc-mainline-slsrpt1a/gcc/xgcc
-B/home/wschmidt/gcc/build/gcc-mainline-slsrpt1a/gcc/
-fno-diagnostics-show-caret -O0 -w -c -m32 -o pr41634.o
/home/wschmidt/gcc/gcc-mainline-slsrpt1a/gcc/testsuite/gcc.c-torture/compile/pr41634.c

[Bug tree-optimization/53774] Reassociator generates non-canonical addition

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53774

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-06-26
     Ever Confirmed|0                           |1

--- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-06-26 08:56:35 UTC ---
Confirmed with -O1.  get_rank (fp_6(D)) returns the same value as
get_rank (constant).  Constants should always have a lesser rank than
non-constants.

Index: gcc/tree-ssa-reassoc.c
===================================================================
--- gcc/tree-ssa-reassoc.c      (revision 188927)
+++ gcc/tree-ssa-reassoc.c      (working copy)
@@ -337,7 +337,7 @@ get_rank (tree e)
 {
   /* Constants have rank 0.  */
   if (is_gimple_min_invariant (e))
-    return 0;
+    return -1;

   /* SSA_NAME's have the rank of the expression they are the result
      of.

would fix it, but I'm not sure we want negative ranks.

[Bug tree-optimization/53774] Reassociator generates non-canonical addition

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53774

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
             Status|NEW                         |ASSIGNED
         AssignedTo|unassigned at gcc dot       |rguenth at gcc dot gnu.org
                   |gnu.org                     |

--- Comment #2 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-06-26 14:24:13 UTC ---
I am testing instead

@@ -2299,8 +2299,16 @@ rewrite_expr_tree (gimple stmt, unsigned
              print_gimple_stmt (dump_file, stmt, 0, 0);
            }

-         gimple_assign_set_rhs1 (stmt, oe1->op);
-         gimple_assign_set_rhs2 (stmt, oe2->op);
+         if (tree_swap_operands_p (oe1->op, oe2->op, true))
+           {
+             gimple_assign_set_rhs1 (stmt, oe2->op);
+             gimple_assign_set_rhs2 (stmt, oe1->op);
+           }
+         else
+           {
+             gimple_assign_set_rhs1 (stmt, oe1->op);
+             gimple_assign_set_rhs2 (stmt, oe2->op);
+           }
          update_stmt (stmt);
          if (rhs1 != oe1->op && rhs1 != oe2->op)
            remove_visited_stmt_chain (rhs1);

which fixes it.  OTOH there are many other places reassoc adjusts
stmt operands (but it eventually relies on operand order).  Adding
a canonicalize_operand_order_and_update_stmt () wherever we
call update_stmt afer adjusting operands might be better ... or
simply calling fold_stmt on all stmts we touch which does the re-ordering, too.

Well, I'm not really sure where we should enforce canonical ordering ...

[Bug tree-optimization/53774] Reassociator generates non-canonical addition

[wschmidt at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53774

--- Comment #3 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2012-06-26 18:42:41 UTC ---
I wonder why fp_6(D) gets a rank of zero.  Is it an uninitialized variable or a
parameter?  Parms are supposed to get small positive numbers for ranks.  Maybe
the "right" fix is to force fp_6(D) to get a nonzero rank?

[Bug tree-optimization/53774] Reassociator generates non-canonical addition

[wschmidt at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53774

--- Comment #4 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2012-06-26 18:52:44 UTC ---
Yeah, looking at the test case it's an uninitialized variable.  Seems like a
hole in the ranking system that it gets a rank of zero.  I think a default
value that isn't a parm should be treated like a parm -- add 1 to the value of
the last parm's rank and give it that rank.

[Bug tree-optimization/53774] Reassociator generates non-canonical addition

[rguenther at suse dot de]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53774

--- Comment #5 from rguenther at suse dot de <rguenther at suse dot de> 2012-06-27 08:28:27 UTC ---
On Tue, 26 Jun 2012, wschmidt at gcc dot gnu.org wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53774
> 
> --- Comment #3 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2012-06-26 18:42:41 UTC ---
> I wonder why fp_6(D) gets a rank of zero.  Is it an uninitialized variable or a
> parameter?  Parms are supposed to get small positive numbers for ranks.  Maybe
> the "right" fix is to force fp_6(D) to get a nonzero rank?

Yes, fp_6(D) is not initialized.

It also seems that ranks for non-constants are based on zero, too,
as for example loop-carried PHIs also might get a rank of zero.

Parameters get ranks starting off 3 (see init_reassoc).  I suppose
we could instead of walking over DECL_ARGUMENTS simply walk over all
SSA names and assign ranks to all default-defs instead.  I'm going
to test that.

Ah, it's

      if (TREE_CODE (SSA_NAME_VAR (e)) == PARM_DECL
          && SSA_NAME_IS_DEFAULT_DEF (e))
        return find_operand_rank (e);

      stmt = SSA_NAME_DEF_STMT (e);
      if (gimple_bb (stmt) == NULL)
        return 0;

in get_rank - that will return zero for all non-param default-defs,
even for the static chain we try to setup properly :/

Yeah, the following works - thanks for the hint ;)

Index: gcc/tree-ssa-reassoc.c
===================================================================
--- gcc/tree-ssa-reassoc.c      (revision 188987)
+++ gcc/tree-ssa-reassoc.c      (working copy)
@@ -383,14 +383,10 @@ get_rank (tree e)
       int i, n;
       tree op;

-      if (TREE_CODE (SSA_NAME_VAR (e)) == PARM_DECL
-         && SSA_NAME_IS_DEFAULT_DEF (e))
+      if (SSA_NAME_IS_DEFAULT_DEF (e))
        return find_operand_rank (e);

       stmt = SSA_NAME_DEF_STMT (e);
-      if (gimple_bb (stmt) == NULL)
-       return 0;
-
       if (gimple_code (stmt) == GIMPLE_PHI)
        return phi_rank (stmt);

@@ -3647,7 +3643,6 @@ init_reassoc (void)
 {
   int i;
   long rank = 2;
-  tree param;
   int *bbs = XNEWVEC (int, last_basic_block + 1);

   /* Find the loops, so that we can prevent moving calculations in
@@ -3666,24 +3661,13 @@ init_reassoc (void)
   bb_rank = XCNEWVEC (long, last_basic_block + 1);
   operand_rank = pointer_map_create ();

-  /* Give each argument a distinct rank.   */
-  for (param = DECL_ARGUMENTS (current_function_decl);
-       param;
-       param = DECL_CHAIN (param))
-    {
-      if (gimple_default_def (cfun, param) != NULL)
-       {
-         tree def = gimple_default_def (cfun, param);
-         insert_operand_rank (def, ++rank);
-       }
-    }
-
-  /* Give the chain decl a distinct rank. */
-  if (cfun->static_chain_decl != NULL)
-    {
-      tree def = gimple_default_def (cfun, cfun->static_chain_decl);
-      if (def != NULL)
-       insert_operand_rank (def, ++rank);
+  /* Give each default definition a distinct rank.  This includes
+     parameters and the static chain.  */
+  for (i = 1; i < (int) num_ssa_names; ++i)
+    {
+      tree name = ssa_name (i);
+      if (name && SSA_NAME_IS_DEFAULT_DEF (name))
+       insert_operand_rank (name, ++rank);
     }

   /* Set up rank for each BB  */

[Bug tree-optimization/53774] Reassociator generates non-canonical addition

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53774

--- Comment #6 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-06-27 11:29:08 UTC ---
Author: rguenth
Date: Wed Jun 27 11:29:04 2012
New Revision: 189012

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=189012
Log:
2012-06-27  Richard Guenther  <rguenther@suse.de>

    PR tree-optimization/53774
    * tree-ssa-reassoc.c (get_rank): All default defs have
    precomputed rank.
    (init_reassoc): Precompute rank for all SSA default defs.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-reassoc.c

[Bug tree-optimization/53774] Reassociator generates non-canonical addition

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53774

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED

--- Comment #6 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-06-27 11:29:08 UTC ---
Author: rguenth
Date: Wed Jun 27 11:29:04 2012
New Revision: 189012

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=189012
Log:
2012-06-27  Richard Guenther  <rguenther@suse.de>

    PR tree-optimization/53774
    * tree-ssa-reassoc.c (get_rank): All default defs have
    precomputed rank.
    (init_reassoc): Precompute rank for all SSA default defs.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-reassoc.c

--- Comment #7 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-06-27 11:29:53 UTC ---
Fixed.

[Bug tree-optimization/53774] Reassociator generates non-canonical addition

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53774

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED

--- Comment #7 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-06-27 11:29:53 UTC ---
Fixed.