CompilersJIT CompilationMedium

Implement Register Allocation for JIT

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

~45 minutes JIT Compilation Ready to learn

Topic Overview

Fast Allocation for JIT Latency

JIT compilers cannot spend seconds on graph coloring. HotSpot's C1 uses linear scan; baseline JITs may use fixed register assignments or none at all. Allocation quality matters less than compile speed for tier-one code.

Linear Scan in JIT

Sort live intervals, assign registers in one pass, spill the rest. Skip expensive coalescing. Reuse allocation across similar bytecode patterns with templates.

c
Loading…

Tier-one: few registers, many memory operands
Tier-two: better allocation after profiling
Register pinning for calls per ABI
Deopt maps need register-to-slot mapping

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 implement register allocation tailored for JIT compilation speed. This exercise asks you to assign registers with a fast linear scan rather than full graph coloring.

Implementation Task

Your Task

Allocate registers for a JIT's expression code with the Sethi. Ullman algorithm: label every node with the number of registers it needs, evaluate the more demanding subtree first so the fewest registers are live, and spill to memory only when the machine truly runs out.

Input

The first line is registers K (K ≥ 2). Then one expression per line over variables a: z, + - * / (usual precedence, left-associative) and parentheses.

Labels (Ershov numbers)

A leaf (variable) has label 1: it must be loaded into a register.
An operator whose children have labels L and R has label L + 1 if L == R, otherwise max(L, R).

Code generation

gen(n, b) computes node n into register Rb, using only Rb … RK (so avail = K - b + 1 registers):

Case	Code
leaf `x`	`LD Rb, x`
both children have label ≥ `avail` (spill)	`gen(right, b)`; `ST tN, Rb`; `gen(left, b)`; `LD Rb+1, tN`; `OP Rb, Rb, Rb+1`
label(left) ≥ label(right)	`gen(left, b)`; `gen(right, b+1)`; `OP Rb, Rb, Rb+1`
otherwise	`gen(right, b)`; `gen(left, b+1)`; `OP Rb, Rb+1, Rb`

OP is ADD SUB MUL DIV and the operands are always left, right. Spill temporaries t1, t2, … are numbered per expression; a spilling node reserves its number before generating its children (so an outer spill is t1 even if an inner spill's store is emitted first). Code starts with gen(root, 1).

Output

For each expression:

c
Loading…

U is the highest register number used.

Example

Input:

c
Loading…

Output:

c
Loading…

Requirements

One labelling pass (post-order) and one recursive generator.
Keep the left/right operand order in the emitted instruction regardless of which subtree was evaluated first.

Hidden tests use K = 2 so balanced trees must spill, right-heavy trees that must evaluate the right side first, and division/subtraction where operand order matters.