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
10.5 KiB
Raw
/**
* Scalar replacement of aggregates, mutable tier (docs/design/
* optimization-pipeline.md §Escape analysis and SROA): an allocation
* that never leaves the function — every use is a field read or a
* field write through it — is deleted, and each of its fields becomes
* an SSA value. Reads become the value written last on the path
* reaching them, and where paths meet, a block parameter carries it.
*
* The immutable tier lives in simplify: a read of an immutable field
* straight off the allocation is the allocation's operand, no control
* flow involved. This pass is what handles a field that is written,
* which is the iterator object's index: after `iterator()` and
* `next()` have inlined into the loop, the object is allocated once
* per loop, read three times and written once per iteration, and
* escapes nowhere. Here it dissolves into a loop-carried parameter.
*
* The construction is the plain one. Every block the allocation's
* block strictly dominates gets one parameter per field, every
* branch into such a block passes the field's current value, and a
* forward walk over each block in instruction order replaces reads
* and deletes writes. Uses of the allocation can only sit in blocks
* it dominates, and every predecessor of such a block is itself
* dominated or is the allocation's block, so every parameter gets an
* argument on every edge. Most of the parameters are then trivial —
* every edge passes the same value — and the block cleanup pass
* deletes them (it runs first in the cleanup sequence), leaving the
* parameters that carry a value around a loop or across a join.
*
* Determinism: candidates in id order, blocks in id order, no hash
* containers.
*/
import { IrBody, IrOp, IrRefField, IrUseLists, buildUseLists, IrScratch } from './ir.zena';
import { IrCfg } from './cfg.zena';
import { WasmStruct } from '../wasm-module.zena';
import { allocatedStruct } from './simplify.zena';
import { growable } from 'zena:core';
/** Runs the pass; returns the number of allocations replaced. */
export function runSroa(body: IrBody, scratch: IrScratch): i32 {
scratch.enter();
let result = runSroaOn(body, scratch);
scratch.exit();
return result;
}
function runSroaOn(body: IrBody, scratch: IrScratch): i32 {
let count = body.instCount();
let nb = body.blocks.length;
if (nb == 0) {
return 0;
}
// Users of every value, for the escape test.
let users = buildUseLists(body, scratch);
// Candidates: a struct_new whose every use is a field read or a
// field write with it as the receiver (a write storing it somewhere
// is a use as a value, and disqualifies).
let candidates = scratch.i32();
for (var i = 0; i < count; i += 1) {
if (body.op(i) != IrOp.struct_new) {
continue;
}
let s = allocatedStruct(body, i);
if (s == null) {
continue;
}
let argc = body.extra[body.a[i]];
if (argc != s.fields.length) {
continue;
}
var local = true;
for (var k = 0; k < users.count(i); k += 1) {
let u = users.at(i, k);
let op = body.op(u);
if (op == IrOp.struct_get && body.a[u] == i) {
continue;
}
if (op == IrOp.struct_set && body.extra[body.a[u]] == i &&
body.extra[body.a[u] + 1] != i) {
continue;
}
local = false;
break;
}
if (local) {
candidates.push(i);
}
}
if (candidates.length == 0) {
return 0;
}
let cfg = new IrCfg(body, scratch);
// The first block of every try body. Emission places the blocks it
// dominates inside the try_table, so they are the protected region.
let tryBodies = scratch.i32();
for (var i = 0; i < count; i += 1) {
if (body.op(i) == IrOp.try_br) {
tryBodies.push(body.extra[body.successorRecord(i, 0)]);
}
}
let repl = scratch.i32();
for (var i = 0; i < count; i += 1) {
repl.push(i);
}
var replaced = 0;
for (let alloc in candidates) {
let home = body.instBlock[alloc];
if (home < 0 || !cfg.isReachable(home)) {
continue;
}
if (writtenInsideTryFromOutside(body, cfg, users, alloc, home, tryBodies)) {
continue;
}
let s = allocatedStruct(body, alloc);
if (s == null) {
continue;
}
let nf = s.fields.length;
let argsIdx = body.a[alloc];
// The blocks strictly dominated by the allocation's block, and one
// parameter per field on each.
let dominated = new Array<boolean>(nb);
for (var b = 0; b < nb; b += 1) {
dominated.push(false);
}
let stack = new Array<i32>();
for (var cK = 0; cK < cfg.domChildCount(home); cK += 1) {
let c = cfg.domChild(home, cK);
stack.push(c);
}
let order = new Array<i32>();
while (stack.length > 0) {
let b = stack.pop();
dominated[b] = true;
order.push(b);
for (var cK = 0; cK < cfg.domChildCount(b); cK += 1) {
let c = cfg.domChild(b, cK);
stack.push(c);
}
}
let paramOf = new Array<i32>();
for (var k = 0; k < nb * nf; k += 1) {
paramOf.push(-1);
}
for (let b in order) {
for (var f = 0; f < nf; f += 1) {
body.typeTable.push(s.fields[f].type);
let id = body.opcode.length;
body.opcode.push(IrOp.param as i32);
body.typeId.push(body.typeTable.length - 1);
body.a.push(-1);
body.b.push(-1);
body.instBlock.push(b);
body.blocks[b].params.push(id);
paramOf[b * nf + f] = id;
}
}
// Forward walk: the allocation's block starts undefined (nothing
// reads before the allocation), every dominated block starts at
// its parameters.
let cur = new Array<i32>(nf);
for (var f = 0; f < nf; f += 1) {
cur.push(-1);
}
let walk = growable<i32>([home]);
for (let b in order) {
walk.push(b);
}
for (let b in walk) {
for (var f = 0; f < nf; f += 1) {
cur[f] = if (b == home) -1 else paramOf[b * nf + f];
}
let insts = body.blocks[b].insts;
for (let inst in insts) {
if (inst == alloc) {
for (var f = 0; f < nf; f += 1) {
cur[f] = body.extra[argsIdx + 1 + f];
}
continue;
}
let op = body.op(inst);
if (op == IrOp.struct_get && body.a[inst] == alloc) {
let f = fieldIndex(body, s, body.b[inst]);
if (f < 0 || cur[f] < 0) {
throw new Error('sroa: field read before the allocation');
}
repl[inst] = cur[f];
nopOut(body, inst);
continue;
}
if (op == IrOp.struct_set && body.extra[body.a[inst]] == alloc) {
let f = fieldIndex(body, s, body.b[inst]);
if (f < 0) {
throw new Error('sroa: write to an unknown field');
}
cur[f] = body.extra[body.a[inst] + 1];
nopOut(body, inst);
continue;
}
}
// The terminator passes the current values to every dominated
// successor.
let term = insts[insts.length - 1];
var anyDominated = false;
let succN = body.successorCount(term);
for (var succK = 0; succK < succN; succK += 1) {
let succRec = body.successorRecord(term, succK);
if (dominated[body.extra[succRec]]) {
anyDominated = true;
}
}
if (anyDominated) {
for (var f = 0; f < nf; f += 1) {
if (cur[f] < 0) {
throw new Error('sroa: field value undefined at a branch');
}
}
appendBranchArgs(body, term, dominated, cur);
}
}
nopOut(body, alloc);
replaced += 1;
}
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 replaced;
}
/**
* Whether a write to `alloc`'s fields sits in a try body that `alloc`'s
* block is outside of. The try's handler edge carries the values at
* try entry, so a field the body wrote before throwing would read in
* the handler, and after it, as the value from before the write. In
* memory the write is there; as an SSA value it is not. An allocation
* made inside the try body is safe: the handler cannot reach it.
*/
function writtenInsideTryFromOutside(body: IrBody, cfg: IrCfg, users: IrUseLists,
alloc: i32, home: i32, tryBodies: GrowableArray<i32>): boolean {
for (var k = 0; k < users.count(alloc); k += 1) {
let u = users.at(alloc, k);
if (body.op(u) != IrOp.struct_set) {
continue;
}
let blk = body.instBlock[u];
for (let t in tryBodies) {
if (cfg.dominates(t, blk) && !cfg.dominates(t, home)) {
return true;
}
}
}
return false;
}
/** The index in `s` of the field a struct_get/struct_set names. */
function fieldIndex(body: IrBody, s: WasmStruct, refIdx: i32): i32 {
let r = body.refTable[refIdx];
if (r is IrRefField) {
return s.fieldIndexByName(r.fieldName);
}
return -1;
}
/**
* Rebuilds a terminator's successor records with `values` appended
* to the arguments of every successor whose target is dominated.
* Records live inline in `extra`, so the rebuilt record is appended
* and the terminator repointed; every branch shape is
* [prefix] ([target, argc, args…])* (see blockmerge's dropBranchArg).
*/
function appendBranchArgs(body: IrBody, term: i32,
dominated: GrowableArray<boolean>, values: 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 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);
let extend = dominated[body.extra[sRec]];
body.extra.push(body.extra[sRec]);
body.extra.push(if (extend) body.extra[sRec + 1] + values.length else body.extra[sRec + 1]);
var i = 0;
while (i < body.extra[sRec + 1]) {
body.extra.push(body.extra[(sRec + 2) + i]);
i += 1;
}
if (extend) {
for (let v in values) {
body.extra.push(v);
}
}
}
if (op == IrOp.br) {
body.a[term] = idx;
} else {
body.b[term] = idx;
}
}
/** A nop stays listed in its block, so it keeps its block id. */
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;
}
- 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 |
|
|