[Bug tree-optimization/48732] New: Nested loops with small iteration count gobble time in "tree reassociation"

[Bug tree-optimization/48732] New: Nested loops with small iteration count gobble time in "tree reassociation"

[arthur.j.odwyer at gmail dot com]

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

           Summary: Nested loops with small iteration count gobble time in
                    "tree reassociation"
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: arthur.j.odwyer@gmail.com


Created attachment 24076
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24076
Output of "gcc-4.5 -w -O1 -S test.c -Q -v"

The following test case takes inordinately long to compile on my machine
(Ubuntu 10.10, 64-bit), starting with gcc-4.5.

cat >test.c <<EOF
void func_47()
{
  int a, b, c, d, e;
  for (a=0; a < 8; ++a) {
    for (b=0; b < 8; ++b) {
      for (c=0; c < 8; ++c) {
        for (d=0; d < 8; ++d) {
          int l_752[8];
          int j;
          for (j = 0; j < 8; j++)
            l_752[j] = 0;
        }
      }
    }
  }
}
EOF
time gcc -w -O1 -S test.c -Q

On my machine, the timings are as follows:
With gcc-4.4: real 0.027s
With gcc-4.5: real 5.801s, spent 94% of that time in "tree reassociation"
With trunk:   real 3.567s, spent 77% of that time in "tree reassociation"

The only difference in the assembly output is that gcc-4.4 uses "ret" and
gcc-4.5 uses "rep ret".
Adding a fifth nested loop with 8 iterations makes compilation take more than
300 seconds; I killed it at that point.

[Bug tree-optimization/48732] Nested loops with small iteration count gobble time in "tree reassociation"

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2011.04.23 09:14:50
         AssignedTo|unassigned at gcc dot       |rguenth at gcc dot gnu.org
                   |gnu.org                     |
     Ever Confirmed|0                           |1

--- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-04-23 09:14:50 UTC ---
I will have a look.

[Bug tree-optimization/48732] Nested loops with small iteration count gobble time in "tree reassociation"

[rguenth at gcc dot gnu.org]

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

--- Comment #2 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-04-26 12:13:50 UTC ---
With -O1 we do not perform expensive control-dependend DCE and thus do not
end up removing the empty loops.  We do however remove the dead store in
the innermost loop which then causes us to compute that completely unrolling
all loops is profitable (we basically see it's all dead code that will be
produced).  Now, unfortunately before removing all that dead code we perform
re-association on the induction variable increment chains ... of which there
are a lot (8 ^ n ones and more, actually).

We've known for quite some time that not doing constant propagation and
dead code elimination on the unrolled loop bodies isn't the best idea
(induction variable analysis is also pessimized by not doing CSE on those).

The only CCP-like pass after loop opts is VRP which does not run at -O2,
or DOM and both runs after re-assoc (though I don't see a particularly good
reason for that fact).

Scheduling DOM right after loop opts "fixes" this.  But a more proper fix
would be to do cleanups closer to unrolling.

[Bug tree-optimization/48732] Nested loops with small iteration count gobble time in "tree reassociation"

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
      Known to work|                            |4.8.0
         Resolution|---                         |FIXED
   Target Milestone|---                         |4.8.0
      Known to fail|                            |4.5.4, 4.6.4, 4.7.4

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed for 4.8 where we now do a simple CCP from inside the GIMPLE unrolling
code.