Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.42.0

0.42.0 / src / back / native / frame.lucb

#==============================================================================================
#
#   frame - The frame and the callee-saved registers, for every code generator
#
#   DESCRIPTION:
#       What a generator decides before it emits a function, and what is the same on every
#       target: which frame slots and temporaries live in callee-saved registers, and where
#       everything else sits below the frame pointer. A target says how many callee-saved
#       integer and float registers it offers (`Registers`); this module numbers them, the
#       integer codes 1..ints first and the float codes after, and the generator spells each
#       code as its register. The policy: temporaries keep as many registers as they can use
#       at once, up to a few of each class; the most-used frame slots of one register width,
#       accessed only as a whole, take the rest (§19.3 codegen); temporaries are given
#       registers by linear scan over live ranges that stretch across loop back-edges, the
#       longest-lived spilled when a class runs out; a frame descriptor for `--debug` needs
#       every slot in the frame, so a debug build promotes nothing.
#
#==============================================================================================

import back.ir.cfg
import back.ir.ir
import back.native.regalloc
import back.native.remat
import back.native.sharing
import memory
import support.list

# mark: Register banks ========================================================================

## The registers a target offers: the callee-saved integer and float ones, how many of each
## the temporaries may keep from the promoted slots, and the caller-saved ones a temporary
## takes when no call or asm block lies inside its life. Codes run: callee-saved integers
## from 1, callee-saved floats, caller-saved integers, caller-saved floats (vectors too).
pub struct Registers:
    ## The number of callee-saved integer registers the target offers.
    pub var ints: u8
    ## The number of callee-saved float (and vector) registers the target offers.
    pub var floats: u8
    ## How many callee-saved integer registers temporaries keep from the promoted slots.
    pub var keep_ints: u8
    ## How many callee-saved float registers temporaries keep from the promoted slots.
    pub var keep_floats: u8
    ## The number of caller-saved integer registers in the pool.
    pub var scratch_ints: u8
    ## The number of caller-saved float (and vector) registers in the pool.
    pub var scratch_floats: u8
    ## Whether the callee-saved float registers are the frame's: promoted slots may take
    ## them, and `layout` gives each one used a save word. On x86-64 they are not: Windows'
    ## nonvolatile xmm registers are saved whole by the generator itself, and no slot lives
    ## in an xmm register.
    pub var frame_floats: bool = true
    ## Whether a float constant is formed again at each use (`constant_of`) in a function
    ## whose floats want more registers than the pools hold, rather than taking one.
    pub var formed_constants: bool = false

    ## The allocator's register pools for this set.
    pub func pools() -> regalloc.Pools:
        return regalloc.Pools(callee_ints = self.ints, callee_floats = self.floats, scratch_ints = self.scratch_ints, scratch_floats = self.scratch_floats)

## A register that a promoted slot holds for the whole function.
let held: u32 = 4294967295

# mark: Frame layout ==========================================================================

## A saved temporary live across the barrier at instruction `at` (`Frame.crossings`).
pub struct Crossing:
    ## The barrier's instruction index.
    pub var at: u32
    ## The temporary.
    pub var temp: u32

