Integer Overflow

[Ben Bacarisse]

Le 30/12/10 00:23, Keith Thompson a écrit :

A cast suffices to transform an unsigned to a signed so if you want
overflow with unsigned just cast...

unsigned a , b , c;

c = (int)b+(int)c;

Casting does not seem to fit the bill. With b == INT_MAX and c == 1
this operation will overflow but the corresponding unsigned operation
would not.

With b == INT_MAX+1 even the cast will cause an overflow (I think you
said that conversions trigger overflow as well). It's not, technically,
an overflow in C but it does seem wise to treat it in the same way.

 

[Ben Bacarisse]

Le 29/12/10 22:51, Keith Thompson a écrit :

Le 29/12/10 15:34, christian.bau a écrit : [...]
What _precisely_ is the semantics of the "_overflow" function?

It returns 1 if the last operation overflowed, zero if not.
Concerned operations: signed +,-,*, and /.

Conversions?

Overflow should be detected in conversions.

This raises the question of what the 'last operation' is. You've shown

c = a + b;
if (_overflow()) ...

as the canonical example of this feature, but the "last operation" is
the conversion of the value of 'a + b' to the type of 'c'. This
operation may be the one I want to test for overflow. How does the
compiler know which overflow (the addition or the conversion) I am
interested in?

<snip>

 

[BartC]

Le 29/12/10 22:54, BartC a écrit :

In that the FIRST overflow will stop computation telling you
where it failed (file and line)

So it's more like:

pragma trap_overflow on/off

Undefined since you do not know how the compiler will schedule
operations.

The proposal by CB I think required this to return True when any overflow
occurs. He wasn't concerned with identifying exactly which two terms was the
cause.

To make it work like that, it may be necessary to insert code to check every
(eligible) operation, and to short-circuit the evaluation whenever overflow
is detected (which is not so simple because some terms may be on the stack).
Alternatively to maintain a separate latching flag, but to complete the
computation even when overflow occurs.

However CB also suggested the expression should have no side-effects, which
would exclude doing:

if (_overflow(d=a+b+c) )...

which would make it difficult to obtain the result of the operation! At
least, without having to repeat it outside of _overflow. It would however
make it easier to short-circuit the evaluation. It depends on whether such
an embedded assignment should still complete (with the wrong result) when
there is overflow.

The restriction on not having function calls in the expression I think is to
avoid having nested _overflow() calls, and also because a function can
contain arithmetic ops that are not checked for overflow. (And in your
variation on C, overloaded operators can be mapped to functions with the
same problem.)

 

[Ike Naar]

Le 30/12/10 11:09, Ike Naar a ?crit :

"Dead" means in this context that no software developers
are working for that machine any more.

There is at least one software developer who uses Alpha for developing
software. The software is supposed to be portable, so it's not
specifically written _for_ the Alpha, but it can run on it. The
Alpha has characteristics that make it a nice platform for testing
the software.

An example of a well-known software product that is still being
maintained for the Alpha is the NetBSD operating system.
NetBSD/alpha 5.1 was released fairly recently (Nov 2010).

 

[jacob navia]

Le 30/12/10 14:34, Ben Bacarisse a écrit :

Le 29/12/10 22:51, Keith Thompson a écrit :

Le 29/12/10 15:34, christian.bau a écrit :
[...]
What _precisely_ is the semantics of the "_overflow" function?

It returns 1 if the last operation overflowed, zero if not.
Concerned operations: signed +,-,*, and /.

Conversions?

Overflow should be detected in conversions.

This raises the question of what the 'last operation' is. You've shown

c = a + b;
if (_overflow()) ...

as the canonical example of this feature, but the "last operation" is
the conversion of the value of 'a + b' to the type of 'c'. This
operation may be the one I want to test for overflow. How does the
compiler know which overflow (the addition or the conversion) I am
interested in?

<snip>

In the example c is int, as b and c. That can't overflow.

Different is
short c;
int b,a;

c =a+b

can overflow (as you say) in a+b AND in the assignment. In that
case you should separate the operations for instance

if (!overflow(a+b)) {
if (_overflow(c=a+b))
// error
}
else // error

 

[jacob navia]

Le 30/12/10 14:25, Ben Bacarisse a écrit :

