A JIT for Guile

About two years ago, I started writing a JIT compiler for GNU Guile. I found that the things I thought would be hard were actually pretty easy, and the hardest part was something I thought would not be a problem.

Why JIT?

Programming language implementations fall on a spectrum. On one end are implementations that do very little preprocessing of a program, but are relatively slow to execute it. The slowest implementation would leave each part of the program as text until it had to execute it – there would be no preprocessing, but it would have to do a lot of work for each statement or expression. On the other end are implementations that are very fast to execute programs, but might need a long time to preprocess them before they can do that. The classic example of these are C or Fortran compilers, which do a lot of up-front analysis, but generate programs that run very quickly.

Implementations of high-level languages generally hit points in between those. A slow interpreter might convert each program to a syntax tree, and then interpret each syntax tree. A faster one might convert a program to bytecode and interpret that. (That’s what Guile does right now.) “JIT” can mean many different sorts of implementations, but the sort I’m talking about is the next step beyond interpreting bytecode – take a bytecode program and convert it into machine code that does what the interpreter would do if it were interpreting the bytecode. The resulting program runs faster because when the CPU is executing the bytecode interpreter, it needs to do some indirection on each instruction in order to determine what code to run, but with machine code it doesn’t.

Writing the JIT Compiler

So a JIT compiler for Guile is a program that walks through a string of bytecode and, for each bytecode instruction, writes some machine code to a buffer. Then it packages up that buffer as a function that can be called by other Scheme and C functions. I had two main jobs – write a program to do that (the actual JIT compiler), and modify the rest of Guile to use it.

First of all, the program needed to generate assembly code, so I needed an assembler. I evaluated Nanojit, SpiderMonkey, GNU Lightning, GNU Libjit, and DynASM. Some were well documented and some were poorly documented. SpiderMonkey is actually a full JavaScript implementation, not just an assembler, and it would take a lot of work to adapt it to Guile. Even within the assemblers there was variation in how much work they do vs. the speed of the generated code – Lightning generates machine code by appending blocks of pre-written code, and Libjit actually works with RTL and does register allocation itself. I experimented with Lightning, but settled on Libjit, because it supported several processor architectures, was well documented, and did register allocation – I like being on the fast end of the implementation spectrum.

The structure of the compiler is very simple – it’s a big switch statement, just like an interpreter. Here’s what it looks like:

for (objcodep = SCM_C_OBJCODE_BASE (objcode);
     objcodep - SCM_C_OBJCODE_BASE (objcode) < objcodelen;
     objcodep++)
{
  switch ((enum scm_opcode)*objcodep) {
    case scm_op_nop:
    break; /* the easiest opcode to implement. */
    case scm_op_assert_nargs_ee:
    ... cases for more instructions down here ...
  }
  ip = jit_insn_add(function, ip, ipup);
}

(The second-to-last line is there because it’s important to keep the VM’s instruction pointer up to date, so JITted code can interoperate with interpreted bytecode.) I implemented cases for enough instructions to compile

(lambda () 0)

It’s a simple function that returns zero, but it’s enough for me to check that the JIT compiler works, and enough for me to work on integrating the JIT compiler with the rest of Guile.

Connecting the JIT to Guile

Connecting the JIT to Guile was mostly straightforward. I made the bytecode interpreter call the JIT compiler on each piece of bytecode at the beginning. If the JIT interpreter worked, the bytecode interpreter would use the machine code it generated instead of interpreting the bytecode. I gave it a failure mode – if the JIT compiler failed to compile a function, the bytecode interpreter would work as usual. This let me test the JIT easily even when it couldn’t compile many functions. I stepped through the program a few times with GDB and made sure that it did, in fact, call JIT-generated machine code.

I also needed a place to store this JIT code, so I didn’t have to re-generate it each time I ran the same piece of machine code. The byte code is stored in ‘struct objcode’ objects. They take four bytes, and I didn’t want to make them bigger because that would put more pressure on the CPU cache. Luckily, the old ‘struct objcode’s didn’t need all four of their bytes: depending on the source of the objcode, either the third or the fourth byte would have information, but never both. So I could store all of that information in the third byte, and leave the fourth byte available for native code. With all of these pieces in place, I had a working JIT compiler in Guile.

Everything’s Easy … Almost

At this point I thought all of the technical challenges would be over. All that was left was to expand the JIT compiler to include all of the other bytecode instructions, and I would be done.

Unfortunately, that would be a bad way to set up the JIT compiler. Each part of the switch statement in the JIT compiler contained exactly the same information as the equivalent part of the switch statement in the bytecode interpreter. This would be a gigantic duplication of code, and every time we updated the bytecode format we would have to update both the bytecode interpreter and the JIT compiler. That seemed inelegant, so I wanted to do something better: generate them both from the same source.

I emailed the Guile development mailing list, and we discussed two possibilities: either generate the JIT compiler from the bytecode interpreter, or generate them both from some third source. It sounded to me like the maintainers did not want to generate the bytecode from anything, so that left generating the JIT compiler from C code, which required parsing C.

Current Status

And that is where I left the JIT compiler, almost two years ago. I did not have a C parser, and I still don’t. I would like Guile to have one in the long term anyway, because it could let it generate FFI bindings automatically, but I haven’t written it yet.

However, in recent mailing list posts, it appears that either people have changed their minds, or I was wrong before – it now seems fine to generate the bytecode interpreter and JIT compiler from some third format. There has also been some work by Stefan Tampe on generating C code from an S-expression representation. That means that it might be possible to finally add a JIT to Guile soon.

Coming Soon

So what happened in those two years? Lots of things! Guile has many compilers, and I’ve worked on several of them. But more on that in another post.

Advertisements