Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.42.0

0.42.0 / src / back / ir / ir.lucb

#==============================================================================================
#
#   ir - The intermediate representation of the native backend
#
#   DESCRIPTION:
#       A small machine-neutral form between the checked tree and a target (base.md §19.1),
#       in the spirit of QBE: instructions over typed temporaries in four classes, `w` (32-bit
#       integer), `l` (64-bit integer or address), `s`, and `d`; stack slots for everything
#       that has an address; calls that carry enough about each argument for a target to
#       classify it. Aggregates never live in temporaries; they live in memory and are
#       moved by `blit`.
#
#       Temporaries are assigned once and used within the block that assigned them. A value
#       that must cross a block, the result of a conditional or a `match` expression, goes
#       through a slot. That keeps register allocation a per-block affair, with no dataflow
#       across the control flow graph.
#
#==============================================================================================

import memory
import support.hashed
import support.list

# mark: Classes and references =================================================================

## The register class of a temporary.
pub enum Class as u8:
    w = 1
    l = 2
    s = 3
    d = 4
    ## a half-precision float, in the low half of a `v` register
    h = 5
    ## a vector of eight or sixteen bytes (§5.12), in a vector register; its lane shape is
    ## on the instruction (`lanes`)
    v = 6

## The ten comparisons: their result is a word whatever they compare.
pub func is_comparison(op: Op) -> bool:
    return (u8)op >= (u8)Op.ceq and (u8)op <= (u8)Op.cuge

## The comparison true exactly when `op` is false, on integers (and on floats for the two
## equalities): what a fused branch tests when its fall-through is the taken side, and
## what folds `x == 0` of a comparison.
pub func negated(op: Op) -> Op:
    match op:
        .ceq: return Op.cne
        .cne: return Op.ceq
        .cslt: return Op.csge
        .csle: return Op.csgt
        .csgt: return Op.csle
        .csge: return Op.cslt
        .cult: return Op.cuge
        .cule: return Op.cugt
        .cugt: return Op.cule
        _: return Op.cult

## Whether `cls` is a float or half-precision register class.
pub func is_float_class(cls: Class) -> bool:
    return cls == Class.s or cls == Class.d or cls == Class.h

## The lane shape of a vector instruction, in its `extra`: the lanes' width in bits, how
## many, and whether they are floats and signed. A vector is `lane_bits * lane_count / 8`
## bytes: eight or sixteen.
pub func lanes(bits: u32, count: u32, is_float: bool, signed: bool) -> u32:
    return bits | (count << 8) | ((1 if is_float else 0) << 16) | ((1 if signed else 0) << 17)

## The lanes' width in bits, from a vector shape.
pub func lane_bits(shape: u32) -> u32:
    return shape & 0xFF

## How many lanes a vector shape has.
pub func lane_count(shape: u32) -> u32:
    return (shape >> 8) & 0xFF

## Whether a vector shape's lanes are floats.
pub func lanes_float(shape: u32) -> bool:
    return (shape & (1 << 16)) != 0

## Whether a vector shape's lanes are signed.
pub func lanes_signed(shape: u32) -> bool:
    return (shape & (1 << 17)) != 0

## The total byte width of a vector shape, eight or sixteen.
pub func vector_bytes(shape: u32) -> u32:
    return lane_bits(shape) * lane_count(shape) // 8

## The bytes of one level of a function's dynamic area (`Op.reserve`): a format buffer's
## 1024 characters and its 24-byte state, to sixteen.
pub let level_bytes: u32 = 1056

## Whether `op` ends a basic block: control leaves through it, or never returns.
pub func is_terminator(op: Op) -> bool:
    return op == Op.jmp or op == Op.jnz or op == Op.switch_ or op == Op.ret or op == Op.trap_

## Whether `op` computes on vectors (§5.12), lane shape in `extra`.
pub func is_vector_op(op: Op) -> bool:
    return ((u8)op >= (u8)Op.loadv and (u8)op <= (u8)Op.vsplat) or ((u8)op >= (u8)Op.vinsert and (u8)op <= (u8)Op.vtruncd)

## What an operand refers to.
pub enum RefKind as u8:
    none_ = 0
    temp = 1
    constant = 2
    slot = 3
    global = 4
    function = 5
    text = 6

## An operand: a temporary, a constant, the address of a slot, global, function, or text.
pub struct Ref:
    ## What the operand refers to.
    pub var kind: RefKind
    ## The temporary, slot, or text index; unused for the rest.
    pub var index: u32
    ## A constant's value, or 1 marking an imported global.
    pub var value: i64
    ## The symbol of a global or function; the bytes of a text literal.
    pub var name: str

## No operand.
pub func none_ref() -> Ref:
    return Ref(kind = RefKind.none_, index = 0, value = 0, name = "")

## The temporary numbered `index`.
pub func temp_ref(index: u32) -> Ref:
    return Ref(kind = RefKind.temp, index = index, value = 0, name = "")

## The integer constant `value`.
pub func const_ref(value: i64) -> Ref:
    return Ref(kind = RefKind.constant, index = 0, value = value, name = "")

## The address of slot `index`.
pub func slot_ref(index: u32) -> Ref:
    return Ref(kind = RefKind.slot, index = index, value = 0, name = "")

## The address of the global named `name`.
pub func global_ref(name: str) -> Ref:
    return Ref(kind = RefKind.global, index = 0, value = 0, name = name)

## A data symbol another image defines, `__stderrp` or an `extern var`: reached through the
## GOT, since a direct page address to a dylib's data does not link.
pub func import_ref(name: str) -> Ref:
    return Ref(kind = RefKind.global, index = 0, value = 1, name = name)

## The address of the function named `name`.
pub func function_ref(name: str) -> Ref:
    return Ref(kind = RefKind.function, index = 0, value = 0, name = name)

