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.7 KiB
Raw
/**
* CFG analyses over a ZIR body: predecessors, reverse postorder, and
* dominators (Cooper–Harvey–Kennedy). Shared by the verifier and the
* emitter. Computed once per body on demand; bodies are not mutated
* between construction and use in the current pipeline.
*/
import { IrBody, IrScratch } from './ir.zena';
export final class IrCfg {
body: IrBody;
// The per-block lists are packed, block b's entries being
// list[start[b] .. start[b + 1]): one array per table rather than one
// per block, for a structure built several times per body per pass.
/** Predecessor block ids per block. */
predStart: GrowableArray<i32>;
predList: GrowableArray<i32>;
/** Successor block ids per block (edge order, duplicates preserved). */
succStart: GrowableArray<i32>;
succList: GrowableArray<i32>;
/** Blocks in reverse postorder (entry first). */
rpo: GrowableArray<i32>;
/** Reverse-postorder number per block; -1 = unreachable from entry. */
rpoIndex: GrowableArray<i32>;
/** Immediate dominator per block; entry's is itself; -1 = unreachable. */
idom: GrowableArray<i32>;
/** Dominator-tree children per block, in ascending RPO order. */
domChildStart: GrowableArray<i32>;
domChildList: GrowableArray<i32>;
/** Where the tables came from; null means fresh lists of its own. */
#scratch: IrScratch | null;
predCount(block: i32): i32 {
return this.predStart[block + 1] - this.predStart[block];
}
pred(block: i32, k: i32): i32 {
return this.predList[this.predStart[block] + k];
}
succCount(block: i32): i32 {
return this.succStart[block + 1] - this.succStart[block];
}
succ(block: i32, k: i32): i32 {
return this.succList[this.succStart[block] + k];
}
domChildCount(block: i32): i32 {
return this.domChildStart[block + 1] - this.domChildStart[block];
}
domChild(block: i32, k: i32): i32 {
return this.domChildList[this.domChildStart[block] + k];
}
/**
* With a pool, the tables and the temporaries come from the caller's
* current scope, and the CFG must not outlive it: a pass builds its
* CFG inside its own scope. Without one, the lists are fresh.
*/
new(this.body, scratch: IrScratch | null = null)
: predStart = listFrom(scratch), predList = listFrom(scratch),
succStart = listFrom(scratch), succList = listFrom(scratch),
rpo = listFrom(scratch), rpoIndex = listFrom(scratch),
idom = listFrom(scratch),
domChildStart = listFrom(scratch), domChildList = listFrom(scratch),
#scratch = scratch {
this.#computePreds();
this.#computeRpo();
this.#computeDominators();
this.#computeDomChildren();
}
isReachable(block: i32): boolean {
return this.rpoIndex[block] >= 0;
}
/** True if `block` has a predecessor that appears later in RPO. */
isLoopHeader(block: i32): boolean {
for (var pK = 0; pK < this.predCount(block); pK += 1) {
let p = this.pred(block, pK);
if (this.rpoIndex[p] >= this.rpoIndex[block]) {
return true;
}
}
return false;
}
/** True if `block` has two or more forward-edge predecessors. */
isMergeNode(block: i32): boolean {
var forward = 0;
for (var pK = 0; pK < this.predCount(block); pK += 1) {
let p = this.pred(block, pK);
if (this.rpoIndex[p] < this.rpoIndex[block]) {
forward += 1;
}
}
return forward >= 2;
}
dominates(a: i32, b: i32): boolean {
var blockId = b;
while (true) {
if (blockId == a) {
return true;
}
if (blockId == 0) {
return false;
}
blockId = this.idom[blockId];
if (blockId < 0) {
return false;
}
}
}
#computePreds(): void {
let {body} = this;
let nb = body.blocks.length;
// Count each block's edges in and out, prefix-sum into the start
// tables, then place.
for (var b = 0; b <= nb; b += 1) {
this.predStart.push(0);
this.succStart.push(0);
}
var total = 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) {
let target = body.extra[body.successorRecord(term, k)];
if (target >= 0 && target < nb) {
this.predStart[target + 1] = this.predStart[target + 1] + 1;
this.succStart[b + 1] = this.succStart[b + 1] + 1;
total += 1;
}
}
}
for (var b = 0; b < nb; b += 1) {
this.predStart[b + 1] = this.predStart[b + 1] + this.predStart[b];
this.succStart[b + 1] = this.succStart[b + 1] + this.succStart[b];
}
let predNext = listFrom(this.#scratch);
let succNext = listFrom(this.#scratch);
for (var b = 0; b < nb; b += 1) {
predNext.push(this.predStart[b]);
succNext.push(this.succStart[b]);
}
for (var i = 0; i < total; i += 1) {
this.predList.push(0);
this.succList.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) {
let target = body.extra[body.successorRecord(term, k)];
if (target >= 0 && target < nb) {
this.predList[predNext[target]] = b;
predNext[target] = predNext[target] + 1;
this.succList[succNext[b]] = target;
succNext[b] = succNext[b] + 1;
}
}
}
}
#computeRpo(): void {
let {body} = this;
var i = 0;
while (i < body.blocks.length) {
this.rpoIndex.push(-1);
i += 1;
}
if (body.blocks.length == 0) {
return;
}
// Iterative DFS postorder from the entry, then reverse. A node must
// finish only after all its (non-cyclic) successors have finished, so
// each stack entry keeps a cursor into its successor list — the
// simpler push-all-successors form finishes nodes too early and
// produces orderings where a forward edge looks like a back edge.
let postorder = listFrom(this.#scratch);
let stack = listFrom(this.#scratch);
let cursor = listFrom(this.#scratch);
let visited = boolsFrom(this.#scratch);
i = 0;
while (i < body.blocks.length) {
visited.push(false);
i += 1;
}
stack.push(0);
cursor.push(0);
visited[0] = true;
while (stack.length > 0) {
let blockId = stack[stack.length - 1];
let next = cursor[cursor.length - 1];
if (next < this.succCount(blockId)) {
cursor[cursor.length - 1] = next + 1;
let target = this.succ(blockId, next);
if (!visited[target]) {
visited[target] = true;
stack.push(target);
cursor.push(0);
}
continue;
}
stack.pop();
cursor.pop();
postorder.push(blockId);
}
i = postorder.length - 1;
while (i >= 0) {
this.rpoIndex[postorder[i]] = this.rpo.length;
this.rpo.push(postorder[i]);
i -= 1;
}
}
/** Cooper–Harvey–Kennedy iterative dominator computation over RPO. */
#computeDominators(): void {
var i = 0;
while (i < this.body.blocks.length) {
this.idom.push(-1);
i += 1;
}
if (this.body.blocks.length == 0) {
return;
}
this.idom[0] = 0;
var changed = true;
while (changed) {
changed = false;
var r = 1;
while (r < this.rpo.length) {
let blockId = this.rpo[r];
var newIdom = -1;
for (var predK = 0; predK < this.predCount(blockId); predK += 1) {
let pred = this.pred(blockId, predK);
if (this.rpoIndex[pred] < 0 || this.idom[pred] < 0) {
continue; // unreachable or not yet processed
}
if (newIdom < 0) {
newIdom = pred;
} else {
newIdom = this.#intersect(pred, newIdom);
}
}
if (newIdom >= 0 && this.idom[blockId] != newIdom) {
this.idom[blockId] = newIdom;
changed = true;
}
r += 1;
}
}
}
#intersect(x: i32, y: i32): i32 {
var a = x;
var b = y;
while (a != b) {
while (this.rpoIndex[a] > this.rpoIndex[b]) {
a = this.idom[a];
}
while (this.rpoIndex[b] > this.rpoIndex[a]) {
b = this.idom[b];
}
}
return a;
}
#computeDomChildren(): void {
let nb = this.body.blocks.length;
for (var b = 0; b <= nb; b += 1) {
this.domChildStart.push(0);
}
var r = 1;
while (r < this.rpo.length) {
let blockId = this.rpo[r];
let parent = this.idom[blockId];
if (parent >= 0 && parent != blockId) {
this.domChildStart[parent + 1] = this.domChildStart[parent + 1] + 1;
}
r += 1;
}
for (var b = 0; b < nb; b += 1) {
this.domChildStart[b + 1] = this.domChildStart[b + 1] + this.domChildStart[b];
}
let next = listFrom(this.#scratch);
for (var b = 0; b < nb; b += 1) {
next.push(this.domChildStart[b]);
}
let total = this.domChildStart[nb];
for (var i = 0; i < total; i += 1) {
this.domChildList.push(0);
}
// Walk in RPO so children lists come out in ascending RPO order.
r = 1;
while (r < this.rpo.length) {
let blockId = this.rpo[r];
let parent = this.idom[blockId];
if (parent >= 0 && parent != blockId) {
this.domChildList[next[parent]] = blockId;
next[parent] = next[parent] + 1;
}
r += 1;
}
}
}
function listFrom(scratch: IrScratch | null): GrowableArray<i32> {
return if (scratch != null) scratch.i32() else new Array<i32>();
}
function boolsFrom(scratch: IrScratch | null): GrowableArray<boolean> {
return if (scratch != null) scratch.bool() else new Array<boolean>();
}
- 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 |
|
|