CompilersJIT CompilationMedium

Understand and Implement a Basic JIT Compiler

Master the fundamental concepts of jit compilation through this focused micro-challenge.

~45 minutes JIT Compilation Ready to learn

Topic Overview

Compile at Runtime

JIT compilers generate machine code in memory and execute it immediately. JVM HotSpot, JavaScriptCore, and LuaJIT profile hot loops, compile them natively, and jump from interpreter to generated code. JIT trades compile latency for peak performance.

Interpreter to Native Handoff

Profile bytecode or AST execution. When a function gets hot, lower IR to machine code into an executable buffer (mmap with PROT_EXEC). Patch call sites to jump to generated code.

c
Loading…

Executable memory requires W^X awareness: write then mprotect
Deoptimization returns to interpreter on guard failure
OS must flush instruction cache after patching (ARM)
Security: JIT surfaces are attack targets

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will understand and implement a basic JIT compiler. This exercise requires allocating executable memory, emitting simple machine code, and transferring control from an interpreter stub to generated code.

Implementation Task

Your Task

Write the code generator of a tiny JIT compiler: turn an arithmetic expression in one variable x into the exact x86-64 machine code bytes of a function long f(long x), and compute what that function returns for the given inputs. (A real JIT would now mmap the bytes executable and call them; here the grader checks the bytes, so the encoding must be exact.)

Input

One function per line:

c
Loading…

EXPR uses x, non-negative integer literals (< 2³¹), + - * (usual precedence, left-associative) and parentheses. After | come the argument values to evaluate it at.

Code generation (a stack machine on the hardware stack)

System V passes x in rdi and expects the result in rax. Generate code by a post-order walk of the expression tree:

Node	Bytes	Assembly
literal `n`	`48 c7 c0` + `n` as 4 little-endian bytes, then `50`	`mov rax, n` · `push rax`
`x`	`57`	`push rdi`
`a + b`	code(a), code(b), `59 58 48 01 c8 50`	`pop rcx` · `pop rax` · `add rax, rcx` · `push rax`
`a - b`	code(a), code(b), `59 58 48 29 c8 50`	… `sub rax, rcx` …
`a * b`	code(a), code(b), `59 58 48 0f af c1 50`	… `imul rax, rcx` …
function end	`58 c3`	`pop rax` · `ret`

Output

For each line:

c
Loading…

D is the largest number of values ever pushed at once.

Example

Input:

c
Loading…

Output:

c
Loading…

Requirements

Parse into a tree, then emit bytes into a growable buffer with one recursive function.
Evaluate by walking the same tree (or by interpreting your own byte sequence).

Hidden tests cover subtraction order (a - b pops b first), large literals, deep nesting, and negative results.