Integer Overflow

[tm]

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.

I think this is approach is too simple.
I use C as target language for my Seed7 to C compiler.
I would be happy if C had some overflow checking.
But I understand that there are also places where the
classic behaviour without overflow checking is needed.
I want to raise overflow exceptions (emulated with
setjmp, longjmp) in Seed7. C with overflow checking
would make this easier.

Checking the processor's overflow flag costs time and
there should be a cheaper way to handle overflows.
I guess that there are processors which can trigger an
interrupt (which could call a function or cause a
longjmp to happen) when the overflow flag is set.
This way the overflow check would cost nothing.

I propose intoducing new types with overflow checking.
The classic types int, long, ... would keep the
behaviour of ignoring overflow. New types like
checkd_int, checkd_long could be used for values which
need overflow checking.

When an overflow occurs a callback function could
be called. Based on this an exception mechanism can
be realized.


Greetings Thomas Mertes

--
Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.

 

[Ian Collins]

I think this is approach is too simple.
I use C as target language for my Seed7 to C compiler.
I would be happy if C had some overflow checking.
But I understand that there are also places where the
classic behaviour without overflow checking is needed.
I want to raise overflow exceptions (emulated with
setjmp, longjmp) in Seed7. C with overflow checking
would make this easier.

Checking the processor's overflow flag costs time and
there should be a cheaper way to handle overflows.

What could possibly be cheaper than reading a status register? If you
want a software interrupt, the cost of a context switch will swamp the
the cycle or two to read the status.

 

[jacob navia]

Le 30/12/10 22:26, tm a écrit :

I think this is approach is too simple.
I use C as target language for my Seed7 to C compiler.
I would be happy if C had some overflow checking.
But I understand that there are also places where the
classic behaviour without overflow checking is needed.
I want to raise overflow exceptions (emulated with
setjmp, longjmp) in Seed7. C with overflow checking
would make this easier.

If you write

_overflow(expression)

overflow will be checked only in the last operation of
"expression". Outside this construct things remain as they are
now.

If you think that the cost of testing for overflow
is too expenseive just produce wrong results very fast

Checking the processor's overflow flag costs time and
there should be a cheaper way to handle overflows.
I guess that there are processors which can trigger an
interrupt (which could call a function or cause a
longjmp to happen) when the overflow flag is set.
This way the overflow check would cost nothing.

Mmmm I know of no processor that does what you propose.
Can you give me an exaple?

I propose intoducing new types with overflow checking.
The classic types int, long, ... would keep the
behaviour of ignoring overflow. New types like
checkd_int, checkd_long could be used for values which
need overflow checking.

This is just too complicated, besides what does
checked_int*int ? Unchecked? checked?

 

[Seebs]

What could possibly be cheaper than reading a status register?

Quite a lot, I think there's at least one chip where the obvious way
to read the status register is a privileged operation which can trap to
the OS in some cases. Hmm. Seem to recall there was something like
this that happened if you swapped the 68000 in an early Amiga out for
a 68010.

-s

 

[BartC]

On 12/31/10 10:26 AM, tm wrote:

What could possibly be cheaper than reading a status register?

Not reading it? Such a check, even if it is a single conditional jump, would
be needed on every single checked operation, whether or not an overflow
occurred.

With an exception, there is zero cost unless an overflow actually occurs. If
you expect these to happen all the time, then perhaps this approach can be
slower. But it is the same cost as a divide-by-zero exception.

 

[Ian Collins]

Not reading it? Such a check, even if it is a single conditional jump,
would be needed on every single checked operation, whether or not an
overflow occurred.

Yes, but the user chooses to pay the cost.

With an exception, there is zero cost unless an overflow actually
occurs. If you expect these to happen all the time, then perhaps this
approach can be slower. But it is the same cost as a divide-by-zero
exception.

But something still has perform the check.

 

[Seebs]

"What could possibly be a cheaper way to detect overflow than reading a
status register?"

