Add a Basic JIT to Your VM

Topic Overview

Template JIT Basics

Interpretation pays dispatch tax every opcode. A template JIT copies pre-built machine-code snippets into an executable buffer, patches immediates, and jumps to native code. LuaJIT and V8 sit farther along this spectrum; template JIT is the entry point.

x86-64 Emission

Each bytecode maps to a native template:

• `mov rax, imm64`: `48 B8` plus 8 immediate bytes
• `add rax, rbx`: `48 01 D8`
• `ret`: `C3`

Executable pages come from `mmap` with `PROT_READ | PROT_WRITE | PROT_EXEC`, or `mprotect` after writing. Modern OS hardening (W^X on iOS, SELinux policies) restricts this, which is why browser JITs need special entitlements.

A switch-based interpreter might spend 5-10 cycles per opcode on fetch and dispatch. JIT'd straight-line code runs at near-native speed for hot sequences.

For example, `PUSH 10; PUSH 20; ADD` becomes a few `mov` instructions and one `add` without a central dispatch loop.

Design Notes

Flush the instruction cache after writing machine code on architectures that require it. Template JIT is not peak performance, but it teaches the exact steps production engines hide inside megabytes of optimization logic.

For This Exercise

This exercise asks you to emit x86-64 machine code for a short bytecode program using `mmap`. You will implement byte emitters and demonstrate calling the generated function from C.

Your Task

A template JIT translates each bytecode instruction into a fixed snippet of machine code and concatenates the snippets. Write the code generator for x86-64: map the VM's operand stack onto the hardware stack (push/pop/[rsp]), emit the exact instruction bytes, verify stack depths statically before emitting anything, and optionally run a constant-folding peephole first. The generated function returns the final value in rax. A reference interpreter computes the expected result, so the program runs anywhere.

Input

cCopy
Loading…

Templates

Rules

• Folding (when on): repeatedly replace PUSH a; PUSH b; ADD|SUB|MUL with PUSH (a op b), using 64-bit wrap-around, but only when the result fits in int32. Report folded K constant operation(s).
• Static checks, in order over the (folded) program:
  • error: OP at I would underflow the stack
  • error: HALT must leave exactly one value on the stack (found D)
  • error: code after HALT
  • error: program must end with HALT
  • On any error nothing is emitted.
• Output: each bytecode instruction on its own line (two-space indent), then its bytes (4-space indent, each byte as %02x , padded to 7 byte slots) and the assembly. Finally N bytes of machine code, max stack depth D, result R, where R is computed with 64-bit wrap-around.
• Load errors: unsupported by the JIT: X and PUSH needs a 32-bit immediate.

Output

cCopy
Loading…

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Emit bytes from per-opcode templates into a buffer, and choose the short push imm8 encoding whenever the value fits.
2. Verify the stack depth before emitting code. Generated machine code has no runtime checks.

Hidden tests cover a negative immediate, a large immediate, fold results that do not fit in 32 bits (left unfolded), -128 and 128 at the imm8 boundary, stack underflow, a missing HALT, extra values at HALT, and code after HALT.