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

10.5 KiB Raw
/**
 * Scalar replacement of aggregates, mutable tier (docs/design/
 * optimization-pipeline.md §Escape analysis and SROA): an allocation
 * that never leaves the function — every use is a field read or a
 * field write through it — is deleted, and each of its fields becomes
 * an SSA value. Reads become the value written last on the path
 * reaching them, and where paths meet, a block parameter carries it.
 *
 * The immutable tier lives in simplify: a read of an immutable field
 * straight off the allocation is the allocation's operand, no control
 * flow involved. This pass is what handles a field that is written,
 * which is the iterator object's index: after `iterator()` and
 * `next()` have inlined into the loop, the object is allocated once
 * per loop, read three times and written once per iteration, and
 * escapes nowhere. Here it dissolves into a loop-carried parameter.
 *
 * The construction is the plain one. Every block the allocation's
 * block strictly dominates gets one parameter per field, every
 * branch into such a block passes the field's current value, and a
 * forward walk over each block in instruction order replaces reads
 * and deletes writes. Uses of the allocation can only sit in blocks
 * it dominates, and every predecessor of such a block is itself
 * dominated or is the allocation's block, so every parameter gets an
 * argument on every edge. Most of the parameters are then trivial —
 * every edge passes the same value — and the block cleanup pass
 * deletes them (it runs first in the cleanup sequence), leaving the
 * parameters that carry a value around a loop or across a join.
 *
 * Determinism: candidates in id order, blocks in id order, no hash
 * containers.
 */
import { IrBody, IrOp, IrRefField, IrUseLists, buildUseLists, IrScratch } from './ir.zena';
import { IrCfg } from './cfg.zena';
import { WasmStruct } from '../wasm-module.zena';
import { allocatedStruct } from './simplify.zena';
import { growable } from 'zena:core';

/** Runs the pass; returns the number of allocations replaced. */
export function runSroa(body: IrBody, scratch: IrScratch): i32 {
  scratch.enter();
  let result = runSroaOn(body, scratch);
  scratch.exit();
  return result;
}

function runSroaOn(body: IrBody, scratch: IrScratch): i32 {
  let count = body.instCount();
  let nb = body.blocks.length;
  if (nb == 0) {
    return 0;
  }

  // Users of every value, for the escape test.
  let users = buildUseLists(body, scratch);

  // Candidates: a struct_new whose every use is a field read or a
  // field write with it as the receiver (a write storing it somewhere
  // is a use as a value, and disqualifies).
  let candidates = scratch.i32();
  for (var i = 0; i < count; i += 1) {
    if (body.op(i) != IrOp.struct_new) {
      continue;
    }
    let s = allocatedStruct(body, i);
    if (s == null) {
      continue;
    }
    let argc = body.extra[body.a[i]];
    if (argc != s.fields.length) {
      continue;
    }
    var local = true;
    for (var k = 0; k < users.count(i); k += 1) {
      let u = users.at(i, k);
      let op = body.op(u);
      if (op == IrOp.struct_get && body.a[u] == i) {
        continue;
      }
      if (op == IrOp.struct_set && body.extra[body.a[u]] == i &&
          body.extra[body.a[u] + 1] != i) {
        continue;
      }
      local = false;
      break;
    }
    if (local) {
      candidates.push(i);
    }
  }
  if (candidates.length == 0) {
    return 0;
  }

  let cfg = new IrCfg(body, scratch);
  // The first block of every try body. Emission places the blocks it
  // dominates inside the try_table, so they are the protected region.
  let tryBodies = scratch.i32();
  for (var i = 0; i < count; i += 1) {
    if (body.op(i) == IrOp.try_br) {
      tryBodies.push(body.extra[body.successorRecord(i, 0)]);
    }
  }
  let repl = scratch.i32();
  for (var i = 0; i < count; i += 1) {
    repl.push(i);
  }
  var replaced = 0;
  for (let alloc in candidates) {
    let home = body.instBlock[alloc];
    if (home < 0 || !cfg.isReachable(home)) {
      continue;
    }
    if (writtenInsideTryFromOutside(body, cfg, users, alloc, home, tryBodies)) {
      continue;
    }
    let s = allocatedStruct(body, alloc);
    if (s == null) {
      continue;
    }
    let nf = s.fields.length;
    let argsIdx = body.a[alloc];

    // The blocks strictly dominated by the allocation's block, and one
    // parameter per field on each.
    let dominated = new Array<boolean>(nb);
    for (var b = 0; b < nb; b += 1) {
      dominated.push(false);
    }
    let stack = new Array<i32>();
    for (var cK = 0; cK < cfg.domChildCount(home); cK += 1) {
      let c = cfg.domChild(home, cK);
      stack.push(c);
    }
    let order = new Array<i32>();
    while (stack.length > 0) {
      let b = stack.pop();
      dominated[b] = true;
      order.push(b);
      for (var cK = 0; cK < cfg.domChildCount(b); cK += 1) {
        let c = cfg.domChild(b, cK);
        stack.push(c);
      }
    }
    let paramOf = new Array<i32>();
    for (var k = 0; k < nb * nf; k += 1) {
      paramOf.push(-1);
    }
    for (let b in order) {
      for (var f = 0; f < nf; f += 1) {
        body.typeTable.push(s.fields[f].type);
        let id = body.opcode.length;
        body.opcode.push(IrOp.param as i32);
        body.typeId.push(body.typeTable.length - 1);
        body.a.push(-1);
        body.b.push(-1);
        body.instBlock.push(b);
        body.blocks[b].params.push(id);
        paramOf[b * nf + f] = id;
      }
    }

    // Forward walk: the allocation's block starts undefined (nothing
    // reads before the allocation), every dominated block starts at
    // its parameters.
    let cur = new Array<i32>(nf);
    for (var f = 0; f < nf; f += 1) {
      cur.push(-1);
    }
    let walk = growable<i32>([home]);
    for (let b in order) {
      walk.push(b);
    }
    for (let b in walk) {
      for (var f = 0; f < nf; f += 1) {
        cur[f] = if (b == home) -1 else paramOf[b * nf + f];
      }
      let insts = body.blocks[b].insts;
      for (let inst in insts) {
        if (inst == alloc) {
          for (var f = 0; f < nf; f += 1) {
            cur[f] = body.extra[argsIdx + 1 + f];
          }
          continue;
        }
        let op = body.op(inst);
        if (op == IrOp.struct_get && body.a[inst] == alloc) {
          let f = fieldIndex(body, s, body.b[inst]);
          if (f < 0 || cur[f] < 0) {
            throw new Error('sroa: field read before the allocation');
          }
          repl[inst] = cur[f];
          nopOut(body, inst);
          continue;
        }
        if (op == IrOp.struct_set && body.extra[body.a[inst]] == alloc) {
          let f = fieldIndex(body, s, body.b[inst]);
          if (f < 0) {
            throw new Error('sroa: write to an unknown field');
          }
          cur[f] = body.extra[body.a[inst] + 1];
          nopOut(body, inst);
          continue;
        }
      }
      // The terminator passes the current values to every dominated
      // successor.
      let term = insts[insts.length - 1];
      var anyDominated = false;
      let succN = body.successorCount(term);
      for (var succK = 0; succK < succN; succK += 1) {
        let succRec = body.successorRecord(term, succK);
        if (dominated[body.extra[succRec]]) {
          anyDominated = true;
        }
      }
      if (anyDominated) {
        for (var f = 0; f < nf; f += 1) {
          if (cur[f] < 0) {
            throw new Error('sroa: field value undefined at a branch');
          }
        }
        appendBranchArgs(body, term, dominated, cur);
      }
    }
    nopOut(body, alloc);
    replaced += 1;
  }

  let canon = (v: i32) => {
    var c = v;
    while (c >= 0 && c < count && repl[c] != c) {
      c = repl[c];
    }
    return c;
  };
  let total = body.instCount();
  for (var i = 0; i < total; i += 1) {
    if (body.op(i) != IrOp.nop) {
      body.rewriteValueOperands(i, canon);
    }
  }
  return replaced;
}

