Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.42.0

0.42.0 / src / back / opt / opt.lucb

#==============================================================================================
#
#   opt - The passes on the IR before a target sees it
#
#   DESCRIPTION:
#       Four passes over each function, repeated until nothing changes, in the spirit of
#       QBE's: a store to a stack slot whose address never leaves a load or store is
#       forwarded to the loads that follow it in the same basic block (`promote`); a copy of
#       a temporary or a constant is read at its uses (`propagate`); an operator on two
#       constants is computed here, a trapping one only when it would not trap (`fold`);
#       and an instruction whose result nothing reads and that has no other effect is
#       dropped, as is a store to a promotable slot the function never loads (`sweep`).
#
#       The lowerer assigns every temporary once, which these passes rely on and keep. A
#       basic block ends at a label, a jump, a branch, a return, or a call: a call may write
#       any memory, so nothing is forwarded across it.
#
#==============================================================================================

import support.list
import back.ir.ir

## After the optimiser's passes: what they leave behind that is dead goes, and a constant
## that a copy exposed folds, once, since nothing here feeds anything else.
pub func clean(program: ir.Unit*) -> !:
    var i: usize = 0
    while i < program.functions.count:
        try clean_function(&program.functions.items[i])
        i += 1

## `clean` for one function: it reads and writes `f` alone.
pub func clean_function(f: ir.Function*) -> !:
    if f.naked:
        return
    _ = try failure_flags(f)
    _ = powers_of_two(f)
    _ = negations(f)
    _ = try low_bits(f)
    _ = fold(f)
    # a chain of values the rewrites left unread goes one link per sweep
    var swept = try sweep(f)
    while swept:
        swept = try sweep(f)

## A call's failure flag comes back 0 or 1 (`ir.Op.word` with `extra2` 1): the zero-extension
## the flag's byte takes on its way through the result's slot is the flag itself. Whether
## any changed.
func failure_flags(f: ir.Function*) -> bool!:
    var flag = try new bool[f.temps.count + 1] ---
    defer free(flag)
    for t in 0..<flag.length:
        flag[t] = false
    var any = false
    for x in f.instrs.span():
        if x.op == ir.Op.word and x.extra2 == 1 and x.dst != 0 and (usize)x.dst < flag.length:
            flag[(usize)x.dst] = true
            any = true
    if not any:
        return false
    var changed = false
    for i in 0..<f.instrs.count:
        var x = f.instrs.get(i)
        let extension = x.op == ir.Op.extub or x.op == ir.Op.extuh or x.op == ir.Op.extsb or x.op == ir.Op.extsh
        if extension and x.cls == ir.Class.w and x.a.kind == ir.RefKind.temp and (usize)x.a.index < flag.length and flag[(usize)x.a.index]:
            x.op = ir.Op.copy
            f.instrs.set(i, x)
            changed = true
    return changed

