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

12.4 KiB Raw
/**
 * Jump threading through a block that only branches on its own
 * parameter. After an iterator's `next()` inlines into a protocol
 * loop and its object dissolves, what remains of the call is its
 * continuation: a block whose parameters are the returned values —
 * a done flag and an element — and whose one instruction is the
 * `br_if` on the flag that picks the loop body or the exit. Every
 * predecessor passes a constant for the flag (1 from the arm that
 * found an element, 0 from the arm that ran out), so each of them
 * already knows which way the branch goes. This pass sends each such
 * predecessor straight to that arm.
 *
 * The values matter more than the jump. The arm's blocks read the
 * continuation's parameters (the body reads the element), and a
 * predecessor that jumps past the continuation must deliver them
 * another way: the arm gets a parameter of its own for each
 * continuation parameter its blocks use, the continuation's edge to
 * the arm passes its parameter through, and a threaded edge passes
 * what it would have passed to the continuation. Uses inside the arm
 * move to the arm's parameter. When the threaded edges were all the
 * continuation had, it loses its last predecessor and the block
 * cleanup pass removes it, and the arm's new parameter is trivial
 * (one edge, one value) and goes the same way. The loop is then the
 * hand-written one: test, element, body, back.
 *
 * Preconditions, all checked: the block has parameters and no
 * instruction but the branch (an `i32.eqz` of the parameter, used
 * only by the branch, is allowed as the condition); the two targets
 * are distinct and neither is the block itself; at least one
 * incoming edge passes a constant; every use of every parameter,
 * besides the branch, lies in a block one of the two targets
 * dominates; and a target that needs parameters has the block as its
 * only predecessor (another predecessor would have nothing to pass).
 * A try's join block is never threaded through.
 *
 * Determinism: blocks in id order, one threading per CFG rebuild.
 */
import { IrBody, IrOp, buildUseLists, IrScratch } from './ir.zena';
import { IrCfg } from './cfg.zena';
import { retarget } from './blockmerge.zena';
import { i32ToString, growable } from 'zena:core';

/** Runs the pass; returns the number of blocks threaded through. */
export function runJumpThreading(body: IrBody, scratch: IrScratch): i32 {
  scratch.enter();
  let result = runJumpThreadingOn(body, scratch);
  scratch.exit();
  return result;
}

function runJumpThreadingOn(body: IrBody, scratch: IrScratch): i32 {
  var threaded = 0;
  while (threaded < 64 && threadStep(body, scratch)) {
    threaded += 1;
  }
  return threaded;
}

/** One threading, in its own scope: the CFG it builds goes back to the pool. */
function threadStep(body: IrBody, scratch: IrScratch): boolean {
  scratch.enter();
  let cfg = new IrCfg(body, scratch);
  let c = findCandidate(body, cfg, scratch);
  if (c >= 0) {
    threadThrough(body, cfg, c, scratch);
  }
  scratch.exit();
  return c >= 0;
}

/** The first block eligible for threading, or -1. */
function findCandidate(body: IrBody, cfg: IrCfg, scratch: IrScratch): i32 {
  let joins = new Array<i32>();
  for (let k in body.tryJoin.keys()) {
    joins.push(body.tryJoin[k]);
  }
  let nb = body.blocks.length;
  for (var c = 1; c < nb; c += 1) {
    if (!cfg.isReachable(c)) {
      continue;
    }
    var isJoin = false;
    for (let j in joins) {
      if (j == c) {
        isJoin = true;
      }
    }
    if (isJoin) {
      continue;
    }
    if (eligible(body, cfg, c, scratch)) {
      return c;
    }
  }
  return -1;
}

/**
 * The branch's condition as a parameter of `c`: the parameter id, or
 * -1. `negated` reports an `i32.eqz` between the two.
 */
function conditionParam(body: IrBody, c: i32): i32 {
  let blk = body.blocks[c];
  let term = blk.insts[blk.insts.length - 1];
  let cond = body.a[term];
  if (body.op(cond) == IrOp.param && body.instBlock[cond] == c) {
    return cond;
  }
  if (body.op(cond) == IrOp.i32_eqz && body.instBlock[cond] == c) {
    let inner = body.a[cond];
    if (body.op(inner) == IrOp.param && body.instBlock[inner] == c) {
      return inner;
    }
  }
  return -1;
}

function conditionNegated(body: IrBody, c: i32) {
  let blk = body.blocks[c];
  let term = blk.insts[blk.insts.length - 1];
  return body.op(body.a[term]) == IrOp.i32_eqz;
}


