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

18.9 KiB Raw
/**
 * CFG cleanup (docs/design/optimization-pipeline.md, cleanup set):
 * removes blocks unreachable from the entry after branch folding. The
 * verifier requires every block reachable, so folding a `br_if` on a
 * constant is only legal paired with this pass.
 *
 * Removal is physical — the block list is compacted and every
 * surviving terminator's targets are renumbered — because block ids
 * are indices. The target of every successor sits exactly two `extra`
 * slots before its first branch arg (the [target, argc, args…] layout
 * every terminator shares, see successors() in ir.zena), so
 * renumbering writes through IrSuccessor.argStart - 2 rather than
 * re-decoding each terminator shape.
 *
 * Two more cleanups keep the graph in the shape the emitter reads
 * best. A block whose only instruction is a `br` forwards every edge
 * into it straight to its target (jump to jump), and a block whose
 * sole predecessor ends in an unconditional `br` to it fuses into that
 * predecessor. Both matter to the emitter's loop-exit placement: it
 * puts an exit block after the loop's `end`, behind a label, only
 * when the exit is a dominator child of the loop header, and an
 * inlined body leaves the header holding one jump into the inlined
 * test, whose exhausted arm is one more jump to the exit. Without the
 * two cleanups the exit sits two levels down and the emitter falls
 * back to an if/else with the exit's code inside the loop, which
 * wasmtime compiles a good deal worse.
 */
import { IrBlock, IrBody, IrOp, IrScratch } from './ir.zena';
import { isValSubtype } from '../wasm-module.zena';

/**
 * Runs the cleanups; returns the number of blocks removed plus the
 * number of block parameters deleted plus the number of edges
 * forwarded and blocks fused.
 */
export function runBlockCleanup(body: IrBody, scratch: IrScratch): i32 {
  scratch.enter();
  let result = runBlockCleanupOn(body, scratch);
  scratch.exit();
  return result;
}

function runBlockCleanupOn(body: IrBody, scratch: IrScratch): i32 {
  var n = removeUnreachable(body, scratch) + removeTrivialParams(body, scratch);
  let forwarded = forwardEmptyBlocks(body, scratch);
  let fused = fuseStraightLine(body, scratch);
  if (forwarded > 0 || fused > 0) {
    n += forwarded + fused + removeUnreachable(body, scratch) + removeTrivialParams(body, scratch);
  }
  return n;
}

/** The join blocks of the function's user tries, which stay as they are. */
function tryJoins(body: IrBody, scratch: IrScratch) {
  let joins = scratch.i32();
  for (let k in body.tryJoin.keys()) {
    joins.push(body.tryJoin[k]);
  }
  return joins;
}

function isIn(list: GrowableArray<i32>, b: i32): boolean {
  for (let x in list) {
    if (x == b) {
      return true;
    }
  }
  return false;
}

/**
 * Sends every edge into a block whose only instruction is a `br`
 * straight to that br's target, with the br's arguments substituted
 * for the block's parameters. Only edges from br/br_if/br_table are
 * moved (a try_br's targets keep their shape for the emitter); a
 * block some other edge still reaches keeps working as it was.
 */
