llvm dev - Apr 2007 - [LLVMdev] Integrating LLVM in an existing project

Hi everyone,

After some time hacking on llvm, let me introduce myself :)
I'm a PhD student at the French university Pierre et Marie Curie in 
Paris. I work on a project
called the "Virtual Virtual Machine" project. You can find some
(dated)
information on the
website http://vvm.lip6.fr.

Basically it's a "low level virtual machine" :) with a just in
time
compiler called the VPU, an execution environment
(GC + threads) and it parses a lisp-like language that is translated to 
the VPU's internal bytecode.

On top of this execution environment we have implemented a java virtual 
machine and a .net virtual machine. They
are both functional and we achieve reasonable performance (1/3 of IBM's 
JVM or Mono).

Our just in time compiler is however what we think the main limit for 
having better performance. Our register allocator
is really simple and we don't have any basic optimization passes. So we 
decided to take a look at llvm and see if it was
possible to translate the VPU's internal bytecode to llvm's bytecode. 
After porting llvm to linux/ppc, and adding some
functionality in llvm (like knowing the required size for the code of a 
method before allocating memory for the method), we can now execute
a large amount of code of our lisp-like language.

So the next step was to execute our Java and .Net virtual machine on top 
of the new execution environment with llvm. They are both
implemented in the lisp-like language, therefore we expected nothing or 
at least little changes. Which was the case. However when executing Java 
or .Net applications we turned into the problem of exception handling.

Exception handling is not integrated in our execution environment. The 
JIT is not aware of exception handling. Therefore they are handled at 
the application level with setjmp and longjmp. When a method with 
exceptions is compiled, we set labels (start, end, handler) in the 
compiler for each exception and after compilation grab the address of 
these labels in the generated code. When an exception is thrown, we 
compare the current instruction pointer with all couples (start, end) of 
the current method. If the IP is in the interval, and if the exception 
type is correct, we setjmp to an instruction in the method's code which 
will jump to the handler. If not, we look at the calling method's 
exceptions, and so on until we reach the end of the backtrace.

This algorithm does not work with llvm because creating labels (which 
correspond to creating basic blocks) does not imply that the label (ie 
the basic block) will have an address. Even without optimizations 
enabled in llvm, some basicblocks are not emitted (obviously because 
some basic blocks are useless).

We can not use current exception handling in llvm, see 
http://www.nondot.org/sabre/LLVMNotes/ExceptionHandlingChanges.txt.
We can not use the llvm.dbg.stoppoint feature because it is not 
implemented in llvm's JIT.

So we are stuck :). However we would really like to see what performance 
gains we have with llvm.

So here are a few questions whose answers will help me go through this issue
1) Is the Chris' exception handling note actually implemented or is it 
still in project? And how difficult do you expect it to be? (Even if I 
have implemented some stuff in llvm, I am still not entirely comfortable 
with the code)
2) The llvm.dbg.stoppoint: how far is it actually implemented?
3) Getting the address of basic blocks: is there a workaround?

Thanks a lot for your answers. And don't hesitate to ask me more infos 
if things aren't clear in my explanations.

Best,
Nicolas

Hi Nicolas,

On Thu, 2007-04-05 at 14:10 +0200, Nicolas Geoffray
wrote:
> Hi everyone,
> 
> After some time hacking on llvm, let me introduce myself :)
> I'm a PhD student at the French university Pierre et Marie Curie in 
> Paris. I work on a project
> called the "Virtual Virtual Machine" project. You can find some
(dated)
> information on the
> website http://vvm.lip6.fr.
> 
> Basically it's a "low level virtual machine" :) with a just
in time
> compiler called the VPU, an execution environment
> (GC + threads) and it parses a lisp-like language that is translated to 
> the VPU's internal bytecode.
Interesting project. I wish you could talk about it at the Developer's
Meeting (http://llvm.org/DevMtgMay2007.html :)

.. snip ..
> So here are a few questions whose answers will help me go through this
issue
> 1) Is the Chris' exception handling note actually implemented or is it 
> still in project? 
I have signed up to implemented this (PR1269) just as Chris' note
states. HLVM needs it for much the same reason that VVM does.  I hope to
address this in late April. I'm not sure if it will make it into the 2.0
release (if it does, it will be close).
> And how difficult do you expect it to be? (Even if I have implemented
> some stuff in llvm, I am still not entirely comfortable with the code)
Well, its not conceptually difficult. At the LLVM IR level its pretty
easy: add an unwind target to a basic block and remove the invoke
instruction. Its dealing with the consequence of those two changes. It
affects many passes and all targets. The changes required individually
are not too bad, but there are a lot of them. See the work plan in
PR1269.
> 2) The llvm.dbg.stoppoint: how far is it actually implemented?
This is fully implemented in static compilations and works well with GDB
(i.e. you can debug a program generated by LLVM quite well).  For JIT,
the reason its not implemented is because its unclear how the
information would be used. Would one want to run LLI under GDB and
actually debug the executed program? If so, where does all the debug
information go? GDB doesn't read debug information out of LLVM IR
representation :) We don't know of a way to generate it on the fly in a
form GDB can consume (it prefers DWARF in a file).

