Blitz

A pure-Rust compiler backend targeting x86-64, optimizing for generated code quality.

Blitz uses a custom e-graph for unified optimization and instruction selection, SSA-based chordal register allocation, and emits ELF64 relocatable object files. It targets only x86-64, which lets the optimizer natively understand addressing modes, flags, LEA tricks, and multi-output instructions without the abstraction penalty of multi-target backends.

Features

• Custom e-graph engine with union-find, hashcons, typed e-classes, and phased rewrite rules (algebraic simplification, strength reduction, constant folding, x86-64 instruction selection, addressing mode formation, LEA/flag fusion)
• Cost-based extraction with DAG sharing awareness and configurable optimization goals (latency, throughput, code size, balanced)
• SSA chordal register allocation with MCS ordering, optimal greedy coloring, aggressive coalescing, loop-aware spill selection, rematerialization, and per-block allocation with cross-block live range splitting
• Hand-written x86-64 encoder covering 70+ instruction forms (integer ALU, shifts, multiply/divide, MOV, LEA, branches, CALL/RET, CMOV, SETCC, SSE2 scalar FP, MOVQ, PUSH/POP, NOP) with correct REX, ModRM, SIB, and displacement encoding
• SystemV AMD64 ABI with register/stack argument passing, callee-saved preservation, 16-byte aligned frames, parallel copy sequentialization for phi elimination, and caller-saved clobber tracking across calls
• ELF64 object emission with .text, .symtab, .strtab, .shstrtab, .rela.text, and .note.GNU-stack sections
• Post-RA passes: peephole optimization (redundant MOV elimination, XOR-zero idiom, TEST-for-CMP, INC/DEC substitution, branch threading), NOP alignment for loop headers, branch relaxation (short/near form selection)
• Multi-block support with RPO ordering, fallthrough optimization, block parameter passing (SSA phi equivalent), and per-block register allocation with global liveness dataflow

Quick Start

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

// Build: 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 (func, egraph) = b.finalize().expect("finalize");

// Compile to object file
let obj = compile(&func, egraph, &CompileOptions::default(), None).expect("compile");
obj.write_to(std::path::Path::new("add.o")).expect("write");

// Link with C: cc main.c add.o -o test

See examples/basic.rs for a complete example with add, max, and sum-to-N functions, and examples/main.c for the C driver.

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

Architecture

Source IR (FunctionBuilder API, or C via the tinyc test frontend)
       |
       v
  [ Inlining ]  -- cost-based, bottom-up
       |
       v
  [ DCE 1 ]  -- unreachable block elimination
       |
       v
  [ Memory ]  -- store-to-load / load-to-load forwarding, dead store
       |          elimination (intra-block, alias-analysis driven)
       v
  [ LICM ]  -- loop detection, preheader insertion, invariant hoisting
       |
       v
  [ E-graph ]  -- unified saturation: algebraic simplification, strength
       |           reduction, constant folding, known-bits, distributivity,
       |           x86-64 instruction selection, addressing modes, LEA
       v
  [ Extraction ]  -- cost-based bottom-up DAG extraction
       |
       v
  [ DCE 2 ]  -- constant branch folding, unreachable blocks, dead loads
       |
       v
  [ Scheduling ]  -- list scheduler with register pressure heuristic
       |
       v
  [ Splitter ]  -- pressure-driven live-range splitting (remat / slot plan)
       |
       v
  [ Register Allocation ]  -- function-scope Chaitin-Briggs coloring
       |
       v
  [ Post-RA ]  -- phi elimination, peephole, NOP alignment,
       |           branch relaxation
       v
  [ Encoding ]  -- x86-64 binary encoder with label fixups
       |
       v
  [ ELF Emission ]  -- relocatable .o file

Testing

cargo test --all-targets --workspace   # 887 tests
bash tests/lit/run_tests.sh            # 382 tests

Coverage includes instruction encoding tests (byte-level verification), end-to-end tests (compile -> link with C -> run -> verify results), miscompile regression tests (signed overflow, spill correctness, phi permutations, nested control flow), unit tests for every pipeline phase, and FileCheck-style codegen tests over C sources in tests/lit/.

End-to-end tests require cc (gcc/clang) on PATH. They skip gracefully if unavailable.

Status

The compiler produces correct code for integer arithmetic, floating-point (F32/F64 via SSE2), conditional branches, loops with block parameters, function calls with up to 6+ register args and stack args, memory loads/stores with addressing mode fusion, and programs requiring register spilling.

crates/tinyc is a small C frontend used to feed the backend realistic input in tests. It is not a product; see ROADMAP.md for the project's goal, priorities, and non-goals.

License

MIT