Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.44.0

0.44.0 / src / back / native / selection.lucb

#==============================================================================================
#
#   selection - Shared, local instruction-selection facts
#
#   DESCRIPTION:
#       Counting every use prevents a comparison needed elsewhere from being consumed by a
#       fused branch, or an address needed elsewhere by a fused load or store. The
#       generators ask these questions as they walk a function's IR.
#
#==============================================================================================

import back.ir.ir
import support.list

# mark: Uses and entry ========================================================================

## The number of times each temporary is used, by index; a comparison used once may fuse.
pub func uses(f: ir.Function*) -> u32[]!:
    var counts = try new u32[f.temps.count + 1] ---
    for i in 0..<counts.length:
        counts[i] = 0
    for x in f.instrs.span():
        if x.op == ir.Op.dbg:
            continue
        mark(counts, x.a)
        mark(counts, x.b)
        let (start, count) = ir.argument_range(f, x)
        for k in 0..<count:
            mark(counts, f.args.get(start + k).value)
    return counts

func mark(counts: u32[], value: ir.Ref):
    if value.kind == ir.RefKind.temp:
        counts[value.index] += 1

## For each parameter, 1 + the index of the load at the function's entry that reads its
## slot (`ssa.promote` puts one there for a promoted parameter), when nothing else names
## that slot: the generator then moves the argument from where it arrives straight into
## the load's result, and neither stores it nor loads it back. 0 for every other.
pub func entry_loads(f: ir.Function*) -> u32[]!:
    var entry = try new u32[f.params.count + 1] ---
    for p in 0..<entry.length:
        entry[p] = 0
    if f.debug or f.symbols:
        return entry
    var named = try new u32[f.slots.count + 1] ---
    defer free(named)
    for s in 0..<named.length:
        named[s] = 0
    for x in f.instrs.span():
        note_slot(named, x.a)
        note_slot(named, x.b)
        let (start, count) = ir.argument_range(f, x)
        for k in 0..<count:
            note_slot(named, f.args.get(start + k).value)
    # the leading loads, each of a slot or through an address of one taken just before
    let counts = try uses(f)
    defer free(counts)
    var slot_of = try new u32[f.temps.count + 1] ---
    defer free(slot_of)
    for t in 0..<slot_of.length:
        slot_of[t] = 0
    for i in 0..<f.instrs.count:
        let x = f.instrs.get(i)
        if x.op == ir.Op.dbg:
            continue
        if x.op == ir.Op.addr and x.a.kind == ir.RefKind.slot and x.dst != 0:
            slot_of[(usize)x.dst] = x.a.index + 1
            continue
        if not ((u8)x.op >= (u8)ir.Op.loadsb and (u8)x.op <= (u8)ir.Op.loadd) or x.dst == 0:
            break
        var slot: u32 = 0
        if x.a.kind == ir.RefKind.slot:
            slot = x.a.index + 1
        elif x.a.kind == ir.RefKind.temp and counts[(usize)x.a.index] == 1:
            slot = slot_of[(usize)x.a.index]
        if slot == 0 or named[(usize)slot - 1] != 1:
            break
        for p in 0..<f.params.count:
            let param = f.params.get(p)
            if param.size == 0 and param.slot + 1 == slot and entry[p] == 0:
                entry[p] = u32(i + 1)
    return entry

func note_slot(named: u32[], value: ir.Ref):
    if value.kind == ir.RefKind.slot and (usize)value.index < named.length:
        named[(usize)value.index] += 1

# mark: Zero upper halves =====================================================================

