backend-lang is the LexerSketch native backend: it takes an ir-lang 2.0 module through instruction selection, SSA register allocation with exact stack maps, and emission to x86-64 machine code through isa-lang, producing code, symbols, call-site records, data, and the relocations a linker needs. Underneath sit a machine IR over virtual and physical registers, target descriptions that state everything the backend needs to know about an ISA as data, SysV and Win64 calling conventions and frame layout, and a parallel-move resolver. It replaces rented backends (Cranelift, LLVM) in the LexerSketch toolchain; nothing on its path is a system assembler, linker, or C library.
This release compiles the integer, control-flow, memory, call, and checked-arithmetic subset of ir-lang 2.0.0-alpha.3, OPS v2 included: every OPS integer operation under every policy ir-lang carries (with check error edges), integer pow and shift = saturate, float pow (a call to the runtime's ls_pow, bit-identical to every other tier), comparisons, conversions, loads and stores, stack slots, field and element addressing, globals, block memory operations, calls and tail calls under SysV and Win64, switches as jump tables or compare trees, GC safepoints with stack maps (hand-written or inserted by ir-lang's insert_statepoints), and invoke with landing pads (no unwind tables yet). Floats move as bit patterns in general-purpose registers; float arithmetic other than pow waits on isa-lang's SSE forms, AArch64 on its AArch64 forms; anything not selected is refused with an error naming what it waits on (see the roadmap). Compiled code is checked against ir-lang's reference interpreter on random programs, in an x86-64 interpreter on every platform and natively on x86-64 Linux and Windows.
MSRV is 1.85+ (Rust 2024 edition). no_std-compatible (needs only alloc), #![forbid(unsafe_code)], two dependencies, both from the family: isa-lang 0.2 and ir-lang =2.0.0-alpha.3 (pinned exactly while it is a pre-release; modules must be built with that version, re-exported as backend_lang::ir_lang).
Status: pre-1.0. The public API is designed across the 0.x series and frozen at1.0.0, after jit-lang 2.0 and aot-lang 2.0 run on it. SeeCHANGELOG.md.
compiletakes an ir-langModuleto aCompiled: the machine code of every function back to back, each function's offset, frame, and call-site records (return address, stack map, landing pad), the relocations against symbols defined elsewhere, and the module's data. Internal calls are already resolved.iselselects one ir-lang function into MIR on virtual registers;regallocassigns physical registers and stack slots.- A
Functionis blocks of target instructions. Instructions name virtual registers (each typed by a register class), physical registers, stack slots, and other functions by symbol. Values cross edges as block parameters: a branch passes arguments, and the target's parameters receive them all at once. - A
Targetdescribes an ISA as data: its registers, its register classes, and its instructions, each with operand rules (definitions, uses, two-address ties, accepted shapes and immediate ranges) and the registers it reads, writes, and clobbers without naming them (idivreadsrdx:rax, a shift byclreadsrcx, flag producers define the flags register). - An
Abiis a calling convention: argument and return registers, callee-saved registers, stack alignment, shadow space, red zone, and stack probing.layout_frameturns a function's slots and saved registers into offsets and a prologue/epilogue plan. - The
MoveResolverturns any parallel copy into moves and swaps a machine can execute one at a time. - The
Emitterencodes physical-register functions through isa-lang, resolving every edge's parallel copy on the way.
What it guarantees, and how each guarantee is checked:
| Guarantee | How it is held |
|---|---|
| Compiled code computes exactly what the IR specifies, results and trap codes alike. | Random valid ir-lang programs (every integer op under every policy, check error edges, loops whose back edges permute their parameters, dense and sparse switches, slots and globals through field and element addresses, block memory operations, direct, indirect, and tail calls, high register pressure) are compiled and run against ir-lang's reference interpreter: in the x86-64 test interpreter under SysV and Win64 on every platform, and natively in-process on x86-64 Linux and Windows. Arguments arrive with junk above their width; callee-saved registers and the stack pointer are checked after every return. |
| Every OPS integer operation, on every type, under every policy, OPS v2 included. | Each op × type × policy on the OPS edge values (0, 1, -1, MIN, MAX, MIN+1, MAX-1, shift amounts around the width) compiled and compared with the interpreter, in the test interpreter under both conventions and natively; pow (wrap, trap, error) and saturating shifts also with every edge value as a constant operand (the unrolled and folded paths), and a negative pow exponent reaching the check's error edge with code 6 under every policy. |
Float pow is ir-lang's ls_pow, bit for bit. |
f64 and f32 pow over signed zeros, infinities, NaNs (payloads included), subnormals, odd and even integers, and random magnitudes, with run-time and constant exponents, compared bit for bit with ls_pow and the interpreter, in the test interpreter and natively. |
| SSA from ir-lang's builders compiles as written. | Random programs built through the variables API (loop headers sealed after their back edges, joins, unassigned reads, checked OPS v2 operations whose error edges assign variables, calls) run against the interpreter; programs whose GC lists insert_statepoints added run under the moving collector (and natively), and invokes with inserted statepoints run through the minimal unwinder. |
| Hostile and huge inputs never panic; the budgets hold. | Any OPS v2 operation with any constant or run-time operands compiles and terminates; a 300,000-instruction function, 20,000 nested branches, a 2,000-parameter join, and 10,000 pow loops compile; the live-set budget is exact to the entry and spill rounds never count against it; hostile MIR is rejected with the same error verify_ssa gives. |
| The register assignment is interference-free. | On every function selected from random programs and on hand-built ones with cycles, ties, and fixed registers, an independent liveness checks point by point: no two live values share a register, no value is live across an instruction that writes its register, block parameters avoid each other and every live-in value. |
| Stack maps are exact. | Every safepoint's recorded root slots are exactly its GC list. A moving collector in the tests walks the real machine stack by the call-site records and frame layouts, moves every object a stack map names, and poisons the old copies, so a missed root or a missed reload changes the result. |
| Parallel copies are exact: any permutation, cycles of every length, fan-out, registers and stack slots mixed, immediates. | Property tests run the resolver against a parallel-assignment reference over random copies built from explicit cycles, chains, fan-out, and immediates; every step is checked to be one x86-64 can execute; every location that is not a destination is checked unchanged. Cycles of every length from 2 to 14 registers and to 64 slots; a 100,000-slot permutation. |
| Moves are minimal under the resolver's rules. | For register-only copies, the step count is checked equal to the minimum: one per copy, k - 1 swaps per k-cycle (or k + 1 moves without swaps), nothing extra for a cycle whose value is also copied out of it. |
| Emitted edges perform their parallel copy. | Random jump and branch edges over all fourteen allocatable registers and up to six stack slots are emitted, executed by an x86-64 interpreter in the test suite, and checked location by location. |
| Every instruction row encodes, and its implicit operands agree with isa-lang. | 913 operand shapes over every opcode are emitted and decoded back; the flags each row declares as read and written are checked against isa-lang's flag effects, and fixed registers against isa-lang's forms. |
| Frames are aligned and disjoint, under SysV and Win64. | Property tests over random slots, saved registers, calls, and outgoing areas simulate each prologue: the stack is 16-aligned at calls, and slots are aligned, disjoint, and clear of the saved registers and the outgoing area. |
| MIR → isa-lang → object-lang → a running process. | Three hand-built programs (a Fibonacci loop with parallel-copy edges, recursive factorial across two functions, and a mix of the instruction table with an indirect call) are wrapped into static ELF executables and run on Linux x86-64 with their exit status checked, and run in the interpreter on every platform. |
| No panics on hostile construction. | Random opcodes with random valid, foreign, and ill-shaped operands are built, verified, printed, laid out, and emitted; every failure is an error value. |
[dependencies]
backend-lang = "0.4"Without the standard library:
[dependencies]
backend-lang = { version = "0.4", default-features = false }compile is the one-call path: an ir-lang module in, x86-64 machine code with symbols and relocations out.
use backend_lang::Options;
use ir_lang::{Linkage, Module, Overflow, Signature, Type};
// fn add(x: i64, y: i64) -> i64 { x + y }
let mut m = Module::new("demo");
let sig = Signature::new(&[Type::I64, Type::I64], &[Type::I64]);
let f = m.declare_function("add", &sig, Linkage::Export)?;
let mut b = m.build(f)?;
let (x, y) = (b.param(0)?, b.param(1)?);
let s = b.add(x, y, Overflow::Wrap)?;
b.ret(&[s])?;
let c = backend_lang::compile(&m, &Options::sysv().with_frame_pointer(false))?;
// add rdi, rsi; mov rax, rdi; ret
assert_eq!(c.code(), [0x48, 0x01, 0xF7, 0x48, 0x89, 0xF8, 0xC3]);
assert_eq!(c.exports(), ["add"]);
# Ok::<(), Box<dyn std::error::Error>>(())A check terminator branches to its error edge with the OPS error code; a trap policy calls the runtime's trap handler, which the module imports by name:
use backend_lang::Options;
use ir_lang::{BinaryOp, BlockArg, BlockCall, DivZero, InstData, Linkage, Module, Overflow, Policy, Signature, Type};
let mut m = Module::new("demo");
let sig = Signature::new(&[Type::I32, Type::I32], &[Type::I32]);
let f = m.declare_function("safe_div", &sig, Linkage::Export)?;
let mut b = m.build(f)?;
let (x, y) = (b.param(0)?, b.param(1)?);
let ok = b.create_block(&[Type::I32])?;
let bad = b.create_block(&[Type::U32])?;
let policy = Policy::overflow(Overflow::Wrap).with_div_zero(DivZero::Error);
let div = InstData::Binary { op: BinaryOp::Div, policy, args: [x, y] };
b.check(
div,
BlockCall::with_args(ok, &[BlockArg::Result(0)]),
BlockCall::with_args(bad, &[BlockArg::ErrorCode]),
)?;
b.switch_to(ok)?;
let q = b.block_param(ok, 0)?;
b.ret(&[q])?;
b.switch_to(bad)?;
let minus_one = b.iconst(Type::I32, -1)?;
b.ret(&[minus_one])?;
let c = backend_lang::compile(&m, &Options::win64())?;
assert!(c.imports().is_empty()); // nothing traps: no runtime call needed
assert!(c.function("safe_div").is_some());
# Ok::<(), Box<dyn std::error::Error>>(())emit is the lower-level path: a function on physical registers in, x86-64 machine code out.
use backend_lang::mir::{Effects, Function};
use backend_lang::x86_64::{op, SYSV, RAX, RDI};
// fn double(x) -> x + x under SysV: x arrives in rdi, the result leaves in rax.
let mut f = Function::new("double", &SYSV);
let entry = f.block()?;
f.add_param(entry, RDI.into())?;
f.push(entry, op::MOV64, &[RAX.into(), RDI.into()])?;
f.push(entry, op::ADD64, &[RAX.into(), RAX.into(), RDI.into()])?;
f.push_with(entry, op::RET, &[], Effects::new().uses(&[RAX]))?;
f.omit_frame_pointer();
let code = backend_lang::emit(&f)?;
// mov rax, rdi; add rax, rdi; ret
assert_eq!(code, [0x48, 0x89, 0xF8, 0x48, 0x01, 0xF8, 0xC3]);
# Ok::<(), Box<dyn std::error::Error>>(())A loop whose back edge swaps its two values. The resolver sees the 2-cycle and emits one xchg; a cycle through memory would borrow a register instead:
use backend_lang::mir::{Effects, Function, Operand};
use backend_lang::x86_64::{self, op, SYSV, RAX, RCX};
use isa_lang::x86_64::{decode_all, Cond};
let mut f = Function::new("swap_loop", &SYSV);
f.omit_frame_pointer();
let (entry, head, exit) = (f.block()?, f.block()?, f.block()?);
f.add_param(head, RAX.into())?;
f.add_param(head, RCX.into())?;
let start = f.block_call(head, &[Operand::Imm(1), Operand::Imm(2)])?;
f.push(entry, op::JMP, &[start.into()])?;
f.push(head, op::CMP64, &[RAX.into(), Operand::Imm(2)])?;
let again = f.block_call(head, &[RCX.into(), RAX.into()])?; // swapped
let done = f.block_call(exit, &[])?;
f.push(head, op::JCC, &[x86_64::cond(Cond::Ne).into(), again.into(), done.into()])?;
f.push_with(exit, op::RET, &[], Effects::new().uses(&[RAX]))?;
let code = backend_lang::emit(&f)?;
let text: Vec<String> = decode_all(&code)
.filter_map(Result::ok)
.map(|(_, d)| d.inst().to_string())
.collect();
assert!(text.contains(&"xchg rax, rcx".to_string()));
# Ok::<(), Box<dyn std::error::Error>>(())use backend_lang::mir::{Function, SlotKind};
use backend_lang::target::abi::{ArgClass, ArgLoc};
use backend_lang::x86_64::{SYSV, WIN64, RCX, RDI, XMM1};
let mut locs = Vec::new();
SYSV.assign_args(&[ArgClass::Int, ArgClass::Float, ArgClass::Float], &mut locs);
assert_eq!(locs[0], ArgLoc::Reg(RDI));
assert_eq!(locs[2], ArgLoc::Reg(XMM1));
locs.clear();
let outgoing = WIN64.assign_args(&[ArgClass::Int; 6], &mut locs);
assert_eq!(locs[0], ArgLoc::Reg(RCX));
assert_eq!(locs[4], ArgLoc::Stack(32)); // above the 32 bytes of shadow space
assert_eq!(outgoing, 48);
// A SysV leaf with a small frame keeps it in the red zone below rsp.
let mut leaf = Function::new("leaf", &SYSV);
let slot = leaf.stack_slot(SlotKind::Local { size: 16, align: 8 })?;
let frame = leaf.frame_layout()?;
assert!(frame.uses_red_zone());
assert!(frame.slot_offset(slot).unwrap() < 0);
# Ok::<(), Box<dyn std::error::Error>>(())Runnable programs in examples/:
| Example | What it shows |
|---|---|
compile |
The Tier-1 path: a module with a loop, a checked division whose error edge returns a sentinel, and a caller, compiled for SysV; each function's allocated MIR and disassembly. cargo run --example compile |
emit |
Build a loop in MIR, print it, emit it, and disassemble the result. cargo run --example emit |
ops_v2 |
OPS v2: a checked signed pow (code 6 for a negative exponent), a saturating shift, and a float pow that imports the runtime's ls_pow; the disassembly of each. cargo run --example ops_v2 |
moves |
The parallel-move resolver on a copy mixing a register rotation, fan-out to a slot, a slot swap, and an immediate, with and without a free register. cargo run --example moves |
Library-only numbers (no process start, no object file) on Windows x86_64, Rust stable, release profile. The machine was shared with other builds during every measurement, so the 0.4 numbers come in pairs: 0.4 and 0.3 run alternately in the same session (the ignored timing tests, ten runs each, three compiles per run), reported as the median and the best run. Criterion figures for the rest are from one cargo bench run in the same session.
| Measurement | 0.3 (same session) | 0.4 |
|---|---|---|
compile of the 100,000-instruction function (validate, select, allocate, emit), median |
~104.5 ms (~0.96 M IR instructions/s) | ~76.2 ms (~1.31 M IR instructions/s) |
| The same, best run | ~85.7 ms (~1.17 M/s) | ~65.9 ms (~1.52 M/s) |
| Register allocation alone on it, median / best | ~70.7 / ~56.3 ms | ~45.1 / ~35.8 ms |
| Selection / emission alone, median | ~14.8 / ~18.4 ms | ~14.7 / ~19.1 ms (unchanged code) |
| The high-pressure function (45,833 IR instructions, 4,096 values spilled): select + allocate + emit, median / best | ~184.5 / ~154.7 ms (~0.30 M/s best) | ~129.8 / ~103.1 ms (~0.44 M/s best) |
The 1 M IR instructions/s target is met on the realistic benchmark (compile_100k) by the median and by 23 of 30 compiles in that loaded session (0.3: 11 of 30; the slowest 0.4 run took ~147 ms), and not on the high-pressure one (compile_pressure), whose allocation cost is its live sets (dozens of values live through thousands of blocks) and whose selection and emission alone take about 36 ms; live-range splitting with interval liveness is v0.5.0 work (ROADMAP).
Criterion benchmark (cargo bench --bench bench) |
What it measures | 0.4 |
|---|---|---|
mir_100k/build, /verify, /emit, /print |
A 100,000-instruction MIR function: build it, verify it, emit it (frame, every edge's parallel copy, encoding, relaxation), print it. | ~5.3 / ~1.9 / ~11.8 / ~7.5 ms |
moves/permutation/4, /100000 |
Random permutations through the resolver. | ~145 ns / ~12.6 ms |
moves/edges_100k_x4 |
100,000 four-move edges through one reused resolver. | ~17.5 ms |
quality/native vs quality/interp |
Compiled code against ir-lang's interpreter: recursive fib(25), a 1,000,000-iteration loop, a 1 KiB memory kernel ×20. |
0.29 ms vs 49 ms; 0.30 ms vs 84 ms; 9.6 µs vs 2.4 ms |
Everything is linear except one sort when the resolver numbers a copy's locations (O(n log n)) and liveness, whose cost is the size of the live sets (budgeted, computed once per function); a reused resolver allocates nothing once it has seen its largest copy.
cargo bench --bench bench- Narrow integers stay narrow only where it matters. An
i8/i16/i32value lives in the low bits of a 64-bit register with the upper bits unspecified, exactly as x86-64's 32-bit instructions leave them; wherever the upper bits matter (comparisons, division, right shifts, overflow checks, widening, switch values, array indices, call boundaries) it is extended first by its signedness.boolis always exactly 0 or 1. - Division never faults. Zero and
MIN / -1are tested beforeidivruns, so every OPS policy (wrap, trap, error edge) is honoured instead of a processor exception. - Coloring without an interference graph. In strict SSA, interfering values have one definition dominating the other, so giving each value, in dominance order, a register no live value holds is a correct coloring. Spilling is spill-everywhere with rematerialization; constants and addresses are recomputed instead of stored.
- Liveness once, updated per spill round. Spill code reads and writes no physical register, a spilled value leaves every live-in set, and a reload temporary lives only just before its user, so a round's effect on liveness is known exactly: the allocator updates the analysis instead of recomputing it, and a round costs one coloring walk.
- Floats as bit patterns,
powfrom the runtime. Until isa-lang encodes SSE, a float lives in a general-purpose register as its bits; moving it needs nothing more. Floatpowis a call to the runtime'sls_pow(ir-lang's routine, never a platform libm): compilingls_powhere would mean emulating its IEEE double arithmetic in integer code, thousands of instructions per call, to be thrown away when SSE arrives, and the call is bit-identical by construction. - Stack maps fall out of the IR. ir-lang's statepoints list every reference live across a safepoint (IR.md §9), so the backend stores exactly those into root slots before the call and reloads the relocated values after it. No reference is ever in a register while a collector runs, and no backend liveness analysis of references is needed.
- Block parameters, not phi nodes. The same information as phis, kept on the edge where it is used: each edge's parallel copy is written down on that edge. ir-lang already uses block parameters, an SSA register allocator resolves each edge with the same resolver, and there is no phi list to keep in sync with predecessor order.
- Implicit operands are data. isa-lang 0.2 describes each form's explicit operands only. A register allocator needs every register an instruction touches, so this crate's instruction table records implicit uses, definitions, and clobbers per row, and calls and returns carry their ABI registers per instruction. The flags are a physical register: producers define it, consumers use it, and an instruction that may leave some flags unchanged (
inc, a shift by zero) also uses it, so a flag value never appears to come from an instruction that might not have produced it. - The stack pointer does not move in the body. Slots have fixed offsets from it; stack arguments are stores to
[rsp + offset];pushandpopbelong to prologues and epilogues only. - Edges split themselves. A conditional branch whose taken edge carries moves branches on the negated condition around them, so critical edges never need an extra block.
- No rented parts. Encoding is isa-lang's and object files are object-lang's; both are this family's own.
cargo test # unit + integration + property + doctests
cargo test --no-default-features # no_std + alloc
cargo clippy --all-targets --all-features -- -D warnings
cargo bench --bench benchThe integration tests carry a small x86-64 interpreter (tests/common) that executes the bytes the emitter produces, written against isa-lang's decoder alone, so emitted programs and edges are checked on every platform, and a random generator of valid ir-lang programs (tests/common/irgen.rs) whose compiled code is compared with ir-lang's reference interpreter (tests/differential.rs); on x86-64 Linux and Windows the same programs also run natively in-process (tests/native.rs), and on Linux tests/executable.rs and tests/link.rs run static executables as real processes. tests/variables.rs builds programs through ir-lang's variables API, tests/stackmaps.rs runs a moving collector over statepoints (hand-written and inserted by ir-lang), and tests/hostile.rs holds the hostile and huge inputs. BACKEND_DIFF_CASES=n sets the number of programs per differential sweep. Every rust example in this README and in docs/API.md is compiled and run as a doctest.
See REPS.md for the engineering standards every change is held to, dev/DIRECTIVES.md for the definition of done, and dev/ROADMAP.md for the roadmap. Before a PR: cargo fmt --all, cargo clippy --all-targets --all-features -- -D warnings, and cargo test --all-features must be clean.
Licensed under either of
- Apache License, Version 2.0 — LICENSE-APACHE
- MIT License — LICENSE-MIT
at your option.