llvm dev - Jun 2010 - [LLVMdev] experimenting with partial evaluation

Hello !

I wanted to experiment with partial evaluation and llvm seems to be the
right tool for this, but since I'm new to it of course I'm a bit lost !

I'll try to explain what I want to do in the simplest possible way :

I have a C program.
In this program, there is a function f( a,b ).
I have a value A for a.
I want to specialise f() so I get a function fA( b ) which is the same as
f( a=A, b ).
It looks like a futamura projection (think about the classical adder
problem).

So, in my program, at runtime, I'd like to get a llvm Function* on the
function I want to specialize, so I can write code that hacks on the
arguments and bitcode of f and JITs a new version of it.

I have found examples about how to generate llvm instructions at runtime
and JIT that into a function, but that's not what I'm interested in : I
want to modify the code of an existing function, not generate a function
   from nothing.

I succeeded in compiling to bitcode, loading the program's bitcode,
extracting a Function *, JITting it and executing it, but then whatever is
in my function can't call the rest of the program, because when I load the
bitcode, what is in it has no relation to the rest of my program, even
though it is the same code, there are actually 2 copies of it which are
not linked.

And I'm a llvm newbie so I have a few questions :

- In a running program, can I get pointers to the llvm Module that
contains the code currently being executed ?
     Using this I could do a module->getFunction() to get the Function,  
clone
it, tweak it, JIT it and I'd be happy.

- When I JIT something how can I link it to my running program so it can
call functions and access globals ?

- How should I compile my program so I can do all that ? (I guess I
shouldn't compile it to x86-64 native but bitcode instead, but what
options ?..)

Maybe I'm asking the wrong questions, feel free to object ;)

Thanks for your time.

Good evening, Pierre.


Here is an example to you. attached. run with -disable-lazy-comilation.
It is *as-is* for Win32 but might be applicable to *-linux-elf more smartly.
It does get llvm::Function* by function ptr(not name!),
and clone a specialized function,
and execute specialized one
in the same context as parent lli.

> - In a running program, can I get pointers to the llvm Module that
> contains the code currently being executed ?
>     Using this I could do a module->getFunction() to get the Function,
> clone
> it, tweak it, JIT it and I'd be happy.
AFAIK, current version of lli does not support.
I let lli to export current llvm::Module* and llvm::ExecutionEngine*.

Current llvm::Module const* could be gotten from llvm::Function const*,
but you must need not Module const* but writable one.
(or, clone a module to optimize)

> - When I JIT something how can I link it to my running program so it can
> call functions and access globals ?
 - to export some symbols in lli and llvm/lib. It would be difficult in Win32.
   I believe it possible to work with ELF.

 - to build llvm with shared object. Some APIs might be neede to
   your application. lli should resolve symbols when he reads *.bc.

> - How should I compile my program so I can do all that ? (I guess I
> shouldn't compile it to x86-64 native but bitcode instead, but what
> options ?..)
I guess you will need a special version of lli.


mata ne, Takumi
-------------- next part --------------
fib(2)=1
GV:0x309e20
FN:0x309e20
RAW:0xb40070
a0=0x311868
Ffib8=0x31f1d8<_Z3fibi1>

