Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.43.0

0.43.0 / src / back / opt / loops.lucb

#==============================================================================================
#
#   loops - Natural loops and conservative motion in SSA
#
#   DESCRIPTION:
#       Only a computation that cannot fail may run before a zero-trip loop. Memory motion is
#       restricted further to unescaped, unchanged stack storage with a statically valid
#       access.
#
#==============================================================================================

import back.ir.cfg
import back.ir.ir
import back.opt.load
import support.list

# mark: Natural loops =========================================================================

## A natural loop: its header, its preheader, and which blocks belong to it.
pub struct Natural:
    ## The loop header block.
    pub var header: u32
    ## The block that enters the header from outside the loop.
    pub var preheader: u32
    ## Which blocks, by index, belong to the loop.
    pub var members: bool[]

    ## The natural loop of a back edge into `header`, or none when there is none.
    pub static func find(g: cfg.Graph*, header: u32) -> Natural?!:
        let block = g.blocks.get(header)
        var members = try new bool[g.count()] ---
        # the set goes out with the loop it describes, and is freed on every other way out
        var handed_out = false
        defer:
            if not handed_out:
                free(members)
        for i in 0..<members.length:
            members[i] = false
        members[header] = true
        var pending = try list.List[u32].create(8)
        defer pending.destroy()
        for pred in block.preds.span():
            if g.dominates(header, pred):
                try pending.push(pred)
        if pending.count == 0:
            return none
        while pending.count > 0:
            pending.count -= 1
            let index = pending.items[pending.count]
            if members[index]:
                continue
            members[index] = true
            let predecessor = g.blocks.get(index)
            for pred in predecessor.preds.span():
                try pending.push(pred)
        var preheader = cfg.none_block
        for pred in block.preds.span():
            if not members[pred]:
                if preheader != cfg.none_block:
                    return none
                preheader = pred
        if preheader == cfg.none_block:
            return none
        let entry = g.blocks.get(preheader)
        # the preheader leads to the header alone (a jump table's default is `succ1` too)
        if entry.succ1 != header or entry.succs.count != 1:
            return none
        handed_out = true
        return Natural(header = header, preheader = preheader, members = members)

    ## Release the members set.
    pub func release():
        free(self.members)

# mark: Straight-line blocks =================================================================

## Join each block entered only from the block just above it, by falling in or by that
## block's one jump, to that block: a `for` loop's body and the step block its `continue`
## names become one, the shape the vectorizer reads. Phis that named the joined block's
## label as a predecessor name the block it joined. Whether any joined.
pub func straighten(f: ir.Function*) -> bool!:
    var g = try cfg.Graph.blocks_of(f)
    defer g.release()
    # how many jumps, branches and table entries name each label
    var named = try new u32[(usize)f.labels + 1] ---
    defer free(named)
    var into = try new u32[(usize)f.labels + 1] ---
    defer free(into)
    for i in 0..<named.length:
        named[i] = 0
        into[i] = (u32)i
    for x in f.instrs.span():
        if x.op == ir.Op.jmp or x.op == ir.Op.jnz or x.op == ir.Op.switch_:
            named[x.extra] += 1
        if x.op == ir.Op.jnz:
            named[x.extra2] += 1
        if x.op == ir.Op.switch_:
            for label in f.table_targets(x.extra2):
                named[label] += 1
    var dropped = try new bool[f.instrs.count] ---
    defer free(dropped)
    for i in 0..<dropped.length:
        dropped[i] = false
    var changed = false
    for b in (u32)1..<(u32)g.count():
        let block = g.blocks.get(b)
        if block.label == 0 or block.preds.count != 1 or block.preds.get(0) != b - 1:
            continue
        let above = g.blocks.get(b - 1)
        if above.succs.count != 1 or above.succ1 != b:
            continue
        let last = f.instrs.get(above.end - 1) if above.end > above.start else f.instrs.get(block.start - 1)
        let jumps = above.end > above.start and last.op == ir.Op.jmp
        if (above.end > above.start and ir.is_terminator(last.op) and not jumps) or named[block.label] != (1 if jumps else 0):
            continue
        if block.end > block.start and f.instrs.get(block.start).op == ir.Op.phi:
            continue
        dropped[block.start - 1] = true
        if jumps:
            dropped[above.end - 1] = true
        into[block.label] = into[above.label]
        changed = true
    if not changed:
        return false
    for k in 0..<f.phi_args.count:
        var arg = f.phi_args.get(k)
        if into[arg.pred] != arg.pred:
            arg.pred = into[arg.pred]
            f.phi_args.set(k, arg)
    var kept = try list.List[ir.Instr].create(f.instrs.count)
    for i in 0..<f.instrs.count:
        if not dropped[i]:
            try kept.push(f.instrs.get(i))
    f.instrs.destroy()
    f.instrs = kept
    return true

