Pathalogical divides

Pathalogical divides

[Richard Kenner]

Consider the following program on x86:

int rem (int a, int b) { return a % b; }

int
main ()
{
  printf ("%d\n", rem (0x80000000, -1));;
}

When run, rather than producing zero, as expected, it gets a SIGFPE.
This is because the division of the largest negative integer by negative one
results in an overflow.

So the first question is whether this is valid C behavior.

Next, compile the above with -O3 on an x86 and notice that GCC gets a
SIGFPE when constant-folding.

Finally, consider:

int
foo (int a, int b)
{
  return (a - ((a == 0x80000000 && b == -1) ? 0 : a % b)) / b;
}

This program when passed "normal" arguments does not get an overflow.
But GCC pulls the conditional out of the subtraction and division and
causes the compiler to run into the SIGFPE above.

I think the compiler crash needs to be fixed.  We can do it either by
protecting the integer part of simplify_binary_operation against SIGFPE
just like the FP or explicitly testing for this case just like we
check for divide by zero.

Any thoughts about whether we need a run-time test for this case
in the "%" operator?

Re: Pathalogical divides

[Andreas Schwab]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 755 bytes --]

kenner@vlsi1.ultra.nyu.edu (Richard Kenner) writes:

|> Consider the following program on x86:
|> 
|> int rem (int a, int b) { return a % b; }
|> 
|> int
|> main ()
|> {
|>   printf ("%d\n", rem (0x80000000, -1));;
|> }
|> 
|> When run, rather than producing zero, as expected, it gets a SIGFPE.
|> This is because the division of the largest negative integer by negative one
|> results in an overflow.
|> 
|> So the first question is whether this is valid C behavior.

IMHO, yes.  You are invoking undefined behaviour.

Andreas.

-- 
Andreas Schwab                                  "And now for something
SuSE Labs                                        completely different."
Andreas.Schwab@suse.de
SuSE GmbH, Schanzäckerstr. 10, D-90443 Nürnberg

Re: Pathalogical divides

[Jeffrey A Law]

  In message < 10009211926.AA26210@vlsi1.ultra.nyu.edu >you write:
  > Consider the following program on x86:
  > 
  > int rem (int a, int b) { return a % b; }
  > 
  > int
  > main ()
  > {
  >   printf ("%d\n", rem (0x80000000, -1));;
  > }
  > 
  > When run, rather than producing zero, as expected, it gets a SIGFPE.
  > This is because the division of the largest negative integer by negative on
  > e
  > results in an overflow.
  > 
  > So the first question is whether this is valid C behavior.
Not valid C behavior.

  > Next, compile the above with -O3 on an x86 and notice that GCC gets a
  > SIGFPE when constant-folding.
  > 
  > Finally, consider:
  > 
  > int
  > foo (int a, int b)
  > {
  >   return (a - ((a == 0x80000000 && b == -1) ? 0 : a % b)) / b;
  > }
  > 
  > This program when passed "normal" arguments does not get an overflow.
  > But GCC pulls the conditional out of the subtraction and division and
  > causes the compiler to run into the SIGFPE above.
  > 
  > I think the compiler crash needs to be fixed.  We can do it either by
  > protecting the integer part of simplify_binary_operation against SIGFPE
  > just like the FP or explicitly testing for this case just like we
  > check for divide by zero.
We need to fix the compiler crash.
jeff

Re: Pathalogical divides

[Alexandre Oliva]

On Sep 22, 2000, Jeffrey A Law <law@cygnus.com> wrote:

>   In message < 10009211926.AA26210@vlsi1.ultra.nyu.edu >you write:

>> This is because the division of the largest negative integer by
>> negative one results in an overflow.

>> So the first question is whether this is valid C behavior.

> Not valid C behavior.

Err...  In my copy of the C Standard, integer overflow invokes
undefined behavior, so signalling is acceptable behavior (just like
anything else :-)

-- 
Alexandre Oliva   Enjoy Guarana', see http://www.ic.unicamp.br/~oliva/
Red Hat GCC Developer                  aoliva@{cygnus.com, redhat.com}
CS PhD student at IC-Unicamp        oliva@{lsd.ic.unicamp.br, gnu.org}
Free Software Evangelist    *Please* write to mailing lists, not to me

Re: Pathalogical divides

[Geoff Keating]

kenner@vlsi1.ultra.nyu.edu (Richard Kenner) writes:

> Consider the following program on x86:
> 
> int rem (int a, int b) { return a % b; }
> 
> int
> main ()
> {
>   printf ("%d\n", rem (0x80000000, -1));;
> }
> 
> When run, rather than producing zero, as expected, it gets a SIGFPE.
> This is because the division of the largest negative integer by negative one
> results in an overflow.
> 
> So the first question is whether this is valid C behavior.

Yes.  C interpreters are permitted to do anything they like when
signed integer arithmetic overflows, including producing a signal.

> Next, compile the above with -O3 on an x86 and notice that GCC gets a
> SIGFPE when constant-folding.

> Finally, consider:
> 
> int
> foo (int a, int b)
> {
>   return (a - ((a == 0x80000000 && b == -1) ? 0 : a % b)) / b;
> }
> 
> This program when passed "normal" arguments does not get an overflow.
> But GCC pulls the conditional out of the subtraction and division and
> causes the compiler to run into the SIGFPE above.

