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

29.9 KiB Raw
import { HashMap } from 'zena:collections';
/**
 * Inlining (docs/design/optimization-pipeline.md §Inlining): a direct
 * call to an eligible callee splices the callee into the caller and
 * replaces the call's value with the callee's return value.
 *
 * Two splice shapes:
 *
 * - **Straight-line.** A single-block callee ending in `ret` copies
 *   its instructions into the call's block at the call site. No
 *   control flow is created; the copied instructions simply live where
 *   the call was, inside whatever protected region it was in.
 * - **General.** Any other callee copies every block as a new caller
 *   block; every `ret` becomes a `br` to a fresh continuation block,
 *   whose parameter is the call's value and whose body is the rest of
 *   the call's block. The call's block ends in a `br` to the copied
 *   entry.
 *
 * A callee returning several values (an iterator's `next()`) inlines
 * the same way with one value per result: the continuation takes one
 * parameter per result, `ret_multi` branches with all of them, and
 * the call's `mv_get` projections become those parameters (or, in a
 * straight-line splice, the returned values themselves). A tail call
 * to a multi-value target — the interface trampoline's shape — copies
 * as the call, its projections, and the branch carrying them.
 *
 * Both paths pre-assign ids for every copied instruction before
 * copying, so operand lookups never depend on within-block order
 * matching id order — a previously inlined body has spliced ids in
 * the middle of its blocks.
 *
 * What never inlines: callees with `try_br` (splicing a protected
 * region inside another is the emitter risk ir.md §15 names),
 * `tail return` (its constant-stack guarantee must not silently
 * become a growing one), suspensions, and
 * self-recursion. A budget on the callee's real instruction count and
 * two per-caller caps (size, splices per sweep) bound growth; chains
 * and mutual recursion resolve across the driver's rounds.
 *
 * Determinism: callers in module function order, sites in block and
 * instruction order, callee lookup by identity map — no iteration
 * over hash containers.
 */
import { String, i32ToString } from 'zena:core';
import { IrBlock, IrBody, IrOp, IrRefFunc, IrScratch } from './ir.zena';
import {
  WasmModule, WasmFunction, WasmSignature, asWasmSignature,
} from '../wasm-module.zena';
import { ValType } from '../wasm.zena';
import { EscapeSummaries } from './escape.zena';
import { isPresentWordName } from '../codegen-utils.zena';

/**
 * Callee real-instruction budgets (nops and returns excluded). A
 * straight-line body costs its instructions minus the call overhead
 * it replaces; a body with control flow also costs a continuation
 * block and its branches, and duplicates more on every round it
 * reaches, so its budget is tighter. At 48 for both, the self-compile
 * at -O2 came out 2.5x the -O1 size.
 */
let straightBudget = 12;
let generalBudget = 16;
/**
 * A body with control flow inlines under generalBudget only when it
 * has one direct call site in the module (its body moves rather than
 * duplicates; harvest deletes the original) or is tiny. At
 * generalBudget for every site count, the self-compile at -O2 was
 * 27% larger than -O1 for no measurable speed over the straight-line
 * tier alone.
 */
let generalTinyBudget = 6;
/**
 * The budget when an argument makes inlining pay: the argument is an
 * object allocated in the caller whose only use is this call, and the
 * callee's parameter does not escape (escape.zena). After inlining,
 * every use of that object is in one body, so the forwarding rules
 * replace its field reads, calls through it become direct, and the
 * allocation is deleted. That is the `map`-over-a-closure shape.
 *
 * The same budget applies to a call to an exploded core
 * (explode.zena) that passes a constant presence mask, which is what a
 * record literal argument becomes: after inlining, every presence test
 * on the mask folds. Without it, a constructor called with a record
 * literal, inlined at -O2 under the allocation rule, would stop being
 * inlined once explosion removed the allocation.
 */
let argumentBudget = 64;
/**
 * A caller takes general splices only while it is under twice its
 * size at the start of the sweep (plus a little room for small
 * callers); the round cap bounds growth across sweeps.
 */