## The address of text literal `index`.
pub func text_ref(index: u32) -> Ref:
    return Ref(kind = RefKind.text, index = index, value = 0, name = "")

# mark: Instructions ===========================================================================
pub enum Op as u8:
    ## `dst = a`
    copy = 1
    ## integer and float arithmetic on the class of `dst`
    add = 10
    sub = 11
    mul = 12
    sdiv = 13
    udiv = 14
    srem = 15
    urem = 16
    and_ = 17
    or_ = 18
    xor = 19
    ## shifts read the count's low five (`w`) or six (`l`) bits, of either integer class,
    ## as every target's shift instruction does; the lowering traps on a count past them
    shl = 20
    lshr = 21
    ashr = 22
    neg = 23
    ## the float functions of the C library a target computes in one instruction
    ## (`isa.float_function`), on the single or double `cls`, bit for bit as the library:
    ## the square root, rounding toward negative infinity, toward positive infinity, toward
    ## zero, to nearest with halves away from zero (C's `round`), and the magnitude
    fsqrt = 24
    ffloor = 25
    fceil = 26
    ftrunc = 27
    fround = 28
    fabs = 29
    ## comparisons: `dst` is `w`, 1 or 0; the class on the instruction is the operands'
    ceq = 30
    cne = 31
    cslt = 32
    csle = 33
    csgt = 34
    csge = 35
    cult = 36
    cule = 37
    cugt = 38
    cuge = 39
    ## loads: `a` is an address; the width and extension are in the op
    loadsb = 40
    loadub = 41
    loadsh = 42
    loaduh = 43
    loadsw = 44
    loaduw = 45
    loadl = 46
    loads = 47
    loadd = 48
    ## `dst = load [a]`, a half float
    loadhf = 49
    ## stores: `a` is the value, `b` the address
    storeb = 50
    storeh = 51
    storew = 52
    storel = 53
    stores = 54
    stored = 55
    ## `store a -> [b]`, a half float
    storehf = 56
    ## conversions between classes
    extsb = 60
    extub = 61
    extsh = 62
    extuh = 63
    extsw = 64
    extuw = 65
    exts = 66
    truncd = 67
    stosi = 68
    stoui = 69
    dtosi = 70
    dtoui = 71
    swtof = 72
    uwtof = 73
    sltof = 74
    ultof = 75
    cast = 76
    ## a half to the single or double `cls`; a single to a half
    exth = 77
    truncs = 78
    ## `dst = address of a` (a slot, global, function, or text)
    addr = 80
    ## `blit a <- b, extra bytes`: copy memory
    blit = 81
    ## `zero a, extra bytes`
    zero = 82
    ## `fill a, extra bytes` with the byte constant `b`: the diagnostic profile's pattern
    fill = 83
    ## `call`: `a` is the callee, arguments follow in the function's argument list
    call = 90
    ## `dst = word extra`: word `extra` of the result of the call just before, which comes
    ## back in registers (`CallInfo.result_words`), a float word (class `s` or `d`) in the
    ## next float result register and any other in the next integer one; a call's words
    ## follow it directly, every one of them in order, and the generator moves them all out
    ## as the call returns.
    ## `extra2` is 1 for a failure flag, which is 0 or 1.
    word = 92
    ## `dst = phi` at a block's head: the value from each predecessor, in `phi_args` from
    ## `extra` for `extra2` entries. Only the optimiser's passes see phis: `dessa` turns
    ## them into copies before a generator does.
    phi = 91
    ## control: `label extra`, `jmp extra`, `jnz a, extra (then), value (else)`, `ret [a]`;
    ## a `ret` with `extra2` words returns the arguments from index `extra` of the
    ## function's `args` as the words of a private result (`Function.result_private`)
    label = 100
    jmp = 101
    jnz = 102
    ret = 103
    ## `trap a` where `a` names the reason text
    trap_ = 104
    ## `check a < b` else trap "index out of bounds"; `a <= b` when `extra` is 1, the
    ## one-past-the-end bound of `&owner[i]` and of a slice's ends, which `b + 1` would wrap
    bounds = 105
    ## `switch a, extra (default), table extra2`: a jump through table `extra2` of the
    ## function's `jump_tables` to the label of entry `a - low`, computed at the class of the
    ## instruction; to `extra` when that is not below the table's `count` (unsigned)
    switch_ = 106
    ## `arith` variants that trap on overflow: `dst = a op b` with the op in `extra`
    addo = 110
    subo = 111
    mulo = 112
    ## `addr_tls`: `dst = address of the thread-local global a`
    addr_tls = 113
    ## `asm a, b`: architecture text `a`, raw lines `b`, no operands
    asm_ = 114
    ## atomics: `extra` is the width in bytes, `extra2` the C memory order;
    ## `atomic_load dst <- [a]`, `atomic_store a -> [b]`, read-modify-write `dst = old; [b] op= a`,
    ## `atomic_cas dst = old; expected and desired are args from index b.value`
    atomic_load = 120
    atomic_store = 121
    atomic_add = 122
    atomic_sub = 123
    atomic_or = 124
    atomic_and_not = 125
    atomic_xor = 126
    atomic_swap = 127
    atomic_max = 128
    atomic_min = 129
    atomic_cas = 130
    ## `fence a`: a full fence with the C memory order in `a`
    fence = 131
    ## Vectors (§5.12): the lanes compute exactly as the scalar operators would, and a
    ## checked lane's overflow traps. `loadv`/`storev` move the shape's bytes; `vshl`/`vshr`
    ## take a scalar count in `b`, already checked against the lane width; `vsplat` takes a
    ## scalar of the lane's class in `a`.
    loadv = 140
    storev = 141
    vadd = 142
    vsub = 143
    vmul = 144
    vdiv = 145
    vand = 146
    vor = 147
    vxor = 148
    vneg = 149
    vnot = 150
    vaddw = 151
    vsubw = 152
    vmulw = 153
    vaddo = 154
    vsubo = 155
    vadds = 156
    vsubs = 157
    vshl = 158
    vshr = 159
    vsplat = 160
    ## `--release --debug`: from here, named local `extra` (an index into `locals`) holds
    ## `a`, a temporary or a constant, until the next `dbg` of it or the end of the
    ## temporary's life; no code, no use of `a` (`ssa.promote` places them, the DWARF
    ## emitter reads them)
    dbg = 161
    ## `fma dst = a * b + c`, rounded once (`mul_add`, §7.2): `c` is the argument at index
    ## `extra2`; `extra` is a vector's lane shape and 0 for a scalar of class `cls`
    fma = 162
    ## `dst = select a, b, c`: `b` when the word `a` is not 0, else `c`, the argument at
    ## index `extra2`; neither is evaluated for it, both are values already (`ifconvert`)
    select = 163
    ## `reserve extra`: from here the dynamic area below the fixed frame holds `extra`
    ## levels of `level_bytes` each (0: none), and the stack pointer is below them, so the
    ## calls made meanwhile leave them be; a statement's format buffers live in its levels.
    reserve = 107
    ## `dst = alloca a`: the stack pointer moves down by `a` bytes, a multiple of sixteen and
    ## at most 4096, the new bottom is touched, and `dst` is its address: storage in the
    ## function's frame until it returns (`memory.frame`, §12.7). The bytes the function's
    ## calls pass on the stack go below it.
    alloca = 108
    ## Lanes the optimiser packs from scalars (`opt/slp`), lane `extra2` of a vector of
    ## shape `extra`: `vinsert dst = a with lane extra2 set to the scalar b` (`a` none: the
    ## other lanes are anything), `vextract dst = lane extra2 of a`, at the lane's class, and
    ## `vsqrt dst = the square root of every lane of a`, as `fsqrt` computes each.
    vinsert = 164
    vextract = 165
    vsqrt = 166
    ## Two lanes between widths, as `exts` and `truncd` convert each: `vexts dst = the
    ## singles of a as doubles`, `vtruncd dst = the doubles of a as singles`; `extra` is the
    ## result's shape.
    vexts = 167
    vtruncd = 168
    ## The frame pointer of the running function, for the debugger.
    frame = 200
    ## Inline assembly operands: `set_reg a -> named register b` before an `asm` block,
    ## `get_reg [a] <- named register b` after it; `cls` is the width.
    set_reg = 210
    get_reg = 211

