[Bug regression/39839] New: [4.3/4.4/4.5 regression] loop invariant motion causes stack spill

[Bug regression/39839] New: [4.3/4.4/4.5 regression] loop invariant motion causes stack spill

[alexvod at google dot com]

The following code:
struct S
{
  int count;
  char *addr;
};

void func(const char*, const char*, int, const char*);

void test(struct S *p)
{
  int off = p->count;
  while (p->count >= 0)
    {
      const char *s = "xyz";
      if (*p->addr) s = "pqr";
      func("abcde", p->addr + off, off, s);
      p->count--;
    }
}

is compiled by GCC 4.2.1 to 64 bytes, and by GCC 4.4.0 to 76 bytes. Bisection
shows that size is increased several times:
123918 -> 123919: 64 -> 72
124041 -> 124042: 72 -> 76
I already filed a bug for 123919
(http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39837), so let's take a look at
http://gcc.gnu.org/viewcvs?view=rev&revision=124042

GCC rev124041 (with -march=armv5te -mthumb -mthumb-interwork -fpic -Os)
test:
        push    {r4, r5, r6, r7, lr}
        ldr     r3, .L9
        ldr     r2, .L9+4
.LPIC0:
        add     r3, pc
        add     r7, r3, r2
        ldr     r2, .L9+8
        ldr     r5, [r0]
        sub     sp, sp, #4
        mov     r4, r0
        add     r6, r3, r2
        b       .L2