Another option is to implement a debugger directly in LLI that knows
about LLVM debug information. This is somewhat like the java approach
(running a debug version of the VM).

So, the question really is, how do you want to use this in the JIT? 
> 3) Getting the address of basic blocks: is there a workaround?
I don't know. I'll let someone else answer this.  This has been
discussed several times but I wasn't paying attention to the
answers/results ;)
> 
> Thanks a lot for your answers. And don't hesitate to ask me more infos 
> if things aren't clear in my explanations.
It was quite clear! Thanks for letting us know.

Reid.
> 
> Best,
> Nicolas
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Hi Reid

Reid Spencer wrote:
>
> Interesting project. I wish you could talk about it at the Developer's
> Meeting (http://llvm.org/DevMtgMay2007.html :)
>
>   
I wish I could! Unfortunately there is very little chance I get the 
fundings to
go to the US in May.
>
> I have signed up to implemented this (PR1269) just as Chris' note
> states. HLVM needs it for much the same reason that VVM does.  I hope to
> address this in late April. I'm not sure if it will make it into the
2.0
> release (if it does, it will be close).
>   
That's great news! I'll look at the PR to see if I can
help.
>> 2) The llvm.dbg.stoppoint: how far is it actually implemented?
>>     
>
> So, the question really is, how do you want to use this in the JIT? 
>
>   
Didn't see that one coming :) Maybe I want to use it like I want to use
basic blocs for getting addresses of instructions. My only concern is to 
be sure that a
list of instruction is generated between one label and one other, and to 
know the
addresses of these labels.

Thanks Reid!

Best,
Nicolas

On Thu, 5 Apr 2007, Nicolas Geoffray wrote:
> On top of this execution environment we have implemented a java virtual
> machine and a .net virtual machine. They
> are both functional and we achieve reasonable performance (1/3 of IBM's
> JVM or Mono).
Cool.
> This algorithm does not work with llvm because creating labels (which
> correspond to creating basic blocks) does not imply that the label (ie
> the basic block) will have an address. Even without optimizations
> enabled in llvm, some basicblocks are not emitted (obviously because
> some basic blocks are useless).
Right.
> We can not use current exception handling in llvm, see
> http://www.nondot.org/sabre/LLVMNotes/ExceptionHandlingChanges.txt.
Why not?
> We can not use the llvm.dbg.stoppoint feature because it is not
> implemented in llvm's JIT.
llvm.dbg.stoppoint isn't really what you want, this is really for debug 
info support.
> So here are a few questions whose answers will help me go through this
issue
> 1) Is the Chris' exception handling note actually implemented or is it
> still in project? And how difficult do you expect it to be? (Even if I
> have implemented some stuff in llvm, I am still not entirely comfortable
> with the code)
There are two separate issues here:

1. catching exceptions from function calls
2. catching exceptions from "non call" instructions like divides, etc.

The LLVM IR, as it stands now, is expressive enough to describe #1, but 
not #2.  The notes above talk solely about how to extend the IR to support 
#2.  Reid has an interest in implementing #2 at some point, which will be 
a great improvement for some applications.

There is an extra wrinkle here though.  Zero-cost C++ exception handling 
(i.e. #1) is about 3/4 of the way implemented in the C front-end and code 
generator, but it is not yet completed (notably, JIT support is missing). 
This work is also currently stalled.

If you'd be interested in helping with any of these projects, please let 
me know!

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/

Hi Chris,

Chris Lattner wrote:
>> We can not use current exception handling in llvm, see
>> http://www.nondot.org/sabre/LLVMNotes/ExceptionHandlingChanges.txt.
>>     
>
> Why not?
>
>   
Like you say, it's not functional for non-calls instructions. Besides, 
having to change
all CalInst to InvokeInst is just too much pain in our current vm.
> There are two separate issues here:
>
> 1. catching exceptions from function calls
> 2. catching exceptions from "non call" instructions like divides,
etc.
>
> The LLVM IR, as it stands now, is expressive enough to describe #1, but 
> not #2.  The notes above talk solely about how to extend the IR to support 
> #2.  Reid has an interest in implementing #2 at some point, which will be 
> a great improvement for some applications.
>
> There is an extra wrinkle here though.  Zero-cost C++ exception handling 
> (i.e. #1) is about 3/4 of the way implemented in the C front-end and code 
> generator, but it is not yet completed (notably, JIT support is missing). 
> This work is also currently stalled.
>
>   
Actually, why is it missing? What's the difference between the code 
generator
and the JIT?
> If you'd be interested in helping with any of these projects, please
let
> me know!
>   
The thing is, I know very little on exception handling (our 
setjmp/longjmp mechanism in our vms
is functional but not really optimized) and zip on LLVM. I looked at 
Reid's notes for implementing #2,
and I'm not sure I can help without having a month or two (of spare 
time) to learn LLVM's internals.

However, I'd be interested to look at how exception handling can be 
implemented in the JIT.
What's the current situation?

Nicolas