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

56.8 KiB Raw
/**
 * ZIR core data structures.
 *
 * See docs/design/ir.md. ZIR is a CFG-of-basic-blocks SSA IR with block
 * parameters instead of phi nodes. The encoding is data-oriented (§4):
 * instructions live in flat parallel i32 arrays indexed by instruction id,
 * and a value id IS the id of its defining instruction (block parameters
 * are `param` instructions, so the value namespace is uniform).
 *
 * Hot arrays hold only i32s. References to module entities (functions,
 * globals, struct types, fields, literals) are corralled into the small
 * per-function `refTable`; types go through `typeTable`. Instructions store
 * indices into those tables, never object references.
 *
 * Operand encoding conventions ("a"/"b" are the two inline operand slots;
 * "a -> [...]" means slot a holds an index into `extra` where the listed
 * items are stored consecutively):
 *
 *   nop, param, unreachable:  no operands
 *   const_i32:   a = the value itself
 *   const_i64:   a = index into constI64
 *   const_f32/const_f64: a = index into constF64
 *   unary ops:   a = operand value
 *   binary ops:  a, b = operand values
 *   ref_null:    no operands (result type = typeId)
 *   ref_test, ref_cast: a = value, b = target type (typeTable index)
 *   ref_func:    b = ref (function)
 *   str_lit:     b = ref (string literal)
 *   global_get:  b = ref (global)
 *   global_set:  a = value, b = ref (global)
 *   var_get:     b = var index (into varTypes)
 *   var_set:     a = value, b = var index
 *   struct_new:  a -> [argc, arg*],           b = ref (struct type)
 *   struct_get:  a = receiver,                b = ref (field)
 *   struct_set:  a -> [receiver, value],      b = ref (field)
 *   array_new:   a -> [length, init or -1],   b = ref (array type)
 *   array_new_data: a -> [offset, length, dataIndex], b = ref (array type)
 *   array_new_fixed: a -> [argc, arg*],       b = ref (array type)
 *   array_get:   a = array, b = index
 *   array_get_u: a = array, b = index  (zero-extending read of a packed element)
 *   array_get_s: a = array, b = index  (sign-extending read of a packed element)
 *   array_set:   a -> [array, index, value]
 *   array_copy:  a -> [dest, destOff, src, srcOff, len]
 *   array_len:   a = array
 *   iface_pack:  a = instance,                b = ref (vtable global);
 *                result type names the fat-pointer struct
 *   iface_vtable, iface_instance: a = fat pointer
 *   call:        a -> [argc, arg*],           b = ref (function)
 *   call_ref:    a -> [callee, argc, arg*]
 *   i64_mul_wide_s, i64_mul_wide_u: a = x, b = y (two i64 results)
 *   i64_add128, i64_sub128:
 *                a -> [lhsLo, lhsHi, rhsLo, rhsHi]  (two i64 results)
 *   mv_get:      a = multi-result producer value, b = result index
 *   ret_multi:   a -> [argc, value*]
 *   throw:       a -> [argc, arg*],           b = ref (tag) or -1
 *   try_br:      a = ref (exception tag),
 *                b -> [bodyTarget, argc, arg*, catchTarget, argc, arg*]
 *   br:          a -> [target, argc, arg*]
 *   br_if:       a = condition,
 *                b -> [thenTarget, thenArgc, arg*, elseTarget, elseArgc, arg*]
 *   br_on_cast, br_on_cast_fail:
 *                a = value,
 *                b -> [targetType (typeTable index),
 *                      okTarget, okArgc, arg*, failTarget, failArgc, arg*]
 *   br_table:    a = selector,
 *                b -> [count, (target, argc, arg*)*]  (last entry = default)
 *   simd_unary:  a = operand,                b = simd opcode
 *   simd_binary: a -> [x, y],                b = simd opcode
 *   simd_ternary: a -> [x, y, z],            b = simd opcode
 *   simd_extract_lane: a = vector,           b -> [opcode, lane]
 *   simd_replace_lane: a -> [vector, value], b -> [opcode, lane]
 *   simd_const:  no operands,                b -> [opcode, 16 bytes]
 *   simd_shuffle: a -> [x, y],               b -> [opcode, 16 lane selectors]
 *   simd_load:   a = addr,                   b -> [opcode, align]
 *   simd_store:  a -> [addr, value],         b -> [opcode, align]
 *   simd_load_lane, simd_store_lane:
 *                a -> [addr, vector],        b -> [opcode, align, lane]
 *   ret:         a = value, or -1 for void
 *   ret_call:     a -> [argc, arg*],          b = ref (function)
 *   ret_call_ref: a -> [callee, argc, arg*]
 *   yield_:      a = yielded value, b -> [target, argc, arg*]
 *   await_:      a = awaited future, b -> [target, argc, arg*]
 *                (both: presplit suspension bodies only — generator
 *                bodies for yield_, async bodies for await_ — and
 *                rewritten by the split pass, never emitted)
 *
 * A result type of -1 in `typeId` means the instruction produces no value.
 * Instruction and block ids are plain i32 indices for now; -1 means "none".
 */
import { Set } from 'zena:collections';
import { ValType, WasmType, WideArithOpcode } from '../wasm.zena';
import { WasmStruct, WasmFunction, WasmGlobal, WasmTag } from '../wasm-module.zena';

