[Bug tree-optimization/57186] New: implement load sinking in loops

[Bug tree-optimization/57186] New: implement load sinking in loops

[ebotcazou at gcc dot gnu.org]

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

             Bug #: 57186
           Summary: implement load sinking in loops
    Classification: Unclassified
           Product: gcc
           Version: 4.9.0
               URL: http://gcc.gnu.org/ml/gcc-patches/2012-10/msg00742.htm
                    l
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: ebotcazou@gcc.gnu.org


Created attachment 30040
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30040
Original implementation

Even at -O3, the compiler doesn't figure out that the following loop is dumb:

#define SIZE 64

int foo (int v[])
{
  int r;

  for (i = 0; i < SIZE; i++)
    r = v[i];

  return r;
}

This isn't entirely unexpected, as it probably matters only for (slightly)
pathological cases.  The attached patch nevertheless implements a form of load
sinking in loops so as to optimize these cases.  It's combined with invariant
motion to optimize:

int foo (int v[], int a)
{
  int r, i;

  for (i = 0; i < SIZE; i++)
    r = v[i] + a;

  return r;
}

and with store sinking to optimize:

int foo (int v1[], int v2[])
{
  int r[SIZE];
  int i, j;

  for (j = 0; j < SIZE; j++)
    for (i = 0; i < SIZE; i++)
      r[j] = v1[j] + v2[i];

  return r[SIZE - 1];
}

The optimization is enabled at -O2 in the patch for measurement purposes but, 
given how rarely it triggers (e.g. exactly 10 occurrences in a GCC bootstrap, 
compiler-only, all languages except Go), it's probably best suited to -O3.

It also comes with 3 testcases.

[Bug tree-optimization/57186] implement load sinking in loops

[ebotcazou at gcc dot gnu.org]

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

--- Comment #1 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2013-05-06 14:51:30 UTC ---
Created attachment 30041
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30041
Testcase #1

[Bug tree-optimization/57186] implement load sinking in loops

[ebotcazou at gcc dot gnu.org]

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

--- Comment #3 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2013-05-06 14:52:25 UTC ---
Created attachment 30043
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30043
Testcase #3

[Bug tree-optimization/57186] implement load sinking in loops

[ebotcazou at gcc dot gnu.org]

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

--- Comment #2 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2013-05-06 14:51:58 UTC ---
Created attachment 30042
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30042
Testcase #2

[Bug tree-optimization/57186] implement load sinking in loops

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-05-07
                 CC|                            |rguenth at gcc dot gnu.org
     Ever Confirmed|0                           |1

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> 2013-05-07 09:02:48 UTC ---
In theory we have the SCCP patch to address at least case #1.  It looks
at loop exit PHIs and tries to replace them with the overall effect of
the loop (using SCEV analysis, which is why it fails for loads).

  <bb 4>:
  # i_15 = PHI <i_10(3), 0(2)>
  _4 = (long unsigned int) i_15;
  _5 = _4 * 4;
  _7 = v_6(D) + _5;
  r_9 = *_7;
  i_10 = i_15 + 1;
  if (i_10 != 64)
    goto <bb 3>;
  else
    goto <bb 5>;

  <bb 5>:
  # r_20 = PHI <r_9(4)>

the complication with handling the above in existing passes (for example
code sinking) is that the final value of _7 is needed to sink the dependent
computations.  So I think what SCCP should do here is look at the
single-use chain from the defs of r_20 and analyze the evolution of
the dependent loop variant SSA names, performing sinking of the dependencies
as well.  Conveniently LIM runs before SCCP and performs the necessary
store sinking to allow handling of the last case.

[Bug tree-optimization/57186] implement load sinking in loops

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |5.0
         Resolution|---                         |FIXED
             Status|NEW                         |RESOLVED

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Fixed in GCC 5 by r5-1146 .