[Bug tree-optimization/49749] New: Reassociation rank algorithm does not include all non-NULL operands

[Bug tree-optimization/49749] New: Reassociation rank algorithm does not include all non-NULL operands

[wschmidt at gcc dot gnu.org]

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

           Summary: Reassociation rank algorithm does not include all
                    non-NULL operands
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: wschmidt@gcc.gnu.org
                CC: dje@gcc.gnu.org, richard.guenther@gmail.com,
                    bergner@gcc.gnu.org, pthaugen@gcc.gnu.org,
                    meissner@gcc.gnu.org
              Host: powerpc64-linux
            Target: powerpc64-linux
             Build: powerpc64-linux


Created attachment 24754
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24754
Excerpt from bwaves showing the problem on r161839 and before

tree-ssa-reassoc.c: get_rank () contains the following code:

      /* Otherwise, find the maximum rank for the operands, or the bb
     rank, whichever is less.   */
      rank = 0;
      maxrank = bb_rank[gimple_bb(stmt)->index];
      if (gimple_assign_single_p (stmt))
    {
      tree rhs = gimple_assign_rhs1 (stmt);
      n = TREE_OPERAND_LENGTH (rhs);
      if (n == 0)
        rank = MAX (rank, get_rank (rhs));
      else
        {
          for (i = 0;
           i < n && TREE_OPERAND (rhs, i) && rank != maxrank; i++)
        rank = MAX(rank, get_rank (TREE_OPERAND (rhs, i)));
        }
    }
      else
    {
      n = gimple_num_ops (stmt);
      for (i = 1; i < n && rank != maxrank; i++)
        {
          gcc_assert (gimple_op (stmt, i));
          rank = MAX(rank, get_rank (gimple_op (stmt, i)));
        }
    }


The loop condition: 

   i < n && TREE_OPERAND (rhs, i) && rank != maxrank; i++)

erroneously stops processing operands as soon as a NULL operand is detected. 
As an example, a TARGET_MEM_REF without a symbol operand (operand 0) will be
assigned a rank of zero by that loop.

The condition "rank != maxrank" in both loops seems to indicate that an
expression should never get a rank larger than its block rank.  I am seeing
cases where the rank is slightly larger; for example, a block rank of 1638400
and an operand rank of 1638404.  If the intent is to limit the value to 1638400
in such a case, this also needs to be fixed.

The existence of this bug has contributed in an odd way to a degradation of the
CPU2006 bwaves benchmark on powerpc64 (affected procedure attached).  In trunk
revision 161840 (7/5/2010), Richard Guenther changed the ivopts code to
generate MEM_REFs in preference to TARGET_MEM_REFs.  Prior to this change, SSA
names from assignments to TARGET_MEM_REFs were given a rank of 1.  Following
this change, SSA names from assignments to MEM_REFs were given a rank of
1638404 (for example), while SSA names from PHI assignments in the same block
were given a rank of 1638400.  Thus, prior to this change, PHI assignments had
higher rank than memory references in the same block, but after this change,
they had lower rank.

Giving preference to the PHI expressions over the memory references provided
better reassociation for the bwaves example.  In particular, prior to 161840 a
prephitmp was reassociated so that copyrename could generate something like

    prephitmp.160_552 = D.1095_522 + prephitmp.160_161;

thus making prephitmp.160 independent of other calculations in the loop
iteration.  When the PHI expression was given lowest rank, this did not occur,
causing prephitmp.160 to be dependent upon the result of the previous loop
iteration's calculations.

For powerpc64, we unroll the loop by a factor of 2.  When the two iterations
are independent, FMAs from the two iterations can be interleaved leading to
good performance.  When the two iterations are not independent, we end up with
a stack of linearly dependent FMAs at the end of the loop that chokes the
floating-point unit.

This leads to the question of whether PHIs at the top of a block should
generally be given preference over memory references in the interior of that
block.  It may be that if the PHIs and the memory references have the same
rank, this is exactly what will happen.  That might just be serendipity,
though; thoughts?

I will be experimenting with capping the rank of an expression at the rank of
the containing block, and including all operands in the ranking.  But I am very
interested in thoughts on this problem from those who are familiar with the
reassociator.

Please let me know if you would like further materials to examine.

The bug goes back a long way; the degradation affects us on 4.6 and 4.7.

[Bug tree-optimization/49749] Reassociation rank algorithm does not include all non-NULL operands

[wschmidt at gcc dot gnu.org]

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

--- Comment #2 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-07-14 19:23:29 UTC ---
Created attachment 24761
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24761
Gimple following reassoc2 with TARGET_MEM_REFs

[Bug tree-optimization/49749] Reassociation rank algorithm does not include all non-NULL operands

[wschmidt at gcc dot gnu.org]

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

--- Comment #1 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-07-14 19:22:08 UTC ---
Created attachment 24760
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24760
Gimple prior to reassoc2

[Bug tree-optimization/49749] Reassociation rank algorithm does not include all non-NULL operands

[wschmidt at gcc dot gnu.org]

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