define internal i32 @_Z3fibi1() nounwind readnone {
entry:
  %0 = icmp sgt i32 2, 2                          ; <i1> [#uses=1]
  br i1 %0, label %entry.bb_crit_edge, label %entry.bb2_crit_edge

entry.bb2_crit_edge:                              ; preds = %entry
  br label %bb2

entry.bb_crit_edge:                               ; preds = %entry
  br label %bb

bb:                                               ; preds = %bb,
%entry.bb_crit_edge
  %lsr.iv = phi i32 [ %lsr.iv.next, %bb ], [ 2, %entry.bb_crit_edge ] ;
<i32> [#uses=2]
  %accumulator.tr1 = phi i32 [ %2, %bb ], [ 1, %entry.bb_crit_edge ] ;
<i32> [#uses=1]
  %tmp1 = add i32 %lsr.iv, -1                     ; <i32> [#uses=1]
  %1 = tail call i32 @_Z3fibi(i32 %tmp1) nounwind ; <i32> [#uses=1]
  %2 = add nsw i32 %1, %accumulator.tr1           ; <i32> [#uses=2]
  %lsr.iv.next = add i32 %lsr.iv, -2              ; <i32> [#uses=2]
  %3 = icmp sgt i32 %lsr.iv.next, 2               ; <i1> [#uses=1]
  br i1 %3, label %bb, label %bb.bb2_crit_edge

bb.bb2_crit_edge:                                 ; preds = %bb
  br label %bb2

bb2:                                              ; preds = %bb.bb2_crit_edge,
%entry.bb2_crit_edge
  %accumulator.tr.lcssa = phi i32 [ 1, %entry.bb2_crit_edge ], [ %2,
%bb.bb2_crit_edge ] ; <i32> [#uses=1]
  ret i32 %accumulator.tr.lcssa
}

Specialized:fnaddr=0xb40720

define internal i32 @_Z3fibi1() nounwind readnone {
entry:
  br i1 false, label %bb, label %bb2

bb:                                               ; preds = %entry, %bb
  br i1 false, label %bb, label %bb2

bb2:                                              ; preds = %bb, %entry
  ret i32 1
}

Specialized fib(2)=1
-------------- next part --------------
A non-text attachment was scrubbed...
Name: j.cpp
Type: application/octet-stream
Size: 1409 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100612/2cb41244/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: lli.diff
Type: application/octet-stream
Size: 3057 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100612/2cb41244/attachment-0001.obj>

> Here is an example to you. attached. run with -disable-lazy-comilation.
> It is *as-is* for Win32 but might be applicable to *-linux-elf more  
> smartly.
> It does get llvm::Function* by function ptr(not name!),
> and clone a specialized function,
> and execute specialized one
> in the same context as parent lli.
Many thanks. Using your code I was able to get useful results ! Many  
thanks to the helpful people on IRC, too.
> AFAIK, current version of lli does not support.
> I let lli to export current llvm::Module* and llvm::ExecutionEngine*.
I've tried to patch lli like you did but the problem was that I got lots  
of "LLVM ERROR: Program used external function" which is why, I guess,
you
had to enumerate all the symbols you used as externs in your patch... I'd  
rather avoid this solution ;)

So I've tried something else : I've written a minimalistic launcher
(like
a bare bones lli) which loads the module which contains the code, passes  
it its own Module* and ExecutionEngine*, so the code inside the module has  
those, then runs it.

It works nicely, except I have to launch my launcher with lli, if I  
compile it native and run it, I get the same undefined external functions  
errors. I've probably done something wrong somewhere...

I'd like to use the patched lli (passing the pointers to the code in the  
Module) since this is the most elegant solution, if anyone has ideas on  
how to get rid of the missing symbols. I guess i'd need to link all  
libraries used by the Module inside lli which could get ugly.

Anyway, I can run partial evaluation on a function like you did, but i  
have a little problem : if the function gets a bit complex, then the  
optimization pass crashes. I get this :


0  libLLVM-2.7.so.1 0x00007fefb5274d2f
1  libLLVM-2.7.so.1 0x00007fefb527538d
2  libpthread.so.0  0x00007fefb46668f0
3  libLLVM-2.7.so.1 0x00007fefb4e90b09  
llvm::ConstantExpr::getSizeOf(llvm::Type const*) + 9
4  libLLVM-2.7.so.1 0x00007fefb4c82c31  
llvm::ScalarEvolution::getSizeOfExpr(llvm::Type const*) + 33
5  libLLVM-2.7.so.1 0x00007fefb4c72693  
llvm::ScalarEvolution::createNodeForGEP(llvm::GEPOperator*) + 483
6  libLLVM-2.7.so.1 0x00007fefb4c731fd  
llvm::ScalarEvolution::createSCEV(llvm::Value*) + 1565
7  libLLVM-2.7.so.1 0x00007fefb4c73ad3  
llvm::ScalarEvolution::getSCEV(llvm::Value*) + 227
8  libLLVM-2.7.so.1 0x00007fefb4c73482  
llvm::ScalarEvolution::createSCEV(llvm::Value*) + 2210
9  libLLVM-2.7.so.1 0x00007fefb4c73ad3  
llvm::ScalarEvolution::getSCEV(llvm::Value*) + 227
10 libLLVM-2.7.so.1 0x00007fefb4c82864  
llvm::ScalarEvolution::createNodeForPHI(llvm::PHINode*) + 1060
11 libLLVM-2.7.so.1 0x00007fefb4c72f10  
llvm::ScalarEvolution::createSCEV(llvm::Value*) + 816
12 libLLVM-2.7.so.1 0x00007fefb4c73ad3  
llvm::ScalarEvolution::getSCEV(llvm::Value*) + 227
13 libLLVM-2.7.so.1 0x00007fefb4c20d58  
llvm::IVUsers::AddUsersIfInteresting(llvm::Instruction*) + 312
14 libLLVM-2.7.so.1 0x00007fefb4c21ffb  
llvm::IVUsers::runOnLoop(llvm::Loop*, llvm::LPPassManager&) + 331
15 libLLVM-2.7.so.1 0x00007fefb4c3aa67  
llvm::LPPassManager::runOnFunction(llvm::Function&) + 1015
16 libLLVM-2.7.so.1 0x00007fefb4ef6172  
llvm::FPPassManager::runOnFunction(llvm::Function&) + 498
17 libLLVM-2.7.so.1 0x00007fefb4ef62eb  
llvm::FunctionPassManagerImpl::run(llvm::Function&) + 91
18 libLLVM-2.7.so.1 0x00007fefb4ef649e  
llvm::FunctionPassManager::run(llvm::Function&) + 110
19 libLLVM-2.7.so.1 0x00007fefb4f9821c  
llvm::JIT::runJITOnFunctionUnlocked(llvm::Function*, llvm::MutexGuard  
const&) + 28
20 libLLVM-2.7.so.1 0x00007fefb4f985e3  
llvm::JIT::getPointerToFunction(llvm::Function*) + 387
21 libLLVM-2.7.so.1 0x00007fefb59a08c9  
llvm::JIT::getPointerToFunction(llvm::Function*) + 10519657
Stack dump:
0.      Program arguments: lli -disable-lazy-compilation launcher_jit.bc
1.      Running pass 'Loop Pass Manager' on function  
'@_Z14rpn_exec_stackPK15RPN_InstructioniPdPK13RPN_Variables_1'
2.      Running pass 'Induction Variable Users' on basic block
'%bb24'
Erreur de segmentation

The partial evaluation on another simpler function works, but if I add an  
Inlining pass, then the optimization pass crashes too. I get this :

0  libLLVM-2.7.so.1 0x00007f72d543dd2f
1  libLLVM-2.7.so.1 0x00007f72d543e38d
2  libpthread.so.0  0x00007f72d482f8f0
3  libLLVM-2.7.so.1 0x00007f72d50bde91  
llvm::ModulePass::assignPassManager(llvm::PMStack&, llvm::PassManagerType)  
+ 113
4  libLLVM-2.7.so.1 0x00007f72d50baef9  
llvm::PMTopLevelManager::schedulePass(llvm::Pass*) + 425
5  libLLVM-2.7.so.1 0x00007f72d5b69854  
llvm::PMTopLevelManager::schedulePass(llvm::Pass*) + 11201284
Stack dump:
0.      Program arguments: lli -disable-lazy-compilation launcher_jit.bc
Erreur de segmentation

Argh. Any ideas ?