[Bug rtl-optimization/42502] New: Bad register allocation in a very simple code

[Bug rtl-optimization/42502] New: Bad register allocation in a very simple code

[sliao at google dot com]

The following code

// compilation options: -march=armv5te -mthumb -Os
struct node
{
 long long a;
 long long b;
};

void func (struct node *n);

long long test (int from, int to)
{
 struct node n;
 func(&n);
 if (from == 1)
   return n.a;
 else
   {
     if (to == 2)
       return n.b;
     else
       return n.b - n.a;
   }
}

is compiled by gcc 4.2.1 to 44 bytes, and gcc 4.4.0 to 60 bytes. Assembly files
shows 6 unneeded movs in the else clause and duplication of sp in r4:

gcc 4.2.1 output:
test:
       push    {r4, r5, lr}
       sub     sp, sp, #20
       mov     r4, r0
       mov     r0, sp
       mov     r5, r1
       bl      func
       cmp     r4, #1
       bne     .L2
       ldr     r0, [sp]
       ldr     r1, [sp, #4]
       b       .L4
.L2:
       ldr     r0, [sp, #8]
       ldr     r1, [sp, #12]
       cmp     r5, #2
       beq     .L4
       ldr     r3, [sp]
       ldr     r4, [sp, #4]
       sub     r0, r0, r3
       sbc     r1, r1, r4
.L4:
       add     sp, sp, #20
       @ sp needed for prologue
       pop     {r4, r5, pc}

gcc 4.4 output:
test:
       push    {r4, r5, r6, lr}
       sub     sp, sp, #16
       mov     r5, r0
       mov     r0, sp
       mov     r6, r1
       mov     r4, sp    // why duplicate sp in r4? sp is never modified in the
function
       bl      func
       cmp     r5, #1
       bne     .L2
       ldr     r3, [sp]
       ldr     r4, [sp, #4]
       b       .L3
.L2:
       ldr     r2, [r4, #8]
       ldr     r3, [r4, #12]
       cmp     r6, #2
       bne     .L4
       mov     r4, r3  // the magic dance of the registers
       mov     r3, r2
       b       .L3
.L4:
       ldr     r0, [r4]
       ldr     r1, [r4, #4]
       mov     r4, r3  // another magic dance
       mov     r3, r2
       sub     r3, r3, r0
       sbc     r4, r4, r1
.L3:
       add     sp, sp, #16
       mov     r0, r3   // again, unneeded movs.
       mov     r1, r4   // result can be calculated in r0,r1 directly (see gcc
4.2.1 version)
       @ sp needed for prologue
       pop     {r4, r5, r6, pc}

The code was extracted from GCC SPEC benchmark.


-- 
           Summary: Bad register allocation in a very simple code
           Product: gcc
           Version: 4.4.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: sliao at google dot com
 GCC build triplet: i686-linux
  GCC host triplet: i686-linux
GCC target triplet: arm-eabi


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

[Bug rtl-optimization/42502] Bad register allocation in a very simple code

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2009-12-31 15:28 -------
Please try with trunk.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization, ra


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

[Bug rtl-optimization/42502] Bad register allocation in a very simple code

[sliao at google dot com]

------- Comment #2 from sliao at google dot com  2010-01-07 13:28 -------
Using flags, -march=armv5te -mthumb -Os, GCC 4.5.0 (trunk) generates the
following code:

00000000 <test>:
   0:    b570          push    {r4, r5, r6, lr}
   2:    b084          sub    sp, #16
   4:    1c05          adds    r5, r0, #0
   6:    4668          mov    r0, sp
   8:    1c0e          adds    r6, r1, #0
   a:    466c          mov    r4, sp
   c:    f7ff fffe     bl    0 <func>
  10:    2d01          cmp    r5, #1
  12:    d102          bne.n    1a <func+0x1a>
  14:    9b00          ldr    r3, [sp, #0]
  16:    9c01          ldr    r4, [sp, #4]
  18:    e00c          b.n    34 <func+0x34>
  1a:    68a2          ldr    r2, [r4, #8]
  1c:    68e3          ldr    r3, [r4, #12]
  1e:    2e02          cmp    r6, #2
  20:    d102          bne.n    28 <func+0x28>
  22:    1c1c          adds    r4, r3, #0
  24:    1c13          adds    r3, r2, #0
  26:    e005          b.n    34 <func+0x34>
  28:    6820          ldr    r0, [r4, #0]
  2a:    6861          ldr    r1, [r4, #4]
  2c:    1c1c          adds    r4, r3, #0
  2e:    1c13          adds    r3, r2, #0
  30:    1a1b          subs    r3, r3, r0
  32:    418c          sbcs    r4, r1
  34:    b004          add    sp, #16
  36:    1c18          adds    r0, r3, #0
  38:    1c21          adds    r1, r4, #0
  3a:    bd70          pop    {r4, r5, r6, pc}
----------------------------------------------------

GCC 4.2.1 generates the following code:

00000000 <test>:
   0:    b530          push    {r4, r5, lr}
   2:    b085          sub    sp, #20
   4:    1c04          adds    r4, r0, #0
   6:    4668          mov    r0, sp
   8:    1c0d          adds    r5, r1, #0
   a:    f7ff fffe     bl    0 <func>
   e:    2c01          cmp    r4, #1
  10:    d102          bne.n    18 <func+0x18>
  12:    9800          ldr    r0, [sp, #0]
  14:    9901          ldr    r1, [sp, #4]
  16:    e007          b.n    28 <func+0x28>
  18:    9802          ldr    r0, [sp, #8]
  1a:    9903          ldr    r1, [sp, #12]
  1c:    2d02          cmp    r5, #2
  1e:    d003          beq.n    28 <func+0x28>
  20:    9b00          ldr    r3, [sp, #0]
  22:    9c01          ldr    r4, [sp, #4]
  24:    1ac0          subs    r0, r0, r3
  26:    41a1          sbcs    r1, r4
  28:    b005          add    sp, #20
  2a:    bd30          pop    {r4, r5, pc}
------------------------------------------------------

GCC 4.2.1's code size is still smaller than GCC 4.5.0, and GCC 4.5.0's
generated code is similar to GCC 4.4.

I think it's still an issue in the trunk now.

For completeness sake, the source code is:
struct node
{
 long long a;
 long long b;
};

void func (struct node *n);

long long test (int from, int to)
{
 struct node n;
 func(&n);
 if (from == 1)
   return n.a;
 else
   {
     if (to == 2)
       return n.b;
     else
       return n.b - n.a;
   }
}


-- 


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

[Bug rtl-optimization/42502] Bad register allocation in a very simple code

[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         |2010-01-12 09:36:39
               date|                            |


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

[Bug rtl-optimization/42502] Bad register allocation in a very simple code

[steven at gcc dot gnu dot org]

------- Comment #3 from steven at gcc dot gnu dot org  2010-02-08 12:49 -------
The duplication of sp in r4 is tracked in a separate bug report, bug 42500.


-- 


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

[Bug rtl-optimization/42502] [4.4/4.5 Regression] Bad register allocation in a very simple code

[steven at gcc dot gnu dot org]

------- Comment #4 from steven at gcc dot gnu dot org  2010-02-10 11:01 -------
This is a regression, so let's mark it as such.

Shin-wei, is it possible for you check what GCC 4.3 does. Bonus if you can
check a 4.4 snapshot from just before and just after IRA was merged.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|sliao at google dot com     |
      Known to fail|                            |4.4.0 4.5.0
      Known to work|                            |4.2.1
   Last reconfirmed|2010-01-12 09:36:39         |2010-02-10 11:01:00
               date|                            |
            Summary|Bad register allocation in a|[4.4/4.5 Regression] Bad
                   |very simple code            |register allocation in a
                   |                            |very simple code


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

[Bug rtl-optimization/42502] [4.4/4.5 Regression] Bad register allocation in a very simple code

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.4.4


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

[Bug rtl-optimization/42502] [4.4/4.5 Regression] Bad register allocation in a very simple code

[mmitchel at gcc dot gnu dot org]

-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2


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

[Bug rtl-optimization/42502] [4.4/4.5 Regression] Bad register allocation in a very simple code

[cltang at pllab dot cs dot nthu dot edu dot tw]

------- Comment #5 from cltang at pllab dot cs dot nthu dot edu dot tw  2010-02-25 16:01 -------
The cause seems to be the subreg lowering pass, the returning of the DImode
value is split into:

(insn 46 32 47 7 c.c:23 (set (reg:SI 0 r0)
        (subreg:SI (reg:DI 133 [ D.2015 ]) 0)) 167 {*thumb1_movsi_insn} (nil))

(insn 47 46 40 7 c.c:23 (set (reg:SI 1 r1 [+4 ])
        (subreg:SI (reg:DI 133 [ D.2015 ]) 4)) 167 {*thumb1_movsi_insn}
(expr_list:REG_DEAD (reg:DI 133 [ D.2015 ])
        (nil)))

As the IRA dumps show, this splitting into two insns causes r0 to conflict with
the lifetime of r133, preventing it to be assigned to r0-r1 and coalesced.

I don't have a patch for this, but I found turning off the subreg lowering by
-fno-split-wide-types retains the DImode return:

(insn 37 32 40 7 c.c:23 (set (reg/i:DI 0 r0)
        (reg:DI 133 [ D.2015 ])) 164 {*thumb1_movdi_insn} (expr_list:REG_DEAD
(reg:DI 133 [ D.2015 ])
        (nil)))

and generates:
        push    {r4, r5, r6, lr}
        sub     sp, sp, #16
        mov     r5, r0
        mov     r0, sp
        mov     r6, r1
        mov     r4, sp
        bl      func
        cmp     r5, #1
        bne     .L2
        ldr     r0, [sp]
        ldr     r1, [sp, #4]
        b       .L3
.L2:
        ldr     r0, [r4, #8]
        ldr     r1, [r4, #12]
        cmp     r6, #2
        beq     .L3
        ldr     r3, [r4]
        ldr     r4, [r4, #4]
        sub     r0, r0, r3
        sbc     r1, r1, r4
.L3:
        add     sp, sp, #16
        @ sp needed for prologue
        pop     {r4, r5, r6, pc}

which should be similar to what 4.2.1 generated.
The sp duplication in r4, as mentioned by others, is another problem.


-- 


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

[Bug rtl-optimization/42502] [4.4/4.5 Regression] Bad register allocation in a very simple code

[bernds at codesourcery dot com]

------- Comment #6 from bernds at codesourcery dot com  2010-03-15 23:44 -------
I'm testing a fwprop patch that fixes the problem except for two unnecessary
movs at the end.


-- 

bernds at codesourcery dot com changed:

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


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

[Bug rtl-optimization/42502] [4.4/4.5/4.6 Regression] Bad register allocation in a very simple code

[jakub at gcc dot gnu dot org]

-- 

jakub at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.4.4                       |4.4.5


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

[Bug rtl-optimization/42502] [4.4/4.5/4.6 Regression] Bad register allocation in a very simple code

[bernds at gcc dot gnu dot org]

------- Comment #7 from bernds at gcc dot gnu dot org  2010-06-04 12:44 -------
Subject: Bug 42502

Author: bernds
Date: Fri Jun  4 12:44:01 2010
New Revision: 160260

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=160260
Log:
        PR rtl-optimization/39871
        PR rtl-optimization/40615
        PR rtl-optimization/42500
        PR rtl-optimization/42502
        * ira.c (init_reg_equiv_memory_loc: New function.
        (ira): Call it twice.
        * reload.h (calculate_elim_costs_all_insns): Declare.
        * ira-costs.c: Include "reload.h".
        (regno_equiv_gains): New static variable.
        (init_costs): Allocate it.
        (finish_costs): Free it.
        (ira_costs): Call calculate_elim_costs_all_insns.
        (find_costs_and_classes): Take estimated elimination costs
        into account.
        (ira_adjust_equiv_reg_cost): New function.
        * ira.h (ira_adjust_equiv_reg_cost): Declare it.
        * reload1.c (init_eliminable_invariants, free_reg_equiv,
        elimination_costs_in_insn, note_reg_elim_costly): New static
        functions.
        (elim_bb): New static variable.
        (reload): Move code out of here into init_eliminable_invariants and
        free_reg_equiv.  Call them.
        (calculate_elim_costs_all_insns): New function.
        (eliminate_regs_1): Declare.  Add extra arg FOR_COSTS;
        all callers changed.  If FOR_COSTS is true, don't call alter_reg,
        but call note_reg_elim_costly if we turned a valid memory address
        into an invalid one.
        * Makefile.in (ira-costs.o): Depend on reload.h.

testsuite/
        PR rtl-optimization/39871
        PR rtl-optimization/40615
        PR rtl-optimization/42500
        PR rtl-optimization/42502
        * gcc.target/arm/eliminate.c: New test.


Added:
    trunk/gcc/testsuite/gcc.target/arm/eliminate.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/Makefile.in
    trunk/gcc/ira-costs.c
    trunk/gcc/ira.c
    trunk/gcc/ira.h
    trunk/gcc/reload.h
    trunk/gcc/reload1.c
    trunk/gcc/testsuite/ChangeLog


-- 


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