/**
 * Whether a write to `alloc`'s fields sits in a try body that `alloc`'s
 * block is outside of. The try's handler edge carries the values at
 * try entry, so a field the body wrote before throwing would read in
 * the handler, and after it, as the value from before the write. In
 * memory the write is there; as an SSA value it is not. An allocation
 * made inside the try body is safe: the handler cannot reach it.
 */
function writtenInsideTryFromOutside(body: IrBody, cfg: IrCfg, users: IrUseLists,
    alloc: i32, home: i32, tryBodies: GrowableArray<i32>): boolean {
  for (var k = 0; k < users.count(alloc); k += 1) {
    let u = users.at(alloc, k);
    if (body.op(u) != IrOp.struct_set) {
      continue;
    }
    let blk = body.instBlock[u];
    for (let t in tryBodies) {
      if (cfg.dominates(t, blk) && !cfg.dominates(t, home)) {
        return true;
      }
    }
  }
  return false;
}

/** The index in `s` of the field a struct_get/struct_set names. */
function fieldIndex(body: IrBody, s: WasmStruct, refIdx: i32): i32 {
  let r = body.refTable[refIdx];
  if (r is IrRefField) {
    return s.fieldIndexByName(r.fieldName);
  }
  return -1;
}

/**
 * Rebuilds a terminator's successor records with `values` appended
 * to the arguments of every successor whose target is dominated.
 * Records live inline in `extra`, so the rebuilt record is appended
 * and the terminator repointed; every branch shape is
 * [prefix] ([target, argc, args…])* (see blockmerge's dropBranchArg).
 */
function appendBranchArgs(body: IrBody, term: i32,
    dominated: GrowableArray<boolean>, values: GrowableArray<i32>): void {
  let op = body.op(term);
  let prefixLen = if (op == IrOp.br_on_cast || op == IrOp.br_on_cast_fail ||
      op == IrOp.br_table) {
    1
  } else {
    0
  };
  let recordStart = if (op == IrOp.br) body.a[term] else body.b[term];
  let sN = body.successorCount(term);
  let idx = body.extra.length;
  var p = 0;
  while (p < prefixLen) {
    body.extra.push(body.extra[recordStart + p]);
    p += 1;
  }
  for (var sK = 0; sK < sN; sK += 1) {
    let sRec = body.successorRecord(term, sK);
    let extend = dominated[body.extra[sRec]];
    body.extra.push(body.extra[sRec]);
    body.extra.push(if (extend) body.extra[sRec + 1] + values.length else body.extra[sRec + 1]);
    var i = 0;
    while (i < body.extra[sRec + 1]) {
      body.extra.push(body.extra[(sRec + 2) + i]);
      i += 1;
    }
    if (extend) {
      for (let v in values) {
        body.extra.push(v);
      }
    }
  }
  if (op == IrOp.br) {
    body.a[term] = idx;
  } else {
    body.b[term] = idx;
  }
}

/** A nop stays listed in its block, so it keeps its block id. */
function nopOut(body: IrBody, inst: i32): void {
  body.opcode[inst] = IrOp.nop as i32;
  body.typeId[inst] = -1;
  body.a[inst] = -1;
  body.b[inst] = -1;
}
VersionPublishedDependenciesApproved by
0.0.2-preview.1 2026-11-19