## Operands of which only the low bits are read: a narrow store writes its value's low
## bytes, and a shift reads its count's low five or six bits (the count modulo the width,
## as every target's shift instruction takes it; a count at or past the width traps
## before the shift is reached). An extension or a mask that keeps those bits as they were
## is not needed before either: `out[o] = (u8)(e >> 16)` loses the zero-extension and the
## `& 255` its conversions left between the shift and the `strb`, and `acc << (bits & 63)`
## shifts by `bits` itself (`lsl x0, x0, x1`). Only a value one instruction defines is
## followed; the extensions go if nothing else reads them (`sweep`). Whether any changed.
func low_bits(f: ir.Function*) -> bool!:
    var definition = try new u32[f.temps.count + 1] ---
    defer free(definition)
    var assigned = try new u32[f.temps.count + 1] ---
    defer free(assigned)
    for t in 0..<definition.length:
        definition[t] = 0
        assigned[t] = 0
    for i in 0..<f.instrs.count:
        let x = f.instrs.get(i)
        if x.dst != 0 and (usize)x.dst < definition.length:
            definition[(usize)x.dst] = (u32)i + 1
            assigned[(usize)x.dst] += 1
    var changed = false
    for i in 0..<f.instrs.count:
        var x = f.instrs.get(i)
        let shift = (x.op == ir.Op.shl or x.op == ir.Op.lshr or x.op == ir.Op.ashr) and (x.cls == ir.Class.w or x.cls == ir.Class.l)
        var bits: u64 = 8 if x.op == ir.Op.storeb else 16 if x.op == ir.Op.storeh else 32 if x.op == ir.Op.storew else 0
        if shift:
            bits = 6 if x.cls == ir.Class.l else 5
        if bits == 0:
            continue
        let operand = x.b if shift else x.a
        var value = operand
        var steps: u32 = 0
        while value.kind == ir.RefKind.temp and (usize)value.index < definition.length and assigned[(usize)value.index] == 1 and steps < 8:
            let d = f.instrs.get((usize)definition[(usize)value.index] - 1)
            steps += 1
            if keeps_low_bits(d, bits):
                value = d.a
            else:
                break
        if shift and value.kind != ir.RefKind.temp:
            # a constant count stays in range, as the folding and the immediates want it
            continue
        if value.kind != operand.kind or value.index != operand.index or value.value != operand.value:
            if shift:
                x.b = value
            else:
                x.a = value
            f.instrs.set(i, x)
            changed = true
    return changed

## An unsigned division or remainder by a power of two is a shift or a mask: `(len - 1) // 4`
## is `lsr #2`, not a division. Whether any changed.
func powers_of_two(f: ir.Function*) -> bool:
    var changed = false
    for i in 0..<f.instrs.count:
        var x = f.instrs.get(i)
        if (x.op != ir.Op.udiv and x.op != ir.Op.urem) or x.b.kind != ir.RefKind.constant or (x.cls != ir.Class.w and x.cls != ir.Class.l):
            continue
        let divisor = (u64)x.b.value if x.cls == ir.Class.l else (u64)(u32)x.b.value
        if divisor == 0 or (divisor & (divisor - 1)) != 0:
            continue
        if x.op == ir.Op.urem:
            x.op = ir.Op.and_
            x.b = ir.const_ref((i64)(divisor - 1))
        else:
            var shift: i64 = 0
            var rest = divisor
            while rest > 1:
                rest >>= 1
                shift += 1
            x.op = ir.Op.lshr
            x.b = ir.const_ref(shift)
        f.instrs.set(i, x)
        changed = true
    return changed

## A comparison negated right after it is the opposite comparison: `a != b`, lowered as
## `a == b` and then `== 0`, compares once and branches on the flags. Only the pair of
## neighbours is taken, so neither operand can have changed between them; of a float
## comparison only equality turns, since an ordering is false both ways on a NaN. The first
## comparison goes if nothing else reads it (`sweep`). Whether any changed.
func negations(f: ir.Function*) -> bool:
    var changed = false
    for i in 1..<f.instrs.count:
        var x = f.instrs.get(i)
        if (x.op != ir.Op.ceq and x.op != ir.Op.cne) or x.cls != ir.Class.w or x.b.kind != ir.RefKind.constant or x.b.value != 0 or x.a.kind != ir.RefKind.temp:
            continue
        let d = f.instrs.get(i - 1)
        if d.dst != x.a.index or not ir.is_comparison(d.op) or d.dst == 0 or same_ref(d.a, ir.temp_ref(d.dst)) or same_ref(d.b, ir.temp_ref(d.dst)):
            continue
        let integer = d.cls == ir.Class.w or d.cls == ir.Class.l
        if x.op == ir.Op.ceq and not integer and d.op != ir.Op.ceq and d.op != ir.Op.cne:
            continue
        x.op = d.op if x.op == ir.Op.cne else ir.negated(d.op)
        x.cls = d.cls
        x.a = d.a
        x.b = d.b
        f.instrs.set(i, x)
        changed = true
    return changed