Note that this code is valid C code, so we can't produce an _error_ in
this case.  Thus I don't think we want to allow the signal to happen.

> I think the compiler crash needs to be fixed.  We can do it either by
> protecting the integer part of simplify_binary_operation against SIGFPE
> just like the FP or explicitly testing for this case just like we
> check for divide by zero.

I suggest the second.  We could then produce a helpful warning
message (but not an error).

> Any thoughts about whether we need a run-time test for this case
> in the "%" operator?

I don't think we do.  (If we do, of course it's only necessary for x86.)

-- 
- Geoffrey Keating <geoffk@cygnus.com>

Re: Pathalogical divides

[Robert Dewar]

<<Yes.  C interpreters are permitted to do anything they like when
signed integer arithmetic overflows, including producing a signal.
>>

Actually while I think that is a valid interpretation of K&R rules,
it is VERY difficult to read the ANSI standard this way, check out
the exact wording, which seems to imply that the result is implementation
defined within certain limits, but I cannot read it to allow a signal.

By the way, the most efficient way of computing a%b to avoid
this problem is a%(abs b) being careful NOT to check for overflow
on the abs operation (not that one is likely to do so in C anyway :-)

Re: Pathalogical divides

[Geoff Keating]

> Cc: gcc@gcc.gnu.org
> Date: Mon, 25 Sep 2000 02:07:04 -0400 (EDT)
> From: dewar@gnat.com (Robert Dewar)
> 
> <<Yes.  C interpreters are permitted to do anything they like when
> signed integer arithmetic overflows, including producing a signal.
> >>
> 
> Actually while I think that is a valid interpretation of K&R rules,
> it is VERY difficult to read the ANSI standard this way, check out
> the exact wording, which seems to imply that the result is implementation
> defined within certain limits, but I cannot read it to allow a signal.

???

It says, in s. 6.5 paragraph 5 of ISO/IEC 9899:1999:

 If an _exceptional condition_ occurs during the evaluation of an
 expression (that is, if the result is not mathematically defined or
 not in the range of representable values for its type), the behaviour
 is undefined.

'undefined behaviour' can always include a signal, or anything else
that a mad compiler designer could dream up.

-- 
- Geoffrey Keating <geoffk@cygnus.com>

Re: Pathalogical divides

[Richard Kenner]

    It says, in s. 6.5 paragraph 5 of ISO/IEC 9899:1999:

     If an _exceptional condition_ occurs during the evaluation of an
     expression (that is, if the result is not mathematically defined or
     not in the range of representable values for its type), the behaviour
     is undefined.

    'undefined behaviour' can always include a signal, or anything else
    that a mad compiler designer could dream up.

Sure, except that the (largest_negtive_number % -1) *is* mathematically
defined: anything mod -1 is 0!  It's the corresponding *division* that's
undefined, but that isn't what the programmer is requesting.

Re: Pathalogical divides

[Geoff Keating]

> Date: Mon, 25 Sep 00 05:57:11 EDT
> From: kenner@vlsi1.ultra.nyu.edu (Richard Kenner)
> Cc: gcc@gcc.gnu.org
> 
>     It says, in s. 6.5 paragraph 5 of ISO/IEC 9899:1999:
> 
>      If an _exceptional condition_ occurs during the evaluation of an
>      expression (that is, if the result is not mathematically defined or
>      not in the range of representable values for its type), the behaviour
>      is undefined.
> 
>     'undefined behaviour' can always include a signal, or anything else
>     that a mad compiler designer could dream up.
> 
> Sure, except that the (largest_negtive_number % -1) *is* mathematically
> defined: anything mod -1 is 0!  It's the corresponding *division* that's
> undefined, but that isn't what the programmer is requesting.

I see!  You are right.  Yes, this is required to work.

-- 
- Geoffrey Keating <geoffk@cygnus.com>

Re: Pathalogical divides

[Jamie Lokier]

Geoff Keating wrote:
> > Sure, except that the (largest_negtive_number % -1) *is* mathematically
> > defined: anything mod -1 is 0!  It's the corresponding *division* that's
> > undefined, but that isn't what the programmer is requesting.
> 
> I see!  You are right.  Yes, this is required to work.

And if it did work, GCC wouldn't crash when compiled with itself :-)

-- Jamie

Re: Pathalogical divides

[Robert Dewar]

<< If an _exceptional condition_ occurs during the evaluation of an
 expression (that is, if the result is not mathematically defined or
 not in the range of representable values for its type), the behaviour
 is undefined.
>>

I don't think this applies, in this csae, the result IS mathematicaly
defined, and IS in the range of representable values for its type (and
in the case of %, all the posisble values allowed by the description
in the RM are in this category).

If you follow this argument, you would permit an implementation to
evaluate

a+b by adding a large number and then subtracting it, and would accept
it getting a signal in some cases.

Re: Pathalogical divides

[Robert Dewar]

>> This is because the division of the largest negative integer by
>> negative one results in an overflow.

But that is part of the *implementation* not the semantic definition

<<Err...  In my copy of the C Standard, integer overflow invokes
undefined behavior, so signalling is acceptable behavior (just like
anything else :-)
>>

That is talking about operations which at the *semantic* level cause
integer overflow.

a % (-1) is defined for all values of a and does not cause integer
overflow, and furthermore in this particular case the range of possible
values allowed by the standard includes only zero.