Checked arithmetic

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
31 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Checked arithmetic

Jonathan S. Shapiro-2
In looking at the LLVM reference manual, it is conspicuous that (a) the
IR does not define condition codes, and (b) the IR does not define
opcodes that return condition results in addition to their computational
results.

Given the IR as it stands, how does one go about *efficiently*
implementing a language that requires checked arithmetic? I do
understand that it can be done using intrinsics, but that implementation
is (to put it mildly) suboptimal.

For integer ops, I really want to be able to get at the carry/overflow
bit. For floating point ops, I really want to be able to get out the
floating point NaN state in order to exploit the NaN propagation
features provided by some hardware.

I'm sure this has been considered, but no means for dealing with this
sort of thing is jumping out at me from looking at the IR spec. What am
I missing?

Note: I can see at least two ways to deal with this by extending the IR,
but I would like to understand the current intentions first.


shap

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Checked arithmetic

Chris Lattner

On Mar 25, 2008, at 8:25 PM, Jonathan S. Shapiro wrote:

> In looking at the LLVM reference manual, it is conspicuous that (a)  
> the
> IR does not define condition codes, and (b) the IR does not define
> opcodes that return condition results in addition to their  
> computational
> results.

We currently don't have this because noone has implemented it yet.  It  
would be great to have this.

> Given the IR as it stands, how does one go about *efficiently*
> implementing a language that requires checked arithmetic? I do
> understand that it can be done using intrinsics, but that  
> implementation
> is (to put it mildly) suboptimal.

Why?

-Chris
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Checked arithmetic

Jonathan S. Shapiro-2
On Tue, 2008-03-25 at 21:18 -0700, Chris Lattner wrote:

> > Given the IR as it stands, how does one go about *efficiently*
> > implementing a language that requires checked arithmetic? I do
> > understand that it can be done using intrinsics, but that  
> > implementation
> > is (to put it mildly) suboptimal.
>
> Why?

Hmm. Perhaps I shouldn't have written so quickly. My assumption was that
intrinsics would likely entail a procedure call.

More later -- my three year old just woke up.


shap

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Checked arithmetic

Jonathan S. Shapiro-2
In reply to this post by Chris Lattner
On Tue, 2008-03-25 at 21:18 -0700, Chris Lattner wrote:

> On Mar 25, 2008, at 8:25 PM, Jonathan S. Shapiro wrote:
>
> > In looking at the LLVM reference manual, it is conspicuous that (a)  
> > the
> > IR does not define condition codes, and (b) the IR does not define
> > opcodes that return condition results in addition to their  
> > computational
> > results.
>
> We currently don't have this because noone has implemented it yet.  It  
> would be great to have this.

I want to background process this for a bit, but it would be helpful to
discuss some approaches first.

There would appear to be three approaches:

  1. Introduce a CC register class into the IR. This seems to be a
     fairly major overhaul.

  2. Introduce a set of scalar and fp computation quasi-instructions
     that accept the same arguments as their computational counterparts,
     but produce *only* the condition code. For example:

        add i32 ...    produces result
        add_cc i32 ... produces condition codes

     Once this exists, re-combine the instructions in the back end with
     peepholes.

  3. Handle CC as a black magic special case, which at least has the
     merit of tradition. :-)

Given the number of different ways that different bits of hardware
handle CCs, I am inclined to think that the right approach, in abstract,
is to introduce a CC register class and deal with CCs in a fully general
way. If so, this is not a small change.

Opinions/reactions?

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Checked arithmetic

Duncan Sands
Hi,

> There would appear to be three approaches:
>
>   1. Introduce a CC register class into the IR. This seems to be a
>      fairly major overhaul.
>
>   2. Introduce a set of scalar and fp computation quasi-instructions
>      that accept the same arguments as their computational counterparts,
>      but produce *only* the condition code. For example:
>
>         add i32 ...    produces result
>         add_cc i32 ... produces condition codes
>
>      Once this exists, re-combine the instructions in the back end with
>      peepholes.
>
>   3. Handle CC as a black magic special case, which at least has the
>      merit of tradition. :-)

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.

Ciao,

Duncan.

PS: In order for codegen to be able to handle i33, you need to turn
on the new LegalizeTypes infrastructure.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Checked arithmetic

Jonathan S. Shapiro-2
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

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Checked arithmetic

Duncan Sands
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.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Checked arithmetic

Jonathan S. Shapiro-2
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

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Checked arithmetic

Duncan Sands
Hi,

> > 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).

I think this is what you get if you do the multiply in an integer of twice
the width.

> 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.

Yes.

> 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.

