/** * The generator split pass (generators.md §4–§5, protocol form). * * Runs between RTA and layout() (`prepareGenerators`): every reached * `gen` function's body is lowered to presplit ZIR (an ordinary CFG * with yield_ suspension terminators), a hidden frame struct * implementing Iterator is synthesized from suspension liveness, * and two finished IrBodies are produced and stashed for the * per-function loop: * * - the RAMP (the generator function itself): allocate the frame, * spill the arguments into it, pack the Iterator fat pointer, * return. Lazy by construction — none of the body runs. * - next(): the state machine. A single dispatcher loop (a br_if * chain; br_table has no emit support yet) heads every resume * point and every yield-containing loop header, so the CFG stays * reducible for the emitter's stackifier. Values live into any * dispatch target are demoted to frame fields: stored at their * definition, loaded at each use (generators.md §5.2's "values * live across any yield — including loop-carried block * parameters — get frame fields"). * * $state encoding: 0 = START, 1 = RUNNING, 2 = DONE, 3+k = suspended * at yield k. Suspend states double as dispatcher pc values; headers * of yield-containing loops get pc values above the suspend range * (never stored in $state — they are internal re-entry points only). * RUNNING is the poison state: reentrancy and resume-after-throw both * land on it. The design calls for throwing an Error there; v1 traps * (unreachable) — loud either way, revisit with the async runtime. */ import { Set, HashMap, HashSet } from 'zena:collections'; import { ValType, ValTypeI32, ValTypeI64, ValTypeF32, ValTypeF64, ValTypeRef, ValTypeRefNull, } from '../wasm.zena'; import { WasmModule, WasmStruct, WasmField, WasmFunction, WasmGlobal, WasmSignature, WasmTag, VTableInit, asWasmStruct, } from '../wasm-module.zena'; import { IrOp, IrBody, IrBlock, IrRef, IrRefField, IrRefType, IrRefGlobal, IrRefTag, isIrTerminator, } from './ir.zena'; import { IrBuilder, valTypesStrictlyEqual } from './builder.zena'; import { IrCfg } from './cfg.zena'; import { FunctionLowerer } from './lowering.zena'; import { LoweringContext } from './lowering-context.zena'; import { ReachabilityAnalysis } from '../reachability/analysis.zena'; import { getInterfaceMemberSignature, getClassTypeParameters, substituteTypeParamsInCodegen, stepInlineValue, inlineLayoutOf, typeToValTypeWithSub, } from '../type-mapping.zena'; import { ClassKey, getInterfaceKey, getClassInterfaceKey, getClassInterfaceVTableName, getInterfaceTrampolineName, } from '../codegen-utils.zena'; import { Type, InterfaceType, FunctionType, TupleType, isScopedType, scopedInner } from '../../types.zena'; import { FunctionExpression, MethodDefinition, Node } from '../../ast.zena'; import { growable } from 'zena:core'; let STATE_RUNNING = 1; let STATE_DONE = 2; let STATE_FIRST_SUSPEND = 3; /** The finished bodies for one generator, keyed by WasmFunction uid. */ final class GeneratorArtifacts(rampBody: IrBody, nextBody: IrBody) /** * Prep-time registry: prepareGenerators fills it, the per-function * loop reads it back through lowerGeneratorRamp/lowerGeneratorNext. * Cleared at the start of every prepare so repeated compiles in one * process stay independent. */ var rampBodies = new Map(); var nextBodies = new Map(); /** * Whether `func` is the forwarder of an exploded function * (ir/explode.zena). It shares its core's node, but the core is the * suspending body: the forwarder only reads the record's fields and * calls it, so neither split rewrites it. */ export function isExplosionForwarder(func: WasmFunction): boolean { let explosion = func.explosion; return explosion != null && explosion.forwarder === func; } /** True if this WasmFunction carries a synchronous `gen` AST node (`!isAsync`). */ export function isGeneratorFunction(func: WasmFunction): boolean { let {node} = func; if (node == null || isExplosionForwarder(func)) { return false; } return match (node) { case FunctionExpression {isGenerator, isAsync}: isGenerator && !isAsync case MethodDefinition {isGenerator, isAsync}: isGenerator && !isAsync case _: false }; } function funcDisplayName(func: WasmFunction) { let {name} = func; if (name != null) { return name; } return 'generator'; } /** * The Iterator (or AsyncIterator) instantiation a generator * returns, from its checked FunctionType with class/function type * arguments substituted (the memoized instantiation object, so * interface keys match the call sites'). */ export function iteratorInstantiationOf(wasm: WasmModule, func: WasmFunction): InterfaceType { let t = func.model.getNodeType(func.node as Node); if (t == null || !(t is FunctionType)) { throw new Error('generator has no checked function type: ' + funcDisplayName(func)); } var ret = t.returnType; // A borrow-taking generator returns Scoped>; the frame // it lowers to is the Iterator behind the wrapper. if (isScopedType(ret)) { let inner = scopedInner(ret); if (inner != null) { ret = inner; } } let {classType} = func; if (classType != null) { let ct = classType; if (ct.typeArguments != null) { ret = substituteTypeParamsInCodegen(wasm, getClassTypeParameters(ct), ct.typeArguments, ret); } } if (func.typeParameters != null && func.typeArguments != null) { ret = substituteTypeParamsInCodegen(wasm, func.typeParameters, func.typeArguments, ret); } if (!(ret is InterfaceType)) { throw new Error('generator return type is not Iterator: ' + funcDisplayName(func)); } return ret; } // --------------------------------------------------------------------------- // Raw IrBody append helpers. The transform mutates the presplit body in // place (blocks own their inst lists; the flat arrays are append-only), // so it cannot go through IrBuilder, which refuses terminated blocks. // // These, computeLiveIn, loopContainsSuspend, weakenToNullable, // rerouteEdges and the TryRegion helpers are exported because the async // split pass (async.zena) is the same transform over a different // suspension terminator and reuses them verbatim. Keep them // suspension-kind neutral. // --------------------------------------------------------------------------- export function truncate(a: GrowableArray): void { while (a.length > 0) { a.pop(); } } /** * One user-level `try` region of a presplit body: the try_br's body and * catch successors, its exception-tag ref, and the join block recorded * on the try_br (-1 when no arm completes). * * A region's extent is the dominator subtree of its body target MINUS * the join's subtree. Dominance alone over-claims: when the catch * diverges, the join's only predecessor is the body's exit, so the * continuation after the try is dominated by the body target while * sitting outside the region (issue #426). The join annotation * (ir.zena, `tryJoin`) is what marks where the region actually ends, * and emit.zena's try_br case applies the same carve-out when placing * the `try_table`. */ export final class TryRegion( bodyTarget: i32, catchTarget: i32, tagRef: i32, joinTarget: i32) /** * Every user `try` region in the presplit body, in block order. * * Regions either split pass synthesizes for itself — async's * failure-capture region around the whole machine, and the fresh * re-entry try_brs below — are built later and are not in here; this * sees only regions the user wrote. */ export function collectTryRegions(body: IrBody): GrowableArray { let regions = new Array(); var bi = 0; while (bi < body.blocks.length) { let insts = body.blocks[bi].insts; if (insts.length > 0) { let term = insts[insts.length - 1]; if (body.op(term) == IrOp.try_br) { let succs = body.successors(term); let join = if (let (true, j) = body.tryJoin.get(term)) j else -1; regions.push(new TryRegion(succs[0].target, succs[1].target, body.a[term], join)); } } bi += 1; } return regions; } /** * The regions enclosing `block`, outermost first. * * Ordering is by dominance between the regions' body targets: an outer * region's body dominates an inner one's, so re-entering them in this * order rebuilds the same nesting the source had. */ export function enclosingRegionsOf( cfg: IrCfg, regions: GrowableArray, block: i32 ): GrowableArray { let hits = new Array(); for (let r in regions) { if (!cfg.dominates(r.bodyTarget, block)) { continue; } // The join's subtree is dominated by the body target when the // catch diverges, but it is AFTER the region — a dispatch target // there must not re-enter this region's handler (issue #426). if (r.joinTarget >= 0 && cfg.dominates(r.joinTarget, block)) { continue; } hits.push(r); } // Insertion sort, outermost (most-dominating) first. var i = 1; while (i < hits.length) { let cur = hits[i]; var j = i - 1; while (j >= 0 && !cfg.dominates(hits[j].bodyTarget, cur.bodyTarget)) { hits[j + 1] = hits[j]; j -= 1; } hits[j + 1] = cur; i += 1; } return hits; } /** * Which user `try` regions enclose each dispatch target, keyed by block. * * Every dispatch target, not just the resume blocks: rerouteEdges sends * every edge into a dispatch target through the dispatcher, so a * suspending loop's header is left by the loop's entry edge and its * backedge alike. Covering only resume blocks protects the segment after * each suspension — which is dominated by its resume block — but leaves * the stretch from the header down to the suspension running outside the * region on every iteration. * * Computed on the pristine CFG, before the transform rewires edges. */ export function dispatchRegionsOf( body: IrBody, cfg: IrCfg, pcOfBlock: HashMap ): HashMap> { let regions = collectTryRegions(body); let out = new Map>(); var b = 0; while (b < body.blocks.length) { if (pcOfBlock.has(b)) { out[b] = enclosingRegionsOf(cfg, regions, b); } b += 1; } return out; } /** * Adds to `pcOfBlock` any merge block inside a user `try` region that * would otherwise be reached from multiple dispatcher arms and hoist * outside its enclosing `try_table` during stackification. * * Each dispatch target `d` (and block 0) heads a separate arm of the * dispatcher. When two arms can both reach a block `b` that sits inside * an enclosing `TryRegion` `r` — either along normal edges after a * diamond whose one arm suspended, or through an inner region's handler * (`ehB` -> `dispatchB` in a `try`/`finally` or `for await` loop) that * gained a second predecessor from `reenterRegions` — `b`'s post-split * immediate dominator becomes the dispatcher rather than `r`'s body, so * the emitter places `b` outside `r`'s `try_table` and any throw or * rethrow in `b` misses `r`'s handler. Promoting `b` to a dispatch * target routes its incoming edges through the dispatcher and re-enters * `r` around `b`. */ export function addRegionMergeTargets( body: IrBody, cfg: IrCfg, pcOfBlock: HashMap, nextPcIn: i32 ): i32 { let regions = collectTryRegions(body); if (regions.length == 0) { return nextPcIn; } let n = body.blocks.length; let tryTargets = new Set(); for (let r in regions) { tryTargets.add(r.bodyTarget); tryTargets.add(r.catchTarget); } let enclosed = new Array(n); var bi = 0; while (bi < n) { enclosed.push(cfg.isReachable(bi) && enclosingRegionsOf(cfg, regions, bi).length > 0); bi += 1; } var nextPc = nextPcIn; var changed = true; while (changed) { changed = false; // Per-block arm state: -1 = unreached, >= 0 = reached by that one // arm, -2 = reached by two or more distinct arms. let armOf = new Array(n); var i = 0; while (i < n) { armOf.push(-1); i += 1; } let mergeArm = (b: i32, arm: i32) => { if (arm < 0) { return; } let cur = armOf[b]; if (cur == -1) { armOf[b] = arm; } else if (cur != arm) { armOf[b] = -2; } }; armOf[0] = 0; pcOfBlock.forEach((d, _pc) => { armOf[d] = d; for (let r in enclosingRegionsOf(cfg, regions, d)) { mergeArm(r.catchTarget, d); } }); var prop = true; while (prop) { prop = false; var u = 0; while (u < n) { let uArm = armOf[u]; if (uArm != -1 && body.blocks[u].insts.length > 0) { let term = body.blocks[u].insts[body.blocks[u].insts.length - 1]; let op = body.op(term); if (op != IrOp.yield_ && op != IrOp.await_ && op != IrOp.ret && op != IrOp.ret_multi && op != IrOp.throw && op != IrOp.unreachable) { let succs = body.successors(term); for (let s in succs) { let v = s.target; if (v != 0 && !pcOfBlock.has(v)) { let prev = armOf[v]; if (uArm == -2) { if (prev != -2) { armOf[v] = -2; prop = true; } } else { mergeArm(v, uArm); if (armOf[v] != prev) { prop = true; } } } } } } u += 1; } } for (let b in cfg.rpo) { if (b != 0 && !pcOfBlock.has(b) && enclosed[b] && !tryTargets.has(b) && armOf[b] == -2) { pcOfBlock[b] = nextPc; nextPc += 1; changed = true; break; } } } return nextPc; } /** * Adds to the spill set every value live into the catch target of a * region enclosing a dispatch target. * * Re-entering those regions from the dispatcher gives each such catch * a predecessor that does not pass through definitions above the * region, so a value defined there and read in or after the catch is * no longer dominated by its definition — only a frame load at the use * restores that. Values defined INSIDE the region need nothing: a * catch's presplit predecessor is the try_br terminator itself, so the * body's values never reached the catch as direct SSA uses in the * first place (they ride cells, ir.md §5.1). */ export function spillCatchLiveIns( liveIn: GrowableArray>, dispatchRegions: HashMap>, spilled: HashSet ): void { dispatchRegions.forEach((target, regions) => { for (let r in regions) { for (let v in liveIn[r.catchTarget]) { spilled.add(v); } } }); } /** * Frame fields for the body's mutable variables, appended to `fields`. * * A mutable variable (ir.md §5.1.1) is pinned to a wasm local, and a * local does not survive a suspension — the reason `try`/`finally` and * `using` used to bail in suspension bodies: their exit-dispatch state * (the exit code, the parked result, the saved payload) rides * variables. In a split body every variable lives in the frame * instead: one nullable-weakened field per var index, with the ops * rewritten by rewriteVarsToFrame. */ export function varFieldsOf(body: IrBody, fields: GrowableArray): void { var i = 0; while (i < body.varTypes.length) { fields.push(new WasmField('$var' + i32ToString(i), weakenToNullable(body.varTypes[i]), true)); i += 1; } } /** * Rewrites var_get/var_set into frame-field reads and writes, then * clears varTypes so emit allocates no locals for them. * * Runs after the spill/reroute passes, so a var_set's value operand * has already been remapped to its frame load where needed. The frame * param dominates every block, so the rewritten accesses need no * dominance care of their own. A var_get of a non-nullable ref type * reads the weakened field through a fresh instruction and the * ORIGINAL id becomes the re-assertion, so users are untouched. Field * defaults (zero/null) match the wasm-local defaults the variables * had, and every dispatch path writes its variable before the replay * reads it. */ export function rewriteVarsToFrame( body: IrBody, bodyBlocks: GrowableArray, frame: WasmStruct, frameParam: i32 ): void { if (body.varTypes.length == 0) { return; } for (let blockId in bodyBlocks) { let block = body.blocks[blockId]; let rebuilt = new Array(); for (let inst in block.insts) { let op = body.op(inst); if (op == IrOp.var_get) { let varId = body.b[inst]; let vt = body.varTypes[varId]; let weak = weakenToNullable(vt); let fieldRef = addRawRef(body, new IrRefField(frame, '$var' + i32ToString(varId))); if (valTypesStrictlyEqual(weak, vt)) { body.opcode[inst] = IrOp.struct_get as i32; body.typeId[inst] = internVt(body, vt); body.a[inst] = frameParam; body.b[inst] = fieldRef; rebuilt.push(inst); } else { let load = rawInst(body, IrOp.struct_get, internVt(body, weak), frameParam, fieldRef); rebuilt.push(load); body.instBlock[load] = blockId; body.opcode[inst] = IrOp.ref_as_non_null as i32; body.typeId[inst] = internVt(body, vt); body.a[inst] = load; body.b[inst] = -1; rebuilt.push(inst); } } else if (op == IrOp.var_set) { let value = body.a[inst]; let varId = body.b[inst]; let fieldRef = addRawRef(body, new IrRefField(frame, '$var' + i32ToString(varId))); let idx = body.extra.length; body.extra.push(frameParam); body.extra.push(value); body.opcode[inst] = IrOp.struct_set as i32; body.typeId[inst] = -1; body.a[inst] = idx; body.b[inst] = fieldRef; rebuilt.push(inst); } else { rebuilt.push(inst); } } replaceContents(block.insts, rebuilt); } while (body.varTypes.length > 0) { body.varTypes.pop(); } } /** Replaces dst's contents with src's, in place (IrBlock fields are * immutable bindings; the arrays themselves are mutable). */ export function replaceContents(dst: GrowableArray, src: GrowableArray): void { truncate(dst); for (let v in src) { dst.push(v); } } export function internVt(body: IrBody, vt: ValType): i32 { let table = body.typeTable; var i = 0; while (i < table.length) { if (valTypesStrictlyEqual(table[i], vt)) { return i; } i += 1; } table.push(vt); return table.length - 1; } export function addRawRef(body: IrBody, ref: IrRef): i32 { body.refTable.push(ref); return body.refTable.length - 1; } /** Appends an instruction to the flat arrays, unplaced (instBlock -1). */ export function rawInst(body: IrBody, op: IrOp, typeIdx: i32, a: i32, b: i32): i32 { body.opcode.push(op as i32); body.typeId.push(typeIdx); body.a.push(a); body.b.push(b); body.instBlock.push(-1); return body.opcode.length - 1; } export function placeInst(body: IrBody, blockId: i32, inst: i32): void { body.blocks[blockId].insts.push(inst); body.instBlock[inst] = blockId; } export function rawParam(body: IrBody, blockId: i32, vt: ValType): i32 { let inst = rawInst(body, IrOp.param, internVt(body, vt), -1, -1); body.blocks[blockId].params.push(inst); body.instBlock[inst] = blockId; return inst; } function rawConstI32(body: IrBody, value: i32) { return rawInst(body, IrOp.const_i32, internVt(body, new ValTypeI32()), value, -1); } /** A zero/null of the given type, for the exhausted `(false, _)` slot. */ export function rawDefaultOf(body: IrBody, vt: ValType): i32 { return match (vt) { case ValTypeI32: rawConstI32(body, 0) case ValTypeI64: { body.constI64.push(0 as i64); rawInst(body, IrOp.const_i64, internVt(body, vt), body.constI64.length - 1, -1) } case ValTypeF32: { body.constF64.push(0.0); rawInst(body, IrOp.const_f32, internVt(body, vt), body.constF64.length - 1, -1) } case ValTypeF64: { body.constF64.push(0.0); rawInst(body, IrOp.const_f64, internVt(body, vt), body.constF64.length - 1, -1) } case _: rawInst(body, IrOp.ref_null, internVt(body, vt), -1, -1) }; } /** * The Ready value of a step as `next()` returns it. It is one result, * unless the step unboxes a tuple (`(1, inline T, _)` with a tuple for * `T`): then the body still yields the tuple boxed, and each of the * tuple's fields is a result of its own. */ export final class StepValue { /** The boxed tuple a yield produces, when the value is unboxed. */ struct: WasmStruct | null; /** The field of `struct` each value result reads. */ fields: GrowableArray; new(this.struct, this.fields); lanes(): i32 { return if (this.struct == null) 1 else this.fields.length; } } /** The shape of `iface`'s Ready value (see `StepValue`). */ export function stepValueOf(wasm: WasmModule, iface: InterfaceType, func: WasmFunction): StepValue { let inner = stepInlineValue(wasm, iface); if (inner == null) { return new StepValue(null, new Array()); } let boxed = new TupleType(inner.elementTypes, null, 0); let st = asWasmStruct(typeToValTypeWithSub(wasm, boxed, func)); if (st == null) { throw new Error('unboxed step value has no tuple struct'); } let layout = inlineLayoutOf(wasm, inner as Type); if (layout == null) { throw new Error('unboxed step value has no layout'); } let fields = new Array(); for (let path in layout.slotPaths) { fields.push(path); } return new StepValue(st, fields); } /** * The value results of a step, unplaced: each at its default when * `value` is -1 (Done), else `value` itself, or its fields when the * step unboxes it. `returns` is the `next()` result list. */ export function rawValueLanes(body: IrBody, returns: GrowableArray, sv: StepValue, value: i32): GrowableArray { let out = new Array(); let st = sv.struct; for (var i = 0; i < sv.lanes(); i += 1) { if (value < 0) { out.push(rawDefaultOf(body, returns[1 + i])); } else if (st == null) { out.push(value); } else { let name = sv.fields[i]; let field = st.fields[st.fieldIndexByName(name)]; out.push(rawInst(body, IrOp.struct_get, internVt(body, field.type), value, addRawRef(body, new IrRefField(st, name)))); } } return out; } /** A step's results as a `ret_multi` operand record: the flag, the * value results, and the future when `future` is not -1. */ export function rawStepResults(body: IrBody, flag: i32, lanes: GrowableArray, future: i32): i32 { let idx = body.extra.length; body.extra.push(1 + lanes.length + (if (future >= 0) 1 else 0)); body.extra.push(flag); for (let lane in lanes) { body.extra.push(lane); } if (future >= 0) { body.extra.push(future); } return idx; } // --------------------------------------------------------------------------- // Liveness on the presplit CFG (standard backward per-block dataflow). // --------------------------------------------------------------------------- /** live-in set per block: values live on entry (block params excluded). */ export function computeLiveIn(body: IrBody, cfg: IrCfg): GrowableArray> { let n = body.blocks.length; let uses = new Array>(n); let defs = new Array>(n); let liveIn = new Array>(n); var bi = 0; while (bi < n) { let use = new Set(); let def = new Set(); let block = body.blocks[bi]; for (let p in block.params) { def.add(p); } let ops = new Array(); for (let inst in block.insts) { truncate(ops); body.appendValueOperands(inst, ops); for (let v in ops) { if (!def.has(v)) { use.add(v); } } def.add(inst); } uses.push(use); defs.push(def); liveIn.push(new Set()); bi += 1; } var changed = true; while (changed) { changed = false; // Reverse RPO converges fastest for backward problems; correctness // only needs the fixpoint. var ri = cfg.rpo.length - 1; while (ri >= 0) { let b = cfg.rpo[ri]; ri -= 1; let inSet = liveIn[b]; let term = body.blocks[b].insts[body.blocks[b].insts.length - 1]; let sN = body.successorCount(term); for (var sK = 0; sK < sN; sK += 1) { let sRec = body.successorRecord(term, sK); for (let v in liveIn[body.extra[sRec]]) { if (!defs[b].has(v) && !inSet.has(v)) { inSet.add(v); changed = true; } } } for (let v in uses[b]) { if (!inSet.has(v)) { inSet.add(v); changed = true; } } } } return liveIn; } // --------------------------------------------------------------------------- // The pass driver. // --------------------------------------------------------------------------- /** * Called by ModuleGenerator between RTA and wasm.layout(): everything * a generator needs (frame struct, next() function, trampoline, * Iterator vtable global) must exist before indices lock. */ export function prepareGenerators( wasm: WasmModule, pass: ReachabilityAnalysis ): void { rampBodies = new Map(); nextBodies = new Map(); // With disposal active, every frame struct subtypes one shared // shape holding the two disposal-relevant fields, so a for-in's // finalizer can test and drive any generator without knowing which. if (wasm.generatorDisposalActive && wasm.generatorFrameSuper == null) { let superFields = growable([ new WasmField('$state', new ValTypeI32(), true), new WasmField('$disposing', new ValTypeI32(), true), ]); let sup = new WasmStruct('$GenFrame', superFields); wasm.types.push(sup); pass.markTypeReached(sup); wasm.generatorFrameSuper = sup; } // Index loop: prepareOne appends trampoline/next functions. var i = 0; while (i < wasm.functions.length) { let func = wasm.functions[i]; i += 1; if (!isGeneratorFunction(func)) { continue; } if (func.typeParameters != null && func.typeArguments == null) { // Generic template; its specializations are processed instead. continue; } prepareOne(wasm, pass, func, i - 1); } } /** * The consumer half of generator disposal, emitted into a for-in's * exit finalizer (control-flow.zena): if the loop's iterator instance * is a generator frame, drive the frame's cancellation delivery. In * this file so the $state encoding it tests (header comment: 0 START, * 1 RUNNING, 2 DONE, 3+ suspended) has one home. * * A frame that never ran or already finished is only marked DONE — * nothing is pending in it, and a generator that completed normally * already ran its finalizers on the way out. A suspended frame gets * $disposing set and one next() call: the resume head raises on the * cancellation channel, the raise unwinds through the re-entered user * regions — the finalizers the suspended yield was under run — and * next()'s cancellation capture marks the frame DONE and returns * exhausted. * * A RUNNING frame is one whose step threw: next() sets RUNNING on the * way in and nothing resets it when an exception leaves, and this * finalizer is where that exception passes next. It is left as it is. * The throw already unwound through the body's own regions, so its * finalizers have run and there is no suspended yield to resume, and * RUNNING stays the poison a later next() traps on (generators.md * §5.2). */ export function emitGeneratorDispose(cx: LoweringContext, iter: i32): void { let supOpt = cx.wasm.generatorFrameSuper; if (supOpt == null) { return; } let sup = supOpt as WasmStruct; let none = new Array(); let i32vt = new ValTypeI32() as ValType; let obj = cx.unwrapFatPointerValue(iter); let isFrame = cx.b.emit(IrOp.ref_test, i32vt, obj, cx.b.internType(new ValTypeRef(sup) as ValType)); let genB = cx.b.newBlock(); let contB = cx.b.newBlock(); cx.b.brIf(isFrame, genB, none, contB, none); cx.b.switchTo(genB); let frameVt = new ValTypeRef(sup) as ValType; let g = cx.b.emit(IrOp.ref_cast, frameVt, obj, cx.b.internType(frameVt)); let stateRef = cx.b.addRef(new IrRefField(sup, '$state')); let s = cx.b.emit(IrOp.struct_get, i32vt, g, stateRef); let suspB = cx.b.newBlock(); let idleB = cx.b.newBlock(); let isSusp = cx.b.binary(IrOp.i32_ge_s, i32vt, s, cx.b.constI32(STATE_FIRST_SUSPEND, i32vt)); cx.b.brIf(isSusp, suspB, none, idleB, none); cx.b.switchTo(suspB); let disposingRef = cx.b.addRef(new IrRefField(sup, '$disposing')); let setDisposing = growable([g, cx.b.constI32(1, i32vt)]); cx.b.emitVoid(IrOp.struct_set, cx.b.pushExtra(setDisposing), disposingRef); cx.slotCallMulti(iter, 'next'); cx.b.br(contB, none); cx.b.switchTo(idleB); let markB = cx.b.newBlock(); let isRunning = cx.b.binary(IrOp.i32_eq, i32vt, s, cx.b.constI32(STATE_RUNNING, i32vt)); cx.b.brIf(isRunning, contB, none, markB, none); cx.b.switchTo(markB); let setDone = growable([g, cx.b.constI32(STATE_DONE, i32vt)]); cx.b.emitVoid(IrOp.struct_set, cx.b.pushExtra(setDone), stateRef); cx.b.br(contB, none); cx.b.switchTo(contB); } export function lowerGeneratorRamp(wasm: WasmModule, func: WasmFunction): IrBody { if (let (true, art) = rampBodies.get(func.uid)) { return art.rampBody; } throw new Error('generator was not prepared (split pass did not run): ' + funcDisplayName(func)); } export function lowerGeneratorNext(wasm: WasmModule, func: WasmFunction): IrBody { if (let (true, art) = nextBodies.get(func.uid)) { return art.nextBody; } throw new Error('generator next() was not prepared: ' + funcDisplayName(func)); } function prepareOne( wasm: WasmModule, pass: ReachabilityAnalysis, func: WasmFunction, funcIndex: i32 ): void { // Generator closures need no special handling: the context struct // ref arrives as param 0 of the implementation function (the ramp), // gets spilled to a frame field like every other param, and capture // reads in the body go through it; mutable captures are heap cells, // so mutation is shared between the generator and its enclosing // scope (and between sibling iterators) through the cell. // The Iterator instantiation and its wasm-side structs. let iface = iteratorInstantiationOf(wasm, func); pass.typeLowerer.discoverType(iface as Type, func.model); let iKey = getInterfaceKey(iface); if (!wasm.interfaceStructs.has(iKey) || !wasm.interfaceVTableStructs.has(iKey)) { throw new Error('generator Iterator instantiation was not materialized: ' + funcDisplayName(func)); } let fatPtr = wasm.interfaceStructs[iKey]; let vst = wasm.interfaceVTableStructs[iKey]; let slotSig = getInterfaceMemberSignature(wasm, iface, 'next'); // Two protocol shapes: the boolean two-arm form (flag, value) and the // three-arm Step (discriminant, value, future). A `gen` produces only // Done and Ready, so under Step it fills the future lane with a // default (null) on every step (async-iteration.md, "a `gen` produces // only Done and Ready"). An unboxed tuple value is several results. let stepValue = stepValueOf(wasm, iface, func); let lanes = stepValue.lanes(); if ((slotSig.returns.length != 1 + lanes && slotSig.returns.length != 2 + lanes) || !(slotSig.returns[0] is ValTypeI32)) { throw new Error('unexpected Iterator.next result shape for generator: ' + funcDisplayName(func)); } // Presplit lowering: the body as an ordinary CFG with yield_ // terminators. A bail inside a generator body is a hard error // (ZirUnsupported propagates; there is no fallback backend). let fl = new FunctionLowerer(wasm, func); fl.presplitGenerator = true; let yieldStruct = stepValue.struct; fl.presplitYieldVt = if (yieldStruct != null) { new ValTypeRef(yieldStruct) as ValType } else { slotSig.returns[1] }; let presplit = fl.lower(); let cfg = new IrCfg(presplit); // Suspension analysis on the pristine CFG: yields (in block order), // dispatch targets, spill set. let yieldBlocks = new Array(); let resumeOf = new Array(); var bi = 0; while (bi < presplit.blocks.length) { let insts = presplit.blocks[bi].insts; if (insts.length > 0) { let term = insts[insts.length - 1]; if (presplit.op(term) == IrOp.yield_) { yieldBlocks.push(bi); resumeOf.push(presplit.extra[presplit.successorRecord(term, 0)]); } } bi += 1; } // pc assignment: resume blocks get their suspend-state value; // yield-containing loop headers get values above the suspend range. let pcOfBlock = new Map(); var yi = 0; while (yi < resumeOf.length) { pcOfBlock[resumeOf[yi]] = STATE_FIRST_SUSPEND + yi; yi += 1; } var nextPc = STATE_FIRST_SUSPEND + resumeOf.length; // Headers of natural loops containing a yield, ascending block id. var hb = 0; while (hb < presplit.blocks.length) { if (cfg.isReachable(hb) && !pcOfBlock.has(hb) && hb != 0 && loopContainsSuspend(presplit, cfg, hb, yieldBlocks)) { pcOfBlock[hb] = nextPc; nextPc += 1; } hb += 1; } nextPc = addRegionMergeTargets(presplit, cfg, pcOfBlock, nextPc); // Which user try regions enclose each dispatch target, so the // dispatcher can re-enter them (generators.md §6, async.md §6). let dispatchRegions = dispatchRegionsOf(presplit, cfg, pcOfBlock); let liveIn = computeLiveIn(presplit, cfg); // Spill set: everything live into a dispatch target, every dispatch // target's block params, and every function parameter (the ramp // stores them all; unused fields cost a few bytes). let spilled = new Set(); let entryParamIds = new Array(); for (let p in presplit.blocks[0].params) { entryParamIds.push(p); spilled.add(p); } let dTargets = growable([0]); var db = 0; while (db < presplit.blocks.length) { if (pcOfBlock.has(db)) { dTargets.push(db); for (let v in liveIn[db]) { spilled.add(v); } for (let p in presplit.blocks[db].params) { spilled.add(p); } } db += 1; } for (let v in liveIn[0]) { spilled.add(v); } spillCatchLiveIns(liveIn, dispatchRegions, spilled); // The frame struct: $state plus one nullable-weakened field per // spilled value, ascending value id (deterministic layout). With // disposal active the frame subtypes the shared $GenFrame shape, so // $disposing sits right after $state, matching the supertype's // field prefix. let disposal = wasm.generatorDisposalActive; let fields = growable([ new WasmField('$state', new ValTypeI32(), true), ]); if (disposal) { fields.push(new WasmField('$disposing', new ValTypeI32(), true)); } var vid = 0; while (vid < presplit.instCount()) { if (spilled.has(vid)) { let vt = presplit.resultType(vid); if (vt == null) { throw new Error('generator spill of valueless instruction'); } fields.push(new WasmField('$v' + i32ToString(vid), weakenToNullable(vt), true)); } vid += 1; } varFieldsOf(presplit, fields); let frameName = `${funcDisplayName(func)}$${i32ToString(funcIndex)}$Frame`; let frame = new WasmStruct(frameName, fields); if (disposal) { frame.superStruct = wasm.generatorFrameSuper; } wasm.types.push(frame); pass.markTypeReached(frame); // next(): (ref null $Frame) -> Iterator.next's scalarized results. let nextParams = growable([new ValTypeRefNull(frame)]); let nextSig = wasm.getSignature(nextParams, slotSig.returns); let nextFunc = new WasmFunction(nextSig, null, func.model); nextFunc.name = frameName + '.next'; nextFunc.isGeneratorNext = true; wasm.addFunction(nextFunc); pass.markFunctionReached(nextFunc); // Iterator vtable global for the frame: trampoline per slot, // mirroring RTA's class-interface vtable construction. let frameKey = frameName as ClassKey; let methods = new Array(); for (let field in vst.fields) { if ((field.name as String) != 'next') { throw new Error('unexpected Iterator vtable member for generator: ' + (field.name as String)); } let tramp = new WasmFunction(slotSig, null, func.model); tramp.name = getInterfaceTrampolineName(frameKey, iKey, 'next'); tramp.interfaceTrampolineTarget = nextFunc; wasm.addFunction(tramp); pass.markFunctionReached(tramp); methods.push(tramp); } let vtableInit = new VTableInit(vst, methods); let viName = getClassInterfaceVTableName(frameKey, iKey); let vtableGlobal = new WasmGlobal( viName, viName, new ValTypeRef(vst), false, null, vtableInit, func.model ); wasm.globals.push(vtableGlobal); wasm.classInterfaceVTables[getClassInterfaceKey(frameKey, iKey)] = vtableGlobal; wasm.usedInterfaceAdaptations.add(getClassInterfaceKey(frameKey, iKey)); // The two bodies. let rampBody = buildRamp(func, frame, fatPtr, vtableGlobal, entryParamIds); let nextBody = buildNextBody(presplit, cfg, frame, spilled, pcOfBlock, dTargets, slotSig, stepValue, resumeOf, dispatchRegions, if (disposal) wasm.cancellationTag else null); let artifacts = new GeneratorArtifacts(rampBody, nextBody); func.isGeneratorRamp = true; rampBodies[func.uid] = artifacts; nextBodies[nextFunc.uid] = artifacts; } /** * Does the natural loop of header h (any backedge into h) contain a * suspension? Shared by both split passes — `suspendBlocks` holds the * yield_ blocks for generators and the await_ blocks for async. */ export function loopContainsSuspend( body: IrBody, cfg: IrCfg, h: i32, suspendBlocks: GrowableArray ): boolean { if (suspendBlocks.length == 0) { return false; } // Collect the natural loop: h plus every block reaching a backedge // source without passing through h. let inLoop = new Set(); inLoop.add(h); let work = new Array(); for (var pK = 0; pK < cfg.predCount(h); pK += 1) { let p = cfg.pred(h, pK); if (cfg.isReachable(p) && cfg.dominates(h, p)) { if (!inLoop.has(p)) { inLoop.add(p); work.push(p); } } } if (work.length == 0 && inLoop.size == 1) { return false; } while (work.length > 0) { let b = work.pop(); for (var pK = 0; pK < cfg.predCount(b); pK += 1) { let p = cfg.pred(b, pK); if (cfg.isReachable(p) && !inLoop.has(p)) { inLoop.add(p); work.push(p); } } } for (let sb in suspendBlocks) { if (inLoop.has(sb)) { return true; } } return false; } export function weakenToNullable(vt: ValType): ValType { return if (let ValTypeRef {target} = vt) new ValTypeRefNull(target) else vt; } /** ramp: allocate the frame, spill the arguments, pack, return. */ function buildRamp( func: WasmFunction, frame: WasmStruct, fatPtr: WasmStruct, vtableGlobal: WasmGlobal, entryParamIds: GrowableArray ): IrBody { let b = new IrBuilder(); let entry = b.newBlock(); let params = new Array(); for (let vt in func.signature.params) { params.push(b.blockParam(entry, vt)); } b.switchTo(entry); let typeRef = b.addRef(new IrRefType(frame)); let inst = b.emit(IrOp.struct_new_default, new ValTypeRef(frame), -1, typeRef); // $state defaults to 0 == START via struct.new_default. var i = 0; while (i < params.length) { let fieldRef = b.addRef(new IrRefField(frame, '$v' + i32ToString(entryParamIds[i]))); let pair = growable([inst, params[i]]); b.emitVoid(IrOp.struct_set, b.pushExtra(pair), fieldRef); i += 1; } let packed = b.emit(IrOp.iface_pack, new ValTypeRef(fatPtr), inst, b.addRef(new IrRefGlobal(vtableGlobal))); b.ret(packed); return b.finish(); } // --------------------------------------------------------------------------- // The state-machine transform: mutates the presplit body in place into // the next() body. // --------------------------------------------------------------------------- function buildNextBody( body: IrBody, cfg: IrCfg, frame: WasmStruct, spilled: HashSet, pcOfBlockIn: HashMap, dTargetsIn: GrowableArray, slotSig: WasmSignature, stepValue: StepValue, resumeOf: GrowableArray, dispatchRegions: HashMap>, cancelTag: WasmTag | null ): IrBody { // Whether the step carries a future result after its value results. let hasFuture = slotSig.returns.length == 2 + stepValue.lanes(); let futureVt = slotSig.returns[slotSig.returns.length - 1]; let origCount = body.blocks.length; let stateRef = addRawRef(body, new IrRefField(frame, '$state')); let i32Vt: ValType = new ValTypeI32(); // Snapshot the dispatch targets' params (cleared below; edges into // them turn into frame stores). let dParams = new Map>(); for (let d in dTargetsIn) { let copy = new Array(); for (let p in body.blocks[d].params) { copy.push(p); } dParams[d] = copy; } // 1. Evacuate the old entry into a fresh block E; block 0 becomes // the prologue head (the function's real entry: one frame param). let entryCopy = new IrBlock(); let oldEntry = body.blocks[0]; body.blocks.push(entryCopy); let entryCopyId = body.blocks.length - 1; for (let p in oldEntry.params) { entryCopy.params.push(p); body.instBlock[p] = entryCopyId; } for (let inst in oldEntry.insts) { entryCopy.insts.push(inst); body.instBlock[inst] = entryCopyId; } body.blocks[0] = new IrBlock(); // Dispatch-target bookkeeping with entry remapped to its new id. let pcOfBlock: HashMap = {entryCopyId => 0}; for (let d in dTargetsIn) { if (d == 0) { continue; } pcOfBlock[d] = pcOfBlockIn[d]; } let dParamsById = new Map>(); for (let d in dTargetsIn) { let mapped = if (d == 0) { entryCopyId } else { d }; dParamsById[mapped] = dParams[d]; } // 2. Prologue: state checks, RUNNING store, dispatcher loop. let frameParam = rawParam(body, 0, new ValTypeRefNull(frame)); let newBlockId = () => { body.blocks.push(new IrBlock()); return body.blocks.length - 1; }; let doneBlock = newBlockId(); let runCheckBlock = newBlockId(); let trapBlock = newBlockId(); let enterBlock = newBlockId(); let dispatcher = newBlockId(); let emitIn = (blockId: i32, op: IrOp, typeIdx: i32, a: i32, b: i32) => { let inst = rawInst(body, op, typeIdx, a, b); placeInst(body, blockId, inst); return inst; }; let brTo = (fromBlock: i32, target: i32, args: GrowableArray) => { let idx = body.extra.length; body.extra.push(target); body.extra.push(args.length); for (let v in args) { body.extra.push(v); } let inst = rawInst(body, IrOp.br, -1, idx, -1); placeInst(body, fromBlock, inst); }; let brIfTo = (fromBlock: i32, cond: i32, thenTarget: i32, elseTarget: i32) => { let idx = body.extra.length; body.extra.push(thenTarget); body.extra.push(0); body.extra.push(elseTarget); body.extra.push(0); let inst = rawInst(body, IrOp.br_if, -1, cond, idx); placeInst(body, fromBlock, inst); }; let storeState = (blockId: i32, valueInst: i32) => { let idx = body.extra.length; body.extra.push(frameParam); body.extra.push(valueInst); let inst = rawInst(body, IrOp.struct_set, -1, idx, stateRef); placeInst(body, blockId, inst); }; let i32Idx = internVt(body, i32Vt); // With disposal active, block 0 enters a cancellation region whose // body is the whole state machine (mirroring async's cancel-capture // nesting): the disposal raise at a resume head unwinds through the // re-entered user regions — their finalizers run — and lands here, // where the frame is marked DONE. Every suspension and completion // RETURNS from inside the region; the one branch out (the DONE // check's exit) is a return block dominated by the region head. var headBlock = 0; var cancelCatchB = -1; var disposingRef = -1; var cancelTagRef = -1; if (cancelTag != null) { headBlock = newBlockId(); cancelCatchB = newBlockId(); disposingRef = addRawRef(body, new IrRefField(frame, '$disposing')); cancelTagRef = addRawRef(body, new IrRefTag(cancelTag)); let cIdx = body.extra.length; body.extra.push(headBlock); body.extra.push(0); body.extra.push(cancelCatchB); body.extra.push(0); let cInst = rawInst(body, IrOp.try_br, -1, cancelTagRef, cIdx); placeInst(body, 0, cInst); } // head: state = frame.$state; state == DONE ? let stateVal = emitIn(headBlock, IrOp.struct_get, i32Idx, frameParam, stateRef); let doneConst = emitIn(headBlock, IrOp.const_i32, i32Idx, STATE_DONE, -1); let isDone = emitIn(headBlock, IrOp.i32_eq, i32Idx, stateVal, doneConst); brIfTo(headBlock, isDone, doneBlock, runCheckBlock); // done: politely exhausted forever: (false, default). let doneFlag = emitIn(doneBlock, IrOp.const_i32, i32Idx, 0, -1); let doneLanes = rawValueLanes(body, slotSig.returns, stepValue, -1); for (let lane in doneLanes) { placeInst(body, doneBlock, lane); } var doneFut = -1; if (hasFuture) { doneFut = rawDefaultOf(body, futureVt); placeInst(body, doneBlock, doneFut); } let doneExtra = rawStepResults(body, doneFlag, doneLanes, doneFut); let doneRet = rawInst(body, IrOp.ret_multi, -1, doneExtra, -1); placeInst(body, doneBlock, doneRet); // runCheck: state == RUNNING ? trap : enter. let runConst = emitIn(runCheckBlock, IrOp.const_i32, i32Idx, STATE_RUNNING, -1); let isRunning = emitIn(runCheckBlock, IrOp.i32_eq, i32Idx, stateVal, runConst); brIfTo(runCheckBlock, isRunning, trapBlock, enterBlock); // trap: reentrancy or resume-after-throw (poison state). let trapInst = rawInst(body, IrOp.unreachable, -1, -1, -1); placeInst(body, trapBlock, trapInst); // cancel catch: a cancellation unwound the body, its finalizers // already run by the re-entered regions' handlers. Mark the frame // exhausted either way. A DISPOSAL raise ends here — the disposer // asked for exactly this — so it returns (false, default); any // other cancellation is just passing through sync code and // continues to the caller. if (cancelTag != null) { let dv = emitIn(cancelCatchB, IrOp.struct_get, i32Idx, frameParam, disposingRef); let ccDone = emitIn(cancelCatchB, IrOp.const_i32, i32Idx, STATE_DONE, -1); storeState(cancelCatchB, ccDone); let cancelDoneB = newBlockId(); let rethrowB = newBlockId(); brIfTo(cancelCatchB, dv, cancelDoneB, rethrowB); let cdFlag = emitIn(cancelDoneB, IrOp.const_i32, i32Idx, 0, -1); let cdLanes = rawValueLanes(body, slotSig.returns, stepValue, -1); for (let lane in cdLanes) { placeInst(body, cancelDoneB, lane); } var cdFut = -1; if (hasFuture) { cdFut = rawDefaultOf(body, futureVt); placeInst(body, cancelDoneB, cdFut); } let cdExtra = rawStepResults(body, cdFlag, cdLanes, cdFut); let cdRet = rawInst(body, IrOp.ret_multi, -1, cdExtra, -1); placeInst(body, cancelDoneB, cdRet); let rtIdx = body.extra.length; body.extra.push(0); let rtInst = rawInst(body, IrOp.throw, -1, rtIdx, cancelTagRef); placeInst(body, rethrowB, rtInst); } // enter: $state = RUNNING; dispatch on the saved state. let runningConst = emitIn(enterBlock, IrOp.const_i32, i32Idx, STATE_RUNNING, -1); storeState(enterBlock, runningConst); let dispatchArgs = growable([stateVal]); brTo(enterBlock, dispatcher, dispatchArgs); /** * Re-enters the user `try` regions enclosing a dispatch target, and * returns the block the dispatcher should branch to (generators.md * §6; the construction and its rationale are async.md §6). * * The dispatcher lives outside every user region, so branching * straight at the target would leave the segment it heads * unprotected: the region silently shrinks to exclude it, and a * `throw` there sails past the handler the source wrote. Each * enclosing region is instead re-entered through a fresh `try_br` * whose catch is that region's own handler, innermost last. */ let reenterRegions = (dispatchTarget: i32, entry: i32) => { // Regions are keyed by the ORIGINAL dispatch target; `entry` is // what the chain actually branches to — the target itself, or the // disposal check block prefixed in front of it, which must sit // inside the same regions so its raise runs their finalizers. let regions = if (let (true, rs) = dispatchRegions.get(dispatchTarget)) rs else new Array(0); var target = entry; // Innermost first, so the outermost try_br ends up on the outside. var ri = regions.length - 1; while (ri >= 0) { let r = regions[ri]; let t = newBlockId(); let idx = body.extra.length; body.extra.push(target); body.extra.push(0); body.extra.push(r.catchTarget); body.extra.push(0); let inst = rawInst(body, IrOp.try_br, -1, r.tagRef, idx); placeInst(body, t, inst); // The fresh region ends where the original did: without this, a // join dominated by the dispatch target would be placed inside // the re-entered try_table (issue #426). if (r.joinTarget >= 0) { body.tryJoin[inst] = r.joinTarget; } target = t; ri -= 1; } return target; }; // dispatcher(pc): br_if chain over the dispatch targets, ascending // pc. The final fall-through is an invalid state — trap. let pcParam = rawParam(body, dispatcher, i32Vt); let chainTargets = new Array(); let chainPcs = new Array(); chainTargets.push(reenterRegions(entryCopyId, entryCopyId)); chainPcs.push(0); var scanPc = STATE_FIRST_SUSPEND; var remaining = pcOfBlock.size - 1; while (remaining > 0) { var found = -1; var fb = 0; while (fb < body.blocks.length) { if (pcOfBlock.has(fb) && pcOfBlock[fb] == scanPc) { found = fb; break; } fb += 1; } if (found >= 0) { // Disposal delivery: a resume head first tests the frame's // $disposing flag and raises on the cancellation channel when // it is set. The check block sits INSIDE the re-entered user // regions, so the raise unwinds through the finalizers the // suspended yield was under — that is the disposal contract // (docs/design/cancellation.md, "Abandonment and generator // disposal"). Only genuine resume points get the check: loop // headers are mid-execution re-entries, and pc 0 is the start. var target = found; if (cancelTag != null && scanPc < STATE_FIRST_SUSPEND + resumeOf.length) { let checkB = newBlockId(); // One raise block per check, so each stays dominated by its // check and the stackifier keeps it inside that region nest — // a shared raise block would be placed outside them all and // the throw would skip the finalizers. let raiseB = newBlockId(); let dv = emitIn(checkB, IrOp.struct_get, i32Idx, frameParam, disposingRef); brIfTo(checkB, dv, raiseB, found); let rIdx = body.extra.length; body.extra.push(0); let rInst = rawInst(body, IrOp.throw, -1, rIdx, cancelTagRef); placeInst(body, raiseB, rInst); target = checkB; } chainTargets.push(reenterRegions(found, target)); chainPcs.push(scanPc); remaining -= 1; } scanPc += 1; } var chainBlock = dispatcher; var ci = 0; while (ci < chainTargets.length) { let cmpConst = emitIn(chainBlock, IrOp.const_i32, i32Idx, chainPcs[ci], -1); let cmp = emitIn(chainBlock, IrOp.i32_eq, i32Idx, pcParam, cmpConst); let elseBlock = if (ci == chainTargets.length - 1) { trapBlock } else { newBlockId() }; brIfTo(chainBlock, cmp, chainTargets[ci], elseBlock); chainBlock = elseBlock; ci += 1; } // The body blocks the remaining passes operate on. let bodyBlocks = growable([entryCopyId]); var obi = 1; while (obi < origCount) { bodyBlocks.push(obi); obi += 1; } // 3. Reroute every edge into a dispatch target through the // dispatcher, converting its branch args into frame stores. for (let blockId in bodyBlocks) { rerouteEdges(body, blockId, pcOfBlock, dParamsById, dispatcher, frameParam, frame, i32Idx, entryCopyId); } // Dispatch targets no longer take params (their values now flow // through frame fields; the loads are inserted by the use pass). for (let d in dTargetsIn) { let mapped = if (d == 0) { entryCopyId } else { d }; truncate(body.blocks[mapped].params); } // 4. Store every spilled definition to its frame field. let skipRemap = new Set(); for (let blockId in bodyBlocks) { let block = body.blocks[blockId]; let rebuilt = new Array(); // Spilled params of non-dispatch blocks: store at block top. for (let p in block.params) { if (spilled.has(p)) { let idx = body.extra.length; body.extra.push(frameParam); body.extra.push(p); let st = rawInst(body, IrOp.struct_set, -1, idx, addRawRef(body, new IrRefField(frame, '$v' + i32ToString(p)))); skipRemap.add(st); rebuilt.push(st); body.instBlock[st] = blockId; } } for (let inst in block.insts) { rebuilt.push(inst); if (spilled.has(inst) && !isIrTerminator(body.op(inst))) { let idx = body.extra.length; body.extra.push(frameParam); body.extra.push(inst); let st = rawInst(body, IrOp.struct_set, -1, idx, addRawRef(body, new IrRefField(frame, '$v' + i32ToString(inst)))); skipRemap.add(st); rebuilt.push(st); body.instBlock[st] = blockId; } } replaceContents(block.insts, rebuilt); } // 5. Load every use of a spilled value from its frame field, // immediately before the use (correct on every dispatch path; GVN // never merges struct_gets, so resumes reload). for (let blockId in bodyBlocks) { let block = body.blocks[blockId]; let rebuilt = new Array(); let ops = new Array(); for (let inst in block.insts) { if (skipRemap.has(inst)) { rebuilt.push(inst); continue; } truncate(ops); body.appendValueOperands(inst, ops); let loadOf = new Map(); for (let v in ops) { if (spilled.has(v) && !loadOf.has(v)) { let vt = body.resultType(v) as ValType; let weak = weakenToNullable(vt); var load = rawInst(body, IrOp.struct_get, internVt(body, weak), frameParam, addRawRef(body, new IrRefField(frame, '$v' + i32ToString(v)))); rebuilt.push(load); body.instBlock[load] = blockId; if (!valTypesStrictlyEqual(weak, vt)) { load = rawInst(body, IrOp.ref_as_non_null, internVt(body, vt), load, -1); rebuilt.push(load); body.instBlock[load] = blockId; } loadOf[v] = load; } } if (loadOf.size > 0) { body.rewriteValueOperands(inst, (v) => { if (let (true, l) = loadOf.get(v)) { return l; } return v; }); } rebuilt.push(inst); } replaceContents(block.insts, rebuilt); } // 6. Rewrite suspensions and completions. slotSig.returns[0]; var yieldIndex = 0; for (let blockId in bodyBlocks) { let block = body.blocks[blockId]; if (block.insts.length == 0) { continue; } let term = block.insts[block.insts.length - 1]; let op = body.op(term); if (op == IrOp.yield_) { let resumeTarget = body.extra[body.successorRecord(term, 0)]; let pc = pcOfBlock[resumeTarget]; let yieldVal = body.a[term]; let rebuilt = new Array(block.insts.length - 1); var k = 0; while (k < block.insts.length - 1) { rebuilt.push(block.insts[k]); k += 1; } let pcConst = rawInst(body, IrOp.const_i32, i32Idx, pc, -1); rebuilt.push(pcConst); body.instBlock[pcConst] = blockId; let idx = body.extra.length; body.extra.push(frameParam); body.extra.push(pcConst); let st = rawInst(body, IrOp.struct_set, -1, idx, stateRef); rebuilt.push(st); body.instBlock[st] = blockId; let flag = rawInst(body, IrOp.const_i32, i32Idx, 1, -1); rebuilt.push(flag); body.instBlock[flag] = blockId; let yLanes = rawValueLanes(body, slotSig.returns, stepValue, yieldVal); for (let lane in yLanes) { if (body.instBlock[lane] < 0) { rebuilt.push(lane); body.instBlock[lane] = blockId; } } var yFut = -1; if (hasFuture) { yFut = rawDefaultOf(body, futureVt); rebuilt.push(yFut); body.instBlock[yFut] = blockId; } let retIdx = rawStepResults(body, flag, yLanes, yFut); body.opcode[term] = IrOp.ret_multi as i32; body.a[term] = retIdx; body.b[term] = -1; rebuilt.push(term); replaceContents(block.insts, rebuilt); yieldIndex += 1; } else if (op == IrOp.ret) { // Bare return / fell off the end: DONE forever. let rebuilt = new Array(block.insts.length - 1); var k = 0; while (k < block.insts.length - 1) { rebuilt.push(block.insts[k]); k += 1; } let doneC = rawInst(body, IrOp.const_i32, i32Idx, STATE_DONE, -1); rebuilt.push(doneC); body.instBlock[doneC] = blockId; let idx = body.extra.length; body.extra.push(frameParam); body.extra.push(doneC); let st = rawInst(body, IrOp.struct_set, -1, idx, stateRef); rebuilt.push(st); body.instBlock[st] = blockId; let flag = rawInst(body, IrOp.const_i32, i32Idx, 0, -1); rebuilt.push(flag); body.instBlock[flag] = blockId; let rLanes = rawValueLanes(body, slotSig.returns, stepValue, -1); for (let lane in rLanes) { rebuilt.push(lane); body.instBlock[lane] = blockId; } var rFut = -1; if (hasFuture) { rFut = rawDefaultOf(body, futureVt); rebuilt.push(rFut); body.instBlock[rFut] = blockId; } let retIdx = rawStepResults(body, flag, rLanes, rFut); body.opcode[term] = IrOp.ret_multi as i32; body.a[term] = retIdx; body.b[term] = -1; rebuilt.push(term); replaceContents(block.insts, rebuilt); } } // Mutable variables move into the frame; their wasm locals would not // survive a suspension. rewriteVarsToFrame(body, bodyBlocks, frame, frameParam); return body; } /** * Rewrites the terminator of `blockId` so every successor that is a * dispatch target branches to the dispatcher with that target's pc, * spilling the edge's branch args into the target's param fields. */ export function rerouteEdges( body: IrBody, blockId: i32, pcOfBlock: HashMap, dParamsById: HashMap>, dispatcher: i32, frameParam: i32, frame: WasmStruct, i32Idx: i32, entryCopyId: i32 ): void { let block = body.blocks[blockId]; if (block.insts.length == 0) { return; } let term = block.insts[block.insts.length - 1]; let op = body.op(term); if (op == IrOp.ret || op == IrOp.ret_multi || op == IrOp.throw || op == IrOp.unreachable || op == IrOp.yield_ || op == IrOp.await_) { // yield_/await_ successors are resume blocks; the suspension // rewrite replaces the terminator wholesale, so no reroute is // needed. return; } // Decode all successors up front (re-encoding appends to extra). let succs = body.successors(term); var touchesDispatch = false; let targets = new Array(); let argLists = new Array>(); for (let s in succs) { var target = s.target; if (target == 0) { target = entryCopyId; } let args = new Array(s.argCount); var ai = 0; while (ai < s.argCount) { args.push(body.extra[s.argStart + ai]); ai += 1; } targets.push(target); argLists.push(args); if (pcOfBlock.has(target)) { touchesDispatch = true; } } if (!touchesDispatch) { return; } if (op == IrOp.try_br || op == IrOp.br_table) { throw new Error('suspension split: unsupported terminator shape into a resume point'); } // Inserted instructions go right before the terminator. let inserted = new Array(); var si = 0; while (si < targets.length) { let target = targets[si]; if (pcOfBlock.has(target)) { // Spill the edge args into the target's (former) param fields. let tps = dParamsById[target]; let args = argLists[si]; if (tps.length != args.length) { throw new Error('suspension split: edge arity mismatch at resume point'); } var pi = 0; while (pi < tps.length) { let idx = body.extra.length; body.extra.push(frameParam); body.extra.push(args[pi]); let st = rawInst(body, IrOp.struct_set, -1, idx, addRawRef(body, new IrRefField(frame, '$v' + i32ToString(tps[pi])))); inserted.push(st); body.instBlock[st] = blockId; pi += 1; } let pcConst = rawInst(body, IrOp.const_i32, i32Idx, pcOfBlock[target], -1); inserted.push(pcConst); body.instBlock[pcConst] = blockId; targets[si] = dispatcher; let newArgs = growable([pcConst]); argLists[si] = newArgs; } si += 1; } // Re-encode the successor records at the end of extra. if (op == IrOp.br) { let idx = body.extra.length; body.extra.push(targets[0]); body.extra.push(argLists[0].length); for (let v in argLists[0]) { body.extra.push(v); } body.a[term] = idx; } else if (op == IrOp.br_if) { let idx = body.extra.length; var ti = 0; while (ti < 2) { body.extra.push(targets[ti]); body.extra.push(argLists[ti].length); for (let v in argLists[ti]) { body.extra.push(v); } ti += 1; } body.b[term] = idx; } else if (op == IrOp.br_on_cast || op == IrOp.br_on_cast_fail) { let typePrefix = body.extra[body.b[term]]; let idx = body.extra.length; body.extra.push(typePrefix); var ti = 0; while (ti < 2) { body.extra.push(targets[ti]); body.extra.push(argLists[ti].length); for (let v in argLists[ti]) { body.extra.push(v); } ti += 1; } body.b[term] = idx; } else { throw new Error('suspension split: unhandled terminator during reroute'); } // Place the inserted spills/consts before the terminator. if (inserted.length > 0) { let rebuilt = new Array(block.insts.length - 1); var k = 0; while (k < block.insts.length - 1) { rebuilt.push(block.insts[k]); k += 1; } for (let inst in inserted) { rebuilt.push(inst); } rebuilt.push(term); replaceContents(block.insts, rebuilt); } }