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

9.7 KiB Raw
/**
 * Devirtualization (docs/design/optimization-pipeline.md
 * §Devirtualization): a `call_ref` whose callee value resolves to one
 * function rewrites in place to a direct `call`. The dead slot-load
 * chain it leaves behind (vtable loads, casts, fat-pointer unpacks)
 * is the cleanup passes' business, and the new direct call is the
 * inliner's on the next round.
 *
 * Every dispatch lowers to the same shape — a vtable value, a
 * `struct_get` of a slot on it, a `ref_cast` to the slot's signature,
 * then `call_ref` — and the resolver reads that shape backwards
 * through casts. Two ways a slot resolves:
 *
 * - **Provenance.** The vtable value itself is known: a `global_get`
 *   of a vtable global, the `iface_vtable` of an `iface_pack` (whose
 *   ref names the pair's vtable global), or the `<vtable>` field of a
 *   `struct_new` (whose operand is the class's vtable global). The
 *   global's initializer names the slot's function outright.
 * - **Hierarchy.** Otherwise, the runtime vtable is some global whose
 *   struct type is the slot's owner or extends it (subclass vtable
 *   structs extend their superclass's; interface pair vtables share
 *   the interface's). RTA materializes a vtable global for exactly the
 *   classes and pairs that can exist at runtime, so the candidates are
 *   every such global in the module, and the slot devirtualizes when
 *   they all install the same function. This is the closed-world
 *   single-implementation rule, computed from the module's globals
 *   rather than a hierarchy walk.
 *
 * A rewrite also requires the target's signature to equal the slot's
 * exactly: wasm permits a stored function's signature to be a subtype
 * of the slot's, and a direct call must type-check against the
 * function's own signature. A multi-value call rewrites like any
 * other: its `mv_get` projections read the producer by id, and the id
 * stays.
 *
 * Determinism: candidates scan wasm.globals in module order; no
 * iteration over hash containers.
 */
import { HashSet } from 'zena:collections';
import {
  IrBody, IrOp, IrRefField, IrRefFunc, IrRefGlobal, IrRefType,
} from './ir.zena';
import {
  WasmModule, WasmFunction, WasmGlobal, WasmStruct, VTableInit,
  SignatureKey, asWasmSignature,
} from '../wasm-module.zena';

/** One vtable global and its initializer, collected once per module. */
final class VTableCandidate {
  global: WasmGlobal;
  init: VTableInit;
  new(this.global, this.init);
}

/** Per-module state for the pass: the vtable globals, in order. */
export final class DevirtContext {
  candidates = new Array<VTableCandidate>();
  new(wasm: WasmModule) {
    for (let g in wasm.globals) {
      let init = g.initVTable;
      if (init != null) {
        this.candidates.push(new VTableCandidate(g, init));
      }
    }
  }
}

/** Runs the pass on one body; returns the number of sites rewritten. */
export function runDevirt(cx: DevirtContext, body: IrBody): i32 {
  var count = 0;
  for (let blk in body.blocks) {
    for (let inst in blk.insts) {
      if (body.op(inst) != IrOp.call_ref) {
        continue;
      }
      let target = resolveCallee(cx, body, body.extra[body.a[inst]]);
      if (target != null && rewriteToCall(body, inst, target)) {
        count += 1;
      }
    }
  }
  return count;
}

/**
 * Rewrites the `call_ref` at `inst` into a direct call of `target`, when
 * `target`'s signature equals the callee's type exactly; returns whether
 * it did.
 */
export function rewriteToCall(body: IrBody, inst: i32, target: WasmFunction): boolean {
  let extraIdx = body.a[inst];
  let calleeType = body.resultType(body.extra[extraIdx]);
  if (calleeType == null) {
    return false;
  }
  let slotSig = asWasmSignature(calleeType);
  if (slotSig == null) {
    return false;
  }
  let targetSig = target.signature;
  let slotKey = new SignatureKey(slotSig.params, slotSig.returns);
  let targetKey = new SignatureKey(targetSig.params, targetSig.returns);
  if (!(slotKey == targetKey)) {
    return false;
  }
  // call_ref [callee, argc, args…] becomes call [argc, args…] with
  // the function in the ref slot; the result type is unchanged
  // because the signatures are.
  let argc = body.extra[extraIdx + 1];
  let newIdx = body.extra.length;
  body.extra.push(argc);
  var i = 0;
  while (i < argc) {
    body.extra.push(body.extra[extraIdx + 2 + i]);
    i += 1;
  }
  body.refTable.push(new IrRefFunc(target));
  body.opcode[inst] = IrOp.call as i32;
  body.a[inst] = newIdx;
  body.b[inst] = body.refTable.length - 1;
  return true;
}

/** Steps over the casts lowering wraps around vtable and slot loads. */
function throughCasts(body: IrBody, v: i32) {
  var c = v;
  while (c >= 0) {
    let op = body.op(c);
    if (op == IrOp.ref_cast || op == IrOp.ref_as_non_null) {
      c = body.a[c];
      continue;
    }
    return c;
  }
  return c;
}

/** The vtable global a `global_get` reads, when it is one. */
function vtableGlobalOf(body: IrBody, v: i32): VTableInit | null {
  if (v < 0 || body.op(v) != IrOp.global_get) {
    return null;
  }
  let r = body.refTable[body.b[v]];
  if (r is IrRefGlobal) {
    return r.target.initVTable;
  }
  return null;
}