export enum IrOp {
  nop,
  param,
  const_i32,
  const_i64,
  const_f32,
  const_f64,
  // i32 arithmetic and comparison (1:1 with wasm)
  i32_add,
  i32_sub,
  i32_mul,
  i32_div_s,
  i32_rem_s,
  i32_and,
  i32_or,
  i32_xor,
  i32_shl,
  i32_shr_s,
  i32_shr_u,
  i32_eqz,
  i32_eq,
  i32_ne,
  i32_lt_s,
  i32_le_s,
  i32_gt_s,
  i32_ge_s,
  i32_div_u,
  i32_rem_u,
  i32_lt_u,
  i32_le_u,
  i32_gt_u,
  i32_ge_u,
  // i64
  i64_add,
  i64_sub,
  i64_mul,
  i64_div_s,
  i64_rem_s,
  i64_and,
  i64_or,
  i64_xor,
  i64_shl,
  i64_shr_s,
  i64_shr_u,
  i64_eq,
  i64_ne,
  i64_lt_s,
  i64_le_s,
  i64_gt_s,
  i64_ge_s,
  i64_div_u,
  i64_rem_u,
  i64_lt_u,
  i64_le_u,
  i64_gt_u,
  i64_ge_u,
  // f64
  f64_add,
  f64_sub,
  f64_mul,
  f64_div,
  f64_eq,
  f64_ne,
  f64_lt,
  f64_le,
  f64_gt,
  f64_ge,
  // f32
  f32_add,
  f32_sub,
  f32_mul,
  f32_div,
  f32_eq,
  f32_ne,
  f32_lt,
  f32_le,
  f32_gt,
  f32_ge,
  // unary numerics
  i64_eqz,
  f64_neg,
  f32_neg,
  // conversions
  i32_wrap_i64,
  i64_extend_i32_s,
  f64_convert_i32_s,
  f32_convert_i32_s,
  f64_convert_i64_s,
  f32_convert_i64_s,
  i32_trunc_sat_f64_s,
  i32_trunc_sat_f32_s,
  i64_trunc_sat_f64_s,
  i64_trunc_sat_f32_s,
  f64_promote_f32,
  f32_demote_f64,
  i64_reinterpret_f64,
  i32_reinterpret_f32,
  f32_reinterpret_i32,
  f64_reinterpret_i64,
  i32_trunc_sat_f32_u,
  i32_trunc_sat_f64_u,
  i64_trunc_sat_f32_u,
  i64_trunc_sat_f64_u,
  i64_extend_i32_u,
  f64_convert_i32_u,
  f32_convert_i32_u,
  f64_convert_i64_u,
  f32_convert_i64_u,
  i32_clz,
  i32_ctz,
  i32_popcnt,
  i64_clz,
  i64_ctz,
  i64_popcnt,
  f32_abs,
  f32_ceil,
  f32_floor,
  f32_nearest,
  f32_sqrt,
  f32_trunc,
  f64_abs,
  f64_ceil,
  f64_floor,
  f64_nearest,
  f64_sqrt,
  f64_trunc,
  f32_min,
  f32_max,
  f32_copysign,
  f64_min,
  f64_max,
  f64_copysign,
  // linear memory loads: a = addr, b = alignment hint
  i32_load,
  i32_load8_u,
  i64_load,
  f32_load,
  f64_load,
  i64_store,
  f32_store,
  f64_store,
  memory_size,
  memory_grow,
  /**
   * The wide-arithmetic proposal (0xFC 19..22). Each produces TWO
   * i64 results — low half first — so like a multi-result call they
   * carry no single value and their results are read through `mv_get`
   * projections emitted immediately after, in ascending order.
   *
   * They exist as ZIR ops even though `WasmModule.wideArithmetic` is
   * off by default: lowering picks between emitting one of these and
   * emitting the equivalent 32-bit-halves sequence, so the day the
   * proposal is on everywhere the change is one boolean, not a new
   * backend path.
   */
  i64_mul_wide_s,
  i64_mul_wide_u,
  i64_add128,
  i64_sub128,
  /**
   * SIMD (§ docs/design/simd.md). One op per OPERAND SHAPE rather than
   * one per instruction: the 236 fixed-width vector instructions differ
   * only in their opcode, so the opcode rides as an immediate and these
   * eleven ops carry all of them. An enum case each would triple `IrOp`
   * and add 236 arms to every match over it for nothing.
   *
   * The result type is the instruction's, in `typeId`, so a `v128`
   * producer and an `i32` one (`i32x4.bitmask`) share `simd_unary`.
   */
  simd_unary,
  simd_binary,
  simd_ternary,
  simd_extract_lane,
  simd_replace_lane,
  simd_const,
  simd_shuffle,
  simd_load,
  simd_store,
  simd_load_lane,
  simd_store_lane,
  // references
  ref_null,
  ref_is_null,
  ref_as_non_null,
  ref_eq,
  ref_test,
  ref_cast,
  ref_func,
  extern_convert_any,
  any_convert_extern,
  // linear memory (fixed alignments matching the streaming helpers)
  i32_store,
  i32_store8,
  // aggregates
  struct_new,
  struct_new_default,
  struct_get,
  struct_set,
  array_new,
  array_new_data,
  array_new_fixed,
  array_get,
  array_get_u,
  array_get_s,
  array_set,
  array_copy,
  array_len,
  // module-level accesses
  global_get,
  global_set,
  /**
   * Reads a mutable variable (§5.1). Distinct from every other value in
   * ZIR: a variable is STORAGE, not an SSA definition, so a read is not
   * value-numbered and sees whatever the last executed `var_set` wrote.
   * Emits as `local.get` on a dedicated wasm local, never coalesced.
   */
  var_get,
  /** Writes a mutable variable. `local.set` on its dedicated local. */
  var_set,
  str_lit,
  // dispatch (docs/design/ir.md §5)
  iface_pack,
  iface_vtable,
  iface_instance,
  call,
  call_ref,
  /** Projects one result out of a multi-result call (which itself
   * produces no single value). Projections are emitted immediately
   * after their call, in ascending result order. */
  mv_get,
  // Terminators. These must stay last and contiguous: isIrTerminator does a
  // band check against IrOp.br.
  br,
  br_if,
  br_table,
  br_on_cast,
  br_on_cast_fail,
  /** Enters a protected region: control flows to the body successor;
   * an exception thrown anywhere in the body's dynamic extent
   * transfers to the catch successor (payload via the exception
   * globals, streaming-compatible). */
  try_br,
  ret,
  /** Multi-value return: all result values at once. */
  ret_multi,
  /**
   * Tail call to a known function: `return_call`. Encoded exactly as
   * `call` — slot a indexes the counted argument list, slot b the
   * refTable entry — and produces no value: the callee's results are
   * this function's results. See docs/design/tail-calls.md.
   */
  ret_call,
  /** Tail call through a funcref: `return_call_ref`. Encoded exactly
   * as `call_ref`. */
  ret_call_ref,
  throw,
  unreachable,
  /** Generator suspension (presplit form only, generators.md §4.1):
   * yields value `a` and resumes at the single successor. Never
   * emitted — the split pass rewrites every yield before emission. */
  yield_,
  /** Async suspension (presplit form only, async.md §3): awaits the
   * `Future` in slot `a` and resumes at the single successor. The
   * awaited future is an ordinary live value across the suspension, so
   * the resume edge carries no arguments — the resumed segment reads
   * the settled result back off the future. Never emitted; the split
   * pass rewrites every await before emission. */
  await_,
  /** Sentinel: the number of ops. Keep last. */
  op_count
}

export function isIrTerminator(op: IrOp): boolean {
  return op as i32 >= IrOp.br as i32;
}

/**
 * `isUnaryNumericOp` and `isSingleValueOp` by op, computed once from
 * the definitions below. The operand decoder asks for every
 * instruction it lists, and the definitions' chains of comparisons
 * cost more than the listing.
 */
let unaryNumericOps = opTable((op) => definesUnaryNumericOp(op));
let singleValueOps = opTable((op) => definesSingleValueOp(op));

/**
 * Unary numeric and conversion ops: exactly one value operand (slot a),
 * no payload. Shared by the operand decoder, the emitter, and (soon)
 * the simplify/constant-folding pass.
 */
export function isUnaryNumericOp(op: IrOp): boolean {
  return unaryNumericOps[op as i32];
}

function opTable(member: (op: IrOp) => boolean): GrowableArray<boolean> {
  let table = new Array<boolean>();
  for (var i = 0; i < IrOp.op_count as i32; i += 1) {
    table.push(member(i as IrOp));
  }
  return table;
}

function definesUnaryNumericOp(op: IrOp): boolean {
  return op == IrOp.i32_eqz || op == IrOp.i64_eqz || op == IrOp.f64_neg ||
      op == IrOp.f32_neg || op == IrOp.i32_wrap_i64 ||
      op == IrOp.i64_extend_i32_s || op == IrOp.f64_convert_i32_s ||
      op == IrOp.f32_convert_i32_s || op == IrOp.f64_convert_i64_s ||
      op == IrOp.f32_convert_i64_s || op == IrOp.i32_trunc_sat_f64_s ||
      op == IrOp.i32_trunc_sat_f32_s || op == IrOp.i64_trunc_sat_f64_s ||
      op == IrOp.i64_trunc_sat_f32_s || op == IrOp.f64_promote_f32 ||
      op == IrOp.f32_demote_f64 || op == IrOp.i64_reinterpret_f64 ||
      op == IrOp.i32_reinterpret_f32 ||
      op == IrOp.f32_reinterpret_i32 ||
      op == IrOp.f64_reinterpret_i64 ||
      op == IrOp.i32_trunc_sat_f32_u ||
      op == IrOp.i32_trunc_sat_f64_u ||
      op == IrOp.i64_trunc_sat_f32_u ||
      op == IrOp.i64_trunc_sat_f64_u ||
      op == IrOp.i64_extend_i32_u ||
      op == IrOp.f64_convert_i32_u ||
      op == IrOp.f32_convert_i32_u ||
      op == IrOp.f64_convert_i64_u ||
      op == IrOp.f32_convert_i64_u ||
      op == IrOp.i32_clz ||
      op == IrOp.i32_ctz ||
      op == IrOp.i32_popcnt ||
      op == IrOp.i64_clz ||
      op == IrOp.i64_ctz ||
      op == IrOp.i64_popcnt ||
      op == IrOp.f32_abs ||
      op == IrOp.f32_ceil ||
      op == IrOp.f32_floor ||
      op == IrOp.f32_nearest ||
      op == IrOp.f32_sqrt ||
      op == IrOp.f32_trunc ||
      op == IrOp.f64_abs ||
      op == IrOp.f64_ceil ||
      op == IrOp.f64_floor ||
      op == IrOp.f64_nearest ||
      op == IrOp.f64_sqrt ||
      op == IrOp.f64_trunc;
}

/**
 * The wide-arithmetic ops: two i64 results each, read through
 * `mv_get`. Grouped because every place that asks "does this leave
 * more than one value on the stack?" wants all four at once.
 */
export function isWideArithOp(op: IrOp): boolean {
  return op == IrOp.i64_mul_wide_s || op == IrOp.i64_mul_wide_u ||
      op == IrOp.i64_add128 || op == IrOp.i64_sub128;
}

/** The two-operand half of the above (the multiplies). */
export function isWideMulOp(op: IrOp): boolean {
  return op == IrOp.i64_mul_wide_s || op == IrOp.i64_mul_wide_u;
}

/** The wasm opcode (after the 0xFC prefix) a wide-arithmetic op emits. */
export function wideArithOpcode(op: IrOp): i32 {
  if (op == IrOp.i64_add128) { return WideArithOpcode.i64_add128 as i32; }
  if (op == IrOp.i64_sub128) { return WideArithOpcode.i64_sub128 as i32; }
  if (op == IrOp.i64_mul_wide_s) { return WideArithOpcode.i64_mul_wide_s as i32; }
  if (op == IrOp.i64_mul_wide_u) { return WideArithOpcode.i64_mul_wide_u as i32; }
  throw new Error(`wideArithOpcode: ${irOpName(op)} is not one`);
}

