Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.44.0

0.44.0 / src / back / opt / switches.lucb

#==============================================================================================
#
#   switches - A chain of equality tests on one value becomes a jump table
#
#   DESCRIPTION:
#       `if s == 4: … elif s == 3: … elif s == 2: … elif s == 1: …` tests its value once
#       per arm in turn, as C's `switch` ported to `if`/`elif` does. Where four or more
#       such tests follow each other through their false sides, each test after the first
#       alone in its block and entered only from the test before it, and the values are
#       dense (`ir.dense_range`, as a `match` decides), the head's branch becomes the
#       `switch` a `match` on the same values lowers to: one subtraction, one bounds test
#       and one indirect jump, which a predictor follows per value instead of through a
#       chain of branches whose outcomes depend on one another. Each value's first test
#       names its target, the last test's false side is the default, and the targets'
#       phis take what the chain's blocks gave them from the head instead. A target with
#       phis entered by more than one of the chain's edges, or a test of any other form,
#       ends the chain where it is.
#
#==============================================================================================

import back.ir.cfg
import back.ir.ir
import memory
import support.list

## The most tests a chain takes.
let longest_chain: usize = 512

## Convert every chain of `f`; whether one was converted.
pub func run(f: ir.Function*) -> bool!:
    with memory.heap:
        var g = try cfg.Graph.blocks_of(f)
        defer g.release()
        var definitions = try new u32[f.temps.count + 1] ---
        defer free(definitions)
        for t in 0..<definitions.length:
            definitions[t] = 0
        for i in 0..<f.instrs.count:
            let x = f.instrs.get(i)
            if x.dst != 0 and (usize)x.dst < definitions.length:
                definitions[(usize)x.dst] = u32(i + 1)
        # each block heads or joins at most one chain; `taken` marks the chains' blocks
        var taken = try new bool[g.blocks.count] ---
        defer free(taken)
        for b in 0..<taken.length:
            taken[b] = false
        var chains = try list.List[Chain].create(4)
        defer release_chains(&chains)
        for h in 0..<g.blocks.count:
            if taken[h] or g.blocks.get(h).rpo == cfg.none_block:
                continue
            if let found = try chain_at(f, &g, definitions, u32(h)):
                var chain = found
                if try accepted(f, &g, &chain):
                    for b in chain.blocks.span():
                        taken[(usize)b] = true
                    try chains.push(chain)
                else:
                    chain.release()
        if chains.count == 0:
            return false
        try rewrite(f, &g, &chains, taken)
        return true

# mark: Recognising a chain =====================================================================

## One test of a chain: the block's value compared with `value`, then to `then`'s label,
## else to `other`'s.
struct Test:
    var subject: u32
    var cls: ir.Class
    var value: i64
    var then: u32
    var other: u32
    ## The comparison's instruction index + 1, and its result temporary.
    var compare: u32
    var result: u32

## A chain: its blocks in order (the head first), each value's target label, sorted by
## value, and the default label.
struct Chain:
    var blocks: list.List[u32]
    var values: list.List[i64]
    var targets: list.List[u32]
    var default: u32
    var subject: u32
    var cls: ir.Class

    func release():
        self.blocks.destroy()
        self.values.destroy()
        self.targets.destroy()

func release_chains(chains: list.List[Chain]*):
    for k in 0..<chains.count:
        chains.items[k].release()
    chains.destroy()

## The test block `b` ends with: a branch on `t == constant` or `t != constant` of an
## integer temporary, the constant held at the comparison's width.
func test_of(f: ir.Function*, definitions: u32[], block: cfg.Block) -> Test?:
    if block.end == block.start:
        return none
    let branch = f.instrs.get((usize)block.end - 1)
    if branch.op != ir.Op.jnz or branch.a.kind != ir.RefKind.temp or (usize)branch.a.index >= definitions.length:
        return none
    let at = definitions[(usize)branch.a.index]
    if at == 0 or at <= block.start or at > block.end:
        return none
    let compare = f.instrs.get((usize)at - 1)
    if (compare.op != ir.Op.ceq and compare.op != ir.Op.cne) or (compare.cls != ir.Class.w and compare.cls != ir.Class.l):
        return none
    var subject = compare.a
    var constant = compare.b
    if subject.kind == ir.RefKind.constant:
        subject = compare.b
        constant = compare.a
    if subject.kind != ir.RefKind.temp or constant.kind != ir.RefKind.constant:
        return none
    # a word compares the low 32 bits: the constant as those bits, signed
    let value = (i64)(i32)(constant.value & 0xFFFFFFFF) if compare.cls == ir.Class.w else constant.value
    let equal = compare.op == ir.Op.ceq
    return Test(subject = subject.index, cls = compare.cls, value = value, then = branch.extra if equal else branch.extra2, other = branch.extra2 if equal else branch.extra, compare = at, result = compare.dst)