--- Comment #5 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-07-14 19:25:51 UTC ---
Created attachment 24764
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24764
Gimple prior to expand, r161840

[Bug tree-optimization/49749] Reassociation rank algorithm does not include all non-NULL operands

[wschmidt at gcc dot gnu.org]

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

--- Comment #4 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-07-14 19:25:18 UTC ---
Created attachment 24763
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24763
Gimple prior to expand, r161839

[Bug tree-optimization/49749] Reassociation rank algorithm does not include all non-NULL operands

[wschmidt at gcc dot gnu.org]

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

--- Comment #3 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-07-14 19:24:19 UTC ---
Created attachment 24762
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24762
Gimple following reassoc2 with MEM_REFs

[Bug tree-optimization/49749] Reassociation rank algorithm does not include all non-NULL operands

[wschmidt at gcc dot gnu.org]

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

--- Comment #6 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-07-15 20:15:09 UTC ---
We ran some experiments attempting to restore the r161839 behavior, either by
lowering the rank of memory references or raising the rank of phi references. 
Although both experiments restored bwaves code generation to respectability,
several other benchmarks suffered, so this is not a general answer.  Any
thoughts on more limited heuristics that might help the bwaves scenario?

It seems that copyrename needs help from reassoc to find the opportunity;
perhaps reassoc can be tweaked to recognize situations that will help
copyrename downstream?

[Bug tree-optimization/49749] Reassociation rank algorithm does not include all non-NULL operands

[wschmidt at gcc dot gnu.org]

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

--- Comment #7 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-07-15 20:19:21 UTC ---
Our experiments didn't distinguish between loop-carried PHIs and other join
points, so that might be another avenue of attack.

[Bug tree-optimization/49749] Reassociation rank algorithm does not include all non-NULL operands

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011.07.18 09:07:11
     Ever Confirmed|0                           |1

--- Comment #8 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-07-18 09:07:11 UTC ---
First of call, confirmed.

[Bug tree-optimization/49749] Reassociation rank algorithm does not include all non-NULL operands

[wschmidt at gcc dot gnu.org]

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

William J. Schmidt <wschmidt at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
         AssignedTo|unassigned at gcc dot       |wschmidt at gcc dot gnu.org
                   |gnu.org                     |

--- Comment #9 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-07-20 16:28:49 UTC ---
Created attachment 24798
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24798
Proposed patch

I'm attaching a patch that solves this issue.  The patch was produced against
the ibm/gcc-4_6-branch, but should apply OK to trunk -- I'll verify that later
if the direction of this patch is acceptable.  This regains the 20% performance
loss we had experienced in 410.bwaves, and also gives a 5% boost to 444.namd. 
No significant degradations were observed on SPEC cpu2006.

In addition to fixing the operand access problems, the patch looks for
loop-carried dependencies in innermost loops, and biases the reassociation so
that the phi target is summed last.  The purpose of this is to identify
accumulator variables in inner loops and make each iteration of their
accumulations independent.  When these loops are unrolled, multiple independent
iterations can be interleaved for improved performance.

The optimization is restricted to innermost loops to avoid unnecessarily
raising register pressure.

There may be a better way to achieve the bias than what I've chosen here, so
please comment.  If the general approach is acceptable, I'll apply comments and
submit the patch for approval.

[Bug tree-optimization/49749] Reassociation rank algorithm does not include all non-NULL operands

[wschmidt at gcc dot gnu.org]

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

--- Comment #10 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-07-20 16:39:26 UTC ---
Created attachment 24799
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24799
The real proposed patch

Oh, for Pete's sake.  I attached the wrong patch.  Here's the right one.

[Bug tree-optimization/49749] Reassociation rank algorithm does not include all non-NULL operands

[wschmidt at gcc dot gnu.org]

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

--- Comment #11 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-07-20 19:01:30 UTC ---
I forgot to mention some justification for the value of PHI_LOOP_BIAS, and I
notice it has a misleading comment by it at the moment.  The value is a
constant that should be larger than the depth of the largest expected
reassociation tree, but generally smaller than twice the rank of the basic
block.  The intent is to limit the effect to single-block loops for now.  One
of the questions I have is whether the bias should be allowed for more complex
innermost loops.

PHI_LOOP_BIAS is a crude method and something more refined is probably needed,
but it serves to demonstrate the viability of the general approach.

[Bug tree-optimization/49749] Reassociation rank algorithm does not include all non-NULL operands

[rguenth at gcc dot gnu.org]

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