function eligible(body: IrBody, cfg: IrCfg, c: i32, scratch: IrScratch): boolean {
  let blk = body.blocks[c];
  if (blk.params.length == 0 || blk.insts.length == 0) {
    return false;
  }
  let term = blk.insts[blk.insts.length - 1];
  if (body.op(term) != IrOp.br_if) {
    return false;
  }
  let p = conditionParam(body, c);
  if (p < 0) {
    return false;
  }
  let cond = body.a[term];
  // Nothing but the branch and, when negated, the eqz.
  for (let inst in blk.insts) {
    if (inst == term || body.op(inst) == IrOp.nop || inst == cond) {
      continue;
    }
    return false;
  }
  let t = body.extra[body.successorRecord(term, 0)];
  let f = body.extra[body.successorRecord(term, 1)];
  if (t == f || t == c || f == c) {
    return false;
  }
  // At least one incoming edge passes a constant for the parameter.
  var j = -1;
  for (var k = 0; k < blk.params.length; k += 1) {
    if (blk.params[k] == p) {
      j = k;
    }
  }
  var anyConstant = false;
  for (var predK = 0; predK < cfg.predCount(c); predK += 1) {
    let pred = cfg.pred(c, predK);
    let pInsts = body.blocks[pred].insts;
    let pTerm = pInsts[pInsts.length - 1];
    let sN = body.successorCount(pTerm);
    for (var sK = 0; sK < sN; sK += 1) {
      let sRec = body.successorRecord(pTerm, sK);
      if (body.extra[sRec] == c && body.op(body.extra[(sRec + 2) + j]) == IrOp.const_i32) {
        anyConstant = true;
      }
    }
  }
  if (!anyConstant) {
    return false;
  }
  // Every other use of a parameter sits under one of the targets, and
  // a target that would need parameters has no other predecessor.
  let users = buildUseLists(body, scratch);
  if (cond != p) {
    // The eqz belongs to the branch alone.
    for (var k = 0; k < users.count(cond); k += 1) {
      let u = users.at(cond, k);
      if (u != term) {
        return false;
      }
    }
  }
  var needT = false;
  var needF = false;
  for (let q in blk.params) {
    for (var k = 0; k < users.count(q); k += 1) {
      let u = users.at(q, k);
      if (u == term || u == cond) {
        continue;
      }
      let arm = armOf(cfg, t, f, body.instBlock[u]);
      if (arm == 0) {
        needT = true;
      } else if (arm == 1) {
        needF = true;
      } else {
        return false;
      }
    }
  }
  if (needT && !onlyPredIs(cfg, t, c)) {
    return false;
  }
  return !(needF && !onlyPredIs(cfg, f, c));
}

/**
 * Which arm a use in block `bu` belongs to: 0 for the first target's
 * region, 1 for the second's, -1 for neither. One arm can lie inside
 * the other's region (the second is a loop header and the first sits
 * in its loop, say); a use dominated by both belongs to the inner arm,
 * whose parameter is the one that reaches it.
 */
function armOf(cfg: IrCfg, t: i32, f: i32, bu: i32): i32 {
  if (bu < 0) {
    return -1;
  }
  let inT = cfg.dominates(t, bu);
  let inF = cfg.dominates(f, bu);
  if (inT && inF) {
    return if (cfg.dominates(f, t)) 0 else 1;
  }
  if (inT) {
    return 0;
  }
  if (inF) {
    return 1;
  }
  return -1;
}

function onlyPredIs(cfg: IrCfg, b: i32, c: i32): boolean {
  for (var pK = 0; pK < cfg.predCount(b); pK += 1) {
    let p = cfg.pred(b, pK);
    if (p != c) {
      return false;
    }
  }
  return true;
}

