Crate backend_lang

Expand description

§backend_lang

The LexerSketch native backend: instruction selection from ir-lang 2.0, SSA register allocation with exact stack maps, and emission to x86-64 machine code through isa_lang, on top of 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. No Cranelift, no LLVM, no system assembler.

This release (0.4) compiles the integer, control-flow, memory, call, and checked-arithmetic subset of ir-lang 2.0.0-alpha.3, OPS v2 included (integer and float pow, shift = saturate), and SSA built by ir-lang’s variables API and statepoint insertion. Floats are carried as bit patterns in general-purpose registers (constants, bitcast, loads, stores, select, edges), and float pow calls the runtime’s ls_pow; other float arithmetic waits on isa-lang’s SSE forms, AArch64 on its AArch64 forms, and unwind tables on object files that carry them. Each is refused with an error that says so, never miscompiled.

§Quick start

compile is the one-call path: an ir-lang module in, 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))?;
// SysV: x arrives in rdi, y in rsi; the sum leaves in rax.
// add rdi, rsi; mov rax, rdi; ret
assert_eq!(c.code(), [0x48, 0x01, 0xF7, 0x48, 0x89, 0xF8, 0xC3]);
assert_eq!(c.function("add").map(|f| f.offset()), Some(0));
assert_eq!(c.exports(), ["add"]);

emit is the lower-level path: a MIR function on physical registers (written by hand, or after regalloc::allocate) in, machine code out.

use backend_lang::mir::{Effects, Function};
use backend_lang::x86_64::{op, SYSV, RAX, RDI};

// fn double(x) -> x + x, 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]);

§The pieces

compile, Options, Compiled: the whole pipeline for a module.
isel: instruction selection, one ir-lang function to MIR on virtual registers.
regalloc: SSA register allocation, virtual registers to physical registers and stack slots.
mir: Functions of Blocks of target instructions, with typed virtual registers, stack slots, symbols, explicit implicit operands, call-site records, and a deterministic text form.
target: the Target description (registers, classes, instructions with their operand rules and implicit operands), abi (argument and return registers, callee-saved sets, stack alignment, shadow space, red zone, probing), and frame (frame layout and prologue/epilogue plans).
moves: the parallel-move resolver every parallel copy goes through.
x86_64: the x86-64 description, SysV and Win64, and the Emitter.

§Block parameters, not phi nodes

Values cross control-flow edges as block parameters: a branch passes arguments, and the target block’s parameters receive them all at once. This is the same information as phi nodes, kept at the edge where it is used: the parallel copy a phi implies on each incoming edge is written down on that edge. The register allocator assigns parameters and arguments independently and resolves each edge with the parallel-move resolver; ir-lang uses block parameters too, so instruction selection maps them one to one; and there is no per-block phi list to keep in sync with predecessor order.

§Guarantees

Compiled code computes what the IR says. Random ir-lang programs (every integer operation under every policy, OPS v2’s pow and saturating shifts, float pow, error edges, loops, switches, memory, calls, tail calls), programs built through ir-lang’s variables API, and programs whose statepoints ir-lang inserted are compiled and run against ir-lang’s reference interpreter, in an x86-64 interpreter under SysV and Win64 and natively on x86-64 Linux and Windows.
Stack maps are exact. At every safepoint the recorded root slots are exactly its GC list (IR.md §9), and no reference is in a register while the collector runs; a moving collector in the tests walks real frames by these records.
Parallel copies are exact. Every edge, copy, and pcopy goes through moves::MoveResolver, which handles any permutation, cycles of any length, fan-out, registers and stack slots mixed, and immediates, with the fewest moves under its rules.
Unsupported is an error, not bad code. What this release does not select is reported as isel::IselError::Unsupported naming what it waits on.
No reachable panics, no recursion. Every table is a dense vector, every walk a loop, every fallible path a Result. Passes are linear in the function (one sort here and there) except liveness, whose cost is the size of the live sets and has a budget (regalloc::Options::live_budget), checked once: spill rounds update the live sets incrementally and only shrink them.

§Features

std (default): no effect beyond isa-lang’s and ir-lang’s; the crate is no_std and needs only alloc.

Re-exports§

pub use ir_lang;
pub use isa_lang;

Modules§

isel: Instruction selection: one ir-lang 2.0 function to a MIR function on virtual registers.
mir: Machine IR: target instructions on virtual and physical registers.
moves: The parallel-move resolver: turns a parallel copy into a sequence of moves (and swaps) that a machine can execute one at a time.
regalloc: SSA register allocation: virtual registers to physical registers and stack slots.
target: Target descriptions: the backend’s half of TARGET-DESC.md.
x86_64: The x86-64 target: registers, classes, calling conventions (SysV and Win64), the machine-instruction table, and emission through isa-lang.

Structs§

Compiled: A compiled module: machine code, every function’s place and call-site records, the relocations against symbols defined elsewhere, and the module’s data.
DataObject: A global’s bytes and the addresses stored in them.
Options: How to compile: the platform’s C convention, frame and runtime choices, and selection and allocation settings.
PReg: A physical register: an index into the target’s register file.
Reg: A register operand: physical or virtual.
RegClass: A register class: the set of physical registers a value may live in, and the type of a virtual register. An index into the target’s class table.
RegSet: A set of physical registers: 128 bits, one per PReg index.
RegSetIter: The registers of a RegSet, in index order. Made by RegSet::iter.
VReg: A virtual register: an index into a function’s virtual-register table.

Enums§

CompileError: Why a module could not be compiled.

Constants§

MAX_PREGS: The most physical registers a target may describe.

Functions§

compile: Compiles every function of module to x86-64 machine code: instruction selection, register allocation, and emission.
compile_function: Selects and allocates one function: the MIR on physical registers that emit or an Emitter encodes.
emit: Emits one function to machine code: the one-call path.