function forwardEmptyBlocks(body: IrBody, scratch: IrScratch): i32 {
  let nb = body.blocks.length;
  let joins = tryJoins(body, scratch);
  // Users of every value: a parameter of a forwarded block must feed
  // nothing but the block's own br, since a block it dominates could
  // otherwise read it and the forwarded edges would carry no value.
  let count = body.instCount();
  let useCount = scratch.i32();
  for (var i = 0; i < count; i += 1) {
    useCount.push(0);
  }
  let operands = scratch.i32();
  for (var i = 0; i < count; i += 1) {
    if (body.op(i) == IrOp.nop) {
      continue;
    }
    operands.clear();
    body.appendValueOperands(i, operands);
    for (let v in operands) {
      if (v >= 0 && v < count) {
        useCount[v] += 1;
      }
    }
  }
  // The predecessors of every block along the edges this pass moves,
  // kept current as it moves them, so each candidate looks only at
  // the terminators that reach it rather than at every block's.
  let preds = new Array<GrowableArray<i32>>(nb);
  for (var b = 0; b < nb; b += 1) {
    preds.push(new Array<i32>());
  }
  for (var b = 0; b < nb; b += 1) {
    let insts = body.blocks[b].insts;
    if (insts.length == 0) {
      continue;
    }
    let term = insts[insts.length - 1];
    let op = body.op(term);
    if (op != IrOp.br && op != IrOp.br_if && op != IrOp.br_table) {
      continue;
    }
    let n = body.successorCount(term);
    for (var k = 0; k < n; k += 1) {
      let target = body.extra[body.successorRecord(term, k)];
      if (target >= 0 && target < nb) {
        preds[target].push(b);
      }
    }
  }
  var forwarded = 0;
  for (var e = 1; e < nb; e += 1) {
    let blk = body.blocks[e];
    if (blk.insts.length == 0 || isIn(joins, e)) {
      continue;
    }
    let term = blk.insts[blk.insts.length - 1];
    if (body.op(term) != IrOp.br) {
      continue;
    }
    var empty = true;
    for (let inst in blk.insts) {
      if (inst != term && body.op(inst) != IrOp.nop) {
        empty = false;
      }
    }
    if (!empty) {
      continue;
    }
    let onward = body.successorRecord(term, 0);
    let onwardTarget = body.extra[onward];
    let onwardArgc = body.extra[onward + 1];
    // Each parameter's uses are all in the br's argument list.
    var paramsLocal = true;
    for (let p in blk.params) {
      var inArgs = 0;
      var i = 0;
      while (i < onwardArgc) {
        if (body.extra[onward + 2 + i] == p) {
          inArgs += 1;
        }
        i += 1;
      }
      if (useCount[p] != inArgs) {
        paramsLocal = false;
      }
    }
    if (!paramsLocal) {
      continue;
    }
    if (onwardTarget == e) {
      continue;
    }
    let ps = preds[e];
    for (let b in ps) {
      if (b == e) {
        continue;
      }
      let pInsts = body.blocks[b].insts;
      let pTerm = pInsts[pInsts.length - 1];
      // Successor slots are re-decoded after every rewrite, since a
      // rewrite appends a fresh record.
      var k = 0;
      while (true) {
        if (k >= body.successorCount(pTerm)) {
          break;
        }
        let rec = body.successorRecord(pTerm, k);
        if (body.extra[rec] != e) {
          k += 1;
          continue;
        }
        let args = new Array<i32>();
        var i = 0;
        while (i < onwardArgc) {
          let v = body.extra[onward + 2 + i];
          var mapped = v;
          for (var q = 0; q < blk.params.length; q += 1) {
            if (blk.params[q] == v) {
              mapped = body.extra[rec + 2 + q];
            }
          }
          args.push(mapped);
          i += 1;
        }
        retarget(body, pTerm, k, onwardTarget, args);
        preds[onwardTarget].push(b);
        forwarded += 1;
        k += 1;
      }
    }
  }
  return forwarded;
}

/**
 * Appends a block to its sole predecessor when that predecessor ends
 * in an unconditional `br` to it and the block has no parameters
 * (a single edge's parameters are trivial and already gone). Chains
 * fuse in one call: the predecessor's new terminator is checked again.
 */