## What a generator settles before emitting a function: where each slot and temporary lives
## and which callee-saved registers it uses.
pub struct Frame:
    ## The target's callee-saved and caller-saved register counts.
    pub var registers: Registers
    ## Where each temporary and each slot lives: an offset below the frame pointer; 0 for a
    ## temporary in a register.
    pub var temp_homes: list.List[u64]
    ## Per slot, its offset below the frame pointer; 0 for a promoted slot in a register.
    pub var slot_homes: list.List[u64]
    ## Per temporary, the register code it lives in, or 0 when it is in the frame.
    pub var temp_regs: list.List[u8]
    ## Per temporary, whether it holds a caller-saved register across barriers it crosses
    ## (`regalloc.Lives.saved`): it has a frame home as well, which `crossings` save it to.
    pub var temp_saved: list.List[bool]
    ## Each barrier instruction and a saved temporary live across it, in instruction order:
    ## the generator stores the temporary to its home before the instruction and loads it
    ## back after.
    pub var crossings: list.List[Crossing]
    ## Per slot, the register code it was promoted to, or 0; per temporary, 1 + the slot
    ## whose address it holds, or 0.
    pub var slot_regs: list.List[u8]
    ## Per temporary, 1 + the slot whose address it holds, or 0.
    pub var temp_slot: list.List[u32]
    ## Per temporary (1-based), the frame address it is formed again as at each use
    ## (`remat.find`), 0 for none.
    var formed: list.List[u64]
    ## Per temporary (1-based), whether it is a float constant formed again at each use
    ## (`Registers.formed_constants`), and the constant's bits.
    var constant_formed: list.List[bool]
    var constant_bits: list.List[u64]
    ## Where each temporary's life ends (`regalloc.Lives.end`, a doubled position), for the
    ## DWARF emitter's location lists; 0 for a temporary with no life.
    pub var temp_ends: list.List[u32]
    ## When each temporary's and each slot's value lives (`sharing`), from `plan`: homes
    ## whose lives never meet share bytes.
    var temp_spans: list.List[sharing.Span]
    var slot_spans: list.List[sharing.Span]
    ## Bit c-1 is set when register code c is used; `save_offset[c]` is where it is spilled.
    pub var used_mask: u64
    ## Where each callee-saved register is spilled, indexed by its code.
    pub var save_offset: u64[64]
    ## Codes the generator keeps for itself on this target, never handed to a temporary:
    ## bit `c - 1` for code `c`.
    pub var reserved: u64
    ## The instructions that overwrite registers of the pools themselves, in order, which
    ## the generator lists before `plan`: no temporary lives in one across them.
    pub var fixed: list.List[regalloc.Clobber]
    ## The frame's size, rounded to 16, and the home of the hidden result pointer when the
    ## function returns through memory.
    pub var size: u64
    ## The frame offset of the hidden result pointer when the function returns through memory.
    pub var indirect_home: u64

    ## An empty frame for a target's register set.
    pub static func create(registers: Registers) -> Frame!:
        var f = Frame(registers = registers, temp_homes = try list.List[u64].create(256), slot_homes = try list.List[u64].create(64),
                      temp_regs = try list.List[u8].create(256), temp_saved = try list.List[bool].create(256), crossings = try list.List[Crossing].create(16), slot_regs = try list.List[u8].create(64), temp_slot = try list.List[u32].create(256), formed = try list.List[u64].create(256), temp_ends = try list.List[u32].create(256), temp_spans = try list.List[sharing.Span].create(256), slot_spans = try list.List[sharing.Span].create(64), fixed = try list.List[regalloc.Clobber].create(16), constant_formed = try list.List[bool].create(256), constant_bits = try list.List[u64].create(256),
                      used_mask = 0, reserved = 0, save_offset = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], size = 0, indirect_home = 0)
        return f

    ## Keep callee-saved register `code` out of the pools and save it on entry, as an asm
    ## block of the function names it (§8.9): it holds no value of the function, and the
    ## caller's survives.
    pub func reserve(code: u8):
        self.reserved = self.reserved | ((u64)1 << (u64)(code - 1))

    func is_reserved(code: u8) -> bool:
        return (self.reserved & ((u64)1 << (u64)(code - 1))) != 0

    ## Whether register `code` is a float (or vector) one, and whether a call preserves it.
    pub func float_code(code: u8) -> bool:
        return self.registers.pools().is_float(code)

    ## The offset below the frame pointer where temporary `t` lives, 0 when it is in a register.
    pub func temp_home(t: u32) -> u64:
        return self.temp_homes.get((usize)t - 1)

    ## The doubled position temporary `t`'s life ends at, 0 when it has none.
    pub func temp_end(t: u32) -> u32:
        return self.temp_ends.get((usize)t - 1) if (usize)t <= self.temp_ends.count else 0

    ## The offset below the frame pointer where slot `s` lives.
    pub func slot_home(s: u32) -> u64:
        return self.slot_homes.get((usize)s)

    ## The callee-saved register code a promoted slot lives in, 0 when it stays in the frame.
    pub func slot_register(s: u32) -> u8:
        if (usize)s >= self.slot_regs.count:
            return 0
        return self.slot_regs.get((usize)s)

    ## Whether register `code` is in use in this frame.
    pub func uses(code: u8) -> bool:
        return (self.used_mask & ((u64)1 << (u64)(code - 1))) != 0

    ## Whether temporary `t` is formed at each use (`remat`, `constant_of`) rather than kept.
    pub func is_rematerialised(t: u32) -> bool:
        return ((usize)t < self.formed.count and self.formed.get((usize)t) != 0) or ((usize)t < self.constant_formed.count and self.constant_formed.get((usize)t))

    ## The bits of the float constant temporary `t` is formed again as at each use, when it
    ## is one: it takes no register and no home, and its definition emits nothing.
    pub func constant_of(t: u32) -> u64?:
        if (usize)t >= self.constant_formed.count or not self.constant_formed.get((usize)t):
            return none
        return self.constant_bits.get((usize)t)

    ## Where temporary `t` is formed at each use (`remat`): its slot and the byte offset
    ## within it, as the distance below the frame pointer; none when it lives as others do.
    pub func rematerialised(t: u32) -> u64?:
        if (usize)t >= self.formed.count or self.formed.get((usize)t) == 0:
            return none
        let k = self.formed.get((usize)t)
        return self.slot_home(u32((k >> 32) - 1)) - (k & 0xFFFFFFFF)

    ## The slot an address temporary stands for, 1-based, or 0. Only meaningful after
    ## `plan`, and only for slots that were promoted.
    pub func promoted_slot(t: u32) -> u32:
        if (usize)t > self.temp_slot.count:
            return 0
        let k = self.temp_slot.get((usize)t - 1)
        if k == 0 or self.slot_regs.get((usize)k - 1) == 0:
            return 0
        return k

    ## The slot a reference stands for, 1-based: a slot reference itself, or a temporary that
    ## holds a slot's address; 0 otherwise.
    pub func slot_of(r: ir.Ref) -> u32:
        if r.kind == ir.RefKind.slot:
            return r.index + 1
        if r.kind == ir.RefKind.temp and (usize)r.index <= self.temp_slot.count:
            return self.temp_slot.get((usize)r.index - 1)
        return 0

    ## The promoted slot an address reference reaches, 1-based, or 0 when it reaches none
    ## or the slot stays in the frame.
    pub func promoted_slot_of(r: ir.Ref) -> u32:
        let k = self.slot_of(r)
        if k == 0 or self.slot_regs.get((usize)k - 1) == 0:
            return 0
        return k

    ## Decide the registers for function `f`: the temporaries' exact lives (`regalloc`), the
    ## pressure they exert, the slots promoted with what the temporaries leave, then the
    ## temporaries themselves.
    pub func plan(f: ir.Function*) -> !:
        with memory.heap:
            var g = try cfg.Graph.blocks_of(f)
            defer g.release()
            try g.loops()
            var lives = try regalloc.Lives.over(f, &g)
            defer lives.release()
            let found = try remat.find(f)
            defer free(found)
            self.formed.count = 0
            for t in 0..<found.length:
                try self.formed.push(found[t])
                if found[t] != 0:
                    lives.forget(u32(t))
            let (ints, floats) = try lives.pressure(f)
            try self.form_constants(f, &lives, floats)
            try self.note_spans(f, &g, &lives)
            let float_budget = budget(floats, self.registers.floats, self.registers.keep_floats) if self.registers.frame_floats else 0
            try self.promote(f, budget(ints, self.registers.ints, self.registers.keep_ints), float_budget)
            # the address of a slot promoted to a register is never formed at all
            for t in 1..<self.formed.count:
                let k = self.formed.get(t)
                if k != 0 and self.slot_regs.get((usize)(k >> 32) - 1) != 0:
                    self.formed.set(t, 0)
            try self.allocate(f, &lives)

    ## When the target forms float constants at their uses and `floats`, the most float
    ## temporaries live at once, fill the float pools (`Registers.formed_constants`): every
    ## temporary assigned once, a float constant, is formed at each use and needs no
    ## register, which the values computed keep instead. A build a debugger reads keeps them.
    func form_constants(f: ir.Function*, lives: regalloc.Lives*, floats: u32) -> !:
        self.constant_formed.count = 0
        self.constant_bits.count = 0
        for _ in 0..<f.temps.count + 1:
            try self.constant_formed.push(false)
            try self.constant_bits.push(0)
        let pool = (u32)self.registers.floats + (u32)self.registers.scratch_floats
        if not self.registers.formed_constants or f.debug or f.symbols or f.naked or floats < pool:
            return
        var defs = try new u8[f.temps.count + 1] ---
        defer free(defs)
        for t in 0..<defs.length:
            defs[t] = 0
        for x in f.instrs.span():
            if x.dst != 0 and defs[(usize)x.dst] < 2:
                defs[(usize)x.dst] += 1
            if x.op == ir.Op.dbg and x.a.kind == ir.RefKind.temp:
                defs[(usize)x.a.index] = 2
        for x in f.instrs.span():
            let constant = (x.op == ir.Op.cast or x.op == ir.Op.copy) and x.a.kind == ir.RefKind.constant
            if x.dst != 0 and defs[(usize)x.dst] == 1 and constant and (x.cls == ir.Class.d or x.cls == ir.Class.s) and not self.is_rematerialised(x.dst):
                self.constant_formed.set((usize)x.dst, true)
                self.constant_bits.set((usize)x.dst, (u64)x.a.value)
                lives.forget(x.dst)

    ## Lay the frame out below `base` (what the prologue already pushed): the hidden result
    ## pointer's home when `indirect_result`, a word per callee-saved register used, every
    ## slot at its alignment, then a word per temporary left in the frame. A parameter whose
    ## slot `straight` marks arrives in its register and a promoted slot lives in one: no home.
    pub func layout(f: ir.Function*, base: u64, indirect_result: bool, straight: const bool[]) -> !:
        self.temp_homes.count = 0
        self.slot_homes.count = 0
        var live_slots = try new bool[f.slots.count + 1] ---
        defer free(live_slots)
        var live_temps = try new bool[f.temps.count + 1] ---
        defer free(live_temps)
        for i in 0..<live_slots.length:
            live_slots[i] = f.debug
        for i in 0..<live_temps.length:
            live_temps[i] = f.debug
        # Parameters are written by the prologue; debug builds also retain every
        # local's described home. Otherwise only surviving IR needs storage.
        for parameter in f.params.span():
            live_slots[parameter.slot] = true
        for x in f.instrs.span():
            if x.op != ir.Op.dbg:
                mark_home(x.a, live_slots, live_temps)
                mark_home(x.b, live_slots, live_temps)
            if x.dst != 0:
                live_temps[x.dst] = true
            if x.op == ir.Op.call:
                let call = f.calls.get(x.extra)
                if call.has_result and call.result_size > 0 and not call.result_words:
                    live_slots[call.result_slot] = true
            let (start, count) = ir.argument_range(f, x)
            for k in 0..<count:
                mark_home(f.args.get(start + k).value, live_slots, live_temps)
        var offset = base
        if indirect_result:
            offset = round_up(offset, 8) + 8
            self.indirect_home = offset
        # a save slot for each callee-saved register used; the caller-saved ones need none,
        # nor the float ones a generator saves itself
        let codes = (usize)self.registers.ints + ((usize)self.registers.floats if self.registers.frame_floats else 0)
        var c: usize = 1
        while c <= codes:
            if self.uses((u8)c):
                offset = round_up(offset + 8, 8)
                self.save_offset[c] = offset
            else:
                self.save_offset[c] = 0
            c += 1
        # every slot and every temporary left in the frame takes a home; values whose lives
        # never meet share bytes (`sharing`), except in a build a debugger reads
        let shared = not f.debug and not f.symbols and f.instrs.count <= 200000 and self.slot_spans.count == f.slots.count + 1 and self.temp_spans.count == f.temps.count + 1
        let whole = sharing.Span(low = sharing.pinned, high = 0)
        var items = try list.List[sharing.Item].create(f.slots.count + f.temps.count + 1)
        defer items.destroy()
        # per item, 1 + the slot or 1 + the temporary index (as a negative count) it homes
        var owners = try list.List[i64].create(f.slots.count + f.temps.count + 1)
        defer owners.destroy()
        var i: usize = 0
        while i < f.slots.count:
            try self.slot_homes.push(0)
            # a slot promoted to a register, or a parameter's taken straight into one, is
            # never in memory; a dynamic one is below the frame (after the packing)
            if live_slots[i] and self.slot_regs.get(i) == 0 and not (i < straight.length and straight[i]) and f.slots.get(i).level == 0:
                let s = f.slots.get(i)
                try items.push(sharing.Item(size = (u64)s.size, align = (u64)s.align, span = self.slot_spans.get(i + 1) if shared else whole))
                try owners.push((i64)i + 1)
            i += 1
        i = 0
        while i < f.temps.count:
            try self.temp_homes.push(0)
            let t = i + 1
            let saved = i < self.temp_saved.count and self.temp_saved.get(i)
            if (self.temp_regs.get(i) == 0 or saved) and live_temps[t] and not self.is_rematerialised(u32(t)):
                # a vector temporary has a sixteen-byte home at a sixteen-byte boundary
                let wide = f.temp_class(u32(t)) == ir.Class.v
                try items.push(sharing.Item(size = 16 if wide else 8, align = 16 if wide else 8, span = self.temp_spans.get(t) if shared else whole))
                try owners.push(-(i64)t)
            i += 1
        let (homes, end) = try sharing.pack(items.span(), offset)
        defer free(homes)
        for k in 0..<homes.length:
            let owner = owners.get(k)
            if owner > 0:
                self.slot_homes.set((usize)owner - 1, homes[k])
            else:
                self.temp_homes.set((usize)(-owner) - 1, homes[k])
        self.size = round_up(end, 16)
        # the dynamic area's levels begin below the fixed frame (`ir.Op.reserve`)
        for k in 0..<f.slots.count:
            let s = f.slots.get(k)
            if s.level > 0:
                self.slot_homes.set(k, self.size + (u64)s.level * (u64)ir.level_bytes - (u64)s.offset)

    ## Record when each temporary and slot lives, for `layout` to share their homes.
    func note_spans(f: ir.Function*, g: cfg.Graph*, lives: regalloc.Lives*) -> !:
        self.temp_spans.count = 0
        self.slot_spans.count = 0
        let temps = try sharing.temp_spans(f, lives)
        defer free(temps)
        for span in temps:
            try self.temp_spans.push(span)
        let slots = try sharing.slot_spans(f, g)
        defer free(slots)
        for span in slots:
            try self.slot_spans.push(span)

    ## Which frame slots live in registers: a slot of 1, 2, 4, or 8 bytes whose address is
    ## taken only to load or store that many bytes at once, in one register class. The
    ## most-used ones take the first `ints` integer and `floats` float codes.
    func promote(f: ir.Function*, ints: u8, floats: u8) -> !:
        self.slot_regs.count = 0
        self.temp_slot.count = 0
        let ns = f.slots.count
        let nt = f.temps.count
        var i: usize = 0
        while i < ns:
            try self.slot_regs.push(0)
            i += 1
        i = 0
        while i < nt:
            try self.temp_slot.push(0)
            i += 1
        if f.debug or ns == 0:
            return
        # 1 = integer, 2 = float, 3 = unfit
        var kind = try new u8[ns] --- in memory.heap
        defer free(kind) in memory.heap
        var uses = try new u32[ns] --- in memory.heap
        defer free(uses) in memory.heap
        i = 0
        while i < ns:
            let sz = f.slots.get(i).size
            kind[i] = 0 if sz == 1 or sz == 2 or sz == 4 or sz == 8 else 3
            uses[i] = 0
            i += 1
        # which temporaries hold a slot's address
        var ix: usize = 0
        while ix < f.instrs.count:
            let n = f.instrs.get(ix)
            if n.op == ir.Op.addr and n.a.kind == ir.RefKind.slot and n.dst > 0:
                self.temp_slot.set((usize)n.dst - 1, n.a.index + 1)
            ix += 1
        # every use of such a temporary, or of a slot directly, must be a whole-slot load or store
        ix = 0
        while ix < f.instrs.count:
            self.note_slot_uses(f, f.instrs.get(ix), kind, uses)
            ix += 1
        self.assign_slot_registers(kind, uses, ints, floats)

    ## The slots instruction `n` reaches: a load or a store through one counts as an access
    ## (`note_access`); any other use of a slot's address leaves it unfit.
    func note_slot_uses(f: ir.Function*, n: ir.Instr, kind: u8[], uses: u32[]):
        if is_load(n.op):
            note_access(f, self.slot_of(n.a), access_width(n.op), is_float_access(n.op), kind, uses)
        elif is_store(n.op):
            note_access(f, self.slot_of(n.b), access_width(n.op), is_float_access(n.op), kind, uses)
            unfit(kind, self.slot_of(n.a))
        elif n.op == ir.Op.addr:
            let inner = self.slot_of(n.a)
            if inner != 0 and n.a.kind == ir.RefKind.temp:
                kind[(usize)inner - 1] = 3
        elif n.op == ir.Op.call or n.op == ir.Op.atomic_cas or n.op == ir.Op.fma or n.op == ir.Op.select:
            if n.op == ir.Op.call:
                let info = f.calls.get((usize)n.extra)
                # an aggregate result is written into its slot by the call sequence itself
                if info.has_result and info.result_size > 0 and not info.result_words and (usize)info.result_slot < kind.length:
                    kind[(usize)info.result_slot] = 3
            else:
                unfit(kind, self.slot_of(n.a))
                # an fma's second factor, a select's value when true
                unfit(kind, self.slot_of(n.b) if n.op == ir.Op.fma or n.op == ir.Op.select else 0)
            let (args_start, args_count) = ir.argument_range(f, n)
            var a: u32 = 0
            while a < args_count:
                unfit(kind, self.slot_of(f.args.get((usize)(args_start + a)).value))
                a += 1
        else:
            unfit(kind, self.slot_of(n.a))
            unfit(kind, self.slot_of(n.b))

    ## The most-used fit slots, used at least twice, take the registers, up to the budget
    ## of `ints` integer and `floats` float codes; a fit slot left over becomes unfit.
    func assign_slot_registers(kind: u8[], uses: u32[], ints: u8, floats: u8):
        let ns = kind.length
        var int_code: u8 = 1
        var float_code: u8 = self.registers.ints + 1
        while true:
            var best: usize = ns
            var best_uses: u32 = 0
            var i: usize = 0
            while i < ns:
                if self.slot_regs.get(i) == 0 and (kind[i] == 1 or kind[i] == 2) and uses[i] >= 2 and uses[i] > best_uses:
                    best = i
                    best_uses = uses[i]
                i += 1
            if best == ns:
                break
            while int_code <= ints and self.is_reserved(int_code):
                int_code += 1
            while float_code <= self.registers.ints + floats and self.is_reserved(float_code):
                float_code += 1
            if kind[best] == 1:
                if int_code > ints:
                    kind[best] = 3
                    continue
                self.slot_regs.set(best, int_code)
                self.used_mask = self.used_mask | ((u64)1 << (u64)(int_code - 1))
                int_code += 1
            else:
                if float_code > self.registers.ints + floats:
                    kind[best] = 3
                    continue
                self.slot_regs.set(best, float_code)
                self.used_mask = self.used_mask | ((u64)1 << (u64)(float_code - 1))
                float_code += 1

    ## Give each temporary a register by linear scan over its life (`regalloc`); a promoted
    ## slot's register is held for the whole function.
    func allocate(f: ir.Function*, lives: regalloc.Lives*) -> !:
        self.temp_regs.count = 0
        self.temp_saved.count = 0
        self.crossings.count = 0
        self.temp_ends.count = 0
        let n = f.temps.count
        var i: usize = 0
        while i < n:
            try self.temp_regs.push(0)
            try self.temp_ends.push(lives.life_end(u32(i + 1)))
            i += 1
        var taken: u64 = self.reserved
        var ps: usize = 0
        while ps < self.slot_regs.count:
            let code = self.slot_regs.get(ps)
            if code != 0:
                taken = taken | ((u64)1 << (u64)(code - 1))
            ps += 1
        self.used_mask = taken
        if n == 0:
            return
        var codes = try new u8[n] ---
        defer free(codes)
        let used = try lives.allocate(f, self.registers.pools(), taken, codes, self.fixed.span())
        i = 0
        while i < n:
            # an address temporary of a promoted slot is never materialised
            self.temp_regs.set(i, codes[i] if self.promoted_slot(u32(i + 1)) == 0 else 0)
            try self.temp_saved.push(lives.saved[i + 1] and self.temp_regs.get(i) != 0)
            i += 1
        self.used_mask = self.used_mask | used
        # where the saved temporaries go to their homes and back: the saved are few, so
        # each barrier asks each of them
        var saved = try list.List[u32].create(8)
        defer saved.destroy()
        for t in 1..<n + 1:
            if self.temp_saved.get(t - 1):
                try saved.push(u32(t))
        if saved.count == 0:
            return
        for at in 0..<f.instrs.count:
            if not regalloc.is_barrier(f.instrs.get(at)):
                continue
            for t in saved.span():
                if lives.covers_across(t, u32(2 * at)):
                    try self.crossings.push(Crossing(at = u32(at), temp = t))