## The instructions of a function, as it holds them and as the inliner rebuilds them.
pub type Instrs = list.List[Instr]

## One instruction. `dst` is 0 when there is none. `extra` carries a label, a
## byte count, or a call's argument range.
pub struct Instr:
    ## The operation.
    pub var op: Op
    ## The class of `dst` and of the operation.
    pub var cls: Class
    ## The result temporary, 0 for none.
    pub var dst: u32
    ## The first operand.
    pub var a: Ref
    ## The second operand.
    pub var b: Ref
    ## A label, a byte count, or a call's argument range.
    pub var extra: u32
    ## A branch's else label, or a second count.
    pub var extra2: u32
    ## The source line and file (an index into the unit's `files`, 1-based, 0 for none)
    ## the instruction came from, for the line table of an optimised build (`--release
    ## --debug`); the passes carry them with the instruction.
    pub var line: u32
    ## The file the line refers to, an index into the unit's `files`.
    pub var file: u32
    ## The lexical scope (an index into the function's `debug_scopes`, 0 for the function's
    ## own) the instruction came from; the passes carry it, and a build with symbols
    ## describes each scope's locals over the addresses its instructions reach.
    pub var scope: u32
    ## The inlined subroutine (an index into the function's `sites`, 1-based, 0 for the
    ## function's own body) the instruction came from, the same way.
    pub var site: u32

## Whether `instruction`, a `bounds` or checked operation, names its statement's position
## text in `extra2` (the text's index + 1) for the trap it may raise; 0 names none.
pub func positioned(instruction: Instr) -> bool:
    let op = instruction.op
    return (op == Op.bounds or op == Op.addo or op == Op.subo or op == Op.mulo or op == Op.vaddo or op == Op.vsubo) and instruction.extra2 > 0

## `words` in ascending order: a bottom-up merge sort, n log n, in the heap (the compiler's
## sources keep to what the seed's library has, which has no sort).
func sort_words(words: u64[]) -> !:
    let n = words.length
    with memory.heap:
        var other = try new u64[n] ---
        defer free(other)
        var source = words
        var target = other
        var width: usize = 1
        while width < n:
            var start: usize = 0
            while start < n:
                let middle = start + width if start + width < n else n
                let end = start + 2 * width if start + 2 * width < n else n
                var i = start
                var j = middle
                var k = start
                while k < end:
                    if i < middle and (j >= end or source[i] <= source[j]):
                        target[k] = source[i]
                        i += 1
                    else:
                        target[k] = source[j]
                        j += 1
                    k += 1
                start = end
            let swap = source
            source = target
            target = swap
            width *= 2
        if source.data != words.data:
            memory.copy(words, source, n)

## One scalar member of an aggregate, wherever it lies: what a calling convention reads to
## classify the aggregate. A union's members overlap; padding has no leaf.
pub struct Leaf:
    ## The member's byte offset in the aggregate.
    pub var offset: u32
    ## The member's size in bytes.
    pub var size: u8
    ## The member's register class.
    pub var cls: Class

## An aggregate's leaves, as a range of the unit's `leaves`; shape 0 is no shape, the
## aggregate is passed in memory whatever the convention.
pub struct Shape:
    ## The first leaf's index in the unit's `leaves`.
    pub var start: u32
    ## How many leaves the shape has.
    pub var count: u32

