Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.42.0

0.42.0 / src / back / native / regalloc.lucb

#==============================================================================================
#
#   back/native/regalloc - Registers for the temporaries, by their exact lives
#
#   DESCRIPTION:
#       Linear scan over intervals with holes (Wimmer and Franz), after the optimiser has
#       brought a function out of single-assignment form. Liveness is computed by dataflow
#       over the blocks, so a temporary's interval is exactly the positions it is live at:
#       a value defined in one arm of a branch and used after the join does not hold its
#       register through the other arm. A target offers two pools per register class: the
#       callee-saved registers, which a call preserves, and the caller-saved ones, which a
#       call or an asm block may clobber, so a temporary that crosses neither takes a
#       caller-saved register first and leaves the callee-saved ones, which cost a save and
#       a restore, to the temporaries that need them. A copy's destination prefers its
#       source's register, so the parallel copies `dessa` wrote for the phis cost nothing
#       when the two do not overlap. A temporary that crosses a call takes a callee-saved
#       register if one is free, else a caller-saved one that the generator saves to the
#       temporary's frame home before each barrier it crosses and reloads after (`saved`).
#       When every register is taken, the temporaries whose reads and writes weigh least
#       for the span of their lives, ten times as much in a loop as outside it (`cost`,
#       `density`), go to the frame for their whole life: a value read at once keeps its
#       register before one read rarely across a long stretch. Nothing is split, since the
#       generators read a temporary from one place.
#
#==============================================================================================

import back.ir.cfg
import back.ir.ir
import back.opt.ssa
import memory
import support.list
## The sentinel position meaning "no instruction"; a doubled index never reaches it.
pub let no_position: u32 = 0xFFFFFFFF

# mark: Register pools ========================================================================

## What a target offers the temporaries, as runs of register codes: the callee-saved
## integer registers are codes 1 to `callee_ints`, the callee-saved float registers follow,
## then the caller-saved integer ones, then the caller-saved float ones, which vectors
## also take.
pub struct Pools:
    ## The number of callee-saved integer registers (codes 1..callee_ints).
    pub var callee_ints: u8
    ## The number of callee-saved float registers, following the integer ones.
    pub var callee_floats: u8
    ## The number of caller-saved integer registers, following the callee-saved ones.
    pub var scratch_ints: u8
    ## The number of caller-saved float (and vector) registers, last.
    pub var scratch_floats: u8

    ## How many register codes the pools hold in all.
    pub func count() -> u8:
        return self.callee_ints + self.callee_floats + self.scratch_ints + self.scratch_floats

    ## Whether `code` names a float register.
    pub func is_float(code: u8) -> bool:
        let callee = self.callee_ints + self.callee_floats
        return (code > self.callee_ints and code <= callee) or code > callee + self.scratch_ints

## An instruction that names registers of the pools itself (x86-64's division in rdx:rax,
## a shift by a count in cl): no temporary live across it may hold one of `codes`. Its
## operands and result may; the generator moves them around it.
pub struct Clobber:
    ## The instruction's index.
    pub var at: u32
    ## Bit `c - 1` for each register code `c` it overwrites.
    pub var codes: u64

# mark: Live ranges ===========================================================================

## One run of positions a temporary is live at: `from` to `to`, one past the last.
struct Range:
    var low: u32
    var high: u32
    var next: u32

## A position a temporary is read at.
struct Use:
    var at: u32
    var next: u32