/**
 * Ops taking exactly ONE value operand (slot a): the unary numerics
 * plus the single-receiver reference/aggregate/dispatch ops — null
 * tests and casts, array_len, field and vtable loads, fat-pointer
 * unpacking — whose slot b (where used) holds a refTable or typeTable
 * index rather than a value. global_set is here too: its one value
 * operand is the stored value; the target global rides in slot b.
 */
export function isSingleValueOp(op: IrOp): boolean {
  return singleValueOps[op as i32];
}

function definesSingleValueOp(op: IrOp): boolean {
  return definesUnaryNumericOp(op) ||
      op == IrOp.ref_is_null || op == IrOp.ref_as_non_null ||
      op == IrOp.ref_test || op == IrOp.ref_cast || op == IrOp.array_len ||
      op == IrOp.extern_convert_any || op == IrOp.any_convert_extern ||
      op == IrOp.i32_load || op == IrOp.i32_load8_u || op == IrOp.i64_load ||
      op == IrOp.f32_load || op == IrOp.f64_load || op == IrOp.memory_grow ||
      op == IrOp.global_set || op == IrOp.var_set ||
      op == IrOp.struct_get || op == IrOp.iface_pack ||
      op == IrOp.iface_vtable || op == IrOp.iface_instance ||
      op == IrOp.mv_get ||
      // The one-operand SIMD shapes. Their slot b holds the opcode
      // (plus, for the other two, an extra index to the lane or
      // alignment immediates) — never a value.
      op == IrOp.simd_unary || op == IrOp.simd_extract_lane ||
      op == IrOp.simd_load;
}

/**
 * Any of the eleven SIMD shapes. They form a contiguous band, so this
 * is a range check — keep them together in the enum.
 */
export function isSimdOp(op: IrOp): boolean {
  let v = op as i32;
  return v >= IrOp.simd_unary as i32 && v <= IrOp.simd_store_lane as i32;
}

/**
 * How many value operands a SIMD op parks in `extra`, starting at slot
 * a. Zero for the shapes that keep their single operand inline (those
 * go through `isSingleValueOp`) and for `simd_const`, which reads
 * nothing. Immediates never appear in this list.
 */
export function simdExtraOperandCount(op: IrOp): i32 {
  if (op == IrOp.simd_binary || op == IrOp.simd_shuffle ||
      op == IrOp.simd_store || op == IrOp.simd_replace_lane ||
      op == IrOp.simd_load_lane || op == IrOp.simd_store_lane) {
    return 2;
  }
  if (op == IrOp.simd_ternary) {
    return 3;
  }
  return 0;
}

/**
 * Binary numeric ops: two inline value operands (slots a and b), no
 * payload. Relies on the enum's contiguous numeric bands.
 */
/**
 * Operand order does not change the result. Integer-only plus the
 * equality ops: float add/mul are left out — their results are
 * value-equal either way, but NaN payload propagation is
 * implementation-defined and reordering them buys nothing here.
 */
export function isCommutativeOp(op: IrOp): boolean {
  return op == IrOp.i32_add || op == IrOp.i32_mul || op == IrOp.i32_and ||
      op == IrOp.i32_or || op == IrOp.i32_xor || op == IrOp.i32_eq ||
      op == IrOp.i32_ne ||
      op == IrOp.i64_add || op == IrOp.i64_mul || op == IrOp.i64_and ||
      op == IrOp.i64_or || op == IrOp.i64_xor || op == IrOp.i64_eq ||
      op == IrOp.i64_ne ||
      op == IrOp.ref_eq;
}

export function isBinaryNumericOp(op: IrOp): boolean {
  let v = op as i32;
  return (v >= IrOp.i32_add as i32 && v <= IrOp.i32_ge_u as i32 &&
          v != IrOp.i32_eqz as i32) ||
         (v >= IrOp.i64_add as i32 && v <= IrOp.f32_ge as i32) ||
         op == IrOp.f32_min || op == IrOp.f32_max ||
         op == IrOp.f32_copysign || op == IrOp.f64_min ||
         op == IrOp.f64_max || op == IrOp.f64_copysign;
}

/**
 * Where an instruction keeps its value operands: the shapes of the
 * operand-encoding table in the file header, as `appendValueOperands`
 * and `rewriteValueOperands` decode them. Slot b of an `InA` op, and
 * the slots of a `None` op, hold payloads (refTable and typeTable
 * indices, immediates), never values.
 */
enum OperandShape {
  /** Constants, params, and reads of module entities through slot b. */
  None,
  /** One value in slot a. */
  InA,
  /** Two values, in slots a and b. */
  InAB,
  /** A fixed number of values (`extraOperandCounts`) in `extra` from slot a. */
  InExtra,
  /** `array_new`: [length, init] in `extra`, init -1 when default-initialized. */
  ArrayNew,
  /** A counted list in `extra`: [argc, arg*]. */
  Counted,
  /** `call_ref`'s callee, then a counted list: [callee, argc, arg*]. */
  CalleeThenCounted,
  /** `ret`: slot a, or -1 for a void return. */
  Ret,
  /** `br`, `try_br`: the arguments of every successor edge (`try_br`'s slot a is a tag). */
  Successors,
  /** The conditional branches and suspensions: slot a, then the successor edges' arguments. */
  InAThenSuccessors,
  /** An op neither decoder handles. */
  Unhandled,
}

/**
 * Each op's `OperandShape`, and for `InExtra` ops their count, computed
 * once from `operandShapeOf`. The decoders run for every instruction a
 * pass visits; testing the op against each shape's list in turn cost
 * them more than the decoding.
 */
let operandShapes = operandShapeTable();
let extraOperandCounts = extraOperandCountTable();

function operandShapeTable(): GrowableArray<OperandShape> {
  let table = new Array<OperandShape>();
  for (var i = 0; i < IrOp.op_count as i32; i += 1) {
    table.push(operandShapeOf(i as IrOp));
  }
  return table;
}

function extraOperandCountTable(): GrowableArray<i32> {
  let table = new Array<i32>();
  for (var i = 0; i < IrOp.op_count as i32; i += 1) {
    table.push(extraOperandCountOf(i as IrOp));
  }
  return table;
}

/** The decoders' one classification of `op`. */
function operandShapeOf(op: IrOp): OperandShape {
  if (op == IrOp.nop || op == IrOp.param || op == IrOp.const_i32 ||
      op == IrOp.const_i64 || op == IrOp.const_f32 || op == IrOp.const_f64 ||
      op == IrOp.ref_null || op == IrOp.ref_func || op == IrOp.str_lit ||
      op == IrOp.global_get || op == IrOp.var_get ||
      op == IrOp.struct_new_default || op == IrOp.simd_const ||
      op == IrOp.memory_size || op == IrOp.unreachable) {
    return OperandShape.None;
  }
  if (definesSingleValueOp(op)) {
    return OperandShape.InA;
  }
  if (op == IrOp.array_get || op == IrOp.array_get_u ||
      op == IrOp.array_get_s || op == IrOp.ref_eq ||
      isWideMulOp(op) || isBinaryNumericOp(op)) {
    return OperandShape.InAB;
  }
  if (extraOperandCountOf(op) > 0) {
    return OperandShape.InExtra;
  }
  if (op == IrOp.array_new) {
    return OperandShape.ArrayNew;
  }
  if (op == IrOp.struct_new || op == IrOp.call || op == IrOp.ret_call ||
      op == IrOp.throw || op == IrOp.array_new_fixed || op == IrOp.ret_multi) {
    return OperandShape.Counted;
  }
  if (op == IrOp.call_ref || op == IrOp.ret_call_ref) {
    return OperandShape.CalleeThenCounted;
  }
  if (op == IrOp.ret) {
    return OperandShape.Ret;
  }
  if (op == IrOp.br || op == IrOp.try_br) {
    return OperandShape.Successors;
  }
  if (op == IrOp.br_if || op == IrOp.br_on_cast ||
      op == IrOp.br_on_cast_fail || op == IrOp.br_table ||
      op == IrOp.yield_ || op == IrOp.await_) {
    return OperandShape.InAThenSuccessors;
  }
  return OperandShape.Unhandled;
}