In any case, this is all at the codegen level.  You suggested introducing
condition codes into the IR, and I tried to point out that you can get
at least some of what you want by using arbitrary precision integers and
floating point types (these last don't exist yet) in the IR.  For sure there
needs to be some careful codegen work to have everything come out optimally
when you codegen.

> >   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.

Ciao,

Duncan.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Checked arithmetic

Chris Lattner
In reply to this post by Jonathan S. Shapiro-2
On Wed, 26 Mar 2008, Jonathan S. Shapiro wrote:

> I want to background process this for a bit, but it would be helpful to
> discuss some approaches first.
>
> There would appear to be three approaches:
>
>  1. Introduce a CC register class into the IR. This seems to be a
>     fairly major overhaul.
>
>  2. Introduce a set of scalar and fp computation quasi-instructions
>     that accept the same arguments as their computational counterparts,
>     but produce *only* the condition code. For example:

Why not define an "add with overflow" intrinsic that returns its value and
overflow bit as an i1?

-Chris

--
http://nondot.org/sabre/
http://llvm.org/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Checked arithmetic

Jonathan S. Shapiro-2
On Wed, 2008-03-26 at 11:02 -0700, Chris Lattner wrote:

> On Wed, 26 Mar 2008, Jonathan S. Shapiro wrote:
> > I want to background process this for a bit, but it would be helpful to
> > discuss some approaches first.
> >
> > There would appear to be three approaches:
> >
> >  1. Introduce a CC register class into the IR. This seems to be a
> >     fairly major overhaul.
> >
> >  2. Introduce a set of scalar and fp computation quasi-instructions
> >     that accept the same arguments as their computational counterparts,
> >     but produce *only* the condition code. For example:
>
> Why not define an "add with overflow" intrinsic that returns its value and
> overflow bit as an i1?

Chris:

I understand several simple ways to implement add with carry. Your
suggestion is one of them. What I'm trying to understand is how to
handle the conditional code issue generally.


shap

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Checked arithmetic

Duncan Sands
In reply to this post by Chris Lattner
Hi Chris,

> Why not define an "add with overflow" intrinsic that returns its value and
> overflow bit as an i1?

what's the point?  We have this today with apint codegen (if you turn on
LegalizeTypes).  For example, this function

define i1 @cc(i32 %x, i32 %y) {
  %xx = zext i32 %x to i33
  %yy = zext i32 %y to i33
  %s = add i33 %xx, %yy
  %tmp = lshr i33 %s, 32
  %b = trunc i33 %tmp to i1
  ret i1 %b
}

codegens (on x86-32) to

cc:
        xorl    %eax, %eax
        movl    4(%esp), %ecx
        addl    8(%esp), %ecx
        adcl    $0, %eax
        andl    $1, %eax
        ret

which uses the condition code as desired.  Pity about the
redundant andl $1, %eax!

Ciao,

Duncan.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Checked arithmetic

Chris Lattner
On Wed, 26 Mar 2008, Duncan Sands wrote:

> Hi Chris,
>
>> Why not define an "add with overflow" intrinsic that returns its value and
>> overflow bit as an i1?
>
> what's the point?  We have this today with apint codegen (if you turn on
> LegalizeTypes).  For example, this function

The desired code is something like:

foo:
    addl %eax, %ecx
    jo overflow_happened
    use(%ecx)

etc.

-Chris

> define i1 @cc(i32 %x, i32 %y) {
>  %xx = zext i32 %x to i33
>  %yy = zext i32 %y to i33
>  %s = add i33 %xx, %yy
>  %tmp = lshr i33 %s, 32
>  %b = trunc i33 %tmp to i1
>  ret i1 %b
> }
>
> codegens (on x86-32) to
>
> cc:
>        xorl    %eax, %eax
>        movl    4(%esp), %ecx
>        addl    8(%esp), %ecx
>        adcl    $0, %eax
>        andl    $1, %eax
>        ret
>
> which uses the condition code as desired.  Pity about the
> redundant andl $1, %eax!
>
> Ciao,
>
> Duncan.
>

-Chris

--
http://nondot.org/sabre/
http://llvm.org/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Checked arithmetic

Chris Lattner
In reply to this post by Jonathan S. Shapiro-2
On Wed, 26 Mar 2008, Jonathan S. Shapiro wrote:
>> Why not define an "add with overflow" intrinsic that returns its value and
>> overflow bit as an i1?
>
> Chris:
>
> I understand several simple ways to implement add with carry. Your
> suggestion is one of them. What I'm trying to understand is how to
> handle the conditional code issue generally.

I'm suggesting basically:

res,overflow = add_with_cary(a,b);
if (overflow) goto somewhere
use(res)

-Chris

--
http://nondot.org/sabre/
http://llvm.org/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Checked arithmetic

Duncan Sands
In reply to this post by Chris Lattner
Hi Chris,

