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