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

14.8 KiB Raw
/**
 * Sparse conditional constant propagation (docs/design/
 * optimization-pipeline.md §SCCP), the Wegman–Zadeck algorithm over
 * ZIR: every value starts as "not yet seen" and every block as
 * unexecuted, and the two worklists lower values to a constant or to
 * "varies" while marking the edges a branch on a known constant can
 * actually take. The optimism is the point. The peephole pass folds a
 * branch whose condition is already a constant instruction; this
 * pass folds a branch whose condition is constant only because the
 * arm that would change it is dead — and that arm is dead only
 * because the condition is constant. A loop that assigns a variable
 * on a path the variable's own value rules out is the shape:
 *
 *   var x = 1;
 *   while (i < n) { if (x != 1) { x = 2; } i += 1; }
 *
 * The header's parameter for x meets 1 from the entry and, from the
 * back edge, the join's parameter — which meets only the untaken
 * arm's value, x itself. So x is 1, the test folds, and the arm goes.
 * Block parameters are where the precision lives: a parameter meets
 * only the arguments arriving on executed edges.
 *
 * Constant evaluation is the shared table in fold.zena, so this pass
 * and the peephole pass fold the same operations to the same values.
 * Type tests use castOutcome from the same file, so a `match` over a
 * value of known exact type decides here as well as there.
 *
 * Rewrites, after the analysis reaches its fixpoint: a constant
 * instruction becomes the constant in place; a constant block
 * parameter is deleted the way blockmerge deletes a trivial one, with
 * a fresh constant at the head of its block standing in; a `br_if` or
 * `br_table` with one executable edge becomes a `br`. Blocks no
 * executable edge reaches are left for the block cleanup pass, which
 * must run after this one (the verifier rejects unreachable blocks).
 * A function whose try-join block would become unreachable is left
 * alone entirely, for the reason blockmerge gives.
 *
 * Determinism: the lattice fixpoint does not depend on worklist
 * order, and the rewrites read only the fixpoint, in id order.
 */
import { IrBlock, IrBody, IrOp, buildUseLists, IrScratch } from './ir.zena';
import { ValTypeRef } from '../wasm.zena';
import {
  IrConst, castOutcome, constOf, evalBinary, evalUnary, foldInstTo,
  isFoldableBinary, isFoldableUnary,
} from './fold.zena';
import { dropBranchArg, dropParamAt } from './blockmerge.zena';
import { rewriteToBr } from './simplify.zena';

/** Lattice states: not yet seen, a known constant, varies. */
let TOP = 0;
let CONST = 1;
let BOTTOM = 2;

