Catching integer overflow

[thomas.mertes]

Is it possible to use some C or compiler extension to catch
integer overflow?

The situation is as follows:
I use C as target language for compiled Seed7 programs.
For integer computions the C type 'long' is used.
That way native C speed can be reached.

Now I want to experiment with raising a Seed7 exception
(which is emulated with setjmp(), longjmp() in C) for integer
overflow. Since the C int's and long's have undefined
behaviour on overflow, I hope to use some C or compiler
extensions to implement the overflow exceptions.

I know that a check before every integer computation
could be used to recognice an overflow, but it is not my
intention to slow down normal computations.

Normal C programs which do integer computations should
have no overhead. When an overflow happens a signal or
something else should happen that I can use to emulate
an exception.

Are there ideas to solve this problem?

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]

Is it possible to use some C or compiler extension to catch
integer overflow?

I know that a check before every integer computation
could be used to recognice an overflow, but it is not my
intention to slow down normal computations.

I don't think an integer overflow would typically cause a hardware
exception.

So this is down to using extra instructions, usally /after/ the operation.

This need not be a high overhead, if you were targetting x86 instead of C,
you might use 'jo label' after the add.

But C doesn't normally have this sort of thing built-in, unless it's in the
form of special compiler extensions and switches. In your case, you cannot
rely on this because your application then becomes compiler-specific (you
might as well rely on inline Asm).

There might be a few workarounds in C, but I guess they all have overheads
of some kind.

What is the purpose of this overflow check? To switch over to large integer
form? Otherwise overflow checking could be optional for the user.

 

[thomas.mertes]

I don't think an integer overflow would typically cause a hardware
exception.

Maybe it is possible to switch the hardware to a some
mode where an interrupt is raised with an integer overflow.
In that case the code for the mode switch and the
interrupt handler would be compiler/os dependend, but
the rest of the program would be plain C.

So this is down to using extra instructions, usally /after/ the operation.

This need not be a high overhead, if you were targetting x86 instead of C,
you might use 'jo label' after the add.

Is 'jo' an actual x86 instruction meaning "Jump when overflow
flag is set"?

But C doesn't normally have this sort of thing built-in, unless it's in the
form of special compiler extensions and switches. In your case, you cannot
rely on this because your application then becomes compiler-specific (you
might as well rely on inline Asm).

I know that this will probably be compiler-specific.
This is just a thing I want to explore.
What about C99 or the next C standard?

There might be a few workarounds in C, but I guess they all have overheads
of some kind.

What is the purpose of this overflow check? To switch over to large integer
form? Otherwise overflow checking could be optional for the user.

It is not my intention to switch to larger integers
on the fly. I just want to avoid undefined behaviour.

The C89 Ansi C standard states:
The handling of overflow, divide check and other exceptions
in expression evaluation is not defined by the language.
Most existing implementations of C ignore overflow in
evaluation of signed integral expressions and assignments,
but this behavior is not guaranteed.

I think that exceptions for integer overflows could
also be helpful to find bugs.

Like other range checks (for array or string access) it
could be made optional. A compiler switch or pragma could
be used to switch it on or off.

Currently I am still hoping for a zero overhead solution.

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.

 

[jacob navia]

Is it possible to use some C or compiler extension to catch
integer overflow?

lcc-win provides the extension:

bool _overflow();

that returns the value of the overflow flag.

Obviously you should separate your operations if
you are insterested in knowing which operation overflowed.

For instance:

int a,b,c;

c = (a+b)*c;

If the overflow flag is set, it means that the multiplication
overflowed, but it is impossible to know if the addition
overflowed.

lcc-win also offers the

lcc -checkoverflow

flag when invoked. This flag will test automatically ALL operations for
overflow and abort the program if an overflow is found.

The situation is as follows:
I use C as target language for compiled Seed7 programs.
For integer computions the C type 'long' is used.
That way native C speed can be reached.

lcc-win is specially adapted for use as a back end compiler. A JIT
compiler is also available (you just pass a C code character
string instead of a file)

 

[Bartc]

Maybe it is possible to switch the hardware to a some
mode where an interrupt is raised with an integer overflow.

I don't know. Integer overflow doesn't seem serious enough to warrant
hardware support.

Is 'jo' an actual x86 instruction meaning "Jump when overflow
flag is set"?