## One argument of a call: the operand, its class, and for an aggregate its byte size,
## alignment, and shape (0 size means a scalar). The convention is the target's: the IR
## says what the value is made of, and the generator decides where it goes.
pub struct Arg:
    ## The argument operand.
    pub var value: Ref
    ## The argument's register class.
    pub var cls: Class
    ## The aggregate's byte size, 0 for a scalar.
    pub var size: u32
    ## The aggregate's alignment.
    pub var align: u32
    ## The argument's type.
    pub var type_id: u32
    ## The aggregate's shape (1-based), 0 for none.
    pub var shape: u32
    ## Scalar storage width before register promotion; zero uses the IR class width.
    ## Apple arm64 packs fixed stack arguments using this width, even for i8/u16.
    pub var scalar_width: u32

## A call's result: a scalar class, or an aggregate written to `slot` of `size` bytes.
pub struct CallInfo:
    ## The first argument's index in the function's `args`.
    pub var args_start: u32
    ## How many arguments the call passes.
    pub var args_count: u32
    ## How many arguments are fixed, before any variadic tail.
    pub var fixed_count: u32
    ## Whether the call is variadic.
    pub var variadic: bool
    ## The result's register class.
    pub var result_cls: Class
    ## Whether the call returns a value.
    pub var has_result: bool
    ## The result's byte size, 0 for a scalar.
    pub var result_size: u32
    ## The result's alignment.
    pub var result_align: u32
    ## The result's type.
    pub var result_type: u32
    ## The slot an aggregate result is written into.
    pub var result_slot: u32
    ## The result aggregate's shape (1-based), 0 for none.
    pub var result_shape: u32
    ## Whether the result comes back in the program's own convention rather than the C one:
    ## a fallible result or a tuple of at most four words, each word holding one float in
    ## the next of the first four float result registers (d0-d3, or xmm0-xmm3) and any other
    ## in the next of the first four integer ones (x0-x3, or rax, rdx, rcx and r8), never
    ## through a hidden pointer (`Unit.word_class`). Nothing outside the program calls a
    ## function whose result is either: neither is C-representable (§17.6's status form
    ## wraps a fallible export).
    pub var result_private: bool = false
    ## Whether the private result's words are left in their registers for the `word`
    ## instructions right after the call, which store them to `result_slot`: the call
    ## itself writes no memory for its result.
    pub var result_words: bool = false

## The jump table of a `switch`: its labels are `jump_labels[start ..< start + count]`,
## entry `k` for the value `low + k`.
pub struct Table:
    ## The value of the first entry.
    pub var low: i64
    ## The first label's index in the function's `jump_labels`.
    pub var start: u32
    ## How many entries the table has.
    pub var count: u32

## A stack slot: `size` bytes at `align`.
pub struct Slot:
    ## The slot's size in bytes.
    pub var size: u32
    ## The slot's alignment.
    pub var align: u32
    ## 0 for a slot of the fixed frame; `k` for one in level `k` of the dynamic area below
    ## it (`Op.reserve`), at `offset` bytes into the level.
    pub var level: u32 = 0
    ## Where in its level a dynamic slot starts.
    pub var offset: u32 = 0

## A parameter as the function receives it.
pub struct Param:
    ## The parameter's register class.
    pub var cls: Class
    ## The parameter's byte size, 0 for a scalar.
    pub var size: u32
    ## The parameter's alignment.
    pub var align: u32
    ## The parameter's type.
    pub var type_id: u32
    ## The slot the parameter is stored into on entry.
    pub var slot: u32
    ## The parameter aggregate's shape (1-based), 0 for none.
    pub var shape: u32
    ## The scalar storage width before promotion; 0 uses the class width.
    pub var scalar_width: u32
    ## Whether the scalar parameter is signed.
    pub var scalar_signed: bool

## The class a load produces.
pub func load_class(op: Op) -> Class:
    match op:
        .loadsb, .loadub, .loadsh, .loaduh, .loaduw: return Class.w
        .loadsw, .loadl: return Class.l
        .loads: return Class.s
        .loadhf: return Class.h
        _: return Class.d

## The class a store writes: `w` for the narrow integer stores, as wide as a word.
pub func store_class(op: Op) -> Class:
    match op:
        .storeb, .storeh, .storew: return Class.w
        .stores: return Class.s
        .stored: return Class.d
        .storehf: return Class.h
        _: return Class.l

## The class a float conversion reads: `exth` a half, `exts` and `truncs` a single, `truncd` a double.
pub func float_source_class(op: Op) -> Class:
    match op:
        .exth: return Class.h
        .exts, .truncs: return Class.s
        _: return Class.d

## The class whose bits `cast` moves into `cls`: the integer as wide as a float, and back.
pub func cast_partner(cls: Class) -> Class:
    match cls:
        .h, .s: return Class.w
        .d: return Class.l
        .w: return Class.s
        _: return Class.d

# mark: Functions and the unit ================================================================

## One incoming value of a phi: what the block whose label is `pred` supplies.
pub struct PhiArg:
    ## The value this predecessor supplies.
    pub var value: Ref
    ## The predecessor block's label.
    pub var pred: u32

## A named local as the debugger sees it (`--debug`): its slot, its type's spelling.
pub struct LocalInfo:
    ## The local's name.
    pub var name: str
    ## The slot the local lives in.
    pub var slot: u32
    ## The local's type, spelled for the debugger.
    pub var kind: str
    ## The local's byte size.
    pub var size: u32
    ## The local's type.
    pub var type_id: u32
    ## The line the local is declared on.
    pub var line: u32
    ## Whether the local is a parameter.
    pub var parameter: bool
    ## The lexical scope the local belongs to.
    pub var scope: usize
    ## The inlined subroutine the local belongs to (`Instr.site`), 0 for the function's own.
    pub var site: u32