## By index, the `w` temporaries whose register holds zeros above the low 32 bits wherever
## they are read. arm64 clears the upper half whenever an instruction writes a register's
## 32-bit view, as the generator does for a `w` operator, comparison, extension, and
## constant, and for a load that zero-fills; a copy of such a value keeps it. What may
## leave the upper half as it was is not: a parameter's load at the entry (the argument's
## own register may become the result: `entry`), a word loaded from a slot (the slot may
## be promoted to a register whose upper half a wider store wrote), a call's result, a
## narrowing copy of an `l`. The generator then emits no `extuw` of one that is already in
## its result's register.
pub func zero_extended(f: ir.Function*, entry: u32[]) -> bool[]!:
    let n = f.temps.count
    var clean = try new bool[n + 1] ---
    var defined = try new bool[n + 1] ---
    defer free(defined)
    var of_slot = try new bool[n + 1] ---
    defer free(of_slot)
    for t in 0..<clean.length:
        clean[t] = t != 0 and f.temp_class(u32(t)) == ir.Class.w
        defined[t] = false
        of_slot[t] = false
    var at_entry = try new bool[f.instrs.count + 1] ---
    defer free(at_entry)
    for i in 0..<at_entry.length:
        at_entry[i] = false
    for k in entry:
        if k != 0:
            at_entry[(usize)k - 1] = true
    for i in 0..<f.instrs.count:
        let x = f.instrs.get(i)
        if x.dst == 0 or (usize)x.dst > n:
            continue
        defined[(usize)x.dst] = true
        if x.op == ir.Op.addr and x.a.kind == ir.RefKind.slot:
            of_slot[(usize)x.dst] = true
        if not clean[(usize)x.dst]:
            continue
        var writes_word = false
        match x.op:
            .add, .sub, .mul, .sdiv, .udiv, .srem, .urem, .and_, .or_, .xor, .shl, .lshr, .ashr, .neg:
                writes_word = x.cls == ir.Class.w
            .ceq, .cne, .cslt, .csle, .csgt, .csge, .cult, .cule, .cugt, .cuge:
                writes_word = x.cls == ir.Class.w or x.cls == ir.Class.l
            .extsb, .extub, .extsh, .extuh:
                writes_word = true
            .loadsb, .loadub, .loadsh, .loaduh:
                writes_word = not at_entry[i]
            .loaduw:
                let through_slot = x.a.kind == ir.RefKind.slot or (x.a.kind == ir.RefKind.temp and (usize)x.a.index <= n and of_slot[(usize)x.a.index])
                writes_word = not at_entry[i] and not through_slot
            .copy:
                writes_word = x.a.kind == ir.RefKind.constant or (x.a.kind == ir.RefKind.temp and f.temp_class(x.a.index) == ir.Class.w)
            _:
                writes_word = false
        if not writes_word:
            clean[(usize)x.dst] = false
    for t in 1..<clean.length:
        if not defined[t]:
            clean[t] = false
    # a copy of a value that may be dirty is too, round the loops until nothing changes
    var changed = true
    while changed:
        changed = false
        for x in f.instrs.span():
            if x.op == ir.Op.copy and x.dst != 0 and (usize)x.dst <= n and clean[(usize)x.dst] and x.a.kind == ir.RefKind.temp and not clean[(usize)x.a.index]:
                clean[(usize)x.dst] = false
                changed = true
    return clean

# mark: Fusions ===============================================================================

## Send every jump to a label that shares its place with others (labels in a row, with
## only `dbg` between) to the first of the run, so a generator falling into the run finds
## its target next (`label_at`) and leaves out the jump; a jump or branch to a block that
## only jumps on (the empty join of an `if` inside a loop, whose arms all go on to the
## loop's next turn) goes where that block goes, one taken branch instead of two; then
## leave out the labels only fallen into (`drop_passed_labels`).
pub func canonical_labels(f: ir.Function*) -> !:
    if f.labels == 0:
        return
    var first = try label_runs(f)
    defer free(first)
    var changed = false
    for k in 0..<first.length:
        changed = changed or first[k] != u32(k)
    var none_quiet: bool[1] = [false]
    if not f.debug and try thread_jumps(f, first, none_quiet[0..<0]):
        changed = true
    if changed:
        retarget(f, first)
    try drop_passed_labels(f)

## Once registers are allocated, `quiet` marks the instructions that emit nothing (a copy
## between temporaries that share a register): a block of only those, the copies `dessa`
## left on an `if`'s empty arm, goes on as a lone jump does, and a jump or branch to it is
## sent where it goes (`thread_jumps`).
pub func thread_quiet(f: ir.Function*, quiet: const bool[]) -> !:
    if f.labels == 0 or f.debug or f.symbols or f.dynamic_levels != 0:
        return
    var first = try label_runs(f)
    defer free(first)
    if try thread_jumps(f, first, quiet):
        retarget(f, first)

## By label, the first label of the run it is in (labels in a row, with only `dbg` between).
func label_runs(f: ir.Function*) -> u32[]!:
    var first = try new u32[(usize)f.labels + 1] ---
    for k in 0..<first.length:
        first[k] = u32(k)
    var run: u32 = 0
    for x in f.instrs.span():
        if x.op == ir.Op.label:
            if run == 0:
                run = x.extra
            elif (usize)x.extra < first.length:
                first[(usize)x.extra] = run
        elif x.op != ir.Op.dbg:
            run = 0
    return first

## The most jumps on one path `thread_jumps` follows: a longer one, or one that comes round
## again (`while true: pass`), keeps its first jump.
let longest_thread: u32 = 16