## Whether block `block` holds nothing but its test: the comparison, the branch, and
## positions for a debugger.
func only_test(f: ir.Function*, block: cfg.Block, tested: Test) -> bool:
    for i in block.start..<block.end - 1:
        let x = f.instrs.get((usize)i)
        if i + 1 != tested.compare and x.op != ir.Op.dbg:
            return false
    return true

## The chain headed by block `h`, when its tests are at least four: the head's test on a
## value, then each block its false side enters that tests the same value at the same
## width, alone, entered from the test before it only.
func chain_at(f: ir.Function*, g: cfg.Graph*, definitions: u32[], h: u32) -> Chain?!:
    let first = test_of(f, definitions, g.blocks.get((usize)h)) else return none
    var chain = Chain(blocks = try list.List[u32].create(8), values = try list.List[i64].create(8), targets = try list.List[u32].create(8), default = first.other, subject = first.subject, cls = first.cls)
    try chain.blocks.push(h)
    try add_case(&chain, first.value, first.then)
    var last = first
    while chain.blocks.count < longest_chain:
        let next = g.block_of(last.other)
        if next == cfg.none_block or next == h or in_chain(&chain, next):
            break
        let block = g.blocks.get((usize)next)
        if block.preds.count != 1 or block.preds.get(0) != chain.blocks.get(chain.blocks.count - 1):
            break
        let link = test_of(f, definitions, block) else break
        if link.subject != first.subject or link.cls != first.cls or not only_test(f, block, link) or holds(&chain, link.value):
            break
        try chain.blocks.push(next)
        try add_case(&chain, link.value, link.then)
        chain.default = link.other
        last = link
    if chain.blocks.count < 4:
        chain.release()
        return none
    return chain

## Whether a test of the chain names `value` already: a second test of it ends the chain,
## whose default it then is.
func holds(chain: Chain*, value: i64) -> bool:
    for v in chain.values.span():
        if v == value:
            return true
    return false

## Add a value's target, the values kept sorted (signed): insertion, since a chain is short.
func add_case(chain: Chain*, value: i64, target: u32) -> !:
    try chain.values.push(value)
    try chain.targets.push(target)
    var j = chain.values.count - 1
    while j > 0 and chain.values.get(j - 1) > value:
        chain.values.set(j, chain.values.get(j - 1))
        chain.targets.set(j, chain.targets.get(j - 1))
        j -= 1
    chain.values.set(j, value)
    chain.targets.set(j, target)

func in_chain(chain: Chain*, b: u32) -> bool:
    for c in chain.blocks.span():
        if c == b:
            return true
    return false

## Whether the chain becomes a jump table: its values dense enough, no target one of its
## own blocks, and every target with phis entered by one of its edges only.
func accepted(f: ir.Function*, g: cfg.Graph*, chain: Chain*) -> bool!:
    if ir.dense_range(chain.values.span()) == none:
        return false
    var labels = try list.List[u32].create(chain.targets.count + 1)
    defer labels.destroy()
    for t in chain.targets.span():
        try labels.push(t)
    try labels.push(chain.default)
    for k in 0..<labels.count:
        let target = g.block_of(labels.get(k))
        if target == cfg.none_block or in_chain(chain, target):
            return false
        let block = g.blocks.get((usize)target)
        if block.start < block.end and f.instrs.get((usize)block.start).op == ir.Op.phi:
            for j in 0..<labels.count:
                if j != k and labels.get(j) == labels.get(k):
                    return false
    return true

# mark: Rewriting ===============================================================================

