/** * Peephole simplification (docs/design/optimization-pipeline.md, * cleanup set): constant folding, algebraic identities, strength * reduction, and constant-condition branch folding, in one forward * pass over instruction ids. Branch folding can strand blocks, so the * block cleanup pass (blockmerge.zena) must run after this one. * Operand ids always precede their uses (the builder appends), so a * fold's result is visible to every later instruction in the same * pass and chains of constants collapse without iteration. * * Runs before GVN in the per-function pipeline. Rewrites are all * in place: an instruction folds by BECOMING a constant (uses keep * their operand id), and an identity replaces the instruction with * one of its operands through the same repl/canon scheme GVN uses, * nop-ing the survivorless instruction. * * Trap discipline: an op that can trap at runtime is never folded or * dropped unless the outcome is proven. Constant evaluation lives in * fold.zena, shared with SCCP, and carries the rules: integer * division and remainder never fold, float arithmetic folds only to * a non-NaN. Float identities (x+0.0, x*1.0) are skipped wholesale * here — -0.0 and NaN break them. * * Determinism: a single id-order walk, no hash containers. */ import { IrBody, IrOp, IrRefField, IrRefGlobal, IrRefType, IrSuccessor, IrScratch } from './ir.zena'; import { WasmStruct, isValSubtype } from '../wasm-module.zena'; import { ValTypeRef } from '../wasm.zena'; import { castIsIdentity, castOutcome, constOf, evalBinary, evalUnary, foldInstTo, isFoldableBinary, isFoldableUnary, } from './fold.zena'; /** Runs the pass; returns the number of instructions rewritten. */ export function runSimplify(body: IrBody, scratch: IrScratch): i32 { scratch.enter(); let result = runSimplifyOn(body, scratch); scratch.exit(); return result; } function runSimplifyOn(body: IrBody, scratch: IrScratch): i32 { let count = body.instCount(); var rewrites = 0; // Value-operand use counts, for rewrites that want to mutate an // operand in place (strength reduction turns `x * 8`'s constant 8 // into the shift count 3, which is only sound if nothing else reads // that constant). Later in-place rewrites only ever REMOVE uses, so // a count of one stays trustworthy for the rest of the pass. let useCount = scratch.i32(); for (var i = 0; i < count; i += 1) { useCount.push(0); } let operands = scratch.i32(); for (var i = 0; i < count; i += 1) { while (operands.length > 0) { operands.pop(); } body.appendValueOperands(i, operands); for (let opnd in operands) { if (opnd >= 0 && opnd < count) { useCount[opnd] += 1; } } } 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 replaceWithValue = (inst: i32, value: i32) => { repl[inst] = value; body.opcode[inst] = IrOp.nop as i32; body.typeId[inst] = -1; body.a[inst] = -1; body.b[inst] = -1; rewrites += 1; }; // In-place folds keep the instruction's id and result type, so // every use — including branch arguments — stays valid unchanged. let foldToI32 = (inst: i32, value: i32) => { body.opcode[inst] = IrOp.const_i32 as i32; body.a[inst] = value; body.b[inst] = -1; rewrites += 1; }; let foldToI64 = (inst: i32, value: i64) => { body.constI64.push(value); body.opcode[inst] = IrOp.const_i64 as i32; body.a[inst] = body.constI64.length - 1; body.b[inst] = -1; rewrites += 1; }; let foldToBool = (inst: i32, value: boolean) => { foldToI32(inst, if (value) 1 else 0); }; for (var inst = 0; inst < count; inst += 1) { body.rewriteValueOperands(inst, canon); let op = body.op(inst); let av = body.a[inst]; let bv = body.b[inst]; // --- branch folding --- // Rewrites leave the untaken successor with one edge fewer, // possibly none: the caller must run the block cleanup pass after // (the verifier rejects unreachable blocks). if (op == IrOp.br_if && body.op(av) == IrOp.const_i32) { let succs = body.successors(inst); let taken = if (body.a[av] != 0) succs[0] else succs[1]; rewriteToBr(body, inst, taken); rewrites += 1; continue; } if (op == IrOp.br_table && body.op(av) == IrOp.const_i32) { // wasm reads the selector as unsigned: negative picks the // default, which is the last successor. let succs = body.successors(inst); let v = body.a[av]; let n = succs.length; let taken = if (v >= 0 && v < n - 1) succs[v] else succs[n - 1]; rewriteToBr(body, inst, taken); rewrites += 1; continue; } // --- constant operands: evaluate (fold.zena holds the table) --- if (isFoldableBinary(op)) { let x = constOf(body, av); let y = constOf(body, bv); if (x != null) { if (y != null) { let r = evalBinary(op, x, y); if (r != null) { foldInstTo(body, inst, r); rewrites += 1; continue; } } } } if (isFoldableUnary(op)) { let x = constOf(body, av); if (x != null) { let r = evalUnary(op, x); if (r != null) { foldInstTo(body, inst, r); rewrites += 1; continue; } } } // --- i32 --- if (isI32Binary(op)) { let aConst = body.op(av) == IrOp.const_i32; let bConst = body.op(bv) == IrOp.const_i32; let ac = if (aConst) body.a[av] else 0; let bc = if (bConst) body.a[bv] else 0; if (op == IrOp.i32_add) { if (aConst && ac == 0) { replaceWithValue(inst, bv); continue; } if (bConst && bc == 0) { replaceWithValue(inst, av); continue; } } if (op == IrOp.i32_sub && bConst && bc == 0) { replaceWithValue(inst, av); continue; } if (op == IrOp.i32_mul) { if (aConst && ac == 1) { replaceWithValue(inst, bv); continue; } if (bConst && bc == 1) { replaceWithValue(inst, av); continue; } if ((aConst && ac == 0) || (bConst && bc == 0)) { foldToI32(inst, 0); continue; } // x * 2^k => x << k, when the constant is this instruction's // alone to rewrite. if (bConst && !aConst && isPowerOfTwoI32(bc) && useCount[bv] == 1) { body.a[bv] = log2I32(bc); body.opcode[inst] = IrOp.i32_shl as i32; rewrites += 1; continue; } if (aConst && !bConst && isPowerOfTwoI32(ac) && useCount[av] == 1) { body.a[av] = log2I32(ac); body.opcode[inst] = IrOp.i32_shl as i32; body.a[inst] = bv; body.b[inst] = av; rewrites += 1; continue; } } if (op == IrOp.i32_div_u && bConst && !aConst && isPowerOfTwoI32(bc) && useCount[bv] == 1) { body.a[bv] = log2I32(bc); body.opcode[inst] = IrOp.i32_shr_u as i32; rewrites += 1; continue; } if (op == IrOp.i32_rem_u && bConst && !aConst && isPowerOfTwoI32(bc) && useCount[bv] == 1) { body.a[bv] = bc - 1; body.opcode[inst] = IrOp.i32_and as i32; rewrites += 1; continue; } if (op == IrOp.i32_and) { if (aConst && ac == -1) { replaceWithValue(inst, bv); continue; } if (bConst && bc == -1) { replaceWithValue(inst, av); continue; } if ((aConst && ac == 0) || (bConst && bc == 0)) { foldToI32(inst, 0); continue; } if (av == bv) { replaceWithValue(inst, av); continue; } } if (op == IrOp.i32_or) { if (aConst && ac == 0) { replaceWithValue(inst, bv); continue; } if (bConst && bc == 0) { replaceWithValue(inst, av); continue; } if ((aConst && ac == -1) || (bConst && bc == -1)) { foldToI32(inst, -1); continue; } if (av == bv) { replaceWithValue(inst, av); continue; } } if (op == IrOp.i32_xor) { if (aConst && ac == 0) { replaceWithValue(inst, bv); continue; } if (bConst && bc == 0) { replaceWithValue(inst, av); continue; } if (av == bv) { foldToI32(inst, 0); continue; } } if ((op == IrOp.i32_shl || op == IrOp.i32_shr_s || op == IrOp.i32_shr_u) && bConst && (bc & 31) == 0) { replaceWithValue(inst, av); continue; } if (op == IrOp.i32_eq && av == bv) { foldToBool(inst, true); continue; } if (op == IrOp.i32_ne && av == bv) { foldToBool(inst, false); continue; } continue; } // --- i64 --- if (isI64Binary(op)) { let aConst = body.op(av) == IrOp.const_i64; let bConst = body.op(bv) == IrOp.const_i64; let ac = if (aConst) body.constI64[body.a[av]] else 0 as i64; let bc = if (bConst) body.constI64[body.a[bv]] else 0 as i64; let zero = 0 as i64; let one = 1 as i64; if (op == IrOp.i64_add) { if (aConst && ac == zero) { replaceWithValue(inst, bv); continue; } if (bConst && bc == zero) { replaceWithValue(inst, av); continue; } } if (op == IrOp.i64_sub && bConst && bc == zero) { replaceWithValue(inst, av); continue; } if (op == IrOp.i64_mul) { if (aConst && ac == one) { replaceWithValue(inst, bv); continue; } if (bConst && bc == one) { replaceWithValue(inst, av); continue; } if ((aConst && ac == zero) || (bConst && bc == zero)) { foldToI64(inst, zero); continue; } } if (op == IrOp.i64_and) { if (av == bv) { replaceWithValue(inst, av); continue; } if ((aConst && ac == zero) || (bConst && bc == zero)) { foldToI64(inst, zero); continue; } } if (op == IrOp.i64_or && av == bv) { replaceWithValue(inst, av); continue; } if (op == IrOp.i64_xor) { if (aConst && ac == zero) { replaceWithValue(inst, bv); continue; } if (bConst && bc == zero) { replaceWithValue(inst, av); continue; } if (av == bv) { foldToI64(inst, zero); continue; } } if (op == IrOp.i64_eq && av == bv) { foldToBool(inst, true); continue; } if (op == IrOp.i64_ne && av == bv) { foldToBool(inst, false); continue; } continue; } // --- unary --- if (op == IrOp.i32_eqz) { // eqz(eqz(x)) normalizes an already-boolean x back to itself. if (body.op(av) == IrOp.i32_eqz && producesBool(body.op(body.a[av]))) { replaceWithValue(inst, body.a[av]); continue; } // eqz(a < b) becomes a >= b, and likewise for every integer // comparison. A loop's exit test is the negation of its // condition, so this is what lets `while (i < n)` exit on one // comparison. The comparison's only use must be this eqz: it // is emptied, and its operands move here. let inverted = invertedIntComparison(body.op(av)); if (inverted >= 0 && useCount[av] == 1) { body.opcode[inst] = inverted; body.a[inst] = body.a[av]; body.b[inst] = body.b[av]; body.opcode[av] = IrOp.nop as i32; body.typeId[av] = -1; body.a[av] = -1; body.b[av] = -1; rewrites += 1; continue; } continue; } // --- allocation forwarding (scalar replacement, immutable tier) --- // A read of an immutable field straight off the allocation that // set it is the allocation's operand; a fat pointer's instance and // vtable are the pack's operand and the pack's vtable global. // Forwarding a read never changes behavior; when every read is // forwarded the allocation has no uses and DCE deletes it, which // is the whole of the immutable tier of scalar replacement // (docs/design/optimization-pipeline.md §Escape analysis and // SROA). Mutable fields stay: a write could sit between the // allocation and the read. if (op == IrOp.struct_get && av >= 0 && body.op(av) == IrOp.struct_new) { let s = allocatedStruct(body, av); let fieldRef = body.refTable[bv]; if (s != null && fieldRef is IrRefField) { let idx = s.fieldIndexByName(fieldRef.fieldName); let argsIdx = body.a[av]; let argc = body.extra[argsIdx]; if (idx >= 0 && idx < argc && !s.fields[idx].isMutable) { let arg = body.extra[argsIdx + 1 + idx]; let argType = body.resultType(arg); let readType = body.resultType(inst); if (arg >= 0 && argType != null && readType != null && isValSubtype(argType, readType)) { replaceWithValue(inst, arg); continue; } } } } // A tuple built from every field of another tuple of its struct, in // order, is that tuple (#529): tuples are immutable and their // identity unobservable (docs/design/equality.md), so the copy and // the original are interchangeable. Its counterpart above forwards // a read off an allocation; this forwards an allocation off reads. if (op == IrOp.struct_new) { let source = rebuiltTupleSource(body, inst); if (source >= 0) { replaceWithValue(inst, source); continue; } } if (op == IrOp.iface_instance && av >= 0 && body.op(av) == IrOp.iface_pack) { let instance = body.a[av]; let instType = body.resultType(instance); let readType = body.resultType(inst); if (instance >= 0 && instType != null && readType != null && isValSubtype(instType, readType)) { replaceWithValue(inst, instance); continue; } } if (op == IrOp.iface_vtable && av >= 0 && body.op(av) == IrOp.iface_pack) { // The pack's ref slot names the pair's vtable global; the read // becomes a global_get of it, in place. let r = body.refTable[body.b[av]]; if (r is IrRefGlobal) { body.opcode[inst] = IrOp.global_get as i32; body.b[inst] = body.b[av]; body.a[inst] = -1; rewrites += 1; continue; } } // --- reference folds --- // A cast the operand's static type already satisfies cannot trap // and yields the operand; folding it is what lets DCE remove the // slot-load chains devirtualization strands (a trapping cast is // never removed unused, so it has to fold first). if (op == IrOp.ref_cast) { let from = body.resultType(av); if (from != null && bv >= 0 && castIsIdentity(from, body.typeTable[bv])) { replaceWithValue(inst, av); continue; } continue; } if (op == IrOp.ref_is_null) { // A non-null-typed value is never null. This is what folds the // null guard an interface trampoline puts around a pack, and // with it the guard's branch and the dead arm. let from = body.resultType(av); if (from != null && from is ValTypeRef) { foldToBool(inst, false); continue; } continue; } if (op == IrOp.ref_test) { // A test the static type decides: a `match` over a value whose // exact class is known (an allocation an inlined callee // returned, say) keeps one arm and loses the test. let from = body.resultType(av); if (from != null && bv >= 0) { let outcome = castOutcome(from, body.typeTable[bv]); if (outcome >= 0) { foldToBool(inst, outcome == 1); continue; } } continue; } if (op == IrOp.ref_as_non_null) { // Same test as the cast: the operand's type must already be a // subtype of this instruction's (non-null) result type. A class // test on the ValType would not do — nullability is what is // being asked, and isValSubtype is where that rule lives. let from = body.resultType(av); let to = body.resultType(inst); if (from != null && to != null && castIsIdentity(from, to)) { replaceWithValue(inst, av); continue; } continue; } } // Ids precede uses only in a freshly lowered body: inlining splices // callee instructions in at the end of the id space, so a spliced // value's users can have SMALLER ids and were visited — operands // rewritten — before the value itself was replaced. One final sweep // makes canonicalization independent of visit order (a fold missed // for the same reason is caught by the next round, never wrong). if (rewrites > 0) { for (var inst = 0; inst < count; inst += 1) { if (body.op(inst) != IrOp.nop) { body.rewriteValueOperands(inst, canon); } } } return rewrites; } /** * Rewrites a two-or-more-way terminator into an unconditional br to * `s`. The [target, argc, args…] record is appended fresh to `extra` * (append-only, so reading the old record while pushing is safe). */ export function rewriteToBr(body: IrBody, inst: i32, s: IrSuccessor): void { let idx = body.extra.length; body.extra.push(s.target); body.extra.push(s.argCount); var i = 0; while (i < s.argCount) { body.extra.push(body.extra[s.argStart + i]); i += 1; } body.opcode[inst] = IrOp.br as i32; body.a[inst] = idx; body.b[inst] = -1; } /** The struct a struct_new allocates, or null if its ref is not one. */ export function allocatedStruct(body: IrBody, alloc: i32): WasmStruct | null { let typeRef = body.refTable[body.b[alloc]]; if (typeRef is IrRefType) { let t = typeRef.target; if (t is WasmStruct) { return t; } } return null; } /** * The tuple the allocation `alloc` copies: one non-null value of a * tuple struct whose every field, in order, `alloc` is built from. -1 * when the fields come from different values, from another struct, or * from only some of the fields. */ function rebuiltTupleSource(body: IrBody, alloc: i32): i32 { let s = allocatedStruct(body, alloc); if (s == null || !s.isTuple) { return -1; } let argsIdx = body.a[alloc]; let argc = body.extra[argsIdx]; if (argc == 0 || argc != s.fields.length) { return -1; } var source = -1; for (var i = 0; i < argc; i += 1) { let arg = body.extra[argsIdx + 1 + i]; if (arg < 0 || body.op(arg) != IrOp.struct_get) { return -1; } let fieldRef = body.refTable[body.b[arg]]; if (!(fieldRef is IrRefField)) { return -1; } if (fieldRef.owner !== s || s.fieldIndexByName(fieldRef.fieldName) != i) { return -1; } let from = body.a[arg]; if (from < 0 || (source >= 0 && from != source)) { return -1; } source = from; } // The copy is non-null, so the source must be typed so too. let t = body.resultType(source); if (t is ValTypeRef && t.target === s) { return source; } return -1; } function isPowerOfTwoI32(v: i32): boolean { return v > 0 && (v & (v - 1)) == 0; } function log2I32(v: i32): i32 { var k = 0; var c = v; while (c > 1) { c = c >>> 1; k += 1; } return k; } /** * The integer comparison that is true exactly when `op` is false, as * an IrOp ordinal, or -1 when `op` is not an integer comparison. Float * comparisons have no such partner: every one of them is false when * an operand is NaN, so `!(a < b)` is not `a >= b`. */ function invertedIntComparison(op: IrOp): i32 { let inverse = if (op == IrOp.i32_eq) IrOp.i32_ne else if (op == IrOp.i32_ne) IrOp.i32_eq else if (op == IrOp.i32_lt_s) IrOp.i32_ge_s else if (op == IrOp.i32_ge_s) IrOp.i32_lt_s else if (op == IrOp.i32_gt_s) IrOp.i32_le_s else if (op == IrOp.i32_le_s) IrOp.i32_gt_s else if (op == IrOp.i32_lt_u) IrOp.i32_ge_u else if (op == IrOp.i32_ge_u) IrOp.i32_lt_u else if (op == IrOp.i32_gt_u) IrOp.i32_le_u else if (op == IrOp.i32_le_u) IrOp.i32_gt_u else if (op == IrOp.i64_eq) IrOp.i64_ne else if (op == IrOp.i64_ne) IrOp.i64_eq else if (op == IrOp.i64_lt_s) IrOp.i64_ge_s else if (op == IrOp.i64_ge_s) IrOp.i64_lt_s else if (op == IrOp.i64_gt_s) IrOp.i64_le_s else if (op == IrOp.i64_le_s) IrOp.i64_gt_s else if (op == IrOp.i64_lt_u) IrOp.i64_ge_u else if (op == IrOp.i64_ge_u) IrOp.i64_lt_u else if (op == IrOp.i64_gt_u) IrOp.i64_le_u else if (op == IrOp.i64_le_u) IrOp.i64_gt_u else IrOp.nop; return if (inverse == IrOp.nop) -1 else inverse as i32; } /** * Ops whose result is always 0 or 1. Consulted before collapsing * eqz(eqz(x)) to x, which is only sound when x is already boolean. */ function producesBool(op: IrOp): boolean { return op == IrOp.i32_eqz || op == IrOp.i64_eqz || op == IrOp.ref_test || op == IrOp.ref_is_null || op == IrOp.ref_eq || (op as i32 >= IrOp.i32_eq as i32 && op as i32 <= IrOp.i32_ge_u as i32 && op != IrOp.i32_div_u && op != IrOp.i32_rem_u) || op == IrOp.i64_eq || op == IrOp.i64_ne || op == IrOp.i64_lt_s || op == IrOp.i64_le_s || op == IrOp.i64_gt_s || op == IrOp.i64_ge_s || op == IrOp.i64_lt_u || op == IrOp.i64_le_u || op == IrOp.i64_gt_u || op == IrOp.i64_ge_u || op == IrOp.f32_eq || op == IrOp.f32_ne || op == IrOp.f32_lt || op == IrOp.f32_le || op == IrOp.f32_gt || op == IrOp.f32_ge || op == IrOp.f64_eq || op == IrOp.f64_ne || op == IrOp.f64_lt || op == IrOp.f64_le || op == IrOp.f64_gt || op == IrOp.f64_ge; } /** * The i32 band minus the unary eqz and minus signed div/rem (which * can trap and get no rewrites here). Unsigned div/rem stay in: they * are strength-reduction targets, and the constant-fold chain simply * has no arm for them. */ function isI32Binary(op: IrOp): boolean { let v = op as i32; return v >= IrOp.i32_add as i32 && v <= IrOp.i32_ge_u as i32 && op != IrOp.i32_eqz && op != IrOp.i32_div_s && op != IrOp.i32_rem_s; } function isI64Binary(op: IrOp): boolean { let v = op as i32; return v >= IrOp.i64_add as i32 && v <= IrOp.i64_ge_u as i32 && op != IrOp.i64_div_s && op != IrOp.i64_rem_s && op != IrOp.i64_div_u && op != IrOp.i64_rem_u; }