# mark: Simplifying phis ======================================================================

## Mutually recursive load phis can all denote one value from before a loop.
## Follow only phis, require exactly one external value, and require that value
## to dominate the root. A bounded search leaves larger components unchanged.
pub func simplify_phis(f: ir.Function*, g: cfg.Graph*) -> bool!:
    var definitions = try new u32[f.temps.count + 1] ---
    defer free(definitions)
    var blocks = try definition_blocks(f, g)
    defer free(blocks)
    var replacements = try new ir.Ref[f.temps.count + 1] ---
    defer free(replacements)
    var visited = try new u32[f.temps.count + 1] ---
    defer free(visited)
    for i in 0..<definitions.length:
        definitions[i] = 0
        replacements[i] = ir.none_ref()
        visited[i] = 0
    for i in 0..<f.instrs.count:
        let x = f.instrs.get(i)
        if x.dst != 0:
            definitions[x.dst] = (u32)i + 1
    var pending = try list.List[u32].create(16)
    defer pending.destroy()
    var changed = false
    for root in f.instrs.span():
        if root.op != ir.Op.phi:
            continue
        pending.count = 0
        try pending.push(root.dst)
        var external = ir.none_ref()
        var valid = true
        var examined: u32 = 0
        while pending.count > 0 and valid:
            pending.count -= 1
            let temp = pending.items[pending.count]
            if visited[temp] == root.dst:
                continue
            visited[temp] = root.dst
            examined += 1
            if examined > 64:
                valid = false
                break
            let phi = f.instrs.get(definitions[temp] - 1)
            for k in 0..<phi.extra2:
                let value = f.phi_args.get(phi.extra + k).value
                if value.kind == ir.RefKind.temp and definitions[value.index] != 0 and f.instrs.get(definitions[value.index] - 1).op == ir.Op.phi:
                    try pending.push(value.index)
                elif external.kind == ir.RefKind.none_:
                    external = value
                elif not same(external, value):
                    valid = false
                    break
        if external.kind == ir.RefKind.temp:
            valid = valid and blocks[external.index] != cfg.none_block and g.strictly_dominates(blocks[external.index], blocks[root.dst])
        if valid and external.kind != ir.RefKind.none_:
            replacements[root.dst] = external
            changed = true
    if changed:
        for i in 0..<f.instrs.count:
            var x = f.instrs.get(i)
            if x.op == ir.Op.phi and replacements[x.dst].kind != ir.RefKind.none_:
                x.op = ir.Op.copy
                x.a = replacements[x.dst]
                x.b = ir.none_ref()
                x.extra = 0
                x.extra2 = 0
                f.instrs.set(i, x)
    return changed

## The block that defines each temporary, by index.
pub func definition_blocks(f: ir.Function*, g: cfg.Graph*) -> u32[]!:
    var definitions = try new u32[f.temps.count + 1] ---
    for i in 0..<definitions.length:
        definitions[i] = cfg.none_block
    for b in 0..<g.count():
        let block = g.blocks.get(b)
        for i in block.start..<block.end:
            let x = f.instrs.get(i)
            if x.dst != 0:
                definitions[x.dst] = (u32)b
    return definitions

## Whether `r` is loop-invariant: a constant, or a value defined outside the loop.
pub func invariant(r: ir.Ref, members: bool[], definitions: u32[]) -> bool:
    return r.kind != ir.RefKind.temp or (definitions[r.index] != cfg.none_block and not members[definitions[r.index]])

# mark: Invariant code motion =================================================================

## Rebuild after each moved group: instruction ranges and definition blocks have
## changed. The bound limits compile time on generated functions with many loops.
pub func run(f: ir.Function*) -> !:
    for round in 0..<32:
        var g = try cfg.Graph.over(f)
        defer g.release()
        var changed = false
        var at = g.order.count
        while at > 0:
            at -= 1
            if let loop = try Natural.find(&g, g.order.get(at)):
                var natural = loop
                defer natural.release()
                if try hoist(f, &g, &natural):
                    changed = true
                    break
        if not changed:
            return