let growthFactor = 2;
let growthFloor = 64;
/** General splices into one caller per sweep. */
let splicesPerSweep = 32;
/**
 * Splices of one callee into one caller per sweep. A recursive callee's
 * copy contains a call to itself, which the sweep would otherwise keep
 * unrolling up to the coarser caps.
 */
let splicesPerCallee = 4;

/**
 * The callee's real instruction count when eligible, or -1.
 */
function inlinableSize(body: IrBody): i32 {
  if (body.blocks.length == 0) {
    return -1;
  }
  var count = 0;
  for (let blk in body.blocks) {
    if (blk.insts.length == 0) {
      return -1;
    }
    for (let inst in blk.insts) {
      let op = body.op(inst);
      if (op == IrOp.nop || op == IrOp.ret || op == IrOp.ret_multi) {
        continue;
      }
      if (op == IrOp.ret_call || op == IrOp.ret_call_ref) {
        // A tail call becomes an ordinary call at the splice. At a
        // plain call site that costs no stack depth: the callee's
        // frame is gone and the target's frame takes its place. Only
        // a tail-call site keeps a constant-stack guarantee, and
        // those sites are never inlined.
        if (tailCallSignature(body, inst) == null) {
          return -1;
        }
        count += 1;
        continue;
      }
      if (op == IrOp.try_br || op == IrOp.yield_ || op == IrOp.await_) {
        return -1;
      }
      count += 1;
    }
  }
  return count;
}

/** A single block ending in a return or tail call: the straight-line shape. */
function isStraightLine(body: IrBody): boolean {
  if (body.blocks.length != 1) {
    return false;
  }
  let insts = body.blocks[0].insts;
  let op = body.op(insts[insts.length - 1]);
  return op == IrOp.ret || op == IrOp.ret_multi || op == IrOp.ret_call ||
      op == IrOp.ret_call_ref;
}

function tailCallSignature(body: IrBody, inst: i32): WasmSignature | null {
  if (body.op(inst) == IrOp.ret_call) {
    let r = body.refTable[body.b[inst]];
    if (r is IrRefFunc) {
      return r.target.signature;
    }
    return null;
  }
  let callee = body.extra[body.a[inst]];
  let t = body.resultType(callee);
  if (t == null) {
    return null;
  }
  return asWasmSignature(t);
}

/**
 * Runs one inline sweep over every body. `changed[i]` is set for each
 * caller that had a site inlined (the driver re-runs cleanup on
 * those). Returns the number of sites inlined.
 */
export function runInline(wasm: WasmModule, bodies: GrowableArray<IrBody>,
    changed: GrowableArray<boolean>, escapes: EscapeSummaries,
    scratch: IrScratch): i32 {
  let bodyIndex = wasm.functionIndex();
  // Direct call sites per callee, tail calls included, over the module
  // as it stands at the start of the sweep.
  let siteCounts = new Array<i32>(bodies.length);
  for (var i = 0; i < bodies.length; i += 1) {
    siteCounts.push(0);
  }
  for (let body in bodies) {
    let n = body.instCount();
    for (var inst = 0; inst < n; inst += 1) {
      let op = body.op(inst);
      if (op == IrOp.call || op == IrOp.ret_call) {
        let idx = calleeBodyFor(body, inst, bodyIndex);
        if (idx >= 0) {
          siteCounts[idx] += 1;
        }
      }
    }
  }
  // inlinableSize per callee, computed on first use and forgotten
  // once a body has taken splices: walking the callee at every call
  // site was 44% of an -O2 compile.
  let sizes = new Array<i32>(bodies.length);
  for (var i = 0; i < bodies.length; i += 1) {
    sizes.push(-2);
  }
  var total = 0;
  for (var i = 0; i < bodies.length; i += 1) {
    scratch.enter();
    let n = inlineIntoBody(bodies[i], bodyIndex, bodies, i, siteCounts,
        escapes, sizes, scratch);
    scratch.exit();
    if (n > 0) {
      changed[i] = true;
      sizes[i] = -2;
      total += n;
    }
  }
  return total;
}