/** Runs the pass; returns the number of rewrites made. */
export function runSccp(body: IrBody, scratch: IrScratch): i32 {
  scratch.enter();
  let result = runSccpOn(body, scratch);
  scratch.exit();
  return result;
}

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

  // Control-flow edges, numbered in block order so a terminator's
  // edges are contiguous: edge k of block b is termFirstEdge[b] + k.
  let edgeTerm = scratch.i32();
  let edgeTarget = scratch.i32();
  let edgeArgStart = scratch.i32();
  let edgeExec = scratch.bool();
  let termFirstEdge = scratch.i32();
  let termEdgeCount = scratch.i32();
  let incoming = new Array<GrowableArray<i32>>();
  for (var b = 0; b < nb; b += 1) {
    termFirstEdge.push(-1);
    termEdgeCount.push(0);
    incoming.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 n = body.successorCount(term);
    termFirstEdge[b] = edgeTerm.length;
    termEdgeCount[b] = n;
    for (var k = 0; k < n; k += 1) {
      let rec = body.successorRecord(term, k);
      let target = body.extra[rec];
      incoming[target].push(edgeTerm.length);
      edgeTerm.push(term);
      edgeTarget.push(target);
      edgeArgStart.push(rec + 2);
      edgeExec.push(false);
    }
  }

  // Def → users, for the SSA worklist. Branch arguments make the
  // terminator a user, which is what re-meets a target's parameters
  // when an argument lowers.
  let users = buildUseLists(body, scratch);

  let state = scratch.i32();
  let value = new Array<IrConst | null>();
  for (var i = 0; i < count; i += 1) {
    state.push(TOP);
    value.push(null);
  }
  let blockExec = scratch.bool();
  for (var b = 0; b < nb; b += 1) {
    blockExec.push(false);
  }
  let ssaWork = scratch.i32();
  let flowWork = scratch.i32();

  // Moves an instruction's lattice value down to (s, v). Values only
  // descend: a constant that meets a different constant varies.
  let lower = (inst: i32, s: i32, v: IrConst | null) => {
    let old = state[inst];
    if (old == BOTTOM || s == TOP) {
      return;
    }
    var newState = s;
    var newValue = v;
    if (old == CONST) {
      if (s == CONST) {
        let ov = value[inst];
        if (ov != null) {
          if (v != null) {
            if (ov.equals(v)) {
              return;
            }
          }
        }
      }
      newState = BOTTOM;
      newValue = null;
    }
    state[inst] = newState;
    value[inst] = newValue;
    for (var k = 0; k < users.count(inst); k += 1) {
      ssaWork.push(users.at(inst, k));
    }
  };

  let markEdge = (e: i32) => {
    if (!edgeExec[e]) {
      edgeExec[e] = true;
      flowWork.push(e);
    }
  };

  // A block parameter meets the arguments arriving on executed edges;
  // arguments not yet seen are ignored, which is the optimism.
  let visitParam = (p: i32, b: i32, j: i32) => {
    var s = TOP;
    var v: IrConst | null = null;
    for (let e in incoming[b]) {
      if (!edgeExec[e]) {
        continue;
      }
      let arg = body.extra[edgeArgStart[e] + j];
      let argState = if (arg >= 0 && arg < count) state[arg] else BOTTOM;
      if (argState == TOP) {
        continue;
      }
      if (argState == BOTTOM) {
        s = BOTTOM;
        v = null;
        break;
      }
      let av = value[arg];
      if (s == TOP) {
        s = CONST;
        v = av;
        continue;
      }
      var same = false;
      if (v != null) {
        if (av != null) {
          same = v.equals(av);
        }
      }
      if (!same) {
        s = BOTTOM;
        v = null;
        break;
      }
    }
    lower(p, s, v);
  };

  let visitBlockParams = (b: i32) => {
    let params = body.blocks[b].params;
    for (var j = 0; j < params.length; j += 1) {
      visitParam(params[j], b, j);
    }
  };

  let visitTerminator = (inst: i32, b: i32) => {
    let first = termFirstEdge[b];
    let n = termEdgeCount[b];
    if (n == 0) {
      return;
    }
    let op = body.op(inst);
    if (op == IrOp.br_if || op == IrOp.br_table) {
      let cond = body.a[inst];
      let cs = state[cond];
      if (cs == TOP) {
        return;
      }
      let cv = value[cond];
      if (cs == CONST && cv != null) {
        if (op == IrOp.br_if) {
          markEdge(first + (if (cv.i != 0) 0 else 1));
        } else {
          // wasm reads the selector as unsigned: negative picks the
          // default, which is the last successor.
          let v = cv.i;
          markEdge(first + (if (v >= 0 && v < n - 1) v else n - 1));
        }
      } else {
        for (var k = 0; k < n; k += 1) {
          markEdge(first + k);
        }
      }
    } else {
      // br, try_br, br_on_cast, yield_, await_: every edge may run.
      for (var k = 0; k < n; k += 1) {
        markEdge(first + k);
      }
    }
    // The branch arguments may be what changed: re-meet the params of
    // every successor already executing (new ones meet from the flow
    // worklist).
    for (var k = 0; k < n; k += 1) {
      let e = first + k;
      if (edgeExec[e] && blockExec[edgeTarget[e]]) {
        visitBlockParams(edgeTarget[e]);
      }
    }
  };

  let visitInst = (inst: i32) => {
    let op = body.op(inst);
    if (op == IrOp.nop) {
      return;
    }
    let b = body.instBlock[inst];
    if (op == IrOp.param) {
      if (b == 0) {
        lower(inst, BOTTOM, null);
        return;
      }
      let params = body.blocks[b].params;
      for (var j = 0; j < params.length; j += 1) {
        if (params[j] == inst) {
          visitParam(inst, b, j);
          return;
        }
      }
      return;
    }
    let insts = body.blocks[b].insts;
    if (insts.length > 0 && insts[insts.length - 1] == inst) {
      visitTerminator(inst, b);
      return;
    }
    if (!body.producesValue(inst) || state[inst] == BOTTOM) {
      return;
    }
    let own = constOf(body, inst);
    if (own != null) {
      lower(inst, CONST, own);
      return;
    }
    let av = body.a[inst];
    if (op == IrOp.ref_is_null) {
      let from = body.resultType(av);
      if (from != null && from is ValTypeRef) {
        lower(inst, CONST, IrConst.ofBool(false));
        return;
      }
      lower(inst, BOTTOM, null);
      return;
    }
    if (op == IrOp.ref_test) {
      let from = body.resultType(av);
      if (from != null && body.b[inst] >= 0) {
        let outcome = castOutcome(from, body.typeTable[body.b[inst]]);
        if (outcome >= 0) {
          lower(inst, CONST, IrConst.ofBool(outcome == 1));
          return;
        }
      }
      lower(inst, BOTTOM, null);
      return;
    }
    if (isFoldableBinary(op)) {
      let bv = body.b[inst];
      if (state[av] == TOP || state[bv] == TOP) {
        return; // an operand is still to come
      }
      let x = value[av];
      let y = value[bv];
      if (x != null) {
        if (y != null) {
          let r = evalBinary(op, x, y);
          if (r != null) {
            lower(inst, CONST, r);
            return;
          }
        }
      }
      lower(inst, BOTTOM, null);
      return;
    }
    if (isFoldableUnary(op)) {
      if (state[av] == TOP) {
        return;
      }
      let x = value[av];
      if (x != null) {
        let r = evalUnary(op, x);
        if (r != null) {
          lower(inst, CONST, r);
          return;
        }
      }
      lower(inst, BOTTOM, null);
      return;
    }
    lower(inst, BOTTOM, null);
  };

  let visitBlock = (b: i32) => {
    visitBlockParams(b);
    for (let inst in body.blocks[b].insts) {
      visitInst(inst);
    }
  };

  blockExec[0] = true;
  for (let p in body.blocks[0].params) {
    lower(p, BOTTOM, null);
  }
  visitBlock(0);
  while (flowWork.length > 0 || ssaWork.length > 0) {
    if (flowWork.length > 0) {
      let e = flowWork.pop();
      let t = edgeTarget[e];
      if (!blockExec[t]) {
        blockExec[t] = true;
        visitBlock(t);
      } else {
        visitBlockParams(t);
      }
      continue;
    }
    let inst = ssaWork.pop();
    if (blockExec[body.instBlock[inst]]) {
      visitInst(inst);
    }
  }

  // A try's join block losing reachability is the case blockmerge
  // refuses to clean; refusing here too keeps the function verifiable.
  for (var i = 0; i < count; i += 1) {
    if (body.op(i) == IrOp.try_br && blockExec[body.instBlock[i]]) {
      if (let (true, join) = body.tryJoin.get(i)) {
        if (!blockExec[join]) {
          return 0;
        }
      }
    }
  }

  var rewrites = 0;

  // Constant instructions become constants in place.
  for (var i = 0; i < count; i += 1) {
    if (state[i] != CONST) {
      continue;
    }
    let op = body.op(i);
    if (op == IrOp.param || op == IrOp.const_i32 || op == IrOp.const_i64 ||
        op == IrOp.const_f64) {
      continue;
    }
    let c = value[i];
    if (c != null) {
      foldInstTo(body, i, c);
      rewrites += 1;
    }
  }

  // Constant block parameters: a constant at the head of the block
  // takes the parameter's uses, and the parameter and its arguments
  // go. Higher indices first, so a deletion leaves the lower ones.
  let repl = scratch.i32();
  for (var i = 0; i < count; i += 1) {
    repl.push(i);
  }
  var paramsRemoved = 0;
  for (var b = 1; b < nb; b += 1) {
    if (!blockExec[b]) {
      continue;
    }
    let blk = body.blocks[b];
    let heads = new Array<i32>();
    var j = blk.params.length - 1;
    while (j >= 0) {
      let p = blk.params[j];
      let c = value[p];
      if (state[p] == CONST && c != null) {
        let id = newConst(body, b, body.typeId[p], c);
        heads.push(id);
        repl[p] = id;
        nopOut(body, p);
        dropParamAt(blk, j);
        for (let term in uniqueTerms(body, incoming[b], edgeTerm)) {
          dropBranchArg(body, term, b, j);
        }
        paramsRemoved += 1;
      }
      j -= 1;
    }
    if (heads.length > 0) {
      prependInsts(blk, heads);
    }
  }
  rewrites += paramsRemoved;

  // Branches with one executable edge become unconditional.
  for (var b = 0; b < nb; b += 1) {
    if (!blockExec[b] || termEdgeCount[b] < 2) {
      continue;
    }
    let insts = body.blocks[b].insts;
    let term = insts[insts.length - 1];
    let op = body.op(term);
    if (op != IrOp.br_if && op != IrOp.br_table) {
      continue;
    }
    var live = -1;
    var liveCount = 0;
    for (var k = 0; k < termEdgeCount[b]; k += 1) {
      if (edgeExec[termFirstEdge[b] + k]) {
        live = k;
        liveCount += 1;
      }
    }
    if (liveCount == 1) {
      let succs = body.successors(term);
      rewriteToBr(body, term, succs[live]);
      rewrites += 1;
    }
  }

  if (paramsRemoved > 0) {
    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 rewrites;
}

