Blitz

A compiler backend that targets x86-64, and nothing else, on purpose.

---

Blitz turns SSA-style IR into linkable ELF object files. It targets a single ISA so the optimizer can reason about addressing modes, flags, lea, and multi-output instructions directly, instead of laundering them through a target-neutral IR and hoping the peephole pass finds them again.

Optimization and instruction selection happen in one e-graph: algebraic rewrites, strength reduction, constant folding, and x86 instruction selection all compete in the same equality-saturation pass, and a cost model picks the winner. There is no separate "isel" phase to undo the optimizer's work.

Quick start

$ cargo add blitzgen

use blitzgen::compile::{CompileOptions, compile};
use blitzgen::ir::builder::FunctionBuilder;
use blitzgen::ir::types::Type;

// fn add(a: i64, b: i64) -> i64 { a + b }
let mut b = FunctionBuilder::new("add", &[Type::I64, Type::I64], &[Type::I64]);
let p = b.params().to_vec();
let sum = b.add(p[0], p[1]);
b.ret(Some(sum));

let obj = compile(b.finalize()?, &CompileOptions::default(), None)?;
obj.write_to(std::path::Path::new("add.o"))?;

Link it against C like any other object file:

$ cc main.c add.o -o demo && ./demo
42

The emitted add is what you would hope for: the addition folded into the address unit, no frame, no moves.

add:
    lea    (%rdi,%rsi,1),%rax
    ret

Use compile_module to put several functions in one object; inlining works across whatever you hand it. examples/basic.rs builds a handful of functions and examples/main.c drives them:

$ cargo run --example basic
$ cc examples/main.c output.o -o demo && ./demo

docs/ir.md is the guide to the IR itself: block parameters instead of phi nodes, pure versus effectful ops, branches, loops, memory, structs and tagged enums, with worked examples.

Code quality

The point of the project is the output, so it is measured rather than asserted, on 24 loop kernels that seed their data from argc — no reference compiler can fold one away and print the answer.

geomean over 24 kernels	vs gcc -O2	vs clang -O2
cycles  tests/run_perf.sh	x2.11	x2.70
instructions  run_codesize.sh --gap	x1.05	x0.72

Cycles is the ranking; instructions is a diagnostic. They disagree often enough that keeping both is the point. Laying a loop body after its header moved cycles 7.9% with the instruction count flat, because what changed is which branches are taken and no static count models that. Folding a stack slot into the addressing mode that reads it took 3% of the instructions off the loop corpus and moved cycles by nothing, so it was measured and shelved.

The clang instruction figure is not a victory lap: clang unrolls and vectorizes where blitz does not, which inflates its count on these kernels. Blitz has no vectorizer, and that is worth about 12% of the cycles gap — the rest is scalar codegen.

What's in it

• E-graph optimizer — union-find, hashcons, typed e-classes, phased rewrites, and cost-based extraction with DAG-sharing awareness. Optimization goals: latency, throughput, size, balanced.
• Function-scope register allocator — Chaitin-Briggs coloring with MCS ordering, optimistic coalescing, rematerialization, loop-aware spill choice, and pressure-driven live-range splitting across blocks.
• A second allocator, on purpose — -O0 puts every value in a frame slot and borrows registers one instruction at a time. Two implementations of one contract is what makes an allocation bug a disagreement the differential harness can see, rather than an answer both levels give.
• Hand-written encoder — 93 x86-64 instruction forms with correct REX, ModRM, SIB and displacement encoding, plus branch relaxation.
• SysV AMD64 ABI — register and stack arguments, callee-saved preservation, 16-byte frames, parallel-copy sequentialization for phi elimination.
• Optimization passes — inlining, SCCP, LICM, store-to-load and load-to-load forwarding, dead store elimination with offset-aware alias analysis, DCE, block layout, peephole, dead-instruction removal, loop-header alignment.

Pipeline

  IR  →  inline  →  DCE  →  memory  →  LICM  →  SCCP  →  e-graph  →  extract
                                                                       ↓
  ELF  ←  encode  ←  layout  ←  post-RA  ←  regalloc  ←  split  ←  schedule

The IR is dual: the e-graph holds pure values, the CFG holds effectful ops and control flow, and effectful ops reference pure values by e-class.

Two orders matter and they are not the same order. RPO is the dominance order and everything up to register allocation reads it; block layout is a greedy trace that puts a loop body directly after its header, so the header's conditional leaves the loop and the fallthrough enters it.

ROADMAP.md has the priorities, the non-goals, and — the part worth reading — what previous attempts measured, including the ones that lost.

Testing

$ cargo test --all-targets --workspace   # 1036 unit and codegen tests
$ bash tests/lit/run_tests.sh            # 594 FileCheck-style tests
$ bash tests/lit/run_diff.sh             # 357 comparisons: -O0 vs -O1 vs cc
$ bash tests/fuzz/run_fuzz.sh            # 1352 random UB-free programs
$ bash tests/fuzz/run_corpus.sh          # the saved failures, in seconds
$ bash tests/run_codesize.sh --check     # 1010 rows of code quality, vs baselines

Two harnesses check values rather than patterns, and they fail differently. run_diff.sh compiles every runnable test at both optimization levels and against a reference compiler, so it catches a pass that changes behavior and a bug that is equally wrong at both levels. run_fuzz.sh generates programs that are free of undefined behavior by construction and interprets them as it generates, so it knows the expected output before any compiler runs.

BLITZ_VERIFY=1 checks the IR at every pass boundary and the machine code after branch relaxation; BLITZ_VERIFY=strict also requires every e-class reference in the CFG to be canonical. BLITZ_PASSES=-licm and friends bisect the pass set against a miscompile.

End-to-end tests need cc on PATH and skip gracefully without it.

Status

Correct code for integer and floating-point arithmetic (F32/F64 via SSE2), branches, loops with block parameters, calls with register and stack arguments, memory access with addressing-mode fusion, and programs that need spilling.

crates/tinyc is a small C frontend that exists to feed the backend realistic input in tests. It is not a product.

License

Dual-licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE)
• MIT license (LICENSE-MIT)

at your option.

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this crate by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.