Casting does not seem to fit the bill. With b == INT_MAX and c == 1
this operation will overflow but the corresponding unsigned operation
would not.

With b == INT_MAX+1 even the cast will cause an overflow (I think you
said that conversions trigger overflow as well). It's not, technically,
an overflow in C but it does seem wise to treat it in the same way.

You are right, cast doesn't work in many cases. I can't tell you right
now how it could be done, need thinking it over.

 

[jacob navia]

Le 30/12/10 16:19, Ben Bacarisse a écrit :

This is something of a distraction. Any processor can be used to detect
overflow -- the question is whether there is a cost.

The Cell SPU has no overflow detection at all. You may feel you can
discount this processor as a valid target for a C compiler, but I'd be
wary of doing that.

Since the general registers of the Cell SPU are 128 bit wide,
you can very easily detect overflow using 32 bit data
by testing one bit of the result. Note that the machine
can't handle more than 32 bit integer operations...

Overflow detection is possible in the Cell SPU, you are
just wrong in this.

Note that I have never spoken about an overflow flag.
It is Thompson that keeps saying that.

MIPS has no overflow bit. It does have overflow-detecting operations
but they raise an exception so the cost of implementing _overflow()
might be quite high.

So what?

You just do not test ALL operations but only the ones where you
are interested in avoiding overflows. You use the form

if (_overflow(expression))

The PowerPC offers most arithmetic instructions in two flavours: one
that sets an overflow bit and one that does not. It may be zero cost to
use the XO-form (that sets the overflow bit) but it seems odd to offer
both if there is no down side.

Same as above: you do not always use the overflow checking but only
when you need it.

 

[Ben Bacarisse]

Le 30/12/10 14:34, Ben Bacarisse a écrit :

Le 29/12/10 22:51, Keith Thompson a écrit :
Le 29/12/10 15:34, christian.bau a écrit :
[...]
What _precisely_ is the semantics of the "_overflow" function?

It returns 1 if the last operation overflowed, zero if not.
Concerned operations: signed +,-,*, and /.

Conversions?

Overflow should be detected in conversions.

This raises the question of what the 'last operation' is. You've shown

c = a + b;
if (_overflow()) ...

as the canonical example of this feature, but the "last operation" is
the conversion of the value of 'a + b' to the type of 'c'. This
operation may be the one I want to test for overflow. How does the
compiler know which overflow (the addition or the conversion) I am
interested in?

<snip>

In the example c is int, as b and c. That can't overflow.

Different is
short c;
int b,a;

c =a+b

can overflow (as you say) in a+b AND in the assignment. In that
case you should separate the operations for instance

if (!overflow(a+b)) {
if (_overflow(c=a+b))
// error
}
else // error

I was asking about something I though you were proposing -- an
_overflow() "intrinsic" that returned the overflow result of the "last
operation". This is a concept that you seemed to think was
self-evident[1] but which you now seem to have abandoned.

Have you dropped the idea of a function that, in effect, returns the
state of the overflow flag? If so, I'll start the whole thing again by
asking you to define the semantics of

_overflow(<expr>)

so I can see what it is you are proposing.

[1] In Message-ID: <[email protected]> you relied to Keith's
'What *exactly* does "the last operation" mean?' with a dismissive 'The
last operation. Can't you understand english?'.

 

[Keith Thompson]

The sentence you quoted just adds that the behavior is undefined.
(For signed operands if the result make some 1 bits disappear)

So what?

Are you seriously saying that left shifting some bit pattern
should provoke a trap and abort the program?

Not at all (though that's obviously one possible result of undefined
behavior). We're simply suggesting that overflow for the "<<" left
shift operator is essentially the same thing as overflow for the "*"
multiplication operator, and that they should be handled similarly.

The whole point of your _overflow() proposal is to allow programs
to handle situations whose behavior would otherwise be undefined.
Why do you oppose extending it to more operators?

 

[Keith Thompson]

Le 30/12/10 11:50, arnuld a écrit :

For instance

January 7th 2007

http://groups.google.com/group/comp...fr&lnk=gst&q=calloc+overflow#818c59e55205be94

Note how Heathfield and Thompson start arguing that "there is no
overflow" since the arguments are unsigned...

