llvm dev - Nov 2007 - [LLVMdev] program specialization vs LTO in LLVM

> LTO and partial evaluation are completely orthogonal
> from each other.  One is an optimization technique 
> and the other is a time that optimization can 
> occur.  Please explain a bit more about what you are
> trying to accomplish.
A contrived example I had in mind is a program that
computes a power function. In pseudocode:

int powerFunc( int x, int n )
{
   if n is 0
      return 1
   
   if n is even
      return square( powerFunc( x, 0.5*n ) )

   if n is odd
      return x * powerFunc( x, n - 1 )
}

If we know what the exponent (say n = 5) is at compile
time, program can be optimized via specialization
(partial evaluation) to get:

int powerFunc5( int x )
{
    return x * square( square( x ) );
}
 
My question is whether LLVM framework can perform
these 
types of transformations at runtime so that the
function can be optimized at runtime based on the
program's input as opposed to at compile time via
specialization. If yes, what are the trade-offs?

In a real program, functions would of course be very
complex with tens of arguments.

Marko 




     
____________________________________________________________________________________
Be a better pen pal. 
Text or chat with friends inside Yahoo! Mail. See how. 
http://overview.mail.yahoo.com/

On Wed, 21 Nov 2007, brdavs wrote:
>> LTO and partial evaluation are completely orthogonal
>> from each other.  One is an optimization technique
>> and the other is a time that optimization can
>> occur.  Please explain a bit more about what you are
>> trying to accomplish.
>
> A contrived example I had in mind is a program that
> computes a power function. In pseudocode:
>
> int powerFunc( int x, int n )
> {
>   if n is 0
>      return 1
>   if n is even
>      return square( powerFunc( x, 0.5*n ) )
>   if n is odd
>      return x * powerFunc( x, n - 1 )
> }
>
> If we know what the exponent (say n = 5) is at compile
> time, program can be optimized via specialization
> (partial evaluation) to get:
>
> int powerFunc5( int x )
> {
>    return x * square( square( x ) );
> }
This is actually a combination of many different things: partial eval, 
inlining, arithmetic simplification, branch folding, etc.

LLVM does have a lot of these sorts of things, but it provides the 
mechanisms to do what you want, you have to assemble them in the right 
way to get a particular job done.
> My question is whether LLVM framework can perform these types of 
> transformations at runtime
Any llvm xforms can be used at runtime.
> so that the
> function can be optimized at runtime based on the
> program's input as opposed to at compile time via
> specialization.
Yes.
> If yes, what are the trade-offs?
What do you mean?  There are none that any other sort of runtime partial 
eval doesn't share: you have the standard tradeoff between the cost of 
compilation and the cost of running the optimized code.  LLVM is very 
fast, so it doesn't take much reuse of the code to be a win, but there is 
a cost.

If you are interested in this, you should check out my (poorly done, 
hastily prepared) talk at the developer meeting, where I talk about how 
apple uses llvm for partial specialization in the opengl stack of MacOS 
10.5.  For example, see the slide "Another Example: Colorspace
Conversion"
here: http://llvm.org/devmtg/2007-05/10-Lattner-OpenGL.pdf

There isn't much detail in the presentation, but yes it definitely does 
work and is used regularly by lots of people (whether they know it or not) 
:)

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/