dymokomi/luce-base
Source of release 0.41.0
0.41.0 / src / back / opt / split.lucb
#==============================================================================================
#
# split - Small aggregates in the frame taken apart into their fields
#
# DESCRIPTION:
# A struct value the lowerer keeps in a slot (a local, a temporary construction, an
# expanded call's argument or result) is read and written a field at a time, zeroed
# whole, and copied whole with `blit`. When nothing else ever sees the slot's address,
# the slot is a set of fields: this pass gives each field a slot of its own, makes
# each access one of those slots', and turns a whole zero or copy into one store or
# one load and store a field, so that `promote` can then keep every field in a
# temporary. `a.subtract(b).cross(c)` on 24-byte vectors, expanded, loses its
# zeroing, its three copies through memory and its reloads (scalar replacement of
# aggregates). Slots joined by a copy between them split alike, into the fields both
# are accessed by; bytes no access names (padding) become fields too, so a copy stays
# exact. A copy of part of a slot (an optional's value into or out of the optional,
# whose flag follows it) copies the fields of that part: the fields either side
# accesses in the copied bytes are fields of both, and the copy splits when the two
# sides then cut those bytes alike, as a zero of part of a slot splits when no field
# crosses its ends. A slot is left whole when its address escapes (a call, a store of
# it, a phi, any other use), when a call writes its aggregate result there, when a
# build with symbols describes it as a local, when an access overlaps another at a
# different width, when a partial zero or copy cuts a field, and when it is larger
# than `largest` bytes or would need more than `most_fields` fields.
#
#==============================================================================================
import support.list
import back.ir.ir
## The largest slot split, in bytes, and the most fields one splits into.
let largest: u32 = 64
let most_fields: usize = 16
## One field of a split layout: its offset, width and class.
struct Field:
var offset: u32
var width: u32
var cls: ir.Class
## The bytes a zero or copy covers of a slot, at `offset` for `bytes`, and for a copy the
## other side's slot (`none_slot` when it is not a slot's) and offset.
struct Range:
var slot: u32
var offset: u32
var bytes: u32
var other: u32
var other_offset: u32
let none_slot: u32 = 0xFFFFFFFF
## Split the small aggregate slots of `f` whose addresses stay within the accesses this pass
## understands; whether it split any.
pub func run(f: ir.Function*) -> bool!:
let ns = f.slots.count
if ns == 0 or f.debug:
return false
var plan = try Plan.over(f)
defer plan.release()
try plan.find_origins(f)
try plan.check_uses(f)
plan.join_copies(f)
try plan.share_copied_fields()
if not try plan.lay_out(f):
return false
if not plan.check_ranges():
return false
try plan.rewrite(f)
return true
# mark: The plan ===============================================================================
## What the pass learns about `f`'s slots before it changes anything.
struct Plan:
## Per slot: whether it may still split.
var ok: bool[]
## Per slot: the group of slots joined by copies it belongs to (a union-find parent).
var group: u32[]
## Per temporary: 1 + the slot whose address plus `offset_of` it holds, 0 for none.
var origin: u32[]
var offset_of: u32[]
## Per temporary: how many instructions assign it.
var defs: u32[]
## Every access seen: slot, offset, width, class.
var accesses: list.List[Field]
var access_slot: list.List[u32]
## Every zero or copy that covers part of a slot (`Range`), and each copy between two slots
## of which one or both is covered in part.
var ranges: list.List[Range]
## Per group root: its fields, from `field_start` for `field_count`, in `fields`.
var fields: Field[]
var field_start: u32[]
var field_count: u32[]
## Per slot and field: the new slot, from `field_start` of the slot's root.
var new_slot: u32[]
static func over(f: ir.Function*) -> Plan!:
let ns = f.slots.count
let nt = f.temps.count + 1
var plan = Plan(ok = try new bool[ns] ---, group = try new u32[ns] ---, origin = try new u32[nt] ---,
offset_of = try new u32[nt] ---, defs = try new u32[nt] ---, accesses = try list.List[Field].create(f.instrs.count + 1),
access_slot = try list.List[u32].create(f.instrs.count + 1), ranges = try list.List[Range].create(8), fields = try new Field[0] ---,
field_start = try new u32[ns] ---, field_count = try new u32[ns] ---, new_slot = try new u32[0] ---)
for s in 0..<ns:
let size = f.slots.get(s).size
plan.ok[s] = size > 0 and size <= largest
plan.group[s] = (u32)s
plan.field_start[s] = 0
plan.field_count[s] = 0
for p in f.params.span():
if (usize)p.slot < ns:
plan.ok[(usize)p.slot] = false
# a local the debugger is told of lives in its slot (--release --debug)
if f.symbols:
for described in f.locals.span():
if (usize)described.slot < ns:
plan.ok[(usize)described.slot] = false
for t in 0..<nt:
plan.origin[t] = 0
plan.offset_of[t] = 0
plan.defs[t] = 0
return plan
func release():
free(self.ok)
free(self.group)
free(self.origin)
free(self.offset_of)
free(self.defs)
self.accesses.destroy()
self.access_slot.destroy()
self.ranges.destroy()
free(self.fields)
free(self.field_start)
free(self.field_count)
free(self.new_slot)
## Which temporaries hold a slot's address, and at what offset: `addr`, then `add` of a
## constant and `copy`, each the temporary's only assignment.
func find_origins(f: ir.Function*) -> !:
for x in f.instrs.span():
if x.dst != 0 and (usize)x.dst < self.defs.length:
self.defs[(usize)x.dst] += 1
var changed = true
var rounds: u32 = 0
while changed and rounds < 8:
changed = false
rounds += 1
for x in f.instrs.span():
if x.dst == 0 or (usize)x.dst >= self.origin.length or self.origin[(usize)x.dst] != 0:
continue
var slot: u32 = 0
var offset: u32 = 0
if x.op == ir.Op.addr and x.a.kind == ir.RefKind.slot and (usize)x.a.index < self.ok.length:
slot = x.a.index + 1
elif x.op == ir.Op.copy or (x.op == ir.Op.add and x.cls == ir.Class.l):
if let found = self.address(x.a):
let (s, o) = found
if x.op == ir.Op.copy:
slot = s + 1
offset = o
elif x.b.kind == ir.RefKind.constant and x.b.value >= 0 and x.b.value < (i64)largest:
slot = s + 1
offset = o + (u32)x.b.value
if slot != 0:
if self.defs[(usize)x.dst] != 1:
# assigned again elsewhere: the address may be anything there
self.ok[(usize)slot - 1] = false
else:
self.origin[(usize)x.dst] = slot
self.offset_of[(usize)x.dst] = offset
changed = true
## The slot and offset `r` is the address of, if it is one.
func address(r: ir.Ref) -> (u32, u32)?:
if r.kind == ir.RefKind.slot and (usize)r.index < self.ok.length:
return (r.index, u32(0))
if r.kind == ir.RefKind.temp and (usize)r.index < self.origin.length and self.origin[(usize)r.index] != 0:
return (self.origin[(usize)r.index] - 1, self.offset_of[(usize)r.index])
return none
## Every use of a slot's address: a load or store of a scalar at an offset is an access;
## a zero or copy is kept for the rewrite, and noted when it covers part of a slot; an
## address derived by `add` or `copy` is followed; anything else leaves the slot whole.
func check_uses(f: ir.Function*) -> !:
for x in f.instrs.span():
if x.dst != 0 and (usize)x.dst < self.origin.length and self.origin[(usize)x.dst] != 0:
# an address derived from another: its uses are what count
continue
if x.op == ir.Op.addr:
continue
if is_load(x.op):
try self.access(f, x.a, access_width(x.op), access_class(x.op))
self.escape(x.b)
elif is_store(x.op):
self.escape(x.a)
try self.access(f, x.b, access_width(x.op), ir.store_class(x.op))
elif x.op == ir.Op.zero:
try self.cover(f, x.a, x.extra, ir.none_ref())
self.escape(x.b)
elif x.op == ir.Op.blit:
try self.cover(f, x.a, x.extra, x.b)
try self.cover(f, x.b, x.extra, x.a)
else:
self.escape(x.a)
self.escape(x.b)
# every instruction's arguments (a call's, a compare-and-swap's, a select's value
# when false, a returned word's), and the slot a call writes an aggregate result
# into whole, naming no address; the argument list keeps the entries of calls an
# expansion removed, which are not uses any more, so each instruction names its own
for x in f.instrs.span():
let (start, count) = ir.argument_range(f, x)
for k in 0..<count:
self.escape(f.args.get((usize)(start + k)).value)
if x.op != ir.Op.call or (usize)x.extra >= f.calls.count:
continue
let call = f.calls.get((usize)x.extra)
if call.has_result and call.result_size > 0 and not call.result_words and (usize)call.result_slot < self.ok.length:
self.ok[(usize)call.result_slot] = false
for phi in f.phi_args.span():
self.escape(phi.value)
func escape(r: ir.Ref):
if let found = self.address(r):
self.ok[(usize)found.0] = false
func access(f: ir.Function*, r: ir.Ref, width: u32, cls: ir.Class) -> !:
let found = self.address(r) else return
let (s, offset) = found
if width == 0 or offset + width > f.slots.get((usize)s).size:
self.ok[(usize)s] = false
return
try self.accesses.push(Field(offset = offset, width = width, cls = cls))
try self.access_slot.push(s)
## A zero or a copy of `bytes` at `r`, copied to or from `other` (none for a zero): of a
## whole slot, or of a part kept as a `Range`; reaching past the slot's end, or within one
## slot, the slot stays whole.
func cover(f: ir.Function*, r: ir.Ref, bytes: u32, other: ir.Ref) -> !:
let found = self.address(r) else return
let (s, offset) = found
let size = f.slots.get((usize)s).size
if bytes == 0 or offset + bytes > size:
self.ok[(usize)s] = false
return
var other_slot = none_slot
var other_offset: u32 = 0
if let beside = self.address(other):
other_slot = beside.0
other_offset = beside.1
if other_slot == s:
self.ok[(usize)s] = false
return
let other_whole = other_slot == none_slot or (other_offset == 0 and bytes == f.slots.get((usize)other_slot).size)
if offset != 0 or bytes != size or not other_whole:
try self.ranges.push(Range(slot = s, offset = offset, bytes = bytes, other = other_slot, other_offset = other_offset))
func root(s: u32) -> u32:
var at = s
while self.group[(usize)at] != at:
at = self.group[(usize)at]
return at
## Slots copied whole into each other split alike: one group, one layout. A copy between a
## slot that may split and one that may not (a parameter's, one whose address escapes)
## splits the one and leaves the other whole: the copy becomes a load and a store a field,
## at the field's offset in the whole one (a span parameter's copy that an expansion made).
## A copy of part of a slot joins nothing (`share_copied_fields`).
func join_copies(f: ir.Function*):
var changed = true
while changed:
changed = false
for x in f.instrs.span():
if x.op != ir.Op.blit:
continue
let found_a = self.address(x.a) else continue
let found_b = self.address(x.b) else continue
let a = found_a.0
let b = found_b.0
if a == b:
continue
let ra = self.root(a)
let rb = self.root(b)
let size = f.slots.get((usize)a).size
if found_a.1 != 0 or found_b.1 != 0 or x.extra != size or size != f.slots.get((usize)b).size:
continue
if self.ok[(usize)a] != self.ok[(usize)b]:
continue
if ra != rb:
self.group[(usize)ra] = rb
## The fields a copy of part of a slot moves are fields of both its sides: each access of
## one side's group in the copied bytes becomes an access of the other's at the same place
## in its own bytes, until no group gains one. A few rounds settle every chain of copies
## a function makes; a field shared too late cuts the other side unlike this one, which
## `check_ranges` finds, and the two stay whole.
func share_copied_fields() -> !:
if self.ranges.count == 0:
return
let ns = self.ok.length
# by group root and byte: the widths (1, 2, 4, 8 as bits 0 to 3) accessed there
let known = try new u8[ns * (usize)largest] ---
defer free(known)
for k in 0..<known.length:
known[k] = 0
for k in 0..<self.accesses.count:
self.note_known(known, self.access_slot.get(k), self.accesses.get(k))
for round in 0..<4:
var gained = false
for range in self.ranges.span():
if range.other == none_slot or not self.ok[(usize)range.slot] or not self.ok[(usize)range.other]:
continue
let source_group = self.root(range.other)
let n = self.accesses.count
for k in 0..<n:
let a = self.accesses.get(k)
if self.root(self.access_slot.get(k)) != source_group or a.offset < range.other_offset or a.offset + a.width > range.other_offset + range.bytes:
continue
let shared = Field(offset = a.offset - range.other_offset + range.offset, width = a.width, cls = a.cls)
if self.note_known(known, range.slot, shared):
try self.accesses.push(shared)
try self.access_slot.push(range.slot)
gained = true
if not gained:
break
## Note that `slot`'s group has `field` among its accesses: whether it was new.
func note_known(known: u8[], slot: u32, field: Field) -> bool:
let at = (usize)self.root(slot) * (usize)largest + (usize)field.offset
let bit = width_bit(field.width)
if at >= known.length or bit == 0 or known[at] & bit != 0:
return false
known[at] |= bit
return true
## Each group's fields: every access of every member, sorted by offset, no two
## overlapping unless alike, and the bytes between them filled; a group that cannot be
## laid out stays whole. Whether any group splits.
func lay_out(f: ir.Function*) -> bool!:
let ns = f.slots.count
# a member that may not split keeps its whole group whole
for s in 0..<ns:
if not self.ok[s]:
self.ok[(usize)self.root((u32)s)] = false
for s in 0..<ns:
if not self.ok[(usize)self.root((u32)s)]:
self.ok[s] = false
var all = try new Field[self.accesses.count + ns * most_fields + 1] ---
var used: usize = 0
var splits = false
var scratch = try new Field[self.accesses.count + 1] ---
defer free(scratch)
for r in 0..<ns:
if self.root((u32)r) != (u32)r or not self.ok[r]:
continue
# the group's accesses, deduplicated and sorted by offset
var n: usize = 0
for k in 0..<self.accesses.count:
if self.root(self.access_slot.get(k)) != (u32)r:
continue
let a = self.accesses.get(k)
var seen = false
for j in 0..<n:
if scratch[j].offset == a.offset and scratch[j].width == a.width:
seen = true
if not seen:
var at = n
while at > 0 and scratch[at - 1].offset > a.offset:
scratch[at] = scratch[at - 1]
at -= 1
scratch[at] = a
n += 1
let size = f.slots.get(r).size
let start = used
var cursor: u32 = 0
var fits = n > 0
for j in 0..<n:
let a = scratch[j]
if a.offset < cursor:
# overlaps the field before at another width
fits = false
break
while cursor < a.offset and fits:
let piece = filler(cursor, a.offset - cursor)
if used - start >= most_fields:
fits = false
else:
all[used] = piece
used += 1
cursor += piece.width
if not fits or used - start >= most_fields:
fits = false
break
all[used] = a
used += 1
cursor = a.offset + a.width
while fits and cursor < size:
let piece = filler(cursor, size - cursor)
if used - start >= most_fields:
fits = false
else:
all[used] = piece
used += 1
cursor += piece.width
if not fits:
used = start
self.ok[r] = false
for s in 0..<ns:
if self.root((u32)s) == (u32)r:
self.ok[s] = false
continue
self.field_start[r] = (u32)start
self.field_count[r] = (u32)(used - start)
splits = true
free(self.fields)
self.fields = all
return splits
## Whether the zeros and copies of parts of slots split, and with them any group: a part
## must begin and end between two fields of its slot, and a copy's two sides cut the
## copied bytes alike. A part that does not leaves its group whole, and its other side's;
## then the parts are checked again, as a copy into a whole slot splits only one side.
func check_ranges() -> bool:
var changed = true
while changed:
changed = false
for range in self.ranges.span():
if not self.ok[(usize)range.slot]:
continue
var fits = self.tiles(range.slot, range.offset, range.bytes)
if fits and range.other != none_slot and self.ok[(usize)range.other]:
fits = self.cut_alike(range)
if not fits:
self.keep_whole(range.slot)
if range.other != none_slot:
self.keep_whole(range.other)
changed = true
for ok in self.ok:
if ok:
return true
return false
## Whether no field of `slot` crosses either end of the `bytes` at `start`.
func tiles(slot: u32, start: u32, bytes: u32) -> bool:
let r = (usize)self.root(slot)
for k in 0..<(usize)self.field_count[r]:
let field = self.fields[(usize)self.field_start[r] + k]
let end = field.offset + field.width
if (field.offset < start and end > start) or (field.offset < start + bytes and end > start + bytes):
return false
return true
## Whether each field of a copy's slot in the copied bytes is a field of the other side's
## slot at the same place in its bytes, as wide and of the same class.
func cut_alike(range: Range) -> bool:
let r = (usize)self.root(range.slot)
for k in 0..<(usize)self.field_count[r]:
let field = self.fields[(usize)self.field_start[r] + k]
if field.offset < range.offset or field.offset >= range.offset + range.bytes:
continue
let other = self.field_of(range.other, field.offset - range.offset + range.other_offset) else return false
if other.1.width != field.width or other.1.cls != field.cls:
return false
return true
## Leave every member of `slot`'s group whole.
func keep_whole(slot: u32):
let r = self.root(slot)
for s in 0..<self.ok.length:
if self.root((u32)s) == r:
self.ok[s] = false
## Give every member of a split group a slot per field, then rebuild the instructions.
func rewrite(f: ir.Function*) -> !:
let ns = f.slots.count
free(self.new_slot)
self.new_slot = try new u32[ns * most_fields + 1] ---
for s in 0..<ns:
if not self.ok[s]:
continue
let r = (usize)self.root((u32)s)
for k in 0..<(usize)self.field_count[r]:
let field = self.fields[(usize)self.field_start[r] + k]
self.new_slot[s * most_fields + k] = try f.slot(field.width, field.width)
var old = f.instrs
f.instrs = try list.List[ir.Instr].create(old.count + 64)
for x in old.span():
try self.emit_rewritten(f, x)
old.destroy()
## The field of slot `s` at `offset`, as its new slot and its layout.
func field_at(s: u32, offset: u32) -> (u32, Field)?:
let found = self.field_of(s, offset) else return none
return (self.new_slot[(usize)s * most_fields + found.0], found.1)
## The field of slot `s`'s layout at `offset`: its index in the layout, and itself.
func field_of(s: u32, offset: u32) -> (usize, Field)?:
let r = (usize)self.root(s)
for k in 0..<(usize)self.field_count[r]:
let field = self.fields[(usize)self.field_start[r] + k]
if field.offset == offset:
return (k, field)
return none
func split_address(r: ir.Ref) -> (u32, u32)?:
let found = self.address(r) else return none
if not self.ok[(usize)found.0]:
return none
return found
func emit_rewritten(f: ir.Function*, x: ir.Instr) -> !:
if is_load(x.op):
if let found = self.split_address(x.a):
let field = self.field_at(found.0, found.1) else trap("split: a load between fields")
let slot = field.0
var y = x
y.a = try slot_address(f, x, slot)
try f.instrs.push(y)
return
elif is_store(x.op):
if let found = self.split_address(x.b):
let field = self.field_at(found.0, found.1) else trap("split: a store between fields")
let slot = field.0
var y = x
y.b = try slot_address(f, x, slot)
try f.instrs.push(y)
return
elif x.op == ir.Op.zero:
if let found = self.split_address(x.a):
let (s, start) = found
let r = (usize)self.root(s)
for k in 0..<(usize)self.field_count[r]:
let field = self.fields[(usize)self.field_start[r] + k]
if field.offset < start or field.offset >= start + x.extra:
continue
let value = try zero_of(f, x, field.cls)
let target = try slot_address(f, x, self.new_slot[(usize)s * most_fields + k])
try push(f, x, ir.store_op((u64)field.width, ir.is_float_class(field.cls)), ir.Class.l, 0, value, target, 0)
return
elif x.op == ir.Op.blit:
let target_of = self.split_address(x.a)
let source_of = self.split_address(x.b)
if target_of != none or source_of != none:
# the fields of a split side in the copied bytes, each to or from the other
# side's field at the same place, or its bytes there when it stays whole
var s: u32 = 0
var start: u32 = 0
if let known = target_of:
s = known.0
start = known.1
elif let known = source_of:
s = known.0
start = known.1
let r = (usize)self.root(s)
for k in 0..<(usize)self.field_count[r]:
let field = self.fields[(usize)self.field_start[r] + k]
if field.offset < start or field.offset >= start + x.extra:
continue
let along = field.offset - start
var source = x.b
if let known = source_of:
let other = self.field_at(known.0, known.1 + along) else trap("split: a copy between fields")
source = try slot_address(f, x, other.0)
else:
source = try offset_address(f, x, x.b, along)
var target = x.a
if let known = target_of:
let other = self.field_at(known.0, known.1 + along) else trap("split: a copy between fields")
target = try slot_address(f, x, other.0)
else:
target = try offset_address(f, x, x.a, along)
let value = try f.temp(field.cls)
try push(f, x, ir.load_op((u64)field.width, false, ir.is_float_class(field.cls)), field.cls, value, source, ir.none_ref(), 0)
try push(f, x, ir.store_op((u64)field.width, ir.is_float_class(field.cls)), ir.Class.l, 0, ir.temp_ref(value), target, 0)
return
try f.instrs.push(x)
## A fresh temporary holding the address of `slot`, for an access to it.
func slot_address(f: ir.Function*, at: ir.Instr, slot: u32) -> ir.Ref!:
let t = try f.temp(ir.Class.l)
try push(f, at, ir.Op.addr, ir.Class.l, t, ir.slot_ref(slot), ir.none_ref(), 0)
return ir.temp_ref(t)
## Zero in a field's class: a float's through its bits.
func zero_of(f: ir.Function*, at: ir.Instr, cls: ir.Class) -> ir.Ref!:
if cls == ir.Class.w or cls == ir.Class.l:
return ir.const_ref(0)
let t = try f.temp(cls)
try push(f, at, ir.Op.cast, cls, t, ir.const_ref(0), ir.none_ref(), 0)
return ir.temp_ref(t)
# mark: Helpers ================================================================================
## An instruction positioned where `at` came from.
func push(f: ir.Function*, at: ir.Instr, op: ir.Op, cls: ir.Class, dst: u32, a: ir.Ref, b: ir.Ref, extra: u32) -> !:
try f.instrs.push(ir.Instr(op = op, cls = cls, dst = dst, a = a, b = b, extra = extra, extra2 = 0, line = at.line, file = at.file, scope = at.scope, site = at.site))
## `base + offset` as an address operand.
func offset_address(f: ir.Function*, at: ir.Instr, base: ir.Ref, offset: u32) -> ir.Ref!:
if offset == 0:
return base
let t = try f.temp(ir.Class.l)
try push(f, at, ir.Op.add, ir.Class.l, t, base, ir.const_ref((i64)offset), 0)
return ir.temp_ref(t)
## The widest aligned piece of `bytes` bytes at `offset`: padding as a field.
func filler(offset: u32, bytes: u32) -> Field:
var width: u32 = 8
while width > 1 and (offset % width != 0 or width > bytes):
width = width // 2
return Field(offset = offset, width = width, cls = ir.Class.l if width == 8 else ir.Class.w)
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
## A width's bit in `share_copied_fields`'s table: 1, 2, 4 and 8 bytes as bits 0 to 3.
func width_bit(width: u32) -> u8:
match width:
1: return 1
2: return 2
4: return 4
8: return 8
_: return 0
## The bytes a load or store moves.
func access_width(op: ir.Op) -> u32:
match op:
.loadsb, .loadub, .storeb:
return 1
.loadsh, .loaduh, .loadhf, .storeh, .storehf:
return 2
.loadsw, .loaduw, .loads, .storew, .stores:
return 4
.loadl, .loadd, .storel, .stored:
return 8
_:
return 0
## The class of the memory a load reads, as wide as its access: `w` for a word or less,
## whatever the register it fills.
func access_class(op: ir.Op) -> ir.Class:
match op:
.loads:
return ir.Class.s
.loadd:
return ir.Class.d
.loadhf:
return ir.Class.h
.loadl:
return ir.Class.l
_:
return ir.Class.w