/**
 * Per-splice state: the callee's tables appended to the caller, and
 * the id every callee instruction (params included) maps to.
 */
final class Splice {
  caller: IrBody;
  callee: IrBody;
  var typeOffset = 0;
  var refOffset = 0;
  var varOffset = 0;
  map: GrowableArray<i32>;
  new(this.caller, this.callee, scratch: IrScratch) : map = scratch.i32() {
    this.typeOffset = this.caller.typeTable.length;
    for (let t in this.callee.typeTable) {
      this.caller.typeTable.push(t);
    }
    this.refOffset = this.caller.refTable.length;
    for (let r in this.callee.refTable) {
      this.caller.refTable.push(r);
    }
    this.varOffset = this.caller.varTypes.length;
    for (let vt in this.callee.varTypes) {
      this.caller.varTypes.push(vt);
    }
    let n = this.callee.instCount();
    for (var i = 0; i < n; i += 1) {
      this.map.push(-1);
    }
  }

  mapValue(v: i32): i32 {
    if (v < 0) {
      return v;
    }
    let mapped = this.map[v];
    if (mapped < 0) {
      throw new Error('inline: callee operand has no copy');
    }
    return mapped;
  }

  /** A fresh `param` instruction of the callee param's type. */
  newParam(calleeParam: i32, block: i32): i32 {
    let id = this.caller.opcode.length;
    this.caller.opcode.push(IrOp.param as i32);
    this.caller.typeId.push(this.callee.typeId[calleeParam] + this.typeOffset);
    this.caller.a.push(-1);
    this.caller.b.push(-1);
    this.caller.instBlock.push(block);
    return id;
  }

  /**
   * The callee's tail call `ci` as an ordinary call appended to the
   * caller: same arguments (mapped), the target's single result as
   * the value, or no value for a void target.
   */
  newCallFromTailCall(ci: i32, block: i32): i32 {
    let op = this.callee.op(ci);
    let av = this.callee.a[ci];
    let sig = tailCallSignature(this.callee, ci);
    if (sig == null) {
      throw new Error('inline: tail call without a signature');
    }
    var ty = -1;
    if (sig.returns.length == 1) {
      this.caller.typeTable.push(sig.returns[0]);
      ty = this.caller.typeTable.length - 1;
    }
    let idx = this.caller.extra.length;
    var newB = -1;
    var newOp = IrOp.call;
    if (op == IrOp.ret_call) {
      let argc = this.callee.extra[av];
      this.caller.extra.push(argc);
      var i = 0;
      while (i < argc) {
        this.caller.extra.push(this.mapValue(this.callee.extra[av + 1 + i]));
        i += 1;
      }
      newB = this.callee.b[ci] + this.refOffset;
    } else {
      newOp = IrOp.call_ref;
      this.caller.extra.push(this.mapValue(this.callee.extra[av]));
      let argc = this.callee.extra[av + 1];
      this.caller.extra.push(argc);
      var i = 0;
      while (i < argc) {
        this.caller.extra.push(this.mapValue(this.callee.extra[av + 2 + i]));
        i += 1;
      }
    }
    let id = this.caller.opcode.length;
    this.caller.opcode.push(newOp as i32);
    this.caller.typeId.push(ty);
    this.caller.a.push(idx);
    this.caller.b.push(newB);
    this.caller.instBlock.push(block);
    return id;
  }

  /** Projection `k` of a multi-result call, of the given type. */
  newMvGet(call: i32, k: i32, vt: ValType, block: i32): i32 {
    this.caller.typeTable.push(vt);
    let id = this.caller.opcode.length;
    this.caller.opcode.push(IrOp.mv_get as i32);
    this.caller.typeId.push(this.caller.typeTable.length - 1);
    this.caller.a.push(call);
    this.caller.b.push(k);
    this.caller.instBlock.push(block);
    return id;
  }