## A statement boundary the in-program debugger stops at (`--debug`).
pub struct DebugPoint:
    ## The instruction index the statement begins at.
    pub var instruction: usize
    ## The statement's source file.
    pub var file: str
    ## The statement's line.
    pub var line: u32
    ## The statement's column.
    pub var column: u32

## A lexical scope (`--debug`), for the locals visible within it.
pub struct DebugScope:
    ## The enclosing scope's index, 0 for the function's own.
    pub var parent: usize
    ## The instruction index the scope opens at.
    pub var start: usize
    ## The instruction index the scope closes at.
    pub var end: usize
    ## The inlined subroutine the scope belongs to (`Instr.site`), 0 for the function's own.
    pub var site: u32

## A call a build with symbols opened out (`opt/inline.lucb`): the callee, for its abstract
## description, and where the call was, for the inlined subroutine's own.
pub struct InlineSite:
    ## The callee's name.
    pub var name: str
    ## The callee's source file.
    pub var source: str
    ## The line the callee is declared on.
    pub var line: u32
    ## The callee's result type.
    pub var result_type: u32
    ## The line and file (`Instr.file`) of the call.
    pub var call_line: u32
    ## The file of the call, 0 for the caller's own source.
    pub var call_file: u32
    ## The caller's scope the call was in.
    pub var scope: u32
    ## The site the call itself was in, 0 for the caller's own body.
    pub var parent: u32

