Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.43.0

0.43.0 / src / back / opt / dessa.lucb

#==============================================================================================
#
#   dessa - Phis into copies, for the generators
#
#   DESCRIPTION:
#       A generator knows no phi: it wants every value produced by an instruction it can
#       emit. This pass gives each phi's temporary its value at the end of every
#       predecessor, by a copy placed before the predecessor's jump, so the temporary is
#       assigned in several places and read at the join, which the frame allocator accepts
#       (a temporary's live range runs from its first assignment to its last use). The
#       copies of one edge are parallel: when one reads what another writes, every source
#       goes through a fresh temporary first. A predecessor that branches two ways (or
#       through a jump table) cannot carry another block's copies, since they would run on
#       every edge: the edge gets a block of its own, the copies and a jump, and the branch
#       (or each table entry) is retargeted to it.
#
#==============================================================================================

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

# mark: Moves on each edge ====================================================================

## A copy to place: at the end of block `at`, `dst = value`.
struct Move:
    var at: u32
    var dst: u32
    var cls: ir.Class
    var value: ir.Ref

## The moves of a function, grouped by the block they are placed in, and which block each
## phi's temporary belongs to.
struct Moves:
    var items: list.List[Move]
    ## The moves of block `b` are `items[start[b] ..< start[b + 1]]`.
    var start: u32[]
    var owner: u32[]

    static func over(f: ir.Function*, g: cfg.Graph*) -> Moves!:
        let nb = g.count()
        var m = Moves(items = try list.List[Move].create(32), start = try new u32[nb + 2] ---, owner = try new u32[f.temps.count + 1] ---)
        var k: usize = 0
        while k < m.start.length:
            m.start[k] = 0
            k += 1
        k = 0
        while k < m.owner.length:
            m.owner[k] = cfg.none_block
            k += 1
        var all = try list.List[Move].create(32)
        defer all.destroy()
        var b: usize = 0
        while b < g.blocks.count:
            let block = g.blocks.get(b)
            var i = block.start
            while i < block.end:
                let x = f.instrs.get((usize)i)
                if x.op != ir.Op.phi:
                    break
                m.owner[(usize)x.dst] = u32(b)
                var a: u32 = 0
                while a < x.extra2:
                    let arg = f.phi_args.get((usize)(x.extra + a))
                    let at = g.block_of(arg.pred)
                    try all.push(Move(at = at, dst = x.dst, cls = x.cls, value = arg.value))
                    m.start[(usize)at + 1] += 1
                    a += 1
                i += 1
            b += 1
        b = 0
        while b < nb:
            m.start[b + 1] += m.start[b]
            b += 1
        var fill = try new u32[nb + 1] ---
        defer free(fill)
        b = 0
        while b <= nb:
            fill[b] = 0
            b += 1
        k = 0
        while k < all.count:
            try m.items.push(all.get(0))
            k += 1
        k = 0
        while k < all.count:
            let mv = all.get(k)
            m.items.set((usize)(m.start[(usize)mv.at] + fill[(usize)mv.at]), mv)
            fill[(usize)mv.at] += 1
            k += 1
        return m

    func release():
        self.items.destroy()
        free(self.start)
        free(self.owner)

# mark: Replacing phis with copies ============================================================

## Replace every phi of `f` by copies. `g` is the graph of `f` as it stands.
pub func run(f: ir.Function*, g: cfg.Graph*) -> !:
    var moves = try Moves.over(f, g)
    defer moves.release()
    if moves.items.count == 0:
        return
    # which predecessors need a block of their own: a branch with copies for a successor
    # that has other predecessors
    let nb = g.count()
    var split_label = try new u32[nb + 1] ---
    defer free(split_label)
    var k: usize = 0
    while k <= nb:
        split_label[k] = 0
        k += 1
    var out = try list.List[ir.Instr].create(f.instrs.count + moves.items.count * 2 + 16)
    var b: usize = 0
    while b < g.blocks.count:
        let block = g.blocks.get(b)
        # the label
        if block.label != 0 and block.start > 0:
            try out.push(f.instrs.get((usize)block.start - 1))
        # the body, phis dropped, the copies before the terminator
        var e = block.end
        let last = f.instrs.get((usize)e - 1) if e > block.start else ir.Instr(op = ir.Op.copy, cls = ir.Class.l, dst = 0, a = ir.none_ref(), b = ir.none_ref(), extra = 0, extra2 = 0, line = 0, file = 0, scope = 0, site = 0)
        let ends = e > block.start and ir.is_terminator(last.op)
        var i2 = block.start
        while i2 < (e - 1 if ends else e):
            let x = f.instrs.get((usize)i2)
            if x.op != ir.Op.phi:
                try out.push(x)
            i2 += 1
        if ends and block.succs.count > 1:
            # copies for a successor with other predecessors go to an edge block
            for s in block.succs.span():
                try place_moves(f, &moves, u32(b), s, &out, split_label, g, false)
            try out.push(retarget(f, last, split_label, g))
            # the edge blocks, right after the branch
            for s in block.succs.span():
                try emit_edge(f, &moves, u32(b), s, &out, split_label, g)
        else:
            try place_moves(f, &moves, u32(b), block.succ1, &out, split_label, g, true)
            if ends:
                try out.push(last)
        b += 1
    f.instrs.destroy()
    f.instrs = out
    f.phi_args.count = 0