Yes, in Nasm syntax anyway. For unsigned overflow a different condition
(jc?) is used. Except of course in C unsigned overflow is an impossibility.

 

[Ben Bacarisse]

Is it possible to use some C or compiler extension to catch
integer overflow?

<off-topic>
gcc has -ftrapv -- probably only when the target can do it
efficiently.

Presumably you don't use gcc or you'd have found it in the man page ;-)
</off-topic>

 

[Peter Nilsson]

Is it possible to use some C or compiler extension to catch
integer overflow?

Have you thought about being portably proactive rather than
non-portably reactive with regards to overflow?

 

[Keith Thompson]

I don't know. Integer overflow doesn't seem serious enough to warrant
hardware support.

[...]

You'd rather have wrong answers quickly?

 

[Bartc]

On x86, you can't use instructions like branch-on-overflow or
trap-on-overflow because they are instructions and cause overhead.
You demanded no overhead.

*IF* you could get the compiler to place a trap-on-overflow
instruction after each signed integer calculation (but not on
the unsigned integer calculations),

This is for implementing a different language, which could well have the
concept of unsigned overflow:

If my unsigned int can only store 0..9, I may want to know that 5+7 only
gave me 2 instead of the correct 12.

 

[Bartc]

I don't know. Integer overflow doesn't seem serious enough to warrant
hardware support.

[...]

You'd rather have wrong answers quickly?

Yes. Integer operations need to be fast. Overflow checking should be
optional, perhaps during development only.

But if there is a hardware trap (like divide by zero) that didn't slow
things down, then that's fine, provided the overflow was a genuine error. I
can see that being difficult to implement however, unless you also have
separate arithmetic instructions for signed and unsigned values.

 

[santosh]

I don't know. Integer overflow doesn't seem serious enough to
warrant hardware support.

[...]

You'd rather have wrong answers quickly?

Yes. Integer operations need to be fast. Overflow checking should be
optional, perhaps during development only.

But if there is a hardware trap (like divide by zero) that didn't slow
things down,

Traps and interrupts actually incur *much* more delay than doing the
detection manually, since under modern systems a trap involves a
context switch and then a signal needs to be delivered to your process,
all of which take more time than a few checks before doing the
operation.

The problem of course is similar to checking return values versus
exceptions. Traps only fire when an overflow actually occurs while
manual checks will slowdown all calculations.

I think that using a lot of #ifdef trickery it's possible to use the
best methods available for each compiler or fall back plain C code when
nothing is available. But it's a lot of work.

<snip>

 

[Bartc]

[...]
I don't know. Integer overflow doesn't seem serious enough to
warrant hardware support.
[...]

You'd rather have wrong answers quickly?

Yes. Integer operations need to be fast. Overflow checking should be
optional, perhaps during development only.

But if there is a hardware trap (like divide by zero) that didn't slow
things down,

Traps and interrupts actually incur *much* more delay than doing the
detection manually, since under modern systems a trap involves a
context switch and then a signal needs to be delivered to your process,
all of which take more time than a few checks before doing the
operation.

I'm assuming the overflow is a rare event. If the program relies on frequent
overflow traps for it's operation then it might as well use extra C code or
get the compiler to insert appropriate instructions. This is better because
you don't get traps occuring in library code or anywhere else just because
/your/ program requires them.

 

[Keith Thompson]

I don't know. Integer overflow doesn't seem serious enough to warrant
hardware support.

[...]

You'd rather have wrong answers quickly?

Yes. Integer operations need to be fast. Overflow checking should be
optional, perhaps during development only.

[...]

Well, luckily for you, C does require overflow checking for operations
on signed integers, and mandates well-defined behavior when the checks
fail, and zero run-time overhead when they don't.

But you might want to verify that information. I though it was more
important to post a followup quickly than to get it right.

 

[thomas.mertes]

[...]
I don't know. Integer overflow doesn't seem serious enough to warrant
hardware support.
[...]
You'd rather have wrong answers quickly?

Yes. Integer operations need to be fast. Overflow checking should be
optional, perhaps during development only.

[...]

Well, luckily for you, C does require overflow checking for operations
on signed integers, and mandates well-defined behavior when the checks
fail, and zero run-time overhead when they don't.

About which C you talking about?
The C89 Ansi C standard states:
The handling of overflow, divide check and other exceptions
in expression evaluation is not defined by the language.
Most existing implementations of C ignore overflow in
evaluation of signed integral expressions and assignments,
but this behavior is not guaranteed.

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.

 