  /**
   * The callee's tail call `ci` copied as a call whose results are the
   * returned list: the call itself for one result, its projections
   * for several, nothing for none. Every instruction goes on `out`.
   */
  newCallResults(ci: i32, block: i32, out: GrowableArray<i32>): GrowableArray<i32> {
    let results = new Array<i32>();
    let callId = this.newCallFromTailCall(ci, block);
    out.push(callId);
    let sig = tailCallSignature(this.callee, ci);
    if (sig == null) {
      throw new Error('inline: tail call without a signature');
    }
    if (sig.returns.length == 1) {
      results.push(callId);
    } else {
      for (var k = 0; k < sig.returns.length; k += 1) {
        let p = this.newMvGet(callId, k, sig.returns[k], block);
        out.push(p);
        results.push(p);
      }
    }
    return results;
  }

  /** A `br target(args)` terminator appended to the caller. */
  newBr(target: i32, args: GrowableArray<i32>, block: i32): i32 {
    let idx = this.caller.extra.length;
    this.caller.extra.push(target);
    this.caller.extra.push(args.length);
    for (let a in args) {
      this.caller.extra.push(a);
    }
    let id = this.caller.opcode.length;
    this.caller.opcode.push(IrOp.br as i32);
    this.caller.typeId.push(-1);
    this.caller.a.push(idx);
    this.caller.b.push(-1);
    this.caller.instBlock.push(block);
    return id;
  }
}

function nopOut(body: IrBody, inst: i32) {
  body.opcode[inst] = IrOp.nop as i32;
  body.typeId[inst] = -1;
  body.a[inst] = -1;
  body.b[inst] = -1;
}

