Bug 56899 - [4.7 Regression] Wrong constant folding
Summary: [4.7 Regression] Wrong constant folding
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.8.0
: P3 normal
Target Milestone: 4.8.0
Assignee: Not yet assigned to anyone
URL:
Keywords: wrong-code
Depends on:
Blocks:
 
Reported: 2013-04-10 07:13 UTC by Ishiura Lab Compiler Team
Modified: 2014-06-12 13:26 UTC (History)
2 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail: 4.6.4, 4.7.3, 4.7.4
Last reconfirmed: 2013-04-10 00:00:00


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Ishiura Lab Compiler Team 2013-04-10 07:13:14 UTC
GCC 4.7.2 and 4.8.0 with -O2 option miscompile the following code where
INT_MIN == -2147483648.

  $ cat error.c
  int main (void)
  {
    volatile int v = 10;
    int x =  -214748365 * ( v - 1 );
    return ( x == -1932735285 );	/* should return 1 */
  }
  $ gcc error.c -O2
  $ ./a.out
  $ echo $?
  0

The following code, with "volatile" removed from variable v, is
correctly compiled.

  $ cat noerror.c
  int main(void)
  {
    int v = 10;
    int x =  -214748365 * ( v - 1 );
    return ( x == -1932735285 );	/* should return 1 */
  }
  $ gcc noerror.c -O2
  $ ./a.out
  $ echo $?
  1

The miscompile occurs on options "-O1 -fstrict-overflow."
Comment 1 Andrew Pinski 2013-04-10 07:32:52 UTC
-2147483648 * 9 overflows so the code is undefined so both answers are correct but inconsistent.
Comment 2 Marc Glisse 2013-04-10 07:42:51 UTC
Andrew, he isn't multiplying INT_MIN by 9 but some number that is roughly INT_MIN/10. extract_muldiv_1 seems to be missing some checks before distributing the multiplication.
Comment 3 Mikael Pettersson 2013-04-10 07:45:20 UTC
What's the target?  I can't reproduce on x86_64, armv5tel, or m68k.
Comment 4 Marc Glisse 2013-04-10 07:49:24 UTC
(In reply to comment #3)
> What's the target?  I can't reproduce on x86_64, armv5tel, or m68k.

I've reproduced it with -O2 on x86_64-linux-gnu using trunk.
Comment 5 Richard Biener 2013-04-10 08:01:22 UTC
We fold (1 - v) * 214748365 to v * -214748365 + 214748365 which is wrong
as it may introduce undefined overflow:

      /* The last case is if we are a multiply.  In that case, we can
         apply the distributive law to commute the multiply and addition
         if the multiplication of the constants doesn't overflow.  */
      if (code == MULT_EXPR)
        return fold_build2 (tcode, ctype,
                            fold_build2 (code, ctype,
                                         fold_convert (ctype, op0),
                                         fold_convert (ctype, c)),
                            op1);

misses the fact that the multiplication of the non-constant part can
also overflow.  I think the case has to be removed completely.
Comment 6 Jakub Jelinek 2013-04-10 08:05:52 UTC
Better testcase:
__attribute__((noinline, noclone)) void
foo (int v)
{
  int x = -214748365 * (v - 1);
  if (x != -1932735285)
    __builtin_abort ();
}

int
main ()
{
  foo (10);
  return 0;
}

This doesn't really look like an expansion issue, but folder issue, introduced
in between r152207 and r152360 (going to bisect it now).

The good *.original dump is:
  int x = (1 - v) * 214748365;
  if (x != -1932735285)
while bad is:
  int x = v * -214748365 + 214748365;
  if (x != -1932735285)
If we want to do this, we'd need to perform the addition in unsigned type instead of signed.
Comment 7 Jakub Jelinek 2013-04-10 08:23:00 UTC
I guess http://gcc.gnu.org/r152217 .  Anyway, shouldn't be hard to reproduce even with plus (say if v is negative).

I've tried
__attribute__((noinline, noclone)) void
foo (int v)
{
  int x = 214748365 * (v + 1);
  if (x != -1932735285)
    __builtin_abort ();
}

int
main ()
{
  foo (-10);
  return 0;
}
but we don't miscompile it, because while we perform the distributive law in that case too (also wrongly), it is folded back to the (v + 1) * 214748365
form (after recursing several times between the two forms).
Comment 8 Jakub Jelinek 2013-04-10 08:24:46 UTC
That said, removing that hunk completely would remove it even for the case where the type has defined overflow, shouldn't we remove it just for undefined overflow (or, replace the addition/subtraction with undefined one)?
Comment 9 Richard Biener 2013-04-10 09:29:43 UTC
(In reply to comment #8)
> That said, removing that hunk completely would remove it even for the case
> where the type has defined overflow, shouldn't we remove it just for undefined
> overflow (or, replace the addition/subtraction with undefined one)?

Yes, that works (remove it for undefined overflow).  Replacing it with
defined overflow one, too, but I prefer to make extract_muldiv do less
(it's a scary beast ...).
Comment 10 Jakub Jelinek 2013-04-11 07:45:59 UTC
Author: jakub
Date: Thu Apr 11 07:30:20 2013
New Revision: 197692

URL: http://gcc.gnu.org/viewcvs?rev=197692&root=gcc&view=rev
Log:
	PR tree-optimization/56899
	* fold-const.c (extract_muldiv_1): Apply distributive law
	only if TYPE_OVERFLOW_WRAPS (ctype).

	* gcc.c-torture/execute/pr56899.c: New test.

Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr56899.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/fold-const.c
    trunk/gcc/testsuite/ChangeLog

Author: jakub
Date: Thu Apr 11 07:37:17 2013
New Revision: 197693

URL: http://gcc.gnu.org/viewcvs?rev=197693&root=gcc&view=rev
Log:
	PR tree-optimization/56899
	* fold-const.c (extract_muldiv_1): Apply distributive law
	only if TYPE_OVERFLOW_WRAPS (ctype).

	* gcc.c-torture/execute/pr56899.c: New test.

Added:
    branches/gcc-4_8-branch/gcc/testsuite/gcc.c-torture/execute/pr56899.c
Modified:
    branches/gcc-4_8-branch/gcc/ChangeLog
    branches/gcc-4_8-branch/gcc/fold-const.c
    branches/gcc-4_8-branch/gcc/testsuite/ChangeLog
Comment 11 Richard Biener 2014-06-12 13:26:52 UTC
Fixed in 4.8.0?