Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.43.0

0.43.0 / src / back / opt / addresses.lucb

#==============================================================================================
#
#   addresses - Accesses at constant distances from one address share it
#
#   DESCRIPTION:
#       `values[at * 3 - 2]` is `base + (at * 3 - 2) * 8`: each neighbouring element costs its
#       own index arithmetic, a multiply and an add before the load. Addresses wrap as every
#       `l` sum does, so `base + (x + k) * s` is `(base + x * s) + k * s` exactly, and the
#       accesses of one block at `x + k` for several constants `k` all add a constant to
#       one address, `base + x * s`, formed once; the generators then fold each constant into
#       its load or store (`[x1, #-16]`). Only an access's address is rewritten, so what an
#       index is checked against is unchanged.
#
#==============================================================================================

import back.ir.ir
import support.list

# mark: The pass ================================================================================

## One address `base + x * scale` formed in the block being rewritten: the temporary
## holding it, and the index of the instruction forming it.
struct Anchor:
    var base: ir.Ref
    var index: ir.Ref
    var op: ir.Op
    var scale: i64
    var at: u32
    var formed: usize

## The rewrite over `f`, in single-assignment form; whether anything changed.
pub func run(f: ir.Function*) -> bool!:
    var counts = try new u32[f.temps.count + 1] ---
    defer free(counts)
    var defs = try new u32[f.temps.count + 1] ---
    defer free(defs)
    for k in 0..<counts.length:
        counts[k] = 0
        defs[k] = 0
    for i in 0..<f.instrs.count:
        let x = f.instrs.get(i)
        if x.dst != 0 and (usize)x.dst < defs.length:
            defs[x.dst] = (u32)i + 1
        count(counts, x.a)
        count(counts, x.b)
        let (start, n) = ir.argument_range(f, x)
        for k in 0..<n:
            count(counts, f.args.get(start + k).value)
    for k in 0..<f.phi_args.count:
        count(counts, f.phi_args.get(k).value)
    var anchors = try list.List[Anchor].create(8)
    defer anchors.destroy()
    var block_start: usize = 0
    var changed = false
    for i in 0..<f.instrs.count:
        let x = f.instrs.get(i)
        if ends_block(x.op):
            anchors.count = 0
            block_start = i + 1
            continue
        if let address = accessed(x):
            if try rewrite(f, address, block_start, i, counts, defs, &anchors):
                changed = true
    return changed

func count(counts: u32[], r: ir.Ref):
    if r.kind == ir.RefKind.temp and (usize)r.index < counts.length:
        counts[r.index] += 1

func ends_block(op: ir.Op) -> bool:
    return op == ir.Op.label or op == ir.Op.jmp or op == ir.Op.jnz or op == ir.Op.switch_ or op == ir.Op.ret or op == ir.Op.trap_

## The address a load or store reads, when it is a temporary.
func accessed(x: ir.Instr) -> ir.Ref?:
    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
    let address = x.a if loads else x.b
    if (loads or stores) and address.kind == ir.RefKind.temp:
        return address
    return none

## The instruction defining `r` when it is in the block, before `at`: its index.
func defined_between(r: ir.Ref, defs: u32[], low: usize, at: usize) -> usize?:
    if r.kind != ir.RefKind.temp or defs[r.index] == 0:
        return none
    let d = (usize)defs[r.index] - 1
    if d < low or d >= at:
        return none
    return d

# mark: One access ==============================================================================

## The access at `at` reads `address`, `base + (x + k) * scale`: it becomes an existing
## anchor for `base`, `x` and `scale` plus `k * scale`, or, when there is none yet, the
## index and the product it goes through (each read only there) become that anchor.
func rewrite(f: ir.Function*, address: ir.Ref, low: usize, at: usize, counts: u32[], defs: u32[], anchors: list.List[Anchor]*) -> bool!:
    let a_at = defined_between(address, defs, low, at) else return false
    let sum = f.instrs.get(a_at)
    if sum.op != ir.Op.add or sum.cls != ir.Class.l:
        return false
    # `base + product`, in either order
    var base = sum.a
    var product = sum.b
    var p_found = defined_between(product, defs, low, a_at)
    if not scaled(f, p_found):
        base = sum.b
        product = sum.a
        p_found = defined_between(product, defs, low, a_at)
        if not scaled(f, p_found):
            return false
    let p_at = p_found else return false
    let times = f.instrs.get(p_at)
    let scale = times.b.value if times.op == ir.Op.mul else (i64)1 << times.b.value
    # the index, `x + k`, `x - k` or `x` alone
    var index = times.a
    var k: i64 = 0
    if let i_at = defined_between(times.a, defs, low, p_at):
        let step = f.instrs.get(i_at)
        if step.cls == ir.Class.l and step.b.kind == ir.RefKind.constant and step.a.kind == ir.RefKind.temp:
            if step.op == ir.Op.add:
                index = step.a
                k = step.b.value
            elif step.op == ir.Op.sub:
                index = step.a
                k = 0 -% step.b.value
    for anchor in anchors.span():
        # an anchor formed after this address (which an earlier access used later) is no use
        if same(anchor.base, base) and same(anchor.index, index) and anchor.op == times.op and anchor.scale == scale and anchor.formed < a_at:
            if anchor.at == address.index:
                return false
            set(f, a_at, ir.Op.add, ir.temp_ref(anchor.at), ir.const_ref(k *% scale))
            return true
    if k == 0:
        try anchors.push(Anchor(base = base, index = index, op = times.op, scale = scale, at = address.index, formed = a_at))
        return false
    # no anchor yet: the index becomes `x * scale`, the product `base + x * scale`, which
    # later accesses share, and the address that plus `k * scale`
    let i_at = defined_between(times.a, defs, low, p_at) else return false
    if counts[times.a.index] != 1 or counts[times.dst] != 1:
        return false
    if let b_at = defined_between(base, defs, low, at):
        if b_at >= p_at:
            return false
    set(f, i_at, times.op, index, times.b)
    set(f, p_at, ir.Op.add, base, times.a)
    set(f, a_at, ir.Op.add, ir.temp_ref(times.dst), ir.const_ref(k *% scale))
    try anchors.push(Anchor(base = base, index = index, op = times.op, scale = scale, at = times.dst, formed = p_at))
    return true

## Whether the instruction at `found` multiplies an `l` temporary by a constant, or shifts
## it left by one.
func scaled(f: ir.Function*, found: usize?) -> bool:
    let at = found else return false
    let x = f.instrs.get(at)
    if x.cls != ir.Class.l or x.a.kind != ir.RefKind.temp or x.b.kind != ir.RefKind.constant:
        return false
    return (x.op == ir.Op.mul and x.b.value > 0) or (x.op == ir.Op.shl and x.b.value >= 0 and x.b.value < 63)

func set(f: ir.Function*, at: usize, op: ir.Op, a: ir.Ref, b: ir.Ref):
    var x = f.instrs.get(at)
    x.op = op
    x.a = a
    x.b = b
    f.instrs.set(at, x)

func same(a: ir.Ref, b: ir.Ref) -> bool:
    if a.kind != b.kind:
        return false
    if a.kind == ir.RefKind.temp:
        return a.index == b.index
    if a.kind == ir.RefKind.constant:
        return a.value == b.value
    return false