.L3:
        ldr     r0, [r4, #4]
        ldrb    r3, [r0]
        cmp     r3, #0
        beq     .L4
        mov     r2, r6
        b       .L6
.L4:
        mov     r2, r7
.L6:
        add     r0, r0, r5
        lsl     r1, r5, #1
        bl      func
        ldr     r3, [r4]
        sub     r3, r3, #1
        str     r3, [r4]
.L2:
        ldr     r3, [r4]
        cmp     r3, #0
        bge     .L3
        add     sp, sp, #4
        @ sp needed for prologue
        pop     {r4, r5, r6, r7, pc}
.L10:

GCC rev124042:
test:
        push    {r4, r5, r6, r7, lr}
        ldr     r3, .L9
        ldr     r2, .L9+4
.LPIC0:
        add     r3, pc
        add     r2, r3, r2
        sub     sp, sp, #12
        ldr     r5, [r0]
        str     r2, [sp, #4]
        ldr     r2, .L9+8
        mov     r4, r0
        lsl     r6, r5, #1
        add     r7, r3, r2
        b       .L2
.L3:
        ldr     r0, [r4, #4]
        ldrb    r3, [r0]
        cmp     r3, #0
        beq     .L4
        mov     r2, r7
        b       .L6
.L4:
        ldr     r2, [sp, #4]
.L6:
        add     r0, r0, r5
        mov     r1, r6
        bl      func
        ldr     r3, [r4]
        sub     r3, r3, #1
        str     r3, [r4]
.L2:
        ldr     r3, [r4]
        cmp     r3, #0
        bge     .L3
        add     sp, sp, #12
        @ sp needed for prologue
        pop     {r4, r5, r6, r7, pc}

The first different dump is 090t.lim, which moves (off << 1) out of the loop.
But this extra variable causes extra stack spill, so it actually a loss, not a
win. Any ideas about what to tweak?


-- 
           Summary: [4.3/4.4/4.5 regression] loop invariant motion causes
                    stack spill
           Product: gcc
           Version: 4.4.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: regression
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: alexvod at google dot com
 GCC build triplet: x86_64-unknown-linux-gnu
  GCC host triplet: x86_64-unknown-linux-gnu
GCC target triplet: arm-eabi


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

[Bug tree-optimization/39839] [4.3/4.4/4.5 regression] loop invariant motion causes stack spill

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2009-04-22 09:39 -------
Implement re-materialization in reload.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|regression                  |tree-optimization
           Keywords|                            |missed-optimization
   Target Milestone|---                         |4.3.4


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

[Bug tree-optimization/39839] [4.3/4.4/4.5 regression] loop invariant motion causes stack spill

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2009-04-22 13:39 -------
Vlad, with YARA you had implemented rematerialization, right?  How difficult is
it to do the same with IRA for cases like this?


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |vmakarov at redhat dot com
           Priority|P3                          |P2


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

[Bug tree-optimization/39839] [4.3/4.4/4.5 regression] loop invariant motion causes stack spill

[vmakarov at redhat dot com]

------- Comment #3 from vmakarov at redhat dot com  2009-04-22 20:37 -------
Actually YARA did not have a rematerialization as IRA.  Reload has a primitive
rematerialization of constant values.

Although about 5 years I did implemented a register pressure relief through
rematerialization which is close to Simpson's thesis.  It was reported on the
2nd GCC summit.  I had a mixed feeling about this: wrong register pressure
calculation (because we have not cover classes at that time), small improvement
but a few additional percents to compilation time.

Probably it is time to return to this and make it optional or default which
will eat a chunk of your recent 5% compilation time improvement :)  I'll try to
include this in my plans.


-- 


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

[Bug tree-optimization/39839] [4.3/4.4/4.5 regression] loop invariant motion causes stack spill

[ramana at gcc dot gnu dot org]

-- 

ramana at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2009-05-20 14:17:11
               date|                            |


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

[Bug tree-optimization/39839] [4.3/4.4/4.5 regression] loop invariant motion causes stack spill

[bonzini at gnu dot org]

------- Comment #4 from bonzini at gnu dot org  2009-06-15 16:26 -------
Someone can please check if this is still a problem in 4.5?


-- 

bonzini at gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bonzini at gnu dot org


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

[Bug tree-optimization/39839] [4.3/4.4/4.5 regression] loop invariant motion causes stack spill

[steven at gcc dot gnu dot org]

------- Comment #5 from steven at gcc dot gnu dot org  2009-06-22 16:29 -------
How is this different from bug 39837?


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
OtherBugsDependingO|                            |16996
              nThis|                            |


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

[Bug tree-optimization/39839] [4.3/4.4/4.5 regression] loop invariant motion causes stack spill

[rguenth at gcc dot gnu dot org]

------- Comment #6 from rguenth at gcc dot gnu dot org  2009-08-04 12:30 -------
GCC 4.3.4 is being released, adjusting target milestone.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.4                       |4.3.5


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

[Bug tree-optimization/39839] [4.3/4.4/4.5 regression] loop invariant motion causes stack spill

[steven at gcc dot gnu dot org]

------- Comment #7 from steven at gcc dot gnu dot org  2010-01-02 00:49 -------
With "GCC: (GNU) 4.5.0 20090808 (experimental) [trunk revision 150579]" I get:

        .arch armv5te
        .fpu softvfp
        .eabi_attribute 20, 1
        .eabi_attribute 21, 1
        .eabi_attribute 23, 3
        .eabi_attribute 24, 1
        .eabi_attribute 25, 1
        .eabi_attribute 26, 1
        .eabi_attribute 30, 4
        .eabi_attribute 18, 4
        .code   16
        .file   "t.c"
        .text
        .align  1
        .global test
        .code   16
        .thumb_func
        .type   test, %function
test:
        push    {r3, r4, r5, r6, r7, lr}
        ldr     r3, .L7
        ldr     r5, .L7+4
.LPIC0:
        add     r3, pc
        add     r5, r3, r5
        mov     r7, r5
        mov     r4, r0
        ldr     r6, [r0]
        add     r7, r7, #8
        b       .L2
.L4:
        ldr     r1, [r4, #4]
        ldrb    r3, [r1]
        cmp     r3, #0
        bne     .L5
        mov     r3, r5
        b       .L3
.L5:
        add     r3, r5, #4
.L3:
        add     r1, r1, r6
        mov     r0, r7
        mov     r2, r6
        bl      func
        ldr     r3, [r4]
        sub     r3, r3, #1
        str     r3, [r4]
.L2:
        ldr     r3, [r4]
        cmp     r3, #0
        bge     .L4
        @ sp needed for prologue
        pop     {r3, r4, r5, r6, r7, pc}
.L8:
       .align  2
.L7:
        .word   _GLOBAL_OFFSET_TABLE_-(.LPIC0+4)
        .word   .LANCHOR0(GOTOFF)
        .size   test, .-test
        .section        .rodata
        .set    .LANCHOR0,. + 0
.LC0:
        .ascii  "xyz\000"
.LC1:
        .ascii  "pqr\000"
.LC2:
        .ascii  "abcde\000"
        .ident  "GCC: (GNU) 4.5.0 20090808 (experimental) [trunk revision
150579]"


I have no idea whether that is better or worse. Alexander, could you give this
a look please?


-- 


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

[Bug tree-optimization/39839] [4.3/4.4/4.5 regression] loop invariant motion causes stack spill

[rguenth at gcc dot gnu dot org]

------- Comment #8 from rguenth at gcc dot gnu dot org  2010-01-02 11:18 -------
You may also want to try -fsched-pressure -fschedule-insns which is new
in GCC 4.5 and might decrease register pressure (no idea if it ever moves
things into loops though - the haifa scheduler might not consider it a
region to work on).


-- 


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

[Bug tree-optimization/39839] [4.3/4.4/4.5/4.6 regression] loop invariant motion causes stack spill

[rguenth at gcc dot gnu dot org]

------- Comment #9 from rguenth at gcc dot gnu dot org  2010-05-22 18:13 -------
GCC 4.3.5 is being released, adjusting target milestone.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.5                       |4.3.6


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

[Bug tree-optimization/39839] [4.3/4.4/4.5/4.6 regression] loop invariant motion causes stack spill

[sandra at codesourcery dot com]

------- Comment #10 from sandra at codesourcery dot com  2010-06-22 16:26 -------
It looks like this bug has been fixed by my proposed patch for PR42505:

http://gcc.gnu.org/ml/gcc-patches/2010-06/msg01920.html

Applying that patch to r160755 gives:

00000000 <test>:
   0:   b570            push    {r4, r5, r6, lr}
   2:   4d0c            ldr     r5, [pc, #48]   ; (34 <test+0x34>)
   4:   1c04            adds    r4, r0, #0
   6:   6806            ldr     r6, [r0, #0]
   8:   447d            add     r5, pc
   a:   e00f            b.n     2c <test+0x2c>
   c:   6861            ldr     r1, [r4, #4]
   e:   1c2b            adds    r3, r5, #0
  10:   780a            ldrb    r2, [r1, #0]
  12:   2a00            cmp     r2, #0
  14:   d101            bne.n   1a <test+0x1a>
  16:   4b08            ldr     r3, [pc, #32]   ; (38 <test+0x38>)
  18:   447b            add     r3, pc
  1a:   4808            ldr     r0, [pc, #32]   ; (3c <test+0x3c>)
  1c:   1989            adds    r1, r1, r6
  1e:   4478            add     r0, pc
  20:   1c32            adds    r2, r6, #0
  22:   f7ff fffe       bl      0 <func>
  26:   6823            ldr     r3, [r4, #0]
  28:   3b01            subs    r3, #1
  2a:   6023            str     r3, [r4, #0]
  2c:   6823            ldr     r3, [r4, #0]
  2e:   2b00            cmp     r3, #0
  30:   daec            bge.n   c <test+0xc>
  32:   bd70            pop     {r4, r5, r6, pc}
  34:   00000028        .word   0x00000028
  38:   0000001c        .word   0x0000001c
  3c:   0000001a        .word   0x0000001a

So, back down to 64 bytes of code, and no spills to stack.

Assuming the PR42505 patch is approved, probably the only thing required to
close this issue is checking in the additional test case.


-- 

sandra at codesourcery dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |sandra at codesourcery dot
                   |                            |com


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

[Bug tree-optimization/39839] [4.3/4.4/4.5/4.6 regression] loop invariant motion causes stack spill

[bonzini at gnu dot org]

------- Comment #11 from bonzini at gnu dot org  2010-06-22 17:28 -------
That would be WONTFIX for 4.5 and earlier, right?  4.4 and earlier are
definitely out of question, but maybe your patch alone gives the same effect on
4.5 branch too, without any of the other ivopts and ARM improvements that
recently went into 4.6?


-- 

bonzini at gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |42505


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

[Bug tree-optimization/39839] [4.3/4.4/4.5/4.6 regression] loop invariant motion causes stack spill

[sandra at codesourcery dot com]

------- Comment #12 from sandra at codesourcery dot com  2010-06-22 18:02 -------
Hrmmm, I was planning to attempt a 4.5 backport of the PR42505 patch for
internal use, but if it's not easy or doesn't help, I think I have better
things to do with my time than to try to come up with some other fix.  ;-)  So,
let's wait and see.


-- 


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

[Bug tree-optimization/39839] [4.3/4.4/4.5/4.6 regression] loop invariant motion causes stack spill

[sandra at codesourcery dot com]

------- Comment #13 from sandra at codesourcery dot com  2010-07-11 01:22 -------
Some further analysis:

The part of my PR42505 patch that made the difference was the change to
estimate_register_pressure_cost in cfgloopanal.c, to make it exclude the
call-clobbered registers.  This part was finally committed separately in a
revised version as r162043.

I'm still looking into what to do about the test case and 4.5 backport.


-- 


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

[Bug tree-optimization/39839] [4.3/4.4/4.5/4.6 regression] loop invariant motion causes stack spill

[sandra at codesourcery dot com]

------- Comment #14 from sandra at codesourcery dot com  2010-07-13 16:13 -------
There are two patches that made the difference:  r158189 (Carrot's patch for
PR42601) and r162043 (the second part of my patch for PR42505).  I checked that
backporting these two changes to the 4.5 branch is sufficient to fix the code
size regression on this example there, too.

I posted the test case patch here:
http://gcc.gnu.org/ml/gcc-patches/2010-07/msg01070.html


-- 


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

[Bug tree-optimization/39839] [4.3/4.4/4.5/4.6 regression] loop invariant motion causes stack spill

[sandra at gcc dot gnu dot org]

------- Comment #15 from sandra at gcc dot gnu dot org  2010-07-23 02:18 -------
Subject: Bug 39839

Author: sandra
Date: Fri Jul 23 02:18:07 2010
New Revision: 162438

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=162438
Log:
2010-07-22  Sandra Loosemore  <sandra@codesourcery.com>

        PR tree-optimization/39839

        gcc/testsuite/
        * gcc.target/arm/pr39839.c: New test case.

Added:
    trunk/gcc/testsuite/gcc.target/arm/pr39839.c
Modified:
    trunk/gcc/testsuite/ChangeLog


-- 


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

[Bug tree-optimization/39839] [4.3/4.4/4.5/4.6 regression] loop invariant motion causes stack spill

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.6                       |4.4.7

--- Comment #18 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-06-27 12:14:33 UTC ---
4.3 branch is being closed, moving to 4.4.7 target.

[Bug tree-optimization/39839] [4.3/4.4/4.5/4.6 regression] loop invariant motion causes stack spill

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.7.0
            Summary|[4.3/4.4/4.5/4.6/4.7        |[4.3/4.4/4.5/4.6
                   |regression] loop invariant  |regression] loop invariant
                   |motion causes stack spill   |motion causes stack spill

--- Comment #17 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-06-24 17:11:01 UTC ---
At least for 4.7 it seems.