/** How many values an `InExtra` op keeps in `extra`; 0 for every other op. */
function extraOperandCountOf(op: IrOp): i32 {
  // i64.add128 / i64.sub128: [lhsLo, lhsHi, rhsLo, rhsHi].
  if (op == IrOp.i64_add128 || op == IrOp.i64_sub128) {
    return 4;
  }
  // struct_set and the memory stores: [receiver or address, value].
  if (op == IrOp.struct_set || op == IrOp.i32_store ||
      op == IrOp.i32_store8 || op == IrOp.i64_store ||
      op == IrOp.f32_store || op == IrOp.f64_store) {
    return 2;
  }
  // array_set: [array, index, value].
  if (op == IrOp.array_set) {
    return 3;
  }
  // array_copy: [dest, destOff, src, srcOff, len].
  if (op == IrOp.array_copy) {
    return 5;
  }
  // array_new_data: [offset, length, dataIndex]; the data index is an
  // immediate.
  if (op == IrOp.array_new_data) {
    return 2;
  }
  // SIMD: the wasm opcode and any lane or alignment immediate ride in
  // slot b.
  return simdExtraOperandCount(op);
}

/**
 * A symbolic reference to a module entity. Instructions address these via
 * refTable indices; numeric wasm indices, field offsets, and vtable slots
 * are bound at layout time, after the optimization fixpoint (ir.md §10.2).
 */
export sealed class IrRef {
  case IrRefFunc(target: WasmFunction)
  case IrRefGlobal(target: WasmGlobal)
  case IrRefTag(target: WasmTag)
  case IrRefType(target: WasmType)
  /** A field named symbolically on a struct (object field or vtable slot). */
  case IrRefField(owner: WasmStruct, fieldName: String)
  /** A (class, interface) pair for fat-pointer construction. */
  case IrRefClassInterface(classStruct: WasmStruct, ifaceStruct: WasmStruct)
  case IrRefStringLit(value: String)
}

/**
 * One basic block.
 *
 * A basic block is a straight-line run of instructions: execution can only
 * enter at the top, and can only leave through the single *terminator*
 * instruction at the end (a branch, return, throw, or unreachable) — there
 * are no jumps into or out of the middle. A function body is a graph of
 * these blocks, with the terminators' targets as the edges.
 *
 * Block *parameters* are how values flow between blocks in SSA form; they
 * replace the phi nodes of textbook SSA. A block declares typed
 * parameters, and every branch to it must pass matching arguments — think
 * of branching to a block as calling it with values. For example, a
 * loop-carried counter is a parameter of the loop-header block: the entry
 * branch passes its initial value and the back-edge branch passes the
 * incremented one. (docs/design/ir.md §3 has a worked example.)
 *
 * `params` holds the ids of this block's param instructions; `insts` holds
 * the body instruction ids in order, the last of which must be a
 * terminator. Blocks are objects (not flattened into IrBody arrays)
 * because block counts are tiny relative to instruction counts; the flat
 * blockStart/blockEnd form from ir.md §4 is the *compacted*
 * representation, produced by compact() before serialization/emission
 * (later milestone).
 */
export final class IrBlock {
  params = new Array<i32>();
  insts = new Array<i32>();
}

/** One decoded control-flow edge: target block + branch arguments. */
export final class IrSuccessor {
  target: i32;
  /** Index into IrBody.extra of the first branch argument. */
  argStart: i32;
  argCount: i32;
  new(this.target, this.argStart, this.argCount);
}

export final class IrBody {
  // Parallel instruction arrays, indexed by instruction id. These always
  // have identical lengths and grow in lockstep (only the builder's
  // #newInst appends). A fused stride-N buffer or a rope could avoid the
  // separate copies on growth, but passes overwhelmingly scan one or two
  // of these fields linearly, which favors the struct-of-arrays split,
  // and growth copies are amortized and cheap (array.copy). Lowering will
  // pre-size them from the AST node count via a builder capacity hint
  // (ir.md §4), which should make mid-build growth rare.
  opcode = new Array<i32>();
  typeId = new Array<i32>();
  a = new Array<i32>();
  b = new Array<i32>();
  /** Block id owning each instruction. */
  instBlock = new Array<i32>();
  /** Overflow operand pool. */
  extra = new Array<i32>();

  blocks = new Array<IrBlock>();

  // Indirection tables (ir.md §4).
  typeTable = new Array<ValType>();
  refTable = new Array<IrRef>();

  // Constant pools.
  constI64 = new Array<i64>();
  constF64 = new Array<f64>();

  /**
   * Mutable variables (§5.1), indexed by var id: the declared type of
   * each. Emission gives every one its OWN wasm local, excluded from
   * coalescing, so its stored value survives an exception unwinding to
   * a handler in the same frame — which no SSA value can, since a
   * handler edge leaves from anywhere in the protected region and can
   * only carry values live at its entry.
   */
  varTypes = new Array<ValType>();

  /**
   * The join block of each user `try`, keyed by its try_br instruction:
   * where control lands after the try, when any arm completes.
   *
   * The CFG cannot express this. When the catch diverges, the join's
   * only predecessor is the body's exit, so by dominance the join
   * looks like part of the protected region — and everything that
   * takes dominance as region membership (emission's try_table
   * placement, the split passes' re-entry) would put the continuation
   * INSIDE the handler's reach. This table records where the region
   * actually ends. Instruction ids are stable through the split
   * passes (blocks are appended, instructions move but keep their
   * ids), and the passes copy entries onto the fresh re-entry try_brs
   * they synthesize.
   */
  tryJoin = new Map<i32, i32>();

  /**
   * The `ret` instructions that ADOPT rather than complete: a
   * `tail return f()` in an async body returns the callee's future,
   * and the split pass settles the frame's future from it
   * (async.md §8) instead of completing with a value. Instruction
   * ids are stable through the split, like `tryJoin`'s.
   */
  adoptReturns = new Set<i32>();

  instCount(): i32 {
    return this.opcode.length;
  }

  op(inst: i32): IrOp {
    return this.opcode[inst] as IrOp;
  }

  /** The result type of an instruction, or null if it produces no value. */
  resultType(inst: i32): ValType | null {
    let t = this.typeId[inst];
    if (t < 0) {
      return null;
    }
    return this.typeTable[t];
  }

  producesValue(inst: i32): boolean {
    return this.typeId[inst] >= 0;
  }

  /**
   * Appends every value operand of `inst` (instruction ids read by it,
   * including branch arguments) to `out`.
   */
  appendValueOperands(inst: i32, out: GrowableArray<i32>): void {
    let op = this.op(inst);
    let av = this.a[inst];
    // One case per `OperandShape`, the commonest first.
    let shape = operandShapes[op as i32];
    if (shape == OperandShape.InA) {
      out.push(av);
      return;
    }
    if (shape == OperandShape.InAB) {
      out.push(av);
      out.push(this.b[inst]);
      return;
    }
    if (shape == OperandShape.None) {
      return;
    }
    if (shape == OperandShape.Counted) {
      let argc = this.extra[av];
      var i = 0;
      while (i < argc) {
        out.push(this.extra[av + 1 + i]);
        i += 1;
      }
      return;
    }
    if (shape == OperandShape.InAThenSuccessors) {
      out.push(av);
      this.#appendSuccessorArgs(inst, out);
      return;
    }
    if (shape == OperandShape.Successors) {
      this.#appendSuccessorArgs(inst, out);
      return;
    }
    if (shape == OperandShape.InExtra) {
      let n = extraOperandCounts[op as i32];
      var i = 0;
      while (i < n) {
        out.push(this.extra[av + i]);
        i += 1;
      }
      return;
    }
    if (shape == OperandShape.CalleeThenCounted) {
      out.push(this.extra[av]);
      let argc = this.extra[av + 1];
      var i = 0;
      while (i < argc) {
        out.push(this.extra[av + 2 + i]);
        i += 1;
      }
      return;
    }
    if (shape == OperandShape.Ret) {
      if (av >= 0) {
        out.push(av);
      }
      return;
    }
    if (shape == OperandShape.ArrayNew) {
      out.push(this.extra[av]);
      let init = this.extra[av + 1];
      if (init >= 0) {
        out.push(init);
      }
      return;
    }
    throw new Error(`appendValueOperands: unhandled opcode ${irOpName(op)}`);
  }

