Archive for December, 2009

Converting stack-to-register

Like many other virtual machines, the YARV machine is stack-based.  Because most modern CPUs are register-based, to compile YARV bytecode to efficient native code means the stack operations need to be converted to register operations.

Ludicrous does this by walking the instruction sequence and pushing and popping value objects onto and off of a stack at compile-time.  This completely eliminates the YARV stack (the machine stack is still used by libjit as necessary), but has some limitations: all control paths must produce an identical stack.  A conditional that produces a different size stack in one path than in another will break this scheme.

Ludicrous does its best to detect this situation if it ever comes up and will refuse to compile bytecode that tries to do evil things like this.  However, I recently discovered a case that wasn’t covered:

irb(main):001:0> require 'internal/method'
=> true
irb(main):002:0> def foo; return true ? 1 : 2; end
=> nil
irb(main):003:0> puts method(:foo).body.body.disasm
== disasm: <RubyVM::InstructionSequence:foo@(irb)>======================
0000 trace            8                                               (   8)
0002 putobject        1
0004 jump             8
0006 putobject        2
0008 trace            16
0010 leave
=> nil

Here YARV has made an optimization — true is always true, so a conditional branch is unnecessary. However YARV wasn’t smart enough to remove the dead code that pushes ‘2’ onto the stack. When Ludicrous compiles this, it gets confused because at the leave instruction the stack contains [ 1, 2 ] (remember that Ludicrous evaluates the stack at compile time).

I suspect this is a bug in the YARV optimizer, but it illustrates the case — converting code written for a stack machine to run on a register machine is no trivial task. I’m not sure yet how to handle this case. All control paths (there is only one) do produce the same stack, but Ludicrous does not have a mechanism to detect that the second pushobject instruction is dead code and does not modify the stack.

Perhaps the best solution is to raise an exception and fall back on the interpreter for functions that do this.

Tags: , , , , , ,

Why libjit?

One question I’ve been asked quite a bit over the last two years is why I decided to use libjit for Ludcirous. Evan Phoenix had considered it for Rubinius a long time ago but rejected it partly because of the license. When I started Ludicrous, I decided to use libjit in spite of the GPL license (the license has since been changed to LGPL).

First of all, why is the GPL (v2) license problematic for a JIT compiler? Any JIT compiler using libjit must link with it, and any program run under this JIT compiler therefore ends up dynamically linking with libjit in the end. This puts the user in a precarious grey area in terms of the GPL (particularly since at the time the code had to be modified to run under Ludicrous). As I said, libjit is now under the LGPL (GPL plus an exception would have been sufficient as well), so this is no longer an issue.

Yet I picked libjit in spite of this because I felt it was the best tool for the job at the time. I evaluated a number of other alternatives:

  • GNU Lightning – much of the library is implemented with macros, making it difficult to use programmatically. It would be virtually impossible to wrap this library as a ruby module without some heavy hacking. It also requires the user to do his own register allocation, which isn’t something I was interested in figuring out.

  • DynASM – this is the “dynamic assembler” used by LuaJIT. It’s supposed to be very fast and lightweight. It’s basically a lua script that preprocesses your C source code, looking for platform-independant asm and replacing it with C calls to generate that asm at runtime. I didn’t look too closely at this because of its dependency on lua.

  • LLVM – somewhat heavyweight, much more than a JIT, but interesting because of its power. However, at the time I could not make heads or tails of their documentation, much less build a simple prototype that adds two numbers. I get the impression this has been addressed now (judging from the number of compilers using LLVM these days), but I’ve never looked back at LLVM.

  • NekoVM – had a working JIT for about two years before I started Ludicrous. Looks lightweight. I wasn’t interested, though, in compiling to a different VM; I wanted Ludicrous-compiled code to run under MRI (giving me full access to all the C extensions that are available).

  • Nanojit – I believe this was available at the time, but was too new to interest me.

  • Libjit – small, lightweight, but most importantly, well documented. It’s a register-based VM that emits code as functions are called, making it easy to wrap as a ruby extension. It does physical register allocation for me; I just pretend I have an infinite number of registers and let libjit do the work. I read through the tutorials in less than half an hour and had a prototype of ruby-libjit running the same afternoon. After that, as they say, it’s all history.