--- Comment #12 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-07-21 12:04:01 UTC ---
+      tree arg = gimple_phi_arg (stmt, i)->def;
+      if (TREE_CODE (arg) == SSA_NAME)
+    {
+      gimple def_stmt = SSA_NAME_DEF_STMT (arg);
+      if (def_stmt
+          && gimple_bb (def_stmt)

arg = gimple_phi_arg_def (stmt, i);
if (TREE_CODE (arg) == SSA_NAME
    && !SSA_NAME_IS_DEFAULT_DEF (arg))
  {
    gimple def_stmt = SSA_NAME_DEF_STMT (arg);
...

without the def_stmt != NULL and gimple_bb != NULL check.

[Bug tree-optimization/49749] Reassociation rank algorithm does not include all non-NULL operands

[wschmidt at gcc dot gnu.org]

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

--- Comment #13 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-07-21 18:07:42 UTC ---
Author: wschmidt
Date: Thu Jul 21 18:07:39 2011
New Revision: 176581

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=176581
Log:
2011-07-21  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

    PR tree-optimization/49749
    * tree-ssa-reassoc.c (get_rank): Fix operand scan conditions and
    remove no-longer-used maxrank variable.


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

[Bug tree-optimization/49749] Reassociation rank algorithm does not include all non-NULL operands

[wschmidt at gcc dot gnu.org]

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

--- Comment #14 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-07-21 20:27:21 UTC ---
Author: wschmidt
Date: Thu Jul 21 20:27:17 2011
New Revision: 176585

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=176585
Log:
2011-07-21  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

    PR tree-optimization/49749
    * tree-ssa-reassoc.c (PHI_LOOP_BIAS): New constant.
    (phi_loop_bias): New function.
    (get_rank): Bias rank upward for loop-carried dependencies; fix
    errors in operand scan conditions.


Modified:
    branches/ibm/gcc-4_6-branch/gcc/ChangeLog.ibm
    branches/ibm/gcc-4_6-branch/gcc/tree-ssa-reassoc.c

[Bug tree-optimization/49749] Reassociation rank algorithm does not include all non-NULL operands

[wschmidt at gcc dot gnu.org]

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

--- Comment #15 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-07-29 18:40:26 UTC ---
Author: wschmidt
Date: Fri Jul 29 18:40:21 2011
New Revision: 176948

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=176948
Log:
2011-07-29  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

    PR tree-optimization/49749
    * tree-ssa-reassoc.c (get_rank): New forward declaration.
    (PHI_LOOP_BIAS): Changed value.
    (phi_loop_bias): Replaced with...
    (phi_rank): ...this new function.
    (loop_carried_phi): New function.
    (propagate_rank): Likewise.
    (get_rank): Replace loop-biasing expression with call to phi_rank;
    remove variable maxrank; replace propagation logic with calls to
    propagate_rank.


Modified:
    branches/ibm/gcc-4_6-branch/gcc/ChangeLog.ibm
    branches/ibm/gcc-4_6-branch/gcc/tree-ssa-reassoc.c

[Bug tree-optimization/49749] Reassociation rank algorithm does not include all non-NULL operands

[wschmidt at gcc dot gnu.org]

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

--- Comment #16 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-07-31 18:58:09 UTC ---
Author: wschmidt
Date: Sun Jul 31 18:58:06 2011
New Revision: 176984

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=176984
Log:
2011-07-29  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

    PR tree-optimization/49749
    * tree-ssa-reassoc.c (get_rank): New forward declaration.
    (PHI_LOOP_BIAS): New macro.
    (phi_rank): New function.
    (loop_carried_phi): Likewise.
    (propagate_rank): Likewise.
    (get_rank): Add calls to phi_rank and propagate_rank.


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

[Bug tree-optimization/49749] Reassociation rank algorithm does not include all non-NULL operands

[wschmidt at gcc dot gnu.org]

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

William J. Schmidt <wschmidt at gcc dot gnu.org> changed:

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

--- Comment #17 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-07-31 19:01:05 UTC ---
Fixed.

[Bug tree-optimization/49749] Reassociation rank algorithm does not include all non-NULL operands

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49749

--- Comment #18 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Ilya Leoshkevich <iii@gcc.gnu.org>:

https://gcc.gnu.org/g:dbed1c8693c6b5cb02c903cea91db574200bd513

commit r12-3922-gdbed1c8693c6b5cb02c903cea91db574200bd513
Author: Ilya Leoshkevich <iii@linux.ibm.com>
Date:   Wed Jun 24 01:30:47 2020 +0200

    reassoc: Propagate PHI_LOOP_BIAS along single uses

    PR tree-optimization/49749 introduced code that shortens dependency
    chains containing loop accumulators by placing them last on operand
    lists of associative operations.

    456.hmmer benchmark on s390 could benefit from this, however, the code
    that needs it modifies loop accumulator before using it, and since only
    so-called loop-carried phis are are treated as loop accumulators, the
    code in the present form doesn't really help.   According to Bill
    Schmidt - the original author - such a conservative approach was chosen
    so as to avoid unnecessarily swapping operands, which might cause
    unpredictable effects.  However, giving special treatment to forms of
    loop accumulators is acceptable.

    The definition of loop-carried phi is: it's a single-use phi, which is
    used in the same innermost loop it's defined in, at least one argument
    of which is defined in the same innermost loop as the phi itself.
    Given this, it seems natural to treat single uses of such phis as phis
    themselves.

    gcc/ChangeLog:

            * tree-ssa-reassoc.c (biased_names): New global.
            (propagate_bias_p): New function.
            (loop_carried_phi): Remove.
            (propagate_rank): Propagate bias along single uses.
            (get_rank): Update biased_names when needed.