Nickel, an exercise in JIT evaluation

As I hinted in my previous post, I have (very) slowly been working on implementing a simple JIT-based evaluator for a toy language, which I've called Nickel. Nickel, which I've now released on GitHub, uses the LLVM C library to leverage the power of the LLVM optimising compiler.

For full details, see the repo on GitHub, but I'll try in this post to give a brief overview. Consider the following Nickel program1, which computes and prints a numeric value:

# Saved to input.nkl...

def g(x)
  9 * x
end

def f(x, y)
  (57005 << x) + g(y + 1)
end

puts f(16, 5430)

We can evaluate this program using the nickel evaluator in simple interpreter mode:

$ ./nickel --interpreter < input.nkl
3735928559

However, the particular value printed will be more familiar with a hex representation:

$ printf "0x%x\n" $(./nickel --interpreter < input.nkl)
0xdeadbeef

A JIT evaluator performs compilation during execution - essentially generating code to execute at run-time. We can witness the generated code by using a debugger such as lldb to break at the point at which we obtain a pointer to the dynamically generated code:

int (*func)(void) = (int (*)(void))LLVMGetFunctionAddress(engine, "__anon_tl"); //<=
func();

Let's run lldb and break before we call func:

$ lldb ./nickel -- --jit
[...]
(lldb) breakpoint set --file jit.c --line 284
[...]
(lldb) process launch -i input.nkl
[...]
* thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
    frame #0: 0x00000001000035f9 nickel`jit(p=0x0000000101a08940) at jit.c:284
   281      }
   282
   283      int (*func)(void) = (int (*)(void))LLVMGetFunctionAddress(engine, "__anon_tl");
-> 284      func();
   285
   286      LLVMDisposeExecutionEngine(engine);
   287  }
[...]

Now, we can ask lldb to disassemble the func function, which will reveal the function's implementation:

(lldb) disassemble -s func
    0x101943030: movabsq $0x101944000, %rdi        ; imm = 0x101944000
    0x10194303a: movabsq $0x7fff67760710, %rcx     ; imm = 0x7FFF67760710
    0x101943044: movl   $0xdeadbeef, %esi         ; imm = 0xDEADBEEF
    0x101943049: xorl   %eax, %eax
    0x10194304b: jmpq   *%rcx
    0x10194304d: addb   %al, (%rax)

and indeed, we can see the literal value 0xdeadbeef, which means our Nickel program has been fully optimisated away by LLVM into the return of a single literal value - very cool!

  1. Nickel syntax is superficially similar to Ruby. ↩