## A call through a temporary that holds a named function's address, its only definition
## (single-assignment form: `kernel(x)` in an inline function called with `twice`), calls
## that function directly, which the inliner may then expand. Whether any changed.
pub func direct_calls(f: ir.Function*) -> bool!:
    var named = try new u32[f.temps.count + 1] ---
    defer free(named)
    var defs = try new u8[f.temps.count + 1] ---
    defer free(defs)
    for t in 0..<named.length:
        named[t] = 0
        defs[t] = 0
    var any = false
    for i in 0..<f.instrs.count:
        let x = f.instrs.get(i)
        if x.dst == 0 or (usize)x.dst >= named.length:
            continue
        defs[(usize)x.dst] = 2 if defs[(usize)x.dst] > 0 else 1
        if x.op == ir.Op.addr and x.a.kind == ir.RefKind.function:
            named[(usize)x.dst] = u32(i) + 1
            any = true
    if not any:
        return false
    var changed = false
    for i in 0..<f.instrs.count:
        var x = f.instrs.get(i)
        if x.op != ir.Op.call or x.a.kind != ir.RefKind.temp or (usize)x.a.index >= named.length:
            continue
        let k = (usize)x.a.index
        if named[k] == 0 or defs[k] != 1:
            continue
        x.a = f.instrs.get((usize)named[k] - 1).a
        f.instrs.set(i, x)
        changed = true
    return changed

func same_ref(a: ir.Ref, b: ir.Ref) -> bool:
    return a.kind == b.kind and a.index == b.index and a.value == b.value

## Whether `d`'s result has the same low `bits` bits as its first operand, an integer:
## an extension from at least that width, or a mask whose low bits are all ones.
func keeps_low_bits(d: ir.Instr, bits: u64) -> bool:
    match d.op:
        .extub, .extsb:
            return bits <= 8
        .extuh, .extsh:
            return bits <= 16
        .extuw, .extsw:
            return bits <= 32
        .copy:
            return d.cls == ir.Class.w or d.cls == ir.Class.l
        .and_:
            if d.b.kind != ir.RefKind.constant:
                return false
            let low: u64 = ((u64)1 << bits) - 1
            return ((u64)d.b.value & low) == low
        _:
            return false

## Run the passes over every function of `program`.
pub func optimise(program: ir.Unit*) -> !:
    var i: usize = 0
    while i < program.functions.count:
        try function(&program.functions.items[i])
        i += 1

## `optimise` for one function: it reads and writes `f` alone.
pub func function(f: ir.Function*) -> !:
    if f.naked:
        return
    var round: u32 = 0
    while round < 6:
        var changed = false
        changed = try promote(f) or changed
        changed = try propagate(f) or changed
        changed = fold(f) or changed
        changed = try sweep(f) or changed
        if not changed:
            return
        round += 1

# mark: What a temporary is ====================================================================

## The slot an `addr` temporary names, per temporary; 0 for every other temporary. Slot
## indices are stored one above their value so that 0 means none.
func addressed_slots(f: ir.Function*) -> u32[]!:
    var slot_of = try new u32[f.temps.count + 1] ---
    var z: usize = 0
    while z < slot_of.length:
        slot_of[z] = 0
        z += 1
    var i: usize = 0
    while i < f.instrs.count:
        let x = f.instrs.get(i)
        if x.op == ir.Op.addr and x.a.kind == ir.RefKind.slot and x.dst != 0:
            slot_of[x.dst] = x.a.index + 1
        i += 1
    return slot_of

