Detecting multipication overflow

[wij]

Hi:
Is there better way of detecting multiplication overflow for type
long than by using double precision of lldiv to verify the result?
Thanks in advance.

I.J.Wang

 

[pete]

Hi:
Is there better way of detecting multiplication overflow for type
long than by using double precision of lldiv to verify the result?
Thanks in advance.

I.J.Wang

Divide LONG_MAX by one of the multiplicands
and see if the result is less than the other multiplicand.

 

[jacob navia]

(e-mail address removed) a écrit :

Hi:
Is there better way of detecting multiplication overflow for type
long than by using double precision of lldiv to verify the result?
Thanks in advance.

I.J.Wang

The lcc-win32 compiler allows detection of overflow
automatically in 2 ways:
1) By a compile time switch. This will test each operation
for overflow in the whole program
2) Using the _overflow() intrinsic to test for overflow after
a specific operation, for instance:
int a,n;

n = n*59876;
if (_overflow())
printf("It did not work\n");

In another compiler systems the best thing is to use assembly:

.text
.globl _overflow
_overflow:
movl $0,%eax
seto %al
ret

This function will return 1 if the overflow flag is set,
zero otherwise. Note that a move is done to zero eax, NOT
xor eax,eax because that would destroy the flags.

If you use another CPU than the x86, you will have to read the
assembly language manual for your machine. If using a SPARC
for instance you could use BVS (Branch on oVerflow Set) to
alternatively set a register to either 0 or 1

jacob
http://www.cs.virginia.edu/~lcc-win32

 

[Dik T. Winter]

> If you use another CPU than the x86, you will have to read the
> assembly language manual for your machine. If using a SPARC
> for instance you could use BVS (Branch on oVerflow Set) to
> alternatively set a register to either 0 or 1

You apparently have not read the assembly language manual for the sparc
thoroughly.
1. BVS does (as the name implies) a branch when the overflow bit is set.
I think you mean SVS (or something like that) which sets a register
to 0 or 1 depending on the overflow bit.
2. If the compiler uses the instructions that do not set the overflow
bit, this will not help at all. "add" will not set it on addition,
"addcc" will set it on addition. I think most compilers do not use
"addcc" as it might trap.

 

[Chris Torek]

This is actually a rather nice method. Of course, it turns out
that people want finer granularity of testing for integer overflow.
You might consider using C99's _Pragma() construct to turn this
automatic overflow-testing on and off. (_Pragma is better than
#pragma as "_Pragma"s can be hidden behind preprocessor macros.)

2) Using the _overflow() intrinsic to test for overflow after
a specific operation, for instance:
int a,n; [presumably here "n" is set to some value; "a" is irrelevant]
n = n*59876;
if (_overflow())
printf("It did not work\n");
In another compiler systems the best thing is to use assembly:
.text
.globl _overflow
_overflow:
movl $0,%eax
seto %al
ret
This function will return 1 if the overflow flag is set,
zero otherwise. Note that a move is done to zero eax, NOT
xor eax,eax because that would destroy the flags.

This method will not work in general, for reasons I will mention in
a moment.

You apparently have not read the assembly language manual for the sparc
thoroughly.
1. BVS does (as the name implies) a branch when the overflow bit is set.
I think you mean SVS (or something like that) which sets a register
to 0 or 1 depending on the overflow bit.

The SPARC does not have an "svs", though it does have a "tvs" (trap
if overflow is set). One could use bvs, if it were not for a rather
different problem that you also mention:

2. If the compiler uses the instructions that do not set the overflow
bit, this will not help at all. "add" will not set it on addition,
"addcc" will set it on addition. I think most compilers do not use
"addcc" as it might trap.

Actually addcc never traps; it merely sets the condition codes
(both %icc and %xcc on V9; V8 and earlier have only %icc) based on
the result of the add. You may be thinking of "taddcc", although
that instruction is intended for Lisp systems.

It is, however, true that most compilers generate a simple "add"
or -- for multiply -- one of three instructions or instruction
sequences, none of which set the "v" flag in %icc and/or %xcc.
So this method will not work on SPARC systems.

Unfortunately, the overflow() function will also not work on x86
systems -- or rather, worse, it will *sometimes* work, but sometimes
fail, in a manner anywhere from "difficult" to "impossible" to
predict. The reason is that there is no requirement that the
compiler call overflow() immediately after the "obvious" instruction
(in this case imull). The code:

n = n * 59876;
if (_overflow())
...
use(n);

might -- as long as n is a local variable, thus "obviously" not
accessible from a function like _overflow() -- quite legitimately
compile to:

call _overflow
testl %eax,%eax
je .Laround
...
..Laround:
# multiply n by 59876 *now*, *after* calling overflow()
imull ... # or equivalent (gcc uses a sequence of "leal"s)
pushl [n] #
call use

As it happens, gcc (2.95.3, and not using -march=k6 or -march=i686)
does not move the multiply itself in a small sample routine I
created, but it does use leal instead of imull, and leal does not
set the "v" bit:

# at this point, "n" is in %ebx
leal (%ebx,%ebx,2),%eax
leal (%ebx,%eax,4),%eax
leal (%eax,%eax,8),%eax
sall $4,%eax
subl %ebx,%eax
leal (%ebx,%eax,8),%eax
leal 0(,%eax,4),%ebx
call _overflow
...

The "v" bit value will be left over from the "subl" instruction,
and will have little to do with whether the multiply really
overflowed. (But note that with 686 or k6 architecture or CPU
selected, the cost of the imull is reduced, so the instruction
selector chooses it instead of the leal-sequence.)

 

[jacob navia]

Well, if your compiler is moving instructions around
that will never work, of course.

In that case there is no other choice than to disable
those optimizations, or find a work-around specific
to the compiler, for instance maybe declaring the result
volatile, or similar stuff.

Since lcc-win32 never does that kind of optimizations
that does not apply to its environment.

The best option remains to test *ALL* operations
for overflow. In modern PCs that adds at most
0.0001% run time when done correctly. The correct
code to generate would be
add ...
jo ; jump if overflow. Predicted as NOT
; taken if it is a forward jump.

that would cost 1 extra cycle, something that would never add
much to your program's run time. Even the solution used in
lcc-win32, adds less than 1% to the run time speed.

jacob

 

[Chuck F.]

>
Well, if your compiler is moving instructions around
that will never work, of course.

In that case there is no other choice than to disable
those optimizations, or find a work-around specific
to the compiler, for instance maybe declaring the result
volatile, or similar stuff.

Since lcc-win32 never does that kind of optimizations
that does not apply to its environment.

The best option remains to test *ALL* operations
for overflow. In modern PCs that adds at most
0.0001% run time when done correctly. The correct
code to generate would be
add ...
jo ; jump if overflow. Predicted as NOT
; taken if it is a forward jump.

that would cost 1 extra cycle, something that would never add
much to your program's run time. Even the solution used in
lcc-win32, adds less than 1% to the run time speed.

This is highly OT, since it refers only to X86 code generation.
However the x86 has the into instruction, which executes a software
interrupt when the overflow bit is set. This is not executed when
the overflow bit is clear. So all interrupts can be handled by a
single service routine, and only that routine (or the connector to
it) need be altered to ignore all overflows.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>

 

[jacob navia]

This is highly OT, since it refers only to X86 code generation. However
the x86 has the into instruction, which executes a software interrupt
when the overflow bit is set. This is not executed when the overflow
bit is clear. So all interrupts can be handled by a single service
routine, and only that routine (or the connector to it) need be altered
to ignore all overflows.

Mmmm That's VERY interesting!

Thanks Chuck!