function threadThrough(body: IrBody, cfg: IrCfg, c: i32, scratch: IrScratch): void {
  let blk = body.blocks[c];
  let term = blk.insts[blk.insts.length - 1];
  let p = conditionParam(body, c);
  let negated = conditionNegated(body, c);
  let targets = growable<i32>([
    body.extra[body.successorRecord(term, 0)],
    body.extra[body.successorRecord(term, 1)],
  ]);
  let users = buildUseLists(body, scratch);
  let count = body.instCount();
  var j = -1;
  for (var k = 0; k < blk.params.length; k += 1) {
    if (blk.params[k] == p) {
      j = k;
    }
  }

  // Which of the continuation's parameters each target's region uses,
  // and the parameter the target gets for each.
  let fwd = new Array<i32>(count);
  for (var i = 0; i < count; i += 1) {
    fwd.push(-1);
  }
  for (var side = 0; side < 2; side += 1) {
    let s = targets[side];
    let used = new Array<i32>();
    for (let q in blk.params) {
      var usedHere = false;
      for (var k = 0; k < users.count(q); k += 1) {
        let u = users.at(q, k);
        if (u == term || u == body.a[term]) {
          continue;
        }
        if (armOf(cfg, targets[0], targets[1], body.instBlock[u]) == side) {
          usedHere = true;
        }
      }
      if (usedHere) {
        used.push(q);
      }
    }
    if (used.length == 0) {
      continue;
    }
    for (var i = 0; i < count; i += 1) {
      fwd[i] = -1;
    }
    for (let q in used) {
      let id = body.opcode.length;
      body.opcode.push(IrOp.param as i32);
      body.typeId.push(body.typeId[q]);
      body.a.push(-1);
      body.b.push(-1);
      body.instBlock.push(s);
      body.blocks[s].params.push(id);
      fwd[q] = id;
    }
    // Uses in the target's region move to the target's parameter.
    let stack = growable<i32>([s]);
    while (stack.length > 0) {
      let b = stack.pop();
      for (let inst in body.blocks[b].insts) {
        if (body.op(inst) != IrOp.nop) {
          body.rewriteValueOperands(inst, (v) => {
            if (v >= 0 && v < count && fwd[v] >= 0) {
              return fwd[v];
            }
            return v;
          });
        }
      }
      for (var childK = 0; childK < cfg.domChildCount(b); childK += 1) {
        let child = cfg.domChild(b, childK);
        stack.push(child);
      }
    }
    // The continuation's own edge passes its parameters through.
    appendArgs(body, term, side, used);
  }

  // Each predecessor edge with a constant flag goes straight to the
  // arm the flag selects, passing what that edge passes to the
  // continuation wherever the arm's record names a continuation
  // parameter.
  let edges = new Array<i32>();
  let edgeIndex = new Array<i32>();
  for (var predK = 0; predK < cfg.predCount(c); predK += 1) {
    let pred = cfg.pred(c, predK);
    let pInsts = body.blocks[pred].insts;
    let pTerm = pInsts[pInsts.length - 1];
    var seen = false;
    for (let t in edges) {
      if (t == pTerm) {
        seen = true;
      }
    }
    if (seen) {
      continue;
    }
    let psN = body.successorCount(pTerm);
    for (var k = 0; k < psN; k += 1) {
      if (body.extra[body.successorRecord(pTerm, k)] == c) {
        edges.push(pTerm);
        edgeIndex.push(k);
      }
    }
  }
  for (var e = 0; e < edges.length; e += 1) {
    let pTerm = edges[e];
    let k = edgeIndex[e];
    let incoming = body.successorRecord(pTerm, k);
    if (body.extra[incoming] != c) {
      // A predecessor with both arms into the block is listed once per
      // arm; each (terminator, slot) pair is handled once.
      continue;
    }
    if (body.extra[incoming + 1] != blk.params.length) {
      throw new Error('thread: edge into b' + i32ToString(c) + ' passes ' +
          i32ToString(body.extra[incoming + 1]) + ' args for ' +
          i32ToString(blk.params.length) + ' params');
    }
    let flag = body.extra[incoming + 2 + j];
    if (body.op(flag) != IrOp.const_i32) {
      continue;
    }
    var taken = body.a[flag] != 0;
    if (negated) {
      taken = !taken;
    }
    let side = if (taken) 0 else 1;
    let armRecord = body.successorRecord(term, side);
    let armArgc = body.extra[armRecord + 1];
    let newArgs = new Array<i32>();
    var i = 0;
    while (i < armArgc) {
      let v = body.extra[armRecord + 2 + i];
      var mapped = v;
      for (var q = 0; q < blk.params.length; q += 1) {
        if (blk.params[q] == v) {
          mapped = body.extra[incoming + 2 + q];
        }
      }
      newArgs.push(mapped);
      i += 1;
    }
    retarget(body, pTerm, k, body.extra[armRecord], newArgs);
  }
}

/** Appends `values` to the arguments of successor `k` of `term`. */
function appendArgs(body: IrBody, term: i32, k: i32,
    values: GrowableArray<i32>): void {
  let s = body.successorRecord(term, k);
  let argc = body.extra[s + 1];
  let args = new Array<i32>(argc);
  var i = 0;
  while (i < argc) {
    args.push(body.extra[s + 2 + i]);
    i += 1;
  }
  for (let v in values) {
    args.push(v);
  }
  retarget(body, term, k, body.extra[s], args);
}

VersionPublishedDependenciesApproved by
0.0.2-preview.1 2026-11-19