## One lowered function: its instructions, slots and temporaries, with the metadata the generators and the debugger need.
pub struct Function:
    ## The function's symbol.
    pub var name: str
    ## Whether the function has C linkage (§9.8).
    pub var exported: bool
    ## Optional standard modules must not impose link dependencies on every program.
    pub var standard: bool
    ## The package its declaration belongs to (`(standard)` for the standard library's),
    ## empty for a function the lowerer makes of its own: a function called from one place
    ## only is expanded there when that place is in its own package, or in such a function
    ## (`inline`).
    pub var package: str = ""
    ## `--debug`: the source file, and every named local for the frame's descriptor.
    pub var debug: bool
    ## `--release --debug`: DWARF for the optimised function, lines on every instruction,
    ## the named locals pinned to their slots; no hooks, no descriptor.
    pub var symbols: bool
    ## The position `emit` stamps on each instruction.
    pub var at_line: u32
    ## The file `emit` stamps on each instruction.
    pub var at_file: u32
    ## The scope the lowerer is in, stamped on each instruction it emits (`Instr.scope`).
    pub var at_scope: u32
    ## The function's source file.
    pub var source: str
    ## The function's source-level name.
    pub var source_name: str
    ## The line the function is declared on.
    pub var source_line: u32
    ## The statement boundaries, for the in-program debugger.
    pub var points: list.List[DebugPoint]
    ## The lexical scopes.
    pub var debug_scopes: list.List[DebugScope]
    ## The calls the inliner opened out in a build with symbols, 1-based by `Instr.site`.
    pub var sites: list.List[InlineSite]
    ## The named locals.
    pub var locals: list.List[LocalInfo]
    ## The parameters as received.
    pub var params: list.List[Param]
    ## The stack slots.
    pub var slots: list.List[Slot]
    ## The instructions, in order.
    pub var instrs: list.List[Instr]
    ## The call arguments and atomic operands, pooled.
    pub var args: list.List[Arg]
    ## The call descriptions, indexed by `Instr.extra`.
    pub var calls: list.List[CallInfo]
    ## The class of each temporary, by index.
    pub var temps: list.List[Class]
    ## The phi arguments, pooled.
    pub var phi_args: list.List[PhiArg]
    ## The jump tables of the `switch` instructions, indexed by `Instr.extra2`.
    pub var jump_tables: list.List[Table]
    ## The jump tables' labels, pooled.
    pub var jump_labels: list.List[u32]
    ## How many labels have been handed out.
    pub var labels: u32
    ## The most levels the dynamic area below the frame holds (`Op.reserve`).
    pub var dynamic_levels: u32 = 0
    ## Whether the function takes storage from its frame as it runs (`Op.alloca`): its stack
    ## pointer then moves by amounts only known at run time.
    pub var allocates_frame: bool = false
    ## Whether the function returns a value.
    pub var has_result: bool
    ## The result's register class.
    pub var result_cls: Class
    ## The result's byte size, 0 for a scalar.
    pub var result_size: u32
    ## The result's alignment.
    pub var result_align: u32
    ## The result's type.
    pub var result_type: u32
    ## The result aggregate's shape (1-based), 0 for none.
    pub var result_shape: u32
    ## Whether the result goes back in the program's own convention (CallInfo.result_private).
    pub var result_private: bool = false
    ## Whether the function is variadic.
    pub var variadic: bool
    ## The attributes of §9.8 that reach the object file.
    pub var naked: bool
    ## Whether the symbol is weak (§9.8).
    pub var weak: bool
    ## Whether the symbol is retained even if unreferenced (§9.8).
    pub var used: bool
    ## The section the function is placed in, empty for the default.
    pub var section: str
    ## `noinline`: the body stands in for no call of it (§9.8).
    pub var noinline: bool
    ## `inline`: the body stands in for every call of it that can be expanded, whatever its
    ## size up to `opt/inline`'s `forced` (§9.8).
    pub var always_inline: bool = false

    ## An empty function named `name`.
    pub static func create(name: str) -> Function!:
        return Function(name = name, exported = false, debug = false, symbols = false, at_line = 0, at_file = 0, at_scope = 0, source = "", source_name = name, source_line = 1, points = try list.List[DebugPoint].create(0), debug_scopes = try list.List[DebugScope].create(0), sites = try list.List[InlineSite].create(0), locals = try list.List[LocalInfo].create(8),
                        params = try list.List[Param].create(8),
                        slots = try list.List[Slot].create(32), instrs = try list.List[Instr].create(256),
                        args = try list.List[Arg].create(32), calls = try list.List[CallInfo].create(16),
                        temps = try list.List[Class].create(128), phi_args = try list.List[PhiArg].create(16), jump_tables = try list.List[Table].create(0), jump_labels = try list.List[u32].create(0), labels = 0, has_result = false,
                        result_cls = Class.l, result_size = 0, result_align = 0, result_type = 0,
                        result_shape = 0, variadic = false)

    ## Free the function's lists, when it is dropped from its unit.
    pub func destroy():
        self.points.destroy()
        self.debug_scopes.destroy()
        self.sites.destroy()
        self.locals.destroy()
        self.params.destroy()
        self.slots.destroy()
        self.instrs.destroy()
        self.args.destroy()
        self.calls.destroy()
        self.temps.destroy()
        self.phi_args.destroy()
        self.jump_tables.destroy()
        self.jump_labels.destroy()

    ## A fresh temporary of class `cls`; its 1-based number.
    pub func temp(cls: Class) -> u32!:
        try self.temps.push(cls)
        return u32(self.temps.count)

    ## The class of temporary `index`.
    pub func temp_class(index: u32) -> Class:
        return self.temps.get((usize)index - 1)

    ## A fresh slot of `wanted` bytes at `align`; its index.
    pub func slot(wanted: u32, align: u32) -> u32!:
        # an aggregate that travels in two registers lands as two words
        let size = 16 if wanted > 8 and wanted < 16 else wanted
        try self.slots.push(Slot(size = size if size > 0 else 1, align = align if align > 0 else 1))
        return u32(self.slots.count - 1)

    ## A slot of `size` bytes at `offset` into level `level` of the dynamic area: the
    ## stack pointer moves below it while the level is reserved, rather than the fixed
    ## frame keeping its bytes for the whole call (a format buffer of an error path in a
    ## recursive function).
    pub func dynamic_slot(level: u32, offset: u32, size: u32, align: u32) -> u32!:
        try self.slots.push(Slot(size = size, align = align, level = level, offset = offset))
        self.dynamic_levels = level if level > self.dynamic_levels else self.dynamic_levels
        return u32(self.slots.count - 1)

    ## A fresh label number.
    pub func label() -> u32:
        self.labels += 1
        return self.labels

    ## Append an instruction, stamping the current source position on it.
    pub func emit(op: Op, cls: Class, dst: u32, a: Ref, b: Ref, extra: u32) -> !:
        try self.instrs.push(Instr(op = op, cls = cls, dst = dst, a = a, b = b, extra = extra, extra2 = 0, line = self.at_line, file = self.at_file, scope = self.at_scope, site = 0))

    ## `dst = op a, b` with a fresh temporary.
    ## `dst = a op b` at class `cls`; a comparison compares at `cls` and answers a word.
    pub func binary(op: Op, cls: Class, a: Ref, b: Ref) -> Ref!:
        let t = try self.temp(Class.w if is_comparison(op) else cls)
        try self.emit(op, cls, t, a, b, 0)
        return temp_ref(t)

    ## `dst = op a` at class `cls`, into a fresh temporary.
    pub func unary(op: Op, cls: Class, a: Ref) -> Ref!:
        let t = try self.temp(cls)
        try self.emit(op, cls, t, a, none_ref(), 0)
        return temp_ref(t)

    ## Mark where label `label` lands.
    pub func place_label(label: u32) -> !:
        try self.emit(Op.label, Class.l, 0, none_ref(), none_ref(), label)

    ## An unconditional jump to `label`.
    pub func jump(label: u32) -> !:
        try self.emit(Op.jmp, Class.l, 0, none_ref(), none_ref(), label)

    ## Branch on `condition` being nonzero, tested at its own width: a pointer's low word
    ## may be zero while the pointer is not.
    pub func branch(condition: Ref, then_label: u32, else_label: u32) -> !:
        var cls = Class.l
        if condition.kind == RefKind.temp and (usize)condition.index <= self.temps.count:
            cls = self.temps.get((usize)condition.index - 1)
        try self.instrs.push(Instr(op = Op.jnz, cls = cls, dst = 0, a = condition, b = none_ref(), extra = then_label, extra2 = else_label, line = 0, file = 0, scope = 0, site = 0))

    ## Jump to `labels[value - low]`, or to `default` when `value - low`, at class `cls`, is
    ## not below the number of labels (compared unsigned).
    pub func switch(value: Ref, cls: Class, low: i64, labels: u32[], default: u32) -> !:
        try self.jump_tables.push(Table(low = low, start = u32(self.jump_labels.count), count = u32(labels.length)))
        for label in labels:
            try self.jump_labels.push(label)
        try self.instrs.push(Instr(op = Op.switch_, cls = cls, dst = 0, a = value, b = none_ref(), extra = default, extra2 = u32(self.jump_tables.count - 1), line = self.at_line, file = self.at_file, scope = self.at_scope, site = 0))

    ## The labels of jump table `index`.
    pub func table_targets(index: u32) -> u32[]:
        let t = self.jump_tables.get((usize)index)
        return self.jump_labels.span()[(usize)t.start..<(usize)(t.start + t.count)]

    ## Load through `address` with `op`, into a fresh temporary.
    pub func load(op: Op, cls: Class, address: Ref) -> Ref!:
        let t = try self.temp(cls)
        try self.emit(op, cls, t, address, none_ref(), 0)
        return temp_ref(t)

    ## Store `value` through `address` with `op`.
    pub func store(op: Op, value: Ref, address: Ref) -> !:
        try self.emit(op, Class.l, 0, value, address, 0)

    ## The address of what `r` refers to, in a fresh temporary.
    pub func address_of(r: Ref) -> Ref!:
        let t = try self.temp(Class.l)
        try self.emit(Op.addr, Class.l, t, r, none_ref(), 0)
        return temp_ref(t)

    ## Copy `size` bytes from `source` to `target`.
    pub func copy_bytes(target: Ref, source: Ref, size: u32) -> !:
        try self.emit(Op.blit, Class.l, 0, target, source, size)

    ## Zero `size` bytes at `target`.
    pub func zero_bytes(target: Ref, size: u32) -> !:
        try self.emit(Op.zero, Class.l, 0, target, none_ref(), size)

