[Bug c/45034] New: "safe" conversion from unsigned to signed char gives broken code

[Bug c/45034] New: "safe" conversion from unsigned to signed char gives broken code

[mikpe at it dot uu dot se]

The following program (which I'll also attach later) gives unexpected results,
where signed char values are passed as non properly sign-extended ints:

> cat char-neg.c
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

static void fixnum_neg(signed char x, signed char *py, int *pv)
{
    unsigned char ux, uy;

    ux = (unsigned char)x;
    uy = -ux;
    *py = (uy <= 127) ? (signed char)uy : (-(signed char)(255 - uy) - 1);
    *pv = (x == -128) ? 1 : 0;
}

void __attribute__((noinline)) foo(int x, int y, int v)
{
    printf("test_neg: -(%d) => (%d, %d)\n", x, y, v);
    if (y < -128 || y > 127)
        abort();
}

int test_neg(void)
{
    signed char x, y;
    int v, err;

    err = 0;
    x = -128;
    for (;;) {
        fixnum_neg(x, &y, &v);
        foo((int)x, (int)y, v);
        if ((v && x != -128) || (!v && x == -128))
            ++err;
        if (x == 127)
            break;
        ++x;
    }
    return err;
}

int main(void)
{
    if (CHAR_BIT != 8
        || SCHAR_MIN != -128 || SCHAR_MAX != 127
        || UCHAR_MAX != 255)
        abort();
    if (test_neg() != 0)
        abort();
    return 0;
}
> gcc -O2 -Wall -Wextra char-neg.c ; ./a.out
test_neg: -(-128) => (-128, 1)
test_neg: -(-127) => (-129, 0)
Abort

The abort shows that the `signed char' variable y is incorrectly extended to
int when passed to foo().

Passing -fwrapv eliminates the failure.  Maybe I've been staring at this for
too long, but I can't see any signed overflow in this code.

The problem occurs with gcc 4.6/4.5/4.4/4.3/4.2, but not with 4.1 or older.

The program comes from some code which attempts to emulate machine-level
integer arithmetic and condition code settings.  To validate the condition code
logic I used exhaustive testing on a smaller integer type (signed char),  but
that broke as shown above.  The assignment to *py in fixnum_neg() is one of
several attempts to cast from unsigned to signed char without (apparently)
triggering undefined behaviour due to signed overflow; other failed attempts
have included plain casts, assignment via a union, and memcpy() via a local
signed char temporary.

gcc was configured --with-gmp=... --with-mpfr=... --with-mpc=...
--disable-plugin --disable-lto --disable-nls --enable-threads=posix
--enable-checking=release --disable-libmudflap --enable-languages=c


-- 
           Summary: "safe" conversion from unsigned to signed char gives
                    broken code
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: mikpe at it dot uu dot se
GCC target triplet: i686-pc-linux-gnu


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

[Bug c/45034] "safe" conversion from unsigned to signed char gives broken code

[mikpe at it dot uu dot se]

------- Comment #1 from mikpe at it dot uu dot se  2010-07-22 21:13 -------
Created an attachment (id=21290)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=21290&action=view)
test case


-- 


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

[Bug tree-optimization/45034] "safe" conversion from unsigned to signed char gives broken code

[pinskia at gcc dot gnu dot org]

------- Comment #2 from pinskia at gcc dot gnu dot org  2010-07-22 21:26 -------
IV-OPTS is causing it.  It also fails in 4.3.2.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c                           |tree-optimization
           Keywords|                            |wrong-code
      Known to fail|                            |4.3.2


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

[Bug tree-optimization/45034] "safe" conversion from unsigned to signed char gives broken code

[hjl dot tools at gmail dot com]

------- Comment #3 from hjl dot tools at gmail dot com  2010-07-23 04:14 -------
It is triggered by revision 121254:

http://gcc.gnu.org/ml/gcc-cvs/2007-01/msg00960.html


-- 

hjl dot tools at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |iant at google dot com


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

[Bug tree-optimization/45034] [4.3/4.4/4.5/4.6 Regression] "safe" conversion from unsigned to signed char gives broken code

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2010-07-23 08:51 -------
Confirmed.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
      Known to work|                            |4.1.2
   Last reconfirmed|0000-00-00 00:00:00         |2010-07-23 08:51:49
               date|                            |
            Summary|"safe" conversion from      |[4.3/4.4/4.5/4.6 Regression]
                   |unsigned to signed char     |"safe" conversion from
                   |gives broken code           |unsigned to signed char
                   |                            |gives broken code
   Target Milestone|---                         |4.3.6


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

[Bug tree-optimization/45034] [4.3/4.4/4.5/4.6 Regression] "safe" conversion from unsigned to signed char gives broken code

[mikpe at it dot uu dot se]

------- Comment #5 from mikpe at it dot uu dot se  2010-07-24 18:47 -------
(In reply to comment #3)
> It is triggered by revision 121254:
> 
> http://gcc.gnu.org/ml/gcc-cvs/2007-01/msg00960.html

I don't think that's correct.  I definitely see the error with both gcc trunk
r121253 (pre 4.3.0) and 4.2.4 on i686-linux.  I'll try to bisect it myself.


-- 


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

[Bug tree-optimization/45034] [4.3/4.4/4.5/4.6 Regression] "safe" conversion from unsigned to signed char gives broken code

[mikpe at it dot uu dot se]

------- Comment #6 from mikpe at it dot uu dot se  2010-07-25 10:56 -------
My bisection identified r114057 as the cause or trigger for this bug:
http://gcc.gnu.org/ml/gcc-cvs/2006-05/msg00661.html

The assembly code diff for the test case with r114056 and r114057 is:

--- char-neg.s-r114056  2010-07-25 12:22:25.000000000 +0200
+++ char-neg.s-r114057  2010-07-25 12:22:31.000000000 +0200
@@ -57,9 +57,10 @@
        movl    %edi, %eax
        xorl    %ebx, %ebx
        cmpb    $-128, %al
+       movl    %edi, %eax
        sete    %bl
        negl    %eax
-       movsbl  %al,%eax
+       subl    $256, %eax
        movl    %ebx, 8(%esp)
        movl    %eax, 4(%esp)
        movl    %edi, (%esp)

which looks completely broken.  (This is the inlined code for foo() in the loop
in test_neg().)

r114057 was backported to 4.1.2, but for some reason the bug doesn't trigger
there.


-- 

mikpe at it dot uu dot se changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rakdver at gcc dot gnu dot
                   |                            |org
      Known to fail|4.3.2                       |4.3.2 4.2.0


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

[Bug tree-optimization/45034] [4.3/4.4/4.5/4.6 Regression] "safe" conversion from unsigned to signed char gives broken code

[rakdver at gcc dot gnu dot org]

------- Comment #7 from rakdver at gcc dot gnu dot org  2010-07-26 14:47 -------
By the time the code reaches ivopts, it looks (modulo SSA form) this way:

signed char x = -128, tmp;

for (;;)
  {
    tmp = -x;
    foo ((int) x, (int) tmp, x==-128);
    ...
    if (x == 127)
      break;
    x++;
  }

Note that all the careful handling of -x in case that x=-128 disappeared. 
Then, ivopts trust that signed arithmetics does not overflow, and misscompile
the program.  In fact, it seems that the error is already there at the very
beginning: the .original dump shows

fixnum_neg
{
  ux = (unsigned char) x;
  uy = (unsigned char) -(signed char) ux;
  ...
}

That is, the negation of unsigned char value is implemented by casting it to
signed char, which introduces signed overflow if the value of x is -128.  As
far as I understand the C standard, this seems incorrect.


-- 


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

[Bug tree-optimization/45034] [4.3/4.4/4.5/4.6 Regression] "safe" conversion from unsigned to signed char gives broken code

[mikpe at it dot uu dot se]

------- Comment #8 from mikpe at it dot uu dot se  2010-07-27 22:18 -------
(In reply to comment #7)
> In fact, it seems that the error is already there at the very
> beginning: the .original dump shows
> 
> fixnum_neg
> {
>   ux = (unsigned char) x;
>   uy = (unsigned char) -(signed char) ux;
>   ...
> }
> 
> That is, the negation of unsigned char value is implemented by casting it to
> signed char, which introduces signed overflow if the value of x is -128.  As
> far as I understand the C standard, this seems incorrect.

It depends on how GCC interprets that cast and negation:
- if the cast has C semantics, then (signed char)ux causes overflow
- if the cast wraps, then it is fine and yields (signed char)-128
- if the negation has C semantics, then (signed char)-128 is widened to int and
then negated to 128
- if the negation maps signed char to signed char, then it causes overflow

IMO, a serious problem with the C standard is that

    signed char x = -1;
    signed char y = (signed char)(unsigned char)x;

triggers signed overflow causing undefined behaviour.

This comes from an asymmetry between cast to unsigned and cast to signed:
- cast from signed to unsigned is a total and injective function
- cast from unsigned to signed is a partial function with range from 0 to the
maximum of the signed type (inclusive), which excludes values converted from
negative signed values

(I'd be happy to be proven wrong about this, if anyone can cite relevant
sections from n1124 (C99 TC2) or n1494 (C1x draft) to the contrary.)

Personally I think GCC should treat source-level casts as wrapping, regardless
of -fstrict-overflow and -fno-wrapv.  Perhaps it intends to, and we're just
seeing the effects of bugs.


-- 


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

[Bug tree-optimization/45034] [4.3/4.4/4.5/4.6 Regression] "safe" conversion from unsigned to signed char gives broken code

[joseph at codesourcery dot com]

------- Comment #9 from joseph at codesourcery dot com  2010-07-27 22:42 -------
Subject: Re:  [4.3/4.4/4.5/4.6 Regression] "safe"
 conversion from unsigned to signed char gives broken code

On Tue, 27 Jul 2010, mikpe at it dot uu dot se wrote:

> Personally I think GCC should treat source-level casts as wrapping, regardless
> of -fstrict-overflow and -fno-wrapv.  Perhaps it intends to, and we're just
> seeing the effects of bugs.

This implementation-defined behavior is already documented in 
implement-c.texi:

    @item
    @cite{The result of, or the signal raised by, converting an integer to a
    signed integer type when the value cannot be represented in an object of
    that type (C90 6.2.1.2, C99 6.3.1.3).}

    For conversion to a type of width @math{N}, the value is reduced
    modulo @math{2^N} to be within range of the type; no signal is raised.


-- 


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

[Bug tree-optimization/45034] [4.3/4.4/4.5/4.6 Regression] "safe" conversion from unsigned to signed char gives broken code

[rakdver at kam dot mff dot cuni dot cz]

------- Comment #10 from rakdver at kam dot mff dot cuni dot cz  2010-07-27 23:09 -------
Subject: Re:  [4.3/4.4/4.5/4.6 Regression]
        "safe" conversion from unsigned to signed char gives broken code

> >   ux = (unsigned char) x;
> >   uy = (unsigned char) -(signed char) ux;
> >   ...
> > }
> > 
> > That is, the negation of unsigned char value is implemented by casting it to
> > signed char, which introduces signed overflow if the value of x is -128.  As
> > far as I understand the C standard, this seems incorrect.
> 
> It depends on how GCC interprets that cast and negation:
> - if the cast has C semantics, then (signed char)ux causes overflow
> - if the cast wraps, then it is fine and yields (signed char)-128
> - if the negation has C semantics, then (signed char)-128 is widened to int and
> then negated to 128
> - if the negation maps signed char to signed char, then it causes overflow
> 
> IMO, a serious problem with the C standard is that
> 
>     signed char x = -1;
>     signed char y = (signed char)(unsigned char)x;
> 
> triggers signed overflow causing undefined behaviour.

no, it does not.  The semantics of the cast in this case is not undefined, it
is implementation-defined.  GCC defines it in the natural way (and induction
variable analysis takes that into account).  The problem is with the negation,
which causes overflow.


-- 


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

[Bug tree-optimization/45034] [4.3/4.4/4.5/4.6 Regression] "safe" conversion from unsigned to signed char gives broken code

[rguenth at gcc dot gnu dot org]

------- Comment #11 from rguenth at gcc dot gnu dot org  2010-07-28 09:32 -------
I suppose that

    uy = -ux;

is really

    uy = (unsigned char) -(int) ux;

as unsigned char promotes to int.  We then incorrectly
narrow this to -(signed char) ux.

We do this again in convert_to_integer.  Our bag of premature (and bogus)
optimizations.

        case NEGATE_EXPR:
        case BIT_NOT_EXPR:
          /* This is not correct for ABS_EXPR,
             since we must test the sign before truncation.  */
          {
            tree typex;

            /* Don't do unsigned arithmetic where signed was wanted,
               or vice versa.  */
            if (TYPE_UNSIGNED (TREE_TYPE (expr)))
              typex = unsigned_type_for (type);
            else
              typex = signed_type_for (type);
            return convert (type,
                            fold_build1 (ex_form, typex,
                                         convert (typex,
                                                  TREE_OPERAND (expr, 0))));

well - I have no idea why we can't always choose an unsigned type here
(testing that now).


-- 


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

[Bug tree-optimization/45034] [4.3/4.4/4.5/4.6 Regression] "safe" conversion from unsigned to signed char gives broken code

[rguenth at gcc dot gnu dot org]

------- Comment #12 from rguenth at gcc dot gnu dot org  2010-07-28 12:23 -------
Works.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rguenth at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2010-07-23 08:51:49         |2010-07-28 12:23:46
               date|                            |


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

[Bug tree-optimization/45034] [4.3/4.4/4.5/4.6 Regression] "safe" conversion from unsigned to signed char gives broken code

[mikpe at it dot uu dot se]

------- Comment #13 from mikpe at it dot uu dot se  2010-07-28 14:13 -------
I've bootstrapped and regtested Richard's proposed fix
(http://gcc.gnu.org/ml/gcc-patches/2010-07/msg02161.html) on top of a recent
4.5 snapshot, and it fixed the test case (and the original code it was based
on) with no testsuite regressions.

Thanks.


-- 


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

[Bug tree-optimization/45034] [4.3/4.4/4.5/4.6 Regression] "safe" conversion from unsigned to signed char gives broken code

[mikpe at it dot uu dot se]

------- Comment #14 from mikpe at it dot uu dot se  2010-07-28 15:38 -------
If I apply Richard's patch to gcc-4.4-20100727 and bootstrap/regtest the new
test case works but I get a single regression in the old ones:

FAIL: gcc.dg/vect/vect-22.c scan-tree-dump-times vect "vectorized 4 loops" 1

Looking in vect-22.c.101t.vect reveals:

...
.../gcc/testsuite/gcc.dg/vect/vect-22.c:87: note: not vectorized: relevant stmt
not supported: D.2174_43 = (short unsigned int) D.2173_42;
...
.../gcc-4.4-20100727/gcc/testsuite/gcc.dg/vect/vect-22.c:73: note: not
vectorized: relevant stmt not supported: D.2164_26 = (unsigned char) D.2163_25;
...
.../gcc-4.4-20100727/gcc/testsuite/gcc.dg/vect/vect-22.c:54: note: vectorized 2
loops in function.


-- 


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

[Bug tree-optimization/45034] [4.3/4.4/4.5/4.6 Regression] "safe" conversion from unsigned to signed char gives broken code

[mikpe at it dot uu dot se]

------- Comment #15 from mikpe at it dot uu dot se  2010-07-28 23:31 -------
Richard's proposed fix appears to need the PR44284 fix to avoid regressing
vect-20.c, much like PR44828 also needed PR44284 to not regress vectorization
tests.  Current 4.5 has PR44284 backported, so the PR45034 fix works there.

I did a preliminary backport of the first PR44284 fix to 4.4, and that solved
the vect-20.c regression but caused a couple of regressions of its own.  I'll
try backporting the followup fixes too, but I suspect the rational conclusion
will be to not backport the PR45034 fix, or to backport it with an adjustment
to vect-20.c to expect the reduced vectorization.


-- 


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

[Bug tree-optimization/45034] [4.3/4.4/4.5 Regression] "safe" conversion from unsigned to signed char gives broken code

[rguenth at gcc dot gnu dot org]

------- Comment #17 from rguenth at gcc dot gnu dot org  2010-07-29 11:00 -------
Fixed on the trunk sofar.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|4.1.2                       |4.1.2 4.6.0
            Summary|[4.3/4.4/4.5/4.6 Regression]|[4.3/4.4/4.5 Regression]
                   |"safe" conversion from      |"safe" conversion from
                   |unsigned to signed char     |unsigned to signed char
                   |gives broken code           |gives broken code


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

[Bug tree-optimization/45034] [4.3/4.4/4.5/4.6 Regression] "safe" conversion from unsigned to signed char gives broken code

[rguenth at gcc dot gnu dot org]

------- Comment #16 from rguenth at gcc dot gnu dot org  2010-07-29 11:00 -------
Subject: Bug 45034

Author: rguenth
Date: Thu Jul 29 10:59:54 2010
New Revision: 162673

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=162673
Log:
2010-07-29  Richard Guenther  <rguenther@suse.de>

        PR middle-end/45034
        * convert.c (convert_to_integer): Always use an unsigned
        type for narrowed negate and bitwise not.

        * gcc.c-torture/execute/pr45034.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr45034.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/convert.c
    trunk/gcc/testsuite/ChangeLog


-- 


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

[Bug tree-optimization/45034] [4.3/4.4/4.5 Regression] "safe" conversion from unsigned to signed char gives broken code

[rguenth at gcc dot gnu dot org]

------- Comment #18 from rguenth at gcc dot gnu dot org  2010-08-08 15:50 -------
Subject: Bug 45034

Author: rguenth
Date: Sun Aug  8 15:50:17 2010
New Revision: 163009

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

        PR middle-end/45034
        * convert.c (convert_to_integer): Always use an unsigned
        type for narrowed negate and bitwise not.

        * gcc.c-torture/execute/pr45034.c: New testcase.

Added:
    branches/gcc-4_5-branch/gcc/testsuite/gcc.c-torture/execute/pr45034.c
Modified:
    branches/gcc-4_5-branch/gcc/ChangeLog
    branches/gcc-4_5-branch/gcc/convert.c
    branches/gcc-4_5-branch/gcc/testsuite/ChangeLog


-- 


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

[Bug tree-optimization/45034] [4.3/4.4 Regression] "safe" conversion from unsigned to signed char gives broken code

[rguenth at gcc dot gnu dot org]

------- Comment #19 from rguenth at gcc dot gnu dot org  2010-08-08 15:51 -------
Also fixed on the 4.5 branch.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|rguenth at gcc dot gnu dot  |unassigned at gcc dot gnu
                   |org                         |dot org
             Status|ASSIGNED                    |NEW
      Known to fail|4.3.2 4.2.0                 |4.3.2 4.2.0 4.5.1
      Known to work|4.1.2 4.6.0                 |4.1.2 4.5.2 4.6.0
            Summary|[4.3/4.4/4.5 Regression]    |[4.3/4.4 Regression] "safe"
                   |"safe" conversion from      |conversion from unsigned to
                   |unsigned to signed char     |signed char gives broken
                   |gives broken code           |code


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