## Send each label whose block does nothing but go on, by a lone `jmp` or by falling into
## the next label, to where it goes, through any run of such blocks, in `first` (already
## sending each label to the first of its run); `quiet` (empty: none) marks instructions
## that emit nothing besides labels and `dbg`. Whether any label was sent on.
func thread_jumps(f: ir.Function*, first: u32[], quiet: const bool[]) -> bool!:
    # each label's block's onward label, or 0 when its block does something
    var onward = try new u32[first.length] ---
    defer free(onward)
    for k in 0..<onward.length:
        onward[k] = 0
    var waiting = try list.List[u32].create(8)
    defer waiting.destroy()
    var any = false
    for i in 0..<f.instrs.count:
        let x = f.instrs.get(i)
        if x.op == ir.Op.label and (usize)x.extra < first.length:
            # the labels waiting, of another run, fall into this one
            if waiting.count > 0 and first[(usize)waiting.get(0)] != first[(usize)x.extra]:
                for label in waiting.span():
                    onward[(usize)label] = first[(usize)x.extra]
                any = true
                waiting.count = 0
            try waiting.push(x.extra)
            continue
        if x.op == ir.Op.dbg or (i < quiet.length and quiet[i]):
            continue
        if x.op == ir.Op.jmp and waiting.count > 0 and (usize)x.extra < first.length:
            for label in waiting.span():
                onward[(usize)label] = first[(usize)x.extra]
            any = true
        waiting.count = 0
    if not any:
        return false
    var sent = false
    for k in 1..<first.length:
        var at = first[k]
        var steps: u32 = 0
        while onward[(usize)at] != 0 and onward[(usize)at] != at and steps < longest_thread:
            at = onward[(usize)at]
            steps += 1
        if steps < longest_thread and at != first[k] and at != u32(k):
            first[k] = at
            sent = true
    return sent

## Every jump to label `k` sent to `first[k]` (`canonical_labels`), except a branch's way
## into the labels right after it, which stays a fall-through into the first of them: going
## on through a quiet block from there costs nothing, and a branch with neither way next
## takes a jump more.
func retarget(f: ir.Function*, first: u32[]):
    for i in 0..<f.instrs.count:
        var x = f.instrs.get(i)
        if x.op == ir.Op.jmp or x.op == ir.Op.switch_:
            x.extra = first[(usize)x.extra] if (usize)x.extra < first.length else x.extra
        elif x.op == ir.Op.jnz:
            x.extra = next_or_first(f, i, x.extra, first)
            x.extra2 = next_or_first(f, i, x.extra2, first)
        else:
            continue
        f.instrs.set(i, x)
    for k in 0..<f.jump_labels.count:
        let label = f.jump_labels.get(k)
        if (usize)label < first.length:
            f.jump_labels.set(k, first[(usize)label])

## Where the branch at `at` to `label` goes: the first of the labels right after it when
## `label` is among them, else `first[label]`.
func next_or_first(f: ir.Function*, at: usize, label: u32, first: u32[]) -> u32:
    var k = at + 1
    while k < f.instrs.count and (f.instrs.get(k).op == ir.Op.label or f.instrs.get(k).op == ir.Op.dbg):
        if f.instrs.get(k).op == ir.Op.label and f.instrs.get(k).extra == label:
            return label_at(f, at + 1) if label_at(f, at + 1) != 0 else label
        k += 1
    return first[(usize)label] if (usize)label < first.length else label

## Leave out each label nothing jumps to that only the instruction before it falls into: an
## expanded function's return point, say. Its block then runs on from the one before, so a
## comparison there and the branch on it after the label meet (`branch`).
func drop_passed_labels(f: ir.Function*) -> !:
    # a development build's scopes span instruction indices (`debug_scopes`), which leaving
    # an instruction out would shift past their labels
    if f.debug:
        return
    var targeted = try new bool[(usize)f.labels + 1] ---
    defer free(targeted)
    for k in 0..<targeted.length:
        targeted[k] = false
    for x in f.instrs.span():
        if x.op == ir.Op.jmp or x.op == ir.Op.switch_:
            aim(targeted, x.extra)
        elif x.op == ir.Op.jnz:
            aim(targeted, x.extra)
            aim(targeted, x.extra2)
    for label in f.jump_labels.span():
        aim(targeted, label)
    var kept: usize = 0
    var before = ir.Op.label
    for i in 0..<f.instrs.count:
        let x = f.instrs.get(i)
        let passed = x.op == ir.Op.label and i > 0 and (usize)x.extra < targeted.length and not targeted[(usize)x.extra] and before != ir.Op.label and not ir.is_terminator(before)
        if x.op != ir.Op.dbg:
            before = x.op
        if passed:
            continue
        f.instrs.set(kept, x)
        kept += 1
    f.instrs.count = kept

