[LLVMdev] program specialization vs LTO in LLVM

[Chris Lattner]

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/