Order of operations

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

Order of operations

Jonathan S. Shapiro-2
Given variables a b c d of compatible scalar arithmetic types, consider
the expression:

        a + b + c + d

There are multiple implementation orders for computing this sum, and the
one you want can be dependent on the source language specification. In
particular, the + operation must not be considered commutative if these
are floating point values and we care about error ranges.

It is not obvious to me from the IR specification how the front end can
specify prescriptively that some particular order of operation is
required.

I'm probably missing something very obvious here.


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: Order of operations

Chris Lattner

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

> Given variables a b c d of compatible scalar arithmetic types,  
> consider
> the expression:
>
> a + b + c + d
>
> There are multiple implementation orders for computing this sum, and  
> the
> one you want can be dependent on the source language specification. In
> particular, the + operation must not be considered commutative if  
> these
> are floating point values and we care about error ranges.
>
> It is not obvious to me from the IR specification how the front end  
> can
> specify prescriptively that some particular order of operation is
> required.
>
> I'm probably missing something very obvious here.

LLVM IR is three address code, not a tree form.  This requires the  
front-end to pick an ordering that works for it explicitly as it  
lowers to LLVM IR.

-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: Order of operations

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

> LLVM IR is three address code, not a tree form.  This requires the  
> front-end to pick an ordering that works for it explicitly as it  
> lowers to LLVM IR.

I got that much. But I assume that optimization passes, if used, are
entitled to rewrite the IR. For example: ANSI C requires that certain
types of parenthesization be honored rigorously, while other operations
can legally be combined or reordered. How does the front end specify in
it's IR emission which kinds are which, so that the optimizer knows
which parts it is not permitted to re-arrange?

_______________________________________________
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: Order of operations

Chris Lattner

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

> On Tue, 2008-03-25 at 20:42 -0700, Chris Lattner wrote:
>
>> LLVM IR is three address code, not a tree form.  This requires the
>> front-end to pick an ordering that works for it explicitly as it
>> lowers to LLVM IR.
>
> I got that much. But I assume that optimization passes, if used, are
> entitled to rewrite the IR. For example: ANSI C requires that certain
> types of parenthesization be honored rigorously,

You're thinking about FORTRAN, not C.

> while other operations
> can legally be combined or reordered. How does the front end specify  
> in
> it's IR emission which kinds are which, so that the optimizer knows
> which parts it is not permitted to re-arrange?

The compiler currently doesn't change code if it changes its  
semantics.  This means it doesn't reassociate FP operations etc.  In  
the future, we may extend the IR to capture information to tell the  
optimizer when it is safe to do this, until then it is completely  
conservative.

-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: Order of operations

Jonathan S. Shapiro-2
On Tue, 2008-03-25 at 21:05 -0700, Chris Lattner wrote:
> The compiler currently doesn't change code if it changes its  
> semantics.  This means it doesn't reassociate FP operations etc.  In  
> the future, we may extend the IR to capture information to tell the  
> optimizer when it is safe to do this, until then it is completely  
> conservative.

Thanks.

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