## A text literal of the unit, emitted once with a NUL after it.
pub struct Text:
    ## The literal's bytes.
    pub var bytes: str

## Data for a global: its symbol, its size, its alignment, and whether it is thread-local.
pub struct Global:
    ## The global's symbol.
    pub var name: str
    ## Whether it belongs to a standard module.
    pub var standard: bool
    ## The global's byte size.
    pub var size: u32
    ## The global's alignment.
    pub var align: u32
    ## Whether it is thread-local.
    pub var is_thread_local: bool
    ## Whether it has C linkage.
    pub var exported: bool
    ## Whether the symbol is weak.
    pub var weak: bool
    ## Whether it is retained even if unreferenced.
    pub var used: bool
    ## The section it is placed in, empty for the default.
    pub var section: str
    ## `linked`: another object defines the storage; the program only refers to it.
    pub var external: bool
    ## A standard global's initialiser, a function of its own that `lb_init_globals`
    ## calls, so the pruner keeps it with the global; empty for the rest.
    pub var init_function: str = ""
    ## The bytes the global starts with, when its initialiser is literals laid out at
    ## compile time (`Lowerer.static_data`): the object holds them and no code stores them.
    ## None for storage that starts zero or is given its value by an initialiser.
    pub var data: u8[]? = none
    ## Whether `data` is a top-level `let`'s, which the object keeps read-only.
    pub var read_only: bool = false

## A witness table: the symbol and the functions it points at, in requirement order.
pub struct WitnessTable:
    ## The table's symbol.
    pub var name: str
    ## The function symbols, in requirement order.
    pub var entries: list.List[str]

## The whole program as the target sees it.
pub struct Unit:
    ## The program's functions.
    pub var functions: list.List[Function]
    ## The source files instructions name by index (`Instr.file`), 1-based.
    pub var files: list.List[str]
    ## The program's globals.
    pub var globals: list.List[Global]
    ## The program's text literals.
    pub var texts: list.List[Text]
    ## Where each text of `texts` is, by its bytes.
    var text_index: hashed.Table[str]
    ## The witness tables.
    pub var tables: list.List[WitnessTable]
    ## Module-level `asm` blocks for this target, verbatim (§8.9).
    pub var module_asm: list.List[Text]
    ## The shapes of the aggregates passed and returned, and their leaves.
    pub var shapes: list.List[Shape]
    ## The aggregate members, referenced by shapes.
    pub var leaves: list.List[Leaf]
    ## The function the loader runs when the image is loaded, empty when there is none:
    ## a library's initialiser (§17.6). The generator places it in its object format's
    ## initialiser section.
    pub var init_function: str
    ## The function a `trap` or a failed `bounds` calls with the reason's text: named here
    ## so the generators spell no symbol of the program, and the inliner keeps it.
    pub var trap_function: str
    ## The same with the position first (§11.5): `trap_at(position, reason)` and, for an
    ## assertion whose message is computed, `trap_two_at(position, reason, detail)`.
    pub var trap_at_function: str
    ## The function for an assertion whose message is computed (`trap_two_at`).
    pub var trap_two_at_function: str

    ## An empty unit.
    pub static func create() -> Unit!:
        return Unit(functions = try list.List[Function].create(64), files = try list.List[str].create(8), globals = try list.List[Global].create(32),
                    texts = try list.List[Text].create(64), tables = try list.List[WitnessTable].create(16),
                    module_asm = try list.List[Text].create(4), shapes = try list.List[Shape].create(64), leaves = try list.List[Leaf].create(256),
                    init_function = "", trap_function = "", trap_at_function = "", trap_two_at_function = "", text_index = try hashed.Table[str].create(64))

    ## Which functions `marked` marks or one of those calls: the functions whose optimised
    ## bodies the marked ones' expansions read (`inline.expand_small`), in the heap.
    pub func called_by(marked: const bool[]) -> bool[]!:
        let n = self.functions.count
        with memory.heap:
            var names = try hashed.Table[str].create(n)
            defer names.destroy()
            for i in 0..<n:
                _ = try names.add(self.functions.items[i].name, i)
            var reached = try new bool[n] ---
            for i in 0..<n:
                reached[i] = marked[i]
            for i in 0..<n:
                if not marked[i]:
                    continue
                for x in self.functions.items[i].instrs.span():
                    if x.op == Op.call and x.a.kind == RefKind.function:
                        if let g = names.find(x.a.name):
                            reached[g] = true
            return reached

    ## The first `n` functions, the most instructions first (by index among equals), in
    ## the heap: the order threads take them in (`parallel.each_ordered`), so that no
    ## large one starts last and keeps one thread busy after the others are done.
    pub func largest_first(n: usize) -> usize[]!:
        with memory.heap:
            var keys = try new u64[n] ---
            defer free(keys)
            for i in 0..<n:
                let size = self.functions.items[i].instrs.count
                let clamped = (u64)size if size < 0xFFFFFFFF else 0xFFFFFFFF
                keys[i] = ((0xFFFFFFFF - clamped) << 32) | (u64)i
            try sort_words(keys)
            var order = try new usize[n] ---
            for i in 0..<n:
                order[i] = (usize)(keys[i] & 0xFFFFFFFF)
            return order

    ## The index of a source file in `files`, adding it when new; 1-based.
    pub func file_index(path: str) -> u32!:
        var i: usize = 0
        while i < self.files.count:
            if self.files.get(i) == path:
                return u32(i + 1)
            i += 1
        try self.files.push(path)
        return u32(self.files.count)

    ## The index of a text literal, adding it when new.
    ## The leaves of shape `shape` (1-based), empty for 0.
    pub func leaves_of(shape: u32) -> Leaf[]:
        if shape == 0 or (usize)shape > self.shapes.count:
            return self.leaves.span()[..<0]
        let s = self.shapes.get((usize)shape - 1)
        return self.leaves.span()[(usize)s.start..<(usize)(s.start + s.count)]

    ## The class word `k` (bytes `8k ..< 8k + 8`) of an aggregate of shape `shape` travels
    ## in when the aggregate comes back in registers word by word: `d` or `s` when the word
    ## holds one float leaf, at its start, and nothing else, in a float register; `l` for
    ## any other word, in an integer one. The program's own convention (`CallInfo.
    ## result_private`) takes every word so, and System V's eightbytes agree where it
    ## returns them a word at a time.
    pub func word_class(shape: u32, k: u32) -> Class:
        let low = k * 8
        var found = Class.l
        var count: u32 = 0
        for leaf in self.leaves_of(shape):
            if leaf.offset < low + 8 and leaf.offset + (u32)leaf.size > low:
                count += 1
                found = leaf.cls if leaf.offset == low and (leaf.cls == Class.d or leaf.cls == Class.s) else Class.l
        return found if count == 1 else Class.l

    ## Record a shape from the leaves pushed since `start`; its 1-based index.
    pub func shape_from(start: usize) -> u32!:
        try self.shapes.push(Shape(start = u32(start), count = u32(self.leaves.count - start)))
        return u32(self.shapes.count)

    ## The index of text literal `bytes` when the unit has it. It reads and never adds, so
    ## the generators' threads may ask it at once (`back.parallel`).
    pub func find_text(bytes: str) -> u32?:
        let index = self.text_index.find(bytes) else return none
        return u32(index)

    ## The index of text literal `bytes`, adding it when new.
    pub func text(bytes: str) -> u32!:
        if let found = self.find_text(bytes):
            return found
        try self.texts.push(Text(bytes = bytes))
        let index = self.texts.count - 1
        _ = try self.text_index.add(bytes, index)
        return u32(index)

    ## Index every text again, after `texts` is replaced (`inline` drops the unread ones).
    pub func index_texts() -> !:
        self.text_index.destroy()
        self.text_index = try hashed.Table[str].create(self.texts.count)
        for index in 0..<self.texts.count:
            _ = try self.text_index.add(self.texts.get(index).bytes, index)