func aim(targeted: bool[], label: u32):
    if (usize)label < targeted.length:
        targeted[(usize)label] = true

## A load's or store's address that is a temporary plus a constant (a field of a record a
## pointer reaches, `shape.offsets`): value numbering computes the sum once where it
## dominates every use, often the function's entry, where it then holds a register for the
## whole function or lives in the frame, loaded at each use. Each load and store through it
## is given the sum right before it instead, which the generators fold into the access
## (`offset_access`), so the base, the pointer, keeps one register and the sums take none.
## A sum the accesses no longer need goes. Only a base assigned once is used where the sum
## was, and a frame address (`remat`) is left to be formed where it is used.
pub func sink_addresses(f: ir.Function*) -> !:
    if f.debug or f.symbols or f.naked:
        return
    let n = f.temps.count + 1
    var counts = try uses(f)
    defer free(counts)
    var defs = try new u8[n] ---
    defer free(defs)
    var def_at = try new u32[n] ---
    defer free(def_at)
    var root = try new u32[n] ---
    defer free(root)
    var offset = try new i64[n] ---
    defer free(offset)
    for t in 0..<n:
        defs[t] = 0
        root[t] = 0
        offset[t] = 0
    for i in 0..<f.instrs.count:
        let x = f.instrs.get(i)
        if x.dst != 0 and (usize)x.dst < n and defs[(usize)x.dst] < 2:
            defs[(usize)x.dst] += 1
            def_at[(usize)x.dst] = u32(i)
    var any = false
    for x in f.instrs.span():
        if let sum = constant_sum(f, x, defs):
            let (base, step) = sum
            if f.instrs.get((usize)def_at[(usize)base]).op == ir.Op.addr:
                continue
            let origin = root[(usize)base] if root[(usize)base] != 0 else base
            let total = step + (offset[(usize)base] if root[(usize)base] != 0 else 0)
            if total >= -256 and total <= 32760:
                root[(usize)x.dst] = origin
                offset[(usize)x.dst] = total
                any = true
    if any:
        try place_sums(f, counts, defs, def_at, root, offset)

## The base and the constant of `x` when it is a sum of a temporary assigned once and a
## constant, assigned once itself.
func constant_sum(f: ir.Function*, x: ir.Instr, defs: u8[]) -> (u32, i64)?:
    if x.op != ir.Op.add or x.cls != ir.Class.l or x.dst == 0 or (usize)x.dst >= defs.length or defs[(usize)x.dst] != 1:
        return none
    var base = x.a
    var step = x.b
    if step.kind != ir.RefKind.constant:
        base = x.b
        step = x.a
    if step.kind != ir.RefKind.constant or base.kind != ir.RefKind.temp or (usize)base.index >= defs.length or defs[(usize)base.index] != 1:
        return none
    if f.temp_class(base.index) != ir.Class.l:
        return none
    return (base.index, step.value)

## The rewriting of `sink_addresses`: a sum before each access through a sum `root` names,
## unless the sum is right before its only access already; then the sums left unread go.
func place_sums(f: ir.Function*, counts: u32[], defs: u8[], def_at: u32[], root: u32[], offset: i64[]) -> !:
    var placed = try list.List[ir.Instr].create(f.instrs.count + 16)
    for i in 0..<f.instrs.count:
        var x = f.instrs.get(i)
        if x.op == ir.Op.add and x.dst != 0 and (usize)x.dst < root.length and root[(usize)x.dst] != 0:
            # a sum of a sum: straight from the root, so the inner one may go
            let base = x.a if x.a.kind == ir.RefKind.temp else x.b
            if base.index != root[(usize)x.dst]:
                counts[(usize)base.index] -= 1
                counts[(usize)root[(usize)x.dst]] += 1
                x.a = ir.temp_ref(root[(usize)x.dst])
                x.b = ir.const_ref(offset[(usize)x.dst])
        let loads = (u8)x.op >= (u8)ir.Op.loadsb and (u8)x.op <= (u8)ir.Op.loadd
        let stores = (u8)x.op >= (u8)ir.Op.storeb and (u8)x.op <= (u8)ir.Op.stored and not same_temp(x.a, x.b)
        let address = x.a if loads else x.b
        if (loads or stores) and address.kind == ir.RefKind.temp and (usize)address.index < root.length and root[(usize)address.index] != 0:
            let d = address.index
            let adjacent = i > 0 and def_at[(usize)d] == u32(i - 1) and counts[(usize)d] == 1
            if not adjacent:
                let sum = try f.temp(ir.Class.l)
                let base = root[(usize)d]
                var add = x
                add.op = ir.Op.add
                add.cls = ir.Class.l
                add.dst = sum
                add.a = ir.temp_ref(base)
                add.b = ir.const_ref(offset[(usize)d])
                add.extra = 0
                add.extra2 = 0
                try placed.push(add)
                counts[(usize)base] += 1
                counts[(usize)d] -= 1
                if loads:
                    x.a = ir.temp_ref(sum)
                else:
                    x.b = ir.temp_ref(sum)
        try placed.push(x)
    f.instrs.destroy()
    f.instrs = placed
    # the sums nothing reads any longer, and then the ones only those read
    var changed = true
    while changed:
        changed = false
        var kept: usize = 0
        for i in 0..<f.instrs.count:
            let x = f.instrs.get(i)
            if x.op == ir.Op.add and x.dst != 0 and (usize)x.dst < root.length and root[(usize)x.dst] != 0 and counts[(usize)x.dst] == 0 and defs[(usize)x.dst] == 1:
                if x.a.kind == ir.RefKind.temp:
                    counts[(usize)x.a.index] -= 1
                if x.b.kind == ir.RefKind.temp:
                    counts[(usize)x.b.index] -= 1
                root[(usize)x.dst] = 0
                changed = true
                continue
            f.instrs.set(kept, x)
            kept += 1
        f.instrs.count = kept

