[Bug c/54027] New: possible mis-optimization of signed left shift in c89 mode

[Bug c/54027] New: possible mis-optimization of signed left shift in c89 mode

[regehr at cs dot utah.edu]

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

             Bug #: 54027
           Summary: possible mis-optimization of signed left shift in c89
                    mode
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: regehr@cs.utah.edu


The program below is clearly undefined in C99, but I'm not sure that it should
be undefined in C89 mode.

GCC pre-4.8.0 turns the code into an infinite loop even in C89 mode at -O2 and
higher.

regehr@home:~/svn/code$ cat shift.c
int main (void)
{
  int x = 1;
  while (x)
    x <<= 1;
  return x;
}
regehr@home:~/svn/code$ gcc -O2 -std=c89 shift.c ; ./a.out 
^C
regehr@home:~/svn/code$ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/home/regehr/z/compiler-install/gcc-r189449-install/libexec/gcc/x86_64-unknown-linux-gnu/4.8.0/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: /home/regehr/z/compiler-source/gcc/configure
--with-libelf=/usr/local --enable-lto
--prefix=/home/regehr/z/compiler-install/gcc-r189449-install
--enable-languages=c,c++
Thread model: posix
gcc version 4.8.0 20120713 (experimental) (GCC)

[Bug c/54027] possible mis-optimization of signed left shift in c89 mode

[rguenth at gcc dot gnu.org]

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

--- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-07-19 10:07:11 UTC ---
Isn't it invoking undefined behavior by means of a signed integer overflow?
(if shifts are not defined in terms of multiplies we may not internally
fold x << 1 to x * 2).

[Bug c/54027] possible mis-optimization of signed left shift in c89 mode

[joseph at codesourcery dot com]

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

--- Comment #2 from joseph at codesourcery dot com <joseph at codesourcery dot com> 2012-07-19 15:07:54 UTC ---
On Thu, 19 Jul 2012, rguenth at gcc dot gnu.org wrote:

> Isn't it invoking undefined behavior by means of a signed integer overflow?
> (if shifts are not defined in terms of multiplies we may not internally
> fold x << 1 to x * 2).

Shifts in GCC are supposed to be defined as long as the shift amount is in 
range, independent of the LHS, so it should not be folding like that.  
(Although we document in implement-c.texi that this is subject to change 
for signed left shift, I don't think changing it would be a particularly 
good idea.)

[Bug tree-optimization/54027] [4.8 Regression] possible mis-optimization of signed left shift in c89 mode

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
           Keywords|                            |wrong-code
   Last reconfirmed|                            |2012-07-20
          Component|c                           |tree-optimization
         AssignedTo|unassigned at gcc dot       |rguenth at gcc dot gnu.org
                   |gnu.org                     |
     Ever Confirmed|0                           |1
            Summary|possible mis-optimization   |[4.8 Regression] possible
                   |of signed left shift in c89 |mis-optimization of signed
                   |mode                        |left shift in c89 mode
   Target Milestone|---                         |4.8.0

--- Comment #3 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-07-20 09:37:54 UTC ---
Mine.  This is VRPs handling of left-shifts via the multiplication code.  I
didn't know this was implementation defined.

[Bug tree-optimization/54027] [4.8 Regression] possible mis-optimization of signed left shift in c89 mode

[markus at trippelsdorf dot de]

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

Markus Trippelsdorf <markus at trippelsdorf dot de> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |markus at trippelsdorf dot
                   |                            |de

--- Comment #4 from Markus Trippelsdorf <markus at trippelsdorf dot de> 2012-08-09 13:31:22 UTC ---
FYI this also turns glibc's  __ieee754_fmodf into an endless loop:

>From sysdeps/ieee754/flt-32/e_fmodf.c:

float
__ieee754_fmodf (float x, float y)
{
        int32_t n,hx,hy,hz,ix,iy,sx,i;

        GET_FLOAT_WORD(hx,x);
        GET_FLOAT_WORD(hy,y);
        sx = hx&0x80000000;             /* sign of x */
        hx ^=sx;                /* |x| */
        hy &= 0x7fffffff;       /* |y| */

    /* purge off exception values */
        if(hy==0||(hx>=0x7f800000)||            /* y=0,or x not finite */
           (hy>0x7f800000))                     /* or y is NaN */
            return (x*y)/(x*y);
        if(hx<hy) return x;                     /* |x|<|y| return x */
        if(hx==hy)
            return Zero[(u_int32_t)sx>>31];     /* |x|=|y| return x*0*/

    /* determine ix = ilogb(x) */
        if(hx<0x00800000) {     /* subnormal x */
            for (ix = -126,i=(hx<<8); i>0; i<<=1) ix -=1;
        } //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ endless loop

Disassembly of section .text:

0000000000000000 <__fmodf_finite>:
   0:   66 0f 7e c0             movd   %xmm0,%eax
   4:   89 c7                   mov    %eax,%edi
   6:   81 e7 00 00 00 80       and    $0x80000000,%edi
   c:   66 41 0f 7e c8          movd   %xmm1,%r8d
  11:   31 f8                   xor    %edi,%eax
  13:   44 89 c6                mov    %r8d,%esi
  16:   81 e6 ff ff ff 7f       and    $0x7fffffff,%esi
  1c:   3d ff ff 7f 7f          cmp    $0x7f7fffff,%eax
  21:   7f 2d                   jg     50 <__fmodf_finite+0x50>
  23:   85 f6                   test   %esi,%esi
  25:   74 29                   je     50 <__fmodf_finite+0x50>
  27:   81 fe 00 00 80 7f       cmp    $0x7f800000,%esi
  2d:   7f 21                   jg     50 <__fmodf_finite+0x50>
  2f:   39 f0                   cmp    %esi,%eax
  31:   7c 6d                   jl     a0 <__fmodf_finite+0xa0>
  33:   74 73                   je     a8 <__fmodf_finite+0xa8>
  35:   3d ff ff 7f 00          cmp    $0x7fffff,%eax
  3a:   89 c2                   mov    %eax,%edx
  3c:   7f 7a                   jg     b8 <__fmodf_finite+0xb8>
  3e:   c1 e2 08                shl    $0x8,%edx
  41:   85 d2                   test   %edx,%edx
  43:   0f 8e 2a 01 00 00       jle    173 <__fmodf_finite+0x173>
  49:   eb fe                   jmp    49 <__fmodf_finite+0x49>

[Bug tree-optimization/54027] [4.8 Regression] possible mis-optimization of signed left shift in c89 mode

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-08-10 08:34:01 UTC ---
Author: rguenth
Date: Fri Aug 10 08:33:57 2012
New Revision: 190286

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=190286
Log:
2012-08-10  Richard Guenther  <rguenther@suse.de>

    PR tree-optimization/54027
    * tree-vrp.c (extract_range_from_binary_expr_1): Merge RSHIFT_EXPR
    and LSHIFT_EXPR handling, force -fwrapv for the multiplication used
    to handle LSHIFT_EXPR with a constant.

    * gcc.dg/torture/pr54027.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr54027.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vrp.c

[Bug tree-optimization/54027] [4.8 Regression] possible mis-optimization of signed left shift in c89 mode

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED

--- Comment #6 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-08-10 08:39:26 UTC ---
Fixed.  VRP shift handling is still lame.