function inlineIntoBody(caller: IrBody, bodyIndex: HashMap<WasmFunction, i32>,
    bodies: GrowableArray<IrBody>, callerIdx: i32,
    siteCounts: GrowableArray<i32>, escapes: EscapeSummaries,
    sizes: GrowableArray<i32>, scratch: IrScratch): i32 {
  var count = 0;
  var generalSplices = 0;
  let perCallee = new Map<i32, i32>();
  let sizeCap = caller.instCount() * growthFactor + growthFloor;
  // Use counts of the caller's values as the sweep starts, for the
  // only-use-is-this-call test. Values the sweep creates are past the
  // end and never qualify.
  let useCount = scratch.i32();
  let originalCount = caller.instCount();
  for (var i = 0; i < originalCount; i += 1) {
    useCount.push(0);
  }
  let operands = scratch.i32();
  for (var i = 0; i < originalCount; i += 1) {
    while (operands.length > 0) {
      operands.pop();
    }
    caller.appendValueOperands(i, operands);
    for (let o in operands) {
      if (o >= 0 && o < originalCount) {
        useCount[o] += 1;
      }
    }
  }
  let freshArgument = (calleeIdx: i32, args: GrowableArray<i32>): boolean => {
    for (var k = 0; k < args.length; k += 1) {
      let a = args[k];
      if (a < 0 || a >= originalCount || useCount[a] != 1) {
        continue;
      }
      let op = caller.op(a);
      if (op != IrOp.struct_new && op != IrOp.iface_pack) {
        continue;
      }
      if (!escapes.paramEscapes(calleeIdx, k)) {
        return true;
      }
    }
    return false;
  };
  let constantPresence = (inst: i32, args: GrowableArray<i32>): boolean => {
    let r = caller.refTable[caller.b[inst]];
    if (!(r is IrRefFunc)) {
      return false;
    }
    let spec = r.target.explosion;
    if (spec == null || spec.core !== r.target) {
      return false;
    }
    var slot = 0;
    for (let d in spec.params) {
      if (d == null) {
        slot += 1;
        continue;
      }
      for (let field in d.fields) {
        let name = field.name;
        if (name != null && isPresentWordName(name) && slot < args.length) {
          let a = args[slot];
          if (a >= 0 && caller.op(a) == IrOp.const_i64) {
            return true;
          }
        }
        slot += 1;
      }
    }
    return false;
  };
  // repl maps an inlined call to its replacement value. It grows on
  // demand: a general splice copies a callee body into new blocks the
  // sweep goes on to visit, so a copied call (with a fresh, larger
  // id) can itself be inlined and replaced.
  let repl = scratch.i32();
  let growRepl = () => {
    while (repl.length < caller.instCount()) {
      repl.push(repl.length);
    }
  };
  growRepl();
  let canon = (v: i32) => {
    var c = v;
    while (c >= 0 && c < repl.length && repl[c] != c) {
      c = repl[c];
    }
    return c;
  };

  // Blocks are appended by general splices (the copied callee blocks
  // and the continuation), and the continuation holds the rest of the
  // split block, so the loop re-reads the block count and moves on to
  // the continuation after a split.
  for (var b = 0; b < caller.blocks.length; b += 1) {
    let blk = caller.blocks[b];
    if (endsInThrow(caller, blk.insts)) {
      continue;
    }
    var j = 0;
    while (j < blk.insts.length) {
      let inst = blk.insts[j];
      if (caller.op(inst) != IrOp.call) {
        j += 1;
        continue;
      }
      let calleeIdx = calleeBodyFor(caller, inst, bodyIndex);
      if (calleeIdx < 0 || calleeIdx == callerIdx) {
        j += 1;
        continue;
      }
      let callee = bodies[calleeIdx];
      var size = sizes[calleeIdx];
      if (size == -2) {
        size = inlinableSize(callee);
        sizes[calleeIdx] = size;
      }
      if (size < 0) {
        j += 1;
        continue;
      }
      let params = callee.blocks[0].params;
      let extraIdx = caller.a[inst];
      let argc = caller.extra[extraIdx];
      if (argc != params.length) {
        j += 1;
        continue;
      }
      let args = new Array<i32>(argc);
      for (var p = 0; p < argc; p += 1) {
        args.push(canon(caller.extra[extraIdx + 1 + p]));
      }
      // Policy: the plain budgets first; then the argument rule, which
      // allows a larger body when this call's arguments make it pay.
      var allowed = if (isStraightLine(callee)) {
        size <= straightBudget
      } else {
        size <= generalBudget &&
            (siteCounts[calleeIdx] == 1 || size <= generalTinyBudget)
      };
      if (!allowed && size <= argumentBudget &&
          (freshArgument(calleeIdx, args) || constantPresence(inst, args))) {
        allowed = true;
      }
      if (!allowed) {
        j += 1;
        continue;
      }

      let sig = calleeSignature(caller, inst);
      if (sig == null) {
        j += 1;
        continue;
      }
      // The call's values map to the splice's results. A call that is
      // a value itself maps to the first result; its mv_get
      // projections, when it has any, map to the results by index.
      // Both can be true of different calls to a one-result function:
      // lowering emits the projection form wherever a call site is
      // written for several results (an iterator whose element is
      // zero-width has a one-lane next()). A projection that is
      // nowhere (deleted as unused) needs nothing.
      let callIsValue = caller.typeId[inst] >= 0;
      let mapResults = (results: GrowableArray<i32>) => {
        if (results.length != sig.returns.length) {
          throw new Error('inline: ' + i32ToString(results.length) +
              ' results for a callee returning ' +
              i32ToString(sig.returns.length) + ' (' +
              calleeName(caller, inst) + ')');
        }
        growRepl();
        if (results.length == 0) {
          return;
        }
        if (callIsValue) {
          repl[inst] = results[0];
        }
        let total = caller.instCount();
        for (var i = 0; i < total; i += 1) {
          if (caller.op(i) == IrOp.mv_get && caller.a[i] == inst) {
            let k = caller.b[i];
            if (k >= 0 && k < results.length) {
              repl[i] = results[k];
              nopOut(caller, i);
            }
          }
        }
      };

      if (isStraightLine(callee)) {
        scratch.enter();
        mapResults(spliceStraight(caller, callee, b, j, inst, args, scratch));
        scratch.exit();
        countCopiedCalls(callee, calleeIdx, bodyIndex, siteCounts);
        count += 1;
        // The copies were inserted before the call; skip past them
        // and the nop-ed call.
        j = blk.insts.length;
        continue;
      }

      var soFar = 0;
      if (let (true, seen) = perCallee.get(calleeIdx)) {
        soFar = seen;
      }
      if (caller.instCount() > sizeCap ||
          generalSplices >= splicesPerSweep ||
          soFar >= splicesPerCallee) {
        j += 1;
        continue;
      }
      perCallee[calleeIdx] = soFar + 1;
      scratch.enter();
      mapResults(spliceGeneral(caller, callee, b, j, inst, args, sig, scratch));
      scratch.exit();
      countCopiedCalls(callee, calleeIdx, bodyIndex, siteCounts);
      count += 1;
      generalSplices += 1;
      // The rest of this block moved to the continuation, which the
      // outer loop reaches in turn.
      j = blk.insts.length;
    }
  }

  if (count > 0) {
    let total = caller.instCount();
    for (var i = 0; i < total; i += 1) {
      if (caller.op(i) != IrOp.nop) {
        caller.rewriteValueOperands(i, canon);
      }
    }
  }
  return count;
}

