backend-lang 0.2.0

The model

• A Function is 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 Target describes 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 (idiv reads rdx:rax, a shift by cl reads rcx, flag producers define the flags register).
• An Abi is a calling convention: argument and return registers, callee-saved registers, stack alignment, shadow space, red zone, and stack probing. layout_frame turns a function's slots and saved registers into offsets and a prologue/epilogue plan.
• The MoveResolver turns any parallel copy into moves and swaps a machine can execute one at a time.
• The Emitter encodes physical-register functions through isa-lang, resolving every edge's parallel copy on the way.

What it guarantees, and how each guarantee is checked:

Installation

[dependencies]
backend-lang = "0.2"

Without the standard library:

[dependencies]
backend-lang = { version = "0.2", default-features = false }

Quick start

emit is the one-call 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>>(())

Edges are parallel copies

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>>(())

Calling conventions and frames

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>>(())

Examples

Runnable programs in examples/:

Performance

Library-only numbers (no process start, no object file), measured with the benchmarks in benches/ on Windows x86_64, Rust stable, release profile:

Everything is linear except one sort when the resolver numbers a copy's locations (O(n log n)); a reused resolver allocates nothing once it has seen its largest copy.

cargo bench --bench bench

Design notes

• 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]; push and pop belong 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.

Testing

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 bench

The 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; on Linux x86-64, tests/executable.rs also runs them as real processes. Every rust example in this README and in docs/API.md is compiled and run as a doctest.

Contributing

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.