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
/**
 * CFG analyses over a ZIR body: predecessors, reverse postorder, and
 * dominators (Cooper–Harvey–Kennedy). Shared by the verifier and the
 * emitter. Computed once per body on demand; bodies are not mutated
 * between construction and use in the current pipeline.
 */
import { IrBody, IrScratch } from './ir.zena';

export final class IrCfg {
  body: IrBody;
  // The per-block lists are packed, block b's entries being
  // list[start[b] .. start[b + 1]): one array per table rather than one
  // per block, for a structure built several times per body per pass.
  /** Predecessor block ids per block. */
  predStart: GrowableArray<i32>;
  predList: GrowableArray<i32>;
  /** Successor block ids per block (edge order, duplicates preserved). */
  succStart: GrowableArray<i32>;
  succList: GrowableArray<i32>;
  /** Blocks in reverse postorder (entry first). */
  rpo: GrowableArray<i32>;
  /** Reverse-postorder number per block; -1 = unreachable from entry. */
  rpoIndex: GrowableArray<i32>;
  /** Immediate dominator per block; entry's is itself; -1 = unreachable. */
  idom: GrowableArray<i32>;
  /** Dominator-tree children per block, in ascending RPO order. */
  domChildStart: GrowableArray<i32>;
  domChildList: GrowableArray<i32>;
  /** Where the tables came from; null means fresh lists of its own. */
  #scratch: IrScratch | null;

  predCount(block: i32): i32 {
    return this.predStart[block + 1] - this.predStart[block];
  }

  pred(block: i32, k: i32): i32 {
    return this.predList[this.predStart[block] + k];
  }

  succCount(block: i32): i32 {
    return this.succStart[block + 1] - this.succStart[block];
  }

  succ(block: i32, k: i32): i32 {
    return this.succList[this.succStart[block] + k];
  }

  domChildCount(block: i32): i32 {
    return this.domChildStart[block + 1] - this.domChildStart[block];
  }

  domChild(block: i32, k: i32): i32 {
    return this.domChildList[this.domChildStart[block] + k];
  }