/**
 * Straight-line splice: the callee's instructions are copied into
 * block `b` in place of the call at index `j`. Returns the ids the
 * call's values map to, one per result.
 */
function spliceStraight(caller: IrBody, callee: IrBody, b: i32, j: i32,
    inst: i32, args: GrowableArray<i32>, scratch: IrScratch): GrowableArray<i32> {
  let sp = new Splice(caller, callee, scratch);
  let params = callee.blocks[0].params;
  for (var p = 0; p < params.length; p += 1) {
    sp.map[params[p]] = args[p];
  }
  let calleeBlk = callee.blocks[0];
  let term = calleeBlk.insts[calleeBlk.insts.length - 1];
  // Pre-assign ids in copy order, then copy in the same order.
  let order = scratch.i32();
  var next = caller.instCount();
  for (let ci in calleeBlk.insts) {
    if (ci == term || callee.op(ci) == IrOp.nop) {
      continue;
    }
    sp.map[ci] = next;
    next += 1;
    order.push(ci);
  }
  let identity = (blockId: i32) => blockId;
  let copied = scratch.i32();
  for (let ci in order) {
    let newId = caller.copyFrom(callee, ci, (v) => sp.mapValue(v),
        sp.typeOffset, sp.refOffset, sp.varOffset, identity);
    if (newId != sp.map[ci]) {
      throw new Error('inline: copied id does not match its assignment');
    }
    caller.instBlock[newId] = b;
    copied.push(newId);
  }
  var results = scratch.i32();
  if (callee.op(term) == IrOp.ret) {
    let retVal = callee.a[term];
    if (retVal >= 0) {
      results.push(sp.mapValue(retVal));
    }
  } else if (callee.op(term) == IrOp.ret_multi) {
    let idx = callee.a[term];
    let argc = callee.extra[idx];
    for (var k = 0; k < argc; k += 1) {
      results.push(sp.mapValue(callee.extra[idx + 1 + k]));
    }
  } else {
    // A tail call: the call's own results are the returned values.
    results = sp.newCallResults(term, b, copied);
  }
  nopOut(caller, inst);
  // Rebuild the block: prefix, copies, the nop-ed call, suffix.
  let blk = caller.blocks[b];
  let rebuilt = scratch.i32();
  for (var k = 0; k < blk.insts.length; k += 1) {
    if (k == j) {
      for (let c in copied) {
        rebuilt.push(c);
      }
    }
    rebuilt.push(blk.insts[k]);
  }
  while (blk.insts.length > 0) {
    blk.insts.pop();
  }
  for (let r in rebuilt) {
    blk.insts.push(r);
  }
  return results;
}

/**
 * General splice: every callee block becomes a new caller block, each
 * `ret` a `br` to a continuation block that takes the call's values as
 * its parameters and the rest of block `b` as its body. Returns the
 * continuation parameters, one per result of `sig`.
 */
