INT_MIN % -1

INT_MIN % -1

[Morten Welinder]

What is the value of  INT_MIN % -1  supposed to be, assuming 32-bit
ints and two-complement representation.

C99 seems to be telling us two things about '%':

(1) It computes remainder for integer division.
(2) "If the quotient  a/b  is representable, the expression
    (a/b)*b + a%b  shall equal  a."

(2) is not useful for the case since the quotient is not representable.  I'd
say that (1) means that the result should be zero, but that would be rather
expensive to implement as you would have to test for -1 at runtime on i386,
for example.

I would claim that there is no overflow in the calculation: both arguments
and the result are perfectly representable as 32-bit ints.  The fact that
the quotient of the same values, if performed, overflows is no more relevant
that the fact that you can't take the square root of the two sides.

gcc 3.4 on solaris/sparc seems to get zero; gcc 3.3.1 on linux gives me a
crash at runtime.  (Because the signed integer division instruction traps
as documented.)

Comments?

Morten



-----------------------------------------------------------------------------

> uname -a
SunOS troll 5.8 Generic_117350-11 sun4u sparc
> ./a.out 
-2147483648 % -1 (const) = 0
-2147483648 % -1 (non-const) = 0

-----------------------------------------------------------------------------

> uname -a
Linux darter 2.4.21-243-default #1 Thu Aug 12 15:22:14 UTC 2004 i686 i686 i386 GNU/Linux
> ./a.out 
-2147483648 % -1 (const) = 0
Floating point exception

-----------------------------------------------------------------------------

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

#define A INT_MIN
#define B -1

static int a = A;
static int b = B;

int
main (int argc, char **argv)
{
  printf ("%d %% %d (const) = %d\n", A, B, A % B);
  printf ("%d %% %d (non-const) = %d\n", a, b, a % b);
  return 0;
}

Re: INT_MIN % -1

[David Daney]

Morten Welinder wrote:
> What is the value of  INT_MIN % -1  supposed to be, assuming 32-bit
> ints and two-complement representation.
> 
> C99 seems to be telling us two things about '%':
> 
> (1) It computes remainder for integer division.
> (2) "If the quotient  a/b  is representable, the expression
>     (a/b)*b + a%b  shall equal  a."
> 
> (2) is not useful for the case since the quotient is not representable.  I'd
> say that (1) means that the result should be zero, but that would be rather
> expensive to implement as you would have to test for -1 at runtime on i386,
> for example.
> 
> I would claim that there is no overflow in the calculation: both arguments
> and the result are perfectly representable as 32-bit ints.  The fact that
> the quotient of the same values, if performed, overflows is no more relevant
> that the fact that you can't take the square root of the two sides.
> 
> gcc 3.4 on solaris/sparc seems to get zero; gcc 3.3.1 on linux gives me a
> crash at runtime.  (Because the signed integer division instruction traps
> as documented.)
> 
> Comments?
> 
> Morten
> 
> 
> 
> -----------------------------------------------------------------------------
> 
> 
>>uname -a
> 
> SunOS troll 5.8 Generic_117350-11 sun4u sparc
> 
>>./a.out 
> 
> -2147483648 % -1 (const) = 0
> -2147483648 % -1 (non-const) = 0
> 
> -----------------------------------------------------------------------------
> 
> 
>>uname -a
> 
> Linux darter 2.4.21-243-default #1 Thu Aug 12 15:22:14 UTC 2004 i686 i686 i386 GNU/Linux
> 
>>./a.out 
> 
> -2147483648 % -1 (const) = 0
> Floating point exception
> 
> -----------------------------------------------------------------------------

/junk # uname -a
Linux (none) 2.4.25-Avtrex #152 Mon Nov 15 10:51:36 PST 2004 mips unknown
/junk # ./bla
-2147483648 % -1 (const) = 0
-2147483648 % -1 (non-const) = 0

Intel chose to trap.  Sun and MIPS chose not to.

I don't have the spec. in front of me, but I can imagine that it allows for
this.

If you want well defined behavior use something like java.  The JLS
specifies exactly what should happen in this case.

David Daney.

Re: INT_MIN % -1

[Andreas Schwab]

terra@gnome.org (Morten Welinder) writes:

> gcc 3.4 on solaris/sparc seems to get zero; gcc 3.3.1 on linux gives me a
> crash at runtime.  (Because the signed integer division instruction traps
> as documented.)

FWIW, on m68k you'll get -1 (because the divs insn does not modify the
operands on overflow and doesn't trap either).

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux Products GmbH, Maxfeldstraße 5, 90409 Nürnberg, Germany
Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: INT_MIN % -1

[Paul Schlie]

> Andreas wrote:
>> terra@gnome.org (Morten Welinder) writes:
>>
>> gcc 3.4 on solaris/sparc seems to get zero; gcc 3.3.1 on linux gives me a
>> crash at runtime.  (Because the signed integer division instruction traps
> as documented.)
>
> FWIW, on m68k you'll get -1 (because the divs insn does not modify the
> operands on overflow and doesn't trap either).

Then would guess divs shouldn't be used with operands which may yield
needlessly incorrect results, and would guess it should likely be considered
a code-generator bug if it is; as a compiler which produces code which
may generate needlessly incorrect results (even if misguidedly allowed
by the standard), isn't truly as useful as one which reliably produces
reasonably correct results.

(where I'm assuming: (-INT_MIN / -1) => -1 isn't reasonably correct or
necessary, nor is a run-time exception/trap)

Although possibly naive, I'd like to think that the C standard won't be used
as a crutch, but that GCC may rise above many of the unspecified behaviors,
and establish instead, well defined logically consistent useful ones, which
others may aspire to emulate.

Re: INT_MIN % -1

[Robert Dewar]

Paul Schlie wrote:

> (where I'm assuming: (-INT_MIN / -1) => -1 isn't reasonably correct or
> necessary, nor is a run-time exception/trap)
> 
> Although possibly naive, I'd like to think that the C standard won't be used
> as a crutch, but that GCC may rise above many of the unspecified behaviors,
> and establish instead, well defined logically consistent useful ones, which
> others may aspire to emulate.

One possibility would be to have an optional divide by zero trap that sets
the right result and continues. Then there is a special compiler switch
that sets up this trap routine if you really really really want this not
very useful marginal behavior (a real division by zero is undefined, so
it is fine to do anything you like). That being said, GNAT (the Ada front
end) does go to the trouble of doing this right. Given the source program:

