Making a JIT compiler

c++ jit brainfuck
orlp picture orlp · May 13, 2011 · Viewed 7.6k times · Source

I've written a Brainfuck implementation (C++) that works like this:

  1. Read input brainfuck file
  2. Do trivial optimizations
  3. Convert brainfuck to machine code for the VM
  4. Execute this machine code in the VM

This is pretty fast, but the bottleneck is now at the VM. It's written in C++ and reads a token, executes an action (which aren't many at all, if you know Brainfuck) and so on.

What I want to do is strip out the VM and generate native machine code on the fly (so basicly, a JIT compiler). This can easily be a 20x speedup.

This would mean step 3 gets replaced by a JIT compiler and step 4 with the executing of the generated machine code.

I don't know really where to start, so I have a few questions:

  1. How does this work, how does the generated machine code get executed?
  2. Are there any C++ libraries for generating native machine code?

Answer

osgx picture osgx · May 13, 2011

  1. Generated machine code is just jmp-ed to or call-ed as usual function. Sometimes it also needed to disable no-execution flag (NX bit) on memory, containing generated code. In linux, this is done with mprotect(addr, size, PROT_READ | PROT_WRITE | PROT_EXEC.) In windows the NX is called DEP.

  2. There are some... E.g. http://www.gnu.org/software/lightning/ - GNU Lightning (universal) and https://developer.mozilla.org/En/Nanojit - Nanojit, which is used in Firefox JavaScript JIT engines. More powerful and modern JIT is LLVM, you just need to translate BF code into LLVM IR, and then LLVM can do optimisations and code generation for many platforms, or run LLVM IR on interpreter (virtual machine) with JIT capabilities. There is a post about BF & LLVM with complete LLVM JIT compiler for BF http://www.remcobloemen.nl/2010/02/brainfuck-using-llvm/

Another BF +LLVM compiler is here, in the svn of LLVM: https://llvm.org/svn/llvm-project/llvm/trunk/examples/BrainF/BrainF.cpp

Related questions

Any tutorial for embedding Clang as script interpreter into C++ Code?

I have no experience with llvm or clang, yet. From what I read clang is said to be easily embeddable Wikipedia-Clang, however, I did not find any tutorials about how to achieve this. So is it possible to provide the …

Read More
How to generate and run native code dynamically?

I'd like to write a very small proof-of-concept JIT compiler for a toy language processor I've written (purely academic), but I'm having some trouble in the middle-altitudes of design. Conceptually, I'm familiar with how JIT works - you compile bytecode …

Read More
Runtime optimization of static languages: JIT for C++?

Is anyone using JIT tricks to improve the runtime performance of statically compiled languages such as C++? It seems like hotspot analysis and branch prediction based on observations made during runtime could improve the performance of any code, but maybe …

Read More