Right. We've argued that because it happens to be true. See C99
6.2.5p9:

A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting
unsigned integer type is reduced modulo the number that is one
greater than the largest value that can be represented by the
resulting type.

Informally, it's reasonable to refer to what happens when the result
of an unsigned operation won't fit in the target type as "overflow".
The point is that the standard very specifically *doesn't* refer
to it as "overflow".

If you don't like the way the standard uses, or doesn't use,
the term "overflow", that's fine. I'm not sure I like it myself.
All I'm doing is pointing out what the standard actually says.

[...]

 

[robertwessel2]

Maybe the overflow flag was dropped from the Dec Alpha *because* no high
language could make use of it.

(Does it still have a carry flag? That tends to be of more use than overflow
for multi-precision arithmetic which I think is mostly unsigned.)

There's no carry flag on Alpha, or on many RISCs. Carry can, of
course, be detected by a process similar to that of overflow detection
(the sequence is even included in the Alpha references, not that it
really needs a lot of documentation). For an add, basically do an
unsigned comparison of the result (sum) with either of the source
operands, if the sum is less, there was a carry.

This does result in considerable unpleasantness when propagating a
carry through multiple words, principally because there’s no add-with-
carry instruction, and if you have a carry in to a word, you have to
do a second addition (of 1), and a second carry detection for that
addition, and then combine that with the first carry detection to
generate the carry out.

