compiler 0.0.2-preview.1
The Zena self-hosted compiler
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.jsonmanifest 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
96.6 KiB
Raw
/**
* ZIR → wasm emission (docs/design/ir.md §12). Values get wasm locals
* except where stack scheduling (#scheduleStack) keeps them on the wasm
* value stack; copy coalescing (#coalesceCopies) lets branch arguments
* share their target params' locals. The CFG is reconstructed into
* wasm's structured control flow with the dominator-based stackifier
* (Ramsey, "Beyond Relooper" — reducible CFGs only, which lowering
* guarantees).
*
* Layout of the algorithm:
* - doTree(X) emits the dominator subtree rooted at X. Loop headers wrap
* themselves in `loop`; merge children (>= 2 forward preds) each get a
* labeled `block` whose end is immediately followed by their own code.
* - Branch edges either `br` to a label (backward edges to loop headers,
* forward edges to merge nodes) or inline the target's subtree in
* place (targets with a single forward predecessor).
* - Branch arguments become local copies into the target's param locals.
* Coalescing turns most into identity moves, which #planMoves drops;
* residual moves are ordered so no source is clobbered before it is
* read, with a per-param temp breaking genuine cycles (param swaps).
*/
import { ValType, ValTypeVoid, ValTypeRef, ValTypeRefNull, ValTypeRefExtern, ValTypeExternRef, ValTypeAnyRef, ValTypeEqRef, ValTypeStructRef, ValTypeNullRef, WasmType, heapTypeToSigned, HeapType, valTypeEquals } from '../wasm.zena';
import { WasmModule, WasmFunction, WasmSignature, WasmArray } from '../wasm-module.zena';
import { WasmEmitter } from '../wasm-emitter.zena';
import {
IrBody, IrOp, IrSuccessor, IrRefFunc, IrRefGlobal, IrRefType, IrRefField, IrRefTag, irOpName, isUnaryNumericOp, isBinaryNumericOp, isCommutativeOp, isIrTerminator, simdExtraOperandCount, isWideArithOp, isWideMulOp, wideArithOpcode, IrScratch } from './ir.zena';
import { WasmStruct } from '../wasm-module.zena';
import { IrCfg } from './cfg.zena';
import { growable } from 'zena:core';
final class EmitFrame {
/** CFG block this label is the branch target of; -1 for if/else frames. */
blockId: i32;
isLoop: boolean;
new(this.blockId, this.isLoop);
}
export final class ZirFunctionEmitter {
wasm: WasmModule;
emitter: WasmEmitter;
func: WasmFunction;
body: IrBody;
cfg: IrCfg;
/** Per instruction id: assigned wasm local index, or -1. */
localOf = new Array<i32>();
/** Per block-param instruction id: cycle-breaking temp local, or -1. */
tempOf = new Array<i32>();
/** Per instruction id: copy-coalescing class representative. */
#classOf = new Array<i32>();
/**
* Residual copy sequence per branch edge, keyed by the edge's
* argStart (unique per successor record): flat (src, dst) local
* pairs. Edges whose moves all coalesced away have no entry.
*/
#movePlans = new Map<i32, GrowableArray<i32>>();
/** Locals beyond the signature params, in index order. */
localTypes = new Array<ValType>();
/**
* Per mutable variable id: its dedicated wasm local. Allocated
* before any SSA value gets one and never entered into a coalescing
* class, so nothing else can land in it — the whole point is that
* the stored value survives an unwind to a handler in this frame.
*/
#varLocal = new Array<i32>();
/** Multi-result call -> its mv_get projections, ascending index. */
#mvProjections = new Map<i32, GrowableArray<i32>>();
frames = new Array<EmitFrame>();
/**
* Stack-scheduled values (ir.md §12, first step): used exactly
* once, by the next emitting instruction in the block, as one of a
* LEADING run of its value operands whose producers sit immediately
* before it in operand order — such values stay on the wasm stack
* with no local, no set/get round-trip, and no nullable-local
* re-assert. `[1, 2, 3]` is three constants streamed straight into
* array.new_fixed; `a * b` streams both operands.
*/
streamed = new Array<boolean>();
/**
* Streamed values currently on the wasm stack, in push order, and
* how many of them the consuming instruction has already claimed
* through #pushValue. Claims run bottom-up — the scheduler only
* streams a LEADING operand run, so operand order is push order —
* and the queue resets once every pending value is claimed.
*/
pendingStreamed = new Array<i32>();
/**
* Per pending entry, the consumer it is owed to. Only that consumer
* may claim it — an INTERVENING instruction that also uses the
* value (a teed producer's other consumer) must read the local
* instead, or it would consume a stack slot that sits below its own
* other operands and call with its arguments swapped. Per entry
* rather than per value because one value can be read early for two
* consumers of the same chain (#prePush).
*/
pendingOwner = new Array<i32>();
/** Per streamed/teed producer: the consumer its on-stack copy is for. */
#streamedFor = new Array<i32>();
/**
* Leading operands pushed early. `i >= this.length` has a parameter
* first and a value produced right before the compare second, so no
* leading run streams and the length takes a set/get round trip. A
* parameter, a value already in a local, or a constant can be read
* at any point, so the scheduler reads such leading operands BEFORE
* the trailing run's producers — at the start of the chain of
* pending producers feeding the run, so they sit under everything
* the run pushes — and the run streams. Keyed by that chain-start
* instruction: the values to push, in order, and the consumer each
* is owed to (an outer consumer's values come first, deepest).
*/
#prePush = new Map<i32, GrowableArray<i32>>();
#prePushFor = new Map<i32, GrowableArray<i32>>();
/**
* Rematerialized constants: a numeric constant or ref.null gets no
* local and emits NOTHING at its definition — every #pushValue of it
* emits the constant inline instead. A local.get and an i32.const
* are the same size, so each use is free and each definition saves
* the local declaration and its local.set — and, unlike streaming,
* rematerialization is immune to GVN sharing a constant across uses
* (the shared `1` of an array literal and its loop increment). Edge
* args keep their locals: #planMoves copies locals, not values.
*/
remat = new Array<boolean>();
/**
* Whether each wasm local has had a set emitted, and whether emission
* is still in the function's straight-line PROLOGUE (no control
* frame opened yet — everything emitted so far runs exactly once,
* in order). Together they justify default-store elision: a fresh
* local already holds its type's default, so a prologue store of
* the default into a never-written local is a no-op (#259).
*/
#localEverSet = new Array<boolean>();
var #prologue = true;
/**
* Multi-use values consumed like streamed ones: the producer emits
* local.tee instead of local.set — the value both lands in its local
* (for the later uses) and stays on the stack for the adjacent
* consumer, which claims it through the same pending queue (#258).
*/
teed = new Array<boolean>();
/**
* Entry-block default-constant definitions — the candidates for
* prologue default-store elision. The stack scheduler treats them
* as non-emitting when scanning producer adjacency (they usually
* vanish); a candidate that FAILS the emission-time check (its
* coalesced local was already written) emits a balanced
* const+local.set, which is stack-net-zero and so cannot disturb a
* pending streamed run — the optimistic skip stays sound.
*/
#elisionCandidate = new Array<boolean>();
/**
* A `return` at the outermost level (no open frames) is emitted
* LAZILY: its values are pushed, and the opcode is written only if
* anything else follows. If nothing does, the function falls
* through to its `end` with the results on the stack — dropping
* both the `return` and the trailing `unreachable` filler, which
* for `return 42` is the difference between 39 bytes and the
* 37-byte ideal module.
*/
var #pendingTopReturn = false;
/** The instruction currently being emitted (diagnostics). */
var currentEmit = -1;
/**
* Live replay of the validator's scoped init-tracking for
* non-defaultable locals (ir.md §12.1), maintained DURING emission:
* #candTarget holds each extra local's would-be non-null heap
* target (null = not a candidate, or demoted), #ownerDepth the
* scope depth at which each local is currently initialized (-1 =
* uninitialized), #scopeSets the locals initialized per open scope.
* A get of an uninitialized candidate demotes it on the spot; copy
* edges accumulate for the end-of-body fixpoint
* (#finishNonNullLocals). All of it is off (#trackInit) when the
* static writer check leaves no candidates.
*/
#candTarget = new Array<WasmType | null>();
#ownerDepth = new Array<i32>();
#scopeSets = new Array<GrowableArray<i32>>();
#copyEdgeDst = new Array<i32>();
#copyEdgeSrc = new Array<i32>();
var #trackInit = false;
/** Source local of the #copyArgs move currently being emitted, or -1. */
var #copyRecordSrc = -1;
/** ZENA_ZIR_STATS: nullable ref locals graduated non-null / kept nullable. */
var graduatedLocals = 0;
var demotedLocals = 0;
/** Reusable per-function tables; the emission is one scope of it. */
scratch: IrScratch;
new(this.wasm, this.emitter, this.func, this.body, this.cfg, this.scratch);
emit(): void {
this.emitter.emitFunctionCodeStart(this.func);
var name = 'func' + i32ToString(this.func.index);
if (this.func.name != null) {
name = this.func.name as String;
}
this.emitter.emitFunctionSignatureStart(name, this.func.signature.index);
this.#allocLocals();
this.#initNonNullTracking();
this.#markParamsSet();
// The array is shared with the emitter, which assembles the
// locals declaration at emitFunctionCodeEnd — after
// #finishNonNullLocals has graduated what the init replay allows.
this.emitter.emitFunctionLocalsStart(this.localTypes);
this.#doTree(0);
// Every doTree leaf ends in a real terminator, but wasm validation
// resets to "reachable" after each block/if/loop `end`, so control
// structurally falls through to the function end with an empty
// stack. A trailing `unreachable` keeps result-typed functions
// valid — EXCEPT when the body's last emission was an outermost
// `return`, still pending here: dropping it leaves the results on
// the stack for the function's own `end`, which both returns them
// and keeps the fall-through valid.
if (this.#pendingTopReturn) {
this.#pendingTopReturn = false;
} else if (this.func.signature.returns.length > 0) {
this.emitter.emitUnreachable();
}
this.#finishNonNullLocals();
this.emitter.emitFunctionEnd();
this.emitter.emitFunctionCodeEnd(this.func);
}
#allocLocals(): void {
let {body} = this;
let paramCount = this.func.signature.params.length;
var i = 0;
while (i < body.instCount()) {
this.localOf.push(-1);
this.tempOf.push(-1);
this.streamed.push(false);
this.remat.push(false);
this.teed.push(false);
this.#elisionCandidate.push(false);
this.#streamedFor.push(-1);
i += 1;
}
this.#planRemat();
this.#scheduleStack();
let entryParams = body.blocks[0].params;
if (entryParams.length != paramCount) {
throw new Error('zir emit: entry block params (' +
i32ToString(entryParams.length) + ') do not match signature (' +
i32ToString(paramCount) + ')');
}
i = 0;
while (i < entryParams.length) {
this.localOf[entryParams[i]] = i;
i += 1;
}
// Mutable variables claim their locals first. They are never in
// #classOf, so coalescing cannot route an SSA value into one.
i = 0;
while (i < body.varTypes.length) {
this.#varLocal.push(paramCount + this.localTypes.length);
this.localTypes.push(this.#localTypeFor(body.varTypes[i]));
i += 1;
}
this.#coalesceCopies();
i = 0;
while (i < body.instCount()) {
if (body.producesValue(i) && this.localOf[i] < 0 &&
!this.streamed[i] && !this.remat[i]) {
let r = this.#classOf[i];
if (this.localOf[r] >= 0) {
this.localOf[i] = this.localOf[r];
} else {
let idx = paramCount + this.localTypes.length;
this.localTypes.push(this.#localTypeFor(body.resultType(i) as ValType));
this.localOf[r] = idx;
this.localOf[i] = idx;
}
}
if (body.op(i) == IrOp.mv_get) {
// Instruction ids ascend, and the builder emits projections in
// ascending result order, so each list arrives sorted.
let callInst = body.a[i];
if (let (true, list) = this.#mvProjections.get(callInst)) {
list.push(i);
} else {
let list = growable<i32>([i]);
this.#mvProjections[callInst] = list;
}
}
i += 1;
}
this.#planMoves();
}
/**
* Params arrive initialized by the caller — they never hold a
* "default" the prologue store elision could rely on.
*/
#markParamsSet(): void {
var pi = 0;
while (pi < this.func.signature.params.length) {
this.#markLocalSet(pi);
pi += 1;
}
}
/**
* Init-discipline local typing (ir.md §12.1): every nullable ref
* local wants its value's precise non-null type — reads then skip
* the ref.as_non_null re-assert (#261). Wasm allows a
* non-defaultable local exactly where the validator's scoped
* init-tracking proves every get follows a set: a set is forgotten
* at the `end` of its containing block — uniformly, so a local set
* in BOTH arms of an if still counts uninitialized after the join —
* while a set in an enclosing scope persists into nested blocks and
* past their ends. Rather than approximate that discipline, this
* replays it live as the single emission pass runs: scope, set, and
* get hooks maintain the validator's own init state, a get of an
* uninitialized candidate demotes it immediately, and the
* re-asserts — emitted optimistically through
* emitRemovableRefAsNonNull — are dropped from the output for the
* locals that graduate, when the emitter assembles the function at
* emitFunctionCodeEnd. The locals declaration is assembled there
* too, so the graduated types apply even though they are decided
* after the body.
*
* This sets up the tracking: the static writer check first — every
* value a producer stores (local.set/tee, multi-value projection,
* var_set) must already have the exact non-null type the local
* would declare — then the scope/owner structures, with everything
* off when no candidate survives.
*/
#initNonNullTracking(): void {
let {body} = this;
let paramCount = this.func.signature.params.length;
let extraCount = this.localTypes.length;
var li = 0;
while (li < extraCount) {
this.#candTarget.push(match (this.localTypes[li]) {
case ValTypeRefNull as r: r.target
case _: null
});
li += 1;
}
let count = body.instCount();
for (var i = 0; i < count; i += 1) {
if (body.producesValue(i) && !this.streamed[i] && !this.remat[i] &&
this.localOf[i] >= paramCount) {
this.#checkWriter(this.localOf[i] - paramCount,
body.resultType(i) as ValType);
}
if (body.op(i) == IrOp.var_set) {
this.#checkWriter(this.#varLocal[body.b[i]] - paramCount,
body.resultType(body.a[i]) as ValType);
}
}
li = 0;
while (li < extraCount) {
if (this.#candTarget[li] != null) {
this.#trackInit = true;
}
li += 1;
}
if (!this.#trackInit) {
return;
}
li = 0;
while (li < paramCount + extraCount) {
this.#ownerDepth.push(-1);
li += 1;
}
this.#scopeSets.push(new Array<i32>());
}
/** Demotes a candidate whose stored value is not exactly (ref target). */
#checkWriter(idx: i32, vt: ValType): void {
let t = this.#candTarget[idx];
if (t == null) {
return;
}
let ok = if (vt is ValTypeRef) {
(vt as ValTypeRef).target == (t as WasmType)
} else {
false
};
if (!ok) {
this.#candTarget[idx] = null;
}
}
/** A control scope opened (block, loop, try_table, if). */
#scopeOpened(): void {
if (!this.#trackInit) {
return;
}
this.#scopeSets.push(new Array<i32>());
}
/**
* The arm switch of an if: the then-arm's sets roll back, and the
* scope stays open at the same depth with a fresh set list.
*/
#scopeElse(): void {
this.#rollbackScope(false);
}
/** A control scope closed: its sets are forgotten, uniformly. */
#scopeClosed(): void {
this.#rollbackScope(true);
}
#rollbackScope(popScope: boolean): void {
if (!this.#trackInit) {
return;
}
// Depth works as the owner id because scopes are stack-like: an
// entry rolls back exactly when the scope that owns it closes.
let depth = this.#scopeSets.length - 1;
let list = this.#scopeSets[depth];
for (let l in list) {
if (this.#ownerDepth[l] == depth) {
this.#ownerDepth[l] = -1;
}
}
if (popScope) {
this.#scopeSets.pop();
} else {
this.#scopeSets[depth] = new Array<i32>();
}
}
/** A read of a local: an uninitialized candidate must stay nullable. */
#trackGet(l: i32): void {
if (!this.#trackInit) {
return;
}
let paramCount = this.func.signature.params.length;
if (this.#ownerDepth[l] < 0 && l >= paramCount) {
this.#candTarget[l - paramCount] = null;
}
}
/**
* Runs the copy fixpoint over the edges collected during emission,
* graduates the surviving candidates in localTypes, and tells the
* emitter which removable asserts to drop. Runs after the body,
* before the emitter assembles the function.
*/
#finishNonNullLocals(): void {
let paramCount = this.func.signature.params.length;
let extraCount = this.localTypes.length;
if (!this.#trackInit) {
var li = 0;
while (li < extraCount) {
if (this.localTypes[li] is ValTypeRefNull) {
this.demotedLocals += 1;
}
li += 1;
}
return;
}
// A #copyArgs move transfers the SOURCE local's declared type, so
// a destination graduates only when every source ends at the same
// non-null type — demotions cascade along copy chains (move temps
// included).
var changed = true;
while (changed) {
changed = false;
var c = 0;
while (c < this.#copyEdgeDst.length) {
let dstIdx = this.#copyEdgeDst[c] - paramCount;
if (this.#candTarget[dstIdx] != null) {
let src = this.#copyEdgeSrc[c];
let srcTarget: WasmType | null = if (src < paramCount) {
match (this.func.signature.params[src]) {
case ValTypeRef as r: r.target
case _: null
}
} else {
this.#candTarget[src - paramCount]
};
if (srcTarget == null ||
(srcTarget as WasmType) !=
(this.#candTarget[dstIdx] as WasmType)) {
this.#candTarget[dstIdx] = null;
changed = true;
}
}
c += 1;
}
}
let graduated = new Array<boolean>(paramCount);
var li = 0;
while (li < paramCount) {
graduated.push(false);
li += 1;
}
var any = false;
li = 0;
while (li < extraCount) {
var g = false;
if (this.localTypes[li] is ValTypeRefNull) {
let t = this.#candTarget[li];
if (t != null) {
this.localTypes[li] = new ValTypeRef(t as WasmType);
this.graduatedLocals += 1;
g = true;
any = true;
} else {
this.demotedLocals += 1;
}
}
graduated.push(g);
li += 1;
}
if (any) {
this.emitter.dropAssertsForLocals(graduated);
}
}
/**
* Copy coalescing over branch edges (ir.md §12): a branch argument
* and its target block param share one wasm local when their live
* ranges do not interfere — the argument's definition then writes
* the param's local directly, and the edge copy degenerates to an
* identity move that #planMoves drops. Classes are built with a
* union-find over every (arg, param) edge pair, guarded by an SSA
* liveness analysis: values may share a local only if neither is
* live just after the other's definition (uses read their operands
* before the definition writes, so a definition's own operands do
* not conflict). Entry params keep their exact signature locals —
* possibly non-nullable, unlike the nullable locals #localTypeFor
* hands out — so their classes never grow.
*/
#coalesceCopies(): void {
let {body} = this;
let count = body.instCount();
let {blocks} = body;
let nb = blocks.length;
let {streamed} = this;
let {localOf} = this;
// Decoded value operands (uses) per instruction, computed once and
// packed end to end: instruction i's are
// useList[useStart[i] .. useStart[i + 1]). One list rather than one
// per instruction, which was the compiler's single largest source
// of garbage.
let useStart = new Array<i32>(count + 1);
let useList = new Array<i32>(count * 2);
for (var i = 0; i < count; i += 1) {
useStart.push(useList.length);
body.appendValueOperands(i, useList);
}
useStart.push(useList.length);
// Position of each instruction within its block; params sit at -1,
// before every instruction. mv_get projections adopt their call's
// position: the call's emission is what writes projection locals,
// so their live ranges must start there.
let posOf = this.scratch.i32();
for (var i = 0; i < count; i += 1) {
posOf.push(-1);
}
for (let blk in blocks) {
for (var k = 0; k < blk.insts.length; k += 1) {
posOf[blk.insts[k]] = k;
}
}
for (var i = 0; i < count; i += 1) {
if (body.op(i) == IrOp.mv_get &&
body.instBlock[i] == body.instBlock[body.a[i]]) {
posOf[i] = posOf[body.a[i]];
}
}
// Block-granularity liveness bitsets, flattened [block * words + w].
// Sized up front: they are blocks x values bits, and a large
// function's four of them pushed from empty doubled through half a
// gigabyte of discarded buffers.
let words = (count + 31) >> 5;
// Fresh and sized up front rather than pooled: built once per
// function, and for a large function too big to keep around.
let liveIn = new Array<i32>(nb * words);
let liveOut = new Array<i32>(nb * words);
let defs = new Array<i32>(nb * words);
let upUse = new Array<i32>(nb * words);
for (var i = 0; i < nb * words; i += 1) {
liveIn.push(0);
liveOut.push(0);
defs.push(0);
upUse.push(0);
}
let bitGet = (arr: GrowableArray<i32>, blk: i32, v: i32) =>
(arr[blk * words + (v >> 5)] & (1 << (v & 31))) != 0;
let bitSet = (arr: GrowableArray<i32>, blk: i32, v: i32) => {
let at = blk * words + (v >> 5);
arr[at] = arr[at] | (1 << (v & 31));
};
var b = 0;
while (b < nb) {
let blk = blocks[b];
for (let p in blk.params) {
bitSet(defs, b, p);
}
for (let inst in blk.insts) {
if (body.producesValue(inst)) {
bitSet(defs, b, inst);
}
for (var ui = useStart[inst]; ui < useStart[inst + 1]; ui += 1) {
let v = useList[ui];
if (v >= 0 && v < count && body.instBlock[v] != b) {
bitSet(upUse, b, v);
}
}
}
b += 1;
}
// Backward fixpoint: liveOut(B) = union of liveIn over successors;
// liveIn(B) = upUse(B) | (liveOut(B) & ~defs(B)). A successor's
// params are its own defs, so they never flow back into liveOut —
// branch arguments are already uses at the predecessor's terminator.
var changed = true;
while (changed) {
changed = false;
b = nb - 1;
while (b >= 0) {
let blk = blocks[b];
if (blk.insts.length > 0) {
let term = blk.insts[blk.insts.length - 1];
if (isIrTerminator(body.op(term))) {
let n = body.successorCount(term);
for (var k = 0; k < n; k += 1) {
let target = body.extra[body.successorRecord(term, k)];
var w = 0;
while (w < words) {
let merged = liveOut[b * words + w] |
liveIn[target * words + w];
if (merged != liveOut[b * words + w]) {
liveOut[b * words + w] = merged;
changed = true;
}
w += 1;
}
}
}
}
var w = 0;
while (w < words) {
let vIn = upUse[b * words + w] |
(liveOut[b * words + w] & (defs[b * words + w] ^ -1));
if (vIn != liveIn[b * words + w]) {
liveIn[b * words + w] = vIn;
changed = true;
}
w += 1;
}
b -= 1;
}
}
// Is x live just after y's definition point?
let liveAtDef = (x: i32, y: i32): boolean => {
let yb = body.instBlock[y];
if (body.instBlock[x] == yb && posOf[x] > posOf[y]) {
return false; // x is defined later in the same block
}
if (bitGet(liveOut, yb, x)) {
return true;
}
let insts = blocks[yb].insts;
var k = posOf[y] + 1;
while (k < insts.length) {
let user = insts[k];
for (var ui = useStart[user]; ui < useStart[user + 1]; ui += 1) {
let v = useList[ui];
if (v == x) {
return true;
}
}
k += 1;
}
return false;
};
let interferes = (x: i32, y: i32): boolean => {
if (body.op(x) == IrOp.param && body.op(y) == IrOp.param &&
body.instBlock[x] == body.instBlock[y]) {
return true; // same-block params are simultaneously live at entry
}
return liveAtDef(x, y) || liveAtDef(y, x);
};
// The local a value's class would occupy (mirrors #localTypeFor).
let localShape = (v: i32): ValType => {
let vt = body.resultType(v) as ValType;
return match (vt) {
case ValTypeRef as r: new ValTypeRefNull(r.target)
case ValTypeRefExtern: new ValTypeExternRef()
case _: vt
};
};
let parent = this.#classOf;
for (var i = 0; i < count; i += 1) {
parent.push(i);
}
let find = (v: i32) => {
var c = v;
while (parent[c] != c) {
c = parent[c];
}
return c;
};
let membersOf = new Map<i32, GrowableArray<i32>>();
let members = (root: i32) => {
if (let (true, list) = membersOf.get(root)) {
return list;
}
let list = growable<i32>([root]);
membersOf[root] = list;
return list;
};
let tryUnion = (arg: i32, param: i32) => {
if (arg < 0 || arg >= count || !body.producesValue(arg) ||
streamed[arg] || this.remat[arg]) {
return;
}
let ra = find(arg);
let rp = find(param);
if (ra == rp) {
return;
}
if (!valTypeEquals(localShape(arg), localShape(param))) {
return;
}
let ma = members(ra);
let mp = members(rp);
// A pinned local (an entry param's signature slot) never merges.
for (let x in ma) {
if (localOf[x] >= 0) {
return;
}
}
for (let y in mp) {
if (localOf[y] >= 0) {
return;
}
}
for (let x in ma) {
for (let y in mp) {
if (interferes(x, y)) {
return;
}
}
}
parent[rp] = ra;
for (let y in mp) {
ma.push(y);
}
membersOf.delete(rp);
};
b = 0;
while (b < nb) {
let blk = blocks[b];
if (blk.insts.length > 0) {
let term = blk.insts[blk.insts.length - 1];
if (isIrTerminator(body.op(term))) {
let sN = body.successorCount(term);
for (var sK = 0; sK < sN; sK += 1) {
let sRec = body.successorRecord(term, sK);
let params = blocks[body.extra[sRec]].params;
var i = 0;
while (i < body.extra[sRec + 1]) {
tryUnion(body.extra[(sRec + 2) + i], params[i]);
i += 1;
}
}
}
}
b += 1;
}
// Flatten chains to final representatives (find tolerates the
// in-place rewrite: replacing a link with its root keeps roots).
for (var i = 0; i < count; i += 1) {
this.#classOf[i] = find(i);
}
}
/**
* Precomputes the residual copy sequence for every branch edge:
* identity moves (coalesced classes, or the same value passed
* through) are dropped, the rest are ordered so no source local is
* overwritten before it is read, and a genuine cycle — a loop
* swapping its own params — is broken by saving one param's old
* value to a per-param temp.
*/
#planMoves(): void {
let {body} = this;
let paramCount = this.func.signature.params.length;
for (let blk in body.blocks) {
if (blk.insts.length == 0) {
continue;
}
let term = blk.insts[blk.insts.length - 1];
if (!isIrTerminator(body.op(term))) {
continue;
}
let sN = body.successorCount(term);
for (var sK = 0; sK < sN; sK += 1) {
let sRec = body.successorRecord(term, sK);
let params = body.blocks[body.extra[sRec]].params;
if (params.length == 0) {
continue;
}
let srcL = new Array<i32>();
let dstL = new Array<i32>();
let paramIds = new Array<i32>();
var i = 0;
while (i < params.length) {
let arg = body.extra[(sRec + 2) + i];
let src = this.localOf[arg];
let dst = this.localOf[params[i]];
if (src < 0 || dst < 0) {
throw new Error('zir emit: branch argument %' + i32ToString(arg) +
' has no local');
}
if (src != dst) {
srcL.push(src);
dstL.push(dst);
paramIds.push(params[i]);
}
i += 1;
}
if (srcL.length == 0) {
continue;
}
let plan = new Array<i32>();
let done = new Array<boolean>();
i = 0;
while (i < srcL.length) {
done.push(false);
i += 1;
}
var remaining = srcL.length;
while (remaining > 0) {
var progressed = false;
i = 0;
while (i < srcL.length) {
if (!done[i]) {
// Emittable when no pending move still reads this dst.
var blocked = false;
var j = 0;
while (j < srcL.length) {
if (j != i && !done[j] && srcL[j] == dstL[i]) {
blocked = true;
}
j += 1;
}
if (!blocked) {
plan.push(srcL[i]);
plan.push(dstL[i]);
done[i] = true;
remaining -= 1;
progressed = true;
}
}
i += 1;
}
if (!progressed) {
// Cycle: save the first pending destination to its temp and
// redirect the readers of that local to the temp.
var k = 0;
while (done[k]) {
k += 1;
}
if (this.tempOf[paramIds[k]] < 0) {
this.tempOf[paramIds[k]] = paramCount + this.localTypes.length;
this.localTypes.push(this.#localTypeFor(
body.resultType(paramIds[k]) as ValType));
}
let t = this.tempOf[paramIds[k]];
plan.push(dstL[k]);
plan.push(t);
var j = 0;
while (j < srcL.length) {
if (!done[j] && srcL[j] == dstL[k]) {
srcL[j] = t;
}
j += 1;
}
}
}
this.#movePlans[(sRec + 2)] = plan;
}
}
}
/**
* Marks values that can live on the wasm stack: single use, by the
* immediately following instruction in the same block, as its first
* value operand, where that consumer's emission is known to push
* its first operand before anything else (the whitelist below).
* Everything is verified again at emission time — a violated
* schedule throws rather than emitting misordered stack code.
*/
/**
* Marks rematerializable constants (see `remat`). A constant used as
* a branch/edge ARGUMENT is exempt: edge copies (#planMoves,
* #copyArgs) move locals, so their sources need one.
*/
#planRemat(): void {
let {body} = this;
let count = body.instCount();
for (var i = 0; i < count; i += 1) {
let op = body.op(i);
if (op == IrOp.const_i32 || op == IrOp.const_i64 ||
op == IrOp.const_f32 || op == IrOp.const_f64 ||
op == IrOp.ref_null) {
this.remat[i] = true;
}
}
for (let blk in body.blocks) {
if (blk.insts.length == 0) { continue; }
let term = blk.insts[blk.insts.length - 1];
if (!isIrTerminator(body.op(term))) { continue; }
let sN = body.successorCount(term);
for (var sK = 0; sK < sN; sK += 1) {
let sRec = body.successorRecord(term, sK);
for (var ai = 0; ai < body.extra[sRec + 1]; ai += 1) {
let arg = body.extra[(sRec + 2) + ai];
if (arg >= 0 && arg < count) {
this.remat[arg] = false;
}
}
}
}
if (body.blocks.length > 0) {
for (let inst in body.blocks[0].insts) {
if (!this.remat[inst] && body.producesValue(inst) &&
this.#isDefaultConst(inst)) {
this.#elisionCandidate[inst] = true;
}
}
}
}
#scheduleStack(): void {
let {body} = this;
let count = body.instCount();
let useCount = this.scratch.i32();
for (var i = 0; i < count; i += 1) {
useCount.push(0);
}
let operands = this.scratch.i32();
for (var i = 0; i < count; i += 1) {
operands.clear();
body.appendValueOperands(i, operands);
for (let v in operands) {
if (v >= 0 && v < count) {
useCount[v] = useCount[v] + 1;
}
}
}
// A producer's on-stack copy can satisfy exactly ONE consumer: a
// teed value leaves one copy on the stack (later uses read the
// local), so a second consumer matching it in its prefix would
// find the copy already consumed and read its operands swapped.
let stackClaimed = this.scratch.bool();
for (var sc = 0; sc < count; sc += 1) {
stackClaimed.push(false);
}
// Where each instruction sits, for the early-read check below: a
// leading operand read before a chain must be defined before it.
let instBlock = this.scratch.i32();
let instPos = this.scratch.i32();
for (var ip = 0; ip < count; ip += 1) {
instBlock.push(-1);
instPos.push(-1);
}
let ops = this.scratch.i32();
for (var bi = 0; bi < body.blocks.length; bi += 1) {
let bl = body.blocks[bi];
for (var q = 0; q < bl.insts.length; q += 1) {
instBlock[bl.insts[q]] = bi;
instPos[bl.insts[q]] = q;
}
}
// Rematerialized constants and elision candidates emit nothing at
// their site, so they are invisible to emission adjacency, like
// nops.
let nonEmitting = (inst: i32) => {
let op = body.op(inst);
return op == IrOp.nop || op == IrOp.mv_get || this.remat[inst] ||
this.#elisionCandidate[inst];
};
for (var bi = 0; bi < body.blocks.length; bi += 1) {
let blk = body.blocks[bi];
let {insts} = blk;
for (var j = 0; j < insts.length; j += 1) {
let consumer = insts[j];
let cop = body.op(consumer);
if (cop == IrOp.nop || cop == IrOp.mv_get) { continue; }
if (!this.#streamsFirstOperand(cop)) { continue; }
ops.clear();
body.appendValueOperands(consumer, ops);
if (ops.length == 0) { continue; }
// A LEADING run of operands streams when its producers are
// exactly the emitting instructions immediately before the
// consumer, in operand order — their values then sit on the
// stack in push order, deepest first, and the consumer's
// remaining operand pushes land above them. The run must
// start at ops[0]: streamed values are the DEEPEST pushes, so
// only the leading operands can be streamed. Terminators are
// capped at one — their later "operands" can be branch args
// with copy semantics, which are not pushed.
let maxPrefix = if (isIrTerminator(cop)) 1 else ops.length;
// A commutative consumer whose natural order streams nothing
// gets a second attempt with its operands swapped: `total + x`
// puts the freshly-produced value SECOND, where a leading-run
// scheduler cannot reach it, and integer add/mul/bitwise and
// the equality ops mean the same thing either way. A
// successful swap is committed to the instruction itself.
var attempt = 0;
var matched = false;
while (attempt < 2 && !matched) {
if (attempt == 1) {
if (!isCommutativeOp(cop) || ops.length != 2 ||
ops[0] == ops[1]) {
break;
}
let tmp = ops[0];
ops[0] = ops[1];
ops[1] = tmp;
}
var prefixLen = if (maxPrefix < ops.length) maxPrefix else ops.length;
while (prefixLen > 0) {
var ok = true;
var scan = j;
var oi = prefixLen - 1;
while (oi >= 0) {
var p = scan - 1;
// Rematerialized constants emit nothing at their site, so
// they are invisible to emission adjacency, like nops.
while (p >= 0 && (body.op(insts[p]) == IrOp.nop ||
body.op(insts[p]) == IrOp.mv_get ||
this.remat[insts[p]] ||
this.#elisionCandidate[insts[p]])) {
p -= 1;
}
if (p < 0) { ok = false; break; }
let producer = insts[p];
if (producer != ops[oi] || !body.producesValue(producer) ||
body.op(producer) == IrOp.mv_get ||
stackClaimed[producer]) {
ok = false;
break;
}
scan = p;
oi -= 1;
}
if (ok) {
if (attempt == 1) {
let savedA = body.a[consumer];
body.a[consumer] = body.b[consumer];
body.b[consumer] = savedA;
}
for (var s = 0; s < prefixLen; s += 1) {
stackClaimed[ops[s]] = true;
this.#streamedFor[ops[s]] = consumer;
// Single-use: pure stream, no local. Multi-use: tee —
// the value lands in its local AND stays on the stack.
if (useCount[ops[s]] == 1) {
this.streamed[ops[s]] = true;
} else {
this.teed[ops[s]] = true;
}
}
matched = true;
break;
}
prefixLen -= 1;
}
attempt += 1;
}
if (matched || isIrTerminator(cop)) { continue; }
this.#scheduleTrailingRun(consumer, j, insts, bi, useCount,
stackClaimed, instBlock, instPos, nonEmitting);
}
}
}
/**
* The second shape (#prePush): a TRAILING run of operands produced
* immediately before the consumer, with every operand before the run
* readable early — a constant, or a value defined before the chain
* of pending producers that feeds the run. The longest such run
* wins. A terminator never gets here: its later operands can be
* branch arguments, which are not pushed.
*/
#scheduleTrailingRun(consumer: i32, j: i32, insts: GrowableArray<i32>,
blockIndex: i32, useCount: GrowableArray<i32>,
stackClaimed: GrowableArray<boolean>,
instBlock: GrowableArray<i32>, instPos: GrowableArray<i32>,
nonEmitting: (inst: i32) => boolean): void {
let {body} = this;
// The swap attempt above may have left `ops` reordered; decode
// the operands afresh.
let ops = new Array<i32>();
body.appendValueOperands(consumer, ops);
if (ops.length < 2) { return; }
var k = 1;
while (k < ops.length) {
var ok = true;
var scan = j;
var start = -1;
var oi = ops.length - 1;
while (oi >= k) {
var p = scan - 1;
while (p >= 0 && nonEmitting(insts[p])) {
p -= 1;
}
if (p < 0) { ok = false; break; }
let producer = insts[p];
if (producer != ops[oi] || !body.producesValue(producer) ||
body.op(producer) == IrOp.mv_get || stackClaimed[producer]) {
ok = false;
break;
}
scan = p;
oi -= 1;
}
if (ok) {
// Walk back over the pending producers feeding the run's first
// producer: the early reads go under all of them.
start = scan;
while (true) {
var p = start - 1;
while (p >= 0 && nonEmitting(insts[p])) {
p -= 1;
}
if (p < 0 || !(this.streamed[insts[p]] || this.teed[insts[p]])) {
break;
}
start = p;
}
for (var i = 0; i < k; i += 1) {
let v = ops[i];
if (this.remat[v]) { continue; }
// A streamed value has no local to read; a value defined at
// or after the chain start is not defined yet when the
// read would be emitted.
if (this.streamed[v] ||
(instBlock[v] == blockIndex && instPos[v] >= start)) {
ok = false;
break;
}
}
}
if (ok) {
let startInst = insts[start];
let pre = new Array<i32>();
let owners = new Array<i32>();
for (var i = 0; i < k; i += 1) {
pre.push(ops[i]);
owners.push(consumer);
}
// A chain already carrying early reads for an inner consumer
// (one whose result this run streams) keeps them after these:
// this consumer claims last, so its reads go deepest.
if (let (true, inner) = this.#prePush.get(startInst)) {
let innerOwners = this.#prePushFor[startInst];
for (var i = 0; i < inner.length; i += 1) {
pre.push(inner[i]);
owners.push(innerOwners[i]);
}
}
this.#prePush[startInst] = pre;
this.#prePushFor[startInst] = owners;
for (var s = k; s < ops.length; s += 1) {
stackClaimed[ops[s]] = true;
this.#streamedFor[ops[s]] = consumer;
if (useCount[ops[s]] == 1) {
this.streamed[ops[s]] = true;
} else {
this.teed[ops[s]] = true;
}
}
return;
}
k += 1;
}
}
/**
* The index in `insts` of the first instruction at or after `from`
* that emits code, or -1 when the block ends first. Nops (GVN
* residue) and mv_gets (their values materialize at their call)
* never touch the wasm stack, so emission-adjacency questions skip
* them.
*/
#nextEmittingIndex(insts: GrowableArray<i32>, from: i32): i32 {
var j = from;
while (j < insts.length && (this.body.op(insts[j]) == IrOp.nop ||
this.body.op(insts[j]) == IrOp.mv_get)) {
j += 1;
}
return if (j < insts.length) j else -1;
}
/**
* Consumers whose emission provably pushes the first value operand
* before anything else. Ops that interleave non-operand pushes
* (iface_pack's vtable global) or use copy semantics (branch args)
* stay off the list.
*/
#streamsFirstOperand(op: IrOp): boolean {
if (isIrTerminator(op)) {
// These terminators push their first decoded operand first,
// via #pushValue (a br_if condition, a returned/thrown value).
// br's operands are branch args — copy semantics — and try_br
// opens control structure before any operand.
// ret_call_ref is off for the same reason call_ref is: wasm
// pushes the callee funcref after the arguments, not before.
return op == IrOp.br_if || op == IrOp.ret || op == IrOp.ret_multi ||
op == IrOp.throw || op == IrOp.ret_call;
}
if (isUnaryNumericOp(op) || isBinaryNumericOp(op)) {
return true;
}
return op == IrOp.ref_cast || op == IrOp.ref_as_non_null ||
op == IrOp.ref_test || op == IrOp.ref_eq || op == IrOp.ref_is_null ||
op == IrOp.struct_get || op == IrOp.struct_set ||
op == IrOp.array_get || op == IrOp.array_get_u ||
op == IrOp.array_get_s ||
op == IrOp.array_len || op == IrOp.array_set ||
op == IrOp.call ||
// call_ref is OFF the list: its decode order is callee-first
// but wasm pushes the callee funcref LAST, after the args.
op == IrOp.struct_new || op == IrOp.array_new_fixed ||
op == IrOp.global_set || op == IrOp.var_set ||
op == IrOp.iface_instance ||
op == IrOp.iface_vtable ||
op == IrOp.i32_load || op == IrOp.i32_load8_u ||
op == IrOp.i64_load || op == IrOp.f32_load || op == IrOp.f64_load ||
op == IrOp.i32_store || op == IrOp.i32_store8 ||
op == IrOp.i64_store || op == IrOp.f32_store || op == IrOp.f64_store ||
// Every SIMD shape pushes its operands first and its immediates
// last, inside the instruction encoding. simd_const has no
// operand to stream, so it is left off.
op == IrOp.simd_unary || op == IrOp.simd_binary ||
op == IrOp.simd_ternary || op == IrOp.simd_extract_lane ||
op == IrOp.simd_replace_lane || op == IrOp.simd_shuffle ||
op == IrOp.simd_load || op == IrOp.simd_store ||
op == IrOp.simd_load_lane || op == IrOp.simd_store_lane ||
// The wide-arithmetic ops push every operand and take no
// immediate off the stack, so a leading run streams into them
// exactly as it does into a binary numeric.
isWideArithOp(op);
}
/**
* Non-nullable reference values are stored in nullable locals, and
* #pushValue re-asserts non-nullness on reads that need the declared
* type (docs/design/ir.md §12). Wasm locals CAN be non-defaultable
* when definitely assigned before use, but the validator's
* initialization tracking rolls back at each block `end` — and this
* every-value-a-local scheme routinely defines a value inside one
* structured block and reads it after that block closes (merge
* params are set on in-edges; values flow into dominated subtrees).
* Stack scheduling / local coalescing (ir.md §12) is the point where
* same-scope values can graduate to non-null locals.
*/
#localTypeFor(vt: ValType): ValType {
return match (vt) {
case ValTypeRef as r: new ValTypeRefNull(r.target)
case ValTypeRefExtern: new ValTypeExternRef()
case _: vt
};
}
/** True if the value's IR type is non-null but its local is nullable. */
#storedNullable(inst: i32): boolean {
let rt = this.body.resultType(inst);
if (!(rt is ValTypeRef) && !(rt is ValTypeRefExtern)) {
return false;
}
let l = this.localOf[inst];
// Signature params keep their declared (possibly non-null) types,
// and graduated locals (#planNonNullLocals) are declared at
// their precise non-null type — neither needs the re-assert.
if (l < this.func.signature.params.length) {
return false;
}
let lt = this.localTypes[l - this.func.signature.params.length];
return lt is ValTypeRefNull || lt is ValTypeExternRef;
}
/** Loads a value at its declared IR type. */
#pushValue(inst: i32): void {
// The first pending value owed to this consumer. Entries owed to
// an OUTER consumer (early reads, #prePush) sit below it on the
// stack and stay queued until that consumer claims them.
var qi = 0;
while (qi < this.pendingStreamed.length &&
this.pendingOwner[qi] != this.currentEmit) {
qi += 1;
}
if (qi < this.pendingStreamed.length && this.pendingStreamed[qi] == inst) {
// Already on the stack from a preceding instruction, at its
// declared IR type — no local, no re-assert. Claims run
// bottom-up: the consumer's operand order is the push order.
this.#removePending(qi);
return;
}
// A non-pending push while pendings are unclaimed is fine: a later
// streamed producer pushes its own operands ABOVE the earlier
// pending values and consumes them itself, netting one value on
// top — the pending prefix below is untouched. Only claiming out
// of order or reading a streamed value that is not pending (the
// localOf < 0 error below) is a schedule violation.
this.#emitRead(inst);
}
#removePending(index: i32): void {
for (var i = index + 1; i < this.pendingStreamed.length; i += 1) {
this.pendingStreamed[i - 1] = this.pendingStreamed[i];
this.pendingOwner[i - 1] = this.pendingOwner[i];
}
this.pendingStreamed.pop();
this.pendingOwner.pop();
}
/** Reads a value that is not on the stack: its constant, or its local. */
#emitRead(inst: i32): void {
if (this.remat[inst]) {
this.#emitConstInline(inst);
return;
}
if (this.localOf[inst] < 0) {
throw new Error('zir emit: streamed value %' + i32ToString(inst) +
' read outside its schedule by %' + i32ToString(this.currentEmit) +
' (' + irOpName(this.body.op(this.currentEmit)) + ') in ' +
(this.func.name ?? '?'));
}
this.#trackGet(this.localOf[inst]);
this.emitter.emitLocalGet(this.localOf[inst]);
if (this.#storedNullable(inst)) {
this.emitter.emitRemovableRefAsNonNull(this.localOf[inst]);
}
}
/** Emits a local.set, recording that the local no longer holds its default. */
#setLocal(idx: i32): void {
this.#markLocalSet(idx);
this.emitter.emitLocalSet(idx);
}
#markLocalSet(idx: i32): void {
if (this.#trackInit) {
if (this.#ownerDepth[idx] < 0) {
let depth = this.#scopeSets.length - 1;
this.#ownerDepth[idx] = depth;
this.#scopeSets[depth].push(idx);
}
if (this.#copyRecordSrc >= 0 &&
idx >= this.func.signature.params.length) {
this.#copyEdgeDst.push(idx);
this.#copyEdgeSrc.push(this.#copyRecordSrc);
}
}
while (this.#localEverSet.length <= idx) {
this.#localEverSet.push(false);
}
this.#localEverSet[idx] = true;
}
#localWasSet(idx: i32): boolean {
if (idx < 0 || idx >= this.#localEverSet.length) { return false; }
return this.#localEverSet[idx];
}
/** True for a constant of its type's default value (positive zero
* for floats — eliding a -0.0 store would change the value). */
#isDefaultConst(inst: i32): boolean {
let {body} = this;
let op = body.op(inst);
if (op == IrOp.const_i32) { return body.a[inst] == 0; }
if (op == IrOp.const_i64) { return body.constI64[body.a[inst]] == 0; }
if (op == IrOp.const_f32 || op == IrOp.const_f64) {
let v = body.constF64[body.a[inst]];
return v == 0.0 && 1.0 / v > 0.0;
}
return op == IrOp.ref_null;
}
/** Emits a rematerialized constant at its use site. */
#emitConstInline(inst: i32): void {
let {body} = this;
let op = body.op(inst);
if (op == IrOp.const_i32) {
this.emitter.emitI32Const(body.a[inst]);
} else if (op == IrOp.const_i64) {
this.emitter.emitI64Const(body.constI64[body.a[inst]]);
} else if (op == IrOp.const_f32) {
this.emitter.emitF32Const(body.constF64[body.a[inst]]);
} else if (op == IrOp.const_f64) {
this.emitter.emitF64Const(body.constF64[body.a[inst]]);
} else if (op == IrOp.ref_null) {
this.#emitRefNullInst(inst);
} else {
throw new Error('zir emit: %' + i32ToString(inst) +
' marked remat but is not a constant');
}
}
#doTree(x: i32): void {
if (this.cfg.isLoopHeader(x)) {
// Dominator children OUTSIDE the natural loop are its exits:
// they emit AFTER the loop `end`, behind labeled blocks, so a
// loop exit is one `br_if` instead of an if/else diamond
// carrying the exit code inside the loop body. Membership is a
// backward flood from the back-edge predecessors (everything
// that reaches a latch without passing the header is in the
// loop) — RPO ranges are not reliable here: the DFS can order
// an exit block between the header and the loop body.
let inLoop = new Array<boolean>(this.body.blocks.length);
var b = 0;
while (b < this.body.blocks.length) {
inLoop.push(false);
b += 1;
}
inLoop[x] = true;
let work = new Array<i32>();
for (var pK = 0; pK < this.cfg.predCount(x); pK += 1) {
let p = this.cfg.pred(x, pK);
if (this.cfg.rpoIndex[p] >= this.cfg.rpoIndex[x]) {
work.push(p);
}
}
while (work.length > 0) {
let m = work.pop();
if (!inLoop[m]) {
inLoop[m] = true;
for (var qK = 0; qK < this.cfg.predCount(m); qK += 1) {
let q = this.cfg.pred(m, qK);
work.push(q);
}
}
}
let inLoopMerge = new Array<i32>();
let exits = new Array<i32>();
for (var cK = 0; cK < this.cfg.domChildCount(x); cK += 1) {
let c = this.cfg.domChild(x, cK);
if (!inLoop[c]) {
exits.push(c);
} else if (this.cfg.isMergeNode(c)) {
inLoopMerge.push(c);
}
}
this.#loopWithExits(x, inLoopMerge, exits, exits.length);
} else {
let mergeChildren = new Array<i32>();
for (var cK = 0; cK < this.cfg.domChildCount(x); cK += 1) {
let c = this.cfg.domChild(x, cK);
if (this.cfg.isMergeNode(c)) {
mergeChildren.push(c);
}
}
this.#nodeWithin(x, mergeChildren, mergeChildren.length);
}
}
/**
* Opens one labeled block per loop exit (outermost = latest in RPO,
* mirroring #nodeWithin), emits the loop inside them, then each
* exit's subtree after its block's end.
*/
#loopWithExits(x: i32, inLoopMerge: GrowableArray<i32>, exits: GrowableArray<i32>,
count: i32): void {
if (count > 0) {
let y = exits[count - 1];
this.#flushPendingReturn();
this.#prologue = false;
this.frames.push(new EmitFrame(y, false));
this.#scopeOpened();
this.emitter.emitBlock(new ValTypeVoid());
this.#loopWithExits(x, inLoopMerge, exits, count - 1);
this.#scopeClosed();
this.emitter.emitEnd();
this.frames.pop();
this.#doTree(y);
return;
}
this.#flushPendingReturn();
this.#prologue = false;
this.frames.push(new EmitFrame(x, true));
this.#scopeOpened();
this.emitter.emitLoop(new ValTypeVoid());
this.#nodeWithin(x, inLoopMerge, inLoopMerge.length);
this.#flushPendingReturn();
this.#scopeClosed();
this.emitter.emitEnd();
this.frames.pop();
}
#nodeWithin(x: i32, mergeChildren: GrowableArray<i32>, count: i32): void {
// The node's own instructions emit BEFORE any merge-child wrapper
// opens: a basic block has no branches, so the labels are only
// needed from the terminator on. Hoisting matters for locals — a
// set inside a wrapper is rolled back by the validator's
// definite-assignment tracking at the wrapper's `end`, while a set
// in the enclosing scope persists into the wrappers and past their
// ends — so a def in this block stays init-visible through the
// whole dominated subtree and the merge subtrees emitted after it
// (ir.md §12.1, label placement). It also keeps the straight-line
// prologue open longer for default-store elision.
let blk = this.body.blocks[x];
// A trailing chain of streamed/teed producers feeds the terminator
// ON THE STACK; wasm frames cannot carry operands across a `block`
// boundary, so that tail must emit inside the wrappers, adjacent
// to its consumer. Non-emitting instructions (nops, mv_gets,
// rematerialized constants, elision candidates) ride along freely.
var tailStart = blk.insts.length - 1;
var t = tailStart - 1;
while (t >= 0) {
let inst = blk.insts[t];
let top = this.body.op(inst);
if (this.streamed[inst] || this.teed[inst] || top == IrOp.nop ||
top == IrOp.mv_get || this.remat[inst] ||
this.#elisionCandidate[inst]) {
tailStart = t;
t -= 1;
} else {
break;
}
}
var j = 0;
while (j < tailStart) {
this.#emitInst(blk.insts[j]);
j += 1;
}
this.#wrapMerges(x, mergeChildren, count, tailStart);
}
#wrapMerges(x: i32, mergeChildren: GrowableArray<i32>, count: i32,
tailStart: i32): void {
if (count > 0) {
let y = mergeChildren[count - 1];
this.#flushPendingReturn();
this.#prologue = false;
this.frames.push(new EmitFrame(y, false));
this.#scopeOpened();
this.emitter.emitBlock(new ValTypeVoid());
this.#wrapMerges(x, mergeChildren, count - 1, tailStart);
this.#flushPendingReturn();
this.#scopeClosed();
this.emitter.emitEnd();
this.frames.pop();
this.#doTree(y);
return;
}
let blk = this.body.blocks[x];
var j = tailStart;
while (j < blk.insts.length - 1) {
this.#emitInst(blk.insts[j]);
j += 1;
}
this.#emitTerminator(blk.insts[blk.insts.length - 1], x);
}
/** Writes a deferred outermost `return` because something follows it. */
#flushPendingReturn(): void {
if (this.#pendingTopReturn) {
this.#pendingTopReturn = false;
this.emitter.emitReturn();
}
}
#emitTerminator(inst: i32, from: i32): void {
this.#flushPendingReturn();
let {body} = this;
let op = body.op(inst);
if (this.pendingStreamed.length > 0) {
// ret / ret_multi / throw / br_if push their leading decoded
// operands first, through #pushValue, which claims pending
// values in order. Anything else with pending values is a
// schedule violation.
let operands = new Array<i32>();
body.appendValueOperands(inst, operands);
let pendingCount = this.pendingStreamed.length;
var ok = this.#streamsFirstOperand(op) &&
operands.length >= pendingCount;
if (ok) {
for (var pi = 0; pi < pendingCount; pi += 1) {
if (operands[pi] != this.pendingStreamed[pi]) {
ok = false;
}
}
}
if (!ok) {
throw new Error('zir emit: streamed value %' +
i32ToString(this.pendingStreamed[0]) +
' left on stack at terminator');
}
}
this.currentEmit = inst;
if (op == IrOp.ret) {
let value = body.a[inst];
if (value >= 0) {
this.#pushValue(value);
}
if (this.frames.length == 0) {
this.#pendingTopReturn = true;
} else {
this.emitter.emitReturn();
}
return;
}
if (op == IrOp.ret_multi) {
let idx = body.a[inst];
let argc = body.extra[idx];
for (var k = 0; k < argc; k += 1) {
this.#pushValue(body.extra[idx + 1 + k]);
}
if (this.frames.length == 0) {
this.#pendingTopReturn = true;
} else {
this.emitter.emitReturn();
}
return;
}
// A tail call is the whole exit: `return_call` transfers control,
// so nothing follows it and no `return` is written (tail-calls.md).
if (op == IrOp.ret_call) {
let argsIdx = body.a[inst];
let argc = body.extra[argsIdx];
for (var k = 0; k < argc; k += 1) {
this.#pushValue(body.extra[argsIdx + 1 + k]);
}
let ref = body.refTable[body.b[inst]];
if (!(ref is IrRefFunc)) {
throw new Error('zir emit: ret_call ref is not a function');
}
this.emitter.emitReturnCall(ref.target);
return;
}
if (op == IrOp.ret_call_ref) {
let idx = body.a[inst];
let callee = body.extra[idx];
let argc = body.extra[idx + 1];
for (var k = 0; k < argc; k += 1) {
this.#pushValue(body.extra[idx + 2 + k]);
}
this.#pushValue(callee);
this.emitter.emitReturnCallRef(this.#signatureOf(callee).index);
return;
}
if (op == IrOp.unreachable) {
this.emitter.emitUnreachable();
return;
}
if (op == IrOp.throw) {
let idx = body.a[inst];
let argc = body.extra[idx];
for (var k = 0; k < argc; k += 1) {
this.#pushValue(body.extra[idx + 1 + k]);
}
let ref = body.refTable[body.b[inst]];
if (!(ref is IrRefTag)) {
throw new Error('zir emit: throw ref kind');
}
this.emitter.emitThrow(ref.target.index);
return;
}
let succs = body.successors(inst);
if (op == IrOp.br) {
this.#doBranch(from, succs[0]);
return;
}
if (op == IrOp.try_br) {
let ref = body.refTable[body.a[inst]];
if (!(ref is IrRefTag)) {
throw new Error('zir emit: try_br ref kind');
}
// The body subtree must place INSIDE the try_table — a br to an
// outer label would leave the region unprotected. Lowering
// creates the body entry with this single forward edge, so this
// only guards emitter regressions.
if (this.cfg.rpoIndex[succs[0].target] <= this.cfg.rpoIndex[from] ||
this.cfg.isMergeNode(succs[0].target)) {
throw new Error('zir emit: try body is not inlineable');
}
// A recorded join that the body target dominates would be
// inlined INSIDE the try_table by the dominance placement below —
// the diverging-catch shape, where the join's only predecessor is
// the body's exit (issue #426). Open its label out here instead,
// so the body's normal completion brs out past the handler's
// reach, and emit its subtree after the region. A join the catch
// also reaches is a merge node handled by the ordinary wrappers
// (its frame is already open), and the dominance test is false
// for it anyway.
let join =
if (let (true, j) = this.body.tryJoin.get(inst)) j else -1;
let hoistJoin = join >= 0 &&
this.cfg.dominates(succs[0].target, join) &&
this.#findDepth(join) < 0;
if (hoistJoin) {
this.#flushPendingReturn();
this.#prologue = false;
this.frames.push(new EmitFrame(join, false));
this.#scopeOpened();
this.emitter.emitBlock(new ValTypeVoid());
}
// block $catch { try_table (catch tag -> $catch) { body } }
// catch-path... Exits from the body br straight to their
// targets (out through the try_table); nothing falls out of it,
// so the code after the inner `end` never runs.
this.#scopeOpened();
this.emitter.emitBlock(new ValTypeVoid());
this.#prologue = false;
this.frames.push(new EmitFrame(-1, false));
this.#scopeOpened();
this.emitter.emitTryTableCatch(new ValTypeVoid(),
ref.target.index, 0);
this.#prologue = false;
this.frames.push(new EmitFrame(-1, false));
this.#doBranch(from, succs[0]);
this.#scopeClosed();
this.emitter.emitEnd();
this.frames.pop();
this.#scopeClosed();
this.emitter.emitEnd();
this.frames.pop();
this.#doBranch(from, succs[1]);
if (hoistJoin) {
this.#flushPendingReturn();
this.#scopeClosed();
this.emitter.emitEnd();
this.frames.pop();
this.#doTree(join);
}
return;
}
if (op == IrOp.br_if) {
// Fast forms: when one arm is a copy-free br to an open label
// (typically a loop exit or back edge after coalescing), a bare
// br_if replaces the if/else diamond and the other arm's code
// continues in the current block.
let d0 = this.#findDepth(succs[0].target);
if (d0 >= 0 && this.#edgeHasNoMoves(succs[0])) {
this.#pushValue(body.a[inst]);
this.emitter.emitBrIf(d0);
this.#doBranch(from, succs[1]);
return;
}
let d1 = this.#findDepth(succs[1].target);
if (d1 >= 0 && this.#edgeHasNoMoves(succs[1])) {
this.#pushValue(body.a[inst]);
this.emitter.emitI32Eqz();
this.emitter.emitBrIf(d1);
this.#doBranch(from, succs[0]);
return;
}
this.#pushValue(body.a[inst]);
this.#scopeOpened();
this.emitter.emitIf(new ValTypeVoid());
this.#prologue = false;
this.frames.push(new EmitFrame(-1, false));
this.#doBranch(from, succs[0]);
this.#scopeElse();
this.emitter.emitElse();
this.#doBranch(from, succs[1]);
this.#scopeClosed();
this.emitter.emitEnd();
this.frames.pop();
return;
}
throw new Error('zir emit: unsupported terminator ' + irOpName(op));
}
#doBranch(from: i32, s: IrSuccessor): void {
this.#flushPendingReturn();
this.#copyArgs(s);
// Anything with an open frame (loop headers, merge nodes, loop
// exits placed after their loop) brs to its label.
let d = this.#findDepth(s.target);
if (d >= 0) {
this.emitter.emitBr(d);
return;
}
if (this.cfg.rpoIndex[s.target] <= this.cfg.rpoIndex[from] ||
this.cfg.isMergeNode(s.target)) {
throw new Error('zir emit: no enclosing label for b' +
i32ToString(s.target));
}
// Single forward predecessor: place the target's subtree right here.
this.#doTree(s.target);
}
/** True when the edge's copies all coalesced away (no move plan). */
#edgeHasNoMoves(s: IrSuccessor): boolean {
if (let (true, plan) = this.#movePlans.get(s.argStart)) {
return plan.length == 0;
}
return true;
}
#copyArgs(s: IrSuccessor): void {
// Copy semantics, not value reads: sources load raw (the target
// param's local is as nullable as the source's), and edges whose
// moves all coalesced away have no plan entry.
if (let (true, plan) = this.#movePlans.get(s.argStart)) {
var i = 0;
while (i < plan.length) {
if (this.#prologue && !this.#localWasSet(plan[i]) &&
!this.#localWasSet(plan[i + 1])) {
// Both locals still hold their type's default (never written,
// and in the prologue nothing has run twice), so the copy is
// default-over-default — a no-op.
i += 2;
continue;
}
this.#trackGet(plan[i]);
this.emitter.emitLocalGet(plan[i]);
this.#copyRecordSrc = plan[i];
this.#setLocal(plan[i + 1]);
this.#copyRecordSrc = -1;
i += 2;
}
}
}
#depthOf(target: i32): i32 {
var i = this.frames.length - 1;
var depth = 0;
while (i >= 0) {
if (this.frames[i].blockId == target) {
return depth;
}
depth += 1;
i -= 1;
}
throw new Error('zir emit: no enclosing label for b' + i32ToString(target));
}
/** Label depth for `target`, or -1 when it has no open frame. */
#findDepth(target: i32): i32 {
var i = this.frames.length - 1;
var depth = 0;
while (i >= 0) {
if (this.frames[i].blockId == target) {
return depth;
}
depth += 1;
i -= 1;
}
return -1;
}
#emitInst(inst: i32): void {
// Early reads scheduled at this chain start: pushed before the
// chain's own code, owed to the consumers that read past them.
// They go first, before the checks below that let an instruction
// emit nothing: the reads belong at the chain start whether or not
// the instruction there emits code.
if (let (true, pre) = this.#prePush.get(inst)) {
this.#flushPendingReturn();
let owners = this.#prePushFor[inst];
for (var i = 0; i < pre.length; i += 1) {
this.#emitRead(pre[i]);
this.pendingStreamed.push(pre[i]);
this.pendingOwner.push(owners[i]);
}
}
// A rematerialized constant emits at each USE (#emitConstInline),
// nothing at its definition.
if (this.remat[inst]) { return; }
// A default-value constant stored into a never-written local in the
// straight-line prologue is a no-op: the fresh local already holds
// the default, and nothing before this point can have run twice.
// Later reads load the untouched default from the local.
if (this.#prologue && this.body.producesValue(inst) &&
!this.streamed[inst] && this.localOf[inst] >= 0 &&
!this.#localWasSet(this.localOf[inst]) &&
this.#isDefaultConst(inst)) {
return;
}
this.#flushPendingReturn();
let {body} = this;
let op = body.op(inst);
this.currentEmit = inst;
match (op) {
case IrOp.nop: { return; }
case IrOp.param: { return; }
case IrOp.mv_get: {
// The multi-result call already stored this projection's local.
return;
}
case IrOp.const_i32: { this.emitter.emitI32Const(body.a[inst]); }
case IrOp.const_i64: {
this.emitter.emitI64Const(body.constI64[body.a[inst]]);
}
case IrOp.const_f32: {
this.emitter.emitF32Const(body.constF64[body.a[inst]]);
}
case IrOp.const_f64: {
this.emitter.emitF64Const(body.constF64[body.a[inst]]);
}
case IrOp.call: { this.#emitCallInst(inst); }
case IrOp.call_ref: { this.#emitCallRefInst(inst); }
case IrOp.global_get: {
this.emitter.emitGlobalGet(this.#globalIndexOf(inst));
}
case IrOp.global_set: {
this.#pushValue(body.a[inst]);
this.emitter.emitGlobalSet(this.#globalIndexOf(inst));
}
case IrOp.var_get: {
let vl = this.#varLocal[body.b[inst]];
this.#trackGet(vl);
this.emitter.emitLocalGet(vl);
// A non-null declared IR type re-asserts on the way out of the
// nullable local — the same round trip #pushValue does for SSA
// values. Dropped from the output if the var local graduates.
if (body.resultType(inst) is ValTypeRef) {
this.emitter.emitRemovableRefAsNonNull(vl);
}
}
case IrOp.var_set: {
this.#pushValue(body.a[inst]);
this.#setLocal(this.#varLocal[body.b[inst]]);
}
case IrOp.struct_new_default: {
this.emitter.emitStructNewDefault(this.#typeIndexOf(inst));
}
case IrOp.struct_new: { this.#emitStructNewInst(inst); }
case IrOp.struct_get: {
this.#pushValue(body.a[inst]);
let field = this.#fieldRef(body.b[inst]);
this.#requireIndexed(field.owner, 'struct_get owner');
this.emitter.emitStructGet(field.owner.index, this.#fieldIndexOf(field));
}
case IrOp.struct_set: {
let pairIdx = body.a[inst];
this.#pushValue(body.extra[pairIdx]);
this.#pushValue(body.extra[pairIdx + 1]);
let field = this.#fieldRef(body.b[inst]);
this.#requireIndexed(field.owner, 'struct_set owner');
this.emitter.emitStructSet(field.owner.index, this.#fieldIndexOf(field));
}
case IrOp.ref_func: {
let ref = body.refTable[body.b[inst]];
if (!(ref is IrRefFunc)) {
throw new Error('zir emit: ref_func ref kind');
}
let {target} = ref;
if (target.index < 0) {
// An unindexed target means reachability never saw this
// function, so it has no slot in the function section. The
// bare emitter assert names neither party; both are needed to
// tell which lowering path invented the reference.
throw new Error('zir emit: ref_func target has no index: ' +
(target.name ?? '<anonymous>') + ' [in ' +
(this.func.name ?? '<anonymous>') + ']');
}
this.emitter.emitRefFunc(target.index);
}
case IrOp.ref_null: { this.#emitRefNullInst(inst); }
case IrOp.ref_cast: { this.#emitRefCastInst(inst); }
case IrOp.ref_test: { this.#emitRefTestInst(inst); }
case IrOp.ref_is_null: {
this.#pushValue(body.a[inst]);
this.emitter.emitRefIsNull();
}
case IrOp.ref_as_non_null: {
this.#pushValue(body.a[inst]);
this.emitter.emitRefAsNonNull();
}
case IrOp.iface_pack: { this.#emitIfacePackInst(inst); }
case IrOp.iface_instance: { this.#emitIfaceFieldInst(inst, 0); }
case IrOp.iface_vtable: { this.#emitIfaceFieldInst(inst, 1); }
case IrOp.array_len: {
this.#pushValue(body.a[inst]);
this.emitter.emitArrayLen();
}
case IrOp.array_new: { this.#emitArrayNewInst(inst); }
case IrOp.array_new_data: { this.#emitArrayNewDataInst(inst); }
case IrOp.array_new_fixed: { this.#emitArrayNewFixedInst(inst); }
case IrOp.array_get: {
this.#pushValue(body.a[inst]);
this.#pushValue(body.b[inst]);
this.emitter.emitArrayGet(this.#arrayTargetOf(body.a[inst]).index);
}
case IrOp.array_get_u: {
this.#pushValue(body.a[inst]);
this.#pushValue(body.b[inst]);
this.emitter.emitArrayGetU(this.#arrayTargetOf(body.a[inst]).index);
}
case IrOp.array_get_s: {
this.#pushValue(body.a[inst]);
this.#pushValue(body.b[inst]);
this.emitter.emitArrayGetS(this.#arrayTargetOf(body.a[inst]).index);
}
case IrOp.array_set: { this.#emitArraySetInst(inst); }
case IrOp.array_copy: { this.#emitArrayCopyInst(inst); }
case IrOp.extern_convert_any: {
this.#pushValue(body.a[inst]);
this.emitter.emitExternConvertAny();
}
case IrOp.any_convert_extern: {
this.#pushValue(body.a[inst]);
this.emitter.emitAnyConvertExtern();
}
case IrOp.i32_store: { this.#emitMemStoreInst(inst); }
case IrOp.i32_store8: { this.#emitMemStoreInst(inst); }
case IrOp.i64_store: { this.#emitMemStoreInst(inst); }
case IrOp.f32_store: { this.#emitMemStoreInst(inst); }
case IrOp.f64_store: { this.#emitMemStoreInst(inst); }
case IrOp.i32_load: { this.#emitMemLoadInst(inst); }
case IrOp.i32_load8_u: { this.#emitMemLoadInst(inst); }
case IrOp.i64_load: { this.#emitMemLoadInst(inst); }
case IrOp.f32_load: { this.#emitMemLoadInst(inst); }
case IrOp.f64_load: { this.#emitMemLoadInst(inst); }
case IrOp.simd_unary: { this.#emitSimdInst(inst); }
case IrOp.simd_binary: { this.#emitSimdInst(inst); }
case IrOp.simd_ternary: { this.#emitSimdInst(inst); }
case IrOp.simd_extract_lane: { this.#emitSimdInst(inst); }
case IrOp.simd_replace_lane: { this.#emitSimdInst(inst); }
case IrOp.simd_const: { this.#emitSimdInst(inst); }
case IrOp.simd_shuffle: { this.#emitSimdInst(inst); }
case IrOp.simd_load: { this.#emitSimdInst(inst); }
case IrOp.simd_store: { this.#emitSimdInst(inst); }
case IrOp.simd_load_lane: { this.#emitSimdInst(inst); }
case IrOp.simd_store_lane: { this.#emitSimdInst(inst); }
case IrOp.memory_size: { this.emitter.emitMemorySize(); }
case IrOp.memory_grow: {
this.#pushValue(body.a[inst]);
this.emitter.emitMemoryGrow();
}
case IrOp.i64_mul_wide_s: { this.#emitWideArithInst(inst); }
case IrOp.i64_mul_wide_u: { this.#emitWideArithInst(inst); }
case IrOp.i64_add128: { this.#emitWideArithInst(inst); }
case IrOp.i64_sub128: { this.#emitWideArithInst(inst); }
case _: {
if (isUnaryNumericOp(op)) {
this.#pushValue(body.a[inst]);
this.#emitOp(op);
} else {
// Binary numerics: two inline value operands.
this.#pushValue(body.a[inst]);
this.#pushValue(body.b[inst]);
this.#emitOp(op);
}
}
}
if (body.producesValue(inst)) {
if (this.streamed[inst]) {
this.pendingStreamed.push(inst);
this.pendingOwner.push(this.#streamedFor[inst]);
} else if (this.teed[inst]) {
this.#markLocalSet(this.localOf[inst]);
this.emitter.emitLocalTee(this.localOf[inst]);
// local.tee returns the LOCAL's declared type, which is the
// nullable widening — re-assert for the on-stack consumer,
// exactly as #pushValue does for a local.get.
if (this.#storedNullable(inst)) {
this.emitter.emitRemovableRefAsNonNull(this.localOf[inst]);
}
this.pendingStreamed.push(inst);
this.pendingOwner.push(this.#streamedFor[inst]);
} else {
this.#setLocal(this.localOf[inst]);
}
}
}
/** The module index of the global-ref payload in slot b. */
#globalIndexOf(inst: i32): i32 {
let ref = this.body.refTable[this.body.b[inst]];
if (!(ref is IrRefGlobal)) {
throw new Error(`zir emit: ${irOpName(this.body.op(inst))} ref kind`);
}
return ref.target.index;
}
/**
* Throws if `t` was never assigned a type-section index — writing
* its -1 produces a module the engine rejects with an opaque
* `invalid heap type` at a byte offset, far from the cause.
*/
#requireIndexed(t: WasmType, what: String): void {
if (t.index < 0) {
let desc = if (t is WasmStruct) {
"struct " + (t.name ?? "unnamed")
} else if (t is WasmSignature) {
"signature"
} else if (t is WasmArray) {
"array"
} else {
"type"
};
throw new Error('zir emit: ' + what + ' references unemitted ' +
desc + ' [in ' + (this.func.name ?? '<anonymous>') + ']');
}
}
/** The module index of the type-ref payload in slot b. */
#typeIndexOf(inst: i32): i32 {
let ref = this.body.refTable[this.body.b[inst]];
if (!(ref is IrRefType)) {
throw new Error(`zir emit: ${irOpName(this.body.op(inst))} ref kind`);
}
let {target} = ref;
if (target.index < 0) {
// Writing -1 here produces a module V8 rejects with an opaque
// `Unknown heap type` at a byte offset; name the type instead.
let desc = if (target is WasmStruct) {
"struct " + (target.name ?? "unnamed")
} else if (target is WasmSignature) {
"signature"
} else {
"type"
};
throw new Error('zir emit: ' + irOpName(this.body.op(inst)) +
' references unemitted ' + desc + ' (index -1) [in ' +
(this.func.name ?? '<anonymous>') + ']');
}
return target.index;
}
#emitCallInst(inst: i32): void {
let {body} = this;
let argsIdx = body.a[inst];
let argc = body.extra[argsIdx];
for (var k = 0; k < argc; k += 1) {
this.#pushValue(body.extra[argsIdx + 1 + k]);
}
let ref = body.refTable[body.b[inst]];
match (ref) {
case IrRefFunc as f: {
this.emitter.emitCall(f.target);
}
case _: {
throw new Error('zir emit: call ref is not a function');
}
}
this.#storeMultiResults(inst);
}
#emitCallRefInst(inst: i32): void {
let {body} = this;
let idx = body.a[inst];
let callee = body.extra[idx];
let argc = body.extra[idx + 1];
for (var k = 0; k < argc; k += 1) {
this.#pushValue(body.extra[idx + 2 + k]);
}
this.#pushValue(callee);
this.emitter.emitCallRef(this.#signatureOf(callee).index);
this.#storeMultiResults(inst);
}
#emitStructNewInst(inst: i32): void {
let {body} = this;
let argsIdx = body.a[inst];
let argc = body.extra[argsIdx];
for (var k = 0; k < argc; k += 1) {
this.#pushValue(body.extra[argsIdx + 1 + k]);
}
this.emitter.emitStructNew(this.#typeIndexOf(inst));
}
#emitRefNullInst(inst: i32): void {
let vt = this.body.resultType(inst) as ValType;
match (vt) {
case ValTypeRefNull as r: {
this.#requireIndexed(r.target, 'ref.null');
this.emitter.emitRefNull(r.target.index);
}
case ValTypeAnyRef: { this.emitter.emitRefNull(heapTypeToSigned(HeapType.any)); }
case ValTypeEqRef: { this.emitter.emitRefNull(heapTypeToSigned(HeapType.eq)); }
case ValTypeStructRef: { this.emitter.emitRefNull(heapTypeToSigned(HeapType.struct)); }
case ValTypeNullRef: { this.emitter.emitRefNull(heapTypeToSigned(HeapType.none)); }
// `externref | null`: a null in the extern hierarchy.
case ValTypeExternRef: { this.emitter.emitRefNull(heapTypeToSigned(HeapType.extern)); }
case _: {
throw new Error('zir emit: ref.null type');
}
}
}
#funcName(): String {
return if (this.func.name != null) this.func.name as String else '<unnamed>';
}
#emitRefCastInst(inst: i32): void {
let {body} = this;
this.#pushValue(body.a[inst]);
match (body.typeTable[body.b[inst]]) {
case ValTypeRef as r: {
this.#requireIndexed(r.target, 'ref.cast');
this.emitter.emitRefCast(r.target.index);
}
case ValTypeRefNull as rn: {
this.#requireIndexed(rn.target, 'ref.cast null');
this.emitter.emitRefCastNull(rn.target.index);
}
case ValTypeEqRef: { this.emitter.emitRefCastEqNull(); }
case ValTypeStructRef: { this.emitter.emitRefCastStructNull(); }
case ValTypeNullRef: { this.emitter.emitRefCastNullNone(); }
case _: {
let kind = match (body.typeTable[body.b[inst]]) {
case ValTypeAnyRef: 'anyref'
case ValTypeVoid: 'void'
case _: 'a non-reference type'
};
throw new Error(`zir emit: ref.cast target kind ${kind} [in ${this.#funcName()}]`);
}
}
}
#emitRefTestInst(inst: i32): void {
let {body} = this;
this.#pushValue(body.a[inst]);
match (body.typeTable[body.b[inst]]) {
case ValTypeRef as r: {
this.#requireIndexed(r.target, 'ref.test');
this.emitter.emitRefTest(r.target.index);
}
case ValTypeRefNull as rn: {
this.#requireIndexed(rn.target, 'ref.test null');
this.emitter.emitRefTestNull(rn.target.index);
}
case _: {
throw new Error('zir emit: ref.test target kind');
}
}
}
#emitIfacePackInst(inst: i32): void {
let {body} = this;
this.#pushValue(body.a[inst]);
match (body.refTable[body.b[inst]]) {
case IrRefGlobal as g: { this.emitter.emitGlobalGet(g.target.index); }
case _: { throw new Error('zir emit: iface_pack ref kind'); }
}
match (body.resultType(inst)) {
case ValTypeRef as r: {
if (!(r.target is WasmStruct)) {
throw new Error('zir emit: iface_pack result kind');
}
this.emitter.emitStructNew((r.target as WasmStruct).index);
}
case _: { throw new Error('zir emit: iface_pack result kind'); }
}
}
/** Fat-pointer field read: 0 = instance, 1 = vtable. */
#emitIfaceFieldInst(inst: i32, fieldIdx: i32): void {
let {body} = this;
this.#pushValue(body.a[inst]);
let fatPtr = this.#structTargetOf(body.a[inst]);
this.emitter.emitStructGet(fatPtr.index, fieldIdx);
}
#emitArrayNewInst(inst: i32): void {
let {body} = this;
let pairIdx = body.a[inst];
let init = body.extra[pairIdx + 1];
let typeIndex = this.#typeIndexOf(inst);
if (init >= 0) {
// array.new pops (init value, length); default form pops length only.
this.#pushValue(init);
this.#pushValue(body.extra[pairIdx]);
this.emitter.emitArrayNew(typeIndex);
} else {
this.#pushValue(body.extra[pairIdx]);
this.emitter.emitArrayNewDefault(typeIndex);
}
}
#emitArrayNewDataInst(inst: i32): void {
let {body} = this;
let idx = body.a[inst];
this.#pushValue(body.extra[idx]);
this.#pushValue(body.extra[idx + 1]);
this.emitter.emitArrayNewData(this.#typeIndexOf(inst), body.extra[idx + 2]);
}
#emitArrayNewFixedInst(inst: i32): void {
let {body} = this;
let argsIdx = body.a[inst];
let argc = body.extra[argsIdx];
for (var k = 0; k < argc; k += 1) {
this.#pushValue(body.extra[argsIdx + 1 + k]);
}
this.emitter.emitArrayNewFixed(this.#typeIndexOf(inst), argc);
}
#emitArraySetInst(inst: i32): void {
let {body} = this;
let tripleIdx = body.a[inst];
this.#pushValue(body.extra[tripleIdx]);
this.#pushValue(body.extra[tripleIdx + 1]);
this.#pushValue(body.extra[tripleIdx + 2]);
this.emitter.emitArraySet(this.#arrayTargetOf(body.extra[tripleIdx]).index);
}
#emitArrayCopyInst(inst: i32): void {
let {body} = this;
let tupleIdx = body.a[inst];
for (var k = 0; k < 5; k += 1) {
this.#pushValue(body.extra[tupleIdx + k]);
}
this.emitter.emitArrayCopy(
this.#arrayTargetOf(body.extra[tupleIdx]).index,
this.#arrayTargetOf(body.extra[tupleIdx + 2]).index);
}
/** Linear-memory store: [addr, value] pair, alignment in slot b. */
#emitMemStoreInst(inst: i32): void {
let {body} = this;
let op = body.op(inst);
let pairIdx = body.a[inst];
let align = body.b[inst];
this.#pushValue(body.extra[pairIdx]);
this.#pushValue(body.extra[pairIdx + 1]);
match (op) {
case IrOp.i32_store: { this.emitter.emitI32Store(align, 0); }
case IrOp.i32_store8: { this.emitter.emitI32Store8(align, 0); }
case IrOp.i64_store: { this.emitter.emitI64Store(align, 0); }
case IrOp.f32_store: { this.emitter.emitF32Store(align, 0); }
case _: { this.emitter.emitF64Store(align, 0); }
}
}
/**
* Every SIMD shape (ir.zena's encoding table): the value operands in
* the order wasm wants them on the stack, then the one emitter hook
* that carries this shape's immediates. The wasm opcode is the first
* word of the slot-b payload for every shape that has one, and rides
* inline in slot b for the three that do not.
*/
/**
* A wide-arithmetic instruction: push its operands, emit it, then
* store its two results into the projections' locals — the same
* shape as a multi-result call, and the reason `#storeMultiResults`
* is keyed on the producer rather than on `IrOp.call`.
*/
#emitWideArithInst(inst: i32): void {
let {body} = this;
let op = body.op(inst);
if (isWideMulOp(op)) {
this.#pushValue(body.a[inst]);
this.#pushValue(body.b[inst]);
} else {
let av = body.a[inst];
var i = 0;
while (i < 4) {
this.#pushValue(body.extra[av + i]);
i += 1;
}
}
this.emitter.emitWideArith(wideArithOpcode(op));
this.#storeMultiResults(inst);
}
#emitSimdInst(inst: i32): void {
let {body} = this;
let op = body.op(inst);
let av = body.a[inst];
let operands = simdExtraOperandCount(op);
if (operands > 0) {
var i = 0;
while (i < operands) {
this.#pushValue(body.extra[av + i]);
i += 1;
}
} else if (op != IrOp.simd_const) {
this.#pushValue(av);
}
if (op == IrOp.simd_unary || op == IrOp.simd_binary ||
op == IrOp.simd_ternary) {
this.emitter.emitSimd(body.b[inst]);
return;
}
let payload = body.b[inst];
let opcode = body.extra[payload];
// Offset is always zero: the intrinsics take an address, and a
// constant offset has nothing to fold into it.
match (op) {
case IrOp.simd_extract_lane: {
this.emitter.emitSimdLane(opcode, body.extra[payload + 1]);
}
case IrOp.simd_replace_lane: {
this.emitter.emitSimdLane(opcode, body.extra[payload + 1]);
}
case IrOp.simd_load: {
this.emitter.emitSimdMem(opcode, body.extra[payload + 1], 0);
}
case IrOp.simd_store: {
this.emitter.emitSimdMem(opcode, body.extra[payload + 1], 0);
}
case IrOp.simd_load_lane: {
this.emitter.emitSimdMemLane(opcode, body.extra[payload + 1], 0,
body.extra[payload + 2]);
}
case IrOp.simd_store_lane: {
this.emitter.emitSimdMemLane(opcode, body.extra[payload + 1], 0,
body.extra[payload + 2]);
}
case _: {
// simd_const and simd_shuffle: sixteen immediate bytes.
let bytes = new Array<i32>(16);
var i = 0;
while (i < 16) {
bytes.push(body.extra[payload + 1 + i]);
i += 1;
}
this.emitter.emitSimdBytes(opcode, bytes);
}
}
}
/** Linear-memory load: address in slot a, alignment in slot b. */
#emitMemLoadInst(inst: i32): void {
let {body} = this;
let op = body.op(inst);
let align = body.b[inst];
this.#pushValue(body.a[inst]);
match (op) {
case IrOp.i32_load: { this.emitter.emitI32Load(align, 0); }
case IrOp.i32_load8_u: { this.emitter.emitI32Load8U(align, 0); }
case IrOp.i64_load: { this.emitter.emitI64Load(align, 0); }
case IrOp.f32_load: { this.emitter.emitF32Load(align, 0); }
case _: { this.emitter.emitF64Load(align, 0); }
}
}
/** The wasm signature behind a funcref-typed value (call_ref callee). */
#signatureOf(inst: i32): WasmSignature {
let vt = this.body.resultType(inst) as ValType;
var target: WasmType | null = null;
match (vt) {
case ValTypeRef as r: { target = r.target; }
case ValTypeRefNull as rn: { target = rn.target; }
case _: {}
}
if (target is WasmSignature) {
return target;
}
throw new Error('zir emit: call_ref callee is not signature-typed');
}
/** The wasm array behind a reference-typed value (array_get/len). */
#arrayTargetOf(inst: i32): WasmArray {
let vt = this.body.resultType(inst) as ValType;
var target: WasmType | null = null;
match (vt) {
case ValTypeRef as r: { target = r.target; }
case ValTypeRefNull as rn: { target = rn.target; }
case _: {}
}
if (target is WasmArray) {
return target;
}
throw new Error('zir emit: array operand is not array-typed');
}
/** The struct behind a reference-typed value (fat-pointer projections). */
#structTargetOf(inst: i32): WasmStruct {
let vt = this.body.resultType(inst) as ValType;
var target: WasmType | null = null;
match (vt) {
case ValTypeRef as r: { target = r.target; }
case ValTypeRefNull as rn: { target = rn.target; }
case _: {}
}
if (target is WasmStruct) {
return target;
}
throw new Error('zir emit: fat-pointer operand is not struct-typed');
}
/**
* After a multi-result call, the results sit on the stack with the
* LAST on top; store them into the projections' locals in reverse.
*/
#storeMultiResults(callInst: i32): void {
if (let (true, projs) = this.#mvProjections.get(callInst)) {
var maxK = 0;
for (let p in projs) {
let idx = this.body.b[p];
if (idx > maxK) {
maxK = idx;
}
}
var k = maxK;
while (k >= 0) {
for (let p in projs) {
if (this.body.b[p] == k) {
this.#setLocal(this.localOf[p]);
break;
}
}
k -= 1;
}
}
}
#fieldRef(refIdx: i32): IrRefField {
let ref = this.body.refTable[refIdx];
if (ref is IrRefField) {
return ref;
}
throw new Error('zir emit: expected field ref');
}
#fieldIndexOf(field: IrRefField): i32 {
let idx = field.owner.fieldIndexByName(field.fieldName);
if (idx < 0) {
throw new Error('zir emit: field not found: ' + field.fieldName);
}
return idx;
}
#emitOp(op: IrOp): void {
let e = this.emitter;
match (op) {
case IrOp.i32_add: { e.emitI32Add(); }
case IrOp.i32_sub: { e.emitI32Sub(); }
case IrOp.i32_mul: { e.emitI32Mul(); }
case IrOp.i32_div_s: { e.emitI32DivS(); }
case IrOp.i32_rem_s: { e.emitI32RemS(); }
case IrOp.i32_and: { e.emitI32And(); }
case IrOp.i32_or: { e.emitI32Or(); }
case IrOp.i32_xor: { e.emitI32Xor(); }
case IrOp.i32_shl: { e.emitI32Shl(); }
case IrOp.i32_shr_s: { e.emitI32ShrS(); }
case IrOp.i32_shr_u: { e.emitI32ShrU(); }
case IrOp.i32_eqz: { e.emitI32Eqz(); }
case IrOp.i32_eq: { e.emitI32Eq(); }
case IrOp.i32_ne: { e.emitI32Ne(); }
case IrOp.i32_lt_s: { e.emitI32LtS(); }
case IrOp.i32_le_s: { e.emitI32LeS(); }
case IrOp.i32_gt_s: { e.emitI32GtS(); }
case IrOp.i32_ge_s: { e.emitI32GeS(); }
case IrOp.i32_div_u: { e.emitI32DivU(); }
case IrOp.i32_rem_u: { e.emitI32RemU(); }
case IrOp.i32_lt_u: { e.emitI32LtU(); }
case IrOp.i32_le_u: { e.emitI32LeU(); }
case IrOp.i32_gt_u: { e.emitI32GtU(); }
case IrOp.i32_ge_u: { e.emitI32GeU(); }
case IrOp.i64_add: { e.emitI64Add(); }
case IrOp.i64_sub: { e.emitI64Sub(); }
case IrOp.i64_mul: { e.emitI64Mul(); }
case IrOp.i64_div_s: { e.emitI64DivS(); }
case IrOp.i64_rem_s: { e.emitI64RemS(); }
case IrOp.i64_and: { e.emitI64And(); }
case IrOp.i64_or: { e.emitI64Or(); }
case IrOp.i64_xor: { e.emitI64Xor(); }
case IrOp.i64_shl: { e.emitI64Shl(); }
case IrOp.i64_shr_s: { e.emitI64ShrS(); }
case IrOp.i64_shr_u: { e.emitI64ShrU(); }
case IrOp.i64_eqz: { e.emitI64Eqz(); }
case IrOp.i64_eq: { e.emitI64Eq(); }
case IrOp.i64_ne: { e.emitI64Ne(); }
case IrOp.i64_lt_s: { e.emitI64LtS(); }
case IrOp.i64_le_s: { e.emitI64LeS(); }
case IrOp.i64_gt_s: { e.emitI64GtS(); }
case IrOp.i64_ge_s: { e.emitI64GeS(); }
case IrOp.i64_div_u: { e.emitI64DivU(); }
case IrOp.i64_rem_u: { e.emitI64RemU(); }
case IrOp.i64_lt_u: { e.emitI64LtU(); }
case IrOp.i64_le_u: { e.emitI64LeU(); }
case IrOp.i64_gt_u: { e.emitI64GtU(); }
case IrOp.i64_ge_u: { e.emitI64GeU(); }
case IrOp.f64_add: { e.emitF64Add(); }
case IrOp.f64_sub: { e.emitF64Sub(); }
case IrOp.f64_mul: { e.emitF64Mul(); }
case IrOp.f64_div: { e.emitF64Div(); }
case IrOp.f64_eq: { e.emitF64Eq(); }
case IrOp.f64_ne: { e.emitF64Ne(); }
case IrOp.f64_lt: { e.emitF64Lt(); }
case IrOp.f64_le: { e.emitF64Le(); }
case IrOp.f64_gt: { e.emitF64Gt(); }
case IrOp.f64_ge: { e.emitF64Ge(); }
case IrOp.f64_neg: { e.emitF64Neg(); }
case IrOp.f32_add: { e.emitF32Add(); }
case IrOp.f32_sub: { e.emitF32Sub(); }
case IrOp.f32_mul: { e.emitF32Mul(); }
case IrOp.f32_div: { e.emitF32Div(); }
case IrOp.f32_eq: { e.emitF32Eq(); }
case IrOp.f32_ne: { e.emitF32Ne(); }
case IrOp.f32_lt: { e.emitF32Lt(); }
case IrOp.f32_le: { e.emitF32Le(); }
case IrOp.f32_gt: { e.emitF32Gt(); }
case IrOp.f32_ge: { e.emitF32Ge(); }
case IrOp.f32_neg: { e.emitF32Neg(); }
case IrOp.ref_eq: { e.emitRefEq(); }
case IrOp.i32_wrap_i64: { e.emitI32WrapI64(); }
case IrOp.i64_extend_i32_s: { e.emitI64ExtendI32S(); }
case IrOp.f64_convert_i32_s: { e.emitF64ConvertI32S(); }
case IrOp.f32_convert_i32_s: { e.emitF32ConvertI32S(); }
case IrOp.f64_convert_i64_s: { e.emitF64ConvertI64S(); }
case IrOp.f32_convert_i64_s: { e.emitF32ConvertI64S(); }
case IrOp.i32_trunc_sat_f64_s: { e.emitI32TruncSatF64S(); }
case IrOp.i32_trunc_sat_f32_s: { e.emitI32TruncSatF32S(); }
case IrOp.i64_trunc_sat_f64_s: { e.emitI64TruncSatF64S(); }
case IrOp.i64_trunc_sat_f32_s: { e.emitI64TruncSatF32S(); }
case IrOp.f64_promote_f32: { e.emitF64PromoteF32(); }
case IrOp.f32_demote_f64: { e.emitF32DemoteF64(); }
case IrOp.i64_reinterpret_f64: { e.emitI64ReinterpretF64(); }
case IrOp.i32_reinterpret_f32: { e.emitI32ReinterpretF32(); }
case IrOp.f32_reinterpret_i32: { e.emitF32ReinterpretI32(); }
case IrOp.f64_reinterpret_i64: { e.emitF64ReinterpretI64(); }
case IrOp.i32_trunc_sat_f32_u: { e.emitI32TruncSatF32U(); }
case IrOp.i32_trunc_sat_f64_u: { e.emitI32TruncSatF64U(); }
case IrOp.i64_trunc_sat_f32_u: { e.emitI64TruncSatF32U(); }
case IrOp.i64_trunc_sat_f64_u: { e.emitI64TruncSatF64U(); }
case IrOp.i64_extend_i32_u: { e.emitI64ExtendI32U(); }
case IrOp.f64_convert_i32_u: { e.emitF64ConvertI32U(); }
case IrOp.f32_convert_i32_u: { e.emitF32ConvertI32U(); }
case IrOp.f64_convert_i64_u: { e.emitF64ConvertI64U(); }
case IrOp.f32_convert_i64_u: { e.emitF32ConvertI64U(); }
case IrOp.i32_clz: { e.emitI32Clz(); }
case IrOp.i32_ctz: { e.emitI32Ctz(); }
case IrOp.i32_popcnt: { e.emitI32Popcnt(); }
case IrOp.i64_clz: { e.emitI64Clz(); }
case IrOp.i64_ctz: { e.emitI64Ctz(); }
case IrOp.i64_popcnt: { e.emitI64Popcnt(); }
case IrOp.f32_abs: { e.emitF32Abs(); }
case IrOp.f32_ceil: { e.emitF32Ceil(); }
case IrOp.f32_floor: { e.emitF32Floor(); }
case IrOp.f32_nearest: { e.emitF32Nearest(); }
case IrOp.f32_sqrt: { e.emitF32Sqrt(); }
case IrOp.f32_trunc: { e.emitF32Trunc(); }
case IrOp.f64_abs: { e.emitF64Abs(); }
case IrOp.f64_ceil: { e.emitF64Ceil(); }
case IrOp.f64_floor: { e.emitF64Floor(); }
case IrOp.f64_nearest: { e.emitF64Nearest(); }
case IrOp.f64_sqrt: { e.emitF64Sqrt(); }
case IrOp.f64_trunc: { e.emitF64Trunc(); }
case IrOp.f32_min: { e.emitF32Min(); }
case IrOp.f32_max: { e.emitF32Max(); }
case IrOp.f32_copysign: { e.emitF32Copysign(); }
case IrOp.f64_min: { e.emitF64Min(); }
case IrOp.f64_max: { e.emitF64Max(); }
case IrOp.f64_copysign: { e.emitF64Copysign(); }
case _: {
throw new Error('zir emit: unsupported opcode ' + irOpName(op));
}
}
}
}
/** Emits one function; returns (graduated, kept-nullable) ref-local counts. */
export function emitZirFunction(wasm: WasmModule, emitter: WasmEmitter, func: WasmFunction, body: IrBody, scratch: IrScratch): (i32, i32) {
scratch.enter();
let cfg = new IrCfg(body, scratch);
let zirEmitter = new ZirFunctionEmitter(wasm, emitter, func, body, cfg, scratch);
zirEmitter.emit();
scratch.exit();
return (zirEmitter.graduatedLocals, zirEmitter.demotedLocals);
}
- zena-lang:wit-parser wit-parser.zena-lang.pkg.zena-lang.dev ~0.0.1-preview.1
| Version | Published | Dependencies | Approved by |
|---|---|---|---|
| 0.0.2-preview.1 | 2026-11-19 |
|
|