## Whether each slot is promotable: every temporary that holds its address is used only as
## the address of a scalar load or store. A slot whose address is copied, passed, blitted,
## or read by an atomic may be reached by anything, and is left as memory.
func promotable_slots(f: ir.Function*, slot_of: u32[]) -> bool[]!:
    var ok = try new bool[f.slots.count + 1] ---
    var k: usize = 0
    while k < ok.length:
        ok[k] = true
        k += 1
    var i: usize = 0
    while i < f.instrs.count:
        let x = f.instrs.get(i)
        if x.op == ir.Op.addr:
            i += 1
            continue
        # a slot named directly, not through an `addr` temporary, is memory this pass does
        # not follow: the inliner stores arguments that way
        if x.a.kind == ir.RefKind.slot and (usize)x.a.index < f.slots.count:
            ok[x.a.index] = false
        if x.b.kind == ir.RefKind.slot and (usize)x.b.index < f.slots.count:
            ok[x.b.index] = false
        let a_slot = slot_named(slot_of, x.a)
        let b_slot = slot_named(slot_of, x.b)
        if is_load(x.op):
            if b_slot != 0:
                ok[b_slot - 1] = false
        elif is_store(x.op):
            if a_slot != 0:
                ok[a_slot - 1] = false
        else:
            if a_slot != 0:
                ok[a_slot - 1] = false
            if b_slot != 0:
                ok[b_slot - 1] = false
        i += 1
    i = 0
    while i < f.args.count:
        let value = f.args.get(i).value
        let s = slot_named(slot_of, value)
        if s != 0:
            ok[s - 1] = false
        if value.kind == ir.RefKind.slot and (usize)value.index < f.slots.count:
            ok[value.index] = false
        i += 1
    return ok

func slot_named(slot_of: u32[], r: ir.Ref) -> u32:
    if r.kind != ir.RefKind.temp or (usize)r.index >= slot_of.length:
        return 0
    return slot_of[r.index]

# mark: promote ================================================================================

## A value known to be in a promotable slot: the stored reference and the store's width.
struct Known:
    var value: ir.Ref
    var op: ir.Op

## Within each basic block, a load of a promotable slot after a store to it reads the
## stored value instead.
func promote(f: ir.Function*) -> bool!:
    let slot_of = try addressed_slots(f)
    defer free(slot_of)
    let ok = try promotable_slots(f, slot_of)
    defer free(ok)
    var known = try new Known[f.slots.count + 1] ---
    defer free(known)
    clear_known(known)
    var changed = false
    var i: usize = 0
    while i < f.instrs.count:
        let x = &f.instrs.items[i]
        if ends_block(x.op):
            clear_known(known)
        elif is_store(x.op):
            let s = slot_named(slot_of, x.b)
            if s != 0 and ok[s - 1]:
                known[s - 1] = Known(value = x.a, op = x.op)
            elif s == 0:
                # a store through an address that is not a promotable slot's: every promotable
                # slot is still its own memory, so nothing changes
                _ = 0
        elif is_load(x.op):
            let s = slot_named(slot_of, x.a)
            if s != 0 and ok[s - 1] and known[s - 1].op != ir.Op.copy and matches(known[s - 1].op, x.op):
                x.op = ir.Op.copy
                x.a = known[s - 1].value
                x.b = ir.none_ref()
                changed = true
        i += 1
    return changed

func clear_known(known: Known[]):
    var k: usize = 0
    while k < known.length:
        known[k] = Known(value = ir.none_ref(), op = ir.Op.copy)
        k += 1

## Whether a load reads exactly what a store wrote: the same width, and for a word the
## same value, since the lowerer keeps a word temporary already extended as its type needs.
func matches(store: ir.Op, load: ir.Op) -> bool:
    if store == ir.Op.storel:
        return load == ir.Op.loadl
    if store == ir.Op.stored:
        return load == ir.Op.loadd
    if store == ir.Op.stores:
        return load == ir.Op.loads
    if store == ir.Op.storew:
        return load == ir.Op.loadsw or load == ir.Op.loaduw
    return false

# mark: propagate ==============================================================================

