[Bug rtl-optimization/34849] New: Missed autoincrement oppurtunities thanks to a different basic block structure.

[Bug rtl-optimization/34849] New: Missed autoincrement oppurtunities thanks to a different basic block structure.

[ramana dot radhakrishnan at celunite dot com]

Whilst investigating a missed optimization oppurtunity in comparison to gcc 3.4
I came across this case. 

void foo (int n, int in[], int res[])
{
  int i;
  for (i=0; i<n;i++)
    if (in[i])
      res[i]= 0x1234;
    else
      res[i]= 0x9876;
}

The basic block structure generated is as follows 
foo (n, in, res)
{
  unsigned int ivtmp.19;
  int i;

<bb 2>:
  if (n > 0)
    goto <bb 3>;
  else
    goto <bb 8>;

<bb 3>:
  i = 0;
  ivtmp.19 = 0;

<bb 4>:
  if (MEM[base: in, index: ivtmp.19] != 0)
    goto <bb 5>;
  else
    goto <bb 6>;

<bb 5>:
  MEM[base: res, index: ivtmp.19] = 4660;
  goto <bb 7>;

<bb 6>:
  MEM[base: res, index: ivtmp.19] = 39030;

<bb 7>:
  i = i + 1;
  ivtmp.19 = ivtmp.19 + 4;
  if (n > i)
    goto <bb 4>;
  else
    goto <bb 8>;

<bb 8>:
  return;

}

If you notice ivtmp.19 can be used for post-increment based addressing modes. 


Note that GCC 3.4 did not have another basic block for the else case, the basic
block for the else case got merged with the tail block of the loop and hence
auto-inc could get generated in the else case and not in the if side of things.
Can be reproduced with today's head of 4.3.0


-- 
           Summary: Missed autoincrement oppurtunities thanks to a different
                    basic block structure.
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: ramana dot radhakrishnan at celunite dot com
 GCC build triplet: i686-linux-gnu
  GCC host triplet: i686-linux-gnu
GCC target triplet: arm-none-eabi


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

[Bug rtl-optimization/34849] Missed autoincrement oppurtunities thanks to a different basic block structure.

[steven at gcc dot gnu dot org]

------- Comment #1 from steven at gcc dot gnu dot org  2008-01-18 14:26 -------
Which optimization level?

Why does cross-jumping not optimize this?


-- 


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

[Bug rtl-optimization/34849] Missed autoincrement oppurtunities thanks to a different basic block structure.

[ramana dot radhakrishnan at celunite dot com]