function spliceGeneral(caller: IrBody, callee: IrBody, b: i32, j: i32,
    inst: i32, args: GrowableArray<i32>, sig: WasmSignature,
    scratch: IrScratch): GrowableArray<i32> {
  let sp = new Splice(caller, callee, scratch);
  let nb = callee.blocks.length;
  let blockBase = caller.blocks.length;
  for (var k = 0; k < nb; k += 1) {
    caller.blocks.push(new IrBlock());
  }
  let cont = new IrBlock();
  let contId = caller.blocks.length;
  caller.blocks.push(cont);
  let mapBlock = (blockId: i32) => blockBase + blockId;

  // Entry params are the arguments; every other block's params are
  // fresh param instructions on the copied block.
  let entryParams = callee.blocks[0].params;
  for (var p = 0; p < entryParams.length; p += 1) {
    sp.map[entryParams[p]] = args[p];
  }
  for (var k = 1; k < nb; k += 1) {
    let dst = caller.blocks[blockBase + k];
    for (let cp in callee.blocks[k].params) {
      let id = sp.newParam(cp, blockBase + k);
      sp.map[cp] = id;
      dst.params.push(id);
    }
  }

  // Continuation parameters: the call's values. A call that is a value
  // itself lends its type; otherwise the signature's return types.
  let results = scratch.i32();
  let resultCount = sig.returns.length;
  for (var k = 0; k < resultCount; k += 1) {
    var ty = caller.typeId[inst];
    if (ty < 0 || resultCount > 1) {
      caller.typeTable.push(sig.returns[k]);
      ty = caller.typeTable.length - 1;
    }
    let id = caller.opcode.length;
    caller.opcode.push(IrOp.param as i32);
    caller.typeId.push(ty);
    caller.a.push(-1);
    caller.b.push(-1);
    caller.instBlock.push(contId);
    cont.params.push(id);
    results.push(id);
  }

  // Pre-assign ids for every copied instruction (returns become
  // branches created during the copy, at the same position), then
  // copy in that order.
  var next = caller.instCount();
  let order = scratch.i32();
  for (var k = 0; k < nb; k += 1) {
    for (let ci in callee.blocks[k].insts) {
      let op = callee.op(ci);
      if (op == IrOp.nop) {
        continue;
      }
      sp.map[ci] = next;
      // A tail call copies as the call, one projection per result
      // when there are several, and the branch to the continuation
      // carrying the values.
      if (op == IrOp.ret_call || op == IrOp.ret_call_ref) {
        next += 2 + (if (resultCount > 1) resultCount else 0);
      } else {
        next += 1;
      }
      order.push(ci);
    }
  }
  for (let ci in order) {
    let dstBlock = mapBlock(callee.instBlock[ci]);
    let op = callee.op(ci);
    var newId = -1;
    if (op == IrOp.ret) {
      let brArgs = scratch.i32();
      let rv = callee.a[ci];
      if (rv >= 0 && results.length > 0) {
        brArgs.push(sp.mapValue(rv));
      }
      newId = sp.newBr(contId, brArgs, dstBlock);
    } else if (op == IrOp.ret_multi) {
      let brArgs = scratch.i32();
      let idx = callee.a[ci];
      let argc = callee.extra[idx];
      for (var k = 0; k < argc; k += 1) {
        brArgs.push(sp.mapValue(callee.extra[idx + 1 + k]));
      }
      newId = sp.newBr(contId, brArgs, dstBlock);
    } else if (op == IrOp.ret_call || op == IrOp.ret_call_ref) {
      let made = scratch.i32();
      let values = sp.newCallResults(ci, dstBlock, made);
      for (let m in made) {
        caller.blocks[dstBlock].insts.push(m);
      }
      let brArgs = scratch.i32();
      if (results.length > 0) {
        for (let v in values) {
          brArgs.push(v);
        }
      }
      let brId = sp.newBr(contId, brArgs, dstBlock);
      if (made[0] != sp.map[ci] || brId != sp.map[ci] + made.length) {
        throw new Error('inline: copied id does not match its assignment');
      }
      caller.blocks[dstBlock].insts.push(brId);
      continue;
    } else {
      newId = caller.copyFrom(callee, ci, (v) => sp.mapValue(v),
          sp.typeOffset, sp.refOffset, sp.varOffset, mapBlock);
      caller.instBlock[newId] = dstBlock;
    }
    if (newId != sp.map[ci]) {
      throw new Error('inline: copied id does not match its assignment');
    }
    caller.blocks[dstBlock].insts.push(newId);
  }

  // Split block b at the call: the suffix moves to the continuation,
  // the call becomes a nop left in the continuation, and b ends in a
  // branch to the copied entry.
  let blk = caller.blocks[b];
  let prefix = new Array<i32>(j);
  for (var k = 0; k < j; k += 1) {
    prefix.push(blk.insts[k]);
  }
  nopOut(caller, inst);
  cont.insts.push(inst);
  caller.instBlock[inst] = contId;
  for (var k = j + 1; k < blk.insts.length; k += 1) {
    let moved = blk.insts[k];
    cont.insts.push(moved);
    caller.instBlock[moved] = contId;
  }
  while (blk.insts.length > 0) {
    blk.insts.pop();
  }
  for (let pinst in prefix) {
    blk.insts.push(pinst);
  }
  let noArgs = new Array<i32>();
  blk.insts.push(sp.newBr(blockBase, noArgs, b));
  return results;
}

