compiler 0.0.2-preview.1
The Zena self-hosted compiler
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.jsonmanifest 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);
}
- zena-lang:wit-parser wit-parser.zena-lang.pkg.zena-lang.dev ~0.0.1-preview.1
| Version | Published | Dependencies | Approved by |
|---|---|---|---|
| 0.0.2-preview.1 | 2026-11-19 |
|
|