[Bug c/59967] New: Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[Bug c/59967] New: Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[chbreitkopf at gmail dot com]

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

            Bug ID: 59967
           Summary: Performance regression from 4.7.x to 4.8.x (loop not
                    unrolled)
           Product: gcc
           Version: 4.8.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: chbreitkopf at gmail dot com

Created attachment 31967
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=31967&action=edit
preprocessed source of ray/src/rt/ambient.c

gcc 4.8.x generates 10-15% slower code compared to 4.7.x for Mark Stock's
radiance benchmark (http://markjstock.org/pages/rad_bench.html).

I observed this regression on Linux x86_64, and with different CPUs (Ivy
Bridge, Haswell, AMD Phenom, Kaveri). I had suspected the new register
allocator, but the actual cause is a difference in loop unrolling.

The hotspot is the nested loops with the recursive call at the end of the
sumambient() function. When using -Ofast, gcc 4.7.x will unroll the outer loop,
which results in some optimization possibilities in the inner loop. gcc 4.8.x
does not unroll the outer loop. -funroll-loops does not change the behavior.

[Bug tree-optimization/59967] [4.8/4.9 Regression] Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c                           |tree-optimization
      Known to work|                            |4.7.3
   Target Milestone|---                         |4.8.3
            Summary|Performance regression from |[4.8/4.9 Regression]
                   |4.7.x to 4.8.x (loop not    |Performance regression from
                   |unrolled)                   |4.7.x to 4.8.x (loop not
                   |                            |unrolled)
      Known to fail|                            |4.8.2

[Bug tree-optimization/59967] [4.8/4.9 Regression] Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[hubicka at ucw dot cz]

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

--- Comment #2 from Jan Hubicka <hubicka at ucw dot cz> ---
> 193246    hubicka       /* If there is call on a hot path through the loop,
> then
> 193246    hubicka        there is most probably not much to optimize.  */
> 193246    hubicka       else if (size.num_non_pure_calls_on_hot_path)
> 138522    rguenth       {
> 138522    rguenth         if (dump_file && (dump_flags & TDF_DETAILS))
> 193246    hubicka           fprintf (dump_file, "Not unrolling loop %d: "
> 193246    hubicka                    "contains call and code would grow.\n",
> 138522    rguenth                    loop->num);
> 138522    rguenth         return false;
> 138522    rguenth       }
> 
> so we conclude
> 
> size: 59-8, last_iteration: 52-5
>   Loop size: 59
>   Estimated size after unrolling: 269
> Not unrolling loop 2: contains call and code would grow.
> 
> so it was disabled on purpose.  Not sure if it's worth special-casing
> self-recursive calls the same as pure/const ones.

Not by the logic above, because self recursion is not really better understood
by optimizers than normal function calls.  I am surprised the unroling makes
10-15% difference in this case then. Is there something that makes the unrolled
loop to optimize better?

Honza

[Bug tree-optimization/59967] [4.8/4.9 Regression] Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[chbreitkopf at gmail dot com]

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

--- Comment #3 from Christoph Breitkopf <chbreitkopf at gmail dot com> ---
It's this conditional in the inner loop. The expression becomes constant only
if both loops are unrolled (i and j are the loop counters):

   if (1<<j & i)
    ck0[j] += s;

This condition is probably not perfectly predictable even by modern branch
predictors, so I assume this is the main reason for the regression.

Chris

[Bug tree-optimization/59967] [4.8/4.9/4.10 Regression] Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.8.3                       |4.8.4

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 4.8.3 is being released, adjusting target milestone.

[Bug tree-optimization/59967] [4.8/4.9/5 Regression] Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.8.4                       |4.8.5

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.8.4 has been released.

[Bug tree-optimization/59967] [4.8/4.9/5 Regression] Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
In the size estimation we have

 BB: 46, after_exit: 0
  size:   1 _319 = MEM[(double *)c0_188(D) + 16B];
  size:   1 _321 = i_171 >> 2;
   Constant expression will be folded away.
  size:   2 if (_321 != 0)

so somehow we fail to see that the conditional is constant after peeling.

Reworking things so we can use a lattice (also avoid calling simple_iv
too many times) will improve that (but also the code doesn't then
only consider MAX (taken-paths-lengths) in case there is an else block).
It looks like reworking this to do a domwalk may be profitable.

The simplistic approach gets us from an estimated size after unrolling
of to 238 (still that won't unroll the loop).  I think we should also
consider size->eliminated_by_peeling in the call heuristic - the
call itself might be a minor distraction and especially eliminated
branches might result in a good speed benefit.

That said, the core algorithm for likely-eliminated should be improved,
but it won't help by itself.

[Bug tree-optimization/59967] [4.8/4.9/5 Regression] Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Let's assign this to me for next stage1.

[Bug tree-optimization/59967] [4.8/4.9/5 Regression] Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
*** Bug 65207 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/59967] [4.8/4.9/5/6 Regression] Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.8.5                       |4.9.3

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
The gcc-4_8-branch is being closed, re-targeting regressions to 4.9.3.

[Bug tree-optimization/59967] [4.9/5/6 Regression] Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[jakub at gcc dot gnu.org]

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

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.3 has been released.

[Bug tree-optimization/59967] [4.9/5/6 Regression] Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.3                       |4.9.4

[Bug tree-optimization/59967] [4.9/5/6 Regression] Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bdeyal at gmail dot com

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
*** Bug 66263 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/59967] [9/10/11/12 Regression] Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|8.5                         |9.4

--- Comment #18 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 8 branch is being closed.

[Bug tree-optimization/59967] [9/10/11/12 Regression] Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|9.4                         |9.5

--- Comment #19 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 9.4 is being released, retargeting bugs to GCC 9.5.

[Bug tree-optimization/59967] [10/11/12/13 Regression] Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|9.5                         |10.4

--- Comment #20 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 9 branch is being closed

[Bug tree-optimization/59967] [10/11/12/13 Regression] Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|10.4                        |10.5

--- Comment #21 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 10.4 is being released, retargeting bugs to GCC 10.5.

[Bug tree-optimization/59967] [11/12/13/14 Regression] Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|10.5                        |11.5

--- Comment #22 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 10 branch is being closed.

[Bug tree-optimization/59967] [11/12/13/14 Regression] Performance regression from 4.7.x to 4.8.x (loop not unrolled)

[pinskia at gcc dot gnu.org]

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

--- Comment #23 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
One thing unrelated to the unrolling I Noticed is:
```
  if (_221 != 0)
    goto <bb 50>; [50.00%]
  else
    goto <bb 49>; [50.00%]

  <bb 49> [local count: 163152564]:
  _212 = _218 - s_202;
  goto <bb 51>; [100.00%]

  <bb 50> [local count: 163152564]:
  _222 = s_202 + _218;

  <bb 51> [local count: 326305128]:
  # ck0$0_144 = PHI <_218(49), _222(50)>
  # prephitmp_211 = PHI <_212(49), _218(50)>
```

Does not use conditional moves on aarch64 (or x86_64) even though it
could/should.
That pattern shows up 3 times due to the unrolling of the inner loop there.
```
   ck0[j] = c0[j];
   if (1<<j & i)
    ck0[j] += s;
   if (r->rop[j] < ck0[j] - 1.0*s)
```