Bug 30484 - Miscompilation of remainder expressions on CPUs of the i386 family
Summary: Miscompilation of remainder expressions on CPUs of the i386 family
Status: UNCONFIRMED
Alias: None
Product: gcc
Classification: Unclassified
Component: target (show other bugs)
Version: 4.1.1
: P3 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
: 37503 (view as bug list)
Depends on:
Blocks: 22200
  Show dependency treegraph
 
Reported: 2007-01-16 15:19 UTC by bagnara
Modified: 2010-02-19 13:08 UTC (History)
7 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description bagnara 2007-01-16 15:19:39 UTC
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).
Comment 1 Vincent Lefèvre 2007-01-16 22:03:59 UTC
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;
}
Comment 2 Vincent Lefèvre 2007-01-16 22:10:37 UTC
-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.
Comment 3 Andrew Pinski 2007-01-16 22:11:28 UTC
(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 :).
Comment 4 Andrew Pinski 2007-01-16 22:15:46 UTC
(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.
Comment 5 Joost VandeVondele 2007-01-17 07:14:43 UTC
(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.
Comment 6 Michael Veksler 2007-01-17 08:49:10 UTC
(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.
Comment 7 nightstrike 2008-09-12 20:32:57 UTC
*** Bug 37503 has been marked as a duplicate of this bug. ***
Comment 8 Joseph S. Myers 2008-09-12 20:39:32 UTC
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.
Comment 9 Joseph S. Myers 2008-09-12 20:41:52 UTC
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.
Comment 10 Joseph S. Myers 2009-02-21 18:45:39 UTC
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.
Comment 11 Vincent Lefèvre 2010-02-19 13:08:09 UTC
(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.