[Bug rtl-optimization/57540] New: stack pointer related loop invariants after reload

[Bug rtl-optimization/57540] New: stack pointer related loop invariants after reload

[amker.cheng at gmail dot com]

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

            Bug ID: 57540
           Summary: stack pointer related loop invariants after reload
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: amker.cheng at gmail dot com

For below program,

void foo ( unsigned char *len,
                         int alphaSize,
                         int maxLen )
{
   int i, j, k;
   unsigned char tooLong;

   int parent [ 258 * 2 ];


      parent[0] = -2;

      tooLong = 0;
      for (i = 1; i <= alphaSize; i++)
      {
         j = 0;
         k = i;
         while (parent[k] >= 0)
     {
         k = parent[k];
         j++;
     }
         len[i-1] = j;
         if (j > maxLen)
         tooLong = 1;
      }
}

Compile with command line,
arm-linux-gnueabihf-gcc -S -O2 -marm -mcpu=cortex-a15 -o foo.S -xc foo.E

The generated code is like,
    .cpu cortex-a15
    .eabi_attribute 27, 3
    .eabi_attribute 28, 1
    .fpu vfpv3-d16
    .eabi_attribute 20, 1
    .eabi_attribute 21, 1
    .eabi_attribute 23, 3
    .eabi_attribute 24, 1
    .eabi_attribute 25, 1
    .eabi_attribute 26, 2
    .eabi_attribute 30, 2
    .eabi_attribute 34, 1
    .eabi_attribute 18, 4
    .file    "foo.E"
    .text
    .align    2
    .global    foo
    .type    foo, %function
foo:
    @ args = 0, pretend = 0, frame = 2064
    @ frame_needed = 0, uses_anonymous_args = 0
    str    lr, [sp, #-4]!
    sub    sp, sp, #2064
    mvn    r3, #1
    sub    sp, sp, #4
    cmp    r1, #0
    str    r3, [sp]
    ble    .L1
    mov    ip, sp
    add    r1, r0, r1
.L6:
    ldr    r3, [ip, #4]!
    mov    r2, #0
    cmp    r3, #0
    blt    .L3
.L5:
    add    lr, sp, #2064            ////loop invariant
    add    r2, r2, #1
    add    r3, lr, r3, asl #2
    ldr    r3, [r3, #-2064]
    cmp    r3, #0
    bge    .L5
    uxtb    r2, r2
.L3:
    strb    r2, [r0], #1
    cmp    r0, r1
    bne    .L6
.L1:
    add    sp, sp, #2064
    add    sp, sp, #4
    @ sp needed
    ldr    pc, [sp], #4
    .size    foo, .-foo
    .ident    "GCC: (GNU) 4.9.0 20130524 (experimental)"
    .section    .note.GNU-stack,"",%progbits


Apparently, first instruction in basic block .L5 is invariant, but kept in loop
because it is generated by reload.

I think this is a common issue.

[Bug rtl-optimization/57540] stack pointer related loop invariants after reload

[amker.cheng at gmail dot com]

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

--- Comment #1 from bin.cheng <amker.cheng at gmail dot com> ---
The dump of loop_init is like,
   72: r178:SI=0
  106: L106:
   90: NOTE_INSN_BASIC_BLOCK 6
   91: r178:SI=r178:SI+0x1
   94: r190:SI=r177:SI<<0x2
      REG_DEAD r177:SI
   95: r191:SI=sfp:SI+r190:SI
      REG_DEAD r190:SI
   96: r192:SI=r191:SI-0x810
      REG_DEAD r191:SI
      REG_DEAD r189:SI
   97: r177:SI=[r192:SI]
      REG_DEAD r192:SI
   98: cc:CC=cmp(r177:SI,0)
   99: pc={(cc:CC>=0)?L104:pc}
      REG_DEAD cc:CC
      REG_BR_PROB 0x238c

Instructions 95/96 should be re-factored as below:
   95: r191:SI=sfp:SI-0x810
      REG_DEAD r190:SI
   96: r192:SI=r191:SI+r190:SI
      REG_DEAD r191:SI
      REG_DEAD r189:SI

Thus instruction 95 is loop invariant and be hoisted. For arm target, the loop
can be simplified into:

    blt    .L3

.L5:
    add    r2, r2, #1
    ldr    r3, [sp, r3, asl #2]
    cmp    r3, #0
    bge    .L5
    uxtb    r2, r2

[Bug target/57540] stack pointer related loop invariants after reload

[amker.cheng at gmail dot com]

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

bin.cheng <amker.cheng at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|rtl-optimization            |target

--- Comment #2 from bin.cheng <amker.cheng at gmail dot com> ---
This only happens on arm mode.
For below gimple,
  k_8 = parent[k_29];
On ARM mode GCC expands it into,
   81: r180:SI=0xf7f0
   82: zero_extract(r180:SI,0x10,0x10)=0xffff
   83: r181:SI=r165:SI<<0x2
   84: r182:SI=r105:SI+r181:SI
   85: r183:SI=r182:SI+r180:SI
   86: r165:SI=[r183:SI]
while on Thumb2 GCC expands it into,
   88: r185:SI=r105:SI
   89: r186:SI=r105:SI-0x810
   90: r171:SI=[r171:SI*0x4+r186:SI]
thus resulting in much better assembly code,
.L5:
    ldr    r3, [sp, r3, lsl #2]
    adds    r2, r2, #1
    cmp    r3, #0
    bge    .L5
    uxtb    r2, r2

[Bug target/57540] stack pointer related loop invariants after reload for ARM mode

[amker.cheng at gmail dot com]

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

--- Comment #3 from bin.cheng <amker.cheng at gmail dot com> ---
I think this should be handled in expand.  During expanding, GCC tries "base +
scaled_offset + offset" pattern, which is invalid for targets like arm. At this
point we still have a chance to refactor "base + offset" and force it into
register, thus generating "reg + scaled_offset".
By doing this, 
1) "base + offset" can be kept as loop invariant;
2) the multiplication is done by scaled address, saving another add
instruction.

I am testing a patch and will send it for review once it passes tests.

[Bug middle-end/57540] stack pointer related loop invariants after reload for ARM mode

[ramana at gcc dot gnu.org]

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

Ramana Radhakrishnan <ramana at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-08-05
                 CC|                            |ramana at gcc dot gnu.org
          Component|target                      |middle-end
     Ever confirmed|0                           |1

[Bug target/57540] stack pointer related loop invariants after reload for ARM mode

[amker.cheng at gmail dot com]

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

bin.cheng <amker.cheng at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|middle-end                  |target

--- Comment #4 from bin.cheng <amker.cheng at gmail dot com> ---
Sorry, according to http://gcc.gnu.org/ml/gcc-patches/2013-06/msg00932.html,
This seems should be fixed in backend.  I will fixed this in
arm_legitimize_address, so I change this entry to TARGET.