/** A fresh constant instruction of the given type, owned by `block`. */
function newConst(body: IrBody, block: i32, typeId: i32, c: IrConst): i32 {
  let id = body.opcode.length;
  body.opcode.push(IrOp.nop as i32);
  body.typeId.push(typeId);
  body.a.push(-1);
  body.b.push(-1);
  body.instBlock.push(block);
  foldInstTo(body, id, c);
  return id;
}

/** Puts `ids` ahead of the block's existing instructions. */
function prependInsts(blk: IrBlock, ids: GrowableArray<i32>): void {
  let old = new Array<i32>();
  for (let i in blk.insts) {
    old.push(i);
  }
  while (blk.insts.length > 0) {
    blk.insts.pop();
  }
  for (let i in ids) {
    blk.insts.push(i);
  }
  for (let i in old) {
    blk.insts.push(i);
  }
}

/**
 * The distinct terminators behind a block's incoming edges, in edge
 * order: a branch both of whose edges reach the block has its
 * argument dropped once.
 */
function uniqueTerms(body: IrBody, edges: GrowableArray<i32>,
    edgeTerm: GrowableArray<i32>): GrowableArray<i32> {
  let terms = new Array<i32>();
  for (let e in edges) {
    let t = edgeTerm[e];
    if (terms.length == 0 || terms[terms.length - 1] != t) {
      terms.push(t);
    }
  }
  return terms;
}

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