Compiler IR (design)¶
Status: steps 1–4, 8, 9 and 10 done; steps 5 and 7 measured and not landed. This page is the plan for giving the compiler an intermediate representation; it describes the compiler, not the language.
Where it starts¶
codegen.kod walks the AST and emits arm64 instructions into a per-function
buffer of regalloc.Insn values. Since the structured-instructions work
(522f24e … abf4e42) most of them are no longer text:
| Variant | What it is |
|---|---|
Slot(store, reg, off) |
ldr/str to a frame slot |
Mov(dst, src) |
register move |
Mem(op, reg, base, off, has_off) |
load or store through a register |
Op(mn, a, b, c, d, flags) |
any other instruction with one-token operands |
Call(target) |
bl |
Branch(op, reg, target) |
b, b.cond, cbz, cbnz |
Label(name) |
a label |
Raw(text, info) |
the rest: about 60 emit sites and the directives |
After a function is emitted, passes run over the buffer (peephole,
promote_locals, forward_copies, register allocation, long_branches), and
the buffer is printed as assembly.
This is already a low-level IR, but an arm64 one: mnemonics are arm64's, physical
registers (x0–x7 for arguments, x16/x17 as scratch, fp, sp, xzr)
are named in it, and calling, addressing and immediates follow arm64's rules.
Goal¶
A target-neutral low-level IR (LIR) in place of the arm64 instruction buffer:
- Operations, not mnemonics:
add,load64,store8,compare,branch_if(cond),call,retain,release, … with virtual registers and immediates as operands. - Roles, not registers: argument i, the result, scratch, the frame, the stack. Each target maps a role to its register.
- Lowering per target: one pass turns LIR into a target's instructions. Arm64 first, printing exactly what the compiler prints today; x86-64 later.
- Passes on LIR: the existing ones, target-neutral where they can be, plus new optimisations.
Not a goal for now: SSA, a mid-level IR between the AST and LIR, or rewriting
how codegen.kod walks the AST. Codegen keeps doing what it does; what it emits
changes.
How it gets there¶
Every step until the first optimisation keeps the output byte-identical, checked
with make asm-diff over the whole corpus, as the structured-instructions steps
were.
- Neutral operations (done).
Opholds aregalloc.Opcode(Add,Compare,SetIf,AddressPage, …),Mema direction and a width in bytes, andBranchaBranchKind(Always,If(Cond),IfZero,IfNonzero); the arm64 lowering (arm64_mnemonic,mem_mnemonic,branch_mnemonic) prints their mnemonics. Conditional branches are now always writtenb.cond, which assembles to the same bytes asbcond(checked withasm_diff --objects). Still strings: the condition operand ofSetIf,SelectandCompareIf, and the register names. - Register roles (done for the allocator). The register pools come from a
regalloc.Target(TARGET,ARM64): the caller- and callee-saved temporaries, the order the prologue saves registers in, and the argument registers. In codegen the registers it names itself stay spelled as arm64 spells them, as role names:x0–x7for arguments and the result,x16,x17andx9as scratch (x17also passes a value to the reference-counting stubs),fp,sp,xzr, andd0,d1for floats. Renaming them would decide nothing yet: what a second target needs is to tell argument 0 from the result (bothx0on arm64), and that is for its lowering, which can mapx0to its first argument register and move the result there after each call. - No text left (done).
Memaddresses through aMemAt(the base, an offset, an index register, scaled by the access size or not, or a symbol's page offset); register pairs are aPair(offset, pre- or post-index); a constant too big for one move is aLoadConst, which the line limits count as the four lines arm64 needs; an inlined runtime function is anIntrinsic(label)whose lines come from the arm64 table (arm64_intrinsic); directives and data labels areData, which no pass reads. Nothing makes instruction text any more:Raw,line_infoand the passes' text paths are gone, and anOpoperand that isn't one token is a compiler bug. Assembly text exists only at output (format_insn, andprint_encodablefor an immediate too big to encode). The symbol's page (AddressPagewith an@PAGEoperand) is still two operations and arm64's way of addressing; oneAddressOf(symbol)is left for the second target to need. - The arm64 lowering in its own module (done).
stdlib/kod/arm64.kodholds everything that writes arm64: the mnemonics and condition names, each instruction's text (format_insn, given the allocator's vreg-to-register table), the inlined runtime functions, themov/movklines for a large constant or an immediate too big to encode, andline_count.regallocholds the IR and the allocator and doesn't import it. Still in codegen and still arm64's:peephole(its patterns are neutral, but the immediates it folds are arm64's 12-bit ones) andlong_branches(arm64's 1 MB branch reach), to move behind the target when a second one exists. - Retain and release cancelling (measured, dropped). The plan was explicit
Retain(v)andRelease(v)operations and a pass cancelling a retain and a release of the same value with nothing between them that could free it. There are none to cancel: each retain copies a borrowed reference into a place that owns it (a local's slot, 58%, or a field or element, 33%), and its release comes much later, when the slot is overwritten or goes out of scope. Nor would it pay much: compilingcodegen.kodruns 46M retains and 50M releases, and with both stubs reduced to aretthe compile is only 5% faster. Most of what reference counting costs is allocating and freeing. -
Measured first. Counting how often each basic block runs, on the compiler compiling
codegen.kodand on the benchmarks, gives each candidate as a share of the instructions executed (an upper bound on the time saved: a 12% drop in instructions madeloop2% faster):Candidate compiler sieve qsort inflate Loads a loop can't change 1.5–3.6% 14% 8.6–16% 1.3–7.4% Register copies 14% 26% 16% 20% Bounds checks run 2.3% 4.7% 7.6% 3.9% Redundant loads within a block 1.8% 1.4% 0.9% 1.0% Dead stores, constant folding <0.5% 0 0 0.2%
Done from it: a frame over 256 bytes is addressed from its bottom in x28,
one instruction per slot instead of three (5% of the compiler's
instructions), and a large constant skips the movk of a zero part.
7. Loop-invariant loads (tried, not landed; branch ir-hoist-loads). After
register allocation, a load in an innermost loop moves to just before the
loop's top label when the loop is entered only there, its address doesn't
change in the loop (a frame slot it doesn't store to; a heap address whose
base it doesn't change, in a loop with no call and no heap store), a heap
load's base is one the loop's top already reads through (so it isn't read
early past a check for none), and the function leaves a register free for
it (callee-saved when the loop makes a call). The load in the loop becomes a
copy from that register. Done before allocation instead, the moved loads
took registers from promoted locals, which then went back to memory.
It made qsort and words about 2% faster and nothing else measurably, while
the pass cost 6% of compile time: the safe rules leave most of the loads
counted above in place (most hot loops store to the heap), and fewer
instructions buy less time than they suggest. Not worth it as it stands.
Register copies are the largest category but the least certain win (Apple's
cores eliminate most of them when renaming), so they were timed first, on
hand-edited output of the hottest loops of sieve and qsort:
| Hand edit | sieve | qsort |
|---|---|---|
| Copies removed (4 of 13 and 2 of 13 instructions) | −0.3% | −0.8% |
| Bounds checks also removed (length load, compare, branch) | −6.1% | −6.2% |
Copies cost next to nothing, so coalescing them isn't worth a pass. Bounds
checks cost a few percent where a hot loop indexes an array, but removing
one needs a proof that the index is in range, which neither of these loops
gives (j <= n against a length built by appends; i/j moved by the
comparisons).
Nor do most checks elsewhere. Of the 66M checks run compiling codegen.kod,
about a fifth are in a for k in a..len(x) loop that leaves x's length
alone, which a simple pass could prove; another fifth follow a test such as
i < len(s) and would need the conditions tracked. At the half a cycle a
check costs in the timed loops, removing all of them would save about 2.5%
of the compile, and the provable fifth about 0.5%; the hot checks of the
benchmarks are none of these. Not worth a pass for now.
8. Registers as numbers. An instruction's registers and Op operands are a
regalloc.Reg, an int64, instead of text: 4n+1 is vreg n (v12),
4n+2 its 32-bit form (w12), 4n+3 the immediate #n, and 4k the
kth name of a table (regalloc.NAMES): 0 is none, x0–x30, fp,
lr, sp and xzr come first, and any other operand (a condition, a
symbol's page, a negative immediate) is added the first time it's named.
Codegen still names registers as text: its emit_ functions turn each into
a Reg once (regalloc.reg_of), so the passes compare numbers instead of
parsing names, and nothing in an instruction is counted. The output turns
them back (regalloc.reg_text, arm64.phys_of). The allocator's pool,
the target's registers and each vreg's register are Regs too. Labels,
call targets, symbols in an address and directives stay text. What is
left of the text is codegen's own: alloc_reg still names a vreg v12,
and each emit_ reads the name back.
9. Machine words instead of text (done). Assembling the output
costs far more than compiling it: as takes 3.1 s on what the compiler
writes for codegen.kod in 0.22 s, and about four fifths of the gates'
CPU time. Clang's assembler spends it matching each register operand
against every kind of register name (22 µs a line); a line written as the
instruction's word, .inst 0xaa0103e0 for mov x0, x1, assembles to the
same bytes about 50 times faster. So arm64.encode gives the word of
each instruction that names only registers and immediates, and the output
writes that; anything with a label or a symbol, and any form encode
doesn't know, stays text. With KOD_ASM_TEXT set, each word is followed
by its instruction as a comment (.inst 0xaa0103e0 // mov x0, x1), for
reading the output; it is left out otherwise, since writing it and
skipping it again cost about a twentieth of a compile.
asm_diff --objects (tools/asm_diff.kod) checks the result: every
object file in the corpus must have the same bytes as when the text is
assembled.
Then the object file without as: kod/macho reads the compiler's
output (labels, the directives it writes, .inst words, and the
instructions that name a label or a symbol) and writes a Mach-O object
itself, in the compiler's own process, when link.cfg says AS := kod.
What it writes is laid out more plainly than clang's (symbols grouped and
sorted, data that points at a temporary label relocated against its
section), so the check is by meaning, not bytes: tools/as_diff.kod
assembles every file of the corpus both ways and compares each section's
bytes with the relocated fields cleared, each relocation's place, kind and
target, and the symbols. Every instruction reaches it as a word except
those, so the compiler writes the words of large constants and inlined
functions too (arm64.encode_text encodes an instruction given as text).
Then no text at all: with AS := kod, sh_kodc _compile (what kod build
runs for each module) hands each instruction to macho.Assembler.insn
instead of writing it out. A word goes into the section, a call or branch
becomes a fixup, a label is defined, and only data and directives are still
read as lines. Compiling and assembling codegen.kod went from 348 to 298 ms,
and the object has the same bytes as through the text.
The Makefile keeps clang's assembler, since it runs before any compiler of
this tree exists.
10. Copy-on-write checks out of loops (done). Arrays are values: before
an element store, emit_unique checks that the array's count is 1 and
copies it otherwise. In an innermost loop entered only at its top that
calls nothing but panics, releases and the copy, no array can gain a
holder (that takes a retain, a call) or be replaced where it's kept (the
same), so hoist_unique_checks drops the loop's checks on an array in a
local's slot the loop doesn't store to, or in a field of a struct in a
register the loop doesn't write or a slot it doesn't store to, and checks
once before the loop instead. Dropping a check that repeats one in
straight-line code (qsort's swap) was tried and gained nothing measurable.
The same reasoning moves loads: in such a loop (with the copy's check
gone too), a field and an array's header change only through a call, so
hoist_loop_loads loads them once before the loop when the base doesn't
change in it (or is reloaded before it from a slot the loop doesn't store
to), nothing in the loop stores at that offset, the loop writes the loaded
register only there, and the loop's first block reads through the base.
The values then live across the loop, which only the strict allocation of
promoted locals keeps apart, so the moved body is used only when that
succeeds. qsort is 6% faster, compiling 1% slower; unlike step 7 it moves
nothing in loops that call, and a store to the heap doesn't stop it.
11. Bounds checks out of the way (done). An index in range falls
through its check (cmp; b.hs), so the common case takes no branch;
the slow path (wrapping a negative index, or the panic) is a cold block
laid out after the next unconditional jump, a loop's after its back edge
(blocks from before a loop wait until after it). The allocator counts a
cold block's lines as its check's line, and its jump back as no loop, so
it keeps nothing live longer; the hoisting passes count a loop's cold
blocks as part of it. qsort and sieve are 6% and 9% faster, the others
about 3%.
12. Then, as needed: an x86-64 lowering (see the parked assessment: register
pools, calling convention, runtime stubs, symbol names).
Open questions¶
- Calls: today codegen moves arguments into
x0–x7itself. Roles cover that while a target has at least as many argument registers as a call needs; x86-64 has six. ACall(target, args)with the arguments as operands would let lowering place them, at the price of touching every call site. - Data: string literals, vtables, line tables and the symbol table are emitted as directives through the same buffer. They need their own representation once text goes.