## One load or store of `width` bytes through slot `k` (1-based): it fits when the width
## is the slot's and the class agrees with every other access.
func note_access(f: ir.Function*, k: u32, width: u32, float: bool, kind: u8[], uses: u32[]):
    if k == 0:
        return
    let i = (usize)k - 1
    if kind[i] == 3:
        return
    if f.slots.get(i).size != width:
        kind[i] = 3
        return
    let want: u8 = 2 if float else 1
    if kind[i] == 0:
        kind[i] = want
    elif kind[i] != want:
        kind[i] = 3
        return
    uses[i] += 1

# mark: Instruction classification ============================================================

## How many of a class's `pool` the promoted slots may take: what the temporaries do not
## keep, and they keep up to `keep` when the pressure asks for that many.
func mark_home(value: ir.Ref, slots: bool[], temps: bool[]):
    if value.kind == ir.RefKind.temp:
        temps[value.index] = true
    elif value.kind == ir.RefKind.slot:
        slots[value.index] = true

func budget(need: u32, pool: u8, keep: u8) -> u8:
    let kept = need if need < (u32)keep else (u32)keep
    return (u8)((u32)pool - kept)

## Marks slot `k` (1-based) unfit for a register; 0 names no slot.
func unfit(kind: u8[], k: u32):
    if k != 0:
        kind[(usize)k - 1] = 3

func is_load(op: ir.Op) -> bool:
    return (u8)op >= (u8)ir.Op.loadsb and (u8)op <= (u8)ir.Op.loadhf

func is_store(op: ir.Op) -> bool:
    return (u8)op >= (u8)ir.Op.storeb and (u8)op <= (u8)ir.Op.storehf

func is_float_access(op: ir.Op) -> bool:
    return op == ir.Op.loads or op == ir.Op.loadd or op == ir.Op.loadhf or op == ir.Op.stores or op == ir.Op.stored or op == ir.Op.storehf

## The bytes a load or store moves.
pub func access_width(op: ir.Op) -> u32:
    match op:
        .loadsb, .loadub, .storeb: return 1
        .loadsh, .loaduh, .storeh, .loadhf, .storehf: return 2
        .loadsw, .loaduw, .storew, .loads, .stores: return 4
        _: return 8

func round_up(value: u64, align: u64) -> u64:
    return (value + align - 1) // align * align