dymokomi/luce-base
Source of release 0.42.0
0.42.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