> > what's the point?  We have this today with apint codegen (if you turn on
> > LegalizeTypes).  For example, this function
>
> The desired code is something like:
>
> foo:
>     addl %eax, %ecx
>     jo overflow_happened
>     use(%ecx)

how's an intrinsic going to help with this?  Also, is there any chance
of codegen being capable one day of combining carry arithmetic coming
from apint and the appropriate conditional branch into a "jo"?

Ciao,

Duncan.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Checked arithmetic

Jonathan S. Shapiro-2
In reply to this post by Chris Lattner
On Wed, 2008-03-26 at 14:11 -0700, Chris Lattner wrote:

> On Wed, 26 Mar 2008, Jonathan S. Shapiro wrote:
> >> Why not define an "add with overflow" intrinsic that returns its value and
> >> overflow bit as an i1?
> >
> > Chris:
> >
> > I understand several simple ways to implement add with carry. Your
> > suggestion is one of them. What I'm trying to understand is how to
> > handle the conditional code issue generally.
>
> I'm suggesting basically:
>
> res,overflow = add_with_cary(a,b);
> if (overflow) goto somewhere
> use(res)
>
> -Chris

Yes. Sorry. I do see that that will work, and I had not intended to
sound ungrateful for your response. It is my nature, when I look at a
design problem, to try to consider the whole problem before implementing
some part. It may turn out here that there isn't really a "whole
problem" to consider. Even if there is, I agree that the shortest path
to solving my immediate problem is to do exactly as you suggest.

I guess my take is that when faced with an architectural question that
you eventually may have to address in full, quick fixes tend to accrete
that have to be undone when you get around to the general solution, and
these make implementing the general thing harder -- unless you have
thought it out in advance and the quick fixes are in line with the
eventual solution.

Now it may turn out that there isn't any "general thing" here at all.
It's just that I'ld like to think that through before adopting what you
suggest.


shap

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Checked arithmetic

Jonathan S. Shapiro-2
In reply to this post by Duncan Sands
On Wed, 2008-03-26 at 21:55 +0100, Duncan Sands wrote:

> Hi Chris,
>
> > > what's the point?  We have this today with apint codegen (if you turn on
> > > LegalizeTypes).  For example, this function
> >
> > The desired code is something like:
> >
> > foo:
> >     addl %eax, %ecx
> >     jo overflow_happened
> >     use(%ecx)
>
> ...is there any chance
> of codegen being capable one day of combining carry arithmetic coming
> from apint and the appropriate conditional branch into a "jo"?

This particular use case pattern (cond branch using CC value generated
as a side effect of a useful operation) appears often enough to be worth
getting right.

So if it's beyond what codegen can do, then codegen wants to be fixed.

It's clear enough that I can get working code emitted today -- that's
not the issue. The concern is that languages supporting non-hardware
arithmetic precisions rely on this particular pattern a whole lot.

I definitely need to dig in harder and understand how LLVM works before
I try to seriously advocate anything on this topic (or any other), but
from a surface understanding of the IR, and experience building several
prior compilers, I would say that the current IR is very well suited to
C and not yet an ideal match to Ada, COBOL, or some other languages.

That's not a criticism. Just a statement of first impressions.


shap

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Checked arithmetic

John Regehr
In reply to this post by Jonathan S. Shapiro-2
On Wed, 26 Mar 2008, Jonathan S. Shapiro wrote:

> I guess my take is that when faced with an architectural question that
> you eventually may have to address in full, quick fixes tend to accrete
> that have to be undone when you get around to the general solution, and
> these make implementing the general thing harder -- unless you have
> thought it out in advance and the quick fixes are in line with the
> eventual solution.

Hey, you need to be careful with this reasoning or else you'll end up
implementing a whole new language, compiler, and OS.

Oh wait nevermind :).

John
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Checked arithmetic

Jonathan S. Shapiro-2
On Thu, 2008-03-27 at 09:51 -0600, John Regehr wrote:
> Hey, you need to be careful with this reasoning or else you'll end up
> implementing a whole new language, compiler, and OS.
>
> Oh wait nevermind :).

Don't forget prover. :-)


shap

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Checked arithmetic

John Regehr
> Don't forget prover. :-)

Say on that note here's something that I want to see: a formal semantics
for LLVM in for example higher order logic.  This would probably not be
that difficult.

The problem that this solves is that current verified compiler efforts
appear to be highly specific to both the language and the target.

Once the semantics exists, you can either prove once and for all the that
each LLVM->LLVM optimization pass preserves the semantics of the code, or
else just do translation validation.

Verifying the LLVM->native backends should not be incredibly difficult.

Verifying a real LLVM front end would be a big projet but substantial
headway is being made on that kind of thing for example by Xavier Leroy's
group.

I've tried to sell some of the HOL folks on this idea (they have a formal
semantics for an ARM ISA, for example) but so far no dice.

John Regehr
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
12