## Move each block that only traps (its labels and a `trap` of a fixed reason and position,
## as a slice's `start <= end` fails) after the function's other blocks, when nothing falls
## into it: the branch to it is then taken only when the trap is, and the code that passes
## runs on without jumping over the trap's call. Blocks using temporaries stay, as their
## values' lives would stretch over everything between.
pub func traps_last(f: ir.Function*) -> !:
    let n = f.instrs.count
    var cold = false
    for i in 1..<n:
        if trap_block_end(f, i) != none:
            cold = true
            break
    if not cold:
        return
    var kept = try list.List[ir.Instr].create(n)
    var moved = try list.List[ir.Instr].create(16)
    defer moved.destroy()
    var i: usize = 0
    while i < n:
        if i > 0:
            if let end = trap_block_end(f, i):
                for k in i..<end:
                    try moved.push(f.instrs.get(k))
                i = end
                continue
        try kept.push(f.instrs.get(i))
        i += 1
    for x in moved.span():
        try kept.push(x)
    f.instrs.destroy()
    f.instrs = kept

## When a block that only traps begins at `at` with nothing falling into it: one past its
## `trap`, which the next block's label follows (or the function's end).
func trap_block_end(f: ir.Function*, at: usize) -> usize?:
    if f.instrs.get(at).op != ir.Op.label or not ir.is_terminator(f.instrs.get(at - 1).op):
        return none
    var k = at
    while k < f.instrs.count and f.instrs.get(k).op == ir.Op.label:
        k += 1
    if k >= f.instrs.count:
        return none
    let x = f.instrs.get(k)
    if x.op != ir.Op.trap_ or x.a.kind == ir.RefKind.temp or x.b.kind == ir.RefKind.temp:
        return none
    if k + 1 < f.instrs.count and f.instrs.get(k + 1).op != ir.Op.label:
        return none
    return k + 1

## By label, whether a jump after it goes back to it: a loop's head, which a generator
## aligns so the loop's body does not straddle more fetch blocks than it must.
pub func loop_heads(f: ir.Function*) -> bool[]!:
    var heads = try new bool[(usize)f.labels + 1] ---
    for k in 0..<heads.length:
        heads[k] = false
    var placed = try new bool[(usize)f.labels + 1] ---
    defer free(placed)
    for k in 0..<placed.length:
        placed[k] = false
    for x in f.instrs.span():
        if x.op == ir.Op.label and (usize)x.extra < placed.length:
            placed[(usize)x.extra] = true
        elif x.op == ir.Op.jmp and (usize)x.extra < placed.length and placed[(usize)x.extra]:
            heads[(usize)x.extra] = true
        elif x.op == ir.Op.jnz:
            if (usize)x.extra < placed.length and placed[(usize)x.extra]:
                heads[(usize)x.extra] = true
            if (usize)x.extra2 < placed.length and placed[(usize)x.extra2]:
                heads[(usize)x.extra2] = true
    return heads

