llvm dev - Mar 2008 - [LLVMdev] Checked arithmetic

On Wed, 2008-03-26 at 15:07 +0100, Duncan Sands wrote:
> 4. Do arithmetic in a type with one more bit.  For example, suppose you
> want to know if an i32 add "x+y" will overflow.  Extend x and y
to 33
> bit integers, and do an i33 add.  Inspect the upper bit to see if it
> overflowed.  Truncate to 32 bits to get the result.  Probably codegen
> can be taught to implement this as a 32 bit add + inspection of the CC.
As a quick fix, that isn't a bad solution for bignum arithmetic, but it
doesn't deal with the upper bits from multiply, and it doesn't deal with
floating point condition codes at all.


shap

Hi Shap,
> > 4. Do arithmetic in a type with one more bit.  For example, suppose
you
> > want to know if an i32 add "x+y" will overflow.  Extend x
and y to 33
> > bit integers, and do an i33 add.  Inspect the upper bit to see if it
> > overflowed.  Truncate to 32 bits to get the result.  Probably codegen
> > can be taught to implement this as a 32 bit add + inspection of the
CC.
> 
> As a quick fix, that isn't a bad solution for bignum arithmetic, but it
> doesn't deal with the upper bits from multiply, and it doesn't deal
with
> floating point condition codes at all.
can you really use condition codes for multiply and floating point?  You
can handle integer multiply by doing it in an integer twice as wide as the
one you are interested in, so an i64 on a 32 bit machine.  Is there hardware
that supports checking for multiply overflow in a more efficient fashion,
and if so how does it work/get used?

Thanks,

Duncan.

On Wed, 2008-03-26 at 15:47 +0100, Duncan Sands wrote:
> can you really use condition codes for multiply and floating point?
For scalar multiply, not really. What you *can* do is use the native
multiply instruction that does (32x32)->(lower,upper), and then decide
based on the upper 32 bits of the result whether you had a
multiply-carry. Similarly for i-divide 64->(quotient,remainder).

For floating point I am thinking about something else entirely. There is
a NaN propagation mode specified in IEEE that lets you run a chain of FP
ops and then check for NaN at the end, with the guarantee that the
intervening ops will be NaN-preserving. You can't store the results back
to memory without a check, but the technique avoids a check in the fp
pipeline that can be serializing on intermediate expression results.

The catch is that you can't use that technique unless you can ensure
that the FPcc isn't clobbered by something else in the middle, which
seems to suggest that you want to track the FP condition code as a
register.

And then there are machines with multiple condition codes, and machines
the simply put the condition codes into a scalar register. These seem to
suggest that first-rate support for condition codes wants them to be
handled as a register class.
>   You
> can handle integer multiply by doing it in an integer twice as wide as the
> one you are interested in, so an i64 on a 32 bit machine.  Is there
hardware
> that supports checking for multiply overflow in a more efficient fashion,
> and if so how does it work/get used?
On some machines there is. For example, both SPARC and MIPS have
instructions that do a 32x32 multiply producing a 64 bit result. The
upper bits of the result go into a side register, or in some cases the
output of the multiply unit goes into a distinct (lower, upper) register
pair that is not part of the normal register set.

This is an idea that comes and goes. The side register has to be renamed
specially, and can become a rename bottleneck in the issue unit, so it
may be an idea whose time came and went. On machines that do 32x32->32,
I do not know what outcome happens on the condition codes, but we can
surely look that up.


shap