function fuseStraightLine(body: IrBody, scratch: IrScratch): i32 {
  let nb = body.blocks.length;
  let joins = tryJoins(body, scratch);
  var fused = 0;
  var progress = true;
  let incoming = scratch.i32();
  while (progress) {
    progress = false;
    // Incoming edge counts.
    incoming.clear();
    for (var b = 0; b < nb; b += 1) {
      incoming.push(0);
    }
    for (var b = 0; b < nb; b += 1) {
      let insts = body.blocks[b].insts;
      if (insts.length == 0) {
        continue;
      }
      let term = insts[insts.length - 1];
      let n = body.successorCount(term);
      for (var k = 0; k < n; k += 1) {
        incoming[body.extra[body.successorRecord(term, k)]] += 1;
      }
    }
    for (var p = 0; p < nb; p += 1) {
      let pBlk = body.blocks[p];
      if (pBlk.insts.length == 0) {
        continue;
      }
      let pTerm = pBlk.insts[pBlk.insts.length - 1];
      if (body.op(pTerm) != IrOp.br) {
        continue;
      }
      let s = body.extra[body.successorRecord(pTerm, 0)];
      if (s == p || s == 0 || incoming[s] != 1 || isIn(joins, s)) {
        continue;
      }
      let sBlk = body.blocks[s];
      if (sBlk.params.length > 0 || sBlk.insts.length == 0) {
        continue;
      }
      // Move: the predecessor's br goes, the block's instructions
      // follow, the block empties (unreachable, removed afterwards).
      nopOut(body, pTerm);
      pBlk.insts.pop();
      for (let inst in sBlk.insts) {
        pBlk.insts.push(inst);
        body.instBlock[inst] = p;
      }
      while (sBlk.insts.length > 0) {
        sBlk.insts.pop();
      }
      incoming[s] = 0;
      fused += 1;
      progress = true;
      // The next pass recounts edges; a chain continues from p.
      break;
    }
  }
  return fused;
}

/**
 * Rebuilds a terminator's successor records with successor `k`
 * replaced by `target(args)`. Records live inline in `extra`, so the
 * rebuilt record is appended and the terminator repointed; every
 * branch shape is [prefix] ([target, argc, args…])*.
 */
export function retarget(body: IrBody, term: i32, k: i32, target: i32,
    args: 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 count = body.successorCount(term);
  let idx = body.extra.length;
  var p = 0;
  while (p < prefixLen) {
    body.extra.push(body.extra[recordStart + p]);
    p += 1;
  }
  // The old records are read as the new ones are appended; the
  // terminator still points at the old ones until the end.
  var rec = body.successorRecord(term, 0);
  for (var n = 0; n < count; n += 1) {
    let argc = body.extra[rec + 1];
    if (n == k) {
      body.extra.push(target);
      body.extra.push(args.length);
      for (let v in args) {
        body.extra.push(v);
      }
    } else {
      body.extra.push(body.extra[rec]);
      body.extra.push(argc);
      var i = 0;
      while (i < argc) {
        body.extra.push(body.extra[rec + 2 + i]);
        i += 1;
      }
    }
    rec += 2 + argc;
  }
  if (op == IrOp.br) {
    body.a[term] = idx;
  } else {
    body.b[term] = idx;
  }
}

