/** * Parameter specialization (docs/design/optimization-pipeline.md * §Signature specialization): a function whose interface-typed * parameter is, at every direct call site, a fat pointer packed * around the same class gets a clone that takes the instance itself. * * A function summing an `Array` called with a `FixedArray` is the * shape. Inside the callee the accesses already devirtualize and * inline (one implementation is live), but the parameter is a fat * pointer: each call packs it, and the body unpacks and casts it. In * the clone the parameter is the array, re-packed once at entry with * an `iface_pack` naming the same vtable global. The forwarding rules * in simplify then dissolve every unpack, vtable read and cast in the * body against that pack (the instance's static type is the class), * and the pack itself dies unused. At each call site the pack's * instance is passed instead, the call names the clone, and the * caller's pack dies too. The original stays for any reference to it * as a value (a vtable install, an export, a `ref_func`); with none, * harvest deletes it, so the module does not grow. * * Only the single-class regime for now: every direct call site must * pass a pack of one vtable global, or the parameter stays. A clone * per argument class, budgeted, is the next tier. * * The clone's signature is new to a laid-out module; * `WasmModule.getSignatureLate` appends it to the type section. * * Determinism: callees in function order, sites in body and * instruction order, clones appended in that order. */ import { String, i32ToString } from 'zena:core'; import { IrBlock, IrBody, IrOp, IrRefFunc, IrRefGlobal, } from './ir.zena'; import { WasmModule, WasmFunction, WasmGlobal, WasmStruct, } from '../wasm-module.zena'; import { ValType, ValTypeRef, refTargetOf } from '../wasm.zena'; /** One direct call passing a pack for parameter `k`. */ final class Site { caller: i32; inst: i32; k: i32; pack: i32; new(this.caller, this.inst, this.k, this.pack); } /** * Runs one sweep; returns the number of clones made. `changed` is set * for every caller rewritten and every clone, and grows with `bodies`. */ export function runSpecialize(wasm: WasmModule, bodies: GrowableArray, changed: GrowableArray): i32 { let bodyIndex = new Map(); let originalCount = wasm.functions.length; for (var i = 0; i < originalCount; i += 1) { bodyIndex[wasm.functions[i]] = i; } // Every direct call to a local function, by callee: the sites that // pass a pack for some parameter, and the count of all sites (a // site passing anything else for that parameter blocks it). let sitesOf = new Array>(); let callCount = new Array(); for (var j = 0; j < originalCount; j += 1) { sitesOf.push(new Array()); callCount.push(0); } for (var i = 0; i < originalCount; i += 1) { let body = bodies[i]; let n = body.instCount(); for (var inst = 0; inst < n; inst += 1) { if (body.op(inst) != IrOp.call) { continue; } let r = body.refTable[body.b[inst]]; if (!(r is IrRefFunc)) { continue; } var j = -1; if (let (true, idx) = bodyIndex.get(r.target)) { j = idx; } if (j < 0) { continue; } callCount[j] += 1; let argsIdx = body.a[inst]; let argc = body.extra[argsIdx]; for (var k = 0; k < argc; k += 1) { let arg = body.extra[argsIdx + 1 + k]; if (arg >= 0 && body.op(arg) == IrOp.iface_pack && packGlobal(body, arg) != null) { let instance = body.a[arg]; let t = body.resultType(instance); if (t != null && t is ValTypeRef) { sitesOf[j].push(new Site(i, inst, k, arg)); } } } } } var clones = 0; for (var j = 0; j < originalCount; j += 1) { let sites = sitesOf[j]; if (sites.length == 0) { continue; } let callee = bodies[j]; let params = callee.blocks[0].params; // Per parameter: the one vtable global every site agrees on, or // null. A parameter with fewer pack sites than calls has a call // passing something else. let agreed = new Array(); let instanceType = new Array(); var any = false; for (var k = 0; k < params.length; k += 1) { var g: WasmGlobal | null = null; var t: ValType | null = null; var count = 0; // The parameter must be the pair struct the packs build (null // allowed), or the pack would be passed at a wider type. let paramPair = pairStructOf(callee.resultType(params[k])); var ok = paramPair != null; for (let s in sites) { if (!ok || s.k != k) { continue; } let sg = packGlobal(bodies[s.caller], s.pack); let st = bodies[s.caller].resultType(bodies[s.caller].a[s.pack]); let packPair = pairStructOf(bodies[s.caller].resultType(s.pack)); if (sg == null || st == null || packPair == null || paramPair == null || packPair.uid != paramPair.uid) { ok = false; break; } if (g == null) { g = sg; t = st; } else if (g.index != sg.index || !sameRefType(t, st)) { ok = false; break; } count += 1; } if (!ok || count == 0 || count != callCount[j]) { agreed.push(null); instanceType.push(null); continue; } agreed.push(g); instanceType.push(t); any = true; } if (!any) { continue; } // The clone: the body copied whole, each specialized parameter // retyped to the instance and re-packed at entry. let original = wasm.functions[j]; let clone = cloneBody(callee); let sigParams = new Array(); for (let p in original.signature.params) { sigParams.push(p); } let heads = new Array(); let count = clone.instCount(); let repl = new Array(count); for (var i = 0; i < count; i += 1) { repl.push(i); } for (var k = 0; k < params.length; k += 1) { let g = agreed[k]; let t = instanceType[k]; if (g == null || t == null) { continue; } let p = clone.blocks[0].params[k]; // The pack is non-null whatever the parameter allowed. let pair = pairStructOf(clone.resultType(p)); if (pair == null) { continue; } clone.typeTable.push(new ValTypeRef(pair)); let pairTy = clone.typeTable.length - 1; clone.typeTable.push(t); clone.typeId[p] = clone.typeTable.length - 1; sigParams[k] = t; clone.refTable.push(new IrRefGlobal(g)); let packId = clone.opcode.length; clone.opcode.push(IrOp.iface_pack as i32); clone.typeId.push(pairTy); clone.a.push(p); clone.b.push(clone.refTable.length - 1); clone.instBlock.push(0); heads.push(packId); repl[p] = packId; } // Uses of the parameter become the pack; the pack keeps the // parameter. let total = clone.instCount(); for (var i = 0; i < total; i += 1) { if (i >= count || clone.op(i) == IrOp.nop) { continue; } clone.rewriteValueOperands(i, (v) => { if (v >= 0 && v < count && repl[v] != v) { return repl[v]; } return v; }); } prependInsts(clone.blocks[0], heads); let sig = wasm.getSignatureLate(sigParams, original.signature.returns); let f = new WasmFunction(sig, null, original.model); f.name = (if (original.name != null) original.name as String else 'anonymous') + '$spec'; f.index = wasm.functionImports.length + wasm.functions.length; wasm.addFunction(f); bodies.push(clone); changed.push(true); clones += 1; // Every site: the pack's instance in place of the pack, the clone // in place of the callee. for (let s in sites) { if (agreed[s.k] == null) { continue; } let body = bodies[s.caller]; let argsIdx = body.a[s.inst]; body.extra[argsIdx + 1 + s.k] = body.a[s.pack]; let r = body.refTable[body.b[s.inst]]; if (!(r is IrRefFunc) || r.target.uid != f.uid) { body.refTable.push(new IrRefFunc(f)); body.b[s.inst] = body.refTable.length - 1; } changed[s.caller] = true; } } return clones; } /** The fat-pointer struct a reference type names, or null. */ function pairStructOf(vt: ValType | null): WasmStruct | null { if (vt == null) { return null; } let t = refTargetOf(vt); if (t is WasmStruct) { return t; } return null; } /** The pair vtable global an iface_pack names, or null. */ function packGlobal(body: IrBody, pack: i32): WasmGlobal | null { let r = body.refTable[body.b[pack]]; if (r is IrRefGlobal) { if (r.target.initVTable != null) { return r.target; } } return null; } function sameRefType(a: ValType | null, b: ValType | null): boolean { if (a == null || b == null) { return false; } if (a is ValTypeRef) { if (b is ValTypeRef) { return a.target.uid == b.target.uid; } } return false; } /** A deep copy of a body: same ids, same blocks, own arrays. */ function cloneBody(src: IrBody): IrBody { let dst = new IrBody(); let n = src.instCount(); for (var i = 0; i < n; i += 1) { dst.opcode.push(src.opcode[i]); dst.typeId.push(src.typeId[i]); dst.a.push(src.a[i]); dst.b.push(src.b[i]); dst.instBlock.push(src.instBlock[i]); } for (let e in src.extra) { dst.extra.push(e); } for (let blk in src.blocks) { let nb = new IrBlock(); for (let p in blk.params) { nb.params.push(p); } for (let inst in blk.insts) { nb.insts.push(inst); } dst.blocks.push(nb); } for (let t in src.typeTable) { dst.typeTable.push(t); } for (let r in src.refTable) { dst.refTable.push(r); } for (let c in src.constI64) { dst.constI64.push(c); } for (let c in src.constF64) { dst.constF64.push(c); } for (let v in src.varTypes) { dst.varTypes.push(v); } for (let k in src.tryJoin.keys()) { dst.tryJoin[k] = src.tryJoin[k]; } for (let k in src.adoptReturns) { dst.adoptReturns.add(k); } return dst; } function prependInsts(blk: IrBlock, ids: GrowableArray): void { let old = new Array(); for (let i in blk.insts) { old.push(i); } while (blk.insts.length > 0) { blk.insts.pop(); } for (let i in ids) { blk.insts.push(i); } for (let i in old) { blk.insts.push(i); } }