Interestingly S/360 has a similar issue even though it has a condition
code (but not a traditional carry flag. An unsigned add (“Add
Logical” - distinct from a signed add), sets the two condition code
bits with a combination of the carry and zero status. The resulting
condition code can be 0-Zero/NoCarry, 1-NZ/NC, 2-Z/C, 3-NZ/C. The
conditional branch instruction can test for any of the condition codes
(for example, “BC 12,dest” would branch if CC 0 or 1 were set, or
branch-if-no-carry). In general this caused the same pain propagating
carries. Recently an add-logical-with-carry instruction has been
added, and it tests for a 2 or a 3 in the condition code and greatly
clean up that code.

 

[Keith Thompson]

Le 30/12/10 01:48, Keith Thompson a écrit :

You can't read Thompson. I said:

I haven't come around a processor that couldn't test for overflow.

Yes, you *also* said that, and it's perfectly true. That's not
what I was disputing.

I did not mention any flag. But you go on saying that, even if in
the text you QUOTED I said something different.

It's possible that I was confused about the context of the discussion;
this has been a very long thread.

In this thread, at Wed, 29 Dec 2010 09:32:37 +0100, in article
<[email protected]>, available at
<http://groups.google.com/group/comp.lang.c/msg/6f9d045e500a9288?dmode=source>,
you wrote:

There is no processor that hasn't an overflow flag.

*That* statement is the source of this entire argument. It is
incorrect, as has been demonstrated repeatedly; there *are*
processors that don't have overflow flags. The DEC Alpha
is an example, and not the only one.

Certainly it's possible to detect overflow on the DEC Alpha.
Nobody has said otherwise. It just uses a mechanism other than an
explicit overflow flag.

Furthermore, you've snipped the statement to which I was responding.
Here's some more of the context:

| jn>> C doesn't work if there is no floating point Mr Thompson.
|
| KT> It's not possible to have a conforming C implementation without
| KT> floating-point, but there have been plenty of implementations that
| KT> support floating-point in software. (I think there have also been
| KT> non-conforming implementations without FP; there's nothing wrong
| KT> with that.)
|
| jn>> That means that if a machine without overflow flag exists,
| jn>> it must be a very primitive one where C will not run in its
| jn>> standard form either.
|
| KT> I fail to see how this follows.
|
| KT> DEC Alpha. Again, do you understand the distinction between having
| KT> an overflow *flag* and being able to detect overflow? An explicit
| KT> flag is not the only possible mechanism. See my other followups.

You see, the DEC Alpha (clearly not a "very primitive" machine "where C
will not run in its standard form") does not have an overflow flag.

This is about *your* failure to distinguish between having an overflow
flag (as the DEC Alpha doesn't), and having a mechanism to detect
overflow (as the DEC Alpha certainly does).

 

[jacob navia]

Le 30/12/10 18:59, Ben Bacarisse a écrit :

Le 30/12/10 14:34, Ben Bacarisse a écrit :

In the example c is int, as b and c. That can't overflow.

Different is
short c;
int b,a;

c =a+b

can overflow (as you say) in a+b AND in the assignment. In that
case you should separate the operations for instance

if (!overflow(a+b)) {
if (_overflow(c=a+b))
// error
}
else // error

I was asking about something I though you were proposing -- an
_overflow() "intrinsic" that returned the overflow result of the "last
operation". This is a concept that you seemed to think was
self-evident[1] but which you now seem to have abandoned.

Not at all. That is why I said above that you have to separate the
addition from the assignment. Overflow detection is NOT sticky,
i.e. it only tells you the overflow of the LAST operation.

Again:
short c = (int)b+(int)a;

There are two operations here: "+" and "=".

To know which overflowed we do first the addition

if (!_overflow(b+a))

If that NOT overflows, THEN we test the assignment.

Have you dropped the idea of a function that, in effect, returns the
state of the overflow flag?

No. And if there is no flag it emulates the flag in software.

If so, I'll start the whole thing again by

asking you to define the semantics of

_overflow(<expr>)

Overflow returns the state of the last operation:
1 if the last operation overflowed, zero if it didn't.

[1] In Message-ID:<[email protected]> you relied to Keith's
'What *exactly* does "the last operation" mean?' with a dismissive 'The
last operation. Can't you understand english?'.

Semantics of _overflow()

(1) Operations in the virtual C machine as specified by the
standard can be scheduled in any order between sequence points
if that reordering doesn't affect the outcome as specified
by the programmer

(2) After scheduling operations, they are executed one after the other.
There is a LAST operation then. THAT operation sets the result of
_overflow.

The user should isolate operations to avoid ambiguities or
false negatives.

Sepantics of
#pragma overflowcheck on/off
Each of the 4 operations in +,-,*,/ are tested for overflow if
signed data is used. If any operation overflows a special
function is called with the line number and file name where
the faulty operation is detected.

The user can redefine the default, compiler provided function.
That default function looks like this:

_overflowHandler(unsigned linenum, char *fileName,...)
{
fprint(stderr,"Overflow at %s line %u\n",fileName,linenum);
abort();
}

I have been repeating that since the beginning but there is no
way that people here seem to understand

 

[Ben Bacarisse]

Le 30/12/10 16:19, Ben Bacarisse a écrit :

Since the general registers of the Cell SPU are 128 bit wide,
you can very easily detect overflow using 32 bit data
by testing one bit of the result. Note that the machine
can't handle more than 32 bit integer operations...

That's not how I understand this processor to work. The 128-bit result
is made up from 4 separate 32-bit adds, each with no carry and overflow
information. Nothing carries from one word addition to another.

Overflow detection is possible in the Cell SPU, you are
just wrong in this.

Of course it's possible. I said it is always possible. The question is
the cost. I don't think the cost is a single bit test on the Cell SPU
but I am no expert on these processors.

There is a "carry generate" instruction that would to the job, but that
is the point I was making: what's the cost of overflow detection? Your
proposal seems to reply on there being a zero-cost status bit that can
be queried. Without it, the compiler must be more sophisticated --
detecting the use of _overflow() and adding particular instructions just
prior to such calls.

Note that I have never spoken about an overflow flag.
It is Thompson that keeps saying that.

In message ID <[email protected]> you said:

| There is no processor that hasn't an overflow flag.

So what?

So you can't make statements like: "There is no processor that hasn't an
overflow flag" and not expect people to comment on that.

You just do not test ALL operations but only the ones where you
are interested in avoiding overflows. You use the form

if (_overflow(expression))

This is new form that, so far as I know, is unimplemented and not yet
defined. My comments may well have been different if this had been
the proposal you seemed to be putting forward.

Originally, you seemed to be suggesting a compiler intrinsic to access the
processor's overflow flag.

<snip>

 

[Seebs]

That's not how I understand this processor to work. The 128-bit result
is made up from 4 separate 32-bit adds, each with no carry and overflow
information. Nothing carries from one word addition to another.

This is exactly correct. The SPU *does not have* scalar operations. It
is a very specialized gizmo, and there's a great deal of interesting work
in compiler land for creating the illusion of scalar operations. Basically,
if you want to add 1 to a single item, you create a vector of 1s, you
use a shuffle intrinsic to turn it into a vector with a single 1, and you
add it to the vector containing the single item.

Of course it's possible. I said it is always possible. The question is
the cost. I don't think the cost is a single bit test on the Cell SPU
but I am no expert on these processors.

I'm not a proper *expert*, but I've written a fair bit about the compiler
technology used for them.

So you can't make statements like: "There is no processor that hasn't an
overflow flag" and not expect people to comment on that.

Exactly.

-s

 

[jacob navia]

Le 30/12/10 20:21, Ben Bacarisse a écrit :
[snip]



Yes, originally i have a proposal that is based in the
implementation that I have done till now.

But the solution proposed by Mr bau is better than what I have
implemented, if I have time I will change that.

I implemented this by checking the overflow flag, that is present in
many processors. OK, it can be emulated in those that do not have any.

My proposal has changed in the discussion because I am not the kind of
guy that says that "I am always right". It is a pity that you do
not answer to the detailed semantics that I wrote.

Anyway, I will reflect more on this and propose it in
comp.lang.c where it will be ignored and everything will stay as it
is now.

What I really do not understand is that you always put the sentence:

"what are the costs".

You are aware that any overflow invalidates all the results of your
software. I mean what is the cost of WRONG RESULTS?????

Isn't THAT cost a way BIGGER cost?

 

[Keith Thompson]

Le 30/12/10 18:59, Ben Bacarisse a écrit : [...]

I was asking about something I though you were proposing -- an
_overflow() "intrinsic" that returned the overflow result of the "last
operation". This is a concept that you seemed to think was
self-evident[1] but which you now seem to have abandoned.

Not at all. That is why I said above that you have to separate the
addition from the assignment. Overflow detection is NOT sticky,
i.e. it only tells you the overflow of the LAST operation.

Again:
short c = (int)b+(int)a;

There are two operations here: "+" and "=".

To know which overflowed we do first the addition

if (!_overflow(b+a))

If that NOT overflows, THEN we test the assignment.

Have you dropped the idea of a function that, in effect, returns the
state of the overflow flag?

No. And if there is no flag it emulates the flag in software.

"if there is no flag"? But you keep saying there's *always* a flag.

If so, I'll start the whole thing again by


Overflow returns the state of the last operation:
1 if the last operation overflowed, zero if it didn't.

There have been two different _overflow() functions proposed here. The
earlier one (implemented in lcc-win?) takes no arguments, and returns an
indication of whether the "last" operation overflowed. The later one
takes an expression as an argument.

If the form that takes an expression as an argument only tells you
whether the "last" operation overflowed, then what's the real difference
between the two forms?

My thought was that _overflow(<expr>) would return 1 if an overflow
occurred *anywhere* within the evaluation of <expr>, and 0 otherwise.
The advantage over the no-argument version is that the scope of the
overflow checking is clear. The compiler might have to generate
different (likely slower) code to evaluate the expression than it
normally would. And of course it could omit checks if it can prove
that an overflow can't occur.

[1] In Message-ID:<[email protected]> you relied to Keith's
'What *exactly* does "the last operation" mean?' with a dismissive 'The
last operation. Can't you understand english?'.

Semantics of _overflow()

(1) Operations in the virtual C machine as specified by the
standard can be scheduled in any order between sequence points
if that reordering doesn't affect the outcome as specified
by the programmer

(2) After scheduling operations, they are executed one after the other.
There is a LAST operation then. THAT operation sets the result of
_overflow.

The user should isolate operations to avoid ambiguities or
false negatives.

You're assuming that operations are performed in sequence. What if
they're performed in parallel? Or does _overflow() impose an additional
requirement to perform operations in sequence?

Sepantics of
#pragma overflowcheck on/off
Each of the 4 operations in +,-,*,/ are tested for overflow if
signed data is used. If any operation overflows a special
function is called with the line number and file name where
the faulty operation is detected.

You've said elsewhere in this thread that -- and ++ are also checked.
I presume this also applies to +=, -=, et al. If you're going
to define the semantics, I suggest that you should define the
semantics completely.

I believe that "%" can also produce an overflow. I don't think
it can produce a result outside the range of the type, but there's
been a ruling from the standard committee that if x / y overflows
(as it can with x==INT_MIN and y==-1), then the behavior of x % y is
undefined. This is a concession to the way most CPUs implement "%".

The user can redefine the default, compiler provided function.
That default function looks like this:

_overflowHandler(unsigned linenum, char *fileName,...)
{
fprint(stderr,"Overflow at %s line %u\n",fileName,linenum);
abort();
}

I have been repeating that since the beginning but there is no
way that people here seem to understand

What makes you think we don't understand?

 

[jacob navia]

Le 30/12/10 20:47, Seebs a écrit :
Then, it is very easy, just SPLIT your number in two
of those 4 slots and add them in parallel, then see if the
high parts overflow.

There was a discussion of precisely that in this thread.

There is NO processor that can't detect overflow.

I'm not a proper *expert*, but I've written a fair bit about the compiler
technology used for them.


Exactly.

-s

Exactly Seebs. Contrary to you (that thinks that you are always right)
I changed slighty my proposal from

expression
_overflow()

to _overflow(expression)

and left out any flags since the overflow detection can be done
with the use of other flags.

What is evident is that your interest is here to prove that
I am wrong and not to propose any solution to the detction
of overflow that apparently is for you a non problem.

Who cares?

If all my results are wrong because computation overflowed
it doesn't matter.

What do YOU propose Seebs? How would YOU solve this problem?

Or you think there is NO PROBLEM here ?

 

[BartC]

There have been two different _overflow() functions proposed here. The
earlier one (implemented in lcc-win?) takes no arguments, and returns an
indication of whether the "last" operation overflowed. The later one
takes an expression as an argument.

If the form that takes an expression as an argument only tells you
whether the "last" operation overflowed, then what's the real difference
between the two forms?

My thought was that _overflow(<expr>) would return 1 if an overflow
occurred *anywhere* within the evaluation of <expr>, and 0 otherwise.
The advantage over the no-argument version is that the scope of the
overflow checking is clear. The compiler might have to generate
different (likely slower) code to evaluate the expression than it
normally would. And of course it could omit checks if it can prove
that an overflow can't occur.

That's what confused me too. It seems that Jacob's implementation of:

_overflow(expr)

would just be equivalent to:

expr;
_overflow();

which could probably be achieved with a macro.

CB who originally proposed _overflow(expr) said it would be harder for the
compiler, so presumably he had in mind the same behaviour as you (and most
other people) would assume.

 

[Keith Thompson]

Le 30/12/10 20:21, Ben Bacarisse a écrit :
[snip]
Yes, originally i have a proposal that is based in the
implementation that I have done till now.

But the solution proposed by Mr bau is better than what I have
implemented, if I have time I will change that.

I independently proposed something very similar in the same thread.
I also made a similar proposal in September of 2009, in a thread
in which you participated (the difference is that my earlier
proposal captured the result of the expression as well as an
overflow indication).

I get the feeling that you refuse to acknowledge that an idea could
have come from me.

I implemented this by checking the overflow flag, that is present in
many processors. OK, it can be emulated in those that do not have any.

So you acknowledge that there are processors that don't have an overflow
flag? Will you also acknowledge that your repeated claim that there are
no such processors was mistaken?

My proposal has changed in the discussion because I am not the kind of
guy that says that "I am always right". It is a pity that you do
not answer to the detailed semantics that I wrote.

Anyway, I will reflect more on this and propose it in
comp.lang.c where it will be ignored and everything will stay as it
is now.

What I really do not understand is that you always put the sentence:

"what are the costs".

You are aware that any overflow invalidates all the results of your
software. I mean what is the cost of WRONG RESULTS?????

Isn't THAT cost a way BIGGER cost?

Yes.

Are you assuming that asking "what are the costs" implies that the
costs must be so great that it's not worth doing? Why would you
assume that? It's just a question, and one that deserves an answer.

In fact, I've worked in at least one language (Ada) that does require
overflow checking for arithmetic operations, though it has mechanisms
for removing the checks. The checks have a real cost associated
with them, though it's probably not as high as some might assume.
(For one thing, an optimizing compiler can eliminate many of the
checks.) You might look into it.