## By label, for a loop's head that only tests whether to go round (the label, then a
## comparison and the branch it fuses with): 1 + the comparison's index; 0 for any other.
## A jump to such a head tests it itself instead (the loop is rotated), so a round takes
## one branch rather than two. Each temporary keeps one register throughout, so the
## comparison reads the same values at the jump; a head where the dynamic area settles, or
## a build a debugger reads, keeps its jumps.
pub func rotations(f: ir.Function*, heads: bool[], counts: u32[], floats: bool) -> u32[]!:
    var tests = try new u32[heads.length] ---
    for k in 0..<tests.length:
        tests[k] = 0
    if f.debug or f.symbols or f.dynamic_levels != 0:
        return tests
    for k in 0..<f.instrs.count:
        let x = f.instrs.get(k)
        if x.op == ir.Op.label and (usize)x.extra < heads.length and heads[(usize)x.extra] and branch(f, k + 1, counts, floats):
            tests[(usize)x.extra] = (u32)k + 2
    return tests

## After `rotations`: a rotated loop goes round from its body's first label, which is then
## the one aligned, not the head it enters by once. When the blocks that fall into its
## latch were moved above the body (`layout.latches_first`), the round begins with them
## instead: the first of their labels is aligned, and the others, the body's among them,
## are only fallen into.
pub func rotate_heads(f: ir.Function*, heads: bool[], tests: u32[]):
    for k in 0..<tests.length:
        if tests[k] != 0:
            let body = f.instrs.get((usize)tests[k]).extra
            heads[k] = false
            let top = label_at(f, (usize)tests[k] + 1)
            if top != body and top != 0 and moved_chain(f, (usize)tests[k] + 1, body, u32(k)):
                var at = (usize)tests[k] + 2
                while at < f.instrs.count:
                    let x = f.instrs.get(at)
                    if x.op == ir.Op.label and (usize)x.extra < heads.length:
                        heads[(usize)x.extra] = false
                        if x.extra == body:
                            break
                    at += 1
                heads[(usize)top] = true
            elif (usize)body < heads.length:
                heads[(usize)body] = true

## Whether the instructions from `first` up to the label `body` are a latch chain moved
## above it: they end in the jump back to `head`, right before the body's label.
func moved_chain(f: ir.Function*, first: usize, body: u32, head: u32) -> bool:
    var at = first
    while at < f.instrs.count:
        let x = f.instrs.get(at)
        if x.op == ir.Op.label and x.extra == body:
            return at > first and f.instrs.get(at - 1).op == ir.Op.jmp and f.instrs.get(at - 1).extra == head
        at += 1
    return false

## The label of the instruction at `at`, or 0 when it is not a label.
pub func label_at(f: ir.Function*, at: usize) -> u32:
    if at < f.instrs.count:
        let x = f.instrs.get(at)
        if x.op == ir.Op.label:
            return x.extra
    return 0

## Whether the instruction at `at` is a comparison whose only use is the branch right
## after it, so the two fuse into one conditional jump; of floats too when the generator
## `floats` branches on their flags.
pub func branch(f: ir.Function*, at: usize, counts: u32[], floats: bool = false) -> bool:
    if f.debug or at + 1 >= f.instrs.count:
        return false
    let x = f.instrs.get(at)
    let next = f.instrs.get(at + 1)
    let fuses = x.cls == ir.Class.w or x.cls == ir.Class.l or (floats and ir.is_float_class(x.cls))
    return ir.is_comparison(x.op) and fuses and x.dst != 0 and counts[x.dst] == 1 and next.op == ir.Op.jnz and next.a.kind == ir.RefKind.temp and next.a.index == x.dst

## When the instruction at `at` loads a signed word whose only use is its widening right
## after (`=w loadsw`, `=l extsw`): the load, its result the widening's, since the load
## already sign-extends the word into the whole register.
pub func widened_load(f: ir.Function*, at: usize, counts: u32[]) -> ir.Instr?:
    if f.debug or f.symbols or at + 1 >= f.instrs.count:
        return none
    var x = f.instrs.get(at)
    let next = f.instrs.get(at + 1)
    if x.op != ir.Op.loadsw or x.dst == 0 or counts[x.dst] != 1 or next.op != ir.Op.extsw or next.cls != ir.Class.l or next.dst == 0 or not same_temp(next.a, ir.temp_ref(x.dst)):
        return none
    x.dst = next.dst
    x.cls = ir.Class.l
    return x

## Whether the instruction at `at` is a comparison whose only use is the `select` right
## after it, as its condition: the flags the comparison sets then choose by themselves.
pub func compared_select(f: ir.Function*, at: usize, counts: u32[]) -> bool:
    if f.debug or at + 1 >= f.instrs.count:
        return false
    let x = f.instrs.get(at)
    let next = f.instrs.get(at + 1)
    return ir.is_comparison(x.op) and x.dst != 0 and counts[x.dst] == 1 and next.op == ir.Op.select and same_temp(next.a, ir.temp_ref(x.dst))