## Every use of a temporary that was a copy of another temporary or a constant reads the
## original; the copy is left for `sweep`.
func propagate(f: ir.Function*) -> bool!:
    var source = try new ir.Ref[f.temps.count + 1] ---
    defer free(source)
    var defs = try new u32[f.temps.count + 1] ---
    defer free(defs)
    var k: usize = 0
    while k < source.length:
        source[k] = ir.none_ref()
        defs[k] = 0
        k += 1
    var i: usize = 0
    while i < f.instrs.count:
        let x = f.instrs.get(i)
        if x.dst != 0:
            defs[(usize)x.dst] += 1
        i += 1
    # only a copy assigned once, of a value assigned once (or a constant), stands for its
    # source everywhere: a temporary assigned in several places changes between them
    var any = false
    i = 0
    while i < f.instrs.count:
        let x = f.instrs.get(i)
        if x.op == ir.Op.copy and x.dst != 0 and defs[(usize)x.dst] == 1 and (x.a.kind == ir.RefKind.constant or (x.a.kind == ir.RefKind.temp and defs[(usize)x.a.index] == 1)) and x.a.index != x.dst:
            source[x.dst] = x.a
            any = true
        i += 1
    if not any:
        return false
    # a chain of copies resolves to its head
    k = 1
    while k < source.length:
        var r = source[k]
        var hops: u32 = 0
        while r.kind == ir.RefKind.temp and source[r.index].kind != ir.RefKind.none_ and hops < 64:
            r = source[r.index]
            hops += 1
        source[k] = r
        k += 1
    var changed = false
    i = 0
    while i < f.instrs.count:
        let x = &f.instrs.items[i]
        if x.op != ir.Op.copy or x.dst == 0 or source[x.dst].kind == ir.RefKind.none_:
            if replace(&x.a, source):
                changed = true
            if x.op != ir.Op.jnz and replace(&x.b, source):
                changed = true
        i += 1
    i = 0
    while i < f.args.count:
        if replace(&f.args.items[i].value, source):
            changed = true
        i += 1
    return changed

func replace(r: ir.Ref*, source: ir.Ref[]) -> bool:
    if r.kind != ir.RefKind.temp or (usize)r.index >= source.length:
        return false
    let s = source[r.index]
    if s.kind == ir.RefKind.none_:
        return false
    *r = s
    return true

# mark: fold ===================================================================================

## An operator on two constants becomes the constant; a trapping one only when it holds.
func fold(f: ir.Function*) -> bool:
    var changed = false
    var i: usize = 0
    while i < f.instrs.count:
        let x = &f.instrs.items[i]
        if x.dst != 0 and x.a.kind == ir.RefKind.constant and x.b.kind == ir.RefKind.constant:
            if let v = constant_of(x.op, x.cls, x.a.value, x.b.value, x.extra == 1):
                x.op = ir.Op.copy
                x.a = ir.const_ref(v)
                x.b = ir.none_ref()
                changed = true
        i += 1
    return changed

## `op a` at class `cls` on one constant: the extensions and negation; `none` otherwise.
pub func unary_constant(op: ir.Op, cls: ir.Class, a: i64) -> i64?:
    let wide = cls == ir.Class.l
    if cls != ir.Class.w and cls != ir.Class.l:
        return none
    match op:
        .extsb: return narrow((i64)(i8)a, wide)
        .extub: return narrow((i64)(u8)a, wide)
        .extsh: return narrow((i64)(i16)a, wide)
        .extuh: return narrow((i64)(u16)a, wide)
        .extsw: return narrow((i64)(i32)a, wide)
        .extuw: return narrow((i64)(u32)a, wide)
        .neg: return narrow(0 -% a, wide)
        _: return none

