compiler 0.0.2-preview.1

The Zena self-hosted compiler

Readme Files Dependencies Versions

compiler#

The Zena compiler, written in Zena. It parses, type-checks, and compiles Zena source code to WebAssembly (Wasm GC) and WebAssembly Text (WAT).

Usage#

Parsing a Single File#

Use compiler/parser to parse Zena source text into an AST (Module):

import { parse } from 'compiler/parser';

let ast = parse('export let answer = 42;', 'example.zena');

Loading and Checking a Program#

Use compiler (createCompiler and checkCompilation) with a CompilerHost to resolve imports across a module graph and type-check a program:

import {
  createCompiler, checkCompilation, buildStdlibConfig
} from 'compiler';
import { FsCompilerHost } from 'compiler/fs-host';

let stdlibRoot = '/stdlib';
let host = new FsCompilerHost(stdlibRoot);
let packages = buildStdlibConfig(stdlibRoot, 'host');
let compiler = createCompiler(host, {
  stdlibRoot,
  packages,
});

let result = await compiler.compile({
  entry: '/workspace/main.zena',
  target: 'host',
});
let checked = checkCompilation(result);

Compiling a File to WebAssembly#

Use compiler/compile-file to compile an entry file on disk to a .wasm or .wat output file:

import { compileFile } from 'compiler/compile-file';

let ok = await compileFile({
  entry: 'src/main.zena',
  outPath: 'out/main.wasm',
  stdlibRoot: '/stdlib',
});

Libraries#

  • compiler / compiler/compiler — compiler entry point (Compiler, createCompiler, checkCompilation, ProgramCheckResult)
  • compiler/compile-file — end-to-end file compilation (compileFile, CompileFileOptions)
  • compiler/tokenizer — lexer and token definitions (tokenize, Token, TokenType)
  • compiler/parser — recursive-descent parser (parse, Parser)
  • compiler/ast — AST node definitions (Node, Module, Statement, Expression, TypeAnnotation)
  • compiler/visitor — AST traversal helpers (walk, Visitor)
  • compiler/scope — lexical scope and symbol resolution (ScopeBuilder, ScopeResult, Symbol)
  • compiler/checker — static type checker (checkModule, CheckResult)
  • compiler/semantic-model — semantic queries over a checked module (SemanticModel)
  • compiler/types — compiler type representations (Type, ClassType, FunctionType, typeToString)
  • compiler/diagnostics — compiler diagnostics and source spans (Diagnostic, DiagnosticCode, DiagnosticSeverity, SourceSpan)
  • compiler/package-manifest — zena-package.json manifest and workspace loader (loadWorkspace, loadPackageMap)
  • compiler/module-resolver — package and relative module specifier resolution (ModuleResolver, PackageConfig)
  • compiler/library-loader — module graph loader (LibraryLoader, CompilerHost, SourceFile)
  • compiler/codegen/binary-generator — WebAssembly GC binary emitter (BinaryGenerator)
  • compiler/codegen/wat-generator — WebAssembly Text (WAT) emitter (WatGenerator)

License#

MIT