## When the instruction at `at` adds a constant (-256 to 32760) to an address and its only
## use is as the address of the load or store right after it: the base and the constant,
## which the access then addresses itself (`[base, #constant]`) while the base is still in
## its register. A half-precision access, and a build a debugger reads, keep the two apart.
pub func offset_access(f: ir.Function*, at: usize, counts: u32[]) -> (ir.Ref, i64)?:
    if f.debug or f.symbols or at + 1 >= f.instrs.count:
        return none
    let x = f.instrs.get(at)
    if x.op != ir.Op.add or x.cls != ir.Class.l or x.dst == 0 or counts[x.dst] != 1:
        return none
    var base = x.a
    var step = x.b
    if step.kind != ir.RefKind.constant:
        base = x.b
        step = x.a
    if step.kind != ir.RefKind.constant or base.kind != ir.RefKind.temp or step.value < -256 or step.value > 32760:
        return none
    let next = f.instrs.get(at + 1)
    let through = ir.temp_ref(x.dst)
    if next.op == ir.Op.loadhf or next.op == ir.Op.storehf:
        return none
    let loads = (u8)next.op >= (u8)ir.Op.loadsb and (u8)next.op <= (u8)ir.Op.loadd and same_temp(next.a, through)
    let stores = (u8)next.op >= (u8)ir.Op.storeb and (u8)next.op <= (u8)ir.Op.stored and same_temp(next.b, through) and not same_temp(next.a, through)
    if not loads and not stores:
        return none
    return (base, step.value)

## An index scaled by a power of two and added to a base, the sum the address of the load
## or store right after, each used once: `a[i]` over `u32`s (`mul i, 4`, `add base`,
## `loaduw`). The base, the index, and the shift, which is 0 or the access's own width, as
## arm64's register-offset addressing takes it (`ldr w0, [x1, x2, lsl #2]`).
pub func scaled_access(f: ir.Function*, at: usize, counts: u32[]) -> (ir.Ref, ir.Ref, u32)?:
    if f.debug or f.symbols or at + 2 >= f.instrs.count:
        return none
    let scale = f.instrs.get(at)
    if scale.cls != ir.Class.l or scale.dst == 0 or counts[scale.dst] != 1 or scale.b.kind != ir.RefKind.constant or scale.a.kind != ir.RefKind.temp:
        return none
    var shift: u32 = 0
    if scale.op == ir.Op.mul:
        let factor = scale.b.value
        if factor <= 0 or (factor & (factor - 1)) != 0:
            return none
        var rest = factor
        while rest > 1:
            rest >>= 1
            shift += 1
    elif scale.op == ir.Op.shl:
        if scale.b.value < 0 or scale.b.value > 3:
            return none
        shift = (u32)scale.b.value
    else:
        return none
    let sum = f.instrs.get(at + 1)
    if sum.op != ir.Op.add or sum.cls != ir.Class.l or sum.dst == 0 or counts[sum.dst] != 1:
        return none
    var base = sum.b
    if not same_temp(sum.a, ir.temp_ref(scale.dst)):
        if not same_temp(sum.b, ir.temp_ref(scale.dst)):
            return none
        base = sum.a
    if base.kind != ir.RefKind.temp or same_temp(base, ir.temp_ref(scale.dst)):
        return none
    let access = f.instrs.get(at + 2)
    if access.op == ir.Op.loadhf or access.op == ir.Op.storehf:
        return none
    let through = ir.temp_ref(sum.dst)
    let loads = (u8)access.op >= (u8)ir.Op.loadsb and (u8)access.op <= (u8)ir.Op.loadd and same_temp(access.a, through)
    let stores = (u8)access.op >= (u8)ir.Op.storeb and (u8)access.op <= (u8)ir.Op.stored and same_temp(access.b, through) and not same_temp(access.a, through)
    if not loads and not stores:
        return none
    if shift != 0 and ((u32)1 << shift) != access_bytes(access.op):
        return none
    return (base, scale.a, shift)