## `a op b` at class `cls`, or `none` when the operator is not folded here or would trap.
pub func constant_of(op: ir.Op, cls: ir.Class, a: i64, b: i64, is_signed: bool) -> i64?:
    let wide = cls == ir.Class.l
    if cls != ir.Class.w and cls != ir.Class.l:
        return none
    # Checked instructions carry signedness separately from their class. A high
    # unsigned bit pattern must never be folded using signed overflow rules.
    if not is_signed and (op == ir.Op.addo or op == ir.Op.subo or op == ir.Op.mulo):
        let left = unsigned(a, wide)
        let right = unsigned(b, wide)
        let maximum: u64 = 18446744073709551615 if wide else 4294967295
        if op == ir.Op.addo:
            return none if right > maximum - left else narrow((i64)(left +% right), wide)
        if op == ir.Op.subo:
            return none if left < right else narrow((i64)(left -% right), wide)
        return none if right != 0 and left > maximum // right else narrow((i64)(left *% right), wide)
    match op:
        .add: return narrow(a +% b, wide)
        .sub: return narrow(a -% b, wide)
        .mul: return narrow(a *% b, wide)
        .and_: return narrow(a & b, wide)
        .or_: return narrow(a | b, wide)
        .xor: return narrow(a ^ b, wide)
        .shl:
            if b < 0 or b >= (64 if wide else 32):
                return none
            return narrow(a << b, wide)
        .lshr:
            if b < 0 or b >= (64 if wide else 32):
                return none
            let bits = (u64)a if wide else (u64)a & 0xFFFFFFFF
            return narrow((i64)(bits >> (u64)b), wide)
        .ashr:
            if b < 0 or b >= (64 if wide else 32):
                return none
            let sa = a if wide else (i64)(i32)a
            return narrow(sa >> b, wide)
        .ceq: return 1 if same(a, b, wide) else 0
        .cne: return 0 if same(a, b, wide) else 1
        .cslt: return 1 if signed(a, wide) < signed(b, wide) else 0
        .csle: return 1 if signed(a, wide) <= signed(b, wide) else 0
        .csgt: return 1 if signed(a, wide) > signed(b, wide) else 0
        .csge: return 1 if signed(a, wide) >= signed(b, wide) else 0
        .cult: return 1 if unsigned(a, wide) < unsigned(b, wide) else 0
        .cule: return 1 if unsigned(a, wide) <= unsigned(b, wide) else 0
        .cugt: return 1 if unsigned(a, wide) > unsigned(b, wide) else 0
        .cuge: return 1 if unsigned(a, wide) >= unsigned(b, wide) else 0
        .addo:
            let (sum, carried) = checked_add(signed(a, wide), signed(b, wide), wide)
            return sum if not carried else none
        .subo:
            let (difference, carried) = checked_sub(signed(a, wide), signed(b, wide), wide)
            return difference if not carried else none
        .mulo:
            let (product, carried) = checked_mul(signed(a, wide), signed(b, wide), wide)
            return product if not carried else none
        _:
            return none

## A constant at its class's width: a word keeps its low 32 bits, sign-extended.
func narrow(v: i64, wide: bool) -> i64:
    return v if wide else (i64)(i32)v

func signed(v: i64, wide: bool) -> i64:
    return v if wide else (i64)(i32)v

func unsigned(v: i64, wide: bool) -> u64:
    return (u64)v if wide else (u64)v & 0xFFFFFFFF

func same(a: i64, b: i64, wide: bool) -> bool:
    return unsigned(a, wide) == unsigned(b, wide)

## Checked arithmetic at the width: the result and whether it overflowed the class.
func checked_add(a: i64, b: i64, wide: bool) -> (i64, bool):
    if wide:
        let s = a +| b
        return (s, (a > 0 and b > 0 and s < 0) or (a < 0 and b < 0 and s >= 0) or s != a +% b)
    let s = a + b
    return (s, s != (i64)(i32)s)

func checked_sub(a: i64, b: i64, wide: bool) -> (i64, bool):
    if wide:
        let d = a -% b
        return (d, (a >= 0 and b < 0 and d < 0) or (a < 0 and b > 0 and d >= 0))
    let d = a - b
    return (d, d != (i64)(i32)d)