------- Comment #2 from ramana dot radhakrishnan at celunite dot com  2008-01-18 14:35 -------
(In reply to comment #1)
> Which optimization level?
-O2 . 

> 
> Why does cross-jumping not optimize this?
> 

Will check on cross-jumping and get back. 


-- 


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

[Bug rtl-optimization/34849] Missed autoincrement oppurtunities thanks to a different basic block structure.

[ramana dot radhakrishnan at celunite dot com]

------- Comment #3 from ramana dot radhakrishnan at celunite dot com  2008-01-18 14:37 -------
Add CC


-- 

ramana dot radhakrishnan at celunite dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pranav dot bhandarkar at
                   |                            |gmail dot com, dave at
                   |                            |icerasemi dot com


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

[Bug rtl-optimization/34849] Missed autoincrement oppurtunities thanks to a different basic block structure.

[hp at gcc dot gnu dot org]

------- Comment #4 from hp at gcc dot gnu dot org  2008-05-23 23:14 -------
Perhaps this is a duplicate of PR31849?


-- 

hp at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hp at gcc dot gnu dot org


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

[Bug rtl-optimization/34849] Missed autoincrement oppurtunities thanks to a different basic block structure.

[pinskia at gcc dot gnu dot org]

------- Comment #5 from pinskia at gcc dot gnu dot org  2008-12-29 18:35 -------
We should do store sinking which allows for this optimization without much
trouble on this code.


-- 


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

[Bug rtl-optimization/34849] Missed autoincrement opportunities due to a different basic block structure.

[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-04-30 13:18:25
               date|                            |


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

[Bug rtl-optimization/34849] Missed autoincrement opportunities due to a different basic block structure.

[steven at gcc dot gnu dot org]

------- Comment #6 from steven at gcc dot gnu dot org  2009-05-01 08:44 -------
I still see no answer to my question from comment #1.


-- 


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

[Bug rtl-optimization/34849] Missed autoincrement opportunities due to a different basic block structure.

[rguenth at gcc dot gnu dot org]

------- Comment #7 from rguenth at gcc dot gnu dot org  2009-05-01 20:34 -------
We can't perform loop store sinking as in and res alias.  And our other
store sinking pass is just too stupid for this case as we have a missed
CSE opportunity for the address stored to:

  D.1243_8 = *D.1242_7;
  if (D.1243_8 != 0)
    goto <bb 4>;
  else
    goto <bb 5>;

<bb 4>:
  D.1246_12 = res_11(D) + D.1241_5;
  *D.1246_12 = 4660;
  goto <bb 6>;

<bb 5>:
  D.1246_15 = res_11(D) + D.1241_5;
  *D.1246_15 = 39030;

but this is the usual missing code hoisting.


-- 


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

[Bug rtl-optimization/34849] Missed autoincrement opportunities due to a different basic block structure.

[steven at gcc dot gnu dot org]

------- Comment #8 from steven at gcc dot gnu dot org  2009-05-01 21:51 -------
Crossjumping does nothing, because there is nothing to crossjump anymore at
that point.  The two stores have been replaced with one and a conditional set:

- in .ce1 (ifcvt1) we haven't converted to a conditional set two stores
- in .ce2 there is a conditional set to a reg and only one store

The conditional set is to a reg (r = in[i] ? 0x1234 : 0x9876).

Anwyay, ce2 is *after* auto-inc-dec.  We would probably optimize this if you'd
run auto-inc-dec after ce2.  I don't know why this transformation is not
already done in ce1.


-- 


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

[Bug rtl-optimization/34849] Missed autoincrement opportunities due to a different basic block structure.

[steven at gcc dot gnu dot org]

------- Comment #9 from steven at gcc dot gnu dot org  2009-05-01 22:27 -------
FWIW, early crossjumping (after ce1) doesn't work either.

The code before trying to crossjump looks like this:

   44 pc={(cc:CC=0x0)?L50:pc}
      REG_DEAD: cc:CC
      REG_BR_PROB: 0x1388
   45 NOTE_INSN_BASIC_BLOCK
   46 r170:SI=0x1234
   47 [r168:SI+r164:SI]=r170:SI
      REG_DEAD: r170:SI
      REG_EQUAL: 0x1234
L50:
   51 NOTE_INSN_BASIC_BLOCK
   52 r171:SI=0x9876
   53 [r168:SI+r164:SI]=r171:SI
      REG_DEAD: r171:SI
      REG_EQUAL: 0x1234
L54:
   55 NOTE_INSN_BASIC_BLOCK
   56 r162:SI=r162:SI+0x1
   57 r164:SI=r164:SI+0x4

Note that we're in cfglayout mode: we fall through to insn 55 from insn 53 and
insn 47 too.

The reason that crossjumping fails, is the difference in input registers (r170
and r171), i.e. the usual problem with the RTL crossjumping pass.

The reason why I keep coming back to crossjumping, is that I am 99% sure we
would have an autoincrement if we crossjumped the two stores.


-- 


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

[Bug rtl-optimization/34849] Missed autoincrement opportunities due to a different basic block structure.

[steven at gcc dot gnu dot org]

------- Comment #10 from steven at gcc dot gnu dot org  2009-06-03 08:16 -------
Ramana, can you please add the exact command line you are using (so that I can
see what flags you use and what cpu you target) and the exact output you are
expecting?  I have hacked things such that the store is cross-jumped but I
still don't get an autoincrement insn.  I get this for arm7-r with r147999,
-Os, and my hack:

        .file   "t.c"
        .text
        .align  2
        .global foo
        .type   foo, %function
foo:
        @ args = 0, pretend = 0, frame = 0
        @ frame_needed = 0, uses_anonymous_args = 0
        ldr     r3, #0
        stmfd   sp!, {r4, r5, lr}
        mov     ip, r3
        b       .L2
.L4:
        ldr     r4, [r1, r3]
        movw    r5, #39030
        cmp     r4, #0
        movw    r4, #4660
        moveq   r4, r5
        str     r4, [r2, r3]
        add     r3, r3, #4              @ I suppose you expect an autoinc here?
.L2:
        cmp     ip, r0
        add     ip, ip, #1
        blt     .L5
        ldmfd   sp!, {r4, r5, pc}
        .size   foo, .-foo
        .ident  "GCC: (GNU) 4.5.0 20090530 (experimental) [trunk revision
147999]"


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |WAITING


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

[Bug rtl-optimization/34849] Missed autoincrement opportunities due to a different basic block structure.

[steven at gcc dot gnu dot org]

------- Comment #11 from steven at gcc dot gnu dot org  2009-06-03 08:25 -------
s/L4/L5/
my punishment from manually typing over the assembly from my laptop screen into
bugzilla on the desktop :-/


-- 


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

[Bug rtl-optimization/34849] Missed autoincrement opportunities due to a different basic block structure.

[ramana at gcc dot gnu dot org]

------- Comment #12 from ramana at gcc dot gnu dot org  2009-06-05 23:16 -------
(In reply to comment #10)
> Ramana, can you please add the exact command line you are using (so that I can
> see what flags you use and what cpu you target) and the exact output you are
> expecting?  I have hacked things such that the store is cross-jumped but I
> still don't get an autoincrement insn.  I get this for arm7-r with r147999,
> -Os, and my hack:

Sorry about the late response, I sort of dropped the ball on this one. The
target was essentially default arm which is armv4t and I suspect the command
line was -O2, -O3 and -Os.


Yes the case where you show is where I would have expected an auto-increment .
I presume this is after the new cross jumping work you've done -

> 
>         .file   "t.c"
>         .text
>         .align  2
>         .global foo
>         .type   foo, %function
> foo:
>         @ args = 0, pretend = 0, frame = 0
>         @ frame_needed = 0, uses_anonymous_args = 0
>         ldr     r3, #0
>         stmfd   sp!, {r4, r5, lr}
>         mov     ip, r3
>         b       .L2
> .L4:
>         ldr     r4, [r1, r3]
>         movw    r5, #39030
>         cmp     r4, #0
>         movw    r4, #4660
>         moveq   r4, r5
>         str     r4, [r2, r3]
>         add     r3, r3, #4              @ I suppose you expect an autoinc here?
> .L2:
>         cmp     ip, r0
>         add     ip, ip, #1
>         blt     .L5
>         ldmfd   sp!, {r4, r5, pc}
>         .size   foo, .-foo
>         .ident  "GCC: (GNU) 4.5.0 20090530 (experimental) [trunk revision
> 147999]"
> 


-- 


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

[Bug rtl-optimization/34849] Missed autoincrement opportunities due to a different basic block structure.

[ramana at gcc dot gnu dot org]

-- 

ramana at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |NEW
   Last reconfirmed|2009-04-30 13:18:25         |2009-07-14 10:47:37
               date|                            |


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

[Bug rtl-optimization/34849] Missed autoincrement opportunities due to a different basic block structure.

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
      Known to fail|                            |
         Resolution|---                         |FIXED
   Target Milestone|---                         |11.0

--- Comment #13 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
This was fixed on the gimple level by the following revisions:
r7-1935 (pre of the res_11(D) + _7 part)
r11-408 (common store sinking)

Loop which we get now:
.L4:
        ldr     r0, [r1], #4
        cmp     r0, #0
        ite     eq
        moveq   r3, r4
        movne   r3, lr
        cmp     r1, ip
        str     r3, [r2, #4]!
        bne     .L4