/**
 * The body index of a call's target when it is a known local function;
 * -1 otherwise (imports, wrappers this module never lowered).
 */
/**
 * A block whose terminator throws or traps runs only on the way out of
 * the function by an exception, so a copy of a callee there buys
 * nothing and costs its size at every such site: every `new Error(...)`
 * in a `throw` would take a copy of the error's constructor and of
 * `captureStackTrace`.
 */
function endsInThrow(body: IrBody, insts: GrowableArray<i32>): boolean {
  if (insts.length == 0) {
    return false;
  }
  let op = body.op(insts[insts.length - 1]);
  return op == IrOp.throw || op == IrOp.unreachable;
}

/**
 * A splice of a callee with several call sites copies its direct calls
 * into the caller, so each function they name has one call site more
 * than the sweep counted. Without the update, a function whose only
 * call was in `callee` would still count one site, and the one-site
 * rule, which inlines a body because it moves rather than copies,
 * would inline it into every copy. A callee with one site moves
 * instead, and its calls move with it: the counts stay, so a chain of
 * one-site functions still collapses into its caller in one sweep. A
 * tail call counts too: the splice makes it an ordinary call.
 */
function countCopiedCalls(callee: IrBody, calleeIdx: i32,
    bodyIndex: HashMap<WasmFunction, i32>, siteCounts: GrowableArray<i32>): void {
  if (siteCounts[calleeIdx] <= 1) {
    return;
  }
  let n = callee.instCount();
  for (var inst = 0; inst < n; inst += 1) {
    let op = callee.op(inst);
    if (op == IrOp.call || op == IrOp.ret_call) {
      let idx = calleeBodyFor(callee, inst, bodyIndex);
      if (idx >= 0) {
        siteCounts[idx] += 1;
      }
    }
  }
}

function calleeBodyFor(caller: IrBody, inst: i32,
    bodyIndex: HashMap<WasmFunction, i32>): i32 {
  let r = caller.refTable[caller.b[inst]];
  if (!(r is IrRefFunc)) {
    return -1;
  }
  if (let (true, idx) = bodyIndex.get(r.target)) {
    return idx;
  }
  return -1;
}

/** The signature of a direct call's target. */
function calleeSignature(caller: IrBody, inst: i32): WasmSignature | null {
  let r = caller.refTable[caller.b[inst]];
  if (r is IrRefFunc) {
    return r.target.signature;
  }
  return null;
}

/** The target's name, for error messages. */
function calleeName(caller: IrBody, inst: i32): String {
  let r = caller.refTable[caller.b[inst]];
  if (r is IrRefFunc) {
    let n = r.target.name;
    if (n != null) {
      return n;
    }
  }
  return '<unnamed>';
}
VersionPublishedDependenciesApproved by
0.0.2-preview.1 2026-11-19