Run Length Encoding
Instead of individually executing 5 consecutive instructions, combine them into one instruction with a count of 5. For example, add 5 to the value, instead of adding 1, 5 times.
Complexity : O(N) (Performed during Lexing)
Bjit
C++23 optimizing Brainfuck tail-call interpreter, and jit compiler
2026
As a fun learning project, to learn more about low level optimization, compilers and interpreters, I made an optimizing brainfuck interpreter and J.I.T. compiler. After parsing it performs multiple optimization passes, such as run length encoding. The interpreter and jit compiler do not implement memory growth, so the amount of memory available to brainfuck programs is bound. This project was also in part inspired by a post about C tail call parsing in Protobuf, which I have linked below..
Once the parsing is done, it can either interpret the bytecode, or compile and execute it, using jit compilation.
Optimizations
Bjit can perform the following optimizations on the bytecode.
Expression Folding
If expressions result in a net zero, they are omitted. For example, 2 shifts to the left, followed directly by 2 shifts to the right, would result in no shifts being emitted.
Complexity : O(N)
Clear-loop Folding
Replaces single-cell loops such as [-] or [+] with a dedicated Clear operation.
Complexity : O(N)
Redundant-clear elimintation
Collapses consecutive Clear operations on the same cell, into one, since clearing an already cleared cell has no effect.
Complexity : O(N)
Clear-span folding
Recognizes sequences equivalent to Clear, Right(1), Clear, as a dedicated ClearSpan operation.
Complexity : O(N)
Scan-loop folding
Converts loops that only move the pointer, such as [>] or [<<<] with a dedicated ScanLeft or ScanRight operation.
Complexity : O(N)
Multiply-add loop folding
Converts suitable loops that distribute the current cell's value into a MultiplyAdd operation. This covers common brainfuck copy, move and multiply loops. The loop must return the pointer to it's starting location, and modify the source by an odd amount.
Complexity : O(N * K), Worst-Case O(N^2)
Jit
The jit compiler make use of xbyak to convert assembly into executable machine code. It also uses some C++ defined helper methods, such as a buffered io implementation of read and write, these are standard function calls, directly to the correct method. For the application binary interface, it currently only supports SysV x86_64, with having been tested on Linux 7.2.0-1.
case OpKind::Inc:
{
const auto amount = static_cast<std::uint8_t>(op.operand);
if (amount == 1)
{
inc(byte[rbx]);
}
else if (amount != 0)
{
add(byte[rbx], amount);
}
break;
}
Interpreter
The interpreter makes use of direct threading, through guaranteed tail calls. It requires a way to guarantee tail calls for this, otherwise you will get a stack overflow. Currently it only supports clang and gcc, as it uses the preserve_none and musttail attributes (musttail is not available -as of writing- in msvc). Musttail as the name implies guarantees tail calls, if a tail call isn't possible, it will generate a compile error. "preserve_none" tells the compiler that the callee preserves almost no general-purpose registers, freeing up the callee-saved registers, this can help paired with the musttail attribute to keep arguments to the musttail handlers pinned in the calle-saved registers, instead of spilling to the stack.
#define VM_NEXT(vm_, pc_, cell_) \
do \
{ \
const auto *next_ = (pc_); \
VM_MUSTTAIL return next_->handler((vm_), next_, (cell_)); \
} while (false)
static VM_CC VmResult
op_inc(Vm *vm, const ThreadedOp *pc, uint8_t *cell)
{
assert(pc);
assert(vm);
assert(cell);
*cell += static_cast<uint8_t>(pc->operand);
VM_NEXT(vm, pc + 1, cell);
}op_inc(Vm*, ThreadedOp const*, unsigned char*):
// Load operand from operation
movzx eax, byte ptr [r13 + 8]
// Add operand to cell
add byte ptr [r14], al
// Load next handler
mov rax, qword ptr [r13 + 32]
// Increment instruction pointer
add r13, 32
// Jump to next handler
jmp raxDependencies
Bjit depends on xbyak for converting the generated assembly into executable machine code.
Future
There are still other optimizations that could be made. For example the ThreadedOp struct can be slimmed down by using a union, instead of storing 3 pointers/integers separately, as they are exclusive to each other, which would allow for more operations to fit on a cache line. We can implement vector scans for the scan loops in the interpreter, matching the jit compiler's avx2 version. For now however it will remain as it is, and has been a very educational project.
using Handler = VmResult(VM_CC *)(Vm *, const ThreadedOp *, uint8_t *);
struct ThreadedOp
{
Handler handler{nullptr};
size_t operand{0};
// The operation that will come after this one.
const ThreadedOp *target{nullptr};
// Optional extra metadata of operation.
const void *meta{nullptr};
};