/**
 * The function a callee value can only ever be, or null. `callee` is
 * the call_ref's callee operand, before any cast stepping.
 */
function resolveCallee(cx: DevirtContext, body: IrBody,
    callee: i32): WasmFunction | null {
  let v = throughCasts(body, callee);
  if (v < 0) {
    return null;
  }
  if (body.op(v) == IrOp.ref_func) {
    let r = body.refTable[body.b[v]];
    if (r is IrRefFunc) {
      return r.target;
    }
    return null;
  }
  if (body.op(v) != IrOp.struct_get) {
    return null;
  }
  let fieldRef = body.refTable[body.b[v]];
  if (!(fieldRef is IrRefField)) {
    return null;
  }
  let vst = fieldRef.owner;
  let slot = vst.fieldIndexByName(fieldRef.fieldName);
  if (slot < 0) {
    return null;
  }
  let vt = throughCasts(body, body.a[v]);
  if (vt < 0) {
    return null;
  }

  // Provenance: the vtable value names its global.
  let known = knownVTable(body, vt);
  if (known != null) {
    // A `<typeinfo>` field leads the functions in a vtable that
    // answers interface type tests; `slotGlobals` holds it.
    let funcSlot = slot - leadingSlots(known);
    if (funcSlot >= 0 && funcSlot < known.funcs.length) {
      return known.funcs[funcSlot];
    }
    return null;
  }

  // Hierarchy: every vtable global whose struct is `vst` or extends
  // it could be the runtime vtable; they must agree on the slot.
  var agreed: WasmFunction | null = null;
  var agreedUid = -1;
  for (let cand in cx.candidates) {
    if (!extendsStruct(cand.init.structType, vst)) {
      continue;
    }
    let funcSlot = slot - leadingSlots(cand.init);
    if (funcSlot < 0 || funcSlot >= cand.init.funcs.length) {
      return null;
    }
    let f = cand.init.funcs[funcSlot];
    if (agreed == null) {
      agreed = f;
      agreedUid = f.uid;
    } else if (f.uid != agreedUid) {
      return null;
    }
  }
  return agreed;
}

/**
 * How many distinct functions the vtable globals whose struct is
 * `owner` or extends it install at field `slot` of `owner`: the
 * implementations a dispatch through that slot can reach, as far as
 * the module's globals say. -1 when some candidate has no function
 * there.
 */
export function slotImplementationCount(cx: DevirtContext, owner: WasmStruct,
    slot: i32): i32 {
  let seen = new HashSet<i32>();
  for (let cand in cx.candidates) {
    if (!extendsStruct(cand.init.structType, owner)) {
      continue;
    }
    let funcSlot = slot - leadingSlots(cand.init);
    if (funcSlot < 0 || funcSlot >= cand.init.funcs.length) {
      return -1;
    }
    seen.add(cand.init.funcs[funcSlot].uid);
  }
  return seen.size;
}

/** The fields before the functions in a vtable: its `<typeinfo>` pointer, if it has one. */
function leadingSlots(init: VTableInit): i32 {
  let slots = init.slotGlobals;
  return if (slots == null) 0 else slots.length;
}

/**
 * The initializer of the vtable a value holds, when the value's
 * construction is visible in this body.
 */
function knownVTable(body: IrBody, vt: i32): VTableInit | null {
  let direct = vtableGlobalOf(body, vt);
  if (direct != null) {
    return direct;
  }
  let op = body.op(vt);
  if (op == IrOp.iface_vtable) {
    // iface_vtable(iface_pack(instance; b = the pair's vtable global)).
    let fp = throughCasts(body, body.a[vt]);
    if (fp >= 0 && body.op(fp) == IrOp.iface_pack) {
      let r = body.refTable[body.b[fp]];
      if (r is IrRefGlobal) {
        return r.target.initVTable;
      }
    }
    return null;
  }
  if (op == IrOp.struct_get) {
    // The <vtable> field of a fresh struct_new is the allocation's
    // vtable operand. The field is declared mutable, but nothing
    // writes it after construction (no struct_set targets it
    // anywhere in lowering), so the operand is the value.
    let r = body.refTable[body.b[vt]];
    if (!(r is IrRefField) || r.fieldName != '<vtable>') {
      return null;
    }
    let recv = throughCasts(body, body.a[vt]);
    if (recv < 0 || body.op(recv) != IrOp.struct_new) {
      return null;
    }
    let sr = body.refTable[body.b[recv]];
    if (!(sr is IrRefType) || !(sr.target is WasmStruct)) {
      return null;
    }
    let s = sr.target as WasmStruct;
    let fieldIdx = s.fieldIndexByName('<vtable>');
    let argsIdx = body.a[recv];
    let argc = body.extra[argsIdx];
    if (fieldIdx < 0 || fieldIdx >= argc) {
      return null;
    }
    let arg = throughCasts(body, body.extra[argsIdx + 1 + fieldIdx]);
    return vtableGlobalOf(body, arg);
  }
  return null;
}

/** `s` is `base` or transitively extends it (by identity). */
function extendsStruct(s: WasmStruct, base: WasmStruct): boolean {
  var cur: WasmStruct | null = s;
  while (cur != null) {
    if (cur.uid == base.uid) {
      return true;
    }
    cur = cur.superStruct;
  }
  return false;
}
VersionPublishedDependenciesApproved by
0.0.2-preview.1 2026-11-19