## A text a generator needed was not among the unit's texts when its function was generated.
pub let missing_text: ErrorCode = ErrorCode.package(44)

## The arguments an instruction reads from the function's argument list, as a start and a
## count: a call's, the expected and desired values of `atomic_cas`, and the addend of
## `fma`, which sit there too. Every pass that walks a call's arguments walks these, so a cas's operands are
## renamed, resolved, counted live, and kept out of promoted slots like any other use.
pub func argument_range(f: Function*, x: Instr) -> (u32, u32):
    if x.op == Op.call:
        let info = f.calls.get((usize)x.extra)
        return (info.args_start, info.args_count)
    if x.op == Op.atomic_cas:
        return ((u32)x.b.value, 2)
    if x.op == Op.fma or x.op == Op.select:
        return (x.extra2, 1)
    if x.op == Op.ret and x.extra2 > 0:
        return (x.extra, x.extra2)
    return (0, 0)

## The load op for a scalar of a size and signedness, or a float.
pub func load_op(size: u64, signed: bool, is_float: bool) -> Op:
    if is_float:
        return Op.loadhf if size == 2 else (Op.loads if size == 4 else Op.loadd)
    if size == 1:
        return Op.loadsb if signed else Op.loadub
    if size == 2:
        return Op.loadsh if signed else Op.loaduh
    if size == 4:
        return Op.loadsw if signed else Op.loaduw
    return Op.loadl

## The store op for a scalar of a size, or a float.
pub func store_op(size: u64, is_float: bool) -> Op:
    if is_float:
        return Op.storehf if size == 2 else (Op.stores if size == 4 else Op.stored)
    if size == 1:
        return Op.storeb
    if size == 2:
        return Op.storeh
    if size == 4:
        return Op.storew
    return Op.storel

## The load of a whole register of class `cls`: a word, a long, a float of its width, or
## a vector.
pub func load_of(cls: Class) -> Op:
    match cls:
        .w: return Op.loaduw
        .l: return Op.loadl
        .v: return Op.loadv
        _: return load_op(8 if cls == Class.d else (2 if cls == Class.h else 4), false, true)

## The store of a whole register of class `cls`.
pub func store_of(cls: Class) -> Op:
    match cls:
        .w: return Op.storew
        .l: return Op.storel
        .v: return Op.storev
        _: return store_op(8 if cls == Class.d else (2 if cls == Class.h else 4), true)

test "a function collects temporaries, slots, and instructions":
    var backing: u8[262144]
    var arena = memory.FixedBuffer.over(backing)
    with arena:
        var f = try Function.create("f")
        let a = try f.binary(Op.add, Class.l, const_ref(1), const_ref(2))
        let s = try f.slot(8, 8)
        try f.store(Op.storel, a, slot_ref(s))
        let back = try f.load(Op.loadl, Class.l, slot_ref(s))
        assert(f.instrs.count == 3)
        assert(f.temps.count == 2)
        assert(back.index == 2)
        var u = try Unit.create()
        assert((try u.text("hi")) == 0)
        assert((try u.text("hi")) == 0)
        assert((try u.text("yo")) == 1)