program specialization vs LTO in LLVM

Project Infrastructure LLVM Dev List Archives
1

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

2

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) :slight_smile:

-Chris