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.4 KiB Raw
/**
 * Loop-invariant code motion (docs/design/optimization-pipeline.md
 * §LICM): an instruction inside a loop whose operands are all defined
 * outside it computes the same value every iteration, so it moves to
 * just before the loop, into the block that immediately dominates the
 * loop header.
 *
 * Only pure instructions that cannot trap move freely: arithmetic,
 * tests, immutable global reads, and loads through a receiver whose
 * type is non-null (an immutable field, an array length, a fat
 * pointer's two fields). A moved instruction may then run on a path
 * that never enters the loop, which is harmless for exactly these.
 * Allocations stay, since one object per iteration and one object
 * shared by all iterations are different programs.
 *
 * A pure instruction that can trap (a cast, a load through a nullable
 * receiver) moves only out of the loop header, only when nothing kept
 * ahead of it in the header has an effect, and only when the
 * destination block jumps straight to the header: then the header
 * runs on every entry to the loop, so the instruction would have run,
 * and trapped or not, before anything the loop does. This is the cast of
 * an interface-typed array's instance in `while (i < xs.length)`,
 * which every inlined accessor repeats.
 *
 * The dominating block is the right destination without building a
 * preheader: every value defined outside the loop that a use in the
 * loop can see dominates the header, so it lies on the header's
 * dominator chain and is available at the end of the header's
 * immediate dominator.
 *
 * Loops are the natural loops of the back edges (an edge to a block
 * that dominates its source). The pass repeats while something moved,
 * so an instruction hoisted out of an inner loop can leave the outer
 * one on the next pass.
 *
 * The client this exists for: a loop over an interface-typed array,
 * whose fat-pointer unpack and vtable-slot load happen once instead
 * of every iteration (array-mutability.md, "Required optimizations").
 *
 * Determinism: blocks in reverse postorder, instructions in block
 * order.
 */
import {
  IrBody, IrOp, IrRefField, IrRefGlobal, isBinaryNumericOp,
  isUnaryNumericOp, IrScratch } from './ir.zena';
import { IrCfg } from './cfg.zena';
import { ValTypeRef } from '../wasm.zena';

/** Runs the pass; returns the number of instructions moved. */
export function runLicm(body: IrBody, scratch: IrScratch): i32 {
  scratch.enter();
  let result = runLicmOn(body, scratch);
  scratch.exit();
  return result;
}

function runLicmOn(body: IrBody, scratch: IrScratch): i32 {
  var total = 0;
  var pass = 0;
  while (pass < 3) {
    let moved = hoistOnce(body, scratch);
    total += moved;
    if (moved == 0) {
      break;
    }
    pass += 1;
  }
  return total;
}

function hoistOnce(body: IrBody, scratch: IrScratch): i32 {
  scratch.enter();
  let result = hoistOnceOn(body, scratch);
  scratch.exit();
  return result;
}

function hoistOnceOn(body: IrBody, scratch: IrScratch): i32 {
  let cfg = new IrCfg(body, scratch);
  let nb = body.blocks.length;
  let dominates = (a: i32, b: i32): boolean => {
    var cur = b;
    while (cur >= 0) {
      if (cur == a) {
        return true;
      }
      if (cur == 0) {
        return false;
      }
      cur = cfg.idom[cur];
    }
    return false;
  };

  var moved = 0;
  // Headers in reverse postorder; each header's loop is the union of
  // its back edges' natural loops.
  for (let h in cfg.rpo) {
    let inLoop = new Array<boolean>(nb);
    for (var i = 0; i < nb; i += 1) {
      inLoop.push(false);
    }
    var isHeader = false;
    for (var pK = 0; pK < cfg.predCount(h); pK += 1) {
      let p = cfg.pred(h, pK);
      if (!cfg.isReachable(p) || !dominates(h, p)) {
        continue;
      }
      isHeader = true;
      // Everything that reaches the back edge's source without
      // passing the header is in the loop.
      inLoop[h] = true;
      let work = new Array<i32>();
      if (!inLoop[p]) {
        inLoop[p] = true;
        work.push(p);
      }
      while (work.length > 0) {
        let b = work.pop();
        for (var qK = 0; qK < cfg.predCount(b); qK += 1) {
          let q = cfg.pred(b, qK);
          if (cfg.isReachable(q) && !inLoop[q]) {
            inLoop[q] = true;
            work.push(q);
          }
        }
      }
    }
    if (!isHeader || h == 0) {
      continue;
    }
    let dest = cfg.idom[h];
    if (dest < 0) {
      continue;
    }
    let destBlk = body.blocks[dest];
    // A trap-capable instruction may move only when the destination
    // falls straight into the header: with blocks in between (a null
    // check that leaves early, say) the instruction would run on a
    // path that never reaches the loop.
    var straightIn = destBlk.insts.length > 0;
    if (straightIn) {
      let sN = body.successorCount(destBlk.insts[destBlk.insts.length - 1]);
      for (var sK = 0; sK < sN; sK += 1) {
        let sRec = body.successorRecord(destBlk.insts[destBlk.insts.length - 1], sK);
        if (body.extra[sRec] != h) {
          straightIn = false;
        }
      }
    }
    let outside = (v: i32): boolean => {
      if (v < 0) {
        return true;
      }
      let b = body.instBlock[v];
      return b < 0 || !inLoop[b];
    };
    let operands = new Array<i32>();
    // Two sweeps over the loop's blocks, so a chain of invariant
    // instructions moves together even when a later block defines
    // what an earlier one (in reverse postorder) uses.
    var sweep = 0;
    while (sweep < 2) {
      for (let b in cfg.rpo) {
        if (!inLoop[b]) {
          continue;
        }
        let blk = body.blocks[b];
        let kept = new Array<i32>();
        // In the header, a trap-capable candidate may move while every
        // instruction kept ahead of it is pure.
        var headerPure = b == h && straightIn;
        for (let inst in blk.insts) {
          if (body.op(inst) == IrOp.nop) {
            kept.push(inst);
            continue;
          }
          let pure = hoistable(body, inst);
          let trapping = !pure && headerPure && trapHoistable(body, inst);
          if (!pure && !trapping) {
            kept.push(inst);
            headerPure = false;
            continue;
          }
          while (operands.length > 0) {
            operands.pop();
          }
          body.appendValueOperands(inst, operands);
          var invariant = true;
          for (let o in operands) {
            if (!outside(o)) {
              invariant = false;
            }
          }
          if (!invariant) {
            kept.push(inst);
            if (trapping) {
              headerPure = false;
            }
            continue;
          }
          // Move: out of this block, in before the destination's
          // terminator.
          let term = destBlk.insts.pop();
          destBlk.insts.push(inst);
          destBlk.insts.push(term);
          body.instBlock[inst] = dest;
          moved += 1;
        }
        if (kept.length != blk.insts.length) {
          while (blk.insts.length > 0) {
            blk.insts.pop();
          }
          for (let k in kept) {
            blk.insts.push(k);
          }
        }
      }
      sweep += 1;
    }
  }
  return moved;
}

