import { HashMap } from 'zena:collections'; /** * Per-parameter escape summaries (docs/design/optimization-pipeline.md * §Escape analysis and SROA): for every function and each of its * parameters, whether the body lets the parameter's object escape. * * A parameter escapes when the body stores it (into a field, an array, * a global, or a mutable variable), returns or throws it, builds * another object from it (struct_new, iface_pack), compares it by * identity, passes it to an indirect call or an import, or passes it * to a known function whose matching parameter escapes. Casts and * null assertions of the parameter are the same object and are * followed; so are block parameters the value is branched to. Reads — * field loads, tests, fat-pointer unpacks, array length — never * escape. * * The answer for one function depends on its callees', so the * summaries start optimistic (nothing escapes) and iterate to a * fixpoint: a parameter is marked escaping only when a concrete * escaping use exists, which makes the result sound for cycles too. * Each parameter is walked once, and again only when a callee * parameter its walk passed the value to turns out to escape: the * walk records those parameters, and marking one escaping queues the * walks that relied on it. * * The inliner uses this: a fresh allocation whose only use is a call * to a function whose parameter does not escape becomes, after * inlining, an object every use of which is in one body — which is * what the forwarding rules and DCE need to delete it. * * Determinism: functions in module order, uses in instruction order; * the function map is used for lookups only. */ import { IrBody, IrOp, IrRefFunc, IrUseLists, IrScratch, buildUseLists } from './ir.zena'; import { WasmModule, WasmFunction } from '../wasm-module.zena'; export final class EscapeSummaries { /** escapes[f][k]: function f's k-th parameter escapes. */ escapes = new Array>(); #bodyIndex: HashMap; new(wasm: WasmModule, bodies: GrowableArray, scratch: IrScratch) : #bodyIndex = wasm.functionIndex() { // The use lists live for the fixpoint; the per-parameter walks // scope their own. scratch.enter(); for (let body in bodies) { let row = new Array(); let n = if (body.blocks.length > 0) body.blocks[0].params.length else 0; for (var k = 0; k < n; k += 1) { row.push(false); } this.escapes.push(row); } // The bodies do not change during the fixpoint, so each one's use // lists are built once, by the first walk that needs them. let tables = new Array(bodies.length); for (var f = 0; f < bodies.length; f += 1) { tables.push(null); } // dependents[g]: triples (g's parameter i, f, k) for each walk of // f's k-th parameter that passed the value to g's parameter i // while that did not escape. let dependents = new Array | null>(bodies.length); for (var f = 0; f < bodies.length; f += 1) { dependents.push(null); } // The walks to do, as (f, k) pairs: every parameter in module order, // then the ones a parameter's escaping put in doubt. let work = new Array(); for (var f = 0; f < bodies.length; f += 1) { for (var k = 0; k < this.escapes[f].length; k += 1) { work.push(f); work.push(k); } } var next = 0; while (next < work.length) { let f = work[next]; let k = work[next + 1]; next += 2; let row = this.escapes[f]; if (row[k]) { continue; } let users = tables[f] ?? buildUseLists(bodies[f], scratch); tables[f] = users; if (!this.#paramEscapes(bodies[f], users, f, k, dependents, scratch)) { continue; } row[k] = true; let waiting = dependents[f]; if (waiting != null) { for (var d = 0; d < waiting.length; d += 3) { if (waiting[d] == k && !this.escapes[waiting[d + 1]][waiting[d + 2]]) { work.push(waiting[d + 1]); work.push(waiting[d + 2]); } } } } scratch.exit(); } paramEscapes(f: i32, k: i32): boolean { let row = this.escapes[f]; if (k < 0 || k >= row.length) { return true; } return row[k]; } #paramEscapes(body: IrBody, users: IrUseLists, f: i32, k: i32, dependents: GrowableArray | null>, scratch: IrScratch): boolean { scratch.enter(); let result = this.#paramEscapesOn(body, users, f, k, dependents, scratch); scratch.exit(); return result; } /** * Walks function `f`'s parameter `k`. A call that passes the value to * a parameter not yet known to escape is recorded in `dependents`, so * the walk is done again if that parameter turns out to escape. */ #paramEscapesOn(body: IrBody, users: IrUseLists, f: i32, k: i32, dependents: GrowableArray | null>, scratch: IrScratch): boolean { let count = body.instCount(); let alias = scratch.bool(); for (var i = 0; i < count; i += 1) { alias.push(false); } let work = scratch.i32(); let start = body.blocks[0].params[k]; alias[start] = true; work.push(start); while (work.length > 0) { let v = work.pop(); for (var ui = 0; ui < users.count(v); ui += 1) { let u = users.at(v, ui); let op = body.op(u); let av = body.a[u]; if (op == IrOp.ref_cast || op == IrOp.ref_as_non_null) { if (!alias[u]) { alias[u] = true; work.push(u); } continue; } if (op == IrOp.struct_get || op == IrOp.ref_test || op == IrOp.ref_is_null || op == IrOp.iface_instance || op == IrOp.iface_vtable || op == IrOp.array_len || op == IrOp.array_get || op == IrOp.array_get_u || op == IrOp.array_get_s) { // Reads. array_get's index slot cannot hold a reference. continue; } if (op == IrOp.struct_set) { if (body.extra[av + 1] == v) { return true; } continue; // written into, not stored } if (op == IrOp.array_set) { if (body.extra[av + 2] == v) { return true; } continue; } if (op == IrOp.call) { let argc = body.extra[av]; let r = body.refTable[body.b[u]]; var calleeIdx = -1; if (r is IrRefFunc) { if (let (true, idx) = this.#bodyIndex.get(r.target)) { calleeIdx = idx; } } var i = 0; while (i < argc) { if (body.extra[av + 1 + i] == v) { if (calleeIdx < 0 || this.paramEscapes(calleeIdx, i)) { return true; } var waiting = dependents[calleeIdx]; if (waiting == null) { waiting = new Array(); dependents[calleeIdx] = waiting; } waiting.push(i); waiting.push(f); waiting.push(k); } i += 1; } continue; } if (op == IrOp.br || op == IrOp.br_if || op == IrOp.br_table || op == IrOp.br_on_cast || op == IrOp.br_on_cast_fail) { // As a branch argument the value flows into the target's // parameter, another alias; as a condition or scrutinee it // is only tested. let n = body.successorCount(u); for (var k = 0; k < n; k += 1) { let rec = body.successorRecord(u, k); let argc = body.extra[rec + 1]; var i = 0; while (i < argc) { if (body.extra[rec + 2 + i] == v) { let p = body.blocks[body.extra[rec]].params[i]; if (!alias[p]) { alias[p] = true; work.push(p); } } i += 1; } } continue; } // Everything else — stores to globals and variables, returns, // throws, allocation from it, packing, identity comparison, // indirect calls, and any op this table does not know — lets // the object out. return true; } } return false; } }