[LLVMdev] program specialization vs LTO in LLVM
sabre at nondot.org
Wed Nov 21 18:10:57 PST 2007
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
> 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
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"
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)
More information about the llvm-dev