Ahh, that's an interesting question. I'm not sure, actually; there's a lot
of ideas that might come to mind, but it's not obvious that any of them
are necessarily cheaper.

That said, there is almost certainly at least one implementation out there
where calculating-in-advance whether or not something will overflow would
be orders of magnitude cheaper than checking the status register. So, you
do your check of the form
if (INT_MAX - b < a)
...
and the resulting instructions execute faster than the equivalent of:
c = a + b;
if (_overflow())
...

Who knows? CPUs surprise us. When I was a kid, I was told to avoid floating
point math because it was so much slower than integer.

-s

 

[Nick]

If you write

_overflow(expression)

overflow will be checked only in the last operation of
"expression". Outside this construct things remain as they are
now.

Why not check overflow in the whole of expression? A bit more work, but
only when quite explicitly asked for.

Otherwise, it's far from clear what

_overflow(a=b+c)

should test.

Should it:
a) always check b+c
b) check the assignment to a
c) check the assignment if a is smaller than (b+c) but otherwise check
b+c?

I don't like any of those, actually.

 

[jacob navia]

Le 30/12/10 23:39, Nick a écrit :

Why not check overflow in the whole of expression? A bit more work, but
only when quite explicitly asked for.

Otherwise, it's far from clear what

_overflow(a=b+c)

should test.

Should it:
a) always check b+c
Yes

b) check the assignment to a

I am not sure of that. There is an awful lot of code that assumes that
int b;
char a;

a = b;

People think that the lower 8 bits of the integer will be in a
after the assignment. Yes, some compiler emit warnings in
"checking" mode, but still there could be a lot of cases where
people just take the lower 8 (or 16 or 32) using an
assignment.

c) check the assignment if a is smaller than (b+c) but otherwise check
b+c?

If there can't be any overflow in the assignment there is no point in
checking it...

I don't like any of those, actually.

So. If you write a+b and your calculation overflows you
DO NOT LIKE to be warned about it and prefer to go on
with wrong results?

Obviously the wrong results will be calculated with
maximum speed... the only thing that counts here.

Or not?

 

[jacob navia]

Le 30/12/10 23:22, BartC a écrit :

Not reading it? Such a check, even if it is a single conditional jump,
would be needed on every single checked operation, whether or not an
overflow occurred.

Yes. For instance

addl %eax,%ecx
jo overflowhandler
; rest of the code here

The conditional jump on overflow will be predicted as not taken
if the label is at the end of the function, and that is always the
case in the generated code.

Then, the correctly predicted conditionaljump will NOT disturb the
pipeline. In machines with a very deep pipeline (something like 20
in old models of the x86 architecture) the cost will be

1 / length of the pipeline

i e less than 1/20 cycle.

Other overhead is code size of course, but it is really not significant
at all.

With an exception, there is zero cost unless an overflow actually
occurs.

Yes, but you suppose an exception when overflow occurs, something that
I have NEVER seen in any processor that I know of.

If you expect these to happen all the time, then perhaps this

approach can be slower. But it is the same cost as a divide-by-zero
exception.

Yes. You hav to talk with Intel, IBM, and others so that they
implement that feature in hardware.

It is just impossible

 

[jacob navia]

Le 30/12/10 23:18, Seebs a écrit :

Quite a lot, I think there's at least one chip where the obvious way
to read the status register is a privileged operation which can trap to
the OS in some cases. Hmm. Seem to recall there was something like
this that happened if you swapped the 68000 in an early Amiga out for
a 68010.

Wrong seebs.

Completely wrong.

There are TWO bytes for flags in the 68000. A supervisor byte
and a user byte. You can access the user byte (where the
overflow flag is) without any privileges OBVIOUSLY.

Convinced now?

 

[jacob navia]

Le 30/12/10 23:54, christian.bau a écrit :

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.

Jacob is quite fixated on "this is what is easy to implement, so this
is what I want to implement. My spec would be:

The function _overflow () is declared as int _overflow (int x). It
returns a value of 0 or 1.
For each of the following operations, the semantics is modified if
that operation is performed as part of the evaluation of the argument
of the _overflow function, except for any operations inside function
calls, and except for any implicit conversion of the argument to type
int:

(followed by a long list of operations, for example: When the result
of adding two signed integers cannot be represented in the result
type, there will be no undefined behaviour, but the result of that
operation is an implementation-defined value, and the result returned
by the _overflow function will be 1).

If there is no operation that forces the result returned to be 1, then
the result returned is 0.

Example:

if (_overflow (x [i + 2] = f (z + 3))) printf ("overflow!\n");

The string "overflow!\n" will be printed if the evaluation of i+2, of z
+3, or the conversion of the result of f () to the element type of the
array x produced an overflow, but not if there is an overflow in the
call to f (), or if the array element x [i+2] does not exist.

Of course in the last two cases the behaviour is undefined, so
anything can happen, including _overflow () returning 1.

That would be much harder to implement than only the last
operation since you wuld have to implement a flag
in software...

For each operation you would OR the overflow flag (if there is any)
to a software flag and then return that result. That is much more
costly, and I do not see what gains you have since you then do
not know which quantity overflowed.

That is much difficult to handle in an exception handler.

Besides, I am scared about overflows in casts since a lot of code out
there assumes that

char c = (int) a;

takes the lower 8 bits of the integer without any trap...
At the beginning of the discussion I thought narrowing casts should
be included but thinking it over it could be really a problem.

The objective should be to give something practical, that does NOT
disturb existing code.

jacob

 

[tm]

Not reading it? Such a check, even if it is a single conditional jump, would
be needed on every single checked operation, whether or not an overflow
occurred.

With an exception, there is zero cost unless an overflow actually occurs. If
you expect these to happen all the time, then perhaps this approach can be
slower. But it is the same cost as a divide-by-zero exception.

Yes, this was what I had in mind.
I want zero cost when no overflow occurs.
When the hardware recognizes the overflow it can cause
an interupt instead of setting the overflow flag.
I guess that many processors have such a possibility.
Maybe the overflow trap must be switched on when an
overflow should cause an interrupt and switched of when
the classic overflow ignoring behaviour is desired.
This switching could still be cheaper than checking
an overflow flag all the time.


Greetings Thomas Mertes

--
Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.

 

[tm]

Yes, but the user chooses to pay the cost.


But something still has perform the check.

The hardware that sets the overflow flag already performs
this check. It just needs to cause an interupt instead
or additionally to setting the flag. I don't know
which processors can do this, but I don't think that
such a feature is expensive to implement for processor
designers. Therefore I guess that several processors
already have such a possibility.


Greetings Thomas Mertes

--
Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.

 

[BartC]

Le 30/12/10 23:39, Nick a écrit :

If there can't be any overflow in the assignment there is no point in
checking it...


So. If you write a+b and your calculation overflows you
DO NOT LIKE to be warned about it and prefer to go on
with wrong results?

I put together these few lines of assembler to calculate
(2000000000+2000000000)+1. It also calculates an overflow status in
bc_overflow (which combines all overflow flags), and jn_overflow which does
it your way:

mov eax,2000000000
mov ebx,2000000000
mov ecx,1

add eax,ebx

seto dl
mov [bc_overflow],dl

add eax,ecx
mov [result],eax
seto dl
or [bc_overflow],dl
mov [jn_overflow],dl

The results when printed are:

result= -294967295
bc_overflow= 1
jn_overflow= 0

The result is obviously wrong (it should be 4000000001 but is outside the
range of signed 32-bits); the bc_overflow flag is correct, but the
jn_overflow is wrong. As I understand it, this is what your _overflow(a+b+c)
would give on the same values.

If you are seriously planning to ignore all but the very last overflow
status on these multiple expressions, then this will give the same wrong
results you warn about above.

 

[Ian Collins]

The hardware that sets the overflow flag already performs
this check. It just needs to cause an interupt instead
or additionally to setting the flag. I don't know
which processors can do this, but I don't think that
such a feature is expensive to implement for processor
designers. Therefore I guess that several processors
already have such a possibility.

