/** * ZIR verifier (docs/design/ir.md §11). * * Checks the SSA and CFG invariants that lowering and every pass must * preserve. Returns a list of human-readable errors; empty means valid. * Failures are meant to be loud — callers in verify mode should treat any * error as fatal rather than limping into emission. * * Checked here: * - every block is non-empty and ends with exactly one terminator * - params are param-instructions owned by their block * - branch targets are valid blocks; branch arg counts and types match * the target's parameters * - all blocks are reachable from the entry block (b0) * - every value operand is defined by a value-producing instruction that * dominates the use (same-block uses must come after the definition) */ import { ValType, ValTypeI32, ValTypeI64, ValTypeF32, ValTypeF64, ValTypeAnyRef, ValTypeEqRef, ValTypeStructRef, ValTypeRef, ValTypeRefNull, } from '../wasm.zena'; import { IrBody, IrOp, isIrTerminator, irOpName, isWideArithOp, IrScratch } from './ir.zena'; import { isValSubtype, WasmStruct } from '../wasm-module.zena'; import { IrCfg } from './cfg.zena'; function debugValType(vt: ValType) { return match (vt) { case ValTypeI32: 'i32' case ValTypeI64: 'i64' case ValTypeF32: 'f32' case ValTypeF64: 'f64' case ValTypeAnyRef: 'anyref' case ValTypeEqRef: 'eqref' case ValTypeStructRef: 'structref' case ValTypeRef as r: 'ref ' + (if (r.target is WasmStruct) ((r.target as WasmStruct).name ?? '?') else 'other') case ValTypeRefNull as rn: 'refnull ' + (if (rn.target is WasmStruct) ((rn.target as WasmStruct).name ?? '?') else 'other') case _: 'other' }; } export final class IrVerifier { body: IrBody; errors = new Array(); // Per-instruction position within its block: params get 0..paramCount-1, // body instructions follow. -1 = never placed in any block list. #instPos = new Array(); var #cfg: IrCfg | null = null; #scratch: IrScratch | null; new(this.body, scratch: IrScratch | null = null) : #scratch = scratch; verify(): GrowableArray { if (this.body.blocks.length == 0) { this.#error('function has no blocks'); return this.errors; } this.#checkBlockStructure(); if (this.errors.length > 0) { // Structure is broken; successor decoding below may be meaningless. return this.errors; } this.#checkEdges(); if (this.errors.length > 0) { return this.errors; } this.#cfg = new IrCfg(this.body, this.#scratch); this.#checkReachability(); this.#checkUses(); this.#checkVars(); return this.errors; } /** * Mutable variables: the id must be in range and a write must supply * the declared type. Reads need no dominance check — a variable is * storage, not an SSA definition — which is exactly why emission * must keep its local out of coalescing. */ #checkVars(): void { let {body} = this; var i = 0; while (i < body.instCount()) { let op = body.op(i); if (op == IrOp.var_get || op == IrOp.var_set) { let varId = body.b[i]; if (varId < 0 || varId >= body.varTypes.length) { this.#error('%' + i32ToString(i) + ' (' + irOpName(op) + ') names out-of-range var ' + i32ToString(varId)); } else if (op == IrOp.var_set) { let have = body.resultType(body.a[i]); let want = body.varTypes[varId]; if (have != null && !isValSubtype(have, want)) { this.#error('%' + i32ToString(i) + ' writes ' + debugValType(have) + ' into var ' + i32ToString(varId) + ' of type ' + debugValType(want)); } } } i += 1; } } #error(message: String): void { this.errors.push(message); } #checkBlockStructure(): void { let {body} = this; var i = 0; while (i < body.instCount()) { this.#instPos.push(-1); i += 1; } var blockId = 0; while (blockId < body.blocks.length) { let blk = body.blocks[blockId]; var pos = 0; for (let p in blk.params) { if (body.op(p) != IrOp.param) { this.#error('b' + i32ToString(blockId) + ': param list entry %' + i32ToString(p) + ' is not a param instruction'); } if (body.instBlock[p] != blockId) { this.#error('b' + i32ToString(blockId) + ': param %' + i32ToString(p) + ' belongs to another block'); } this.#instPos[p] = pos; pos += 1; } if (blk.insts.length == 0) { this.#error(`b${i32ToString(blockId)} is empty`); blockId += 1; continue; } var j = 0; while (j < blk.insts.length) { let inst = blk.insts[j]; if (body.instBlock[inst] != blockId) { this.#error('b' + i32ToString(blockId) + ': instruction %' + i32ToString(inst) + ' belongs to another block'); } this.#instPos[inst] = pos; pos += 1; let isTerm = isIrTerminator(body.op(inst)); let isLast = j == blk.insts.length - 1; if (isTerm && !isLast) { this.#error('b' + i32ToString(blockId) + ': terminator in the middle of the block at %' + i32ToString(inst)); } if (!isTerm && isLast) { this.#error(`b${i32ToString(blockId)} does not end with a terminator`); } if (body.op(inst) == IrOp.param) { this.#error('b' + i32ToString(blockId) + ': param %' + i32ToString(inst) + ' appears in instruction list'); } j += 1; } blockId += 1; } } #checkEdges(): void { let {body} = this; var blockId = 0; while (blockId < body.blocks.length) { let blk = body.blocks[blockId]; let term = blk.insts[blk.insts.length - 1]; let sN = body.successorCount(term); for (var sK = 0; sK < sN; sK += 1) { let sRec = body.successorRecord(term, sK); if (body.extra[sRec] < 0 || body.extra[sRec] >= body.blocks.length) { this.#error('b' + i32ToString(blockId) + ': branch to missing b' + i32ToString(body.extra[sRec])); continue; } let targetParams = body.blocks[body.extra[sRec]].params; if (body.extra[sRec + 1] != targetParams.length) { this.#error('b' + i32ToString(blockId) + ': branch to b' + i32ToString(body.extra[sRec]) + ' passes ' + i32ToString(body.extra[sRec + 1]) + ' args, expected ' + i32ToString(targetParams.length)); continue; } var i = 0; while (i < body.extra[sRec + 1]) { let arg = body.extra[(sRec + 2) + i]; let param = targetParams[i]; if (arg >= 0 && arg < body.instCount() && body.producesValue(arg) && body.producesValue(param)) { let argType = body.typeTable[body.typeId[arg]]; let paramType = body.typeTable[body.typeId[param]]; if (!isValSubtype(argType, paramType)) { this.#error('b' + i32ToString(blockId) + ': branch arg %' + i32ToString(arg) + ' type does not match param %' + i32ToString(param) + ' of b' + i32ToString(body.extra[sRec]) + ' [arg ' + debugValType(argType) + ' vs param ' + debugValType(paramType) + '; arg op ' + irOpName(body.op(arg)) + ', param op ' + irOpName(body.op(param)) + ']'); } } i += 1; } } blockId += 1; } } #checkReachability(): void { let cfg = this.#cfg as IrCfg; var blockId = 0; while (blockId < this.body.blocks.length) { if (!cfg.isReachable(blockId)) { this.#error('b' + i32ToString(blockId) + ' is unreachable from the entry block'); } blockId += 1; } } #checkUses(): void { let {body} = this; let cfg = this.#cfg as IrCfg; let operands = new Array(); var blockId = 0; while (blockId < body.blocks.length) { if (!cfg.isReachable(blockId)) { blockId += 1; continue; // already reported unreachable } let blk = body.blocks[blockId]; for (let inst in blk.insts) { while (operands.length > 0) { operands.pop(); } body.appendValueOperands(inst, operands); for (let v in operands) { this.#checkUse(inst, v, blockId); } } blockId += 1; } } #checkUse(user: i32, value: i32, useBlock: i32): void { let {body} = this; let cfg = this.#cfg as IrCfg; if (value < 0 || value >= body.instCount()) { this.#error('%' + i32ToString(user) + ' uses invalid value id %' + i32ToString(value)); return; } if (!body.producesValue(value)) { // Exception: mv_get projects results out of a multi-result // producer, which itself produces no single value — a call, or // one of the two-result wide-arithmetic instructions. let mvOk = body.op(user) == IrOp.mv_get && (body.op(value) == IrOp.call || body.op(value) == IrOp.call_ref || isWideArithOp(body.op(value))); if (!mvOk) { this.#error('%' + i32ToString(user) + ' uses %' + i32ToString(value) + ' (' + irOpName(body.op(value)) + '), which produces no value'); return; } } let defBlock = body.instBlock[value]; if (defBlock == useBlock) { if (this.#instPos[value] >= this.#instPos[user]) { this.#error('%' + i32ToString(user) + ' uses %' + i32ToString(value) + ' before its definition in b' + i32ToString(useBlock)); } return; } if (!cfg.dominates(defBlock, useBlock)) { this.#error('%' + i32ToString(user) + ' in b' + i32ToString(useBlock) + ' uses %' + i32ToString(value) + ' from b' + i32ToString(defBlock) + ', which does not dominate it'); } } } export function verifyIr(body: IrBody, scratch: IrScratch | null = null): GrowableArray { if (scratch != null) { scratch.enter(); } let verifier = new IrVerifier(body, scratch); let errors = verifier.verify(); if (scratch != null) { scratch.exit(); } return errors; }