## The lives of a function's temporaries: each one's ranges, earliest first, its uses, and
## whether a call or an asm block lies inside it. Positions are doubled: instruction `i`
## reads its operands at `2i` and writes its result at `2i + 1`, so a result may take the
## register of an operand that dies there, as the generators compute in place.
pub struct Lives:
    var count: usize
    var start: u32[]
    var end: u32[]
    var head: u32[]
    var use_head: u32[]
    var crosses: bool[]
    ## Whether an asm block reads or writes the temporary: it may never be in a caller-saved
    ## register, since loading the block's operands clobbers them.
    var asm_bound: bool[]
    ## Whether the temporary, crossing a call, holds a caller-saved register all the same and
    ## is saved to its frame home before each barrier it crosses and reloaded after
    ## (`crossed_barriers`): the callee-saved ones were all taken.
    pub var saved: bool[]
    ## The temporary whose register this one prefers, 0 for none: a copy's source.
    var hint: u32[]
    ## What a read at each instruction weighs: its block's loop weight (`cfg.loops`), ten
    ## for each loop the block is inside, so the paths that leave a loop weigh as little
    ## as code outside it, however the blocks are laid out.
    var weights: u32[]
    ## By temporary, the weight of the instructions that write it: the stores it would take
    ## living in the frame.
    var writes: u64[]
    var ranges: list.List[Range]
    var uses: list.List[Use]

    ## The doubled position temporary `t`'s life begins at, `no_position` when it has none.
    pub func life_start(t: u32) -> u32:
        return self.start[(usize)t]

    ## Temporary `t` needs no register nor home (`remat`): it has no life to allocate.
    pub func forget(t: u32):
        self.start[(usize)t] = no_position
        self.head[(usize)t] = no_position

    ## The doubled position temporary `t`'s life ends at, 0 when it has none.
    pub func life_end(t: u32) -> u32:
        return self.end[(usize)t] if self.start[(usize)t] != no_position else 0

    ## The lives of `f`'s temporaries over its graph `g`, whose loops are found
    ## (`cfg.Graph.loops`). Every allocation is the current allocator's; `release` gives
    ## them back.
    pub static func over(f: ir.Function*, g: cfg.Graph*) -> Lives!:
        let n = f.temps.count
        let m = f.instrs.count
        var l = Lives(count = n, start = try new u32[n + 1] ---, end = try new u32[n + 1] ---, head = try new u32[n + 1] ---, use_head = try new u32[n + 1] ---,
                      crosses = try new bool[n + 1] ---, asm_bound = try new bool[n + 1] ---, saved = try new bool[n + 1] ---, hint = try new u32[n + 1] ---, weights = try new u32[m + 1] ---, writes = try new u64[n + 1] ---, ranges = try list.List[Range].create(2 * m + n + 2),
                      uses = try list.List[Use].create(3 * m + 2))
        var t: usize = 0
        while t <= n:
            l.start[t] = no_position
            l.end[t] = 0
            l.head[t] = no_position
            l.use_head[t] = no_position
            l.crosses[t] = false
            l.asm_bound[t] = false
            l.saved[t] = false
            l.hint[t] = 0
            l.writes[t] = 0
            t += 1
        l.weigh(f, g)
        var live = try ssa.Liveness.over(f, g)
        defer live.release()
        # blocks from the last to the first, and each backwards, so that a range is always
        # added before the ranges that precede it and only the head can merge
        var bi = g.blocks.count
        while bi > 0:
            bi -= 1
            let block = g.blocks.get(bi)
            if block.end <= block.start:
                continue
            var w: usize = 0
            while w < live.words:
                var bits = live.live_out[bi * live.words + w]
                var bit: u32 = 0
                while bits != 0:
                    if (bits & 1) != 0:
                        let t2 = u32(w * 64) + bit
                        if t2 >= 1 and (usize)t2 <= n:
                            try l.add_range(t2, 2 * block.start, 2 * block.end)
                    bits >>= 1
                    bit += 1
                w += 1
            var i = block.end
            while i > block.start:
                i -= 1
                let x = f.instrs.get((usize)i)
                if x.dst != 0 and (usize)x.dst <= n:
                    # a call's words are all written as it returns (`word`), so they are all
                    # defined where the first is: an unread one still keeps its own register
                    try l.define_at(x.dst, 2 * word_start(f, i) + 1 if x.op == ir.Op.word else 2 * i + 1)
                if x.op == ir.Op.dbg:
                    # what a debugger reads is no use: the value's life is its own
                    continue
                try l.use_at(x.a, 2 * block.start, 2 * i)
                try l.use_at(x.b, 2 * block.start, 2 * i)
                let (args_start, args_count) = ir.argument_range(f, x)
                var a: u32 = 0
                while a < args_count:
                    try l.use_at(f.args.get((usize)(args_start + a)).value, 2 * block.start, 2 * i)
                    a += 1
                # a copy, and a word's zero-extension, which the generator leaves out when
                # the two share a register and the word's upper half is zero already
                if (x.op == ir.Op.copy or x.op == ir.Op.extuw) and x.a.kind == ir.RefKind.temp and x.dst != 0:
                    l.hint[(usize)x.dst] = x.a.index
                    # A loop phi is usually allocated before its backedge value.
                    # The reverse preference lets that later value reuse the phi's
                    # register when their live ranges do not overlap.
                    if l.hint[(usize)x.a.index] == 0:
                        l.hint[(usize)x.a.index] = x.dst
        try l.mark_barriers(f)
        return l

    ## Which temporaries a call or an asm block clobbers (`crosses`), and which an asm block
    ## binds (`asm_bound`).
    func mark_barriers(f: ir.Function*) -> !:
        let n = self.count
        let m = f.instrs.count
        # what a call or an asm block clobbers: the caller-saved registers of every
        # temporary live across it; a copy, a zeroing, or a fill of many bytes is a call
        # to the C library's routine in either generator. The barriers' positions in
        # order, and each temporary's ranges searched for one inside
        var barriers = try list.List[u32].create(16)
        defer barriers.destroy()
        # an asm block's operands go into the registers it names, any of them, one after
        # another before it (`set_reg`), and its outputs are stored through their addresses
        # (`get_reg`) after its text: what an operand reads, an output's address, and every
        # value live across an operand's move stay out of the caller-saved registers
        var operands = try list.List[u32].create(4)
        defer operands.destroy()
        var p: usize = 0
        while p < m:
            let x = f.instrs.get(p)
            if x.op == ir.Op.set_reg or x.op == ir.Op.get_reg:
                self.mark_at(x.a, n)
                if x.op == ir.Op.set_reg:
                    try operands.push(u32(2 * p))
            if is_barrier(x):
                try barriers.push(u32(2 * p))
                # an asm block's operands are loaded into registers the lowerer chose from
                # the same caller-saved set, in an order that may clobber an operand still
                # to be read: a value the block reads or writes stays out of them
                if x.op == ir.Op.asm_:
                    self.mark_at(x.a, n)
                    self.mark_at(x.b, n)
                    if x.dst != 0 and (usize)x.dst <= n:
                        self.crosses[(usize)x.dst] = true
                        self.asm_bound[(usize)x.dst] = true
            p += 1
        if barriers.count > 0:
            var t3: usize = 1
            while t3 <= n:
                if not self.crosses[t3] and self.spans_barrier(u32(t3), barriers.span()):
                    self.crosses[t3] = true
                if operands.count > 0 and not self.asm_bound[t3] and self.spans_barrier(u32(t3), operands.span()):
                    self.crosses[t3] = true
                    self.asm_bound[t3] = true
                t3 += 1

    ## The temporary `r` names, when it is one, must survive an asm block.
    func mark_at(r: ir.Ref, n: usize):
        if r.kind == ir.RefKind.temp and (usize)r.index <= n:
            self.crosses[(usize)r.index] = true
            self.asm_bound[(usize)r.index] = true

    ## Whether one of the sorted barrier positions lies inside a range of `t`: a barrier
    ## at `p` is inside when `low <= p` and `high > p + 1`, so the value is live at the
    ## instruction's reads and still after its result.
    func spans_barrier(t: u32, barriers: u32[]) -> bool:
        var r = self.head[(usize)t]
        while r != no_position:
            let range = self.ranges.items[(usize)r]
            # the first barrier at or after the range's start
            var lo: usize = 0
            var hi: usize = barriers.length
            while lo < hi:
                let mid = (lo + hi) // 2
                if barriers[mid] < range.low:
                    lo = mid + 1
                else:
                    hi = mid
            if lo < barriers.length and barriers[lo] + 1 < range.high:
                return true
            r = range.next
        return false

    ## Free the lives' backing storage.
    pub func release():
        free(self.start)
        free(self.end)
        free(self.head)
        free(self.use_head)
        free(self.crosses)
        free(self.asm_bound)
        free(self.saved)
        free(self.hint)
        free(self.weights)
        free(self.writes)
        self.ranges.destroy()
        self.uses.destroy()

    ## Each instruction's weight, its block's loop weight, and what the writes of each
    ## temporary weigh.
    func weigh(f: ir.Function*, g: cfg.Graph*):
        for i in 0..<self.weights.length:
            self.weights[i] = 1
        for block in g.blocks.span():
            # a label belongs to the block it heads
            let labelled = block.start > 0 and f.instrs.get((usize)block.start - 1).op == ir.Op.label
            let first = block.start - 1 if labelled else block.start
            for i in first..<block.end:
                self.weights[(usize)i] = block.loop_weight if block.loop_weight > 0 else 1
        for i in 0..<f.instrs.count:
            let x = f.instrs.get(i)
            if x.dst != 0 and (usize)x.dst <= self.count:
                self.writes[(usize)x.dst] += (u64)self.weights[i]

    ## Add `[low, high)` to temporary `t`: merged into the head range when they touch.
    func add_range(t: u32, low: u32, high: u32) -> !:
        let h = self.head[(usize)t]
        let k = (usize)h
        if h != no_position and self.ranges.items[k].low <= high:
            if low < self.ranges.items[k].low:
                self.ranges.items[k].low = low
            if high > self.ranges.items[k].high:
                self.ranges.items[k].high = high
        else:
            self.head[(usize)t] = u32(self.ranges.count)
            try self.ranges.push(Range(low = low, high = high, next = h))
        if low < self.start[(usize)t]:
            self.start[(usize)t] = low
        if high > self.end[(usize)t]:
            self.end[(usize)t] = high

    ## Temporary `t` is defined at `at`: its head range begins there; a value nothing reads
    ## still occupies its register at the instruction that writes it.
    func define_at(t: u32, at: u32) -> !:
        let h = self.head[(usize)t]
        let k = (usize)h
        if h != no_position and self.ranges.items[k].low <= at and at < self.ranges.items[k].high:
            # the blocks are walked last first, so the head range is the lowest and the
            # temporary's life now starts at its definition, not where its block does: a
            # value read for the last time by the instruction defining another leaves its
            # register to that one (a loop's `acc |= x` keeps acc's register)
            self.ranges.items[k].low = at
            self.start[(usize)t] = at
            return
        try self.add_range(t, at, at + 1)

    ## `r`, when a temporary, is read at `at` inside a block beginning at `block_start`.
    func use_at(r: ir.Ref, block_start: u32, at: u32) -> !:
        if r.kind != ir.RefKind.temp or (usize)r.index > self.count:
            return
        try self.add_range(r.index, block_start, at + 1)
        let previous = self.use_head[(usize)r.index]
        self.use_head[(usize)r.index] = u32(self.uses.count)
        try self.uses.push(Use(at = at, next = previous))

    ## Whether a range of `t` reaches across the instruction reading at position `p`: the
    ## value is live at `p` (defined earlier, or live into the block there) and still
    ## after the instruction's own result at `p + 1`, so it must survive what `p` clobbers.
    pub func covers_across(t: u32, p: u32) -> bool:
        var r = self.head[(usize)t]
        while r != no_position:
            let range = self.ranges.items[(usize)r]
            if range.low > p:
                return false
            if range.high > p + 1:
                return true
            r = range.next
        return false

    ## Whether `t` is live at `p`; the ranges ascend from the head, so the walk stops at
    ## the first that begins after `p`.
    func covers(t: u32, p: u32) -> bool:
        var r = self.head[(usize)t]
        while r != no_position:
            let range = self.ranges.items[(usize)r]
            if range.low > p:
                return false
            if p < range.high:
                return true
            r = range.next
        return false

    ## The first position where `a` and `b` are both live, or `no_position`: one walk
    ## down both ascending range lists.
    func first_intersection(a: u32, b: u32) -> u32:
        var ra = self.head[(usize)a]
        var rb = self.head[(usize)b]
        while ra != no_position and rb != no_position:
            let x = self.ranges.items[(usize)ra]
            let y = self.ranges.items[(usize)rb]
            let low = x.low if x.low > y.low else y.low
            let high = x.high if x.high < y.high else y.high
            if low < high:
                return low
            if x.high <= y.high:
                ra = x.next
            else:
                rb = y.next
        return no_position

    ## What keeping `t` in the frame for its whole life costs, as eviction would: a load
    ## for each read and a store for each write, each weighing its block's loop weight.
    func cost(t: u32) -> u64:
        var total: u64 = 0
        var u = self.use_head[(usize)t]
        while u != no_position:
            let use = self.uses.items[(usize)u]
            let i = (usize)(use.at // 2)
            total += (u64)(self.weights[i] if i < self.weights.length else 1)
            u = use.next
        return total + self.writes[(usize)t]

    ## What keeping `t` in the frame costs for each position of its life it holds a register
    ## (`cost` over its span, scaled): a value read often in a short life weighs more than one
    ## read as often over a long one, which would hold the register through other lives.
    func density(t: u32) -> u64:
        let total = self.cost(t)
        if self.start[(usize)t] == no_position:
            return total
        let span = (u64)(self.end[(usize)t] - self.start[(usize)t]) + 2
        return total * 65536 // span

    ## The most temporaries of each class live at one position: integers, then floats.
    pub func pressure(f: ir.Function*) -> (u32, u32)!:
        let m = 2 * f.instrs.count + 3
        var delta_int = try new i32[m] ---
        defer free(delta_int)
        var delta_float = try new i32[m] ---
        defer free(delta_float)
        var k: usize = 0
        while k < m:
            delta_int[k] = 0
            delta_float[k] = 0
            k += 1
        var t: usize = 1
        while t <= self.count:
            let c = f.temp_class(u32(t))
            let is_int = c == ir.Class.w or c == ir.Class.l
            if is_int or ir.is_float_class(c):
                var r = self.head[t]
                while r != no_position:
                    let range = self.ranges.items[(usize)r]
                    if is_int:
                        delta_int[(usize)range.low] += 1
                        delta_int[(usize)range.high] -= 1
                    else:
                        delta_float[(usize)range.low] += 1
                        delta_float[(usize)range.high] -= 1
                    r = range.next
            t += 1
        var ints: i32 = 0
        var floats: i32 = 0
        var live_int: i32 = 0
        var live_float: i32 = 0
        k = 0
        while k < m:
            live_int += delta_int[k]
            live_float += delta_float[k]
            if live_int > ints:
                ints = live_int
            if live_float > floats:
                floats = live_float
            k += 1
        return ((u32)ints, (u32)floats)

    ## Give each temporary a register code, 0 for the frame: `held` is the mask of codes the
    ## promoted slots keep for the whole function, `fixed` the instructions that overwrite
    ## registers of the pools themselves, in order; `regs` receives a code per temporary and
    ## the mask of every code used comes back. A linear scan over the intervals by start.
    pub func allocate(f: ir.Function*, pools: Pools, held: u64, regs: u8[], fixed: const Clobber[]) -> u64!:
        let n = self.count
        for t in 0..<n:
            regs[t] = 0
        if n == 0:
            return 0
        let (order, alive) = try self.by_start(f)
        defer free(order)
        var scan = try Scan.create(alive)
        defer scan.release()
        let codes = (usize)pools.count()
        var free_until = try new u32[codes + 1] ---
        defer free(free_until)
        var holders_cost = try new u64[codes + 1] ---
        defer free(holders_cost)
        # what each temporary would cost in the frame for its span, once: eviction asks it of
        # every holder
        var costs = try new u64[n + 1] ---
        defer free(costs)
        for each in 1..<costs.length:
            costs[each] = self.density(u32(each))
        var used: u64 = 0
        for i in 0..<alive:
            let cur = order[i]
            scan.advance(&self, self.start[(usize)cur])
            let cls = f.temp_class(cur)
            let is_int = cls == ir.Class.w or cls == ir.Class.l
            let is_vector = cls == ir.Class.v
            if not is_int and not is_vector and not ir.is_float_class(cls):
                continue
            let ranges = self.ranges_of(cur, is_int, is_vector, pools)
            self.fill_free_until(&scan, regs, cur, free_until)
            let my_end = self.end[(usize)cur]
            # the promoted slots' registers, and those an instruction inside the life overwrites
            let barred = held | self.overwritten(cur, fixed)
            var chosen: usize = 0
            # the hint: a copy's source, when its register is free for the whole life
            let wanted = self.hint[(usize)cur]
            if wanted != 0 and regs[(usize)wanted - 1] != 0:
                let r = (usize)regs[(usize)wanted - 1]
                let in_pool = (r >= ranges.low_scratch and r <= ranges.high_scratch) or (r >= ranges.low_callee and r <= ranges.high_callee)
                if in_pool and (barred & ((u64)1 << (u64)(r - 1))) == 0 and free_until[r] >= my_end:
                    chosen = r
            if chosen == 0:
                chosen = pick_free(free_until, barred, ranges.low_scratch, ranges.high_scratch, my_end)
            if chosen == 0:
                chosen = pick_free(free_until, barred, ranges.low_callee, ranges.high_callee, my_end)
            if chosen == 0 and ranges.low_saved != 0:
                chosen = pick_free(free_until, barred, ranges.low_saved, ranges.high_saved, my_end)
            if chosen == 0 and costs[(usize)cur] > 0:
                chosen = self.evict(&scan, regs, cur, ranges, barred, costs, holders_cost)
            if chosen != 0:
                if ranges.low_saved != 0 and chosen >= ranges.low_saved and chosen <= ranges.high_saved:
                    self.saved[(usize)cur] = true
                regs[(usize)cur - 1] = (u8)chosen
                used = used | ((u64)1 << (u64)(chosen - 1))
                scan.activate(cur)
        return used

    ## The codes the instructions of `fixed` overwrite while `t` lives across them: live at
    ## an instruction's reads and still after its result (`covers_across`).
    func overwritten(t: u32, fixed: const Clobber[]) -> u64:
        var codes: u64 = 0
        if fixed.length == 0:
            return codes
        var r = self.head[(usize)t]
        while r != no_position:
            let range = self.ranges.items[(usize)r]
            # the first instruction reading at or after the range's start
            var lo: usize = 0
            var hi: usize = fixed.length
            while lo < hi:
                let mid = (lo + hi) // 2
                if 2 * fixed[mid].at < range.low:
                    lo = mid + 1
                else:
                    hi = mid
            while lo < fixed.length and 2 * fixed[lo].at + 1 < range.high:
                codes = codes | fixed[lo].codes
                lo += 1
            r = range.next
        return codes

    ## The live temporaries in order of their starts, by counting, and how many there are.
    func by_start(f: ir.Function*) -> (u32[], usize)!:
        let n = self.count
        let m = 2 * f.instrs.count + 2
        var bucket = try new u32[m + 1] ---
        defer free(bucket)
        for k in 0..<m + 1:
            bucket[k] = 0
        var alive: usize = 0
        for t in 1..<n + 1:
            if self.start[t] != no_position:
                bucket[(usize)self.start[t] + 1] += 1
                alive += 1
        for k in 1..<m + 1:
            bucket[k] += bucket[k - 1]
        var order = try new u32[alive + 1] ---
        for t in 1..<n + 1:
            if self.start[t] != no_position:
                order[(usize)bucket[(usize)self.start[t]]] = u32(t)
                bucket[(usize)self.start[t]] += 1
        return (order, alive)

    ## The codes temporary `cur` may draw on: caller-saved first when it crosses no
    ## barrier, then callee-saved, then caller-saved saved around the barriers it crosses.
    func ranges_of(cur: u32, is_int: bool, is_vector: bool, pools: Pools) -> Ranges:
        let codes = (usize)pools.count()
        let callee = (usize)pools.callee_ints + (usize)pools.callee_floats
        var r = Ranges()
        let crosses = self.crosses[(usize)cur]
        if is_int:
            if not crosses:
                r.low_scratch = callee + 1
                r.high_scratch = callee + (usize)pools.scratch_ints
            r.low_callee = 1
            r.high_callee = (usize)pools.callee_ints
        else:
            if not crosses:
                r.low_scratch = callee + (usize)pools.scratch_ints + 1
                r.high_scratch = codes
            if not is_vector:
                r.low_callee = (usize)pools.callee_ints + 1
                r.high_callee = callee
        # a temporary crossing a barrier may still take a caller-saved register, saved
        # before each barrier it crosses and reloaded after, rather than the frame for its
        # whole life: the barriers are usually off the hot path (a table's slow lookup, an
        # error's report), the value's reads are not
        if crosses and not self.asm_bound[(usize)cur]:
            if is_int:
                r.low_saved = callee + 1
                r.high_saved = callee + (usize)pools.scratch_ints
            elif not is_vector:
                r.low_saved = callee + (usize)pools.scratch_ints + 1
                r.high_saved = codes
        return r

    ## Where each register is next needed at or after `cur`'s start: at once for an active
    ## interval's, at its first meeting with `cur` for an inactive one's, never otherwise.
    func fill_free_until(scan: Scan*, regs: u8[], cur: u32, free_until: u32[]):
        for c in 1..<free_until.length:
            free_until[c] = no_position
        for a in 0..<scan.active_count:
            free_until[(usize)regs[(usize)scan.active[a] - 1]] = 0
        for a in 0..<scan.inactive_count:
            let h = scan.inactive[a]
            let r = (usize)regs[(usize)h - 1]
            let meet = self.first_intersection(h, cur)
            if meet != no_position and meet < free_until[r]:
                free_until[r] = meet

    ## Every register is taken: the one whose holders would cost least in the frame for the
    ## span they hold it (a read or write in a loop ten times one outside it, `density`) goes
    ## to `cur` when they cost less than it would, its holders moving to the frame; 0 when
    ## `cur` should.
    func evict(scan: Scan*, regs: u8[], cur: u32, ranges: Ranges, held: u64, costs: u64[], holders_cost: u64[]) -> usize:
        for c in 1..<holders_cost.length:
            holders_cost[c] = 0
        for a in 0..<scan.active_count:
            let h = scan.active[a]
            holders_cost[(usize)regs[(usize)h - 1]] += costs[(usize)h]
        for a in 0..<scan.inactive_count:
            let h = scan.inactive[a]
            if self.first_intersection(h, cur) != no_position:
                holders_cost[(usize)regs[(usize)h - 1]] += costs[(usize)h]
        var far: usize = 0
        var far_cost: u64 = 0xFFFFFFFFFFFFFFFF
        for c in 1..<holders_cost.length:
            if ranges.holds(c) and (held & ((u64)1 << (u64)(c - 1))) == 0 and holders_cost[c] < far_cost:
                far_cost = holders_cost[c]
                far = c
        if far == 0 or far_cost >= costs[(usize)cur]:
            return 0
        scan.drop_holders(regs, far)
        return far

## The codes a temporary may draw on, each pool a range `low..high`; an empty one is 0..0.
struct Ranges:
    var low_scratch: usize = 0
    var high_scratch: usize = 0
    var low_callee: usize = 0
    var high_callee: usize = 0
    var low_saved: usize = 0
    var high_saved: usize = 0

    ## Whether code `c` is in one of the ranges.
    func holds(c: usize) -> bool:
        return (c >= self.low_scratch and c <= self.high_scratch) or (c >= self.low_callee and c <= self.high_callee) or (c >= self.low_saved and c <= self.high_saved)

## The intervals that hold a register at the scan's position: the active ones cover it,
## the inactive ones have a hole there and resume later.
struct Scan:
    var active: u32[]
    var active_count: usize
    var inactive: u32[]
    var inactive_count: usize

    ## Room for `alive` intervals in each set.
    static func create(alive: usize) -> Scan!:
        let active = try new u32[alive + 1] ---
        errdefer free(active)
        return Scan(active = active, active_count = 0, inactive = try new u32[alive + 1] ---, inactive_count = 0)

    func release():
        free(self.active)
        free(self.inactive)

    ## Move to position `s`: what ended is dropped, what has a hole here becomes inactive,
    ## and what resumes here active again.
    func advance(lives: Lives*, s: u32):
        var a: usize = 0
        while a < self.active_count:
            let h = self.active[a]
            if lives.end[(usize)h] <= s:
                self.active[a] = self.active[self.active_count - 1]
                self.active_count -= 1
            elif not lives.covers(h, s):
                self.inactive[self.inactive_count] = h
                self.inactive_count += 1
                self.active[a] = self.active[self.active_count - 1]
                self.active_count -= 1
            else:
                a += 1
        a = 0
        while a < self.inactive_count:
            let h = self.inactive[a]
            if lives.end[(usize)h] <= s:
                self.inactive[a] = self.inactive[self.inactive_count - 1]
                self.inactive_count -= 1
            elif lives.covers(h, s):
                self.active[self.active_count] = h
                self.active_count += 1
                self.inactive[a] = self.inactive[self.inactive_count - 1]
                self.inactive_count -= 1
            else:
                a += 1

    func activate(t: u32):
        self.active[self.active_count] = t
        self.active_count += 1

    ## Send every interval holding register `code` to the frame.
    func drop_holders(regs: u8[], code: usize):
        var a: usize = 0
        while a < self.active_count:
            if (usize)regs[(usize)self.active[a] - 1] == code:
                regs[(usize)self.active[a] - 1] = 0
                self.active[a] = self.active[self.active_count - 1]
                self.active_count -= 1
            else:
                a += 1
        a = 0
        while a < self.inactive_count:
            if (usize)regs[(usize)self.inactive[a] - 1] == code:
                regs[(usize)self.inactive[a] - 1] = 0
                self.inactive[a] = self.inactive[self.inactive_count - 1]
                self.inactive_count -= 1
            else:
                a += 1

## The index of the first of the `word`s in a row that the one at `i` belongs to.
func word_start(f: ir.Function*, i: u32) -> u32:
    var j = i
    while j > 0 and f.instrs.get((usize)j - 1).op == ir.Op.word:
        j -= 1
    return j

# mark: Barriers and free registers ===========================================================

## An instruction that may clobber the caller-saved registers: a call, an asm block, and
## the block operations the generators hand to `memcpy` and `memset` past their inline size.
pub func is_barrier(x: ir.Instr) -> bool:
    # a copy or zeroing of up to `inline_block` bytes is loads and stores through registers no
    # temporary takes (x16/x17 on arm64, %rax/%xmm8 on x86_64): a struct copy in a loop does
    # not push the values live across it out of the caller-saved registers
    if (x.op == ir.Op.blit or x.op == ir.Op.zero) and x.extra <= inline_block:
        return false
    # `addr_tls` calls the loader's resolver on Mach-O, which keeps only the callee-saved registers
    return x.op == ir.Op.call or x.op == ir.Op.asm_ or x.op == ir.Op.blit or x.op == ir.Op.zero or x.op == ir.Op.fill or x.op == ir.Op.addr_tls

## No instruction overwriting registers of the pools itself, for the tests.
let no_fixed: Clobber[1] = [Clobber(at = 0, codes = 0)]

## The most bytes the generators copy or zero with loads and stores instead of a call.
pub let inline_block: u32 = 128

## The code in `[low, high]` that stays free the longest, when one stays free for the whole
## life ending at `end`; 0 otherwise. The first of equals wins, so the lowest register.
func pick_free(free_until: u32[], held: u64, low: usize, high: usize, end: u32) -> usize:
    var best: usize = 0
    var best_until: u32 = 0
    var c = low
    while c != 0 and c <= high:
        if (held & ((u64)1 << (u64)(c - 1))) == 0 and free_until[c] > best_until:
            best_until = free_until[c]
            best = c
        c += 1
    if best != 0 and best_until >= end:
        return best
    return 0

test "a temporary across a call keeps a callee-saved register and one beside it a scratch one":
    var backing: u8[1048576]
    var arena = memory.FixedBuffer.over(backing)
    with arena:
        var f = try ir.Function.create("t")
        # t1 = 1; t2 = 2; call g(); t3 = t1 + t2 (t1, t2 cross the call); t4 = t3 + 1 (t4 does not)
        let t1 = try f.temp(ir.Class.l)
        let t2 = try f.temp(ir.Class.l)
        try f.emit(ir.Op.copy, ir.Class.l, t1, ir.const_ref(1), ir.none_ref(), 0)
        try f.emit(ir.Op.copy, ir.Class.l, t2, ir.const_ref(2), ir.none_ref(), 0)
        try f.calls.push(ir.CallInfo(args_start = 0, args_count = 0, fixed_count = 0, variadic = false, result_cls = ir.Class.w, has_result = false, result_size = 0, result_align = 8, result_type = 0, result_slot = 0, result_shape = 0))
        try f.emit(ir.Op.call, ir.Class.w, 0, ir.function_ref("g"), ir.none_ref(), 0)
        let t3 = try f.temp(ir.Class.l)
        try f.emit(ir.Op.add, ir.Class.l, t3, ir.temp_ref(t1), ir.temp_ref(t2), 0)
        let t4 = try f.temp(ir.Class.l)
        try f.emit(ir.Op.add, ir.Class.l, t4, ir.temp_ref(t3), ir.const_ref(1), 0)
        let t5 = try f.temp(ir.Class.l)
        try f.emit(ir.Op.copy, ir.Class.l, t5, ir.temp_ref(t4), ir.none_ref(), 0)
        try f.emit(ir.Op.ret, ir.Class.l, 0, ir.temp_ref(t5), ir.none_ref(), 0)
        var g = try cfg.Graph.over(&f)
        var lives = try Lives.over(&f, &g)
        assert(lives.crosses[(usize)t1])
        assert(lives.crosses[(usize)t2])
        assert(not lives.crosses[(usize)t3])
        assert(not lives.crosses[(usize)t4])
        let (ints, floats) = try lives.pressure(&f)
        assert(ints == 2)
        assert(floats == 0)
        var regs: u8[8]
        let pools = Pools(callee_ints = 2, callee_floats = 1, scratch_ints = 2, scratch_floats = 1)
        let used = try lives.allocate(&f, pools, 0, regs[..<5], no_fixed[0..<0])
        assert(regs[0] == 1 and regs[1] == 2)
        # t3 does not cross the call: the first scratch code, 4
        assert(regs[2] == 4)
        # t4 is a copy's source and t5 its destination: t5 takes t4's register
        assert(regs[3] != 0 and regs[4] == regs[3])
        assert((used & 1) != 0 and (used & 8) != 0)
        lives.release()
        g.release()

test "intervals have holes: two values alive in different arms share one register":
    var backing: u8[1048576]
    var arena = memory.FixedBuffer.over(backing)
    with arena:
        var f = try ir.Function.create("t")
        # c = ...; jnz c, L1, L2; L1: a = 1; jmp L3; L2: b = 2; jmp L3; L3: (a used in L1 only, b in L2 only)
        let c = try f.temp(ir.Class.w)
        try f.emit(ir.Op.copy, ir.Class.w, c, ir.const_ref(1), ir.none_ref(), 0)
        let l1 = f.label()
        let l2 = f.label()
        let l3 = f.label()
        try f.branch(ir.temp_ref(c), l1, l2)
        try f.place_label(l1)
        let a = try f.temp(ir.Class.l)
        try f.emit(ir.Op.copy, ir.Class.l, a, ir.const_ref(1), ir.none_ref(), 0)
        let a2 = try f.temp(ir.Class.l)
        try f.emit(ir.Op.add, ir.Class.l, a2, ir.temp_ref(a), ir.const_ref(1), 0)
        try f.jump(l3)
        try f.place_label(l2)
        let b = try f.temp(ir.Class.l)
        try f.emit(ir.Op.copy, ir.Class.l, b, ir.const_ref(2), ir.none_ref(), 0)
        let b2 = try f.temp(ir.Class.l)
        try f.emit(ir.Op.add, ir.Class.l, b2, ir.temp_ref(b), ir.const_ref(1), 0)
        try f.jump(l3)
        try f.place_label(l3)
        try f.emit(ir.Op.ret, ir.Class.l, 0, ir.none_ref(), ir.none_ref(), 0)
        var g = try cfg.Graph.over(&f)
        var lives = try Lives.over(&f, &g)
        assert(not lives.covers(a, lives.start[(usize)b]))
        var regs: u8[8]
        let pools = Pools(callee_ints = 1, callee_floats = 0, scratch_ints = 0, scratch_floats = 0)
        _ = try lives.allocate(&f, pools, 0, regs[..<5], no_fixed[0..<0])
        # one callee-saved register serves both arms: a and b never meet
        assert(regs[(usize)a - 1] == 1 and regs[(usize)b - 1] == 1)
        lives.release()
        g.release()

test "a call's words take their own registers even when one is never read":
    var backing: u8[1048576]
    var arena = memory.FixedBuffer.over(backing)
    with arena:
        var f = try ir.Function.create("t")
        # call g() -> two words; w0 = word 0 (unread); w1 = word 1; t = w1 + 1
        try f.calls.push(ir.CallInfo(args_start = 0, args_count = 0, fixed_count = 0, variadic = false, result_cls = ir.Class.l, has_result = true, result_size = 16, result_align = 8, result_type = 0, result_slot = 0, result_shape = 0, result_private = true, result_words = true))
        try f.emit(ir.Op.call, ir.Class.l, 0, ir.function_ref("g"), ir.none_ref(), 0)
        let w0 = try f.temp(ir.Class.w)
        try f.emit(ir.Op.word, ir.Class.w, w0, ir.none_ref(), ir.none_ref(), 0)
        let w1 = try f.temp(ir.Class.w)
        try f.emit(ir.Op.word, ir.Class.w, w1, ir.none_ref(), ir.none_ref(), 1)
        let t = try f.temp(ir.Class.w)
        try f.emit(ir.Op.add, ir.Class.w, t, ir.temp_ref(w1), ir.const_ref(1), 0)
        try f.emit(ir.Op.ret, ir.Class.w, 0, ir.temp_ref(t), ir.none_ref(), 0)
        var g = try cfg.Graph.over(&f)
        var lives = try Lives.over(&f, &g)
        # both are written as the call returns, so both live from the first word on
        assert(lives.start[(usize)w0] == lives.start[(usize)w1])
        var regs: u8[8]
        let pools = Pools(callee_ints = 1, callee_floats = 0, scratch_ints = 2, scratch_floats = 0)
        _ = try lives.allocate(&f, pools, 0, regs[..<3], no_fixed[0..<0])
        assert(regs[(usize)w0 - 1] != regs[(usize)w1 - 1])
        lives.release()
        g.release()

test "no temporary holds a register across an instruction that overwrites it itself":
    var backing: u8[1048576]
    var arena = memory.FixedBuffer.over(backing)
    with arena:
        var f = try ir.Function.create("t")
        # t1 = 1; t2 = 2; t3 = t1 / t2 (overwrites code 2); t4 = t3 + t1 (t1 crosses it)
        let t1 = try f.temp(ir.Class.l)
        let t2 = try f.temp(ir.Class.l)
        try f.emit(ir.Op.copy, ir.Class.l, t1, ir.const_ref(1), ir.none_ref(), 0)
        try f.emit(ir.Op.copy, ir.Class.l, t2, ir.const_ref(2), ir.none_ref(), 0)
        let t3 = try f.temp(ir.Class.l)
        try f.emit(ir.Op.udiv, ir.Class.l, t3, ir.temp_ref(t1), ir.temp_ref(t2), 0)
        let t4 = try f.temp(ir.Class.l)
        try f.emit(ir.Op.add, ir.Class.l, t4, ir.temp_ref(t3), ir.temp_ref(t1), 0)
        try f.emit(ir.Op.ret, ir.Class.l, 0, ir.temp_ref(t4), ir.none_ref(), 0)
        var g = try cfg.Graph.over(&f)
        var lives = try Lives.over(&f, &g)
        var regs: u8[8]
        let pools = Pools(callee_ints = 0, callee_floats = 0, scratch_ints = 2, scratch_floats = 0)
        var fixed: Clobber[1] = [Clobber(at = 2, codes = 2)]
        _ = try lives.allocate(&f, pools, 0, regs[..<4], fixed[0..])
        # t1 lives across the division: code 1, never 2; t2, its operand, and t3, its
        # result, may take 2
        assert(regs[(usize)t1 - 1] == 1)
        assert(regs[(usize)t2 - 1] == 2)
        assert(regs[(usize)t3 - 1] == 2)
        lives.release()
        g.release()

test "a short life read at once keeps the register a long one read rarely gives up":
    var backing: u8[1048576]
    var arena = memory.FixedBuffer.over(backing)
    with arena:
        var f = try ir.Function.create("t")
        # long = 1; short = 2; a few unrelated steps; long read three times far apart, short
        # once at once: by cost alone long (4) outweighs short (2) and keeps the one register;
        # by cost over its span short does
        _ = try f.slot(8, 8)
        let long = try f.temp(ir.Class.l)
        try f.emit(ir.Op.copy, ir.Class.l, long, ir.const_ref(1), ir.none_ref(), 0)
        let early = try f.temp(ir.Class.l)
        try f.emit(ir.Op.add, ir.Class.l, early, ir.temp_ref(long), ir.const_ref(1), 0)
        try f.emit(ir.Op.storel, ir.Class.l, 0, ir.temp_ref(early), ir.slot_ref(0), 0)
        let short = try f.temp(ir.Class.l)
        try f.emit(ir.Op.copy, ir.Class.l, short, ir.const_ref(2), ir.none_ref(), 0)
        try f.emit(ir.Op.storel, ir.Class.l, 0, ir.temp_ref(short), ir.slot_ref(0), 0)
        for _ in 0..<8:
            try f.emit(ir.Op.storel, ir.Class.l, 0, ir.const_ref(3), ir.slot_ref(0), 0)
        let late = try f.temp(ir.Class.l)
        try f.emit(ir.Op.add, ir.Class.l, late, ir.temp_ref(long), ir.temp_ref(long), 0)
        try f.emit(ir.Op.ret, ir.Class.l, 0, ir.temp_ref(late), ir.none_ref(), 0)
        var g = try cfg.Graph.over(&f)
        var lives = try Lives.over(&f, &g)
        assert(lives.cost(long) > lives.cost(short))
        var regs: u8[8]
        let pools = Pools(callee_ints = 1, callee_floats = 0, scratch_ints = 0, scratch_floats = 0)
        _ = try lives.allocate(&f, pools, 0, regs[..<5], no_fixed[0..<0])
        assert(regs[(usize)short - 1] == 1)
        assert(regs[(usize)long - 1] == 0)
        lives.release()
        g.release()