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
37.7 KiB
Raw
/**
* Interprocedural type propagation (#421): for every reference value in
* the module's bodies, the set of things that can reach it, and from
* that, which `call_ref` sites can only ever call one function.
*
* The graph has a node per instruction of every body, per field (keyed
* by the struct that declares it and its name, so every subclass's
* struct shares its superclass's fields), per array element type (each
* flowing into its declared supertype's, since an immutable array is
* read through its supertype with no cast in between), per global, per
* function result and per mutable variable. Edges follow
* every flow ZIR names: branch arguments into block parameters, call
* arguments into the callee's entry parameters and its results back,
* stores into fields, arrays, globals and variables and loads out of
* them, casts. Sets hold **atoms**: a struct type allocated by
* `struct_new` (a class instance, a closure pair, a context), a global
* (a class vtable, a class-interface vtable), and a function named by
* `ref_func`.
*
* Three loads resolve through the atoms of their receiver rather than
* through a field node, which is where the precision comes from:
* `<vtable>` of an object is its class's vtable global, a slot of a
* vtable global is the function it installs, and a fat pointer's
* vtable and instance are the pair global and the instance it was
* packed from. A `call_ref` whose callee reaches a function atom adds
* that function's argument and result edges, so the call graph and the
* sets reach a fixpoint together.
*
* Only the bodies something reaches are in the graph: the exports and
* the start function, and then every function a reached body calls,
* a reached `call_ref` resolves to, or the host can be handed. A
* function a vtable installs is not reached until some dispatch loads
* it.
*
* Anything that comes from outside the program is **top**: an exported
* function's parameters, an import's results, `any_convert_extern`, an
* imported global, and the parameters of a function whose reference
* reaches an import. So is anything an unmodelled instruction produces.
* A site resolves only when its callee's set is one function and not
* top.
*
* `propagationReport` measures; `runPropagationDevirt` makes the
* resolved sites direct, at -O2 when `ModuleGenerator.propagate` is on.
* docs/design/type-propagation.md has the numbers. Determinism: bodies,
* instructions and atoms in module order, the node worklist first in
* first out, reached bodies built last in first out.
*/
import { i32ToString, growable } from 'zena:core';
import { HashMap, HashSet } from 'zena:collections';
import {
IrBody, IrOp, IrRef, IrRefFunc, IrRefGlobal, IrRefType, IrRefField,
} from './ir.zena';
import {
WasmModule, WasmFunction, WasmGlobal, WasmStruct, WasmArray, VTableInit,
} from '../wasm-module.zena';
import { ValType, isRefValType, refTargetOf } from '../wasm.zena';
import { getClassKey } from '../codegen-utils.zena';
import { CallKinds } from './census.zena';
import { rewriteToCall } from './devirt.zena';
/** What an atom stands for. */
enum AtomKind {
Struct,
Global,
Function,
}
/** The flow graph and its sets. */
final class Graph {
/** Per node: its atoms, sorted, or null when empty. */
sets = new GrowableArray<GrowableArray<i32> | null>();
/** Per node: reached by something from outside the program. */
top = new GrowableArray<boolean>();
/** Per node: the nodes it flows into. */
succ = new GrowableArray<GrowableArray<i32> | null>();
/** Per node: the constraints that read it. */
watchers = new GrowableArray<GrowableArray<i32> | null>();
queue = new GrowableArray<i32>();
var head: i32 = 0;
queued = new GrowableArray<boolean>();
newNode(): i32 {
this.sets.push(null);
this.top.push(false);
this.succ.push(null);
this.watchers.push(null);
this.queued.push(false);
return this.sets.length - 1;
}
#enqueue(n: i32): void {
if (!this.queued[n]) {
this.queued[n] = true;
this.queue.push(n);
}
}
edge(from: i32, to: i32): void {
var list = this.succ[from];
if (list == null) {
let fresh = new GrowableArray<i32>();
this.succ[from] = fresh;
list = fresh;
}
let l = list as GrowableArray<i32>;
for (let s in l) {
if (s == to) {
return;
}
}
l.push(to);
// What has already reached `from` reaches `to` too.
if (this.top[from] || this.sets[from] != null) {
this.#enqueue(from);
}
}
watch(n: i32, constraint: i32): void {
var list = this.watchers[n];
if (list == null) {
let fresh = new GrowableArray<i32>();
this.watchers[n] = fresh;
list = fresh;
}
(list as GrowableArray<i32>).push(constraint);
if (this.top[n] || this.sets[n] != null) {
this.#enqueue(n);
}
}
/** Adds `atom` to `n`; true when it was new. */
add(n: i32, atom: i32): boolean {
var set = this.sets[n];
if (set == null) {
let fresh = new GrowableArray<i32>();
this.sets[n] = fresh;
set = fresh;
}
let s = set as GrowableArray<i32>;
var lo = 0;
var hi = s.length;
while (lo < hi) {
let mid = (lo + hi) >> 1;
if (s[mid] < atom) {
lo = mid + 1;
} else {
hi = mid;
}
}
if (lo < s.length && s[lo] == atom) {
return false;
}
s.push(0);
var i = s.length - 1;
while (i > lo) {
s[i] = s[i - 1];
i -= 1;
}
s[lo] = atom;
this.#enqueue(n);
return true;
}
setTop(n: i32): void {
if (!this.top[n]) {
this.top[n] = true;
this.#enqueue(n);
}
}
}
/** A field's node and the struct that declares the field. */
final class FieldNode {
node: i32;
owner: WasmStruct;
name: String;
new(this.node, this.owner, this.name);
}
/** An array type's element node. */
final class ArrayNode {
node: i32;
array: WasmArray;
new(this.node, this.array);
}
/** A load or call whose result depends on the atoms reaching one node. */
final class Constraint {
/** 0 `<vtable>` load, 1 vtable slot load, 2 fat pointer vtable, 3 fat pointer instance, 4 call_ref. */
kind: i32;
dst: i32;
/** For a slot load: the slot's field name. */
name: String;
/** For a call_ref: its body and instruction. */
body: i32;
inst: i32;
/** Atoms this constraint has handled already. */
done = new GrowableArray<i32>();
var sawTop: boolean = false;
new(this.kind, this.dst, this.name, this.body, this.inst);
}
/** The analysis over one module's bodies. */
final class Propagation {
wasm: WasmModule;
bodies: GrowableArray<IrBody>;
g = new Graph();
/** Per body: the node id of its instruction 0. */
base = new GrowableArray<i32>();
/** Per function: its result nodes. */
results = new GrowableArray<GrowableArray<i32>>();
#fieldNodes = new HashMap<String, i32>();
#arrayNodes = new HashMap<i32, i32>();
#globalNodes = new HashMap<String, i32>();
#varNodes = new HashMap<String, i32>();
constraints = new GrowableArray<Constraint>();
// Atoms: kind and object, by id.
atomKind = new GrowableArray<AtomKind>();
atomStruct = new GrowableArray<WasmStruct | null>();
atomGlobal = new GrowableArray<WasmGlobal | null>();
atomFunc = new GrowableArray<WasmFunction | null>();
#structAtoms = new HashMap<i32, i32>();
#globalAtoms = new HashMap<String, i32>();
#funcAtoms = new HashMap<i32, i32>();
/** WasmFunction uid → index in wasm.functions. */
#funcIndex = new HashMap<i32, i32>();
/** Class struct uid → its class vtable global. */
#vtableOf = new HashMap<i32, WasmGlobal>();
/** Uids of the class and interface vtable structs. */
#vtableStructs = new HashSet<i32>();
/** The node values reach when they leave for the host. */
var hostNode: i32 = -1;
/** Per body: whether something reaches it, and so whether its instructions are in the graph. */
reached = new GrowableArray<boolean>();
/** Bodies reached but not built yet. */
#pending = new GrowableArray<i32>();
new(this.wasm, this.bodies) {
for (var i = 0; i < this.wasm.functions.length; i += 1) {
this.#funcIndex[this.wasm.functions[i].uid] = i;
}
for (let entry in this.wasm.classInfos) {
let vg = entry.value.vtableGlobal;
if (vg != null) {
this.#vtableOf[entry.value.structType.uid] = vg;
}
let vst = entry.value.vtableStructType;
if (vst != null) {
this.#vtableStructs.add(vst.uid);
}
}
for (let entry in this.wasm.interfaceVTableStructs) {
this.#vtableStructs.add(entry.value.uid);
}
}
structAtom(s: WasmStruct): i32 {
if (let (true, a) = this.#structAtoms.get(s.uid)) {
return a;
}
let a = this.#newAtom(AtomKind.Struct);
this.atomStruct[a] = s;
this.#structAtoms[s.uid] = a;
return a;
}
globalAtom(gl: WasmGlobal): i32 {
if (let (true, a) = this.#globalAtoms.get(gl.name)) {
return a;
}
let a = this.#newAtom(AtomKind.Global);
this.atomGlobal[a] = gl;
this.#globalAtoms[gl.name] = a;
return a;
}
funcAtom(f: WasmFunction): i32 {
if (let (true, a) = this.#funcAtoms.get(f.uid)) {
return a;
}
let a = this.#newAtom(AtomKind.Function);
this.atomFunc[a] = f;
this.#funcAtoms[f.uid] = a;
return a;
}
#newAtom(kind: AtomKind): i32 {
this.atomKind.push(kind);
this.atomStruct.push(null);
this.atomGlobal.push(null);
this.atomFunc.push(null);
return this.atomKind.length - 1;
}
value(b: i32, inst: i32): i32 {
return this.base[b] + inst;
}
/** The struct that declares field `name` of `owner`: the topmost one in its chain that has it. */
declaring(owner: WasmStruct, name: String): WasmStruct {
var top = owner;
var cur = owner.superStruct;
while (cur != null) {
let c = cur as WasmStruct;
if (c.fieldIndexByName(name) >= 0) {
top = c;
}
cur = c.superStruct;
}
return top;
}
fieldNode(owner: WasmStruct, name: String): i32 {
let decl = this.declaring(owner, name);
let key = `${i32ToString(decl.uid)}:${name}`;
if (let (true, n) = this.#fieldNodes.get(key)) {
return n;
}
let n = this.g.newNode();
this.#fieldNodes[key] = n;
this.fieldList.push(new FieldNode(n, decl, name));
return n;
}
/** Every field node, with the struct that declares it. */
fieldList = new GrowableArray<FieldNode>();
/** Every array element node, with its array type. */
arrayList = new GrowableArray<ArrayNode>();
arrayNode(arr: WasmArray): i32 {
if (let (true, n) = this.#arrayNodes.get(arr.uid)) {
return n;
}
let n = this.g.newNode();
this.#arrayNodes[arr.uid] = n;
this.arrayList.push(new ArrayNode(n, arr));
// An immutable array is a subtype of its element's supertype's
// array with no instruction between them, so a read through the
// supertype sees this array's elements.
let sup = arr.superArray;
if (sup != null) {
this.g.edge(n, this.arrayNode(sup as WasmArray));
}
return n;
}
globalNode(gl: WasmGlobal): i32 {
if (let (true, n) = this.#globalNodes.get(gl.name)) {
return n;
}
let n = this.g.newNode();
this.#globalNodes[gl.name] = n;
if (gl.isImport) {
this.g.setTop(n);
}
return n;
}
varNode(b: i32, v: i32): i32 {
let key = `${i32ToString(b)}:${i32ToString(v)}`;
if (let (true, n) = this.#varNodes.get(key)) {
return n;
}
let n = this.g.newNode();
this.#varNodes[key] = n;
return n;
}
#constrain(src: i32, c: Constraint): void {
this.constraints.push(c);
this.g.watch(src, this.constraints.length - 1);
}
#isRef(body: IrBody, inst: i32): boolean {
let t = body.resultType(inst);
return t != null && isRefValType(t as ValType);
}
/** The function a call instruction names, or null. */
#callee(body: IrBody, inst: i32): WasmFunction | null {
let r = body.refTable[body.b[inst]];
if (r is IrRefFunc) {
return r.target;
}
return null;
}
/** Index of `f` in wasm.functions (and so in `bodies`), or -1. */
funcIndex(f: WasmFunction): i32 {
if (let (true, i) = this.#funcIndex.get(f.uid)) {
return i;
}
return -1;
}
/** Wires a call to `f` with arguments at extra[argsAt .. argsAt + argc) and results into `out`. */
#wireCall(b: i32, f: WasmFunction, argsAt: i32, argc: i32, out: GrowableArray<i32>): void {
let body = this.bodies[b];
let fi = this.funcIndex(f);
if (f.isImport || fi < 0 || this.bodies[fi].blocks.length == 0) {
// The host: arguments leave, results come back as anything.
for (var k = 0; k < argc; k += 1) {
let arg = body.extra[argsAt + k];
if (arg >= 0 && this.#isRef(body, arg)) {
this.g.edge(this.value(b, arg), this.hostNode);
}
}
for (let r in out) {
this.g.setTop(r);
}
return;
}
let params = this.bodies[fi].blocks[0].params;
for (var k = 0; k < argc && k < params.length; k += 1) {
let arg = body.extra[argsAt + k];
if (arg >= 0 && this.#isRef(body, arg)) {
this.g.edge(this.value(b, arg), this.value(fi, params[k]));
}
}
let res = this.results[fi];
for (var k = 0; k < out.length && k < res.length; k += 1) {
this.g.edge(res[k], out[k]);
}
this.#reach(fi);
}
/** Marks body `fi` reached; its instructions join the graph before the next node is solved. */
#reach(fi: i32): void {
if (fi < 0 || this.reached[fi]) {
return;
}
this.reached[fi] = true;
this.#pending.push(fi);
}
/** Builds the bodies reached since the last call. */
#buildPending(): void {
while (this.#pending.length > 0) {
this.#buildBody(this.#pending.pop());
}
}
/** The nodes a call's results land in: the call itself, or its `mv_get` projections. */
#resultNodes(b: i32, inst: i32): GrowableArray<i32> {
let body = this.bodies[b];
let out = new GrowableArray<i32>();
if (body.producesValue(inst)) {
out.push(this.value(b, inst));
return out;
}
// Projections follow the call immediately, in result order.
var j = inst + 1;
while (j < body.instCount() && body.op(j) == IrOp.mv_get && body.a[j] == inst) {
out.push(this.value(b, j));
j += 1;
}
return out;
}
build(roots: GrowableArray<WasmFunction>): void {
var total = 0;
for (let body in this.bodies) {
this.base.push(total);
total += body.instCount();
}
for (var i = 0; i < total; i += 1) {
this.g.newNode();
}
this.hostNode = this.g.newNode();
for (var f = 0; f < this.bodies.length; f += 1) {
let row = new GrowableArray<i32>();
for (let _r in this.wasm.functions[f].signature.returns) {
row.push(this.g.newNode());
}
this.results.push(row);
}
for (var b = 0; b < this.bodies.length; b += 1) {
this.reached.push(false);
}
// Exported functions are called by the host with anything.
for (let root in roots) {
this.#callFromHost(this.funcIndex(root));
}
let start = this.wasm.startFunction;
if (start != null) {
this.#reach(this.funcIndex(start));
}
// The host can read an exported global.
for (let key in this.wasm.exportGlobalMap.keys()) {
this.g.edge(this.globalNode(this.wasm.exportGlobalMap[key]), this.hostNode);
}
this.#buildPending();
}
/** Body `fi` is called by the host, with anything. */
#callFromHost(fi: i32): void {
if (fi < 0 || this.bodies[fi].blocks.length == 0) {
return;
}
for (let p in this.bodies[fi].blocks[0].params) {
this.g.setTop(this.value(fi, p));
}
this.#reach(fi);
}
#buildBody(b: i32): void {
let body = this.bodies[b];
for (var blk = 0; blk < body.blocks.length; blk += 1) {
for (let inst in body.blocks[blk].insts) {
this.#buildInst(b, inst);
}
}
}
#buildInst(b: i32, inst: i32): void {
let body = this.bodies[b];
let op = body.op(inst);
let v = this.value(b, inst);
let a = body.a[inst];
if (op == IrOp.struct_new || op == IrOp.struct_new_default) {
let r = body.refTable[body.b[inst]];
let rt = if (r is IrRefType) (r as IrRefType).target else null;
if (rt != null && rt is WasmStruct) {
let st = rt as WasmStruct;
this.g.add(v, this.structAtom(st));
if (op == IrOp.struct_new) {
let argc = body.extra[a];
for (var k = 0; k < argc && k < st.fields.length; k += 1) {
let arg = body.extra[a + 1 + k];
let fname = st.fields[k].name;
if (arg >= 0 && fname != null && this.#isRef(body, arg)) {
this.g.edge(this.value(b, arg), this.fieldNode(st, fname as String));
}
}
}
} else {
this.g.setTop(v);
}
return;
}
if (op == IrOp.struct_get) {
if (!this.#isRef(body, inst)) {
return;
}
let r = body.refTable[body.b[inst]];
if (!(r is IrRefField)) {
this.g.setTop(v);
return;
}
let f = r as IrRefField;
if (f.fieldName == '<vtable>') {
this.#constrain(this.value(b, a), new Constraint(0, v, '', b, inst));
} else if (this.#isVTableStruct(f.owner)) {
this.#constrain(this.value(b, a), new Constraint(1, v, f.fieldName, b, inst));
} else {
this.g.edge(this.fieldNode(f.owner, f.fieldName), v);
}
return;
}
if (op == IrOp.struct_set) {
let value = body.extra[a + 1];
let r = body.refTable[body.b[inst]];
if (r is IrRefField && value >= 0 && this.#isRef(body, value)) {
let f = r as IrRefField;
this.g.edge(this.value(b, value), this.fieldNode(f.owner, f.fieldName));
}
return;
}
if (op == IrOp.array_new || op == IrOp.array_new_fixed) {
let r = body.refTable[body.b[inst]];
let rt = if (r is IrRefType) (r as IrRefType).target else null;
if (rt != null && rt is WasmArray) {
let arr = rt as WasmArray;
let n = this.arrayNode(arr);
if (op == IrOp.array_new) {
let init = body.extra[a + 1];
if (init >= 0 && this.#isRef(body, init)) {
this.g.edge(this.value(b, init), n);
}
} else {
let argc = body.extra[a];
for (var k = 0; k < argc; k += 1) {
let arg = body.extra[a + 1 + k];
if (arg >= 0 && this.#isRef(body, arg)) {
this.g.edge(this.value(b, arg), n);
}
}
}
}
return;
}
if (op == IrOp.array_get) {
if (!this.#isRef(body, inst)) {
return;
}
let arr = this.#arrayOf(body, a);
if (arr == null) {
this.g.setTop(v);
return;
}
this.g.edge(this.arrayNode(arr as WasmArray), v);
return;
}
if (op == IrOp.array_set) {
let arrV = body.extra[a];
let value = body.extra[a + 2];
if (value >= 0 && this.#isRef(body, value)) {
let arr = this.#arrayOf(body, arrV);
if (arr == null) {
this.g.edge(this.value(b, value), this.hostNode);
} else {
this.g.edge(this.value(b, value), this.arrayNode(arr as WasmArray));
}
}
return;
}
if (op == IrOp.array_copy) {
let dst = this.#arrayOf(body, body.extra[a]);
let src = this.#arrayOf(body, body.extra[a + 2]);
if (dst != null && src != null) {
this.g.edge(this.arrayNode(src as WasmArray), this.arrayNode(dst as WasmArray));
}
return;
}
if (op == IrOp.global_get) {
if (!this.#isRef(body, inst)) {
return;
}
let r = body.refTable[body.b[inst]];
if (!(r is IrRefGlobal)) {
this.g.setTop(v);
return;
}
let gl = (r as IrRefGlobal).target;
if (gl.initVTable != null) {
this.g.add(v, this.globalAtom(gl));
}
let single = gl.initSingletonStruct;
if (single != null) {
if (let (true, info) = this.wasm.classInfos.get(getClassKey(single))) {
this.g.add(v, this.structAtom(info.structType));
} else {
this.g.setTop(v);
}
}
this.g.edge(this.globalNode(gl), v);
return;
}
if (op == IrOp.global_set) {
let r = body.refTable[body.b[inst]];
if (r is IrRefGlobal && a >= 0 && this.#isRef(body, a)) {
let gl = (r as IrRefGlobal).target;
this.g.edge(this.value(b, a), this.globalNode(gl));
if (gl.isImport) {
this.g.edge(this.value(b, a), this.hostNode);
}
}
return;
}
if (op == IrOp.var_get) {
if (this.#isRef(body, inst)) {
this.g.edge(this.varNode(b, body.b[inst]), v);
}
return;
}
if (op == IrOp.var_set) {
if (a >= 0 && this.#isRef(body, a)) {
this.g.edge(this.value(b, a), this.varNode(b, body.b[inst]));
}
return;
}
if (op == IrOp.ref_func) {
let r = body.refTable[body.b[inst]];
if (r is IrRefFunc) {
this.g.add(v, this.funcAtom((r as IrRefFunc).target));
} else {
this.g.setTop(v);
}
return;
}
if (op == IrOp.str_lit) {
let sc = this.wasm.stringClass;
if (sc != null) {
if (let (true, info) = this.wasm.classInfos.get(getClassKey(sc))) {
this.g.add(v, this.structAtom(info.structType));
return;
}
}
this.g.setTop(v);
return;
}
if (op == IrOp.iface_pack) {
if (a >= 0) {
this.g.edge(this.value(b, a), v);
}
let r = body.refTable[body.b[inst]];
if (r is IrRefGlobal) {
this.g.add(v, this.globalAtom((r as IrRefGlobal).target));
} else {
this.g.setTop(v);
}
return;
}
if (op == IrOp.iface_vtable) {
this.#constrain(this.value(b, a), new Constraint(2, v, '', b, inst));
return;
}
if (op == IrOp.iface_instance) {
this.#constrain(this.value(b, a), new Constraint(3, v, '', b, inst));
return;
}
if (op == IrOp.ref_cast || op == IrOp.ref_as_non_null) {
if (this.#isRef(body, inst)) {
this.g.edge(this.value(b, a), v);
}
return;
}
if (op == IrOp.any_convert_extern) {
this.g.setTop(v);
return;
}
if (op == IrOp.extern_convert_any) {
if (a >= 0) {
this.g.edge(this.value(b, a), this.hostNode);
}
this.g.setTop(v);
return;
}
if (op == IrOp.call || op == IrOp.ret_call) {
let f = this.#callee(body, inst);
let out = if (op == IrOp.call) this.#resultNodes(b, inst) else this.results[b];
if (f == null) {
for (let o in out) {
this.g.setTop(o);
}
return;
}
this.#wireCall(b, f as WasmFunction, a + 1, body.extra[a], out);
return;
}
if (op == IrOp.call_ref || op == IrOp.ret_call_ref) {
let callee = body.extra[a];
this.#constrain(this.value(b, callee), new Constraint(4, v, '', b, inst));
return;
}
if (op == IrOp.ret) {
if (a >= 0 && this.#isRef(body, a) && this.results[b].length > 0) {
this.g.edge(this.value(b, a), this.results[b][0]);
}
return;
}
if (op == IrOp.ret_multi) {
let argc = body.extra[a];
let res = this.results[b];
for (var k = 0; k < argc && k < res.length; k += 1) {
let value = body.extra[a + 1 + k];
if (value >= 0 && this.#isRef(body, value)) {
this.g.edge(this.value(b, value), res[k]);
}
}
return;
}
if (op == IrOp.mv_get || op == IrOp.param) {
// Projections are wired by their call; block parameters by the
// branches into them (below); entry parameters by callers.
return;
}
if (op == IrOp.br || op == IrOp.br_if || op == IrOp.br_table ||
op == IrOp.br_on_cast || op == IrOp.br_on_cast_fail || op == IrOp.try_br) {
let n = body.successorCount(inst);
for (var k = 0; k < n; k += 1) {
let rec = body.successorRecord(inst, k);
let target = body.extra[rec];
let argc = body.extra[rec + 1];
let params = body.blocks[target].params;
for (var i = 0; i < params.length; i += 1) {
let arg = if (i < argc) body.extra[rec + 2 + i] else -1;
if (arg >= 0 && arg < body.instCount() && this.#isRef(body, arg)) {
this.g.edge(this.value(b, arg), this.value(b, params[i]));
} else if (this.#isRef(body, params[i])) {
// Includes a handler parameter a tag's payload fills, which
// no argument names. Zena's own throws carry no payload (it
// travels through the exception global), so this is only
// for a tag that something else throws.
this.g.setTop(this.value(b, params[i]));
}
}
}
return;
}
// Anything else that produces a reference is not modelled.
if (body.producesValue(inst) && this.#isRef(body, inst) &&
op != IrOp.ref_null) {
this.g.setTop(v);
}
}
/** A class or interface vtable struct: what a vtable global's initializer fills. */
#isVTableStruct(s: WasmStruct): boolean {
return this.#vtableStructs.has(s.uid);
}
#arrayOf(body: IrBody, v: i32): WasmArray | null {
if (v < 0) {
return null;
}
let t = body.resultType(v);
if (t == null) {
return null;
}
let target = refTargetOf(t as ValType);
if (target is WasmArray) {
return target as WasmArray;
}
return null;
}
/** Runs the worklist to a fixpoint. */
solve(): void {
let g = this.g;
while (true) {
this.#buildPending();
if (g.head >= g.queue.length) {
break;
}
let n = g.queue[g.head];
g.head += 1;
g.queued[n] = false;
let set = g.sets[n];
let isTop = g.top[n];
let succ = g.succ[n];
if (succ != null) {
for (let s in succ as GrowableArray<i32>) {
if (isTop) {
g.setTop(s);
}
if (set != null) {
for (let atom in set as GrowableArray<i32>) {
g.add(s, atom);
}
}
}
}
let watchers = g.watchers[n];
if (watchers != null) {
for (let c in watchers as GrowableArray<i32>) {
this.#apply(this.constraints[c], set, isTop);
}
}
if (n == this.hostNode && set != null) {
// A function whose reference leaves for the host can be called
// from there with anything.
for (let atom in set as GrowableArray<i32>) {
let f = this.atomFunc[atom];
if (f != null) {
this.#callFromHost(this.funcIndex(f as WasmFunction));
}
}
}
}
}
#apply(c: Constraint, set: GrowableArray<i32> | null, isTop: boolean): void {
let g = this.g;
if (isTop && !c.sawTop) {
c.sawTop = true;
if (c.kind == 4) {
for (let r in this.#callResults(c)) {
g.setTop(r);
}
} else {
g.setTop(c.dst);
}
}
if (set == null) {
return;
}
for (let atom in set as GrowableArray<i32>) {
if (c.done.contains(atom)) {
continue;
}
c.done.push(atom);
let kind = this.atomKind[atom];
if (c.kind == 0) {
// `<vtable>` of an object: its class's vtable global.
let st = this.atomStruct[atom];
if (st != null) {
if (let (true, vg) = this.#vtableOf.get((st as WasmStruct).uid)) {
g.add(c.dst, this.globalAtom(vg));
} else {
g.setTop(c.dst);
}
} else {
g.setTop(c.dst);
}
} else if (c.kind == 1) {
// A slot of a vtable global: the function it installs.
let gl = this.atomGlobal[atom];
let initOpt = if (gl != null) (gl as WasmGlobal).initVTable else null;
if (initOpt == null) {
g.setTop(c.dst);
continue;
}
let init = initOpt as VTableInit;
let slot = init.structType.fieldIndexByName(c.name);
// A `<typeinfo>` field leads the functions in a vtable that
// answers interface type tests (devirt.zena's leadingSlots).
let slotGlobals = init.slotGlobals;
let leading = if (slotGlobals != null) slotGlobals.length else 0;
let fs = slot - leading;
if (fs >= 0 && fs < init.funcs.length) {
g.add(c.dst, this.funcAtom(init.funcs[fs]));
} else {
g.setTop(c.dst);
}
} else if (c.kind == 2) {
if (kind == AtomKind.Global) {
g.add(c.dst, atom);
}
} else if (c.kind == 3) {
if (kind == AtomKind.Struct) {
g.add(c.dst, atom);
}
} else {
let f = this.atomFunc[atom];
if (f == null) {
for (let r in this.#callResults(c)) {
g.setTop(r);
}
continue;
}
let body = this.bodies[c.body];
let at = body.a[c.inst];
this.#wireCall(c.body, f as WasmFunction, at + 2, body.extra[at + 1],
this.#callResults(c));
}
}
}
#callResults(c: Constraint): GrowableArray<i32> {
let body = this.bodies[c.body];
if (body.op(c.inst) == IrOp.ret_call_ref) {
return this.results[c.body];
}
return this.#resultNodes(c.body, c.inst);
}
/**
* How many functions reach the callee of the `call_ref` at `inst` in
* body `b`, or -1 when something from outside the program does.
*/
calleeCount(b: i32, inst: i32): i32 {
let body = this.bodies[b];
let callee = this.value(b, body.extra[body.a[inst]]);
if (this.g.top[callee]) {
return -1;
}
let set = this.g.sets[callee];
var funcs = 0;
if (set != null) {
for (let atom in set as GrowableArray<i32>) {
if (this.atomFunc[atom] != null) {
funcs += 1;
}
}
}
return funcs;
}
/** The one function the callee of the `call_ref` at `inst` can be, or null. */
onlyCallee(b: i32, inst: i32): WasmFunction | null {
if (this.calleeCount(b, inst) != 1) {
return null;
}
let body = this.bodies[b];
let set = this.g.sets[this.value(b, body.extra[body.a[inst]])] as GrowableArray<i32>;
for (let atom in set) {
let f = this.atomFunc[atom];
if (f != null) {
return f;
}
}
return null;
}
}
/**
* Runs the analysis and rewrites every reached `call_ref` whose callee
* can only be one function into a direct call of it, flagging the
* bodies it changes. Returns the number of sites rewritten.
*/
export function runPropagationDevirt(wasm: WasmModule, bodies: GrowableArray<IrBody>,
roots: GrowableArray<WasmFunction>, changed: GrowableArray<boolean>): i32 {
let p = new Propagation(wasm, bodies);
p.build(roots);
p.solve();
var count = 0;
for (var b = 0; b < bodies.length; b += 1) {
if (!p.reached[b]) {
continue;
}
let body = bodies[b];
for (let blk in body.blocks) {
for (let inst in blk.insts) {
if (body.op(inst) != IrOp.call_ref) {
continue;
}
let f = p.onlyCallee(b, inst);
if (f != null && rewriteToCall(body, inst, f as WasmFunction)) {
changed[b] = true;
count += 1;
}
}
}
}
return count;
}
/**
* The analysis's report for `ZENA_ZIR_STATS`, on the module as it is
* about to be emitted: the functions nothing reaches (and how many of
* them a vtable slot some body reads installs); per kind of `call_ref`,
* how many sites reach one function, several, something from outside or
* nothing; and how many interface-typed fields and array elements one
* class reaches.
*/
export function propagationReport(wasm: WasmModule, bodies: GrowableArray<IrBody>,
roots: GrowableArray<WasmFunction>): GrowableArray<String> {
let p = new Propagation(wasm, bodies);
p.build(roots);
p.solve();
let kinds = new CallKinds(wasm);
let tallies = growable<SiteTally>([
new SiteTally('class dispatch'), new SiteTally('interface dispatch'),
new SiteTally('closure'), new SiteTally('other'),
]);
var unreached = 0;
var unreachedInsts = 0;
var unreachedSites = 0;
for (var b = 0; b < bodies.length; b += 1) {
let body = bodies[b];
if (body.blocks.length == 0) {
continue;
}
if (!p.reached[b]) {
unreached += 1;
unreachedInsts += body.instCount();
}
for (let blk in body.blocks) {
for (let inst in blk.insts) {
let op = body.op(inst);
if (op != IrOp.call_ref && op != IrOp.ret_call_ref) {
continue;
}
if (!p.reached[b]) {
unreachedSites += 1;
continue;
}
let tally = tallies[kinds.kindOf(body, inst) as i32];
let funcs = p.calleeCount(b, inst);
if (funcs < 0) {
tally.outside += 1;
} else if (funcs == 0) {
tally.nothing += 1;
} else if (funcs == 1) {
tally.one += 1;
} else {
tally.several += 1;
}
}
}
}
// Interface-typed fields and array elements, by how many
// class-interface pairs reach them: a slot only one pair reaches
// could hold the instance instead of a fat pointer.
let fatPtrs = new HashSet<i32>();
for (let entry in wasm.interfaceStructs) {
fatPtrs.add(entry.value.uid);
}
let pairVTables = new HashSet<i32>();
for (let entry in wasm.interfaceVTableStructs) {
pairVTables.add(entry.value.uid);
}
let fieldPairs = new PairTally('interface-typed fields');
for (let f in p.fieldList) {
let idx = f.owner.fieldIndexByName(f.name);
if (idx >= 0 && isFatPointer(f.owner.fields[idx].type, fatPtrs)) {
fieldPairs.add(p, f.node, pairVTables);
}
}
let elementPairs = new PairTally('interface-typed array elements');
for (let a in p.arrayList) {
if (isFatPointer(a.array.elementType, fatPtrs)) {
elementPairs.add(p, a.node, pairVTables);
}
}
// The functions nothing reaches, split by whether some vtable slot
// that installs them is read anywhere: one that only unread slots
// install would go with the slots, without this analysis.
let vtableStructs = new HashSet<i32>();
for (let u in pairVTables) {
vtableStructs.add(u);
}
for (let entry in wasm.classInfos) {
let vst = entry.value.vtableStructType;
if (vst != null) {
vtableStructs.add(vst.uid);
}
}
let readSlots = new HashSet<String>();
for (var b = 0; b < bodies.length; b += 1) {
if (!p.reached[b]) {
continue;
}
let body = bodies[b];
for (let blk in body.blocks) {
for (let inst in blk.insts) {
if (body.op(inst) != IrOp.struct_get) {
continue;
}
let r = body.refTable[body.b[inst]];
if (r is IrRefField) {
let f = r as IrRefField;
if (vtableStructs.has(f.owner.uid)) {
readSlots.add(`${i32ToString(p.declaring(f.owner, f.fieldName).uid)}:${f.fieldName}`);
}
}
}
}
}
let inReadSlot = new HashSet<i32>();
for (let gl in wasm.globals) {
let init = gl.initVTable;
if (init == null) {
continue;
}
let st = init.structType;
let slotGlobals = init.slotGlobals;
let leading = if (slotGlobals != null) slotGlobals.length else 0;
for (var k = 0; k < init.funcs.length; k += 1) {
let name = st.fields[leading + k].name;
if (name != null &&
readSlots.has(`${i32ToString(p.declaring(st, name as String).uid)}:${name as String}`)) {
inReadSlot.add(init.funcs[k].uid);
}
}
}
var unreachedInReadSlots = 0;
for (var b = 0; b < bodies.length; b += 1) {
if (bodies[b].blocks.length > 0 && !p.reached[b] && inReadSlot.has(wasm.functions[b].uid)) {
unreachedInReadSlots += 1;
}
}
let lines = new GrowableArray<String>();
lines.push(`zir propagation: of the functions nothing reaches, ${i32ToString(unreachedInReadSlots)} ` +
`are installed in a vtable slot some body reads`);
lines.push(`zir propagation: ${i32ToString(unreached)} functions nothing reaches ` +
`(${i32ToString(unreachedInsts)} instructions, ${i32ToString(unreachedSites)} call_ref sites); ` +
`${i32ToString(p.g.sets.length)} nodes, ${i32ToString(p.atomKind.length)} atoms`);
for (let t in tallies) {
lines.push(t.format());
}
lines.push(fieldPairs.format());
lines.push(elementPairs.format());
return lines;
}
function isFatPointer(t: ValType, fatPtrs: HashSet<i32>): boolean {
if (!isRefValType(t)) {
return false;
}
let target = refTargetOf(t);
return target is WasmStruct && fatPtrs.has((target as WasmStruct).uid);
}
/** Interface-typed slots by how many class-interface pairs reach them. */
final class PairTally {
what: String;
var none: i32 = 0;
var one: i32 = 0;
var two: i32 = 0;
var more: i32 = 0;
var outside: i32 = 0;
new(this.what);
add(p: Propagation, node: i32, pairVTables: HashSet<i32>): void {
if (p.g.top[node]) {
this.outside += 1;
return;
}
var pairs = 0;
let set = p.g.sets[node];
if (set != null) {
for (let atom in set as GrowableArray<i32>) {
let gl = p.atomGlobal[atom];
if (gl == null) {
continue;
}
let init = (gl as WasmGlobal).initVTable;
if (init != null && pairVTables.has(init.structType.uid)) {
pairs += 1;
}
}
}
if (pairs == 0) {
this.none += 1;
} else if (pairs == 1) {
this.one += 1;
} else if (pairs == 2) {
this.two += 1;
} else {
this.more += 1;
}
}
format(): String {
return `zir propagation: ${this.what}: ${i32ToString(this.one)} reached by one class, ` +
`${i32ToString(this.two)} by two, ${i32ToString(this.more)} by more, ` +
`${i32ToString(this.outside)} by something from outside, ${i32ToString(this.none)} by none`;
}
}
/** How the reached `call_ref` sites of one kind resolved. */
final class SiteTally {
what: String;
var one: i32 = 0;
var several: i32 = 0;
var outside: i32 = 0;
var nothing: i32 = 0;
new(this.what);
format(): String {
return `zir propagation: ${this.what}: ${i32ToString(this.one)} reach one function, ` +
`${i32ToString(this.several)} several, ${i32ToString(this.outside)} something from outside, ` +
`${i32ToString(this.nothing)} nothing`;
}
}
- 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 |
|
|