/** * Global value numbering over the dominator tree (docs/design/ir.md's * optimization loop, first pass): a pure instruction whose key — * opcode, canonical value operands, interned payload, result type — * already has a definition in a DOMINATING block reuses that * definition instead of recomputing. The dominant client is the * narrowing contract (ir.md §5): every read of a flow-narrowed * binding emits its own ref_cast, and dominated repeats collapse to * the first. Repeated ref_tests, fat-pointer unwraps, immutable * global reads (vtables), and numeric recomputation fold the same * way. * * Determinism: instructions process in id order along a * deterministic dominator-tree walk, and keys are plain strings — * stage-2 byte-parity is preserved. * * Replaced instructions become nops (their result type cleared); * emission already skips nops, and every consumer was rewritten to * the canonical id via IrBody.rewriteValueOperands. */ import { IrBody, IrOp, IrRefField, IrRefGlobal, isBinaryNumericOp, isUnaryNumericOp, IrScratch } from './ir.zena'; import { IrCfg } from './cfg.zena'; import { ValType, ValTypeRef, ValTypeRefNull, valTypeToOpcode, } from '../wasm.zena'; export function runGvn(body: IrBody, scratch: IrScratch): void { scratch.enter(); runGvnOn(body, new IrCfg(body, scratch), scratch); scratch.exit(); } function runGvnOn(body: IrBody, cfg: IrCfg, scratch: IrScratch): void { let count = body.instCount(); let repl = scratch.i32(); for (var i = 0; i < count; i += 1) { repl.push(i); } let canon = (v: i32) => { if (v < 0 || v >= count) { return v; } var c = v; while (repl[c] != c) { c = repl[c]; } return c; }; let table = new Map(); let scopeKeys = new Array(); // Iterative dominator-tree DFS: negative entries mark subtree exits // (pop this block's insertions from the scope table). let work = scratch.i32(); let marks = scratch.i32(); work.push(0); while (work.length > 0) { let item = work.pop(); if (item < 0) { let mark = marks.pop(); while (scopeKeys.length > mark) { table.delete(scopeKeys.pop()); } continue; } marks.push(scopeKeys.length); work.push(-1); let insts = body.blocks[item].insts; for (let inst in insts) { body.rewriteValueOperands(inst, canon); let key = gvnKey(body, inst); if (key == null) { continue; } if (let (true, prior) = table.get(key)) { repl[inst] = prior; body.opcode[inst] = IrOp.nop as i32; body.typeId[inst] = -1; body.a[inst] = -1; body.b[inst] = -1; } else { table[key] = inst; scopeKeys.push(key); } } // Children push in REVERSE so the walk visits them in ascending // order (pure determinism hygiene; any fixed order is correct). var ci = cfg.domChildCount(item) - 1; while (ci >= 0) { work.push(cfg.domChild(item, ci)); ci -= 1; } } } /** * The value-numbering key for pure instructions; null for anything * with effects, allocation identity, or unknown shape. Operands are * already canonical (rewritten before keying). */ /** * A type's identity for a key: the heap type's uid plus nullability * for references, the opcode for scalars. Type table indices will not * do — inlining appends the callee's whole table to the caller's, so * two casts to the same type from two inlined bodies name it at two * indices, and the point of numbering them is that they are one. */ function typeCode(vt: ValType) { if (vt is ValTypeRef) { return vt.target.uid * 4 + 1; } if (vt is ValTypeRefNull) { return vt.target.uid * 4 + 2; } return valTypeToOpcode(vt) * 4 + 3; } /** * A value-numbering key. A case class rather than a string: the * string form cost about eleven allocations per instruction, one per * number and per concatenation, a fifth of all the strings a large * compile built. `kind` tells the shapes apart; `name` is a field * name for struct loads and empty otherwise. */ final class GvnKey(kind: i32, a: i32, b: i32, c: i32, ty: i32, name: String) function gvnKey(body: IrBody, inst: i32): GvnKey | null { let op = body.op(inst); let av = body.a[inst]; let bv = body.b[inst]; let ty = if (body.typeId[inst] >= 0) typeCode(body.typeTable[body.typeId[inst]]) else 0; if (op == IrOp.const_i32) { // a IS the value. return new GvnKey(0, av, 0, 0, ty, ''); } if (op == IrOp.const_i64 || op == IrOp.const_f32 || op == IrOp.const_f64) { // a is a pool index; identical indices are identical values // (missing equal-value pool duplicates is fine). return new GvnKey(1, av, 0, op as i32, ty, ''); } if (isBinaryNumericOp(op) || op == IrOp.ref_eq) { return new GvnKey(2, av, bv, op as i32, ty, ''); } if (op == IrOp.ref_test || op == IrOp.ref_cast) { // a = value operand; b = the target type's table index, keyed by // the type it names. return new GvnKey(3, av, typeCode(body.typeTable[bv]), op as i32, ty, ''); } if (isUnaryNumericOp(op) || op == IrOp.ref_as_non_null || op == IrOp.iface_instance || op == IrOp.iface_vtable) { // a = value operand; b = -1 or an immediate. return new GvnKey(3, av, bv, op as i32, ty, ''); } // The wide-arithmetic ops are pure, but numbering one means // redirecting its mv_get projections too, and nothing generates the // same wide multiply twice. They fall through to null. if (op == IrOp.global_get) { // Only immutable globals (vtables, singletons) are pure reads. let r = body.refTable[bv]; if (r is IrRefGlobal && !r.target.isMutable) { return new GvnKey(4, r.target.index, 0, 0, ty, ''); } return null; } if (op == IrOp.struct_get) { // A load of a wasm-immutable field (a `let` field, under // single-shot construction) is a pure function of the receiver. // The key uses the owner struct's uid + field name, not the // refTable index — addRef appends per use, so indices differ // between two loads of the same field. Trap equivalence holds // without a non-null receiver check: a dominated repeat on the // same receiver value traps exactly when the dominating load did. let r = body.refTable[bv]; if (r is IrRefField) { let idx = r.owner.fieldIndexByName(r.fieldName); if (idx >= 0 && !r.owner.fields[idx].isMutable) { return new GvnKey(5, av, r.owner.uid, 0, ty, r.fieldName); } } return null; } if (op == IrOp.array_len) { // An array's length is fixed at allocation; same trap-equivalence // argument as immutable fields. return new GvnKey(6, av, 0, 0, ty, ''); } return null; }