dymokomi/luce-base
Source of release 0.43.0
0.43.0 / src / back / native / sharing.lucb
#==============================================================================================
#
# sharing - Frame homes shared by values whose lives never meet
#
# DESCRIPTION:
# A slot or a spilled temporary needs its home only while its value lives. Two whose
# lives do not overlap take the same bytes, as a C compiler colors its stack: the
# locals of one `match` arm and those of the next, the results of fallible calls in
# different statements, the spills of unrelated temporaries. A temporary's life is
# the register allocator's own. A slot's is the span of every use of its address,
# drawn out over each loop it is used in, since its bytes carry a value around the
# back edge. A slot whose address leaves the function's sight keeps its home to
# itself: stored, returned, passed to a call or asm, put in a register or an atomic.
#
#==============================================================================================
import back.ir.cfg
import back.ir.ir
import back.native.regalloc
import memory
# mark: Lives =================================================================================
## When a slot or temporary's value lives: doubled positions from `low` up to `high`
## (one past), as `regalloc.Lives` counts them; `low == unused` for one never used.
pub struct Span:
## The first position the value lives at, `unused` or `pinned`.
pub var low: u32
## One past the last position it lives at.
pub var high: u32
## A span nothing is in.
pub let unused: u32 = 0xFFFFFFFF
## A home only its own value may use, the whole function long.
pub let pinned: u32 = 0xFFFFFFFE
## The spans of every temporary: the hull of its ranges.
pub func temp_spans(f: ir.Function*, lives: const regalloc.Lives*) -> Span[]!:
let n = f.temps.count
let spans = try new Span[n + 1] ---
for t in 0..<n + 1:
spans[t] = Span(low = unused, high = 0)
for t in 1..<n + 1:
let end = lives.life_end(u32(t))
if end != 0:
# one past the instruction that last reads it, so no instruction both reads it
# and writes another value to the same home
spans[t] = Span(low = lives.life_start(u32(t)), high = end + 2)
return spans
## The spans of every slot: its address's uses, over the loops they are in, from the
## function's start for a parameter's; `pinned` for a slot whose address escapes into
## memory or out of the function, or reaches a temporary a copy defines (a loop's carried
## value, used before it is written). One pass forwards.
pub func slot_spans(f: ir.Function*, g: const cfg.Graph*) -> Span[]!:
let ns = f.slots.count
let spans = try new Span[ns + 1] ---
for s in 0..<ns + 1:
spans[s] = Span(low = unused, high = 0)
# a parameter's slot is written by the prologue, before the first instruction, and
# lives on only as far as its uses reach: once promoted, that is its entry load. The
# entry loads a generator takes straight from their registers are all done in the
# prologue too, so every parameter's slot lives through all of them
var entry: u32 = 0
while (usize)entry < f.instrs.count and entry_instruction(f.instrs.get((usize)entry).op):
entry += 1
for parameter in f.params.span():
spans[parameter.slot + 1] = Span(low = 0, high = 2 * entry + 2)
# 1 + the slot whose address a temporary holds or was computed from, 0 for none
let origin = try new u32[f.temps.count + 1] ---
defer free(origin)
for t in 0..<origin.length:
origin[t] = 0
var i: u32 = 0
while (usize)i < f.instrs.count:
let x = f.instrs.get((usize)i)
let at = 2 * i
let value = derived(x.a, origin)
let place = derived(x.b, origin)
# the address itself kept where this function cannot see its uses: stored, returned,
# put in a register, handed to asm or an atomic operation
if value != 0 and escapes_value(x.op):
spans[value].low = pinned
if place != 0 and is_atomic(x.op):
spans[place].low = pinned
if value != 0:
widen(spans, value, at)
if place != 0:
widen(spans, place, at)
let source = value if value != 0 else place
# an address handed to a call or asm may be kept by it (`push_break_entry(fd, &be)`
# stores it for later) or answered back (`memcpy` its destination): its slot is the
# local's alone for the whole function
let (start, count) = ir.argument_range(f, x)
for k in 0..<count:
let argument = derived(f.args.get(start + k).value, origin)
if argument != 0:
spans[argument].low = pinned
if x.op == ir.Op.call:
let call = f.calls.get(x.extra)
if call.has_result and call.result_size > 0 and not call.result_words:
widen(spans, call.result_slot + 1, at)
# what an address flows into, unless it is only read through
if x.dst != 0 and source != 0 and not is_load(x.op) and not ir.is_comparison(x.op):
if x.op == ir.Op.copy or origin[x.dst] != 0:
# a copy carries a value around a loop: its temporary may be read before
# this write, which a forward pass cannot see; a second writer likewise
spans[source].low = pinned
if origin[x.dst] != 0:
spans[origin[x.dst]].low = pinned
origin[x.dst] = source
i += 1
try over_loops(g, spans)
return spans
## Whether `op` may be among a function's leading entry loads (`selection.entry_loads`).
func entry_instruction(op: ir.Op) -> bool:
return op == ir.Op.addr or op == ir.Op.dbg or ((u8)op >= (u8)ir.Op.loadsb and (u8)op <= (u8)ir.Op.loadd)
## A slot's value may cross a back edge: a span that meets a loop covers all of it. The
## loops' extents are merged into disjoint runs first, so each slot is widened once.
func over_loops(g: const cfg.Graph*, spans: Span[]) -> !:
# one extent per edge at most: a jump table's block has more than two
var edges: usize = 1
for b in g.blocks.span():
edges += b.succs.count
var lows = try new u32[edges] ---
defer free(lows)
var highs = try new u32[edges] ---
defer free(highs)
var n: usize = 0
for b in g.blocks.span():
for successor in b.succs.span():
let head = g.blocks.get((usize)successor).start
if head <= b.start and n < lows.length:
lows[n] = 2 * head
highs[n] = 2 * b.end
n += 1
if n == 0:
return
# sort by start, then merge overlapping extents
var k: usize = 1
while k < n:
let low = lows[k]
let high = highs[k]
var j = k
while j > 0 and lows[j - 1] > low:
lows[j] = lows[j - 1]
highs[j] = highs[j - 1]
j -= 1
lows[j] = low
highs[j] = high
k += 1
var runs: usize = 0
for r in 0..<n:
if runs > 0 and lows[r] <= highs[runs - 1]:
if highs[r] > highs[runs - 1]:
highs[runs - 1] = highs[r]
else:
lows[runs] = lows[r]
highs[runs] = highs[r]
runs += 1
for s in 1..<spans.length:
let span = spans[s]
if span.low >= pinned:
continue
var low = span.low
var high = span.high
for r in 0..<runs:
if lows[r] < high and highs[r] > low:
low = lows[r] if lows[r] < low else low
high = highs[r] if highs[r] > high else high
spans[s] = Span(low = low, high = high)
## Take in position `at` (an instruction's reads and its result) for slot `k`, 1-based.
func widen(spans: Span[], k: u32, at: u32):
let span = spans[k]
if span.low == pinned:
return
spans[k] = Span(low = at if span.low == unused or at < span.low else span.low, high = at + 2 if at + 2 > span.high else span.high)
## The slot, 1-based, an operand holds the address of (directly or computed from), or 0.
func derived(r: ir.Ref, origin: u32[]) -> u32:
if r.kind == ir.RefKind.slot:
return r.index + 1
if r.kind == ir.RefKind.temp and (usize)r.index < origin.length:
return origin[r.index]
return 0
## Whether an operation keeps its first operand where this function cannot follow it: a
## store's value (a vector's too), a returned value, a register's, asm's, an atomic's.
func escapes_value(op: ir.Op) -> bool:
return is_store(op) or op == ir.Op.storev or op == ir.Op.ret or op == ir.Op.asm_ or op == ir.Op.set_reg or is_atomic(op)
func is_atomic(op: ir.Op) -> bool:
return (u8)op >= (u8)ir.Op.atomic_load and (u8)op <= (u8)ir.Op.atomic_cas
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
# mark: Packing ===============================================================================
## A value wanting a frame home: its bytes, their alignment, and when it lives.
pub struct Item:
## How many bytes it needs.
pub var size: u64
## The alignment of its home.
pub var align: u64
## When it lives.
pub var span: Span
## The home of each item below `base`, an offset below the frame pointer, and the lowest
## offset handed out. Items are placed in the order their lives begin, each at the first
## offset where it meets no item still alive -- first fit, as a C compiler colors its
## stack -- so a dead value's bytes go to any later one they fit, not only to one of the
## same size. A pinned or never-used item lives the whole function: it takes the first
## gap no item placed before it covers.
pub func pack(items: const Item[], base: u64) -> (u64[], u64)!:
let n = items.length
let homes = try new u64[n] ---
errdefer free(homes)
let order = try by_low(items)
defer free(order)
# the items placed whose lives may still meet the next ones, as indices
let active = try new u32[n if n > 0 else 1] ---
defer free(active)
var live: usize = 0
var end = base
# how many of `order` have their homes
var done: usize = 0
for k in order:
let item = items[(usize)k]
let size = bytes(item)
let align = item.align if item.align > 0 else 1
var home: u64 = 0
if item.span.low < pinned:
# a later item begins no earlier, so one that has died stays dead
var kept: usize = 0
for a in 0..<live:
let other = items[(usize)active[a]].span
if other.low >= pinned or other.high > item.span.low:
active[kept] = active[a]
kept += 1
live = kept
home = round_up(base + size, align)
var moved = true
while moved:
moved = false
for a in 0..<live:
let at = homes[(usize)active[a]]
let low = at - bytes(items[(usize)active[a]])
if low < home and home - size < at:
home = round_up(at + size, align)
moved = true
elif done > most_searched:
home = round_up(end + size, align)
else:
# a whole-function item meets every other: the first gap none of them covers
home = round_up(base + size, align)
var moved = true
while moved:
moved = false
for placed in order[..<done]:
let at = homes[(usize)placed]
let low = at - bytes(items[(usize)placed])
if low < home and home - size < at:
home = round_up(at + size, align)
moved = true
homes[(usize)k] = home
done += 1
end = home if home > end else end
active[live] = k
live += 1
return (homes, end)
## The most items placed before a whole-function one that `pack` searches for a gap in;
## past it, the item goes below them all, so a function of thousands of kept locals
## lays out in time.
let most_searched: usize = 4096
## The bytes an item takes: an empty one still one.
func bytes(item: Item) -> u64:
return item.size if item.size > 0 else 1
## The item indices ordered by when their lives begin, equal ones in their own order;
## pinned and never-used ones (the highest `low`) last.
func by_low(items: const Item[]) -> u32[]!:
let n = items.length
var order = try new u32[n] ---
errdefer free(order)
var other = try new u32[n] ---
defer free(other)
for k in 0..<n:
order[k] = u32(k)
# bottom-up merge sort: stable, and n log n for the largest functions
var width: usize = 1
while width < n:
var start: usize = 0
while start < n:
let middle = start + width if start + width < n else n
let stop = start + 2 * width if start + 2 * width < n else n
var i = start
var j = middle
var out = start
while out < stop:
if i < middle and (j >= stop or items[(usize)order[i]].span.low <= items[(usize)order[j]].span.low):
other[out] = order[i]
i += 1
else:
other[out] = order[j]
j += 1
out += 1
start = stop
let swap = order
order = other
other = swap
width *= 2
return order
func round_up(value: u64, align: u64) -> u64:
return (value + align - 1) // align * align