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
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;
}
- 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 |
|
|