function removeUnreachable(body: IrBody, scratch: IrScratch): i32 {
  let nb = body.blocks.length;
  if (nb == 0) {
    return 0;
  }
  let reachable = scratch.bool();
  for (var i = 0; i < nb; i += 1) {
    reachable.push(false);
  }
  let stack = scratch.i32();
  reachable[0] = true;
  stack.push(0);
  while (stack.length > 0) {
    let b = stack.pop();
    let insts = body.blocks[b].insts;
    let term = insts[insts.length - 1];
    let n = body.successorCount(term);
    for (var k = 0; k < n; k += 1) {
      let target = body.extra[body.successorRecord(term, k)];
      if (!reachable[target]) {
        reachable[target] = true;
        stack.push(target);
      }
    }
  }

  var removedCount = 0;
  for (var i = 0; i < nb; i += 1) {
    if (!reachable[i]) {
      removedCount += 1;
    }
  }
  if (removedCount == 0) {
    return 0;
  }

  // A try's join block (IrBody.tryJoin) is where emission ends the
  // protected region. It dies when folding or inlining leaves the try
  // body no way to complete, as when the body calls a function that
  // only throws; the try_br survives without it (renumbering drops
  // the entry). No block is then reached through the body's normal
  // exit, so nothing can be placed inside the try_table that belongs
  // after it, which is what the join is there to prevent.
  let instCount = body.instCount();

  let map = scratch.i32();
  var next = 0;
  for (var i = 0; i < nb; i += 1) {
    if (reachable[i]) {
      map.push(next);
      next += 1;
    } else {
      map.push(-1);
    }
  }

  // Nop every instruction (params included) of the dead blocks so use
  // counts, stats, and emission never see them again.
  for (var i = 0; i < nb; i += 1) {
    if (reachable[i]) {
      continue;
    }
    let blk = body.blocks[i];
    for (let p in blk.params) {
      nopOut(body, p);
    }
    for (let inst in blk.insts) {
      nopOut(body, inst);
    }
  }

  // Renumber: instBlock for survivors, successor targets, tryJoin.
  for (var i = 0; i < instCount; i += 1) {
    let ob = body.instBlock[i];
    if (ob >= 0 && ob < nb) {
      body.instBlock[i] = map[ob];
    }
  }
  for (var i = 0; i < nb; i += 1) {
    if (!reachable[i]) {
      continue;
    }
    let insts = body.blocks[i].insts;
    let term = insts[insts.length - 1];
    let sN = body.successorCount(term);
    for (var sK = 0; sK < sN; sK += 1) {
      let sRec = body.successorRecord(term, sK);
      body.extra[(sRec + 2) - 2] = map[body.extra[sRec]];
    }
  }
  let newJoin = new Map<i32, i32>();
  for (var i = 0; i < instCount; i += 1) {
    if (body.op(i) == IrOp.try_br) {
      if (let (true, join) = body.tryJoin.get(i)) {
        if (map[join] >= 0) {
          newJoin[i] = map[join];
        }
      }
    }
  }
  // tryJoin's field is immutable; rebuild its contents in place, in
  // instruction-id order for determinism.
  let oldKeys = scratch.i32();
  for (let k in body.tryJoin.keys()) {
    oldKeys.push(k);
  }
  for (let k in oldKeys) {
    body.tryJoin.delete(k);
  }
  for (var i = 0; i < instCount; i += 1) {
    if (body.op(i) == IrOp.try_br) {
      if (let (true, join) = newJoin.get(i)) {
        body.tryJoin[i] = join;
      }
    }
  }

  // Compact the block list in place (the field itself is immutable).
  let survivors = new Array<IrBlock>();
  for (var i = 0; i < nb; i += 1) {
    if (reachable[i]) {
      survivors.push(body.blocks[i]);
    }
  }
  while (body.blocks.length > 0) {
    body.blocks.pop();
  }
  for (let blk in survivors) {
    body.blocks.push(blk);
  }
  return removedCount;
}

/**
 * Deletes every block parameter that every incoming edge passes the
 * same value for (a back edge passing the parameter itself does not
 * count): uses of the parameter become that value, the parameter
 * leaves the block, and its argument leaves every incoming branch.
 * The value dominates the block because it dominates each
 * predecessor.
 *
 * The common case is the continuation block an inlined callee returns
 * through: its parameter is the callee's one returned value, and once
 * the parameter is gone the forwarding rules in simplify see the
 * allocation behind it. (Redirecting uses while leaving the parameter
 * in place was tried first and made emission worse — the emitter
 * coalesces a parameter with its incoming copies, and a redirected
 * use defeats that — so the parameter and the arguments go too.)
 */
