/** * Harvest (docs/design/optimization-pipeline.md §Harvest and layout * feedback): after the optimization loop, delete the functions and * globals nothing can reach any more. The loop inlines bodies, makes * calls direct, and forwards fat pointers away without touching the * callee or the vtable, so a function whose every call site was * inlined, or an interface pair whose every pack was forwarded, is * still in the module until this runs. * * Reachability starts from the roots — the exported functions and * globals and the start function — and follows, in the bodies it * reaches, direct calls, tail calls, `ref_func`, and global reads, * writes, and packs; a live vtable global makes the functions it * installs live, and a live singleton global makes its class's vtable * global live. Nothing else can name a function or a global. * * An imported function is live when something live calls or names it, * and the others go too: reachability reaches a host function through * any method in a vtable (`App.listen` reaches the host server), and a * component imports exactly what its module does, so an import left * behind is one the host must provide, which a declared world that does * not import it rejects (#840). * * Removal rebinds function and global indices the way layout assigns * them (imports first, then survivors in order) and recomputes which * functions need an element-segment entry. Emission reads indices off * the objects, so it needs no other change; this runs before any * section is emitted. * * The caller feeds the result back: with vtable globals gone, * devirtualization has fewer candidates per slot, so another round * can make more calls direct. * * Determinism: the worklist is seeded in root order and follows * bodies in instruction order; the maps are used for lookups only. */ import { IrBody, IrOp, IrRefFunc, IrRefGlobal } from './ir.zena'; import { WasmModule, WasmFunction, WasmGlobal } from '../wasm-module.zena'; import { getClassKey } from '../codegen-utils.zena'; import { HashSet } from 'zena:collections'; /** What one harvest removed. */ export final class HarvestResult { functions: i32; globals: i32; imports: i32; new(this.functions, this.globals, this.imports); } /** * Deletes unreachable functions (from `wasm.functions` and `bodies`, * kept parallel) and globals, and rebinds their indices. */ export function pruneUnreached(wasm: WasmModule, bodies: GrowableArray, roots: GrowableArray): HarvestResult { let fcount = wasm.functions.length; let bodyIndex = wasm.functionIndex(); // Globals are looked up by their index, which layout assigned as // the position in wasm.globals and which this pass rebinds the same // way, so it stays the position across harvests. let gcount = wasm.globals.length; let importGCount = wasm.globalImports.length; let liveF = new Array(fcount); for (var i = 0; i < fcount; i += 1) { liveF.push(false); } let liveG = new Array(gcount); for (var i = 0; i < gcount; i += 1) { liveG.push(false); } // An import has no body to walk: it is live once something names it. let liveImports = new HashSet(); // One worklist for both kinds: function entries are their body // index, global entries are offset past the function count. let work = new Array(); let markFunction = (f: WasmFunction) => { if (f.isImport) { liveImports.add(f); return; } if (let (true, idx) = bodyIndex.get(f)) { if (!liveF[idx]) { liveF[idx] = true; work.push(idx); } } }; // The function whose body is being walked, for the error below. var referrerName = 'the roots'; let markGlobal = (g: WasmGlobal) => { if (g.isImport) { return; } let idx = g.index - importGCount; if (idx < 0 || idx >= gcount) { throw new Error(`harvest: a global outside the module: ${g.name} (index ${i32ToString(g.index)}), referenced from ${referrerName}`); } if (!liveG[idx]) { liveG[idx] = true; work.push(fcount + idx); } }; for (let r in roots) { markFunction(r); } let start = wasm.startFunction; if (start != null) { markFunction(start); } let exportedGlobals = wasm.exportGlobalMap.keys(); for (let key in exportedGlobals) { markGlobal(wasm.exportGlobalMap[key]); } while (work.length > 0) { let item = work.pop(); if (item >= fcount) { let g = wasm.globals[item - fcount]; let init = g.initVTable; if (init != null) { for (let f in init.funcs) { markFunction(f); } let slots = init.slotGlobals; if (slots != null) { for (let s in slots) { if (s != null) { markGlobal(s); } } } } let singleton = g.initSingletonStruct; if (singleton != null) { if (let (true, info) = wasm.classInfos.get(getClassKey(singleton))) { let vt = info.vtableGlobal; if (vt != null) { markGlobal(vt); } } } continue; } let body = bodies[item]; referrerName = wasm.functions[item].name ?? ''; let n = body.instCount(); for (var inst = 0; inst < n; inst += 1) { let op = body.op(inst); if (op == IrOp.call || op == IrOp.ret_call || op == IrOp.ref_func) { let r = body.refTable[body.b[inst]]; if (r is IrRefFunc) { markFunction(r.target); } } else if (op == IrOp.global_get || op == IrOp.global_set || op == IrOp.iface_pack) { let r = body.refTable[body.b[inst]]; if (r is IrRefGlobal) { markGlobal(r.target); } } } } var removedF = 0; let keptFunctions = new Array(); let keptBodies = new Array(); for (var i = 0; i < fcount; i += 1) { if (liveF[i]) { keptFunctions.push(wasm.functions[i]); keptBodies.push(bodies[i]); } else { removedF += 1; } } var removedG = 0; let keptGlobals = new Array(); for (var i = 0; i < gcount; i += 1) { if (liveG[i]) { keptGlobals.push(wasm.globals[i]); } else { removedG += 1; } } let keptImports = new Array(); for (let f in wasm.functionImports) { if (liveImports.has(f)) { keptImports.push(f); } } let removedI = wasm.functionImports.length - keptImports.length; if (removedF == 0 && removedG == 0 && removedI == 0) { return new HarvestResult(0, 0, 0); } if (removedI > 0) { wasm.functionImports.clear(); for (let f in keptImports) { wasm.functionImports.push(f); } } while (wasm.functions.length > 0) { wasm.functions.pop(); } while (bodies.length > 0) { bodies.pop(); } for (let f in keptFunctions) { wasm.functions.push(f); } wasm.invalidateFunctionIndex(); for (let b in keptBodies) { bodies.push(b); } while (wasm.globals.length > 0) { wasm.globals.pop(); } for (let g in keptGlobals) { wasm.globals.push(g); } wasm.bindIndices(); // The element segment lists the functions ref_func names, plus the // vtable installs; recompute it from what survived. for (let f in wasm.functions) { f.isReferenceTaken = false; } for (let g in wasm.globals) { let init = g.initVTable; if (init != null) { for (let f in init.funcs) { f.isReferenceTaken = true; } } } for (let body in bodies) { let n = body.instCount(); for (var inst = 0; inst < n; inst += 1) { if (body.op(inst) == IrOp.ref_func) { let r = body.refTable[body.b[inst]]; if (r is IrRefFunc) { r.target.isReferenceTaken = true; } } } } return new HarvestResult(removedF, removedG, removedI); }