[Bug tree-optimization/47004] New: missed optimization in comparison

[Bug tree-optimization/47004] New: missed optimization in comparison

[bosch at gcc dot gnu.org]

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

           Summary: missed optimization in comparison
           Product: gcc
           Version: 4.5.4
            Status: UNCONFIRMED
          Severity: minor
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: bosch@gcc.gnu.org


Created attachment 22811
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=22811
Preprocessed source to reproduce

The attached C test case shows missed optimization, where lenzero could be
optimized to generate the same code as lenzero2. This pattern is very common in
Ada, where the 'Length attribute for arrays expands to the same code as that
for len. As this is all simple integer code without any aliasing issues, I have
some hope that GCC can do better here.

Regards,
  -Geert 

cat lenzero.c && gcc -O3 -fomit-frame-pointer -save-temps -c lenzero.c && otool
-tv lenzero.o
int len(int f, int l) {
 return l < f ? 0 : l - f + 1;
}

int lenzero(int f, int l) {
 return len(f, l) == 0;
}

int lenzero2(int f, int l) {
 return l < f;
}

lenzero.o:
(__TEXT,__text) section
_len:
0000000000000000    xorl    %eax,%eax
0000000000000002    cmpl    %edi,%esi
0000000000000004    jl    0x0000000b
0000000000000006    subl    %edi,%esi
0000000000000008    leal    0x01(%rsi),%eax
000000000000000b    repz/ret
000000000000000d    nop
000000000000000e    nop
_lenzero:
0000000000000010    cmpl    %esi,%edi
0000000000000012    movl    $0x00000001,%eax
0000000000000017    jg    0x00000023
0000000000000019    subl    %edi,%esi
000000000000001b    xorl    %eax,%eax
000000000000001d    cmpl    $0xff,%esi
0000000000000020    sete    %al
0000000000000023    repz/ret
0000000000000025    nop
0000000000000026    nopw    %cs:0x00000000(%rax,%rax)
_lenzero2:
0000000000000030    xorl    %eax,%eax
0000000000000032    cmpl    %edi,%esi
0000000000000034    setl    %al
0000000000000037    ret

[Bug tree-optimization/47004] missed optimization in comparison

[bosch at gcc dot gnu.org]

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

Geert Bosch <bosch at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bosch at gcc dot gnu.org

--- Comment #1 from Geert Bosch <bosch at gcc dot gnu.org> 2010-12-18 19:22:13 UTC ---
The compiler gets really close in being able to optimize this testcase.
In fact, adding an extra always-true expression, as I did in lenzero4,
causes the compiler to optimize correctly.

int lenzero3 (int f, int l) {
  return (l < f ? 0 == 0 : l - f + 1 == 0);
}
int lenzero4 (int f, int l) {
  return (l < f ? 0 == 0 : (l - f >= 0) && (l - f + 1 == 0));
}

The first generates:
_lenzero3:
0000000000000040    cmpl    %edi,%esi
0000000000000042    movl    $0x00000001,%eax
0000000000000047    jl    0x00000053
0000000000000049    subl    %edi,%esi
000000000000004b    xorl    %eax,%eax
000000000000004d    cmpl    $0xff,%esi
0000000000000050    sete    %al
0000000000000053    repz/ret

The second:
_lenzero4:
0000000000000060    xorl    %eax,%eax
0000000000000062    cmpl    %edi,%esi
0000000000000064    setl    %al
0000000000000067    ret

The extra condition (l - f >= 0), provides the compiler with the right
hint to do the optimization. It can prove this added condition is always
true, and it then can derive that the condition (l - f + 1 == 0) is
always false.

So, the compiler *can* prove l < f implies l - f >= 0, it just doesn't
know it should prove it in order to optimize the expression in lenzero3.

  -Geert

[Bug tree-optimization/47004] missed optimization in length comparison

[ebotcazou at gcc dot gnu.org]

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

Eric Botcazou <ebotcazou at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2010.12.19 08:55:31
                 CC|                            |ebotcazou at gcc dot
                   |                            |gnu.org
            Version|4.5.4                       |4.6.0
            Summary|missed optimization in      |missed optimization in
                   |comparison                  |length comparison
     Ever Confirmed|0                           |1
           Severity|minor                       |enhancement

--- Comment #2 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2010-12-19 08:55:31 UTC ---
Still visible on the mainline.  Maybe this could help other languages as well.

[Bug tree-optimization/47004] missed optimization in length comparison

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
   Target Milestone|---                         |5.0
           Keywords|                            |missed-optimization
      Known to work|                            |5.1.0
             Status|NEW                         |RESOLVED
      Known to fail|                            |4.9.4

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Fixed for GCC 5 by r5-3799.


We get a VRP range now of:
_4: [0, +INF(OVF)]


For:
  if (f_2(D) <= l_3(D))
    goto <bb 3>;
  else
    goto <bb 4>;

  <bb 3>:
  _4 = l_3(D) - f_2(D);
Which is exactly as we had expected.

[Bug tree-optimization/47004] missed optimization in length comparison

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=102138

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note we don;t optimize at -O1 yet, that is PR 102138.


With this code:
int g(); int h();

int lenzero1(int f, int l) {
 if ( len(f, l) == 0)
   return g();
  return h();
}
We can optimize this one at -O1 since GCC 8 with DOM optimizing it out the
second conditional (I did not look to see what fixed it though).