  /**
   * Rewrites every VALUE operand of `inst` through `map`, in place —
   * the mutating mirror of appendValueOperands, branch for branch
   * (keep the two in sync). Non-value payloads (refTable/typeTable
   * indices, immediates, alignments) are untouched.
   */
  rewriteValueOperands(inst: i32, map: (v: i32) => i32): void {
    let op = this.op(inst);
    let av = this.a[inst];
    let shape = operandShapes[op as i32];
    if (shape == OperandShape.InA) {
      this.a[inst] = map(av);
      return;
    }
    if (shape == OperandShape.InAB) {
      this.a[inst] = map(av);
      this.b[inst] = map(this.b[inst]);
      return;
    }
    if (shape == OperandShape.None) {
      return;
    }
    if (shape == OperandShape.Counted) {
      let argc = this.extra[av];
      var i = 0;
      while (i < argc) {
        this.extra[av + 1 + i] = map(this.extra[av + 1 + i]);
        i += 1;
      }
      return;
    }
    if (shape == OperandShape.InAThenSuccessors) {
      this.a[inst] = map(av);
      this.#rewriteSuccessorArgs(inst, map);
      return;
    }
    if (shape == OperandShape.Successors) {
      this.#rewriteSuccessorArgs(inst, map);
      return;
    }
    if (shape == OperandShape.InExtra) {
      let n = extraOperandCounts[op as i32];
      var i = 0;
      while (i < n) {
        this.extra[av + i] = map(this.extra[av + i]);
        i += 1;
      }
      return;
    }
    if (shape == OperandShape.CalleeThenCounted) {
      this.extra[av] = map(this.extra[av]);
      let argc = this.extra[av + 1];
      var i = 0;
      while (i < argc) {
        this.extra[av + 2 + i] = map(this.extra[av + 2 + i]);
        i += 1;
      }
      return;
    }
    if (shape == OperandShape.Ret) {
      if (av >= 0) {
        this.a[inst] = map(av);
      }
      return;
    }
    if (shape == OperandShape.ArrayNew) {
      this.extra[av] = map(this.extra[av]);
      let init = this.extra[av + 1];
      if (init >= 0) {
        this.extra[av + 1] = map(init);
      }
      return;
    }
    throw new Error(`rewriteValueOperands: unhandled opcode ${irOpName(op)}`);
  }

  /**
   * Copies an instruction from `src` into this body, remapping value
   * operands through `map`, branch targets through `mapBlock`, and
   * table references by the given offsets (the caller appends src's
   * typeTable, refTable, and varTypes wholesale before copying and
   * passes the pre-append lengths; constant-pool values are copied
   * here directly). Returns the new instruction id; the caller owns
   * instBlock and block membership. Third mirror of
   * appendValueOperands / rewriteValueOperands — keep all three in
   * sync, branch for branch. Params, returns, tail calls, try_br, and
   * suspensions throw rather than risk a silently mishandled copy: the
   * inliner creates or excludes those itself.
   */
  copyFrom(src: IrBody, inst: i32, map: (v: i32) => i32, typeOffset: i32,
      refOffset: i32, varOffset: i32, mapBlock: (b: i32) => i32): i32 {
    let op = src.op(inst);
    let av = src.a[inst];
    let bv = src.b[inst];
    let ty = src.typeId[inst];
    let newTy = if (ty >= 0) ty + typeOffset else -1;
    let newId = this.opcode.length;
    let emit = (na: i32, nb: i32) => {
      this.opcode.push(op as i32);
      this.typeId.push(newTy);
      this.a.push(na);
      this.b.push(nb);
      this.instBlock.push(-1);
      return newId;
    };
    let copyExtraRecord = (start: i32, len: i32) => {
      let idx = this.extra.length;
      var i = 0;
      while (i < len) {
        this.extra.push(src.extra[start + i]);
        i += 1;
      }
      return idx;
    };
    let copyMappedRecord = (start: i32, len: i32) => {
      let idx = this.extra.length;
      var i = 0;
      while (i < len) {
        this.extra.push(map(src.extra[start + i]));
        i += 1;
      }
      return idx;
    };

    if (op == IrOp.param || op == IrOp.nop || op == IrOp.ret ||
        op == IrOp.ret_multi || op == IrOp.ret_call ||
        op == IrOp.ret_call_ref || op == IrOp.try_br ||
        op == IrOp.yield_ || op == IrOp.await_) {
      // Params are definitions the caller creates itself; returns
      // become branches to a continuation the caller owns; tail calls,
      // protected regions, and suspensions are excluded from inlining.
      throw new Error(`copyFrom: cannot copy ${irOpName(op)}`);
    }
    // Branch terminators: successor records [target, argc, args…]
    // copied with targets through mapBlock and args through map.
    let copySuccessors = (start: i32, count: i32, prefixLen: i32) => {
      let idx = this.extra.length;
      var p = 0;
      while (p < prefixLen) {
        this.extra.push(src.extra[start + p]);
        p += 1;
      }
      var pos = start + prefixLen;
      var s = 0;
      while (s < count) {
        let target = src.extra[pos];
        let argc = src.extra[pos + 1];
        this.extra.push(mapBlock(target));
        this.extra.push(argc);
        var i = 0;
        while (i < argc) {
          this.extra.push(map(src.extra[pos + 2 + i]));
          i += 1;
        }
        pos += 2 + argc;
        s += 1;
      }
      return idx;
    };
    if (op == IrOp.br) {
      return emit(copySuccessors(av, 1, 0), bv);
    }
    if (op == IrOp.br_if) {
      return emit(map(av), copySuccessors(bv, 2, 0));
    }
    if (op == IrOp.br_on_cast || op == IrOp.br_on_cast_fail) {
      // The record leads with the target type's typeTable index.
      let idx = this.extra.length;
      this.extra.push(src.extra[bv] + typeOffset);
      copySuccessors(bv + 1, 2, 0);
      return emit(map(av), idx);
    }
    if (op == IrOp.br_table) {
      let count = src.extra[bv];
      return emit(map(av), copySuccessors(bv, count, 1));
    }
    if (op == IrOp.throw) {
      let argc = src.extra[av];
      let idx = this.extra.length;
      this.extra.push(argc);
      var i = 0;
      while (i < argc) {
        this.extra.push(map(src.extra[av + 1 + i]));
        i += 1;
      }
      return emit(idx, if (bv >= 0) bv + refOffset else bv);
    }
    if (op == IrOp.unreachable) {
      return emit(av, bv);
    }
    // Shape: no value operands. Payloads by op: const pools, refTable
    // entities, var indices, the simd_const byte record.
    if (op == IrOp.const_i32 || op == IrOp.memory_size) {
      return emit(av, bv);
    }
    if (op == IrOp.const_i64) {
      this.constI64.push(src.constI64[av]);
      return emit(this.constI64.length - 1, bv);
    }
    if (op == IrOp.const_f32 || op == IrOp.const_f64) {
      this.constF64.push(src.constF64[av]);
      return emit(this.constF64.length - 1, bv);
    }
    if (op == IrOp.ref_null) {
      return emit(av, bv);
    }
    if (op == IrOp.ref_func || op == IrOp.str_lit || op == IrOp.global_get ||
        op == IrOp.struct_new_default) {
      return emit(av, if (bv >= 0) bv + refOffset else bv);
    }
    if (op == IrOp.var_get) {
      return emit(av, bv + varOffset);
    }
    if (op == IrOp.simd_const) {
      return emit(av, copyExtraRecord(bv, 17));
    }
    // Shape: one value in slot a; slot b's meaning varies by op.
    if (isSingleValueOp(op)) {
      let na = map(av);
      if (op == IrOp.ref_test || op == IrOp.ref_cast) {
        return emit(na, bv + typeOffset);
      }
      if (op == IrOp.global_set || op == IrOp.struct_get ||
          op == IrOp.iface_pack) {
        return emit(na, bv + refOffset);
      }
      if (op == IrOp.var_set) {
        return emit(na, bv + varOffset);
      }
      if (op == IrOp.simd_extract_lane || op == IrOp.simd_load) {
        return emit(na, copyExtraRecord(bv, 2));
      }
      // mv_get's result index, simd_unary's opcode, and the -1 of the
      // pure unary ops all ride slot b verbatim.
      return emit(na, bv);
    }
    // Shape: two values inline.
    if (op == IrOp.array_get || op == IrOp.array_get_u ||
        op == IrOp.array_get_s || op == IrOp.ref_eq ||
        isWideMulOp(op) || isBinaryNumericOp(op)) {
      return emit(map(av), map(bv));
    }
    if (op == IrOp.i64_add128 || op == IrOp.i64_sub128) {
      return emit(copyMappedRecord(av, 4), bv);
    }
    if (op == IrOp.struct_set) {
      return emit(copyMappedRecord(av, 2), bv + refOffset);
    }
    if (op == IrOp.i32_store || op == IrOp.i32_store8 ||
        op == IrOp.i64_store || op == IrOp.f32_store ||
        op == IrOp.f64_store) {
      return emit(copyMappedRecord(av, 2), bv);
    }
    if (op == IrOp.array_set) {
      return emit(copyMappedRecord(av, 3), bv);
    }
    if (op == IrOp.array_copy) {
      return emit(copyMappedRecord(av, 5), bv);
    }
    if (op == IrOp.array_new_data) {
      // [offset, length, dataIndex] — the data segment is module-level,
      // so its index copies verbatim.
      let idx = this.extra.length;
      this.extra.push(map(src.extra[av]));
      this.extra.push(map(src.extra[av + 1]));
      this.extra.push(src.extra[av + 2]);
      return emit(idx, if (bv >= 0) bv + refOffset else bv);
    }
    if (op == IrOp.array_new) {
      let idx = this.extra.length;
      this.extra.push(map(src.extra[av]));
      let init = src.extra[av + 1];
      this.extra.push(if (init >= 0) map(init) else init);
      return emit(idx, if (bv >= 0) bv + refOffset else bv);
    }
    if (op == IrOp.struct_new || op == IrOp.call ||
        op == IrOp.array_new_fixed) {
      let argc = src.extra[av];
      let idx = this.extra.length;
      this.extra.push(argc);
      var i = 0;
      while (i < argc) {
        this.extra.push(map(src.extra[av + 1 + i]));
        i += 1;
      }
      return emit(idx, if (bv >= 0) bv + refOffset else bv);
    }
    if (op == IrOp.call_ref) {
      let idx = this.extra.length;
      this.extra.push(map(src.extra[av]));
      let argc = src.extra[av + 1];
      this.extra.push(argc);
      var i = 0;
      while (i < argc) {
        this.extra.push(map(src.extra[av + 2 + i]));
        i += 1;
      }
      return emit(idx, bv);
    }
    // SIMD shapes with a value list in extra; slot b is either the
    // plain opcode (binary/ternary) or an immediate record.
    let simdCount = simdExtraOperandCount(op);
    if (simdCount > 0) {
      let na = copyMappedRecord(av, simdCount);
      if (op == IrOp.simd_binary || op == IrOp.simd_ternary) {
        return emit(na, bv);
      }
      if (op == IrOp.simd_shuffle) {
        return emit(na, copyExtraRecord(bv, 17));
      }
      if (op == IrOp.simd_store || op == IrOp.simd_replace_lane) {
        return emit(na, copyExtraRecord(bv, 2));
      }
      if (op == IrOp.simd_load_lane || op == IrOp.simd_store_lane) {
        return emit(na, copyExtraRecord(bv, 3));
      }
    }
    throw new Error(`copyFrom: unhandled opcode ${irOpName(op)}`);
  }

