[Bug c/27116] New: Incorrect integer division (wrong sign).

[Bug c/27116] New: Incorrect integer division (wrong sign).

[laurent at komite dot net]

The following test demonstrates an incorrect sign in the following division :

#include <stdio.h>

int main (void)
{
    volatile long int n;
    n = -2;

    printf ("%ld\n", (-2147483647L - 1L) / (-n));
    return 0;
}

I get a correct result with 4.0.3, and a wrong sign with snapshots 20060325 and
20060408. Also reported in debian : 

http://bugs.debian.org/361883


-- 
           Summary: Incorrect integer division (wrong sign).
           Product: gcc
           Version: 4.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: laurent at komite dot net


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

[Bug c/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2006-04-11 10:46 -------
Overflow flag set problem:

  n = -2;
  n.10 = n;
  D.2132 = -080000000 / n.10;

-fwrapv "fixes" the problem.  This is a dup of ...


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
           Keywords|                            |wrong-code
      Known to work|                            |4.1.0 4.0.3
   Last reconfirmed|0000-00-00 00:00:00         |2006-04-11 10:46:59
               date|                            |
            Summary|Incorrect integer division  |[4.2 Regression] Incorrect
                   |(wrong sign).               |integer division (wrong
                   |                            |sign).


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

[Bug c/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[laurent at komite dot net]

------- Comment #2 from laurent at komite dot net  2006-04-11 15:06 -------

(In reply to comment #1)
> Overflow flag set problem:
> 
>   n = -2;
>   n.10 = n;
>   D.2132 = -080000000 / n.10;
> 
> -fwrapv "fixes" the problem.  This is a dup of ...

I'm not sure this is just an overflow problem, it might be more general. As
suggested by a friend, I tried the simple example :

int f (int a, int b)
{
    return (-a) / (-b);
}

The assembly and `-fdump-tree-all' output show that both negations are removed,
which is incorrect since the input domain is not symmetric wrt 0.


-- 


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

[Bug c/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[vincent at vinc17 dot org]

------- Comment #3 from vincent at vinc17 dot org  2006-04-11 15:16 -------
(In reply to comment #2)
> which is incorrect since the input domain is not symmetric wrt 0.

I disagree. Could you give an explicit example?


-- 


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

[Bug c/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2006-04-11 15:25 -------
I mean the middle-end probably does some "interesting" foldings of -2147483647L
- 1L as the result -080000000 has the overflow flag set.  It doesn't do it with
-fwrapv though.


-- 


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

[Bug c/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[vincent at vinc17 dot org]

------- Comment #5 from vincent at vinc17 dot org  2006-04-11 15:46 -------
(In reply to comment #4)
> I mean the middle-end probably does some "interesting" foldings of -2147483647L
> - 1L as the result -080000000 has the overflow flag set.

The bug also occurs with: (long) -2147483648LL.


-- 


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

[Bug c/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[vincent at vinc17 dot org]

------- Comment #6 from vincent at vinc17 dot org  2006-04-11 15:50 -------
BTW, concerning the overflow flag, I think it comes from the sign cancellation:
the long constant -2147483648 is replaced its opposite, but the opposite is not
representable in a long, hence the overflow.


-- 


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

[Bug c/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[guillaume dot melquiond at ens-lyon dot fr]

------- Comment #7 from guillaume dot melquiond at ens-lyon dot fr  2006-04-11 15:55 -------
> I disagree. Could you give an explicit example?

Sorry, my mistake, I should not have suggested this testcase: this optimization
is indeed fine (yet GCC 4.1 does not apply it). The following testcase is not
fine though (directly derived from the original testcase):

int f(int a, int b) { return (-1 - a) / (-b); }

GCC 4.2 generates the division "(a + 1) / b". This optimization is wrong when
"a" contains the biggest positive integer.


-- 


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

[Bug c/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[pinskia at gcc dot gnu dot org]

------- Comment #8 from pinskia at gcc dot gnu dot org  2006-04-12 01:14 -------
GRRRRRRR.

This is partly caused by the patch for PR 23669.

(In reply to comment #7)
> > I disagree. Could you give an explicit example?
> Sorry, my mistake, I should not have suggested this testcase: this optimization
> is indeed fine (yet GCC 4.1 does not apply it). The following testcase is not
> fine though (directly derived from the original testcase):
> int f(int a, int b) { return (-1 - a) / (-b); }
> GCC 4.2 generates the division "(a + 1) / b". This optimization is wrong when
> "a" contains the biggest positive integer.

This is undefined only if b is known to be negative otherwise it is defined.

Note I cannot patch anything right now so if someone wants to revert my patch
that is fine.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org
OtherBugsDependingO|                            |23669
              nThis|                            |
      Known to work|4.1.0 4.0.3                 |
   Target Milestone|---                         |4.2.0


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

[Bug c/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[guillaume dot melquiond at ens-lyon dot fr]

------- Comment #9 from guillaume dot melquiond at ens-lyon dot fr  2006-04-12 05:28 -------
> This is undefined only if b is known to be negative otherwise it is defined.

What is undefined? The value of "b" does not matter here. As soon as "a" is
INT_MAX, the computed value with the optimization will be the exact opposite of
the computed value without the optimization, whatever the sign of "b". So the
result is always wrong.

As far as I understand it, the compiler should be allowed to add a unary minus
only if it can prove (VRP?) that INT_MIN is outside the range of the
expression. However, for compilations with -fno-wrapv, a range excluding
INT_MIN should be added after any unary minus written by the user. As a
consequence of these two points, when nothing is known about "a" and -fno-wrapv
is in effect, the compiler would be allowed to optimize (-a)/(-b) (PR 23669)
but would be forbidden to optimize (-1-a)/(-b).


-- 


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

[Bug c/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[rguenth at gcc dot gnu dot org]

------- Comment #10 from rguenth at gcc dot gnu dot org  2006-05-02 10:23 -------
A reversal of PR23669 bootstrapped and regtested ok on
x86_64-unknown-linux-gnu, in case c95008a is yet another spurious Ada failure.

                === acats tests ===
FAIL:   c35507m
FAIL:   c95008a
FAIL:   cd2a23e
FAIL:   cdd2a02
FAIL:   cxh1001

                === gcc tests ===


Running target unix
WARNING: program timed out.
FAIL: gcc.c-torture/compile/20001226-1.c (test for excess errors)
FAIL: gcc.c-torture/execute/20050121-1.c execution,  -O0 
FAIL: gcc.c-torture/execute/complex-6.c execution,  -O0 
FAIL: gcc.dg/compat/scalar-return-3 c_compat_x_tst.o-c_compat_y_tst.o execute 
FAIL: gcc.dg/visibility-11.c scan-assembler memcpy@PLT
FAIL: gcc.dg/tree-ssa/divide-1.c (test for excess errors)
FAIL: gcc.dg/tree-ssa/divide-2.c (test for excess errors)
FAIL: gcc.dg/tree-ssa/divide-4.c scan-tree-dump-times a / 10 1
FAIL: gcc.target/x86_64/abi/test_complex_returning.c execution,  -O0 


-- 


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

[Bug middle-end/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[pinskia at gcc dot gnu dot org]

------- Comment #11 from pinskia at gcc dot gnu dot org  2006-05-08 07:58 -------
Mine.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |pinskia at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED


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

[Bug middle-end/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[mmitchel at gcc dot gnu dot org]

-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1


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

[Bug middle-end/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[rguenth at gcc dot gnu dot org]

------- Comment #12 from rguenth at gcc dot gnu dot org  2006-06-07 15:42 -------
I'm going to do it.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|pinskia at gcc dot gnu dot  |rguenth at gcc dot gnu dot
                   |org                         |org


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

[Bug middle-end/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[patchapp at dberlin dot org]

------- Comment #13 from patchapp at dberlin dot org  2006-06-07 15:45 -------
Subject: Bug number PR27116

A patch for this bug has been added to the patch tracker.
The mailing list url for the patch is
http://gcc.gnu.org/ml/gcc-patches/2006-06/msg00363.html


-- 


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

[Bug middle-end/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[rguenth at gcc dot gnu dot org]

------- Comment #14 from rguenth at gcc dot gnu dot org  2006-06-07 19:16 -------
Oh, btw. the transformation is implemented correctly.  Just we fold -1-a to ~a
(ok), and then negate_expr_p says it can easily negate ~a and negate_expr
negates it as a+1, which introduces the overflow.  So, I'll prepare a different
fix.


-- 


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

[Bug middle-end/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[patchapp at dberlin dot org]

------- Comment #15 from patchapp at dberlin dot org  2006-06-08 02:52 -------
Subject: Bug number PR27116

A patch for this bug has been added to the patch tracker.
The mailing list url for the patch is
http://gcc.gnu.org/ml/gcc-patches/2006-06/msg00378.html


-- 


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

[Bug middle-end/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[guillaume dot melquiond at ens-lyon dot fr]

------- Comment #16 from guillaume dot melquiond at ens-lyon dot fr  2006-06-08 06:35 -------
Sorry if I'm misunderstanding your patch (I didn't try it), but it seems to me
that GCC will still generate wrong code if the testcase is compiled with
-fwrapv -fno-trapv.


-- 


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

[Bug middle-end/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[vincent at vinc17 dot org]

------- Comment #17 from vincent at vinc17 dot org  2006-06-08 07:18 -------
The patch looks strange to me too: is there any reason why the optimization
would be correct under wrapping? i.e. I don't understand why -fwrapv can "fix"
the problem (as said in comment #1).


-- 


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

[Bug middle-end/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[rguenth at gcc dot gnu dot org]

------- Comment #18 from rguenth at gcc dot gnu dot org  2006-06-08 08:31 -------
The transformation -~a to a + 1 is valid with -fwrapv, but with -fwrapv, the
further transformation of the division will not happen, because that in turn is
not safe for -fwrapv.


-- 


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

[Bug middle-end/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[rguenth at gcc dot gnu dot org]

------- Comment #19 from rguenth at gcc dot gnu dot org  2006-06-08 08:42 -------
Well, ok, with the testcase in comment #1 we hit another problem in
negate_expr(_p) which I pointed out before.  I'll prepare a followup patch.


-- 


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

[Bug middle-end/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[rguenth at gcc dot gnu dot org]

------- Comment #20 from rguenth at gcc dot gnu dot org  2006-06-08 08:49 -------
Subject: Bug 27116

Author: rguenth
Date: Thu Jun  8 08:49:19 2006
New Revision: 114483

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

        PR middle-end/27116
        * fold-const.c (negate_expr_p): We can negate BIT_NOT_EXPR
        only, if overflow is defined and not trapping.
        (negate_expr): Likewise.

        * gcc.dg/torture/pr27116.c: New testcase.
        * gcc.dg/pr15785-1.c: Remove test for invalid transformation.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr27116.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/fold-const.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/pr15785-1.c


-- 


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

[Bug middle-end/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[patchapp at dberlin dot org]

------- Comment #21 from patchapp at dberlin dot org  2006-06-09 12:55 -------
Subject: Bug number PR27116

A patch for this bug has been added to the patch tracker.
The mailing list url for the patch is
http://gcc.gnu.org/ml/gcc-patches/2006-06/msg00457.html


-- 


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

[Bug middle-end/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[rguenth at gcc dot gnu dot org]

------- Comment #22 from rguenth at gcc dot gnu dot org  2006-06-16 14:56 -------
Subject: Bug 27116

Author: rguenth
Date: Fri Jun 16 14:56:34 2006
New Revision: 114723

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=114723
Log:
2006-06-16  Richard Guenther  <rguenther@suse.de>

        PR middle-end/27116
        * fold-const.c (negate_expr_p): Do not introduce undefined
        overflow in negating INTEGER_CSTs.
        (fold_negate_expr): Rename from negate_expr.  Revert last
        change for folding BIT_NOT_EXPR.  Change semantics to
        return NULL_TREE for non-simplified negations.  Do not
        strip type conversions and unify type handling.
        (negate_expr): New function, wrap around fold_negate_expr
        but ensure building a tree always.  Strip type conversions
        here, fold to result type.
        (fold_unary): Use fold_negate_expr for folding NEGATE_EXPR.

        * gcc.dg/pr15785-1.c: Revert last change.
        * gcc.dg/torture/pr27116-2.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr27116-2.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/fold-const.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/pr15785-1.c


-- 


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

[Bug middle-end/27116] [4.2 Regression] Incorrect integer division (wrong sign).

[rguenth at gcc dot gnu dot org]

------- Comment #23 from rguenth at gcc dot gnu dot org  2006-06-16 14:57 -------
Fixed.


-- 

rguenth at gcc dot gnu dot org changed:

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


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