62.6 KiB Raw
/**
 * 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<T> 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<T> 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<i32, GeneratorArtifacts>();
var nextBodies = new Map<i32, GeneratorArtifacts>();

/**
 * 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<T> (or AsyncIterator<T>) 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<Iterator<T>>; 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<T>: ' +
        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<i32>): 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<TryRegion> {
  let regions = new Array<TryRegion>();
  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<TryRegion>,
  block: i32
): GrowableArray<TryRegion> {
  let hits = new Array<TryRegion>();
  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<i32, i32>
): HashMap<i32, GrowableArray<TryRegion>> {
  let regions = collectTryRegions(body);
  let out = new Map<i32, GrowableArray<TryRegion>>();
  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<i32, i32>,
  nextPcIn: i32
): i32 {
  let regions = collectTryRegions(body);
  if (regions.length == 0) {
    return nextPcIn;
  }
  let n = body.blocks.length;
  let tryTargets = new Set<i32>();
  for (let r in regions) {
    tryTargets.add(r.bodyTarget);
    tryTargets.add(r.catchTarget);
  }
  let enclosed = new Array<boolean>(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<i32>(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<HashSet<i32>>,
  dispatchRegions: HashMap<i32, GrowableArray<TryRegion>>,
  spilled: HashSet<i32>
): 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<WasmField>): 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<i32>,
  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<i32>();
    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<i32>, src: GrowableArray<i32>): 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<String>;

  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<String>());
  }
  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<String>();
  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<ValType>,
    sv: StepValue, value: i32): GrowableArray<i32> {
  let out = new Array<i32>();
  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<i32>, 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<HashSet<i32>> {
  let n = body.blocks.length;
  let uses = new Array<HashSet<i32>>(n);
  let defs = new Array<HashSet<i32>>(n);
  let liveIn = new Array<HashSet<i32>>(n);
  var bi = 0;
  while (bi < n) {
    let use = new Set<i32>();
    let def = new Set<i32>();
    let block = body.blocks[bi];
    for (let p in block.params) {
      def.add(p);
    }
    let ops = new Array<i32>();
    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<i32>());
    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<T> vtable global) must exist before indices lock.
 */
export function prepareGenerators(
  wasm: WasmModule,
  pass: ReachabilityAnalysis
): void {
  rampBodies = new Map<i32, GeneratorArtifacts>();
  nextBodies = new Map<i32, GeneratorArtifacts>();
  // 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<WasmField>([
      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<i32>();
  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<i32>([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<i32>([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<T> 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<i32>();
  let resumeOf = new Array<i32>();
  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<i32, i32>();
  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<i32>();
  let entryParamIds = new Array<i32>();
  for (let p in presplit.blocks[0].params) {
    entryParamIds.push(p);
    spilled.add(p);
  }
  let dTargets = growable<i32>([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<WasmField>([
    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<ValType>([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<T> vtable global for the frame: trampoline per slot,
  // mirroring RTA's class-interface vtable construction.
  let frameKey = frameName as ClassKey;
  let methods = new Array<WasmFunction>();
  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<i32>
): 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<i32>();
  inLoop.add(h);
  let work = new Array<i32>();
  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<i32>
): IrBody {
  let b = new IrBuilder();
  let entry = b.newBlock();
  let params = new Array<i32>();
  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<i32>([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<i32>,
  pcOfBlockIn: HashMap<i32, i32>,
  dTargetsIn: GrowableArray<i32>,
  slotSig: WasmSignature,
  stepValue: StepValue,
  resumeOf: GrowableArray<i32>,
  dispatchRegions: HashMap<i32, GrowableArray<TryRegion>>,
  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<i32, GrowableArray<i32>>();
  for (let d in dTargetsIn) {
    let copy = new Array<i32>();
    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<i32, i32> = {entryCopyId => 0};
  for (let d in dTargetsIn) {
    if (d == 0) {
      continue;
    }
    pcOfBlock[d] = pcOfBlockIn[d];
  }
  let dParamsById = new Map<i32, GrowableArray<i32>>();
  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<i32>) => {
    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<i32>([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<TryRegion>(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<i32>();
  let chainPcs = new Array<i32>();
  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<i32>([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<i32>();
  for (let blockId in bodyBlocks) {
    let block = body.blocks[blockId];
    let rebuilt = new Array<i32>();
    // 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<i32>();
    let ops = new Array<i32>();
    for (let inst in block.insts) {
      if (skipRemap.has(inst)) {
        rebuilt.push(inst);
        continue;
      }
      truncate(ops);
      body.appendValueOperands(inst, ops);
      let loadOf = new Map<i32, i32>();
      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<i32>(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<i32>(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<i32, i32>,
  dParamsById: HashMap<i32, GrowableArray<i32>>,
  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<i32>();
  let argLists = new Array<GrowableArray<i32>>();
  for (let s in succs) {
    var target = s.target;
    if (target == 0) {
      target = entryCopyId;
    }
    let args = new Array<i32>(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<i32>();
  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<i32>([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<i32>(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);
  }
}
VersionPublishedDependenciesApproved by
0.0.2-preview.1 2026-11-19