/** * Counters for `ZENA_ZIR_STATS=1` that measure what interprocedural * type propagation (#421) could still improve once the module loop has * run: the `call_ref` sites it left, what each dispatches through and * how many implementations the module's vtables hold for its slot; the * class-interface pair vtables and trampolines discovery built and the * ones that survived; and the interface type tests whose operand is not * statically the interface. * * A dispatch site whose slot has two or more implementations in the * module is the case a per-site class set can resolve and the module's * own vtables cannot. A site with one implementation survived for some * other reason (a signature that differs from the slot's). */ import { i32ToString, growable } from 'zena:core'; import { HashMap, HashSet } from 'zena:collections'; import { IrBody, IrOp, IrRefField } from './ir.zena'; import { DevirtContext, slotImplementationCount } from './devirt.zena'; import { WasmModule, WasmStruct } from '../wasm-module.zena'; import { ClassType, InterfaceType } from '../../types.zena'; /** Sites by how many implementations their slot has: 1, 2, 3, 4, 5–8, 9+, unknown. */ final class ImplementationHistogram { counts = growable([0, 0, 0, 0, 0, 0, 0]); add(n: i32): void { let bucket = if (n < 0) 6 else if (n <= 1) 0 else if (n <= 4) n - 1 else if (n <= 8) 4 else 5; this.counts[bucket] = this.counts[bucket] + 1; } format(): String { let c = this.counts; return `1: ${i32ToString(c[0])}, 2: ${i32ToString(c[1])}, 3: ${i32ToString(c[2])}, ` + `4: ${i32ToString(c[3])}, 5-8: ${i32ToString(c[4])}, 9+: ${i32ToString(c[5])}, ` + `unknown: ${i32ToString(c[6])}`; } } /** The surviving dispatch sites through one vtable slot. */ final class SlotTally { key: String; implementations: i32; var sites: i32 = 1; new(this.key, this.implementations); } /** What discovery built, counted before the module loop and harvest change it. */ export final class DiscoveryCounts { pairVTables: i32; trampolines: i32; new(wasm: WasmModule) : pairVTables = wasm.classInterfaceVTables.size, trampolines = countTrampolines(wasm); } function countTrampolines(wasm: WasmModule): i32 { var n = 0; for (let f in wasm.functions) { if (f.interfaceTrampolineTarget != null) { n += 1; } } return n; } /** Steps over the casts lowering wraps around vtable and slot loads. */ function throughCasts(body: IrBody, v: i32): i32 { var c = v; while (c >= 0) { let op = body.op(c); if (op == IrOp.ref_cast || op == IrOp.ref_as_non_null) { c = body.a[c]; continue; } return c; } return c; } /** What a `call_ref` site dispatches through. */ export enum CallKind { ClassDispatch, InterfaceDispatch, Closure, Other, } /** Classifies `call_ref` sites by the struct their callee is loaded from. */ export final class CallKinds { #interfaceVTables = new HashSet(); #classVTables = new HashSet(); #closures = new HashSet(); new(wasm: WasmModule) { for (let entry in wasm.interfaceVTableStructs) { this.#interfaceVTables.add(entry.value.uid); } for (let entry in wasm.classInfos) { let vst = entry.value.vtableStructType; if (vst != null) { this.#classVTables.add(vst.uid); } } for (let entry in wasm.closureStructs) { this.#closures.add(entry.value.uid); } } /** The `struct_get` that loads the callee of the call at `inst`, through casts, or -1. */ slotLoad(body: IrBody, inst: i32): i32 { let v = throughCasts(body, body.extra[body.a[inst]]); if (v < 0 || body.op(v) != IrOp.struct_get || !(body.refTable[body.b[v]] is IrRefField)) { return -1; } return v; } ofOwner(owner: WasmStruct): CallKind { if (this.#closures.has(owner.uid)) { return CallKind.Closure; } if (this.#interfaceVTables.has(owner.uid)) { return CallKind.InterfaceDispatch; } if (this.#classVTables.has(owner.uid)) { return CallKind.ClassDispatch; } return CallKind.Other; } kindOf(body: IrBody, inst: i32): CallKind { let v = this.slotLoad(body, inst); if (v < 0) { return CallKind.Other; } return this.ofOwner((body.refTable[body.b[v]] as IrRefField).owner); } } /** * The census lines, for the module as it is about to be emitted: * `bodies` are the surviving functions' bodies after every pass. */ export function censusReport(wasm: WasmModule, bodies: GrowableArray, before: DiscoveryCounts): GrowableArray { let interfaceVTables = new HashSet(); for (let entry in wasm.interfaceVTableStructs) { interfaceVTables.add(entry.value.uid); } let kinds = new CallKinds(wasm); let cx = new DevirtContext(wasm); var total = 0; var closureCalls = 0; var otherCalls = 0; let classSites = new ImplementationHistogram(); let interfaceSites = new ImplementationHistogram(); var classCalls = 0; var interfaceCalls = 0; let slotTallies = new HashMap(); let slotOrder = new GrowableArray(); for (let body in bodies) { 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; } total += 1; let v = kinds.slotLoad(body, inst); if (v < 0) { otherCalls += 1; continue; } let fieldRef = body.refTable[body.b[v]] as IrRefField; let owner = fieldRef.owner; let kind = kinds.ofOwner(owner); if (kind == CallKind.Closure) { closureCalls += 1; continue; } if (kind == CallKind.Other) { otherCalls += 1; continue; } let isInterface = kind == CallKind.InterfaceDispatch; let impls = slotImplementationCount(cx, owner, owner.fieldIndexByName(fieldRef.fieldName)); if (isInterface) { interfaceCalls += 1; interfaceSites.add(impls); } else { classCalls += 1; classSites.add(impls); } let key = `${if (owner.name != null) owner.name as String else ''}.${fieldRef.fieldName}`; if (let (true, tally) = slotTallies.get(key)) { tally.sites += 1; } else { let tally = new SlotTally(key, impls); slotTallies[key] = tally; slotOrder.push(tally); } } } } var pairVTables = 0; for (let g in wasm.globals) { let init = g.initVTable; if (init != null && interfaceVTables.has(init.structType.uid)) { pairVTables += 1; } } var classSources = 0; var interfaceSources = 0; var otherSources = 0; for (let site in wasm.typeTestSites) { let s = site.source; if (s is ClassType) { classSources += 1; } else if (s is InterfaceType) { interfaceSources += 1; } else { otherSources += 1; } } let lines = new GrowableArray(); lines.push(`zir census: ${i32ToString(total)} call_ref sites left: ` + `${i32ToString(classCalls)} class dispatch, ${i32ToString(interfaceCalls)} interface dispatch, ` + `${i32ToString(closureCalls)} closure, ${i32ToString(otherCalls)} other`); lines.push(`zir census: class dispatch by implementations of the slot: ${classSites.format()}`); lines.push(`zir census: interface dispatch by implementations of the slot: ${interfaceSites.format()}`); // The slots with the most sites, most first; ties keep first-seen order. var i = 1; while (i < slotOrder.length) { let t = slotOrder[i]; var j = i - 1; while (j >= 0 && slotOrder[j].sites < t.sites) { slotOrder[j + 1] = slotOrder[j]; j -= 1; } slotOrder[j + 1] = t; i += 1; } var shown = 0; for (let t in slotOrder) { if (shown >= 20) { break; } lines.push(` ${i32ToString(t.sites)} sites through ${t.key} ` + `(${i32ToString(t.implementations)} implementations)`); shown += 1; } lines.push(`zir census: ${i32ToString(pairVTables)} class-interface vtables ` + `(${i32ToString(before.pairVTables)} built), ${i32ToString(countTrampolines(wasm))} trampolines ` + `(${i32ToString(before.trampolines)} built)`); lines.push(`zir census: ${i32ToString(wasm.typeTestSites.length)} interface type tests on a value ` + `not held as the interface (operand a class: ${i32ToString(classSources)}, ` + `another interface: ${i32ToString(interfaceSources)}, other: ${i32ToString(otherSources)}); ` + `${i32ToString(wasm.typeTestPairs.size)} class-interface pairs answer them`); return lines; }