/** Pure, trap-free, and not an allocation: safe to run speculatively. */
function hoistable(body: IrBody, inst: i32): boolean {
  if (body.typeId[inst] < 0) {
    return false;
  }
  let op = body.op(inst);
  if (op == IrOp.const_i32 || op == IrOp.const_i64 ||
      op == IrOp.const_f32 || op == IrOp.const_f64) {
    return true;
  }
  if (isBinaryNumericOp(op)) {
    return op != IrOp.i32_div_s && op != IrOp.i32_div_u &&
        op != IrOp.i32_rem_s && op != IrOp.i32_rem_u &&
        op != IrOp.i64_div_s && op != IrOp.i64_div_u &&
        op != IrOp.i64_rem_s && op != IrOp.i64_rem_u;
  }
  if (isUnaryNumericOp(op)) {
    return true;
  }
  if (op == IrOp.ref_null || op == IrOp.ref_is_null ||
      op == IrOp.ref_test || op == IrOp.ref_eq || op == IrOp.ref_func ||
      op == IrOp.extern_convert_any || op == IrOp.any_convert_extern) {
    return true;
  }
  if (op == IrOp.global_get) {
    let r = body.refTable[body.b[inst]];
    if (r is IrRefGlobal) {
      return !r.target.isMutable;
    }
    return false;
  }
  if (op == IrOp.struct_get || op == IrOp.array_len ||
      op == IrOp.iface_vtable || op == IrOp.iface_instance) {
    let receiver = body.a[inst];
    if (receiver < 0) {
      return false;
    }
    let t = body.resultType(receiver);
    if (t == null || !(t is ValTypeRef)) {
      return false;
    }
    if (op == IrOp.struct_get) {
      return fieldIsImmutable(body, inst);
    }
    return true;
  }
  return false;
}

/**
 * Pure but able to trap: a cast, a null assertion, or a load of an
 * immutable field, an array length or a fat pointer's fields through
 * a nullable receiver. Movable from a loop header alone.
 */
function trapHoistable(body: IrBody, inst: i32): boolean {
  if (body.typeId[inst] < 0) {
    return false;
  }
  let op = body.op(inst);
  if (op == IrOp.ref_cast || op == IrOp.ref_as_non_null) {
    return true;
  }
  if (op == IrOp.array_len || op == IrOp.iface_vtable ||
      op == IrOp.iface_instance) {
    return body.a[inst] >= 0;
  }
  if (op == IrOp.struct_get) {
    return body.a[inst] >= 0 && fieldIsImmutable(body, inst);
  }
  return false;
}

function fieldIsImmutable(body: IrBody, inst: i32): boolean {
  let r = body.refTable[body.b[inst]];
  if (r is IrRefField) {
    let idx = r.owner.fieldIndexByName(r.fieldName);
    return idx >= 0 && !r.owner.fields[idx].isMutable;
  }
  return false;
}
VersionPublishedDependenciesApproved by
0.0.2-preview.1 2026-11-19