> procedure K is
>    X, Y : Integer;
>    function Id (X : Integer) return Integer is begin return X; end Id;
> begin
>    X := Id (Integer'First);
>    Y := Id ( - 1);
>    X := X mod y;
> end;

(the Id function is to stop the compiler from doing optimizing value tracing :-)

The generated code (-gnatG output) (with checks off to simplifty) looks like:

procedure k is
    x : integer;
    y : integer;

    function k__id (x : integer) return integer is
    begin
       return x;
    end k__id;
begin
    x := k__id (-16#8000_0000#);
    y := k__id (-1);
    x := (if y = -1 then 0 else x mod y);
    return;
end k;

The test for y = -1 is precisely to handle this case, and it is only one test.
Note that the cost in Ada is generally smaller than in C, because we know more
about the range of variables. For example, the Ada program:

procedure K is
    X, Y : Integer range -1000 .. +1000;
    function Id (X  : Integer) return Integer is begin return X; end Id;
begin
    X := Id (1);
    Y := Id ( - 1);
    X := X mod y;
end;

Does not generate the check for -1, because it knows that X cannot be Integer'First.

Re: INT_MIN % -1

[Paul Schlie]

With reference to the below:

I would guess that rather than attempting to expose a check for a / or % by
-1 to the compiler, I would assume that it's best handled by the back end
during code generations, as the most efficient solution is target specific:

- for targets which have hardware / and/or % instruction support and handle
  things properly, nothing special is required other than a correctly coded
  .md file.

- for targets which have hardware/ and/or % instruction support, but don't
  handle things properly, it's likely sufficient to incorporate a test for
  a -1 divisor into the .md description of the operations (which fortunately
  will likely only minimally affect performance, as / and % functions tend
  to often be multi-cycle to begin with, if supported at all).

- for targets which don't have hardware / and/or % instruction support,
  it's likely simplest to trasparently incorporate correct behavior into
  the libgcc2 built-in / and/or % function definitions.

Independently, in circumstances where either the dividend or divisor are
constants, the middle-end may always choose to eliminate the / or %
operations altogether, if it's result can be determined statically.


> From: Robert Dewar <dewar@gnat.com>
> 
>> Paul Schlie wrote:
>> 
>> (where I'm assuming: (-INT_MIN / -1) => -1 isn't reasonably correct or
>> necessary, nor is a run-time exception/trap)
>> 
>> Although possibly naive, I'd like to think that the C standard won't be used
>> as a crutch, but that GCC may rise above many of the unspecified behaviors,
>> and establish instead, well defined logically consistent useful ones, which
>> others may aspire to emulate.
> 
> One possibility would be to have an optional divide by zero trap that sets
> the right result and continues. Then there is a special compiler switch
> that sets up this trap routine if you really really really want this not
> very useful marginal behavior (a real division by zero is undefined, so
> it is fine to do anything you like). That being said, GNAT (the Ada front
> end) does go to the trouble of doing this right. Given the source program:
> 
>> procedure K is
>>    X, Y : Integer;
>>    function Id (X : Integer) return Integer is begin return X; end Id;
>> begin
>>    X := Id (Integer'First);
>>    Y := Id ( - 1);
>>    X := X mod y;
>> end;
> 
> (the Id function is to stop the compiler from doing optimizing value tracing
> :-)
> 
> The generated code (-gnatG output) (with checks off to simplifty) looks like:
> 
> procedure k is
>     x : integer;
>     y : integer;
> 
>     function k__id (x : integer) return integer is
>     begin
>        return x;
>     end k__id;
> begin
>     x := k__id (-16#8000_0000#);
>     y := k__id (-1);
>     x := (if y = -1 then 0 else x mod y);
>     return;
> end k;
> 
> The test for y = -1 is precisely to handle this case, and it is only one test.
> Note that the cost in Ada is generally smaller than in C, because we know more
> about the range of variables. For example, the Ada program:
> 
> procedure K is
>     X, Y : Integer range -1000 .. +1000;
>     function Id (X  : Integer) return Integer is begin return X; end Id;
> begin
>     X := Id (1);
>     Y := Id ( - 1);
>     X := X mod y;
> end;
> 
> Does not generate the check for -1, because it knows that X cannot be
> Integer'First.
> 

Re: INT_MIN % -1

[Robert Dewar]

Paul Schlie wrote:
> With reference to the below:
> 
> I would guess that rather than attempting to expose a check for a / or % by
> -1 to the compiler, I would assume that it's best handled by the back end
> during code generations, as the most efficient solution is target specific: 

Indeed, but remember we would need to have both operations, one with the
special handling and one without.

Re: INT_MIN % -1

[Paul Schlie]

> From: Robert Dewar <dewar@gnat.com>
> 
> Paul Schlie wrote:
>> With reference to the below:
>> 
>> I would guess that rather than attempting to expose a check for a / or % by
>> -1 to the compiler, I would assume that it's best handled by the back end
>> during code generations, as the most efficient solution is target specific:
> 
> Indeed, but remember we would need to have both operations, one with the
> special handling and one without.

Understood, as ADA programs may bound the domain of it's variables
guaranteeing that the operation would be well behaved within the bounds of
it's operands; but wonder if saving a few cycles out of the likely several
required for a divide or modulo operation would likely be worth the added,
albeit minor, complexity?

Re: INT_MIN % -1

[Robert Dewar]

Paul Schlie wrote:

> Understood, as ADA programs may bound the domain of it's variables
> guaranteeing that the operation would be well behaved within the bounds of
> it's operands; but wonder if saving a few cycles out of the likely several
> required for a divide or modulo operation would likely be worth the added,
> albeit minor, complexity?
> 
> 
I think so, it's by far the most common case, and it is a pity to take a hit
in the normal case in Ada just so that a pathological case in C can be done
right :-) Actually even in C, you can often tell that the bad case is impossible.

P.S. The language is Ada, not ADA, it's a woman's name. ADA is the Americans with
Disability Act (among others) and there is a great poster of Clinton saying "I want
you to pay attention to ADA!" :-)