  #rewriteSuccessorArgs(inst: i32, map: (v: i32) => i32): void {
    let n = this.successorCount(inst);
    for (var k = 0; k < n; k += 1) {
      let rec = this.successorRecord(inst, k);
      let argc = this.extra[rec + 1];
      var i = 0;
      while (i < argc) {
        this.extra[rec + 2 + i] = map(this.extra[rec + 2 + i]);
        i += 1;
      }
    }
  }

  #appendSuccessorArgs(inst: i32, out: GrowableArray<i32>): void {
    let n = this.successorCount(inst);
    for (var k = 0; k < n; k += 1) {
      let rec = this.successorRecord(inst, k);
      let argc = this.extra[rec + 1];
      var i = 0;
      while (i < argc) {
        out.push(this.extra[rec + 2 + i]);
        i += 1;
      }
    }
  }


  /**
   * Where a terminator's successor records start in `extra`, or -1 for
   * one with no successors. Each record is `target, argc, args...`,
   * so they are walked, not indexed. (Start and count are separate
   * queries rather than one tuple: a tuple return is a heap struct,
   * and these run once per edge visit.)
   */
  #successorStart(inst: i32): i32 {
    let op = this.op(inst);
    if (op == IrOp.br) {
      return this.a[inst];
    }
    if (op == IrOp.br_if || op == IrOp.try_br ||
        op == IrOp.yield_ || op == IrOp.await_) {
      return this.b[inst];
    }
    if (op == IrOp.br_on_cast || op == IrOp.br_on_cast_fail) {
      return this.b[inst] + 1; // skip target type
    }
    if (op == IrOp.br_table) {
      return this.b[inst] + 1; // skip the count
    }
    if (op == IrOp.ret || op == IrOp.ret_multi || op == IrOp.throw ||
        op == IrOp.ret_call || op == IrOp.ret_call_ref ||
        op == IrOp.unreachable) {
      return -1;
    }
    throw new Error(`successors: not a terminator: ${irOpName(op)}`);
  }

  /** How many control-flow successors a terminator has. */
  successorCount(inst: i32): i32 {
    let op = this.op(inst);
    if (op == IrOp.br || op == IrOp.yield_ || op == IrOp.await_) {
      return 1;
    }
    if (op == IrOp.br_if || op == IrOp.try_br ||
        op == IrOp.br_on_cast || op == IrOp.br_on_cast_fail) {
      return 2;
    }
    if (op == IrOp.br_table) {
      return this.extra[this.b[inst]];
    }
    if (op == IrOp.ret || op == IrOp.ret_multi || op == IrOp.throw ||
        op == IrOp.ret_call || op == IrOp.ret_call_ref ||
        op == IrOp.unreachable) {
      return 0;
    }
    throw new Error(`successors: not a terminator: ${irOpName(op)}`);
  }

  /**
   * The index in `extra` of a terminator's `k`th successor record: the
   * target is at it, the argument count one past, the arguments two
   * past. The allocation-free form of `successors`, for passes that
   * walk edges in a loop; a rewrite appends a fresh record, so an index
   * is good until the next `retarget` of the same terminator.
   */
  successorRecord(inst: i32, k: i32): i32 {
    if (k >= this.successorCount(inst)) {
      throw new Error(`successorRecord: ${irOpName(this.op(inst))} has ${i32ToString(this.successorCount(inst))} successors, asked for ${i32ToString(k)}`);
    }
    var idx = this.#successorStart(inst);
    var i = 0;
    while (i < k) {
      idx += 2 + this.extra[idx + 1];
      i += 1;
    }
    return idx;
  }

  /** Decodes the control-flow successors of a terminator instruction. */
  successors(inst: i32): GrowableArray<IrSuccessor> {
    let result = new Array<IrSuccessor>();
    let count = this.successorCount(inst);
    var idx = this.#successorStart(inst);
    var i = 0;
    while (i < count) {
      let argc = this.extra[idx + 1];
      result.push(new IrSuccessor(this.extra[idx], idx + 2, argc));
      idx += 2 + argc;
      i += 1;
    }
    return result;
  }
}

/**
 * Wasm-style mnemonic per op, indexed by the dense IrOp value; ops
 * without an entry (empty string) print as op#N.
 */