func hoist(f: ir.Function*, g: cfg.Graph*, loop: Natural*) -> bool!:
    var definitions = try definition_blocks(f, g)
    defer free(definitions)
    var aliases = try load.Aliases.over(f, g)
    defer aliases.release()
    var moved = try new bool[f.instrs.count] ---
    defer free(moved)
    for i in 0..<moved.length:
        moved[i] = false
    var ordered = try list.List[ir.Instr].create(16)
    defer ordered.destroy()
    # Iteration finds dependent invariants even across unusual block layouts.
    for round in 0..<8:
        var changed = false
        for b in g.order.span():
            if not loop.members[b]:
                continue
            let block = g.blocks.get(b)
            for i in block.start..<block.end:
                let x = f.instrs.get(i)
                if moved[i] or x.dst == 0 or not invariant(x.a, loop.members, definitions) or not invariant(x.b, loop.members, definitions):
                    continue
                if not movable(x.op) and not stable_load(f, g, loop, &aliases, x):
                    continue
                try ordered.push(x)
                moved[i] = true
                definitions[x.dst] = loop.preheader
                changed = true
        if not changed:
            break
    if ordered.count == 0:
        return false
    let preheader = g.blocks.get(loop.preheader)
    var insertion = preheader.end
    if insertion > preheader.start and ir.is_terminator(f.instrs.get(insertion - 1).op):
        insertion -= 1
    var out = try list.List[ir.Instr].create(f.instrs.count)
    for i in 0..=f.instrs.count:
        if i == insertion:
            for x in ordered.span():
                try out.push(x)
        if i < f.instrs.count and not moved[i]:
            try out.push(f.instrs.get(i))
    f.instrs.destroy()
    f.instrs = out
    return true

func stable_load(f: ir.Function*, g: cfg.Graph*, loop: Natural*, aliases: load.Aliases*, x: ir.Instr) -> bool:
    if not load.is_load(x.op):
        return false
    let address = aliases.at(x.a, 0)
    let bytes = width(x.op)
    if address.kind != load.Kind.slot or aliases.escaped(address) or address.offset < 0:
        return false
    if (u64)address.offset + (u64)bytes > (u64)f.slots.get(address.base).size:
        return false
    for b in 0..<g.count():
        if not loop.members[b]:
            continue
        let block = g.blocks.get(b)
        for i in block.start..<block.end:
            let y = f.instrs.get(i)
            if load.is_store(y.op):
                if aliases.relation(address, bytes, y.b, width(y.op)) != load.no_alias:
                    return false
            # A call also writes its ABI result slot, which need not appear in
            # its ordinary arguments. Treat every call as a memory barrier here.
            elif y.op == ir.Op.call or y.op == ir.Op.blit or y.op == ir.Op.zero or y.op == ir.Op.fill or y.op == ir.Op.storev or y.op == ir.Op.asm_ or ((u8)y.op >= (u8)ir.Op.atomic_load and (u8)y.op <= (u8)ir.Op.fence):
                return false
    return true

func width(op: ir.Op) -> i64:
    match op:
        .loadsb, .loadub, .storeb: return 1
        .loadsh, .loaduh, .loadhf, .storeh, .storehf: return 2
        .loadsw, .loaduw, .loads, .storew, .stores: return 4
        _: return 8

func movable(op: ir.Op) -> bool:
    match op:
        .copy, .addr, .add, .sub, .mul, .and_, .or_, .xor, .shl, .lshr, .ashr, .neg: return true
        .fsqrt, .ffloor, .fceil, .ftrunc, .fround, .fabs: return true
        .ceq, .cne, .cslt, .csle, .csgt, .csge, .cult, .cule, .cugt, .cuge: return true
        .extsb, .extub, .extsh, .extuh, .extsw, .extuw, .cast, .exth, .exts, .truncs, .truncd: return true
        _: return false

## Whether two references are the same temporary or the same constant.
pub func same(a: ir.Ref, b: ir.Ref) -> bool:
    return a.kind == b.kind and a.index == b.index and a.value == b.value and a.name == b.name