dymokomi/luce-base
Source of release 0.42.0
0.42.0 / src / back / opt / gvn.lucb
#==============================================================================================
#
# gvn - Value numbering over the dominator tree
#
# DESCRIPTION:
# On the single-assignment form, a walk down the dominator tree keeps a table of the
# computations already available where the walk stands: an instruction whose
# operator, class, and operands are in the table is a copy of the earlier result,
# one on constants is its constant, one with an identity (`x + 0`, `x & x`, `x == x`
# on integers) is its operand, an extension of a value already in the extended range
# (`extub` of a `loadub`) is the value, a sum less one of its operands is the other,
# and a phi whose arguments all agree is that argument.
# Every such instruction is dropped and its uses read the value it stood for. A
# branch (or a jump table) on a constant becomes a jump, and the blocks that no branch reaches any more
# go, their phis losing the arguments those blocks supplied. This is QBE's gvn.c
# without global code motion, so a computation replaces another only where its
# block dominates the use: the table is scoped to the walk.
#
#==============================================================================================
import memory
import support.list
import back.ir.cfg
import back.ir.ir
import back.opt.opt
# mark: The value table =======================================================================
## An entry of the table: what an instruction computed, and where its result is.
struct Entry:
var op: ir.Op
var cls: ir.Class
var a: ir.Ref
var b: ir.Ref
var extra: u32
## The lane of a `vinsert` or `vextract`, which two otherwise equal ones differ by.
var lane: u32
var result: u32
## The table of available computations, scoped to the walk: open addressing over the
## entries' hashes, with every insertion logged so that leaving a dominator-tree node
## restores the buckets it filled, in reverse, which keeps every probe sequence intact.
struct Table:
var buckets: u32[]
var entries: list.List[Entry]
var log: list.List[u32]
## Per temporary, 1 + the index of the one instruction that assigns it, 0 when none or
## several do: what `redundant_extension` reads an operand's range from.
var defining: u32[]
static func create(f: ir.Function*) -> Table!:
let room = f.instrs.count
var size: usize = 64
while size < room * 2:
size *= 2
var t = Table(buckets = try new u32[size] ---, entries = try list.List[Entry].create(room + 1), log = try list.List[u32].create(room + 1), defining = try new u32[f.temps.count + 1] ---)
var k: usize = 0
while k < size:
t.buckets[k] = 0
k += 1
for d in 0..<t.defining.length:
t.defining[d] = 0
for i in 0..<f.instrs.count:
let x = f.instrs.get(i)
if x.dst != 0 and (usize)x.dst < t.defining.length:
# a second assignment leaves the temporary unknown for good
t.defining[(usize)x.dst] = u32(i + 1) if t.defining[(usize)x.dst] == 0 else 0xFFFFFFFF
for d in 0..<t.defining.length:
if t.defining[d] == 0xFFFFFFFF:
t.defining[d] = 0
return t
## The instruction that assigns temporary `r`, when it is one assigned once.
func definition(f: ir.Function*, r: ir.Ref) -> ir.Instr?:
if r.kind != ir.RefKind.temp or (usize)r.index >= self.defining.length or self.defining[(usize)r.index] == 0:
return none
return f.instrs.get((usize)self.defining[(usize)r.index] - 1)
func release():
free(self.defining)
free(self.buckets)
self.entries.destroy()
self.log.destroy()
func mark() -> usize:
return self.log.count
## Empty the buckets filled since `mark`, latest first.
func cut(mark: usize):
while self.log.count > mark:
let bucket = self.log.get(self.log.count - 1)
self.log.count -= 1
self.buckets[(usize)bucket] = 0
self.entries.count -= 1
## The result of the entry equal to `x`, or 0.
func find(x: ir.Instr) -> u32:
var at = hash_of(x) & (self.buckets.length - 1)
while self.buckets[at] != 0:
let entry = self.entries.get((usize)self.buckets[at] - 1)
if entry.op == x.op and entry.cls == x.cls and entry.extra == x.extra and entry.lane == lane_of(x) and same_ref(entry.a, x.a) and same_ref(entry.b, x.b):
return entry.result
at = (at + 1) & (self.buckets.length - 1)
return 0
func insert(x: ir.Instr) -> !:
var at = hash_of(x) & (self.buckets.length - 1)
while self.buckets[at] != 0:
at = (at + 1) & (self.buckets.length - 1)
try self.entries.push(Entry(op = x.op, cls = x.cls, a = x.a, b = x.b, extra = x.extra, lane = lane_of(x), result = x.dst))
self.buckets[at] = u32(self.entries.count)
try self.log.push(u32(at))
## The lane a `vinsert` or `vextract` names in `extra2`; 0 for every other instruction,
## whose `extra2` is no part of what it computes (a position, an argument's index).
func lane_of(x: ir.Instr) -> u32:
return x.extra2 if x.op == ir.Op.vinsert or x.op == ir.Op.vextract else 0
func hash_of(x: ir.Instr) -> usize:
var h: u64 = 0xcbf29ce484222325
h = (h ^ (u64)x.op) *% 0x100000001b3
h = (h ^ (u64)x.cls) *% 0x100000001b3
h = (h ^ (u64)x.extra) *% 0x100000001b3
h = (h ^ (u64)lane_of(x)) *% 0x100000001b3
h = (h ^ ref_hash(x.a)) *% 0x100000001b3
h = (h ^ ref_hash(x.b)) *% 0x100000001b3
return (usize)h
func ref_hash(r: ir.Ref) -> u64:
var h = (u64)r.kind *% 0x9E3779B97F4A7C15
h ^= (u64)r.index *% 0xC2B2AE3D27D4EB4F
h ^= (u64)r.value *% 0x165667B19E3779F9
if r.kind == ir.RefKind.global or r.kind == ir.RefKind.function:
for byte in r.name.bytes:
h = (h ^ (u64)byte) *% 0x100000001b3
return h
# mark: The pass ==============================================================================
## The pass over `f`, whose graph is `g`. Answers the graph of the function as it stands
## afterwards, which is a new one when blocks were removed.
pub func run(f: ir.Function*, g: cfg.Graph*) -> cfg.Graph!:
let n = f.temps.count + 1
var rep = try new ir.Ref[n] ---
defer free(rep)
var t: usize = 0
while t < n:
rep[t] = ir.none_ref()
t += 1
var dead = try new bool[f.instrs.count + 1] ---
defer free(dead)
var i: usize = 0
while i <= f.instrs.count:
dead[i] = false
i += 1
var table = try Table.create(f)
defer table.release()
try number(f, g, 0, rep, dead, &table)
# every use reads what its value became
i = 0
while i < f.instrs.count:
var x = f.instrs.get(i)
x.a = resolve(rep, x.a)
x.b = resolve(rep, x.b)
f.instrs.set(i, x)
i += 1
i = 0
while i < f.args.count:
var a = f.args.get(i)
a.value = resolve(rep, a.value)
f.args.set(i, a)
i += 1
i = 0
while i < f.phi_args.count:
var a = f.phi_args.get(i)
a.value = resolve(rep, a.value)
f.phi_args.set(i, a)
i += 1
# constant branches become jumps
var branched = false
i = 0
while i < f.instrs.count:
var x = f.instrs.get(i)
if x.op == ir.Op.jnz and (x.a.kind == ir.RefKind.constant or x.extra == x.extra2):
let taken = x.extra2 if x.a.kind == ir.RefKind.constant and x.a.value == 0 else x.extra
x = ir.Instr(op = ir.Op.jmp, cls = ir.Class.l, dst = 0, a = ir.none_ref(), b = ir.none_ref(), extra = taken, extra2 = 0, line = 0, file = 0, scope = 0, site = 0)
f.instrs.set(i, x)
branched = true
elif x.op == ir.Op.switch_ and x.a.kind == ir.RefKind.constant:
let taken = switch_target(f, x)
x = ir.Instr(op = ir.Op.jmp, cls = ir.Class.l, dst = 0, a = ir.none_ref(), b = ir.none_ref(), extra = taken, extra2 = 0, line = 0, file = 0, scope = 0, site = 0)
f.instrs.set(i, x)
branched = true
i += 1
# the survivors, in order
var out = try list.List[ir.Instr].create(f.instrs.count)
i = 0
while i < f.instrs.count:
if not dead[i]:
try out.push(f.instrs.get(i))
i += 1
f.instrs.destroy()
f.instrs = out
if branched:
var reached = try cfg.Graph.over(f)
try drop_unreachable(f, &reached)
reached.release()
try drop_dead_phis(f)
# the graph of the function as it stands now, ranges and all
return try cfg.Graph.over(f)
## Where a `switch` on a constant goes: the entry the value names, else the default. The
## index is taken at the instruction's class, as the generators compute it.
func switch_target(f: ir.Function*, x: ir.Instr) -> u32:
let table = f.jump_tables.get((usize)x.extra2)
var index = (u64)(x.a.value -% table.low)
if x.cls == ir.Class.w:
index = index & 0xFFFFFFFF
if index >= (u64)table.count:
return x.extra
return f.jump_labels.get((usize)table.start + (usize)index)
## The value a reference stands for, through the replacements.
func resolve(rep: ir.Ref[], r: ir.Ref) -> ir.Ref:
var out = r
var hops: u32 = 0
while out.kind == ir.RefKind.temp and rep[(usize)out.index].kind != ir.RefKind.none_ and hops < 64:
out = rep[(usize)out.index]
hops += 1
return out
## One block on the walk's stack: which block, the next of its dominator-tree
## children to visit, and the table's size before the block was numbered.
struct Visit:
var block: u32
var child: usize
var mark: usize
## The walk: block `b`, then its dominator-tree children with the table as it stands
## there, then the table cut back. An explicit stack, not recursion: a long function
## is a long chain of blocks, and a frame per block overflowed the compiler's stack.
func number(f: ir.Function*, g: cfg.Graph*, b: u32, rep: ir.Ref[], dead: bool[], table: Table*) -> !:
var stack = try list.List[Visit].create(64)
defer stack.destroy()
let root_mark = table.mark()
try number_block(f, g, b, rep, dead, table)
try stack.push(Visit(block = b, child = 0, mark = root_mark))
while stack.count > 0:
var top = stack.get(stack.count - 1)
let block = g.blocks.get((usize)top.block)
if top.child < block.children.count:
let child = block.children.get(top.child)
top.child += 1
stack.set(stack.count - 1, top)
let mark = table.mark()
try number_block(f, g, child, rep, dead, table)
try stack.push(Visit(block = child, child = 0, mark = mark))
else:
table.cut(top.mark)
stack.count -= 1
## Number one block's instructions against the table, extending it.
func number_block(f: ir.Function*, g: cfg.Graph*, b: u32, rep: ir.Ref[], dead: bool[], table: Table*) -> !:
let block = g.blocks.get((usize)b)
var i = block.start
while i < block.end:
var x = f.instrs.get((usize)i)
if x.op == ir.Op.phi:
if let same = agreeing_phi(f, x, rep):
rep[(usize)x.dst] = same
dead[(usize)i] = true
elif let earlier = same_phi(f, block, i, rep, dead):
rep[(usize)x.dst] = ir.temp_ref(earlier)
dead[(usize)i] = true
i += 1
continue
x.a = resolve(rep, x.a)
x.b = resolve(rep, x.b)
let (args_start, args_count) = ir.argument_range(f, x)
var k: u32 = 0
while k < args_count:
var a = f.args.get((usize)(args_start + k))
a.value = resolve(rep, a.value)
f.args.set((usize)(args_start + k), a)
k += 1
if x.dst != 0 and numberable(x.op):
if commutes(x.op) and ordered_after(x.a, x.b):
let swap = x.a
x.a = x.b
x.b = swap
if let value = folded(x):
rep[(usize)x.dst] = value
dead[(usize)i] = true
f.instrs.set((usize)i, x)
i += 1
continue
if let same = identity(x):
rep[(usize)x.dst] = same
dead[(usize)i] = true
f.instrs.set((usize)i, x)
i += 1
continue
if let same = redundant_extension(f, table, x):
rep[(usize)x.dst] = same
dead[(usize)i] = true
f.instrs.set((usize)i, x)
i += 1
continue
if let same = undone_sum(f, table, x):
rep[(usize)x.dst] = same
dead[(usize)i] = true
f.instrs.set((usize)i, x)
i += 1
continue
let found = table.find(x)
if found != 0:
rep[(usize)x.dst] = ir.temp_ref(found)
dead[(usize)i] = true
else:
try table.insert(x)
f.instrs.set((usize)i, x)
i += 1
## Whether an instruction's result depends on its operands alone: the arithmetic and the
## conversions, the comparisons, addresses, and the vector forms; not loads, stores, calls,
## traps, or anything with an effect. A checked or dividing operator is here too: computed
## twice on the same operands it traps twice or never, so once is enough.
func numberable(op: ir.Op) -> bool:
let code = (u8)op
if op == ir.Op.copy or op == ir.Op.addr or op == ir.Op.addr_tls:
return true
if code >= (u8)ir.Op.add and code <= (u8)ir.Op.neg:
return true
if code >= (u8)ir.Op.ceq and code <= (u8)ir.Op.cuge:
return true
if code >= (u8)ir.Op.extsb and code <= (u8)ir.Op.truncs:
return true
if op == ir.Op.addo or op == ir.Op.subo or op == ir.Op.mulo:
return true
if ir.is_vector_op(op):
return op != ir.Op.loadv and op != ir.Op.storev
return false
func commutes(op: ir.Op) -> bool:
return op == ir.Op.add or op == ir.Op.mul or op == ir.Op.and_ or op == ir.Op.or_ or op == ir.Op.xor or op == ir.Op.ceq or op == ir.Op.cne or op == ir.Op.addo or op == ir.Op.mulo
## A canonical order of two operands: temporaries before constants, then by number.
func ordered_after(a: ir.Ref, b: ir.Ref) -> bool:
if a.kind == ir.RefKind.constant and b.kind == ir.RefKind.temp:
return true
if a.kind == ir.RefKind.temp and b.kind == ir.RefKind.temp:
return a.index > b.index
if a.kind == ir.RefKind.constant and b.kind == ir.RefKind.constant:
return a.value > b.value
return false
func same_ref(a: ir.Ref, b: ir.Ref) -> bool:
if a.kind != b.kind:
return false
match a.kind:
.none_: return true
.temp, .slot, .text: return a.index == b.index
.constant: return a.value == b.value
_: return a.name == b.name and a.value == b.value
## The constant an instruction on constants computes, when it computes one.
func folded(x: ir.Instr) -> ir.Ref?:
if x.op == ir.Op.copy and x.a.kind == ir.RefKind.constant:
return x.a
if x.a.kind != ir.RefKind.constant:
return none
if x.b.kind == ir.RefKind.constant:
if let v = opt.constant_of(x.op, x.cls, x.a.value, x.b.value, x.extra == 1):
return ir.const_ref(v)
return none
if x.b.kind == ir.RefKind.none_:
# a unary: the extensions and negation of a constant word
if let v = opt.unary_constant(x.op, x.cls, x.a.value):
return ir.const_ref(v)
return none
## The operand an instruction is a copy of by its operator's identity, on integers.
func identity(x: ir.Instr) -> ir.Ref?:
if x.op == ir.Op.copy:
return x.a
if x.cls != ir.Class.w and x.cls != ir.Class.l:
return none
let zero = x.b.kind == ir.RefKind.constant and x.b.value == 0
let one = x.b.kind == ir.RefKind.constant and x.b.value == 1
let same = x.a.kind == ir.RefKind.temp and x.b.kind == ir.RefKind.temp and x.a.index == x.b.index
match x.op:
.add, .sub, .or_, .xor, .shl, .lshr, .ashr, .addo, .subo:
if zero:
return x.a
.mul, .mulo, .sdiv, .udiv:
if one:
return x.a
_:
_ = 0
if same:
match x.op:
.and_, .or_: return x.a
.xor, .sub, .subo, .cne, .cslt, .csgt, .cult, .cugt: return ir.const_ref(0)
.ceq, .csle, .csge, .cule, .cuge: return ir.const_ref(1)
_: _ = 0
return none
## An extension of a value that is already what the extension would make of it: a byte
## loaded by `loadub`, extended by `extub` before, a comparison's, or a phi of byte constants,
## needs no `extub` again. An extension
## reads only its operand's low bits, which a widening (`extuw`, `extsw`) keeps, so it
## looks through one to the word; the value stands for the extension when its class is
## the extension's.
func redundant_extension(f: ir.Function*, table: Table*, x: ir.Instr) -> ir.Ref?:
let wanted = extension_kind(x.op)
if wanted == 0:
return none
var source = x.a
var d = table.definition(f, source) else return none
if d.op == ir.Op.extuw or d.op == ir.Op.extsw:
source = d.a
d = table.definition(f, source) else return none
if source.kind != ir.RefKind.temp or f.temp_class(source.index) != x.cls:
return none
# a comparison's 0 or 1 is a byte: the bool an expanded predicate (`math.is_nan`) hands
# its caller's branch; so is a phi of byte constants, an expanded optional's flag
let known = 1 if ir.is_comparison(d.op) or bytes_joined(f, d) else extension_kind(d.op)
if known == 0:
return none
# kinds: 1 u8, 2 u16, 3 s8, 4 s16; what each wanted range contains
let holds = known == wanted or (wanted == 2 and known == 1) or (wanted == 4 and (known == 1 or known == 3))
return source if holds else none
## The other operand of a sum less one of its operands: `(a + b) - a` is `b`, as the length
## of `values[start..<start + count]` is `count`. A wrapping difference undoes a wrapping or
## a checked sum, and a checked difference a checked sum of the same signedness, which it
## cannot overflow once the sum has not; a checked difference of a wrapping sum stays.
func undone_sum(f: ir.Function*, table: Table*, x: ir.Instr) -> ir.Ref?:
if (x.op != ir.Op.sub and x.op != ir.Op.subo) or (x.cls != ir.Class.w and x.cls != ir.Class.l):
return none
let sum = table.definition(f, x.a) else return none
if sum.cls != x.cls or not (sum.op == ir.Op.addo or (sum.op == ir.Op.add and x.op == ir.Op.sub)):
return none
if x.op == ir.Op.subo and sum.extra != x.extra:
return none
if same_ref(sum.a, x.b):
return sum.b
if same_ref(sum.b, x.b):
return sum.a
return none
## Whether `x` is a phi whose every argument is a constant byte.
func bytes_joined(f: ir.Function*, x: ir.Instr) -> bool:
if x.op != ir.Op.phi or x.extra2 == 0:
return false
for k in 0..<x.extra2:
let value = f.phi_args.get((usize)(x.extra + k)).value
if value.kind != ir.RefKind.constant or value.value < 0 or value.value > 255:
return false
return true
## The range an operation leaves its result in, as a kind: 1 an unsigned byte, 2 an
## unsigned half, 3 a signed byte, 4 a signed half; 0 for any other.
func extension_kind(op: ir.Op) -> u8:
match op:
.extub, .loadub: return 1
.extuh, .loaduh: return 2
.extsb, .loadsb: return 3
.extsh, .loadsh: return 4
_: return 0
## The one value a phi's arguments agree on (the phi itself aside), or none.
func agreeing_phi(f: ir.Function*, x: ir.Instr, rep: ir.Ref[]) -> ir.Ref?:
var value = ir.none_ref()
var k: u32 = 0
while k < x.extra2:
let a = resolve(rep, f.phi_args.get((usize)(x.extra + k)).value)
if a.kind == ir.RefKind.temp and a.index == x.dst:
k += 1
continue
if value.kind == ir.RefKind.none_:
value = a
elif not same_ref(value, a):
return none
k += 1
if value.kind == ir.RefKind.none_:
return none
return value
## An earlier phi of the same block with the same arguments, by predecessor.
func same_phi(f: ir.Function*, block: cfg.Block, at: u32, rep: ir.Ref[], dead: bool[]) -> u32?:
let x = f.instrs.get((usize)at)
var i = block.start
while i < at:
let y = f.instrs.get((usize)i)
if y.op != ir.Op.phi:
break
if not dead[(usize)i] and y.cls == x.cls and y.extra2 == x.extra2:
var agree = true
var k: u32 = 0
while k < x.extra2:
let ax = f.phi_args.get((usize)(x.extra + k))
var matched = false
var q: u32 = 0
while q < y.extra2:
let ay = f.phi_args.get((usize)(y.extra + q))
if ay.pred == ax.pred and same_ref(resolve(rep, ay.value), resolve(rep, ax.value)):
matched = true
q += 1
if not matched:
agree = false
k += 1
if agree:
return y.dst
i += 1
return none
## Remove the blocks the entry no longer reaches, and the phi arguments they supplied.
func drop_unreachable(f: ir.Function*, g: cfg.Graph*) -> !:
var keep_label = try new bool[(usize)f.labels + 1] ---
defer free(keep_label)
var k: usize = 0
while k < keep_label.length:
keep_label[k] = false
k += 1
keep_label[0] = true
var b: usize = 0
while b < g.blocks.count:
let block = g.blocks.get(b)
if block.rpo != cfg.none_block:
keep_label[(usize)block.label] = true
b += 1
var out = try list.List[ir.Instr].create(f.instrs.count)
b = 0
while b < g.blocks.count:
let block = g.blocks.get(b)
if block.rpo == cfg.none_block:
b += 1
continue
if block.label != 0 and block.start > 0:
try out.push(f.instrs.get((usize)block.start - 1))
var i = block.start
while i < block.end:
var x = f.instrs.get((usize)i)
if x.op == ir.Op.phi:
# drop the arguments of predecessors that are gone
var kept: u32 = 0
var q: u32 = 0
while q < x.extra2:
let arg = f.phi_args.get((usize)(x.extra + q))
if keep_label[(usize)arg.pred]:
f.phi_args.set((usize)(x.extra + kept), arg)
kept += 1
q += 1
x.extra2 = kept
try out.push(x)
i += 1
b += 1
f.instrs.destroy()
f.instrs = out
## Remove the phis nothing reads, until none is left: a phi feeding only dead phis is dead.
func drop_dead_phis(f: ir.Function*) -> !:
var changed = true
while changed:
changed = false
var used = try new bool[f.temps.count + 1] ---
defer free(used)
var k: usize = 0
while k < used.length:
used[k] = false
k += 1
var i: usize = 0
while i < f.instrs.count:
let x = f.instrs.get(i)
if x.op != ir.Op.dbg:
mark_use(used, x.a)
mark_use(used, x.b)
if x.op == ir.Op.phi:
var q: u32 = 0
while q < x.extra2:
let arg = f.phi_args.get((usize)(x.extra + q))
if not (arg.value.kind == ir.RefKind.temp and arg.value.index == x.dst):
mark_use(used, arg.value)
q += 1
i += 1
i = 0
while i < f.args.count:
mark_use(used, f.args.get(i).value)
i += 1
var out = try list.List[ir.Instr].create(f.instrs.count)
i = 0
while i < f.instrs.count:
let x = f.instrs.get(i)
if x.op == ir.Op.phi and not used[(usize)x.dst]:
changed = true
else:
try out.push(x)
i += 1
f.instrs.destroy()
f.instrs = out
func mark_use(used: bool[], r: ir.Ref):
if r.kind == ir.RefKind.temp and (usize)r.index < used.length:
used[(usize)r.index] = true
test "two lanes extracted from one vector are two values":
var backing: u8[262144]
var arena = memory.FixedBuffer.over(backing)
with arena:
# t1 = loadv; t2 = lane 0 of t1; t3 = lane 1 of t1; ret t2 + t3: luce-3d's
# splat packing lost its second lane when value numbering took them as one
var f = try ir.Function.create("lanes")
let shape = ir.lanes(64, 2, true, false)
let s = try f.slot(16, 16)
let v = try f.temp(ir.Class.v)
try f.emit(ir.Op.loadv, ir.Class.v, v, ir.slot_ref(s), ir.none_ref(), shape)
let low = try f.temp(ir.Class.d)
try f.emit(ir.Op.vextract, ir.Class.d, low, ir.temp_ref(v), ir.none_ref(), shape)
let high = try f.temp(ir.Class.d)
try f.emit(ir.Op.vextract, ir.Class.d, high, ir.temp_ref(v), ir.none_ref(), shape)
f.instrs.items[f.instrs.count - 1].extra2 = 1
let sum = try f.binary(ir.Op.add, ir.Class.d, ir.temp_ref(low), ir.temp_ref(high))
try f.emit(ir.Op.ret, ir.Class.d, 0, sum, ir.none_ref(), 0)
var g = try cfg.Graph.over(&f)
var numbered = try run(&f, &g)
_ = numbered
var extracts: u32 = 0
for x in f.instrs.span():
if x.op == ir.Op.vextract:
extracts += 1
if x.op == ir.Op.add:
assert(x.a.index != x.b.index)
assert(extracts == 2)