[Bug tree-optimization/50204] New: [4.5/4.6/4.7 Regression] Missed fully redundant load found in crafty (SPEC 2k)

[Bug tree-optimization/50204] New: [4.5/4.6/4.7 Regression] Missed fully redundant load found in crafty (SPEC 2k)

[pinskia at gcc dot gnu.org]

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

             Bug #: 50204
           Summary: [4.5/4.6/4.7 Regression] Missed fully redundant load
                    found in crafty (SPEC 2k)
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: pinskia@gcc.gnu.org


Simplified testcase:
extern int opening;
extern int middle_game;
int s;
extern int d[1];
void PreEvaluate(int wtm)
{
  int i, j;
  if (opening) {
    d[0]=1;
  }
  else if (middle_game) {
    d[0]=-1;
  }
  if (4 != opening) {
    return;
  }
  s = 1;
}
--- CUT ---
4.3 catches the load of opening but 4.6 does not (4.5 does not either).

[Bug tree-optimization/50204] [4.5/4.6/4.7 Regression] Missed fully redundant load found in crafty (SPEC 2k)

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
      Known to work|                            |4.3.3
   Target Milestone|---                         |4.5.4
      Known to fail|                            |4.5.4, 4.6.1, 4.7.0

[Bug tree-optimization/50204] [4.5/4.6/4.7 Regression] Missed fully redundant load found in crafty (SPEC 2k)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011-08-27
                 CC|                            |rguenth at gcc dot gnu.org
     Ever Confirmed|0                           |1

--- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-08-27 08:13:12 UTC ---
This is because we have, for the 2nd load

<bb 6>:
  # .MEM_4 = PHI <.MEM_7(3), .MEM_6(D)(4), .MEM_8(5)>
  # VUSE <.MEM_4>
  opening.0_3 = opening;
  if (opening.0_3 != 4)


Thus three incoming edges.  The walker in SCCVN does not try to handle
more than two, see tree-ssa-alias.c:get_continuation_for_phi ().

In principle one can handle N PHI arguments by reducing them to
N - 1 PHI arguments by handling two of them and reducing them to
the dominating continuation.  And then iterate.  But the idea of
get_continuation_for_phi () is to make this walk linear which it
wouldn't be for this case.

Confirmed anyway.

I suppose it's not performance critical for crafty to see this redundant
load?

[Bug tree-optimization/50204] [4.5/4.6/4.7 Regression] Missed fully redundant load found in crafty (SPEC 2k)

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> 2011-08-29 03:00:48 UTC ---
Created attachment 25124
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25124
Patch which was tested on x86_64 without any regressions

Note I am going to add this patch here as the copyright assignment for Cavium
is not completed yet (though it is in the process of clearing up).  This
implements what is mentioned in comment #1 and was tested on x86_64-linux-gnu
with no regressions.  I don't know what the compile time slow down that happens
yet and have not added any testcases but it works on the testcase attached to
the bug.  I also have not checked what the performance increase on SPEC would
be.

[Bug tree-optimization/50204] [4.5/4.6/4.7 Regression] Missed fully redundant load found in crafty (SPEC 2k)

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-08-29 07:29:57 UTC ---
The loop over PHI args is a little hard to follow, but yeah, that's
how it should work.

Eventually we can put this in with a new --param telling the maximum
number of PHI args to consider (and defaulting it to two).  I'd probably
keep the n == 1 handling in the main function separately instead of
trying to handle it via the loop.  Then I'd pre-seed the first arg which
should make the loop a little easier to follow.

[Bug tree-optimization/50204] [4.5/4.6/4.7 Regression] Missed fully redundant load found in crafty (SPEC 2k)

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-08-29 07:57:29 UTC ---
On a 2nd thought the work should be still linear, even for N PHI args the
way the merging is constructed (one arg has to dominate the other - the
only exception is the diamond case which has a constant cost of two).

So with some cleanup (essentially peel the first iteration of the loop)
the patch should be ok as-is.

[Bug tree-optimization/50204] [4.5/4.6/4.7 Regression] Missed fully redundant load found in crafty (SPEC 2k)

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-10-10 12:28:19 UTC ---
Ping?  It would be nice to have this patch in 4.7 ...

[Bug tree-optimization/50204] [4.5/4.6/4.7 Regression] Missed fully redundant load found in crafty (SPEC 2k)

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> 2011-10-10 19:58:32 UTC ---
(In reply to comment #5)
> Ping?  It would be nice to have this patch in 4.7 ...

I cannot officially submit it until Cavium's assignment has been fully
submitted.

[Bug tree-optimization/50204] [4.5/4.6/4.7 Regression] Missed fully redundant load found in crafty (SPEC 2k)

[rguenther at suse dot de]

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

--- Comment #7 from rguenther at suse dot de <rguenther at suse dot de> 2011-10-10 20:48:40 UTC ---
On Mon, 10 Oct 2011, pinskia at gcc dot gnu.org wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50204
> 
> --- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> 2011-10-10 19:58:32 UTC ---
> (In reply to comment #5)
> > Ping?  It would be nice to have this patch in 4.7 ...
> 
> I cannot officially submit it until Cavium's assignment has been fully
> submitted.

Do you mind if I take over the patch?

[Bug tree-optimization/50204] [4.5/4.6/4.7 Regression] Missed fully redundant load found in crafty (SPEC 2k)

[pinskia at gcc dot gnu.org]

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

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> 2011-10-10 20:51:11 UTC ---
(In reply to comment #7)
> Do you mind if I take over the patch?

No I don't mind at all.

[Bug tree-optimization/50204] [4.5/4.6/4.7 Regression] Missed fully redundant load found in crafty (SPEC 2k)

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #9 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-10-11 09:01:47 UTC ---
Mine.

[Bug tree-optimization/50204] [4.5/4.6 Regression] Missed fully redundant load found in crafty (SPEC 2k)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
      Known to work|                            |4.7.0
         Resolution|                            |FIXED
   Target Milestone|4.5.4                       |4.7.0
            Summary|[4.5/4.6/4.7 Regression]    |[4.5/4.6 Regression] Missed
                   |Missed fully redundant load |fully redundant load found
                   |found in crafty (SPEC 2k)   |in crafty (SPEC 2k)
      Known to fail|4.7.0                       |

--- Comment #11 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-10-11 11:58:09 UTC ---
Fixed for 4.7, wontfix on release branches.

[Bug tree-optimization/50204] [4.5/4.6/4.7 Regression] Missed fully redundant load found in crafty (SPEC 2k)

[rguenth at gcc dot gnu.org]

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

--- Comment #10 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-10-11 11:57:28 UTC ---
Author: rguenth
Date: Tue Oct 11 11:57:23 2011
New Revision: 179799

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=179799
Log:
2011-10-11  Richard Guenther  <rguenther@suse.de>

    PR tree-optimization/50204
    * tree-ssa-alias.c (get_continuation_for_phi_1): Split out
    two argument handling from ...
    (get_continuation_for_phi): ... here.  Handle arbitrary number
    of PHI args.

    * gcc.dg/tree-ssa/ssa-fre-36.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-36.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-alias.c