dymokomi/luce-base
Source of release 0.46.0
0.46.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