Partial evaluation and LLVM (2)

Message: 3
Date: Tue, 12 Jun 2007 10:42:50 -0700 (PDT)
From: Chris Lattner <sabre@nondot.org>
Subject: Re: [LLVMdev] Partial evaluation and LLVM
To: LLVM Developers Mailing List <llvmdev@cs.uiuc.edu>
Message-ID: <Pine.LNX.4.62.0706121039530.30413@nondot.org>
Content-Type: text/plain; charset="iso-8859-1"

Would LLVM be adapted to express and do some kind of function
"partial evaluation", like having a function of 2 arguments, and when
a value of one of the 2 parameter is known, the function could be
specialized to produce as result a more efficient new function that
would take one 1 parameter. I was told that the "ReplaceAllUsesWith"
operation could be possibly used for that purpose. Is there any
example of this technique I could look at?

LLVM has direct API support for this.

1. Compile your generic function to LLVM bytecode.
2. In the code that does the specialization, create a new Function object
    with just the new set of arguments (the specialized arguments should
    not be created).
3. Create a DenseMap<const Value*, Value*> ValueMap object. Populate it
    with mappings from the generic function's arguments to either the new
    functions arguments (if they are not specialized) or the constants you
    want to specialize the argument to.
4. Call the CloneAndPruneFunctionInto function
    (llvm/Transforms/Utils/Cloning.h) passing in the new empty
    (destination) function, the generic "source" function, and your value
    map.
5. Run any other optimizations that you want over the new function.

-Chris

--
Chris Lattner's Homepage
http://llvm.org/

Thanks, this works.

Would it be possible to specialize a function that has some "free" variables, more precisely a method in a class that use the value of some of the object instance fields? Or does the function to specialize has to be closed in some way?

Thanks

Stephane Letz

Thanks, this works.

Great.

Would it be possible to specialize a function that has some "free"
variables, more precisely a method in a class that use the value of
some of the object instance fields? Or does the function to
specialize has to be closed in some way?

Yes.

The solution I've found is to use llvm global variables. Consider:

extern int specializevar;

void genericfunc() {
   if (specializevar == 42)
     blah();
}

The steps become:

1. Clone genericfunc (specializing based on arguments if you like).
2. Give specializevar an initializer for the value you want to specialize on. Mark it constant.
3. Run instcombine and other xforms on genericfunc. Instcombine will forward substitute loads from the global into the constant values.
4. JIT the result etc.
5. Mark specializevar non-constant, remove the initializer.

-Chris