function removeTrivialParams(body: IrBody, scratch: IrScratch): i32 {
  let nb = body.blocks.length;
  let incoming = new Array<GrowableArray<i32>>(nb);
  for (var i = 0; i < nb; i += 1) {
    incoming.push(new Array<i32>());
  }
  for (let blk in body.blocks) {
    if (blk.insts.length == 0) {
      continue;
    }
    let term = blk.insts[blk.insts.length - 1];
    let n = body.successorCount(term);
    for (var k = 0; k < n; k += 1) {
      // Once per terminator: a branch whose edges both reach the same
      // block would otherwise have the argument dropped twice.
      let list = incoming[body.extra[body.successorRecord(term, k)]];
      if (list.length == 0 || list[list.length - 1] != term) {
        list.push(term);
      }
    }
  }
  let count = body.instCount();
  let repl = scratch.i32();
  for (var i = 0; i < count; i += 1) {
    repl.push(i);
  }
  let canon = (v: i32) => {
    var c = v;
    while (c >= 0 && c < count && repl[c] != c) {
      c = repl[c];
    }
    return c;
  };
  var removed = 0;
  // Block 0 holds the function's parameters, which have no incoming
  // edges; every other block's parameters are candidates. Higher
  // indices first, so removing one leaves the lower indices intact.
  for (var b = 1; b < nb; b += 1) {
    let edges = incoming[b];
    if (edges.length == 0) {
      continue;
    }
    let params = body.blocks[b].params;
    var j = params.length - 1;
    while (j >= 0) {
      let p = params[j];
      var value = -1;
      var trivial = true;
      for (let term in edges) {
        let n = body.successorCount(term);
        for (var k = 0; k < n; k += 1) {
          let rec = body.successorRecord(term, k);
          if (body.extra[rec] != b) {
            continue;
          }
          let arg = canon(body.extra[rec + 2 + j]);
          if (arg == p) {
            continue;
          }
          if (value < 0) {
            value = arg;
          } else if (arg != value) {
            trivial = false;
          }
        }
      }
      if (trivial && value >= 0) {
        let from = body.resultType(value);
        let to = body.resultType(p);
        if (from != null && to != null && isValSubtype(from, to)) {
          repl[p] = value;
          nopOut(body, p);
          dropParamAt(body.blocks[b], j);
          for (let term in edges) {
            dropBranchArg(body, term, b, j);
          }
          removed += 1;
        }
      }
      j -= 1;
    }
  }
  if (removed > 0) {
    for (var i = 0; i < count; i += 1) {
      if (body.op(i) != IrOp.nop) {
        body.rewriteValueOperands(i, canon);
      }
    }
  }
  return removed;
}

export function dropParamAt(blk: IrBlock, j: i32): void {
  let kept = new Array<i32>();
  for (var k = 0; k < blk.params.length; k += 1) {
    if (k != j) {
      kept.push(blk.params[k]);
    }
  }
  while (blk.params.length > 0) {
    blk.params.pop();
  }
  for (let p in kept) {
    blk.params.push(p);
  }
}

/**
 * Rebuilds a terminator's successor records without argument `j` of
 * every successor targeting `target`. Records live inline in `extra`,
 * so the rebuilt record is appended and the terminator repointed.
 * Every branch shape is [prefix] ([target, argc, args…])*: no prefix
 * for br/br_if/try_br, the target type for br_on_cast, the count for
 * br_table (see the encoding table in ir.zena).
 */
export function dropBranchArg(body: IrBody, term: i32, target: i32, j: 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);
    body.extra.push(body.extra[sRec]);
    let drop = body.extra[sRec] == target;
    body.extra.push(if (drop) body.extra[sRec + 1] - 1 else body.extra[sRec + 1]);
    var i = 0;
    while (i < body.extra[sRec + 1]) {
      if (!(drop && i == j)) {
        body.extra.push(body.extra[(sRec + 2) + i]);
      }
      i += 1;
    }
  }
  if (op == IrOp.br) {
    body.a[term] = idx;
  } else {
    body.b[term] = idx;
  }
}

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;
  body.instBlock[inst] = -1;
}
VersionPublishedDependenciesApproved by
0.0.2-preview.1 2026-11-19