[Bug tree-optimization/58459] New: [4.9 regression] Loop invariant is not hoisted out of loop after r202525.

[Bug tree-optimization/58459] New: [4.9 regression] Loop invariant is not hoisted out of loop after r202525.

[ysrumyan at gmail dot com]

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

            Bug ID: 58459
           Summary: [4.9 regression] Loop invariant is not hoisted out of
                    loop after r202525.
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: ysrumyan at gmail dot com

We noticed significant performance regression on important bench from eembc2.0
suite which can be exhibit with attached test-case.

Assembly produced compiler prior to r202525 for innermost loop:

.L18:
    movl    %esi, %ebp
    movl    8(%eax), %edx
    sall    %cl, %ebp
    movl    12(%eax), %eax
    testl    %ebp, %ebx  <-- p->key is hoisted out of loop
    cmove    %edx, %eax
    movl    %ecx, %edx

but assembly produced compiler after r202525 contains redundant load:

.L17:
    movl    %esi, %ebp
    movl    8(%eax), %edx
    sall    %cl, %ebp
    movl    12(%eax), %eax
    testl    %ebp, (%ebx)  <-- p->key is not hoisted out of loop
    cmove    %edx, %eax
    movl    %ecx, %edx

The test-case must be compiled with -Ofast -m32 -march=atom -mtune=atom
options.

[Bug tree-optimization/58459] [4.9 regression] Loop invariant is not hoisted out of loop after r202525.

[ysrumyan at gmail dot com]

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

--- Comment #1 from Yuri Rumyantsev <ysrumyan at gmail dot com> ---
Created attachment 30850
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30850&action=edit
test-case to reproduce

Test must be compiled on x86 with options -Ofast -m332 -march=atom -mtune=atom

[Bug tree-optimization/58459] [4.9 regression] Loop invariant is not hoisted out of loop after r202525.

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2013-09-18
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
   Target Milestone|---                         |4.9.0
     Ever confirmed|0                           |1

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
I will have a look.

[Bug tree-optimization/58459] [4.9 regression] Loop invariant is not hoisted out of loop after r202525.

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
It is actually different behavior of PRE and not LIM doing the invariant
motion.
So it should reproduce with -O2 already (maybe you can double-check that).

[Bug tree-optimization/58459] [4.9 regression] Loop invariant is not hoisted out of loop after r202525.

[mpolacek at gcc dot gnu.org]

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

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mpolacek at gcc dot gnu.org

--- Comment #4 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #3)
> It is actually different behavior of PRE and not LIM doing the invariant
> motion.
> So it should reproduce with -O2 already (maybe you can double-check that).

Yes, that's right.

[Bug tree-optimization/58459] [4.9 regression] Loop invariant is not hoisted out of loop after r202525.

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Value-numbering it is (-good +bad):

-Value numbering _29 stmt = _29 = _7->key;
+Value numbering _29 stmt = _29 = MEM[(struct S *)&a][j_40].key;
 Setting value number of _29 to _29
...
 Value numbering _18 stmt = _18 = _7->key;
-Setting value number of _18 to _29 (changed)
+Setting value number of _18 to _18 (changed)

and this is because

static bool
forward_propagate_addr_expr (tree name, tree rhs)
{
...
      /* If the use is in a deeper loop nest, then we do not want
         to propagate non-invariant ADDR_EXPRs into the loop as that
         is likely adding expression evaluations into the loop.  */
      if (bb_loop_depth (gimple_bb (use_stmt)) > stmt_loop_depth
          && !is_gimple_min_invariant (rhs))
        {
          all = false;
          continue;

so we do not replace the address in the loop.

Value-numbering does some limited forward propagation, but it does not
handle varying addresses.

The best fix would be to SCCVN, another fix is to either propagate into to
all uses or into no uses.  I lean towards all uses (the above is too strict,
forwarding of say &p->a.b.c should not be constrained).  Note that dependence
analysis will also be confused when present with a mix of a[i][j] and *p
addressing.  Which really boils down to canonicalizing everything to
*p style addressing and lowering the address computation ... (as was my
original MEM_REF plan).

[Bug tree-optimization/58459] [4.9 regression] Loop invariant is not hoisted out of loop after r202525.

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
LIM does not move the invariant because it does not see that _7 in _7->key
is always dereferenced in the innermost loop.  This is because LIM computes
this property as a basic-block property, not as a reference property
(if all references are in the same form we could track that on a per reference
basis).

OTOH this again boils down to the fact that we do not have a code hoisting
pass.  PRE figures this out one level but fails to catch the third
occurance for some reason (just testing with -fno-tree-forwprop).

So, without major restructuring LIM won't do this and it certainly
wouldn't do it with partial rewritten _7 as we have it now with the
interesting loop still using the dereference form.

[Bug tree-optimization/58459] [4.9 regression] Loop invariant is not hoisted out of loop after r202525.

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Fri Sep 27 08:14:53 2013
New Revision: 202966

URL: http://gcc.gnu.org/viewcvs?rev=202966&root=gcc&view=rev
Log:
2013-09-27  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/58459
    * tree-ssa-forwprop.c (forward_propagate_addr_expr): Remove
    restriction not propagating into loops.

    * gcc.dg/tree-ssa/ssa-pre-31.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-31.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-forwprop.c

[Bug tree-optimization/58459] [4.9 regression] Loop invariant is not hoisted out of loop after r202525.

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.