function buildIrOpNames() {
  let count = IrOp.op_count as i32;
  let n = new Array<String>(count);
  for (var i = 0; i < count; i += 1) {
    n.push('');
  }
  n[IrOp.nop as i32] = 'nop';
  n[IrOp.param as i32] = 'param';
  n[IrOp.const_i32 as i32] = 'const.i32';
  n[IrOp.const_i64 as i32] = 'const.i64';
  n[IrOp.const_f32 as i32] = 'const.f32';
  n[IrOp.const_f64 as i32] = 'const.f64';
  n[IrOp.i32_add as i32] = 'i32.add';
  n[IrOp.i32_sub as i32] = 'i32.sub';
  n[IrOp.i32_mul as i32] = 'i32.mul';
  n[IrOp.i32_div_s as i32] = 'i32.div_s';
  n[IrOp.i32_rem_s as i32] = 'i32.rem_s';
  n[IrOp.i32_and as i32] = 'i32.and';
  n[IrOp.i32_or as i32] = 'i32.or';
  n[IrOp.i32_xor as i32] = 'i32.xor';
  n[IrOp.i32_shl as i32] = 'i32.shl';
  n[IrOp.i32_shr_s as i32] = 'i32.shr_s';
  n[IrOp.i32_shr_u as i32] = 'i32.shr_u';
  n[IrOp.i32_eqz as i32] = 'i32.eqz';
  n[IrOp.i32_eq as i32] = 'i32.eq';
  n[IrOp.i32_ne as i32] = 'i32.ne';
  n[IrOp.i32_lt_s as i32] = 'i32.lt_s';
  n[IrOp.i32_le_s as i32] = 'i32.le_s';
  n[IrOp.i32_gt_s as i32] = 'i32.gt_s';
  n[IrOp.i32_ge_s as i32] = 'i32.ge_s';
  n[IrOp.i32_div_u as i32] = 'i32.div_u';
  n[IrOp.i32_rem_u as i32] = 'i32.rem_u';
  n[IrOp.i32_lt_u as i32] = 'i32.lt_u';
  n[IrOp.i32_le_u as i32] = 'i32.le_u';
  n[IrOp.i32_gt_u as i32] = 'i32.gt_u';
  n[IrOp.i32_ge_u as i32] = 'i32.ge_u';
  n[IrOp.i64_add as i32] = 'i64.add';
  n[IrOp.i64_sub as i32] = 'i64.sub';
  n[IrOp.i64_mul as i32] = 'i64.mul';
  n[IrOp.i64_div_s as i32] = 'i64.div_s';
  n[IrOp.i64_rem_s as i32] = 'i64.rem_s';
  n[IrOp.i64_and as i32] = 'i64.and';
  n[IrOp.i64_or as i32] = 'i64.or';
  n[IrOp.i64_xor as i32] = 'i64.xor';
  n[IrOp.i64_shl as i32] = 'i64.shl';
  n[IrOp.i64_shr_s as i32] = 'i64.shr_s';
  n[IrOp.i64_shr_u as i32] = 'i64.shr_u';
  n[IrOp.i64_eq as i32] = 'i64.eq';
  n[IrOp.i64_ne as i32] = 'i64.ne';
  n[IrOp.i64_lt_s as i32] = 'i64.lt_s';
  n[IrOp.i64_le_s as i32] = 'i64.le_s';
  n[IrOp.i64_gt_s as i32] = 'i64.gt_s';
  n[IrOp.i64_ge_s as i32] = 'i64.ge_s';
  n[IrOp.i64_div_u as i32] = 'i64.div_u';
  n[IrOp.i64_rem_u as i32] = 'i64.rem_u';
  n[IrOp.i64_lt_u as i32] = 'i64.lt_u';
  n[IrOp.i64_le_u as i32] = 'i64.le_u';
  n[IrOp.i64_gt_u as i32] = 'i64.gt_u';
  n[IrOp.i64_ge_u as i32] = 'i64.ge_u';
  n[IrOp.f64_add as i32] = 'f64.add';
  n[IrOp.f64_sub as i32] = 'f64.sub';
  n[IrOp.f64_mul as i32] = 'f64.mul';
  n[IrOp.f64_div as i32] = 'f64.div';
  n[IrOp.f64_eq as i32] = 'f64.eq';
  n[IrOp.f64_ne as i32] = 'f64.ne';
  n[IrOp.f64_lt as i32] = 'f64.lt';
  n[IrOp.f64_le as i32] = 'f64.le';
  n[IrOp.f64_gt as i32] = 'f64.gt';
  n[IrOp.f64_ge as i32] = 'f64.ge';
  n[IrOp.f32_add as i32] = 'f32.add';
  n[IrOp.f32_sub as i32] = 'f32.sub';
  n[IrOp.f32_mul as i32] = 'f32.mul';
  n[IrOp.f32_div as i32] = 'f32.div';
  n[IrOp.f32_eq as i32] = 'f32.eq';
  n[IrOp.f32_ne as i32] = 'f32.ne';
  n[IrOp.f32_lt as i32] = 'f32.lt';
  n[IrOp.f32_le as i32] = 'f32.le';
  n[IrOp.f32_gt as i32] = 'f32.gt';
  n[IrOp.f32_ge as i32] = 'f32.ge';
  n[IrOp.i64_eqz as i32] = 'i64.eqz';
  n[IrOp.f64_neg as i32] = 'f64.neg';
  n[IrOp.f32_neg as i32] = 'f32.neg';
  n[IrOp.i32_wrap_i64 as i32] = 'i32.wrap_i64';
  n[IrOp.i64_extend_i32_s as i32] = 'i64.extend_i32_s';
  n[IrOp.f64_convert_i32_s as i32] = 'f64.convert_i32_s';
  n[IrOp.f32_convert_i32_s as i32] = 'f32.convert_i32_s';
  n[IrOp.f64_convert_i64_s as i32] = 'f64.convert_i64_s';
  n[IrOp.f32_convert_i64_s as i32] = 'f32.convert_i64_s';
  n[IrOp.i32_trunc_sat_f64_s as i32] = 'i32.trunc_sat_f64_s';
  n[IrOp.i32_trunc_sat_f32_s as i32] = 'i32.trunc_sat_f32_s';
  n[IrOp.i64_trunc_sat_f64_s as i32] = 'i64.trunc_sat_f64_s';
  n[IrOp.i64_trunc_sat_f32_s as i32] = 'i64.trunc_sat_f32_s';
  n[IrOp.f64_promote_f32 as i32] = 'f64.promote_f32';
  n[IrOp.f32_demote_f64 as i32] = 'f32.demote_f64';
  n[IrOp.i64_reinterpret_f64 as i32] = 'i64.reinterpret_f64';
  n[IrOp.i32_reinterpret_f32 as i32] = 'i32.reinterpret_f32';
  n[IrOp.f32_reinterpret_i32 as i32] = 'f32.reinterpret_i32';
  n[IrOp.f64_reinterpret_i64 as i32] = 'f64.reinterpret_i64';
  n[IrOp.i32_trunc_sat_f32_u as i32] = 'i32.trunc_sat_f32_u';
  n[IrOp.i32_trunc_sat_f64_u as i32] = 'i32.trunc_sat_f64_u';
  n[IrOp.i64_trunc_sat_f32_u as i32] = 'i64.trunc_sat_f32_u';
  n[IrOp.i64_trunc_sat_f64_u as i32] = 'i64.trunc_sat_f64_u';
  n[IrOp.i64_extend_i32_u as i32] = 'i64.extend_i32_u';
  n[IrOp.f64_convert_i32_u as i32] = 'f64.convert_i32_u';
  n[IrOp.f32_convert_i32_u as i32] = 'f32.convert_i32_u';
  n[IrOp.f64_convert_i64_u as i32] = 'f64.convert_i64_u';
  n[IrOp.f32_convert_i64_u as i32] = 'f32.convert_i64_u';
  n[IrOp.i32_clz as i32] = 'i32.clz';
  n[IrOp.i32_ctz as i32] = 'i32.ctz';
  n[IrOp.i32_popcnt as i32] = 'i32.popcnt';
  n[IrOp.i64_clz as i32] = 'i64.clz';
  n[IrOp.i64_ctz as i32] = 'i64.ctz';
  n[IrOp.i64_popcnt as i32] = 'i64.popcnt';
  n[IrOp.f32_abs as i32] = 'f32.abs';
  n[IrOp.f32_ceil as i32] = 'f32.ceil';
  n[IrOp.f32_floor as i32] = 'f32.floor';
  n[IrOp.f32_nearest as i32] = 'f32.nearest';
  n[IrOp.f32_sqrt as i32] = 'f32.sqrt';
  n[IrOp.f32_trunc as i32] = 'f32.trunc';
  n[IrOp.f64_abs as i32] = 'f64.abs';
  n[IrOp.f64_ceil as i32] = 'f64.ceil';
  n[IrOp.f64_floor as i32] = 'f64.floor';
  n[IrOp.f64_nearest as i32] = 'f64.nearest';
  n[IrOp.f64_sqrt as i32] = 'f64.sqrt';
  n[IrOp.f64_trunc as i32] = 'f64.trunc';
  n[IrOp.f32_min as i32] = 'f32.min';
  n[IrOp.f32_max as i32] = 'f32.max';
  n[IrOp.f32_copysign as i32] = 'f32.copysign';
  n[IrOp.f64_min as i32] = 'f64.min';
  n[IrOp.f64_max as i32] = 'f64.max';
  n[IrOp.f64_copysign as i32] = 'f64.copysign';
  n[IrOp.i32_load as i32] = 'i32.load';
  n[IrOp.i32_load8_u as i32] = 'i32.load8_u';
  n[IrOp.i64_load as i32] = 'i64.load';
  n[IrOp.f32_load as i32] = 'f32.load';
  n[IrOp.f64_load as i32] = 'f64.load';
  n[IrOp.i64_store as i32] = 'i64.store';
  n[IrOp.f32_store as i32] = 'f32.store';
  n[IrOp.f64_store as i32] = 'f64.store';
  n[IrOp.memory_size as i32] = 'memory.size';
  n[IrOp.memory_grow as i32] = 'memory.grow';
  n[IrOp.i64_mul_wide_s as i32] = 'i64.mul_wide_s';
  n[IrOp.i64_mul_wide_u as i32] = 'i64.mul_wide_u';
  n[IrOp.i64_add128 as i32] = 'i64.add128';
  n[IrOp.i64_sub128 as i32] = 'i64.sub128';
  // The shape, not the instruction: the printer appends the wasm name
  // from the opcode immediate, so a dump reads `simd.binary i32x4.add`.
  n[IrOp.simd_unary as i32] = 'simd.unary';
  n[IrOp.simd_binary as i32] = 'simd.binary';
  n[IrOp.simd_ternary as i32] = 'simd.ternary';
  n[IrOp.simd_extract_lane as i32] = 'simd.extract_lane';
  n[IrOp.simd_replace_lane as i32] = 'simd.replace_lane';
  n[IrOp.simd_const as i32] = 'simd.const';
  n[IrOp.simd_shuffle as i32] = 'simd.shuffle';
  n[IrOp.simd_load as i32] = 'simd.load';
  n[IrOp.simd_store as i32] = 'simd.store';
  n[IrOp.simd_load_lane as i32] = 'simd.load_lane';
  n[IrOp.simd_store_lane as i32] = 'simd.store_lane';
  n[IrOp.ref_null as i32] = 'ref.null';
  n[IrOp.ref_is_null as i32] = 'ref.is_null';
  n[IrOp.ref_as_non_null as i32] = 'ref.as_non_null';
  n[IrOp.ref_eq as i32] = 'ref.eq';
  n[IrOp.ref_test as i32] = 'ref.test';
  n[IrOp.ref_cast as i32] = 'ref.cast';
  n[IrOp.ref_func as i32] = 'ref.func';
  n[IrOp.extern_convert_any as i32] = 'extern.convert_any';
  n[IrOp.any_convert_extern as i32] = 'any.convert_extern';
  n[IrOp.i32_store as i32] = 'i32.store';
  n[IrOp.i32_store8 as i32] = 'i32.store8';
  n[IrOp.struct_new as i32] = 'struct.new';
  n[IrOp.struct_new_default as i32] = 'struct.new_default';
  n[IrOp.struct_get as i32] = 'struct.get';
  n[IrOp.struct_set as i32] = 'struct.set';
  n[IrOp.array_new as i32] = 'array.new';
  n[IrOp.array_new_data as i32] = 'array.new_data';
  n[IrOp.array_new_fixed as i32] = 'array.new_fixed';
  n[IrOp.array_get as i32] = 'array.get';
  n[IrOp.array_get_u as i32] = 'array.get_u';
  n[IrOp.array_get_s as i32] = 'array.get_s';
  n[IrOp.array_set as i32] = 'array.set';
  n[IrOp.array_copy as i32] = 'array.copy';
  n[IrOp.array_len as i32] = 'array.len';
  n[IrOp.global_get as i32] = 'global.get';
  n[IrOp.global_set as i32] = 'global.set';
  n[IrOp.var_get as i32] = 'var.get';
  n[IrOp.var_set as i32] = 'var.set';
  n[IrOp.str_lit as i32] = 'str.lit';
  n[IrOp.iface_pack as i32] = 'iface.pack';
  n[IrOp.iface_vtable as i32] = 'iface.vtable';
  n[IrOp.iface_instance as i32] = 'iface.instance';
  n[IrOp.call as i32] = 'call';
  n[IrOp.call_ref as i32] = 'call_ref';
  n[IrOp.mv_get as i32] = 'mv.get';
  n[IrOp.br as i32] = 'br';
  n[IrOp.br_if as i32] = 'br_if';
  n[IrOp.br_table as i32] = 'br_table';
  n[IrOp.br_on_cast as i32] = 'br_on_cast';
  n[IrOp.br_on_cast_fail as i32] = 'br_on_cast_fail';
  n[IrOp.try_br as i32] = 'try_br';
  n[IrOp.ret as i32] = 'ret';
  n[IrOp.ret_multi as i32] = 'ret.multi';
  n[IrOp.ret_call as i32] = 'ret.call';
  n[IrOp.ret_call_ref as i32] = 'ret.call_ref';
  n[IrOp.throw as i32] = 'throw';
  n[IrOp.unreachable as i32] = 'unreachable';
  n[IrOp.yield_ as i32] = 'yield';
  n[IrOp.await_ as i32] = 'await';
  return n;
}

