Anvil logo

Rust · zero dependencies · compiler backend

Compile it,
then prove it right.

Most build-your-own-compiler projects stop at the front end. Anvil is the backend. It takes an SSA intermediate representation and lowers it to a small target machine with only K physical registers, using a readable Chaitin-Briggs graph coloring register allocator with real spilling. Then it proves the result correct: a reference IR interpreter and the lowered target interpreter must return the same answer, even when a tiny K forces values onto the stack. Paste IR, pick K, and watch liveness, interference, coloring, spills, and the emitted assembly.

Open the playground View on GitHub

Anvil is a compiler backend you can watch: paste SSA IR, pick how many physical registers K to allow, and press Compile and check to see liveness, the interference graph, the register coloring and spills, and the lowered target code, verified against a reference interpreter.

How to use this playground

The page runs the whole backend in your browser and mirrors the Rust pipeline.

  • Edit the SSA IR, or click a preset to load an example program.
  • Set K, the number of physical registers. A small K forces values onto the stack as spills.
  • Give the function arguments, then press Compile and check.
  • Read the panels for liveness, interference, allocation, and target assembly. The banner reports whether the target result matches the reference interpreter.

runs fully client-side, the same passes as the Rust crate: parse, SSA destruction, liveness, interference, Chaitin-Briggs coloring, spilling, lowering, and the round-trip check

Liveness live-in and live-out per block, phi-free

Interference graph who cannot share a register

Allocation coloring and spills at K

Target assembly the lowered code the target machine runs


  






  
One equation is the whole test

  
Anvil ships two interpreters: an oracle that runs the SSA over unlimited virtual registers, and a target interpreter that runs the lowered program over only K physical registers plus a stack of spill slots. For every program, at K=2, K=3, and a K large enough to need no spilling, Anvil asserts they agree.

  
# the single invariant that validates regalloc, spilling, phi elimination, and lowering
interp_ir(program, args) == interp_target(lower(regalloc(program, K)), args)

# sum of 1..n at K=2, where register pressure forces spilling to the stack
$ anvil check sum.ir --regs 2 100
IR interpreter:     5050
target interpreter: 5050
registers: 2, spills: 7, slots: 7
OK: results match

  
If those two ever disagree, the backend is wrong, and the page shows it in the banner. That same check runs here in your browser on every compile, so the playground is not a demo of the pipeline, it is the pipeline, holding itself to the equation.






  
How it differs

  
Anvil sits between the tutorials that never reach a backend and the production backends that are correct but too large to read.

  

    
Build-your-own-compiler tutorials
Most stop at the front end: a parser, an AST, maybe a tree-walking interpreter. Register allocation, the hard part of a backend, is the part they skip.

    
Production backends (LLVM, Cranelift)
Real graph coloring or linear scan allocators, trusted through enormous test corpora. Correct, but the allocator is buried in a large codebase and hard to read end to end.

    
Anvil
A readable Chaitin-Briggs graph coloring allocator with real spilling, in one small Rust crate with zero dependencies, and a round-trip oracle that proves each lowering correct instead of arguing it. The same pipeline runs here in the browser.

  






  
The passes that matter

  
The pipeline, one small module each

  
SSA IR flows through these stages to target code. Each is a separate module in the crate and runs identically in the playground.

  

    
parse Text IR
Parses the SSA text form into blocks, instructions, and terminators, and round-trips with the printer so parse then print then parse is identical.

    
validate Well-formed SSA
Checks each value is defined once, every use is dominated by its definition, and each phi has exactly one entry per control flow predecessor.

    
ssa Phi elimination
Turns phi nodes into copies in predecessors, splits critical edges so a copy has a safe home, and sequences parallel copies so a swap cycle does not clobber.

    
liveness Backward dataflow
Iterates live-in and live-out sets over the control flow graph to a fixed point, so allocation knows which values are alive at the same time.

    
interference Who cannot share
Two values interfere when one is live at the other's definition. A copy is the exception: source and destination hold the same value, so they may share a register.

    
regalloc Chaitin-Briggs
Build, simplify low-degree nodes onto a stack, optimistically push a potential spill, select colors, and on an actual spill insert reload code and run again.

    
lower Target code
Walks the fully colored IR and maps each instruction to the small target machine, replacing every virtual register with its color and dropping same-register copies.

    
oracle Two interpreters
The IR interpreter over unlimited virtual registers and the target interpreter over K registers plus spill slots must return the same value, on every program and input.

  






  
Use it

  
Anvil is a Rust crate with a small command line front end. The surfaces below are the real ways to drive it.

  

    
CLI: run
Interpret the IR directly with the reference interpreter and print the result, optionally with function arguments.

    
CLI: regalloc
Show liveness, the interference graph, the coloring, and the spills at a chosen number of registers K.

    
CLI: emit
Print the lowered target assembly the small target machine runs after allocation.

    
CLI: check
Run the round-trip oracle at K and report OK when the two interpreters agree or a mismatch when they do not.

    
Library crate
The pipeline is a lib crate (ir, parse, ssa, liveness, interference, regalloc, lower, target), so each pass can be called on its own.

    
Test suite
The round-trip oracle runs across the test programs at K=2, K=3, and a large K, asserting spilling really happens at K=2 and not at large K.

  

  
# build, test, and lint the backend (Rust, zero dependencies)
cargo build
cargo test
cargo clippy --all-targets

# interpret the IR and print the result, optionally with arguments
anvil run      program.ir 5

# show liveness, interference, coloring and spills at K registers
anvil regalloc program.ir --regs 2

# print the lowered target assembly
anvil emit     program.ir --regs 2

# run the round-trip oracle and report OK or mismatch
anvil check    program.ir --regs 2 100