dymokomi/luce-base
Source of release 0.46.0
0.46.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 widened_comparisons(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 64-bit comparison of a zero-extended word with a constant a word holds is the same
## comparison of the word: a shift count checked against the width (`(u64)sh >= 32`)
## compares the count's register, with no extension before it. Only an equality or an
## unsigned order turns, and only an extension one instruction defines; it goes if nothing
## else reads it (`sweep`). Whether any changed.
func widened_comparisons(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 ordered = x.op == ir.Op.ceq or x.op == ir.Op.cne or x.op == ir.Op.cult or x.op == ir.Op.cule or x.op == ir.Op.cugt or x.op == ir.Op.cuge
if not ordered or x.cls != ir.Class.l or x.a.kind != ir.RefKind.temp or x.b.kind != ir.RefKind.constant or x.b.value < 0 or x.b.value > 4294967295:
continue
let k = (usize)x.a.index
if k >= definition.length or assigned[k] != 1 or definition[k] == 0:
continue
let d = f.instrs.get((usize)definition[k] - 1)
if d.op != ir.Op.extuw or d.a.kind != ir.RefKind.temp:
continue
x.cls = ir.Class.w
x.a = d.a
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