Bug 27116

Summary: [4.2 Regression] Incorrect integer division (wrong sign).
Product: gcc Reporter: Laurent Fousse <laurent>
Component: middle-endAssignee: Richard Biener <rguenth>
Status: RESOLVED FIXED    
Severity: normal CC: fang, gcc-bugs, guillaume.melquiond, pinskia, rguenth, tbm, vincent-gcc
Priority: P1 Keywords: wrong-code
Version: 4.2.0   
Target Milestone: 4.2.0   
Host: Target:
Build: Known to work:
Known to fail: Last reconfirmed: 2006-04-11 10:46:59
Bug Depends on:    
Bug Blocks: 23669    

Description Laurent Fousse 2006-04-11 10:28:15 UTC
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
Comment 1 Richard Biener 2006-04-11 10:46:59 UTC
Overflow flag set problem:

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

-fwrapv "fixes" the problem.  This is a dup of ...
Comment 2 Laurent Fousse 2006-04-11 15:06:05 UTC
(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.
Comment 3 Vincent Lefèvre 2006-04-11 15:16:26 UTC
(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?
Comment 4 Richard Biener 2006-04-11 15:25:29 UTC
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.
Comment 5 Vincent Lefèvre 2006-04-11 15:46:32 UTC
(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.
Comment 6 Vincent Lefèvre 2006-04-11 15:50:32 UTC
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.
Comment 7 Guillaume Melquiond 2006-04-11 15:55:33 UTC
> 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.
Comment 8 Andrew Pinski 2006-04-12 01:14:55 UTC
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.
Comment 9 Guillaume Melquiond 2006-04-12 05:28:36 UTC
> 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).
Comment 10 Richard Biener 2006-05-02 10:23:16 UTC
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 
Comment 11 Andrew Pinski 2006-05-08 07:58:29 UTC
Mine.
Comment 12 Richard Biener 2006-06-07 15:42:33 UTC
I'm going to do it.
Comment 13 patchapp@dberlin.org 2006-06-07 15:45:14 UTC
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
Comment 14 Richard Biener 2006-06-07 19:16:25 UTC
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.
Comment 15 patchapp@dberlin.org 2006-06-08 02:52:49 UTC
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
Comment 16 Guillaume Melquiond 2006-06-08 06:35:16 UTC
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.
Comment 17 Vincent Lefèvre 2006-06-08 07:18:09 UTC
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).
Comment 18 Richard Biener 2006-06-08 08:31:11 UTC
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.
Comment 19 Richard Biener 2006-06-08 08:42:16 UTC
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.
Comment 20 Richard Biener 2006-06-08 08:49:32 UTC
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

Comment 21 patchapp@dberlin.org 2006-06-09 12:55:12 UTC
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
Comment 22 Richard Biener 2006-06-16 14:56:44 UTC
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

Comment 23 Richard Biener 2006-06-16 14:57:01 UTC
Fixed.