Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.46.0

0.46.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