[thomas.mertes]

Have you thought about being portably proactive rather than
non-portably reactive with regards to overflow?

What do you mean with proactive?
Doing checks before every integer operation?

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.

 

[thomas.mertes]

lcc-win provides the extension:

bool _overflow();

that returns the value of the overflow flag.

Is checking the overflow flag the only possibility?
How is the overflow flag reset?
Would it be possible to minimize the checks for the flag?
Since I want to raise an exception, all integer variables
below the (stack) level of the exception handler could
theoretically contain wrong (overflowed) values without
having an infuence on the rest of the program.

lcc-win also offers the

lcc -checkoverflow

flag when invoked. This flag will test automatically ALL operations for
overflow and abort the program if an overflow is found.

Todays hardware does so many things.
Is it really impossible to tell the (x86) processor
to interupt when the overflow flag is set?

lcc-win is specially adapted for use as a back end compiler. A JIT
compiler is also available (you just pass a C code character
string instead of a file)

Ok.

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.

 

[Bart]

[...]
I don't know. Integer overflow doesn't seem serious enough to warrant
hardware support.
[...]
You'd rather have wrong answers quickly?

...
Well, luckily for you, C does require overflow checking for operations
on signed integers...

But you might want to verify that information.  I though it was more
important to post a followup quickly than to get it right.

We may be talking at cross purposes. It seems you are saying I posted
incorrect information? OK let's see:

I don't know. [about exceptions on integer overflow]

Well I can verify that! Whether machines in general have an interrupt
setting to automatically trap signed integer overflow, without using
an explicit instruction per arithmetic operation, perhaps someone can
enlighten us.

Although as I've indicated in another post, such a global setting
would cause problems, since an Add-op for example is typically neither
signed or unsigned, so it would not know if this was a signed add or
not.

Integer overflow doesn't seem serious enough to warrant

hardware support. [Ie. automatically trap on overflow, not merely set flags]

That's my opinion. And again I can verify that.

 

[thomas.mertes]

gcc has -ftrapv -- probably only when the target can do it
efficiently.

Presumably you don't use gcc or you'd have found it in the man page ;-)

As far as I can see the -ftrapv option seems to use
checks for the (x86) overflow flag and terminates the
program on overflow.

I did not find that a signal is raised or a callback
function is activated when an integer overflow occurs.

Can you confirm this?

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.

 

[jacob navia]

Is checking the overflow flag the only possibility?

If you want to check for a specific operation yes.
If not, the compiler can introduce the check in ALL
arithmetic operations automatically. Then, you
do not check anything.

How is the overflow flag reset?

Each arithmetic operation resets the overflow flag to a new
value.

Would it be possible to minimize the checks for the flag?

If you check only the operations you are interested in,
fewer checks are done.

Since I want to raise an exception, all integer variables
below the (stack) level of the exception handler could
theoretically contain wrong (overflowed) values without
having an infuence on the rest of the program.

Only the last variable would contain an overflow, not
ALL of them. For instance:

int a,b,c;

c = a*b;

if (_overflow()) {
// The value of 'c' is wrong.
// a AND b are correct!
}

Todays hardware does so many things.
Is it really impossible to tell the (x86) processor
to interupt when the overflow flag is set?

Yes. There is an interrupt on overflow, opcode 0xCE. But you
will have to write an interrupt handler, and that is quite
difficult. You will also have to convince the operating
system to load your interrupt handler, etc.

Note that this instruction only works in 32 bit mode. In 64 bit mode
this instruction will provoke an illegal instrution exception...

Probably there is a mode for 64 bit overflow testing but I would
have to investigate the matter.

 

[Bart]

Is checking the overflow flag the only possibility?
How is the overflow flag reset?
Would it be possible to minimize the checks for the flag?

This is all stuff for the compiler writer to worry about.

Todays hardware does so many things.
Is it really impossible to tell the (x86) processor
to interupt when the overflow flag is set?

Someone mentioned an INTO instruction but I think you use that
following your operation.

The problem with the x86 specifically, is that instructions such as
ADD work with both signed and unsigned values. An operation which sets
the (signed) overflow flag, may be fine for an unsigned operation. But
the cpu doesn't know which was intended.

You might enable/disable the setting around each operation, but that
will be quite an overhead.