So you would think, floating point errors already do.

 

[tm]

Le 30/12/10 23:22, BartC a crit :



Yes. For instance

addl %eax,%ecx
jo overflowhandler
; rest of the code here

No, this is NOT what I have in my mind.
I want that overflow recognition costs nothing (not a
single instruction) as long as no overflow occours.
The hardware already recognizes the overflow situation,
otherwise the overflow flag could not be set. So the
hardware should cause a trap (or something equivalent)
when an overflow occurs instead or additionally to
setting the overflow flag.

Yes. You hav to talk with Intel, IBM, and others so that they
implement that feature in hardware.

Are you sure that such a feature is not available?
There are so many things that were added to the
processors and such a feature is missing?

Even when it is missing in the current hardware it makes
sense to talk about it, because it is the "Right way to
do" overflow detection. Every other solution will have
a runtime penalty for the normal case (no overflow occurs).

It would be really strange if the hardware recognizes
overflow without extra cost and the only way to use it
is checking a flag all the time. There are several
programming languages which would benefit from such
an zero cost overflow detection. E.g.: Pascal, Ada,
Eiffel, Seed7 and probably many more.

Unlimited precision arithmetic could also benefit from
zero cost overflow detection.

It is just impossible

It is NOT impossible. Even such things can change.


Greetings Thomas Mertes

--
Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.

 

[BartC]

Are you sure that such a feature is not available?
There are so many things that were added to the
processors and such a feature is missing?

Even when it is missing in the current hardware it makes
sense to talk about it, because it is the "Right way to
do" overflow detection. Every other solution will have
a runtime penalty for the normal case (no overflow occurs).

It would be really strange if the hardware recognizes
overflow without extra cost and the only way to use it
is checking a flag all the time. There are several
programming languages which would benefit from such
an zero cost overflow detection. E.g.: Pascal, Ada,
Eiffel, Seed7 and probably many more.

The way it's done now (on x86 anyway) makes sense. An overflow from unsigned
arithmetic is not that much of a calamity. And software that is worried
about it can just check the flag.

If an overflow interrupt was possible, then it would need to be maskable.

After all, would you want an interrupt when the carry flag was set? Almost
certainly not. But a carry flag would signal overflow of unsigned arithmetic
(even if C chooses to pretend that such an overflow is impossible).

Unlimited precision arithmetic could also benefit from
zero cost overflow detection.

But not via an interrupt routine, surely, since it would slow it down by
several hundred times. An interrupt for overflow only makes sense for
languages paranoid about overflows on integer arithmetic, which can then
choose to abort, or activate an exception handler in the language.

 

[Charles]

Le 30/12/10 22:26, tm a écrit :

This is just too complicated, besides what does
checked_int*int ? Unchecked? checked?

Ref: C++ SafeInt. It's already been done, questions already answered.

http://msdn.microsoft.com/en-us/library/dd570023.aspx

 

[robertwessel2]

Le 30/12/10 23:18, Seebs a crit :



Wrong seebs.

Completely wrong.

There are TWO bytes for flags in the 68000. A supervisor byte
and a user byte. You can access the user byte (where the
overflow flag is) without any privileges OBVIOUSLY.

Convinced now?

No, Seebs is right. On the 68000 there was a single unprivileged
instruction (MOVE SR,_ea_ ...) to read the entire 16 bit status
register, including both the user and supervisor parts. There was no
instruction to read only the unprivileged part. User access to the
suppervisor flag presents certain problems, particularly with
virtualization. On the 68010 and later, that was changed so that the
*existing* 68000 instruction became privileged, and a *new*
instruction (MOVE CCR,_ea_ ...)was added that read only the
unprivileged part (still returned a 16 bit result, just with the high
byte cleared).

Systems upgrading from the 68000 to the 68010 needed either changes in
user code to use the new instruction, or OS support to trap and
emulate the now privileged instruction.