The machine task contract

This whole page is frozen surface: the contract's version (one line, extracted by scripts/surface-extract.sh as the machine kind) may only go up, and only in a commit that adds a Version N → M paragraph like the ones below — check-freeze enforces both (hooks.md § 8).

Contract version 6 -- the integer tasks, the depth type, deriving a machine, the KIND obligation, the register allocator and the unsigned comparisons (M17, M24, M39, M45, M49). src/gen_walk.mc is the target-independent walker; src/machine_arm64.mc (M17 step A) and src/machine_x86_64.mc (step B, and M20's Win64 half) are the three machines behind it in the compiler -- arm64, x86_64, x86_64-win -- and machine(name, tab) in src/hooks.mc is the seam. Since M39 there is a fourth, and it is not in the compiler: examples/kernel/machine_riscv64.mc registers riscv64 from a module under examples/, which is the proof that the seam is real from outside; since M40 there is a fifth, examples/avr/machine_avr.mc, which is the proof that an 8-bit part with a two-byte pointer is one too (§ The AVR implementation). M40 appends no slot and changes no signature. Since M24 a machine also reads the TYPE of a depth (walk_depth_type), which is how lib/machine_arm64_float.mc answers fadd where the built-in answers add, and how a module derives a machine with machine_tab / machine_slot; #machine was dropped (docs/specs/M24.md § M9).

A version is the list of MTASK_* slots below, in that order and with those signatures, plus what a machine outside src/ may rely on. Adding a task appends a slot and bumps the version; changing one's signature is a breaking change to every machine, and there is exactly one place to look for the answer — this page.

Version 1 → 2 appended exactly one slot, MTASK_RELOC_OFF. Version 1 assumed a relocation patches the instruction from its first byte, which is true of every fixed-width encoding and false of x86: call rel32 carries its field one byte in, lea r, [rip + disp32] three. The walker now asks. AArch64 answers 0 and its objects did not move a byte.

Version 2 → 3 (M24) appends no slot and changes no signature. The bump is what a module may rely on: walk_depth_type(d) and walk_ret_type() (§ 3), machine_tab/machine_slot as the way to derive a table, and the three allocator functions § 3 publishes by name. The float tasks the old § 3 specified — thirteen mf_* slots — were dropped: a second register file needs no contract line once the walker says what type is at a depth, and <float> is a library over that (docs/specs/M24.md). #machine was dropped with them, for the reasons in § 4.

Version 3 → 4 (M45) appends no slot and changes no signature either. The bump is an OBLIGATION: the ty a ty-carrying slot receives may be an id the registry owns, of width 1, 2, 4 or 8 and of kind TK_INT or TK_SINT, and a machine owes extension by kind — zero above the width for a TK_INT, the sign for a TK_SINT — in its loads and its MTASK_CAST, and truncation by width in its stores. The core itself now registers one such id, i32 (language.md § 2), so this is not hypothetical. A machine that keys those slots on the core ids alone is silently wrong: its MTASK_CAST(i32) is a no-op and its MTASK_LOCAL_LOAD(i32) reads eight bytes out of a four-byte slot. The rule, stated once: dispatch on type_width(ty) and type_kind(ty), never on the id. A machine that will not implement the kind must remove the word from its surface — type_disable(ty_i32) from its user_init, which is what examples/avr does.

Version 4 → 5 (M49) APPENDS SIX SLOTS and changes no signature — MTASK_REG_COUNT, REG_LOAD, REG_STORE, REG_SAVE, REG_RESTORE and PARAM_REG, MTASK_COUNT 31 → 37 (§ 5). They are how the walker asks a machine to keep a local in a callee-saved register instead of in a frame slot, and they are reached only when the developer said --opt=1 (cli.md). The version's second half is the null-slot rule: for slots 31 and up the walker reads the table entry itself and treats 0 as "this machine does not do this". A machine table is a zero-filled global of MTASK_COUNT entries, so a machine that fills the first 31 answers 0 to MTASK_REG_COUNT, is never asked the other five, and emits byte for byte what it emitted under version 4 — with no edit. examples/kernel/machine_riscv64.mc and examples/avr/machine_avr.mc are exactly that case, and scripts/check-opt.sh proves it by comparing their artefacts on both roads.

Version 5 → 6 appends no slot and changes no signature. It appends four values to ONE argument: MTASK_CMP's cond may now be MCOND_ULT, MCOND_ULE, MCOND_UGT or MCOND_UGE (6..9) as well as the six it has always carried. Every comparison used to be signed, so a u64 or a uptr with bit 63 set read as negative and 2 >= (1 << 63) answered TRUE. The walker now picks the unsigned code when neither operand is a signed type and one of them is eight bytes wide (§ 3); a narrow unsigned operand keeps the signed code, because the slot invariant zero-fills it and a signed 64-bit compare of two such values is already right. A machine that does not map the four is wrong, not merely old: there is no null-slot escape here, because the codes arrive in an argument and not in a table entry. The obligation is one line per code in whatever the machine already dispatches on — a condition-code table on arm64 and x86-64, a choice of slt against sltu on riscv64, a choice of brlt/brge against brlo/brsh on AVR — and a machine that receives a code it does not know must refuse (unknown condition) rather than encode the signed twin. All five machines in this tree map them.

Why the split exists #

Until M17 gen_lower did two things at once: it walked the AST (frames, the depth stack, labels, calls, name resolution) and it selected AArch64 instructions (I_* opcodes, x9..x15 as depth registers, x16/x17 as scratch). A second instruction set cannot be added without separating them, and separating them must not change a single byte of the objects the first one produces — which is why the acceptance criterion is that check-obj (32/32) and check-asm (73/73) stay identical against the frozen C seed, which is still one monolithic generator.

After the split:

• src/gen_resolve.mc — resolution and typing, in a side table indexed by node. Every name is bound and every expression typed before a single instruction is selected (objects.md § 2).
• src/gen_walk.mc — the walker. It knows nothing about registers. It owns the Ins buffer, the frame in bytes, the label counter, the loop stack, the block scoping of locals, the sections, the globals, the string literals and every symbol; and it drives a machine table: one &fn per task, invoked through callp.
• src/machine_arm64.mc — the register partition, the spill policy, the selection, the encoders and the --dump-asm text, moved behind that table. src/machine_x86_64.mc (step B) is a second one of exactly that shape.
• gen_lower, gen_encode_all and the three format writers keep their names and their behaviour, so lib/backend_arm64.mc, src/backend_exe.mc and src/backend_elf.mc did not change a line in step A; step B added an EM_X86_64 entry point to the ELF writer and touched neither of the other two.

1. Registering a machine #

void machine(uptr name, uptr tab)   // tab: MTASK_COUNT entries of &fn, in MTASK_* order
i64  machine_find(uptr name)        // index, or -1; searches back to front
void machine_use(uptr name)         // make that machine the one in effect

machine() appends to a linear table in registration order — unlike backend(), a machine is not chosen by a flag but by the target, and the compiler always has exactly one in effect. A registration takes that place when there is no machine yet, when the name is new, or when it replaces the name that is in effect; a registration of some other registered name does not (the full rule, and what it is for, is in hooks.md § machine). The ceiling is fixed (MAXMACHINES 8): a machine does not scale with the program being compiled, so M23's "no MAX* on tables that grow with the input" does not apply.

src/machine_arm64.mc builds its own table with two helpers and registers it from main(), before any backend can lower:

void machine_task(i64 task, uptr fn)   // one slot of m_arm64
void machine_arm64_init()              // fills all 31 slots, then machine("arm64", m_arm64)

src/machine_x86_64.mc is the same two functions under its own names, x86_task and machine_x86_64_init() — which registers x86_64 and then, from a copy of the same table with MTASK_PROLOGUE replaced, x86_64-win (M20).

The walker reaches the table through uptr mach(i64 task), which is the only place that reads mach_tab. A machine that is missing is no machine registered, not a crash.

How a machine is chosen (settled in step B). main() registers every machine and then names the host's, because the first registration is what is current by default:

machine_arm64_init();
machine_x86_64_init();
machine_use_if(host_machine());

From there the object backend picks, as its first statement — backend_elf does machine_use("arm64"), backend_elf_x86 does machine_use("x86_64"), and backend_coff_x86 does machine_use("x86_64-win"), which is how the Win64 ABI is reached without target() growing a fifth column. Step A left two shapes open: a fifth column on target(), or machine_use from the backend. The backend won, for three reasons. target() keeps the four columns docs/specs/M33.md § 1 wrote down. An AST-consuming backend (wasm) needs no machine at all, so a mandatory machine column on every target would be a column it has to leave empty. And the file format already records the architecture — e_machine, cputype — so the writer that fills that field is exactly the code that knows which instruction set produced the bytes; splitting the two across a registry row would let them disagree.

The --dump-* modes never reach a backend, so --machine=NAME (cli.md) is what points them at a machine other than the host's: mc --dump-asm --machine=x86_64 f.mc.

2. The integer tasks (version 2) #

Every task takes depth indices, never registers: the walker says "the value is at depth 2", and whether depth 2 lives in a register or in a frame slot is the machine's decision. ty is a core type id — one of the core constants (TY_U8, TY_U16, TY_U32, TY_U64, TY_I64, TY_UPTR) or one the registry owns, i32 included — and stands for the access width and, for a load or a cast, for the kind that says how the bytes above that width are filled (contract version 4: type_width(ty) and type_kind(ty), never the id); l is a label number; sym a symbol index; e an Ins record.

The six register-allocation slots (version 5) #

They are appended after MTASK_DUMP in the MTASK_* order --dump-machine prints, and none of them is mandatory: a 0 entry in any of the six reads as "the machine does not do this", which is the null-slot rule. r is an allocatable register index, 0 .. count - 1; what register that IS, is the machine's business and appears nowhere above this file.

MTASK_REG_LOAD carries no type on purpose: a register holds the fully extended eight bytes, exactly as a spill slot does, so the extension is performed once at the store and never at a load. The save area is ordinary frame slots, asked of slot_new like any other, which is what keeps every claim of objects.md § 4 true on the optimized road too — the frame record is still unconditional, the epilogue is still add sp / ldp / ret, and a stack walker or a debugger finds a saved register at a fixed [sp, #k].

The walker asks for the count through i64 walk_reg_count(), which answers 0 whenever walk_opt() is 0: an optimizer that is off asks nothing of the machine at all. A machine that answers a non-zero count and leaves one of the other five null is a bug in that machine, and it is said so: mc: machine answers MTASK_REG_COUNT but leaves a version 5 slot empty.

Two obligations come with the version, and both were found by running the code.

1. Read a depth through val_reg(d, scratch), never as REG_BASE + d. Since version 5 the value of a depth may live in an allocatable register rather than in the depth's own — that is what MTASK_REG_LOAD records, and it emits no instruction at all — so val_reg is the only function that knows where it is. A derived machine that computes the register itself reads a stale x9. lib/machine_arm64_float.mc did exactly that in its own fa_save_live and in its stack-argument path and was corrected with this version; lib/machine_x86_64_float.mc had the same three (its fx_save_live, its fx_restore_live and its stack-argument path) and lib/i128.mc's xw_call a fourth, all corrected when the x86-64 allocator landed (D2). Nothing else in lib/ or examples/ computes a depth register by hand.
2. A machine that overrides MTASK_PARAM MUST override MTASK_PARAM_REG. The bundled a64_param_reg reads argument i out of x_i, because on an integer-only ABI the source index is the register number. On a float ABI it is not — fa_param walks its own NGRN/NSRN/stack counters, so a float in position 0 and an integer in position 1 make i and the register disagree from the second parameter on. Inheriting the bundled slot put the wrong register in the local, measured: tests/float/019-putf64.mc printed 0. -1.3 0.4 where it prints 3.500 -1.25 0. lib/machine_arm64_float.mc and lib/i128.mc (whose own counter skips a register for the even-pair rule) each carry a *_param_reg of their own for this reason, and so do their x86-64 halves, fx_param_reg and xw_param_reg — on Win64 the float and integer argument slots are SHARED, so i and the register disagree there for a different reason again.

What the arm64 allocator does #

a64_reg_count() answers 10: x19..x28, with r meaning x(19 + r). x18 is never allocated. The saves and restores are plain str/ldr into frame slots, so the allocator adds no instruction form at all — measured, the set of distinct mnemonics in src/mc.mc's object is the same on both roads, and the 2284 distinct instructions of the optimized object re-assemble byte for byte under llvm-mc -triple=aarch64-apple-macos.

Two things make an allocated local usable as an operand directly, and both are private to the machine:

• the alias table. MTASK_REG_LOAD(d, r) emits nothing and records dalias[d] = 19 + r; val_reg(d, …) answers that register, and every task that produces a NEW value at d clears the entry (one line in dst_done, which every value-producing task already ends with). save_live and restore_live skip an aliased depth entirely: its value is in a register the callee is required to preserve, so the frame round trip around a call is dead work. Aliases are cleared at every MTASK_LABEL — a control-flow merge, where a value carried in an alias could have arrived by another path — and after every MTASK_REG_STORE.
• the store rewrite. MTASK_REG_STORE(ty, 0, r) looks at the instruction just emitted; if it WROTE the depth's own register (a whitelist: the eleven three-operand forms, msub, mvn, neg, cset, the three immediate forms, mov/mov w, the three sign extensions and the load half of the memory table — never a store, whose rd is its SOURCE, and never movz/movk, which come in chains of up to four writing the same register), its destination is retargeted at the local's register and no mov is emitted. That is what makes x = x * C + K end in add x19, x9, x10 and i = i + 1 in add x21, x21, x10.

Two more emission-time peepholes fuse a comparison and the branch that reads it. Neither is a slot and neither is a pass: the machine already sees the instruction it just emitted, and each pattern is "the instruction I am about to emit consumes the one just emitted and nothing else can". Both are guarded by walk_opt() != 0 and by adjacency — an I_LABEL between would BE the last instruction and is not an I_CSET, so the guard fails and the plain lowering stands.

• P1 — the branch fusion. a64_jz/a64_jnz: when the last instruction is a cset rd, cc whose rd is the depth's own register, drop it (I_NOP generates no word) and branch on the flags the preceding cmp left. JNZ (branch when the boolean is true) emits b.cc; JZ (branch when it is false) emits b.<cc ^ 1> — the negation of every C_* pair (EQ/NE, GE/LT, GT/LE) is exactly cc ^ 1, the same inversion the cset encoder itself applies. The cset's register is dead after a branch at every walker site (gen_if at depth 0, gen_logic overwrites the depth on both paths), so no liveness beyond adjacency is needed.
• P2 — the LNOT flip. a64_un for MUN_LNOT: when the last instruction is a cset rd, cc on the depth's register, flip its condition in place (cset rd, cc ^ 1) and emit nothing — instead of the plain cmp #0; cset eq a logical NOT would otherwise cost.

b.<cond> (I_BCOND) is the one instruction form the peephole adds to the sweep; it was already encoded, dumped and in lib/backend_arm64.mc and simply had no emitter before. Together P1 and P2 turn the prelude's five-instruction while condition — cmp; cset lt; cmp #0; cset eq; cbz — into cmp; b.lt plus the loop's own unconditional branch.

What the x86-64 allocators do (step D2) #

x86_reg_count() answers 5 on BOTH machines: rbx, r12, r13, r14, r15 — the five that System V and Win64 agree are the callee's to preserve. rdi and rsi are callee-saved on Win64 and argument registers 1 and 2 on System V, so a count that depended on which prologue last ran would be stale for the first function of a unit; two registers are not worth a second code path (D11), and the assertion in scripts/check-surface.sh is that x86_64-win's optimized lowering of src/mc.mc does not NAME them at all. The register partition does not move: depths stay in r8..r11 and scratch stays rax/rcx/rdx. r is an index and x86_allocreg_at(r) is the map — arithmetic rather than a base, because the set is not contiguous.

The saves and restores are mov [rbp - k], rbx / mov rbx, [rbp - k] into ordinary frame slots, so they add no instruction form: leave still ends every function, MTASK_FRAME_FIX still patches only the prologue's sub rsp, and a stack walker's view does not change.

The alias table is the same mechanism, in the same place (xalias_at, the second half of the xdslot array), with one difference that is the architecture and not a choice:

• the store rewrite is a much smaller whitelist. x86 is two-operand, so add rd, rn means rd = rd + rn: retargeting its destination at the local's register would add to a register that does not hold the old value. So add/sub/and/or/xor/imul/shl/shr/sar/neg/not are all out, every store is out (its rd is its SOURCE), setcc is out (it writes one byte), call r 's rd is the target and idiv/div 's is the divisor. What is left is every form that only WRITES: the three movs, the two leas, the five register movzx/movsx and the seven loads — which is what a local's initialiser, a constant, a global read and a comparison's boolean all end in. x = x + 1 therefore costs one mov on x86-64 where it costs none on AArch64.
• far more tasks have to materialise an aliased depth first, for the same reason: x86_own(d) is a64_own's counterpart and is called by MTASK_BIN (whose destination IS its left operand), MTASK_UN, MTASK_BOOL and MTASK_CAST.

The two peepholes are the same two patterns over the pair x86 needs for a boolean, setcc rd, cc followed by movzx rd, rd (setcc writes one byte, so the movzx is never separable from it):

• P1 — x86_jz/x86_jnz: when the last two instructions are that pair on the depth's own register, drop both (X_NOP generates no bytes and no dump line) and branch on the flags the cmp left, instead of the test rd, rd; jcc the plain road emits. JNZ uses cc, JZ uses cc ^ 1 — x86 condition codes are defined in negation pairs (the low bit of tttn), so one xor inverts e/ne, l/ge and le/g alike.
• P2 — x86_un for MUN_LNOT: the same pair, condition flipped in place, nothing emitted.

jcc rel32 is NOT a new form, which is a correction to docs/specs/M49.md § 4.7: x86_jz has always ended in X_JCC, so the descriptor row and the encoder were already there and already swept. What the peephole adds is four new CONDITION VALUES of that existing form — jl (0f 8c), jge (0f 8d), jle (0f 8e), jg (0f 8f) beside the je/jne the plain road already emits — and the mnemonic set of the optimized object is the plain one's plus exactly those four, on System V and on Win64 alike, with 0 mismatches in the llvm-mc sweep.

Loop-invariant values are allocated the same way, as pseudo-locals. A register a taken local did not want goes to a value that a loop rebuilds every iteration, and there are two kinds: an N_INT whose immediate costs two or more instructions (any 16-bit part above the low one non-zero -- one movz plus up to three movk) and whose type is an integer of the word width or less, and the address of a GLOBAL, which is an adrp + add pair.

That type condition is TK_INT or TK_SINT with type_width <= 8 — exactly what the walker asks of a local, and for exactly the same reason. A taught literal is an N_INT too: <float>'s f64 literal is an N_INT whose type is TK_FLOAT and whose val is the IEEE bit pattern, and that value belongs in a float register, so putting it in x19..x28 and handing the depth an integer alias makes a derived machine read a register that never held it (measured: 0.0 + 2.5 three times came out 0x56e6e8cc4576e6a1 instead of 0x401e000000000000 before the condition existed; tests/float/028-lit-in-loop.mc is the gate). A GLOBAL's address needs no such condition: an array's decay is a uptr whatever its elements are. The walker records each DISTINCT value once, in first-occurrence order -- constants by value, globals by their index in the global table -- scores it with the same 8^depth weight and the same threshold of 3, and takes what the locals left. A taken one is materialised ONCE, at function entry, right after the parameters (MTASK_CONST or MTASK_SYM_ADDR at depth 0, then MTASK_REG_STORE(TY_I64, 0, r)), and every use of that value anywhere in the function -- inside the loop and outside it -- becomes an MTASK_REG_LOAD, which is to say an alias-table entry and no instruction at all.

Entry materialisation runs even when the loop is never entered. Two to four instructions cannot fault: a symbol address is a relocation, not a load, and a constant is an immediate.

A machine sees nothing new: the tasks are the ones it already fills, at the depth it already handles, and a machine that answers 0 to MTASK_REG_COUNT never reaches the code. On the plain road the candidate list is empty and the three loops that walk it have zero iterations.

Not hoisted, on record: a STRING literal's address and a FUNCTION's address. Both would have to be keyed by a symbol index and both CREATE their symbol on first use (str_sym also appends to __cstring), so hoisting one would move symbol creation and literal placement inside a function for a gain the measurement below never needed. A global's symbol already exists -- gen_globals runs before the first gen_func.

Measured on bench/mc/bench.mc (Apple M4, --exe --opt=1, best of 11 interleaved with the reference): the whole workload is 0.54 s against 0.79 s on the plain road and 0.42 s for clang -O2 — 1.30x. Per phase, mix 0.45 -> 0.22 s, primes 0.21 -> 0.19 s, fib 0.13 s unchanged (its cost is the call count, which nothing here touches). --dump-asm of the workload goes from 370 lines on the plain road to 319, and the mix loop body from 50 instructions per iteration to 18 — no memory traffic, and no constant costing more than the single movz a shift count is worth. The last two steps' own shares are each at the edge of this host's 10 ms timer -- the branch peephole moved mix 0.22 -> 0.21 and primes 0.20 -> 0.19, hoisting moved mix 0.22 -> 0.216, primes 0.206 -> 0.198 and the whole workload 0.551 -> 0.542 -- because these loops are latency-bound on the dependent mul/add chain once the frame round trip the allocator removed is gone. src/mc.mc's own __text is 480 420 B with --opt=1 against 535 720 B plain, -10.3%: two instructions per allocated register buy back more than they cost.

The operator vocabulary the tasks speak:

MOP_ADD MOP_SUB MOP_MUL MOP_SDIV MOP_UDIV MOP_SMOD MOP_UMOD
MOP_AND MOP_OR MOP_XOR MOP_SHL MOP_SHR MOP_SAR
MUN_NEG MUN_NOT MUN_LNOT
MCOND_EQ MCOND_NE MCOND_LT MCOND_LE MCOND_GT MCOND_GE
MCOND_ULT MCOND_ULE MCOND_UGT MCOND_UGE

Signed and unsigned are separate operations, not a flag: the walker picks MOP_SDIV over MOP_UDIV (and MOP_SAR over MOP_SHR) from res_type of the left operand, which is mc's actual rule — i64 and every TK_SINT divide and shift with sign, everything else does not (type_signed, M45). Comparison is the same shape and, since contract version 6, the same rule: ten codes, and cmp_unsigned in src/gen_walk.mc is the whole of it —

unsigned  iff  neither operand is a signed type, both are TK_INT,
               and one of them is eight bytes wide

— so u64 and uptr compare as addresses and everything else keeps the signed code. EQ and NE have no signed form to be the other of, which is why there are ten and not twelve. Three things follow, and each is deliberate:

• A narrow unsigned operand keeps the signed code. A u8, u16 or u32 is zero-filled above its width by the slot invariant (§ 5), so both values are far below 2^63 and a signed 64-bit comparison of them is already the unsigned one. This is what let every object in the corpus come out byte for byte what it was.
• A comparison with an i64 on either side stays signed, which is NOT C's rule. C makes the whole expression unsigned and turns a negative i64 into a huge number; here the signed side wins, so no program that works today changes meaning. A plain integer literal is i64 (language.md § 3), so a constant with bit 63 set belongs in a u64 variable.
• A float, a wide type and an opaque type are excluded by the kind test, so <float>'s f64 (eight bytes, not signed) and <i128>'s u128 keep receiving the six codes their own MTASK_CMP knows.

The walker itself issues MTASK_CAST in two places no expression asked for it (M45): after MTASK_CALL, when the callee's declared result is a TK_INT/TK_SINT narrower than the word and is not uptr, and before MTASK_RET, when the function's own declared result is. Every ABI leaves the bits above a narrow result unspecified, so that extension is the compiler's to perform, and routing it through a slot every machine already fills is what keeps the contract at 31 slots. The ty those two casts carry is the DECLARED type, and the walker rewrites walk_depth_type(d) to it before the call-side one, so a derived machine reading the depth type as the cast's SOURCE sees an integer and not the type of argument 0.

The four divide operations say nothing about a zero divisor or about INT64_MIN / -1: a machine emits its target's divide instruction and the ISA answers, so a new machine owes no guard and is not judged on the answer it gives — but it does owe the row in the table below. Three answers exist today and they are all different: AArch64's sdiv/udiv give 0, x and INT64_MIN and never trap; x86-64's idiv/div raise SIGFPE and the process dies; RV64M's div/divu/rem/remu give -1, x and INT64_MIN and never trap (../core-language.md § "Division by zero, and INT64_MIN / -1"). Shift counts are the opposite case: mc and all three machines mask them modulo 64.

What the walker keeps, and what it hands over #

frame too large is deliberately kept in the walker even though the 12-bit limit is AArch64's: docs/specs/M17.md § step B says a machine with no such limit should keep the language limit anyway, so the diagnostic is the same on every target.

And a machine with a SMALLER limit pays for it itself. RISC-V's load/store displacement is a signed 12-bit field and reaches 2047, where 4095 is AArch64's unsigned one; frames of 2048..4095 are legal to the walker and unencodable by a naive machine — a silent wrong address, not a diagnostic. The obligation is on the machine, not on the walker (docs/specs/M39.md § G7): examples/kernel/machine_riscv64.mc materialises any offset past 2047 in t2 and adds it, which is what makes V_ADDI, the eight memory forms and the frame reserve variable-length, and therefore what makes running the real encoder for MTASK_INS_SIZE mandatory rather than tidy. A machine that cannot encode the whole 0..4095 range has to say so on this page.

The same rule covers jump range. The walker has no limit on how much code a function may contain, and the three machines disagree by two orders of magnitude on how far one jump reaches: AArch64's b 128 MiB, x86-64's rel32 ±2 GiB, RISC-V's jal 1 MiB. A machine whose field is too small must say so with a diagnostic, never mask the displacement into it — a truncated jump gives an image that builds, boots and lands in the middle of an instruction, which no later gate catches. src/machine_arm64.mc does it in br_off (branch too far, checked against the smallest of its three fields), and examples/kernel/machine_riscv64.mc in rv_jal_off (riscv jal out of range), and examples/avr/machine_avr.mc in avr_rjmp_off (avr rjmp out of range, at ±4 KiB — the smallest reach of any machine here, and the one where a real program can hit it). All three check on the ENCODE pass only: MTASK_INS_SIZE runs before any label address exists, and both machines' jump forms are fixed width, so the size does not depend on the answer.

The AArch64 implementation #

The thirty-one slots are filled by a64_prologue, a64_param, a64_epilogue, a64_frame_fix, a64_const, a64_bin, a64_cmp, a64_un, a64_bool, a64_cast, a64_load, a64_store, a64_local_addr, a64_local_load, a64_local_store, a64_sym_addr, a64_global_load, a64_global_store, a64_call, a64_callp, a64_ret, a64_jump, a64_jz, a64_jnz, a64_label, a64_word, a64_ins_size, a64_encode, dump_ins, a64_reloc_kind and a64_reloc_off (which returns 0: the word is the field). Under them sit the pieces a backend can still call by name: gen_imm(rd, v), gen_cast(rd, ty) and gen_gaddr(rd, sym) (objects.md § 3).

Deviations from docs/specs/M17.md's sketch #

The spec's list is the same contract with three names collapsed, and this page is the normative one:

• m_global_addr and m_str_addr are one task, MTASK_SYM_ADDR: both are "the address of this symbol", and &fn is the third caller of it.
• m_arg_move(d, i) is not a slot. The walker lowers the arguments to depths and then calls MTASK_CALL / MTASK_CALLP once; where each argument goes, and what has to be saved around the call, is entirely the machine's — which is what lets callp put its pointer in x16 without the walker knowing.
• m_prologue(frame, nparams) is split into MTASK_PROLOGUE (no arguments), one MTASK_PARAM per parameter and MTASK_FRAME_FIX(frame), because the frame size is only known after the body: the spill slots are allocated while it is being walked.

The x86-64 implementation (M17 step B) #

src/machine_x86_64.mc fills the same thirty-one slots, and registers two machines out of one set of functions: x86_64 (System V, M17 step B) and x86_64-win (Win64, M20). It is the proof that the split is real: not one line of src/gen_walk.mc is architecture-specific, and the ELF writer is shared with aarch64 down to the section table.

The two ABIs are two machines, not a flag. m_x86_64_win is a copy of m_x86_64 with one slot replaced, MTASK_PROLOGUE; the other thirty entries are literally the same &fn, because MTASK_INS_SIZE, MTASK_ENCODE, MTASK_DUMP, MTASK_RELOC_KIND and MTASK_RELOC_OFF are pure functions of the Ins record and know nothing about a calling convention. The convention itself lives in three globals — the argument table, how many arguments travel in registers, and the caller's shadow space — set by that prologue, which gen_func always runs before the first MTASK_PARAM and before any MTASK_CALL, so they can never be stale. Two machines rather than a runtime flag because --dump-asm --machine=x86_64-win has to be able to show the Win64 sequence, and a flag the backend sets could not.

Two consequences of variable-length encoding, both already in the contract:

• MTASK_ENCODE writes into the section buffer instead of returning a word, and MTASK_INS_SIZE is what the label pass asks. There is exactly one encoder, x86_put: MTASK_ENCODE is that function, and MTASK_INS_SIZE runs the same function over a scratch buffer and returns its length. The two therefore cannot disagree — and a one-byte disagreement would silently move every later branch, so "cannot" is worth more than "is checked".
• One descriptor table drives all three readers of an opcode. x86_desc holds six columns per opcode — form, REX.W, the opcode byte(s), the ModRM extension, an optional 0x66 prefix, and whether REX is forced — and x86_put and the --dump-asm printer both dispatch on the form. Thirty of the forty-five opcodes need no code of their own at all.
• Functions are still aligned to 4 (gen_encode_one), so up to three zero bytes sit between them. They are never executed — every function ends in ret — but a disassembler decodes them as add %al, (%rax).

The arguments past the register table are pushed with push r/m64, straight from the frame slot, so no scratch register is spent on them; an odd count reserves an extra 8 bytes first, because rsp has to be 16-byte aligned at the call. On Win64 the 32 bytes of shadow space are subtracted last, so they end up below the pushed arguments and the fifth argument lands at [rsp+32] — the place the callee's MTASK_PARAM reads it from. The alignment rule does not change: 8*np + 32 is 0 mod 16 exactly when np is even. objects.md § 4c is the full Win64 contract, including why r8/r9 being argument registers 3 and 4 and depth registers 0 and 1 is safe.

The RISC-V 64 implementation (M39) — from outside the compiler #

examples/kernel/machine_riscv64.mc fills the same thirty-one slots from a module under examples/, with its own two-line setter (rv_task), and examples/kernel/image.mc is the writer that consumes it. Nothing in src/ changed to make it possible.

Three things are worth reading it for, beyond the columns.

MTASK_BIN has no special case at all. All thirteen MOP_* are one R-type instruction each: no msub for the remainder, no cqo/idiv pair, no ModRM. sll/srl/sra already mask the count modulo 64 and lbu/lhu/lwu/ld already zero-extend, which is exactly what MTASK_LOAD asks for — and lb/lh/lw are the sign-extending twins contract version 4 asks for, at no cost. RV64IM is the friendliest set the walker has met.

Two relocations are fused into one instruction. MTASK_SYM_ADDR is a single 8-byte Ins holding auipc rd,0 + addi rd,rd,0, and MTASK_CALL a single one holding auipc ra,0 + jalr ra,ra,0, each carrying ONE relocation at offset 0. Emitting the two words as two instructions would need a second relocation against a local label naming the auipc — RISC-V's %pcrel_lo(L) — which is a shape neither reloc_add nor sym_* has a name for; fusing avoids it entirely (docs/specs/M39.md § G3, decision D4). The kinds are 32 and 33, chosen by the module the way src/machine_x86_64.mc chose 16 and 17.

Addressing is pc-relative and not absolute. lui t2, 0x80000 on RV64 yields 0xFFFFFFFF80000000 — the immediate is sign-extended — so the lui/%hi route is wrong at exactly the address a virt board loads a kernel at, while auipc at the same place yields 0x0000000080000000 (decision D3).

Verification. Every distinct instruction the machine emits while compiling examples/kernel/main.mc (234), examples/kernel/tests/sweep.mc (262) and a generated source of 800 functions (1057) re-assembles byte-identically under llvm-mc -triple=riscv64 -mattr=+m; the pc-relative displacements — 58, 34 and 34 fused pairs plus 51, 53 and 3253 branches — are checked against a placement of the sections recomputed independently from --dump-syms. And the image boots: examples/kernel/test.sh asserts the transcript and the exit code under QEMU, on the owner's machine and on the baremetal-riscv64 CI leg.

The AVR implementation (M40) — the first narrow word #

examples/avr/machine_avr.mc fills the same thirty-one slots from a module under examples/, and examples/avr/image_avr.mc is the ELF32 writer that consumes it. Nothing in src/ changed to make it possible either — but one thing the compiler that carries it DECLARES did not exist before M41: type_set_width(TY_UPTR, 2), called from user_init, which is what makes a pointer two bytes in a frame slot, in a global and in a uptr[] initializer (docs/specs/M41.md § 4a). The machine does not read that width for its own decisions; the walker does.

Four things are worth reading it for.

A depth is memory, and that is a design and not a shortcut. Every task loads its operands from frame slots into r16..r23, computes, and stores back. The win is that MTASK_CALL needs no save_live/restore_live at all — a callee cannot clobber a frame slot — and the cost is size: about 500 bytes of flash for a statement like check(11, a * 3, 0x0369d0369d0369cd). On a part with 32 KiB that is the binding constraint, and it is why examples/avr/tests/ is two programs.

Arithmetic happens at the depth's declared width, and it diverges. walk_depth_type(d) (M24) is what makes u16 + u16 two adds instead of eight, and docs/specs/M40.md D4 accepted the consequence rather than discovering it:

i64 narrow3(u8 a, u16 b, u32 c) { return a + b + c; }
narrow3(200, 40000, 3000000000)      // 8 on avr, 3000040200 on arm64

res_binary types a sum from its LEFT operand and nothing re-widens it, so the addition is done in eight bits here and in sixty-four there. A source that wants the portable answer casts: (i64) a + (i64) b + (i64) c. examples/avr/tests/sweep_b.mc asserts both answers, checks 52 and 56, so the divergence cannot drift unnoticed.

Comparison is the one place narrow arithmetic cannot be narrow. Two narrow operands reach a machine with a SIGNED condition — the walker only picks an unsigned one when a side is eight bytes wide (§ 3) — while u8/u16/u32 are themselves unsigned, so comparing two zero-extended u16s at two bytes would answer -25536 < 1 for 40000. The machine compares at max(w1, w2) + 1 bytes when neither operand is i64, and at all eight when one is: the extra byte is zero by the slot invariant, which turns the signed comparison into the unsigned one. avr_cmp_width is the whole rule. A version 6 unsigned condition reaches it too, at eight bytes, and avr_cmp answers it with brlo/brsh — the C flag the cp/cpc chain leaves — where the signed twin takes brlt/brge.

Every slot holds eight valid bytes. A value of a type of width w has its bytes above w filled by its KIND — zero for a TK_INT, the sign for i64 and for a TK_SINT — which is what lets a consumer read a depth at a width the producer did not use: i64 x = u8v; stores one byte and reads eight, and both are right. Without that invariant every task would need to know what the next one intends. This machine implements the zero half only, and the compiler that drives it therefore takes the one TK_SINT word the core registers back out of the surface (type_disable(ty_i32) in examples/avr/mc-avr.mc); sign-fill on AVR is a later ask.

Verification. Every distinct instruction the machine emits over the firmware (570) and the two sweeps (675 and 735) re-assembles byte-identically under llvm-mc -triple=avr -mcpu=atmega328p; the 337 relative and 226 absolute targets are recomputed against the section bounds; the ELF is compared field by field with the same program built by avr-gcc -mmcu=atmega328p; and the image runs under both simavr and qemu-system-avr, with the two sweeps checking their own answers on the device. examples/avr/test.sh and the baremetal-avr CI leg.

#opcode, emit() and reloc() are architecture-specific by nature — a source full of hand-encoded AArch64 words is portable to Linux arm64 and nowhere else — so the tests that use them carry a // skip-x86_64: header with the reason, which scripts/test-linux.sh --arch x86_64 prints.

Verification. Every distinct instruction the machine emitted while compiling src/mc.mc for x86-64 — 948 of them — was fed back through llvm-mc -triple=x86_64-linux-musl and came out byte-identical; the relocation shapes (R_X86_64_PC32 at instruction + 3 with addend −4, R_X86_64_PLT32 at instruction + 1 with addend −4) match clang --target=x86_64-linux-musl -c of equivalent C, field for field. The suite itself runs: make test-linux-x86_64.

The Win64 half was swept the same way (M20): the 967 distinct instructions the machine emits while compiling src/mc.mc for windows/x86_64 re-assemble byte-identically under llvm-mc -triple=x86_64-windows-msvc, and the 9361 pc-relative displacements it wrote were checked against target - (address + length). The relocation shapes match clang --target=x86_64-windows-msvc -c of equivalent C: IMAGE_REL_AMD64_REL32 at instruction + 1 for a call and at instruction + 3 for a lea r, [rip+d32], with the in-place field zero and no addend anywhere (objects.md § 8). The suite itself runs on the windows-2025 CI leg: make test-windows-x86_64 cross-compiles it.

3. The depth type, and what a taught machine may rely on (version 3) #

A machine with one register file needs nothing here: the walker says "the value is at depth 2" and depth 2 is an integer. A machine with two — floats in v0..v31, a wide value in a pair, a vector in ymm — has to know what is at depth 2 before it can pick the file, the instruction and the ABI register. MTASK_PARAM has carried ty since M17, so the callee side of a float ABI was already reachable; MTASK_BIN/CMP/UN/BOOL/CALL/RET carry no type at all, and that asymmetry is exactly what these two functions close.

Neither is a task slot. No signature moves, the contract stays additive, and a machine that never reads them emits byte for byte what it emitted under version 2.

How they are maintained. gen_expr is a wrapper around the dispatch: it writes res_type(n) into the depth before the children run, calls the dispatch, and writes res_type(n) again after. The second write is the one that matters — the value that actually lands at d is described by the node that produced it, not by the last child that happened to use the same depth. That one line covers, in one place, every site where the type changes under the walker's feet: a comparison (i64 out of two floats), gen_logic's shortcut constant, MUN_LNOT, a cast, an intrinsic load, and a call — where depth d is overwritten by argument 0 before the result comes back. walk_ret_type() is saved and restored around each child for the same reason, which is why a MTASK_CALL handler can still ask what the call returns while dtype[d] holds argument 0's type. Every depth is reset to TY_I64 at the top of each function.

Where a callp's answer comes from. MTASK_CALLP(d, na) reads walk_ret_type() exactly as MTASK_CALL does, and an indirect call has no callee to read a signature from — so the answer is what the cast around the call declared: (f64) callp(p, x) types the call node f64 and the handler is told f64 (docs/reference/language.md § 7). With no cast the node is i64 and the handler is told i64, which is what every callp has been told since M10. A machine that reads walk_ret_type() in MTASK_CALLP therefore needs no new slot and no new rule; before this contract it was told i64 unconditionally and a float result was never moved out of d0/xmm0. The narrow half follows the same rule: (i32) callp(...) extends at the call, the way M45 extends a direct call, and walk_depth_type(d) holds i32 when the written cast's own MTASK_CAST runs.

Take the result before you restore. A machine that saves its live depths around a call has to move the value out of the ABI's return register before it reloads them, because the two can be the same register: on Win64 <float> puts the float depths in xmm0..xmm5 (xmm6..xmm15 are callee-saved), so depth 0's register is xmm0, and restoring first overwrites what the callee returned. AArch64 (v16..v23 against d0), SysV (xmm8..xmm13 against xmm0) and every integer half (rax/x0 is nobody's depth) do not show it, so one order has to serve them all — result, then restore, in MTASK_CALL and MTASK_CALLP alike.

What this buys. MTASK_BIN(MOP_ADD, d, d2) with walk_depth_type(d) == f64 is an fadd; MTASK_RET(d) returns in v0; MTASK_CALL(d, na, sym) walks walk_depth_type(d + i) and runs the AAPCS64 NGRN/NSRN split — the whole float ABI, with no task added. A stale entry is wrong code rather than a diagnostic, so lib/machine_probe.mc derives a machine that asserts the contract on every task and is run over the whole of src/mc.mc by scripts/check-surface.sh; the criterion is that the assertion never fires and the object stays byte for byte the bundled machine's.

The allocator functions a task handler may call #

A machine's register partition and spill policy are private — dslot, in_reg, save_live, REG_BASE are nobody's business. Exactly three names are published, because a task handler and an intrinsic handler (hooks.md § 3) written outside src/ have to be able to find where the allocator put their operands:

They exist with these signatures in both bundled machines (src/machine_arm64.mc, src/machine_x86_64.mc) and the x86-64 ones carry the x86_ prefix (x86_val_reg, x86_dst_reg, x86_dst_done) because .mc has no file scope. Nothing else of a machine's internals is contract: a derived table reaches the built-in implementation of any slot through the pointer it copied, which is what keeps a64_bin/a64_const from being frozen surface.

Deriving a machine #

machine_tab(name) gives the table to copy from and machine_slot(tab, task, fn) writes one slot of the copy; the recipe, and the one trap in it — delegate through a pristine second copy, not through the table you patched — is in hooks.md § 3. lib/machine_probe.mc is the smallest complete example, src/machine_x86_64.mc's Win64 half the oldest one, and lib/machine_arm64_float.mc the one that adds a register file.

The opcode bands #

A derived machine that adds instructions the bundled one does not have gives them opcode numbers of their own, above every I_* / X_* the core uses (52 today). Those numbers are shared by every machine derived from the same table, so two modules that pick the same base cannot be loaded into one compiler — and because derivation is ordered and last-wins, which of the two loses depends on the registration order.

Two rules, and a registry. Both are obligations of a derived machine:

1. Bound the band at both ends. Every slot that dispatches on ins_op — the encoder, the dump, MTASK_INS_SIZE, MTASK_RELOC_KIND, MTASK_RELOC_OFF, a store-rewrite whitelist — asks op >= BASE && op < MAXOP and delegates to the pristine table otherwise. op >= BASE alone claims every opcode ANOTHER module put above it. Write the test once, as one predicate the slots share, so they cannot disagree about where the band ends.
2. Take a free base from the registry below, one band per module per architecture, and record it there in the pull request that adds it.

A module-private RELOCATION kind is a separate space and has its own convention (examples/kernel/machine_riscv64.mc uses 32 and 33).

Seen from the bundled side, the rule has a second half: an opcode no machine claims is refused. src/machine_arm64.mc and src/machine_x86_64.mc check op < I_COUNT / op < X_COUNT and die with

mc: opcode 303 is not x86-64's: no machine claims it

naming the opcode and the table. It is the one message either of them has for a band whose owner is not in the compiler that is running — which happens when a module's intrinsic registrations outlive its machine: <f16> drives arm64 alone, so an f16 program compiled for x86-64 through --backend= or --machine= (both read after user_init, so a module cannot see them) reaches the x86 table with HI_* in hand. On arm64 the tables are searched and the old answer was instruction with no dump / instruction with no encoder, which named neither; on x86-64 x86_desc and x86_name are indexed by the opcode, so the encoder read past the end of the array and emitted whatever the next rows happened to say — a program that segfaulted with no diagnostic anywhere. The guard sits in x86_d and x86_name_at, the two accessors every reader (x86_form, x86_put for MTASK_ENCODE and MTASK_INS_SIZE, x86_dump) goes through, and at the head of a64_ins_size, encode and dump_ins.

tests/wide/035-coexist.mc is the gate: <float>, <f16> and <i128>/<u128> in one compiler, built in both registration orders (lib/mc_float_wide.mc, lib/mc_wide_float.mc), producing the same object and the same output.

4. Why there is no #machine #

The directive that would have made the table teachable from a source file —

#machine arm64  fadd_f64(rd, rn, rm)  0x1E602800 | (rm << 16) | (rn << 5) | rd

— was specified through M17 and dropped by M24, deliberately, for three reasons worth keeping:

• it is a fourth encoding-template language after #opcode and x86_desc;
• a task is not an instruction. MTASK_BIN(MOP_ADD, d, d2) on a spilled depth is a load, an op and a store, so a one-word template is false for every deep expression;
• it would be a directive the frozen stage0/lex.c's dir_names[] cannot parse, so it could never appear in src/*.mc anyway.

machine_slot + #opcode + intrinsic + --dump-machine reach the same place with no new syntax: a module writes an ordinary .mc function, puts it in a copied table, and --dump-machine (cli.md) prints every task of every machine with the origin of its slot, so an override is auditable and a wrong one is visible. lib/user_badmach.mc is exactly that test: one replaced slot lowers + as a subtraction, a program that adds 50 and 8 answers 42, and the dump reports bin taught on the arm64 row with every other task still bundled.

5. What a module can do instead of writing a machine #

The other seam is the one in objects.md: call gen_lower(root) and replace gen_encode_all() with your own encoder over gen_ins_at and gen_prel_*. lib/backend_arm64.mc does exactly that and proves the seam is real by producing byte-identical objects — a whole-encoder replacement rather than a per-task one. Both seams are live and neither replaces the other: a machine changes what instructions are chosen, a backend changes how they are written out.

What a runtime — rather than a backend — may rely on is the register and frame contract in objects.md § 4: parameters 1..8 in x0..x7 (9..12 at [x29 + 16 + 8*(i-8)]) untouched by the prologue, x0 untouched by the epilogue, depths in x9..x15, scratch in x8/x16/x17, x18..x28 never written, and the unconditional stp x29, x30 frame record. Every machine added here has to keep those or say plainly that it does not — they are what a #opcode syscall wrapper, an atomic and a stack walker are built on, and scripts/check-surface.sh asserts them against --dump-asm.

That contract is per machine, and the assertions are AArch64's. The RISC-V machine states its own in examples/kernel/README.md § The ABI, and examples/kernel/test.sh asserts every line of it against --dump-asm --machine=riscv64 over the whole kernel — which is what makes the two-instruction context switch in examples/kernel/lib/sched.mc legitimate rather than lucky. The x86-64 machine states its own, in the table above and in objects.md § 4b: parameters untouched in rdi rsi rdx rcx r8 r9, rax untouched by leave; ret, depths in r8..r11, scratch rax/rcx/rdx, rbx and r12..r15 never written, an unconditional push rbp; mov rbp, rsp frame record. A runtime written with #opcode is bound to one instruction set anyway.

6. The declared word (M41) #

How wide a pointer is is the one fixed decision of the core a machine may override. It is declared from user_init(), not from the task table — a width is not a task, and the walker needs the answer before it lowers the first slot:

void user_init() {
    machine_avr_init();
    type_set_width(TY_UPTR, 2);
}

type_set_width(ty, w) accepts TY_UPTR only, with w in {1, 2, 4, 8}; every other type is refused with type_set_width only declares the width of uptr (i64 folds in 64 bits at parse time and would disagree with the machine). Two functions in src/gen_walk.mc read it, and they are the whole of what follows:

Inert with nothing declared: width 8, granule 8, alignment 16, an 8-byte initializer — byte for byte what the walker did before the mechanism existed, which is what scripts/check-inert.sh proves over the whole corpus.

A machine does not have to consent to the width: it is the walker that changes, and the machine sees the smaller offsets in MTASK_LOCAL_LOAD, MTASK_LOCAL_STORE, MTASK_LOCAL_ADDR and MTASK_FRAME_FIX like any other frame. What it must do is honour them — a machine whose load instruction cannot reach an odd offset has to say so itself.

The trap, stated once: uptr t[1000] is 8000 bytes and refused as local array too large on arm64, and 2000 bytes and accepted at width 2. The same source, two answers. sizeof does not exist in this language, so a record laid out with #define offsets has to write them as N * W with a per-dialect W.

Edit this page