## Two registers added, the sum used once as the address of the load or store right after:
## `data[pos]` over bytes (`add base, pos`, `loadub`). The two, which arm64's register-offset
## addressing adds itself (`ldrb w0, [x1, x2]`).
pub func summed_access(f: ir.Function*, at: usize, counts: u32[]) -> (ir.Ref, ir.Ref)?:
    if f.debug or f.symbols or at + 1 >= f.instrs.count:
        return none
    let sum = f.instrs.get(at)
    if sum.op != ir.Op.add or sum.cls != ir.Class.l or sum.dst == 0 or counts[sum.dst] != 1:
        return none
    if sum.a.kind != ir.RefKind.temp or sum.b.kind != ir.RefKind.temp or f.temp_class(sum.a.index) != ir.Class.l or f.temp_class(sum.b.index) != ir.Class.l:
        return none
    let access = f.instrs.get(at + 1)
    if access.op == ir.Op.loadhf or access.op == ir.Op.storehf:
        return none
    let through = ir.temp_ref(sum.dst)
    let loads = (u8)access.op >= (u8)ir.Op.loadsb and (u8)access.op <= (u8)ir.Op.loadd and same_temp(access.a, through)
    let stores = (u8)access.op >= (u8)ir.Op.storeb and (u8)access.op <= (u8)ir.Op.stored and same_temp(access.b, through) and not same_temp(access.a, through)
    if not loads and not stores:
        return none
    return (sum.a, sum.b)

## A value shifted left by a constant (or multiplied by a power of two), used once, by the
## add right after it: `base + i * 8` (`shl i, 3`, `add base`). The other addend, the shifted value and the shift, which arm64's
## shifted-register add takes itself (`add x0, x1, x2, lsl #3`).
pub func shifted_add(f: ir.Function*, at: usize, counts: u32[]) -> (ir.Ref, ir.Ref, u32)?:
    if f.debug or f.symbols or at + 1 >= f.instrs.count:
        return none
    let shift = f.instrs.get(at)
    if (shift.op != ir.Op.shl and shift.op != ir.Op.mul) or (shift.cls != ir.Class.l and shift.cls != ir.Class.w) or shift.dst == 0 or counts[shift.dst] != 1:
        return none
    if shift.a.kind != ir.RefKind.temp or shift.b.kind != ir.RefKind.constant:
        return none
    # a multiply by 2^k is a shift by k
    var bits = shift.b.value
    if shift.op == ir.Op.mul:
        if bits <= 1 or (bits & (bits - 1)) != 0:
            return none
        var k: i64 = 0
        while bits > 1:
            bits >>= 1
            k += 1
        bits = k
    if bits < 0 or bits >= (64 if shift.cls == ir.Class.l else 32):
        return none
    let sum = f.instrs.get(at + 1)
    if sum.op != ir.Op.add or sum.cls != shift.cls:
        return none
    let through = ir.temp_ref(shift.dst)
    var other = sum.a
    if not same_temp(sum.b, through):
        if not same_temp(sum.a, through):
            return none
        other = sum.b
    if other.kind != ir.RefKind.temp or same_temp(other, through):
        return none
    return (other, shift.a, (u32)bits)

## An integer product by a constant used once, by the add right after it, the constant no
## power of two or one above one (which `shifted_add` and a shifted add take): `base + i *
## 248`, the `i`th record of 248 bytes. The other addend and the two factors, which arm64's
## multiply-add takes in one instruction (`madd x0, x1, x2, x3`). A product of two variables
## keeps its `mul` and `add`: as a `madd` in matrix_product's inner loop
## (benchmarks/native_vs_c) it ran a fifth slower on an M4.
pub func multiplied_add(f: ir.Function*, at: usize, counts: u32[]) -> (ir.Ref, ir.Ref, ir.Ref)?:
    if f.debug or f.symbols or at + 1 >= f.instrs.count:
        return none
    let product = f.instrs.get(at)
    if product.op != ir.Op.mul or (product.cls != ir.Class.l and product.cls != ir.Class.w) or product.dst == 0 or counts[product.dst] != 1:
        return none
    if product.a.kind != ir.RefKind.temp or product.b.kind != ir.RefKind.constant:
        return none
    let value = (u64)product.b.value
    if value <= 2 or (value & (value - 1)) == 0 or ((value - 1) & (value - 2)) == 0:
        return none
    let sum = f.instrs.get(at + 1)
    if sum.op != ir.Op.add or sum.cls != product.cls:
        return none
    let through = ir.temp_ref(product.dst)
    var other = sum.a
    if not same_temp(sum.b, through):
        if not same_temp(sum.a, through):
            return none
        other = sum.b
    if other.kind != ir.RefKind.temp or same_temp(other, through):
        return none
    return (other, product.a, product.b)

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

func same_temp(a: ir.Ref, b: ir.Ref) -> bool:
    return a.kind == ir.RefKind.temp and b.kind == ir.RefKind.temp and a.index == b.index