let irOpNames = buildIrOpNames();

export function irOpName(op: IrOp): String {
  let raw = op as i32;
  if (raw >= 0 && raw < irOpNames.length) {
    let name = irOpNames[raw];
    if (name.length > 0) {
      return name;
    }
  }
  return `op#${raw}`;
}

/**
 * The users of every value of a body, packed: value `v`'s users are
 * `list[start[v] .. start[v + 1])`. One table per body rather than one
 * list per instruction, which constant propagation, scalar
 * replacement, jump threading and the escape analysis each built on
 * every visit — 128M lists in an -O2 compile of the zena module.
 */
export final class IrUseLists {
  start: GrowableArray<i32>;
  list: GrowableArray<i32>;
  new(this.start, this.list);

  count(v: i32): i32 {
    return this.start[v + 1] - this.start[v];
  }

  at(v: i32, k: i32): i32 {
    return this.list[this.start[v] + k];
  }
}

/**
 * Reusable lists for a pass's per-body tables. A pass takes what it
 * needs (`i32`, `bool`) inside a scope (`enter` … `exit`), and the
 * scope's end returns every list taken in it, cleared but keeping
 * its buffer, so a table sized to the body is allocated once per
 * compile rather than once per visit: those tables, pushed from
 * empty on every visit of every pass, were a third of what an -O2
 * compile allocated as small lists and most of another tenth as the
 * growth of large ones. A list taken in a scope must not outlive it;
 * a loop that takes lists per iteration scopes each iteration.
 */
let retainLimit = 262144;

export final class IrScratch {
  #freeI32 = new Array<GrowableArray<i32>>();
  #freeBool = new Array<GrowableArray<boolean>>();
  #takenI32 = new Array<GrowableArray<i32>>();
  #takenBool = new Array<GrowableArray<boolean>>();
  /** Pairs of taken counts at each open scope. */
  #scopes = new Array<i32>();

  enter(): void {
    this.#scopes.push(this.#takenI32.length);
    this.#scopes.push(this.#takenBool.length);
  }

  /**
   * Ends the scope. A list that grew past `retainLimit` entries is
   * dropped rather than pooled: one large function would otherwise
   * leave its tables in the pool for the rest of the compile.
   */
  exit(): void {
    let bools = this.#scopes.pop();
    let ints = this.#scopes.pop();
    while (this.#takenBool.length > bools) {
      let list = this.#takenBool.pop();
      if (list.length <= retainLimit) {
        list.clear();
        this.#freeBool.push(list);
      }
    }
    while (this.#takenI32.length > ints) {
      let list = this.#takenI32.pop();
      if (list.length <= retainLimit) {
        list.clear();
        this.#freeI32.push(list);
      }
    }
  }

  /** An empty i32 list for the current scope. */
  i32(): GrowableArray<i32> {
    let list = if (this.#freeI32.length > 0) this.#freeI32.pop() else new Array<i32>();
    this.#takenI32.push(list);
    return list;
  }

  /** An empty boolean list for the current scope. */
  bool(): GrowableArray<boolean> {
    let list = if (this.#freeBool.length > 0) this.#freeBool.pop() else new Array<boolean>();
    this.#takenBool.push(list);
    return list;
  }
}

/** The use lists of `body`'s non-nop instructions, in `scratch`'s scope. */
export function buildUseLists(body: IrBody, scratch: IrScratch): IrUseLists {
  let count = body.instCount();
  let start = scratch.i32();
  for (var i = 0; i <= count; i += 1) {
    start.push(0);
  }
  let operands = scratch.i32();
  // Count users per value into start[v + 1], then prefix-sum, so the
  // second pass places each user at its value's cursor.
  for (var i = 0; i < count; i += 1) {
    if (body.op(i) == IrOp.nop) {
      continue;
    }
    operands.clear();
    body.appendValueOperands(i, operands);
    for (let v in operands) {
      if (v >= 0 && v < count) {
        start[v + 1] = start[v + 1] + 1;
      }
    }
  }
  for (var v = 0; v < count; v += 1) {
    start[v + 1] = start[v + 1] + start[v];
  }
  let total = start[count];
  let list = scratch.i32();
  for (var i = 0; i < total; i += 1) {
    list.push(0);
  }
  let next = scratch.i32();
  for (var v = 0; v < count; v += 1) {
    next.push(start[v]);
  }
  for (var i = 0; i < count; i += 1) {
    if (body.op(i) == IrOp.nop) {
      continue;
    }
    operands.clear();
    body.appendValueOperands(i, operands);
    for (let v in operands) {
      if (v >= 0 && v < count) {
        list[next[v]] = i;
        next[v] = next[v] + 1;
      }
    }
  }
  return new IrUseLists(start, list);
}
VersionPublishedDependenciesApproved by
0.0.2-preview.1 2026-11-19