## Each chain's head ends in its `switch`; the other tests' blocks go, and their
## comparisons with them unless something else reads one.
func rewrite(f: ir.Function*, g: cfg.Graph*, chains: list.List[Chain]*, taken: bool[]) -> !:
    var heads = try new u32[g.blocks.count] ---
    defer free(heads)
    for b in 0..<heads.length:
        heads[b] = cfg.none_block
    for k in 0..<chains.count:
        heads[(usize)chains.items[k].blocks.get(0)] = u32(k)
    let reads = try read_counts(f)
    defer free(reads)
    var out = try list.List[ir.Instr].create(f.instrs.count + 8)
    for b in 0..<g.blocks.count:
        let block = g.blocks.get(b)
        if taken[b] and heads[b] == cfg.none_block:
            continue
        if block.label != 0:
            try out.push(ir.Instr(op = ir.Op.label, cls = ir.Class.l, dst = 0, a = ir.none_ref(), b = ir.none_ref(), extra = block.label, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
        if heads[b] == cfg.none_block:
            for i in block.start..<block.end:
                try out.push(f.instrs.get((usize)i))
            continue
        let chain = &chains.items[(usize)heads[b]]
        let branch = f.instrs.get((usize)block.end - 1)
        # each test's comparison goes with its branch unless something else reads it; a
        # later test's then moves up to the head, which dominates whatever its block did,
        # and the rest of that block was positions alone
        for c in 0..<chain.blocks.count:
            let link = g.blocks.get((usize)chain.blocks.get(c))
            let condition = f.instrs.get((usize)link.end - 1).a.index
            for i in link.start..<link.end - 1:
                let x = f.instrs.get((usize)i)
                let read_elsewhere = x.dst == condition and reads[(usize)x.dst] > 1
                if read_elsewhere or (c == 0 and x.dst != condition):
                    try out.push(x)
        try push_switch(f, chain, branch, &out)
        try relabel_phis(f, g, chain, block.label)
    f.instrs.destroy()
    f.instrs = out

## The `switch` over the chain's values, at the head's branch's position.
func push_switch(f: ir.Function*, chain: Chain*, branch: ir.Instr, out: list.List[ir.Instr]*) -> !:
    let entries = ir.dense_range(chain.values.span()) else return
    let low = chain.values.get(0)
    try f.jump_tables.push(ir.Table(low = low, start = u32(f.jump_labels.count), count = u32(entries)))
    let start = f.jump_labels.count
    for k in 0..<entries:
        try f.jump_labels.push(chain.default)
    for k in 0..<chain.values.count:
        let entry = (usize)((u64)chain.values.get(k) -% (u64)low)
        f.jump_labels.set(start + entry, chain.targets.get(k))
    try out.push(ir.Instr(op = ir.Op.switch_, cls = chain.cls, dst = 0, a = ir.temp_ref(chain.subject), b = ir.none_ref(), extra = chain.default, extra2 = u32(f.jump_tables.count - 1), line = branch.line, file = branch.file, scope = branch.scope, site = branch.site))

## What the chain's blocks gave the targets' phis, the head gives now.
func relabel_phis(f: ir.Function*, g: cfg.Graph*, chain: Chain*, head: u32) -> !:
    var labels = try list.List[u32].create(chain.blocks.count)
    defer labels.destroy()
    for b in chain.blocks.span():
        try labels.push(g.blocks.get((usize)b).label)
    var targets = try list.List[u32].create(chain.targets.count + 1)
    defer targets.destroy()
    for t in chain.targets.span():
        try targets.push(t)
    try targets.push(chain.default)
    for label in targets.span():
        let block = g.blocks.get((usize)g.block_of(label))
        var at = block.start
        while at < block.end and f.instrs.get((usize)at).op == ir.Op.phi:
            let phi = f.instrs.get((usize)at)
            for k in 0..<phi.extra2:
                let entry = f.phi_args.get((usize)(phi.extra + k))
                for chained in labels.span():
                    if entry.pred == chained:
                        f.phi_args.items[(usize)(phi.extra + k)].pred = head
            at += 1

## How many times each temporary is read: by an instruction, a phi, or a pooled argument.
func read_counts(f: ir.Function*) -> u32[]!:
    var reads = try new u32[f.temps.count + 1] ---
    for t in 0..<reads.length:
        reads[t] = 0
    for x in f.instrs.span():
        count_read(reads, x.a)
        count_read(reads, x.b)
    for entry in f.phi_args.span():
        count_read(reads, entry.value)
    for arg in f.args.span():
        count_read(reads, arg.value)
    return reads

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