func checked_mul(a: i64, b: i64, wide: bool) -> (i64, bool):
    if wide:
        let p = a *% b
        let overflow = a != 0 and ((a == -1 and b == -9223372036854775807 - 1) or (b == -1 and a == -9223372036854775807 - 1) or p // a != b)
        return (p, overflow)
    let p = a * b
    return (p, p != (i64)(i32)p)

# mark: sweep ==================================================================================

## Drop an instruction whose result nothing reads and that has no other effect, and a store
## to a promotable slot the function never loads.
func sweep(f: ir.Function*) -> bool!:
    var used = try new bool[f.temps.count + 1] ---
    defer free(used)
    clear_flags(used)
    var i: usize = 0
    while i < f.instrs.count:
        let x = f.instrs.get(i)
        if x.op != ir.Op.dbg:
            mark(used, x.a)
            mark(used, x.b)
        i += 1
    i = 0
    while i < f.args.count:
        mark(used, f.args.get(i).value)
        i += 1
    let slot_of = try addressed_slots(f)
    defer free(slot_of)
    let ok = try promotable_slots(f, slot_of)
    defer free(ok)
    var loaded = try new bool[f.slots.count + 1] ---
    defer free(loaded)
    clear_flags(loaded)
    i = 0
    while i < f.instrs.count:
        let x = f.instrs.get(i)
        if is_load(x.op):
            let s = slot_named(slot_of, x.a)
            if s != 0:
                loaded[s - 1] = true
        i += 1
    var out = try list.List[ir.Instr].create(f.instrs.count)
    var changed = false
    i = 0
    while i < f.instrs.count:
        let x = f.instrs.get(i)
        var keep = true
        if x.dst != 0 and not used[x.dst] and pure(x.op):
            keep = false
        elif is_store(x.op):
            let s = slot_named(slot_of, x.b)
            if s != 0 and ok[s - 1] and not loaded[s - 1]:
                keep = false
        if keep:
            try out.push(x)
        else:
            changed = true
        i += 1
    if changed:
        f.instrs.destroy()
        f.instrs = out
    else:
        out.destroy()
    return changed

func clear_flags(flags: bool[]):
    var k: usize = 0
    while k < flags.length:
        flags[k] = false
        k += 1

func mark(used: bool[], r: ir.Ref):
    if r.kind == ir.RefKind.temp and (usize)r.index < used.length:
        used[r.index] = true

# mark: Operators ==============================================================================

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 ends_block(op: ir.Op) -> bool:
    return op == ir.Op.label or op == ir.Op.jmp or op == ir.Op.jnz or op == ir.Op.switch_ or op == ir.Op.ret or op == ir.Op.call or op == ir.Op.asm_ or op == ir.Op.set_reg or op == ir.Op.get_reg or (u8)op >= (u8)ir.Op.atomic_load and (u8)op <= (u8)ir.Op.fence

## An instruction with no effect beyond its result: the arithmetic that cannot trap, the
## comparisons, conversions, loads, and addresses.
func pure(op: ir.Op) -> bool:
    let code = (u8)op
    if op == ir.Op.copy or op == ir.Op.addr or op == ir.Op.addr_tls or op == ir.Op.select:
        return true
    if code >= (u8)ir.Op.add and code <= (u8)ir.Op.neg:
        return op != ir.Op.sdiv and op != ir.Op.udiv and op != ir.Op.srem and op != ir.Op.urem
    if code >= (u8)ir.Op.ceq and code <= (u8)ir.Op.cuge:
        return true
    if is_load(op):
        return true
    if code >= (u8)ir.Op.extsb and code <= (u8)ir.Op.truncs:
        return true
    if op == ir.Op.loadv or op == ir.Op.vsplat:
        return true
    if ir.is_vector_op(op):
        # a checked lane traps; a store has its effect
        return op != ir.Op.storev and op != ir.Op.vaddo and op != ir.Op.vsubo
    return false