Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.41.0

0.41.0 / src / back / native / incoming.lucb

#==============================================================================================
#
#   incoming - Parameters moved from their argument registers into their registers
#
#   DESCRIPTION:
#       A promoted scalar parameter is read once, by a load at the function's entry
#       (`selection.entry_loads`). Rather than store the argument to the parameter's slot
#       in the prologue and load it back, the generator moves it from the register it
#       arrives in to where the load's result lives. The moves run together, as a parallel
#       copy: a result may live in another argument's register, so each move waits until
#       no other move still reads its destination, and a cycle is broken by parking one
#       argument in the target's scratch register.
#
#==============================================================================================

import memory
import support.list

## A parameter that moves from its argument register into its entry load's result: the
## load's index, the argument's number among the integer or the float registers.
pub struct Move:
    ## The entry load's index.
    pub var at: u32
    ## The argument register's number.
    pub var argument: u8
    ## Whether it is a float register.
    pub var float: bool

## Nothing: a destination that is no argument register.
pub let no_argument: u8 = 0xFF

## One step of the sequence: move `index`, reading its argument's register, or its parked
## copy when `parked`; or, when `park`, copy that argument into the scratch register first.
pub struct Step:
    ## Which move.
    pub var index: u32
    ## Copy the move's argument into scratch rather than move it.
    pub var park: bool
    ## The move reads the scratch register, not its argument.
    pub var parked: bool

## An order for the moves from argument registers `sources[k]` to destinations
## `destinations[k]` (the argument register a destination is, or `no_argument`) that reads
## every argument before any move overwrites it.
pub func sequence(sources: const u8[], destinations: const u8[]) -> list.List[Step]!:
    let n = sources.length
    var steps = try list.List[Step].create(n + 2)
    var pending = try new bool[n + 1] ---
    defer free(pending)
    var parked = try new bool[n + 1] ---
    defer free(parked)
    for k in 0..<n:
        pending[k] = true
        parked[k] = false
    var left = n
    while left > 0:
        var moved = false
        for k in 0..<n:
            if pending[k] and not read_by_other(sources, destinations[k], pending, parked, k):
                try steps.push(Step(index = u32(k), park = false, parked = parked[k]))
                pending[k] = false
                left -= 1
                moved = true
        if not moved:
            # every pending destination is still read: the moves wait on a cycle. The one
            # that reads the first pending move's destination parks its argument, which lets
            # that move go and the cycle unwind; parking a move nobody waits on (the head of
            # a chain that leads into the cycle) would free nothing, and the next round would
            # be stuck the same way for ever
            var first = n
            for k in 0..<n:
                if pending[k]:
                    first = k
                    break
            var blocker = n
            for k in 0..<n:
                if k != first and pending[k] and not parked[k] and sources[k] == destinations[first]:
                    blocker = k
                    break
            # a move reads every pending destination, or none would be stuck
            assert(blocker != n)
            try steps.push(Step(index = u32(blocker), park = true, parked = false))
            parked[blocker] = true
    return steps

## Whether a pending move other than `k`, still reading its argument, reads `register`.
func read_by_other(sources: const u8[], register: u8, pending: bool[], parked: bool[], k: usize) -> bool:
    if register == no_argument:
        return false
    for j in 0..<sources.length:
        if j != k and pending[j] and not parked[j] and sources[j] == register:
            return true
    return false

## Run `steps` over registers holding their own numbers, with 9 as the scratch; what each
## destination holds after.
func simulate(sources: const u8[], destinations: const u8[], steps: Step[]) -> u8[10]:
    var regs: u8[10] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    for step in steps:
        let k = (usize)step.index
        if step.park:
            regs[9] = regs[(usize)sources[k]]
        else:
            regs[(usize)destinations[k]] = regs[9] if step.parked else regs[(usize)sources[k]]
    return regs

test "a parallel copy reads every argument before it is overwritten, through a cycle":
    var backing: u8[65536]
    var arena = memory.FixedBuffer.over(backing)
    with arena:
        # 0 -> 1, 1 -> 2, 2 -> 0: a cycle; 3 -> 4 and 4 -> 5: a chain
        let sources: u8[5] = [0, 1, 2, 3, 4]
        let destinations: u8[5] = [1, 2, 0, 4, 5]
        var steps = try sequence(sources[0..<5], destinations[0..<5])
        let regs = simulate(sources[0..<5], destinations[0..<5], steps.span())
        assert(regs[1] == 0 and regs[2] == 1 and regs[0] == 2 and regs[4] == 3 and regs[5] == 4)
        # a swap
        let two: u8[2] = [0, 1]
        let back: u8[2] = [1, 0]
        var swap = try sequence(two[0..<2], back[0..<2])
        let swapped = simulate(two[0..<2], back[0..<2], swap.span())
        assert(swapped[0] == 1 and swapped[1] == 0)
        # the first move waits on a swap it is not part of: 5 -> 0 wants register 0, which
        # the swap 0 -> 1, 1 -> 0 still reads; parking the 5 would free nothing
        let chained: u8[3] = [5, 0, 1]
        let into: u8[3] = [0, 1, 0]
        var chain = try sequence(chained[0..<3], into[0..<3])
        assert(chain.count <= 5)