## The branch `last` with each target that has an edge block of its own sent there: a
## `jnz`'s two labels, or a `switch`'s default and every entry of its table.
func retarget(f: ir.Function*, last: ir.Instr, split_label: u32[], g: cfg.Graph*) -> ir.Instr:
    var branch = last
    branch.extra = edge_label(branch.extra, split_label, g)
    if branch.op == ir.Op.jnz:
        branch.extra2 = edge_label(branch.extra2, split_label, g)
    elif branch.op == ir.Op.switch_:
        let table = f.jump_tables.get((usize)branch.extra2)
        for k in 0..<(usize)table.count:
            let at = (usize)table.start + k
            f.jump_labels.items[at] = edge_label(f.jump_labels.items[at], split_label, g)
    return branch

## The label an edge to the block headed by `label` takes: its edge block's when it has one.
func edge_label(label: u32, split_label: u32[], g: cfg.Graph*) -> u32:
    let s = g.block_of(label)
    if s == cfg.none_block:
        return label
    let split = split_label[(usize)s]
    return split if split != 0 and split != label else label

## The copies of edge `at` -> `s`, into `out` when `inline`, else noted for an edge block
## in `split_label` (the block's own label when the edge needs none).
func place_moves(f: ir.Function*, moves: Moves*, at: u32, s: u32, out: list.List[ir.Instr]*, split_label: u32[], g: cfg.Graph*, inline: bool) -> !:
    if s == cfg.none_block:
        return
    var any = false
    var i = (usize)moves.start[(usize)at]
    while i < (usize)moves.start[(usize)at + 1]:
        if moves.owner[(usize)moves.items.get(i).dst] == s:
            any = true
        i += 1
    if not any:
        return
    if inline:
        try copy_edge(f, moves, at, s, out, g)
        return
    let block = g.blocks.get((usize)s)
    if block.preds.count == 1:
        # the only predecessor: the copies may sit before the branch
        try copy_edge(f, moves, at, s, out, g)
        return
    split_label[(usize)s] = f.label()

## An edge block: its label, the copies, and the jump on to the successor.
func emit_edge(f: ir.Function*, moves: Moves*, at: u32, s: u32, out: list.List[ir.Instr]*, split_label: u32[], g: cfg.Graph*) -> !:
    if s == cfg.none_block or split_label[(usize)s] == 0:
        return
    let label = split_label[(usize)s]
    split_label[(usize)s] = 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 = label, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
    try copy_edge(f, moves, at, s, out, g)
    try out.push(ir.Instr(op = ir.Op.jmp, cls = ir.Class.l, dst = 0, a = ir.none_ref(), b = ir.none_ref(), extra = g.blocks.get((usize)s).label, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))

## The parallel copies of one edge: through fresh temporaries when a source is another
## copy's destination.
func copy_edge(f: ir.Function*, moves: Moves*, at: u32, s: u32, out: list.List[ir.Instr]*, g: cfg.Graph*) -> !:
    let lo = (usize)moves.start[(usize)at]
    let hi = (usize)moves.start[(usize)at + 1]
    var clash = false
    var i = lo
    while i < hi:
        let m = moves.items.get(i)
        if moves.owner[(usize)m.dst] != s:
            i += 1
            continue
        var j = lo
        while j < hi:
            let o = moves.items.get(j)
            if j != i and o.value.kind == ir.RefKind.temp and o.value.index == m.dst and moves.owner[(usize)o.dst] == s:
                clash = true
            j += 1
        i += 1
    if not clash:
        i = lo
        while i < hi:
            let m = moves.items.get(i)
            if moves.owner[(usize)m.dst] == s:
                if not (m.value.kind == ir.RefKind.temp and m.value.index == m.dst):
                    try out.push(ir.Instr(op = ir.Op.copy, cls = m.cls, dst = m.dst, a = m.value, b = ir.none_ref(), extra = 0, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
            i += 1
        return
    # every source first, then every destination
    var staged = try list.List[u32].create(8)
    defer staged.destroy()
    i = lo
    while i < hi:
        let m = moves.items.get(i)
        if moves.owner[(usize)m.dst] == s:
            let t = try f.temp(m.cls)
            try out.push(ir.Instr(op = ir.Op.copy, cls = m.cls, dst = t, a = m.value, b = ir.none_ref(), extra = 0, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
            try staged.push(t)
        i += 1
    var k: usize = 0
    i = lo
    while i < hi:
        let m = moves.items.get(i)
        if moves.owner[(usize)m.dst] == s:
            try out.push(ir.Instr(op = ir.Op.copy, cls = m.cls, dst = m.dst, a = ir.temp_ref(staged.get(k)), b = ir.none_ref(), extra = 0, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
            k += 1
        i += 1