  /**
   * With a pool, the tables and the temporaries come from the caller's
   * current scope, and the CFG must not outlive it: a pass builds its
   * CFG inside its own scope. Without one, the lists are fresh.
   */
  new(this.body, scratch: IrScratch | null = null)
    : predStart = listFrom(scratch), predList = listFrom(scratch),
      succStart = listFrom(scratch), succList = listFrom(scratch),
      rpo = listFrom(scratch), rpoIndex = listFrom(scratch),
      idom = listFrom(scratch),
      domChildStart = listFrom(scratch), domChildList = listFrom(scratch),
      #scratch = scratch {
    this.#computePreds();
    this.#computeRpo();
    this.#computeDominators();
    this.#computeDomChildren();
  }

  isReachable(block: i32): boolean {
    return this.rpoIndex[block] >= 0;
  }

  /** True if `block` has a predecessor that appears later in RPO. */
  isLoopHeader(block: i32): boolean {
    for (var pK = 0; pK < this.predCount(block); pK += 1) {
      let p = this.pred(block, pK);
      if (this.rpoIndex[p] >= this.rpoIndex[block]) {
        return true;
      }
    }
    return false;
  }

  /** True if `block` has two or more forward-edge predecessors. */
  isMergeNode(block: i32): boolean {
    var forward = 0;
    for (var pK = 0; pK < this.predCount(block); pK += 1) {
      let p = this.pred(block, pK);
      if (this.rpoIndex[p] < this.rpoIndex[block]) {
        forward += 1;
      }
    }
    return forward >= 2;
  }

  dominates(a: i32, b: i32): boolean {
    var blockId = b;
    while (true) {
      if (blockId == a) {
        return true;
      }
      if (blockId == 0) {
        return false;
      }
      blockId = this.idom[blockId];
      if (blockId < 0) {
        return false;
      }
    }
  }

  #computePreds(): void {
    let {body} = this;
    let nb = body.blocks.length;
    // Count each block's edges in and out, prefix-sum into the start
    // tables, then place.
    for (var b = 0; b <= nb; b += 1) {
      this.predStart.push(0);
      this.succStart.push(0);
    }
    var total = 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) {
        let target = body.extra[body.successorRecord(term, k)];
        if (target >= 0 && target < nb) {
          this.predStart[target + 1] = this.predStart[target + 1] + 1;
          this.succStart[b + 1] = this.succStart[b + 1] + 1;
          total += 1;
        }
      }
    }
    for (var b = 0; b < nb; b += 1) {
      this.predStart[b + 1] = this.predStart[b + 1] + this.predStart[b];
      this.succStart[b + 1] = this.succStart[b + 1] + this.succStart[b];
    }
    let predNext = listFrom(this.#scratch);
    let succNext = listFrom(this.#scratch);
    for (var b = 0; b < nb; b += 1) {
      predNext.push(this.predStart[b]);
      succNext.push(this.succStart[b]);
    }
    for (var i = 0; i < total; i += 1) {
      this.predList.push(0);
      this.succList.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) {
        let target = body.extra[body.successorRecord(term, k)];
        if (target >= 0 && target < nb) {
          this.predList[predNext[target]] = b;
          predNext[target] = predNext[target] + 1;
          this.succList[succNext[b]] = target;
          succNext[b] = succNext[b] + 1;
        }
      }
    }
  }

  #computeRpo(): void {
    let {body} = this;
    var i = 0;
    while (i < body.blocks.length) {
      this.rpoIndex.push(-1);
      i += 1;
    }
    if (body.blocks.length == 0) {
      return;
    }
    // Iterative DFS postorder from the entry, then reverse. A node must
    // finish only after all its (non-cyclic) successors have finished, so
    // each stack entry keeps a cursor into its successor list — the
    // simpler push-all-successors form finishes nodes too early and
    // produces orderings where a forward edge looks like a back edge.
    let postorder = listFrom(this.#scratch);
    let stack = listFrom(this.#scratch);
    let cursor = listFrom(this.#scratch);
    let visited = boolsFrom(this.#scratch);
    i = 0;
    while (i < body.blocks.length) {
      visited.push(false);
      i += 1;
    }
    stack.push(0);
    cursor.push(0);
    visited[0] = true;
    while (stack.length > 0) {
      let blockId = stack[stack.length - 1];
      let next = cursor[cursor.length - 1];
      if (next < this.succCount(blockId)) {
        cursor[cursor.length - 1] = next + 1;
        let target = this.succ(blockId, next);
        if (!visited[target]) {
          visited[target] = true;
          stack.push(target);
          cursor.push(0);
        }
        continue;
      }
      stack.pop();
      cursor.pop();
      postorder.push(blockId);
    }
    i = postorder.length - 1;
    while (i >= 0) {
      this.rpoIndex[postorder[i]] = this.rpo.length;
      this.rpo.push(postorder[i]);
      i -= 1;
    }
  }

  /** Cooper–Harvey–Kennedy iterative dominator computation over RPO. */
  #computeDominators(): void {
    var i = 0;
    while (i < this.body.blocks.length) {
      this.idom.push(-1);
      i += 1;
    }
    if (this.body.blocks.length == 0) {
      return;
    }
    this.idom[0] = 0;
    var changed = true;
    while (changed) {
      changed = false;
      var r = 1;
      while (r < this.rpo.length) {
        let blockId = this.rpo[r];
        var newIdom = -1;
        for (var predK = 0; predK < this.predCount(blockId); predK += 1) {
          let pred = this.pred(blockId, predK);
          if (this.rpoIndex[pred] < 0 || this.idom[pred] < 0) {
            continue; // unreachable or not yet processed
          }
          if (newIdom < 0) {
            newIdom = pred;
          } else {
            newIdom = this.#intersect(pred, newIdom);
          }
        }
        if (newIdom >= 0 && this.idom[blockId] != newIdom) {
          this.idom[blockId] = newIdom;
          changed = true;
        }
        r += 1;
      }
    }
  }

  #intersect(x: i32, y: i32): i32 {
    var a = x;
    var b = y;
    while (a != b) {
      while (this.rpoIndex[a] > this.rpoIndex[b]) {
        a = this.idom[a];
      }
      while (this.rpoIndex[b] > this.rpoIndex[a]) {
        b = this.idom[b];
      }
    }
    return a;
  }

  #computeDomChildren(): void {
    let nb = this.body.blocks.length;
    for (var b = 0; b <= nb; b += 1) {
      this.domChildStart.push(0);
    }
    var r = 1;
    while (r < this.rpo.length) {
      let blockId = this.rpo[r];
      let parent = this.idom[blockId];
      if (parent >= 0 && parent != blockId) {
        this.domChildStart[parent + 1] = this.domChildStart[parent + 1] + 1;
      }
      r += 1;
    }
    for (var b = 0; b < nb; b += 1) {
      this.domChildStart[b + 1] = this.domChildStart[b + 1] + this.domChildStart[b];
    }
    let next = listFrom(this.#scratch);
    for (var b = 0; b < nb; b += 1) {
      next.push(this.domChildStart[b]);
    }
    let total = this.domChildStart[nb];
    for (var i = 0; i < total; i += 1) {
      this.domChildList.push(0);
    }
    // Walk in RPO so children lists come out in ascending RPO order.
    r = 1;
    while (r < this.rpo.length) {
      let blockId = this.rpo[r];
      let parent = this.idom[blockId];
      if (parent >= 0 && parent != blockId) {
        this.domChildList[next[parent]] = blockId;
        next[parent] = next[parent] + 1;
      }
      r += 1;
    }
  }
}

function listFrom(scratch: IrScratch | null): GrowableArray<i32> {
  return if (scratch != null) scratch.i32() else new Array<i32>();
}

function boolsFrom(scratch: IrScratch | null): GrowableArray<boolean> {
  return if (scratch != null) scratch.bool() else new Array<boolean>();
}
VersionPublishedDependenciesApproved by
0.0.2-preview.1 2026-11-19