[Bug target/30484] New: Miscompilation of remainder expressions on CPUs of the i386 family

[Bug target/30484] New: Miscompilation of remainder expressions on CPUs of the i386 family

[bagnara at cs dot unipr dot it]

The program below shows (at all the optimization levels) a miscompilation of
the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of
the i386 family.

#include <limits.h>
#include <stdio.h>

int minus_one(int n) {
  return (n+1)*(n-1)-n*n;
}

void p(int x, int y) {
  int z = x % y;
  printf("%d %% %d -> %d\n", x, y, z);
}

int main(int argc, char** argv) {
  p(INT_MIN, minus_one(argc));
}

For simpler programs, the behavior depends on the ability of the optimizer to
realize that the divisor is -1, in which case the compiler evaluates the
remainder expression (to 0, at compile-time) and no signal is raised.

Since the remainder is always defined, this violates the C standard.

By the way, the Ariane 5 Flight 501 crash was caused by an unexpected exception
(http://en.wikipedia.org/wiki/Ariane_5_Flight_501).


-- 
           Summary: Miscompilation of remainder expressions on CPUs of the
                    i386 family
           Product: gcc
           Version: 4.1.1
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: target
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: bagnara at cs dot unipr dot it


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

[Bug target/30484] Miscompilation of remainder expressions on CPUs of the i386 family

[vincent at vinc17 dot org]

------- Comment #1 from vincent at vinc17 dot org  2007-01-16 22:03 -------
Is this specific to x86? On PowerPC (gcc 4.0.1 from Mac OS X), I get:

-2147483648 % -1 -> -2147483648

Ditto with:

#include <limits.h>
#include <stdio.h>

int main (void)
{
  volatile int i = INT_MIN, j = -1;
  printf ("%d\n", i % j);
  return 0;
}


-- 

vincent at vinc17 dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |vincent at vinc17 dot org


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

[Bug target/30484] Miscompilation of remainder expressions on CPUs of the i386 family

[vincent at vinc17 dot org]

------- Comment #2 from vincent at vinc17 dot org  2007-01-16 22:10 -------
-2147483648, this was on a G5, with gcc 4.0.1 under Mac OS X. On a G4 under
Linux, with gcc 4.1.2 prerelease (Debian), I get 2147483647.


-- 


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

[Bug target/30484] Miscompilation of remainder expressions on CPUs of the i386 family

[pinskia at gcc dot gnu dot org]

------- Comment #3 from pinskia at gcc dot gnu dot org  2007-01-16 22:11 -------
(In reply to comment #1)
> Is this specific to x86? On PowerPC (gcc 4.0.1 from Mac OS X), I get:

This is because the PPC ISA says for divide:
If an attempt is made to perform either of the divisions -- 0x8000_0000 / -1 or
<anything> / 0, then the contents of rD are undefined, as are the contents of
the LT, GT, and EQ bits of the CR0 field (if Rc = 1).  In this case, if OE = 1
then OV is set.

The 32-bit signed remainder of diving the contents of rA by the contents of rB
can be computed as follows, exept in the case that hthe constnat of ra = - 2^31
and the constants of rB = -1.
divw rD, rA, rB
mullw rD, rD, rB
subf rD, rD, rA

----------------------
So the ISA in fact even mentions this case :).


-- 


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

[Bug target/30484] Miscompilation of remainder expressions on CPUs of the i386 family

[pinskia at gcc dot gnu dot org]

------- Comment #4 from pinskia at gcc dot gnu dot org  2007-01-16 22:15 -------
(In reply to comment #3)
> So the ISA in fact even mentions this case :).
But the PPC compiler writers guide does not talk about that case, hmmm.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|major                       |normal


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

[Bug target/30484] Miscompilation of remainder expressions on CPUs of the i386 family

[jv244 at cam dot ac dot uk]

------- Comment #5 from jv244 at cam dot ac dot uk  2007-01-17 07:14 -------
(In reply to comment #0)
> The program below shows (at all the optimization levels) a miscompilation of
> the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of
> the i386 family.

notice that this is language dependent. I.e. in Fortran the equivalent of the
above 'INT_MIN % -1' is undefined. So, whatever the fix for C and friends, it
should not slow down Fortran programs using MOD.


-- 


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

[Bug target/30484] Miscompilation of remainder expressions on CPUs of the i386 family

[veksler at il dot ibm dot com]

------- Comment #6 from veksler at il dot ibm dot com  2007-01-17 08:49 -------
(In reply to comment #0)
> The program below shows (at all the optimization levels) a miscompilation of
> the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of
> the i386 family.
For the record on Linux i386, this was my suggestion for the best performing
work-around (fastest at least for all cases other than INT_MIN % -1).
Intercept SIGFPE, and if it comes from
  idivl
then set the remainder to 0, and the quotient to INT_MIN (in C/C++ we are
allowed to do this because INT_MIN/-1 is undefined).

There are several technical problems to this suggestion:

(1)
To avoid interference with user assembly code that expects SIGFPE in case of
INT_MIN/-1 (e.g. -ftrapv), the compiler will have to mark this 
  idivl 
in some special way (e.g. add some useless prefixes, or write something
in one of the ELF sections).

(2)
Who should intercept SIGFPE? User space or kernel?

(2.1)
User space is much more complicated, because it might interfere with
other user set SIGFPE signal handlers. libgcc would have to chain
the signal handlers.

(2.2)
If implemented in the kernel then it will take much more time to see this
change propagate to all users. This also means that BSD,Hurd and cygwin 
will all have to use a different fix, each.


-- 

veksler at il dot ibm dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |veksler at il dot ibm dot
                   |                            |com


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

[Bug target/30484] Miscompilation of remainder expressions on CPUs of the i386 family

[nightstrike at gmail dot com]

------- Comment #7 from nightstrike at gmail dot com  2008-09-12 20:32 -------
*** Bug 37503 has been marked as a duplicate of this bug. ***


-- 

nightstrike at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |nightstrike at gmail dot com


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

[Bug target/30484] Miscompilation of remainder expressions on CPUs of the i386 family

[jsm28 at gcc dot gnu dot org]

------- Comment #8 from jsm28 at gcc dot gnu dot org  2008-09-12 20:39 -------
I suggest an option such as -fdivide-checks, off by default.  -std=c99 and
other conformance options, for languages where INT_MIN % -1 is defined, would
enable this option unless -fno-divide-checks is specified by the user.  -fwrapv
would enable this option unless -fno-divide-checks is specified by the user.

The option would cause checks to be inserted at gimplification time or earlier:
A % B would evaluate A and B for their side effects, then check whether B is -1
and if so evaluate to 0 instead of carrying out the modulo operation.  If
flag_wrapv is set as well, similar checks would be applied to division to catch
INT_MIN / -1.

If a target macro is defined that says that the implementations of the relevant
RTL insn patterns will generate the desired results (0 for modulo, INT_MIN
for division) without trapping, then the option would have no effect.  I don't
know what processors this might apply to.

libgcc functions for long long division and modulo need checking.  I'd guess
they can be arranged to get this right unconditionally rather than needing to
call different functions in the two modes.


-- 


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

[Bug target/30484] Miscompilation of remainder expressions on CPUs of the i386 family

[jsm28 at gcc dot gnu dot org]

------- Comment #9 from jsm28 at gcc dot gnu dot org  2008-09-12 20:41 -------
Note libgcc functions would only need to get it right for CPUs defining the
macro, if in other cases the source checks would be inserted anyway.  Or the
macro could depend on the mode of the division/modulo operation.


-- 


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

[Bug target/30484] Miscompilation of remainder expressions on CPUs of the i386 family

[jsm28 at gcc dot gnu dot org]

------- Comment #10 from jsm28 at gcc dot gnu dot org  2009-02-21 18:45 -------
This issue was discussed on the WG14 reflector in October 2008, and the general
view was that the standard should not make INT_MIN % -1 well defined (as this
would impose a significant performance cost on many programs to benefit very
few) and probably didn't intend to.

There is still a bug for the -fwrapv case, where clearly both INT_MIN / -1
and INT_MIN % -1 should be well defined, but probably the extra checks
if implemented should only be enabled implicitly for -fwrapv, not for C
standards conformance modes.


-- 


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

[Bug target/30484] Miscompilation of remainder expressions on CPUs of the i386 family

[vincent at vinc17 dot org]

------- Comment #11 from vincent at vinc17 dot org  2010-02-19 13:08 -------
(In reply to comment #10)
> This issue was discussed on the WG14 reflector in October 2008, and the general
> view was that the standard should not make INT_MIN % -1 well defined (as this
> would impose a significant performance cost on many programs to benefit very
> few) and probably didn't intend to.

My opinion is that introducing an undefined behavior on a particular case like
that is a bad idea: If this case can occur in some application, then the
programmer would have to do a test anyway (and this would even be more costly
as the test would be needed for all implementations, instead of being generated
by the compiler only when needed) or the software could behave erratically
(which is worse). If this case cannot occur, then the programmer should have a
way to tell that to the compiler.


-- 


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