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
18.9 KiB
Raw
/**
* CFG cleanup (docs/design/optimization-pipeline.md, cleanup set):
* removes blocks unreachable from the entry after branch folding. The
* verifier requires every block reachable, so folding a `br_if` on a
* constant is only legal paired with this pass.
*
* Removal is physical — the block list is compacted and every
* surviving terminator's targets are renumbered — because block ids
* are indices. The target of every successor sits exactly two `extra`
* slots before its first branch arg (the [target, argc, args…] layout
* every terminator shares, see successors() in ir.zena), so
* renumbering writes through IrSuccessor.argStart - 2 rather than
* re-decoding each terminator shape.
*
* Two more cleanups keep the graph in the shape the emitter reads
* best. A block whose only instruction is a `br` forwards every edge
* into it straight to its target (jump to jump), and a block whose
* sole predecessor ends in an unconditional `br` to it fuses into that
* predecessor. Both matter to the emitter's loop-exit placement: it
* puts an exit block after the loop's `end`, behind a label, only
* when the exit is a dominator child of the loop header, and an
* inlined body leaves the header holding one jump into the inlined
* test, whose exhausted arm is one more jump to the exit. Without the
* two cleanups the exit sits two levels down and the emitter falls
* back to an if/else with the exit's code inside the loop, which
* wasmtime compiles a good deal worse.
*/
import { IrBlock, IrBody, IrOp, IrScratch } from './ir.zena';
import { isValSubtype } from '../wasm-module.zena';
/**
* Runs the cleanups; returns the number of blocks removed plus the
* number of block parameters deleted plus the number of edges
* forwarded and blocks fused.
*/
export function runBlockCleanup(body: IrBody, scratch: IrScratch): i32 {
scratch.enter();
let result = runBlockCleanupOn(body, scratch);
scratch.exit();
return result;
}
function runBlockCleanupOn(body: IrBody, scratch: IrScratch): i32 {
var n = removeUnreachable(body, scratch) + removeTrivialParams(body, scratch);
let forwarded = forwardEmptyBlocks(body, scratch);
let fused = fuseStraightLine(body, scratch);
if (forwarded > 0 || fused > 0) {
n += forwarded + fused + removeUnreachable(body, scratch) + removeTrivialParams(body, scratch);
}
return n;
}
/** The join blocks of the function's user tries, which stay as they are. */
function tryJoins(body: IrBody, scratch: IrScratch) {
let joins = scratch.i32();
for (let k in body.tryJoin.keys()) {
joins.push(body.tryJoin[k]);
}
return joins;
}
function isIn(list: GrowableArray<i32>, b: i32): boolean {
for (let x in list) {
if (x == b) {
return true;
}
}
return false;
}
/**
* Sends every edge into a block whose only instruction is a `br`
* straight to that br's target, with the br's arguments substituted
* for the block's parameters. Only edges from br/br_if/br_table are
* moved (a try_br's targets keep their shape for the emitter); a
* block some other edge still reaches keeps working as it was.
*/
function forwardEmptyBlocks(body: IrBody, scratch: IrScratch): i32 {
let nb = body.blocks.length;
let joins = tryJoins(body, scratch);
// Users of every value: a parameter of a forwarded block must feed
// nothing but the block's own br, since a block it dominates could
// otherwise read it and the forwarded edges would carry no value.
let count = body.instCount();
let useCount = scratch.i32();
for (var i = 0; i < count; i += 1) {
useCount.push(0);
}
let operands = scratch.i32();
for (var i = 0; i < count; i += 1) {
if (body.op(i) == IrOp.nop) {
continue;
}
operands.clear();
body.appendValueOperands(i, operands);
for (let v in operands) {
if (v >= 0 && v < count) {
useCount[v] += 1;
}
}
}
// The predecessors of every block along the edges this pass moves,
// kept current as it moves them, so each candidate looks only at
// the terminators that reach it rather than at every block's.
let preds = new Array<GrowableArray<i32>>(nb);
for (var b = 0; b < nb; b += 1) {
preds.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 op = body.op(term);
if (op != IrOp.br && op != IrOp.br_if && op != IrOp.br_table) {
continue;
}
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) {
preds[target].push(b);
}
}
}
var forwarded = 0;
for (var e = 1; e < nb; e += 1) {
let blk = body.blocks[e];
if (blk.insts.length == 0 || isIn(joins, e)) {
continue;
}
let term = blk.insts[blk.insts.length - 1];
if (body.op(term) != IrOp.br) {
continue;
}
var empty = true;
for (let inst in blk.insts) {
if (inst != term && body.op(inst) != IrOp.nop) {
empty = false;
}
}
if (!empty) {
continue;
}
let onward = body.successorRecord(term, 0);
let onwardTarget = body.extra[onward];
let onwardArgc = body.extra[onward + 1];
// Each parameter's uses are all in the br's argument list.
var paramsLocal = true;
for (let p in blk.params) {
var inArgs = 0;
var i = 0;
while (i < onwardArgc) {
if (body.extra[onward + 2 + i] == p) {
inArgs += 1;
}
i += 1;
}
if (useCount[p] != inArgs) {
paramsLocal = false;
}
}
if (!paramsLocal) {
continue;
}
if (onwardTarget == e) {
continue;
}
let ps = preds[e];
for (let b in ps) {
if (b == e) {
continue;
}
let pInsts = body.blocks[b].insts;
let pTerm = pInsts[pInsts.length - 1];
// Successor slots are re-decoded after every rewrite, since a
// rewrite appends a fresh record.
var k = 0;
while (true) {
if (k >= body.successorCount(pTerm)) {
break;
}
let rec = body.successorRecord(pTerm, k);
if (body.extra[rec] != e) {
k += 1;
continue;
}
let args = new Array<i32>();
var i = 0;
while (i < onwardArgc) {
let v = body.extra[onward + 2 + i];
var mapped = v;
for (var q = 0; q < blk.params.length; q += 1) {
if (blk.params[q] == v) {
mapped = body.extra[rec + 2 + q];
}
}
args.push(mapped);
i += 1;
}
retarget(body, pTerm, k, onwardTarget, args);
preds[onwardTarget].push(b);
forwarded += 1;
k += 1;
}
}
}
return forwarded;
}
/**
* Appends a block to its sole predecessor when that predecessor ends
* in an unconditional `br` to it and the block has no parameters
* (a single edge's parameters are trivial and already gone). Chains
* fuse in one call: the predecessor's new terminator is checked again.
*/
function fuseStraightLine(body: IrBody, scratch: IrScratch): i32 {
let nb = body.blocks.length;
let joins = tryJoins(body, scratch);
var fused = 0;
var progress = true;
let incoming = scratch.i32();
while (progress) {
progress = false;
// Incoming edge counts.
incoming.clear();
for (var b = 0; b < nb; b += 1) {
incoming.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) {
incoming[body.extra[body.successorRecord(term, k)]] += 1;
}
}
for (var p = 0; p < nb; p += 1) {
let pBlk = body.blocks[p];
if (pBlk.insts.length == 0) {
continue;
}
let pTerm = pBlk.insts[pBlk.insts.length - 1];
if (body.op(pTerm) != IrOp.br) {
continue;
}
let s = body.extra[body.successorRecord(pTerm, 0)];
if (s == p || s == 0 || incoming[s] != 1 || isIn(joins, s)) {
continue;
}
let sBlk = body.blocks[s];
if (sBlk.params.length > 0 || sBlk.insts.length == 0) {
continue;
}
// Move: the predecessor's br goes, the block's instructions
// follow, the block empties (unreachable, removed afterwards).
nopOut(body, pTerm);
pBlk.insts.pop();
for (let inst in sBlk.insts) {
pBlk.insts.push(inst);
body.instBlock[inst] = p;
}
while (sBlk.insts.length > 0) {
sBlk.insts.pop();
}
incoming[s] = 0;
fused += 1;
progress = true;
// The next pass recounts edges; a chain continues from p.
break;
}
}
return fused;
}
/**
* Rebuilds a terminator's successor records with successor `k`
* replaced by `target(args)`. Records live inline in `extra`, so the
* rebuilt record is appended and the terminator repointed; every
* branch shape is [prefix] ([target, argc, args…])*.
*/
export function retarget(body: IrBody, term: i32, k: i32, target: i32,
args: GrowableArray<i32>): void {
let op = body.op(term);
let prefixLen = if (op == IrOp.br_on_cast || op == IrOp.br_on_cast_fail ||
op == IrOp.br_table) {
1
} else {
0
};
let recordStart = if (op == IrOp.br) body.a[term] else body.b[term];
let count = body.successorCount(term);
let idx = body.extra.length;
var p = 0;
while (p < prefixLen) {
body.extra.push(body.extra[recordStart + p]);
p += 1;
}
// The old records are read as the new ones are appended; the
// terminator still points at the old ones until the end.
var rec = body.successorRecord(term, 0);
for (var n = 0; n < count; n += 1) {
let argc = body.extra[rec + 1];
if (n == k) {
body.extra.push(target);
body.extra.push(args.length);
for (let v in args) {
body.extra.push(v);
}
} else {
body.extra.push(body.extra[rec]);
body.extra.push(argc);
var i = 0;
while (i < argc) {
body.extra.push(body.extra[rec + 2 + i]);
i += 1;
}
}
rec += 2 + argc;
}
if (op == IrOp.br) {
body.a[term] = idx;
} else {
body.b[term] = idx;
}
}
function removeUnreachable(body: IrBody, scratch: IrScratch): i32 {
let nb = body.blocks.length;
if (nb == 0) {
return 0;
}
let reachable = scratch.bool();
for (var i = 0; i < nb; i += 1) {
reachable.push(false);
}
let stack = scratch.i32();
reachable[0] = true;
stack.push(0);
while (stack.length > 0) {
let b = stack.pop();
let insts = body.blocks[b].insts;
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 (!reachable[target]) {
reachable[target] = true;
stack.push(target);
}
}
}
var removedCount = 0;
for (var i = 0; i < nb; i += 1) {
if (!reachable[i]) {
removedCount += 1;
}
}
if (removedCount == 0) {
return 0;
}
// A try's join block (IrBody.tryJoin) is where emission ends the
// protected region. It dies when folding or inlining leaves the try
// body no way to complete, as when the body calls a function that
// only throws; the try_br survives without it (renumbering drops
// the entry). No block is then reached through the body's normal
// exit, so nothing can be placed inside the try_table that belongs
// after it, which is what the join is there to prevent.
let instCount = body.instCount();
let map = scratch.i32();
var next = 0;
for (var i = 0; i < nb; i += 1) {
if (reachable[i]) {
map.push(next);
next += 1;
} else {
map.push(-1);
}
}
// Nop every instruction (params included) of the dead blocks so use
// counts, stats, and emission never see them again.
for (var i = 0; i < nb; i += 1) {
if (reachable[i]) {
continue;
}
let blk = body.blocks[i];
for (let p in blk.params) {
nopOut(body, p);
}
for (let inst in blk.insts) {
nopOut(body, inst);
}
}
// Renumber: instBlock for survivors, successor targets, tryJoin.
for (var i = 0; i < instCount; i += 1) {
let ob = body.instBlock[i];
if (ob >= 0 && ob < nb) {
body.instBlock[i] = map[ob];
}
}
for (var i = 0; i < nb; i += 1) {
if (!reachable[i]) {
continue;
}
let insts = body.blocks[i].insts;
let term = insts[insts.length - 1];
let sN = body.successorCount(term);
for (var sK = 0; sK < sN; sK += 1) {
let sRec = body.successorRecord(term, sK);
body.extra[(sRec + 2) - 2] = map[body.extra[sRec]];
}
}
let newJoin = new Map<i32, i32>();
for (var i = 0; i < instCount; i += 1) {
if (body.op(i) == IrOp.try_br) {
if (let (true, join) = body.tryJoin.get(i)) {
if (map[join] >= 0) {
newJoin[i] = map[join];
}
}
}
}
// tryJoin's field is immutable; rebuild its contents in place, in
// instruction-id order for determinism.
let oldKeys = scratch.i32();
for (let k in body.tryJoin.keys()) {
oldKeys.push(k);
}
for (let k in oldKeys) {
body.tryJoin.delete(k);
}
for (var i = 0; i < instCount; i += 1) {
if (body.op(i) == IrOp.try_br) {
if (let (true, join) = newJoin.get(i)) {
body.tryJoin[i] = join;
}
}
}
// Compact the block list in place (the field itself is immutable).
let survivors = new Array<IrBlock>();
for (var i = 0; i < nb; i += 1) {
if (reachable[i]) {
survivors.push(body.blocks[i]);
}
}
while (body.blocks.length > 0) {
body.blocks.pop();
}
for (let blk in survivors) {
body.blocks.push(blk);
}
return removedCount;
}
/**
* Deletes every block parameter that every incoming edge passes the
* same value for (a back edge passing the parameter itself does not
* count): uses of the parameter become that value, the parameter
* leaves the block, and its argument leaves every incoming branch.
* The value dominates the block because it dominates each
* predecessor.
*
* The common case is the continuation block an inlined callee returns
* through: its parameter is the callee's one returned value, and once
* the parameter is gone the forwarding rules in simplify see the
* allocation behind it. (Redirecting uses while leaving the parameter
* in place was tried first and made emission worse — the emitter
* coalesces a parameter with its incoming copies, and a redirected
* use defeats that — so the parameter and the arguments go too.)
*/
function removeTrivialParams(body: IrBody, scratch: IrScratch): i32 {
let nb = body.blocks.length;
let incoming = new Array<GrowableArray<i32>>(nb);
for (var i = 0; i < nb; i += 1) {
incoming.push(new Array<i32>());
}
for (let blk in body.blocks) {
if (blk.insts.length == 0) {
continue;
}
let term = blk.insts[blk.insts.length - 1];
let n = body.successorCount(term);
for (var k = 0; k < n; k += 1) {
// Once per terminator: a branch whose edges both reach the same
// block would otherwise have the argument dropped twice.
let list = incoming[body.extra[body.successorRecord(term, k)]];
if (list.length == 0 || list[list.length - 1] != term) {
list.push(term);
}
}
}
let count = body.instCount();
let repl = scratch.i32();
for (var i = 0; i < count; i += 1) {
repl.push(i);
}
let canon = (v: i32) => {
var c = v;
while (c >= 0 && c < count && repl[c] != c) {
c = repl[c];
}
return c;
};
var removed = 0;
// Block 0 holds the function's parameters, which have no incoming
// edges; every other block's parameters are candidates. Higher
// indices first, so removing one leaves the lower indices intact.
for (var b = 1; b < nb; b += 1) {
let edges = incoming[b];
if (edges.length == 0) {
continue;
}
let params = body.blocks[b].params;
var j = params.length - 1;
while (j >= 0) {
let p = params[j];
var value = -1;
var trivial = true;
for (let term in edges) {
let n = body.successorCount(term);
for (var k = 0; k < n; k += 1) {
let rec = body.successorRecord(term, k);
if (body.extra[rec] != b) {
continue;
}
let arg = canon(body.extra[rec + 2 + j]);
if (arg == p) {
continue;
}
if (value < 0) {
value = arg;
} else if (arg != value) {
trivial = false;
}
}
}
if (trivial && value >= 0) {
let from = body.resultType(value);
let to = body.resultType(p);
if (from != null && to != null && isValSubtype(from, to)) {
repl[p] = value;
nopOut(body, p);
dropParamAt(body.blocks[b], j);
for (let term in edges) {
dropBranchArg(body, term, b, j);
}
removed += 1;
}
}
j -= 1;
}
}
if (removed > 0) {
for (var i = 0; i < count; i += 1) {
if (body.op(i) != IrOp.nop) {
body.rewriteValueOperands(i, canon);
}
}
}
return removed;
}
export function dropParamAt(blk: IrBlock, j: i32): void {
let kept = new Array<i32>();
for (var k = 0; k < blk.params.length; k += 1) {
if (k != j) {
kept.push(blk.params[k]);
}
}
while (blk.params.length > 0) {
blk.params.pop();
}
for (let p in kept) {
blk.params.push(p);
}
}
/**
* Rebuilds a terminator's successor records without argument `j` of
* every successor targeting `target`. Records live inline in `extra`,
* so the rebuilt record is appended and the terminator repointed.
* Every branch shape is [prefix] ([target, argc, args…])*: no prefix
* for br/br_if/try_br, the target type for br_on_cast, the count for
* br_table (see the encoding table in ir.zena).
*/
export function dropBranchArg(body: IrBody, term: i32, target: i32, j: i32): void {
let op = body.op(term);
let prefixLen = if (op == IrOp.br_on_cast || op == IrOp.br_on_cast_fail ||
op == IrOp.br_table) {
1
} else {
0
};
let recordStart = if (op == IrOp.br) body.a[term] else body.b[term];
let sN = body.successorCount(term);
let idx = body.extra.length;
var p = 0;
while (p < prefixLen) {
body.extra.push(body.extra[recordStart + p]);
p += 1;
}
for (var sK = 0; sK < sN; sK += 1) {
let sRec = body.successorRecord(term, sK);
body.extra.push(body.extra[sRec]);
let drop = body.extra[sRec] == target;
body.extra.push(if (drop) body.extra[sRec + 1] - 1 else body.extra[sRec + 1]);
var i = 0;
while (i < body.extra[sRec + 1]) {
if (!(drop && i == j)) {
body.extra.push(body.extra[(sRec + 2) + i]);
}
i += 1;
}
}
if (op == IrOp.br) {
body.a[term] = idx;
} else {
body.b[term] = idx;
}
}
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;
}
- 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 |
|
|