/** * Sparse conditional constant propagation (docs/design/ * optimization-pipeline.md §SCCP), the Wegman–Zadeck algorithm over * ZIR: every value starts as "not yet seen" and every block as * unexecuted, and the two worklists lower values to a constant or to * "varies" while marking the edges a branch on a known constant can * actually take. The optimism is the point. The peephole pass folds a * branch whose condition is already a constant instruction; this * pass folds a branch whose condition is constant only because the * arm that would change it is dead — and that arm is dead only * because the condition is constant. A loop that assigns a variable * on a path the variable's own value rules out is the shape: * * var x = 1; * while (i < n) { if (x != 1) { x = 2; } i += 1; } * * The header's parameter for x meets 1 from the entry and, from the * back edge, the join's parameter — which meets only the untaken * arm's value, x itself. So x is 1, the test folds, and the arm goes. * Block parameters are where the precision lives: a parameter meets * only the arguments arriving on executed edges. * * Constant evaluation is the shared table in fold.zena, so this pass * and the peephole pass fold the same operations to the same values. * Type tests use castOutcome from the same file, so a `match` over a * value of known exact type decides here as well as there. * * Rewrites, after the analysis reaches its fixpoint: a constant * instruction becomes the constant in place; a constant block * parameter is deleted the way blockmerge deletes a trivial one, with * a fresh constant at the head of its block standing in; a `br_if` or * `br_table` with one executable edge becomes a `br`. Blocks no * executable edge reaches are left for the block cleanup pass, which * must run after this one (the verifier rejects unreachable blocks). * A function whose try-join block would become unreachable is left * alone entirely, for the reason blockmerge gives. * * Determinism: the lattice fixpoint does not depend on worklist * order, and the rewrites read only the fixpoint, in id order. */ import { IrBlock, IrBody, IrOp, buildUseLists, IrScratch } from './ir.zena'; import { ValTypeRef } from '../wasm.zena'; import { IrConst, castOutcome, constOf, evalBinary, evalUnary, foldInstTo, isFoldableBinary, isFoldableUnary, } from './fold.zena'; import { dropBranchArg, dropParamAt } from './blockmerge.zena'; import { rewriteToBr } from './simplify.zena'; /** Lattice states: not yet seen, a known constant, varies. */ let TOP = 0; let CONST = 1; let BOTTOM = 2; /** Runs the pass; returns the number of rewrites made. */ export function runSccp(body: IrBody, scratch: IrScratch): i32 { scratch.enter(); let result = runSccpOn(body, scratch); scratch.exit(); return result; } function runSccpOn(body: IrBody, scratch: IrScratch): i32 { let nb = body.blocks.length; let count = body.instCount(); if (nb == 0) { return 0; } // Control-flow edges, numbered in block order so a terminator's // edges are contiguous: edge k of block b is termFirstEdge[b] + k. let edgeTerm = scratch.i32(); let edgeTarget = scratch.i32(); let edgeArgStart = scratch.i32(); let edgeExec = scratch.bool(); let termFirstEdge = scratch.i32(); let termEdgeCount = scratch.i32(); let incoming = new Array>(); for (var b = 0; b < nb; b += 1) { termFirstEdge.push(-1); termEdgeCount.push(0); incoming.push(new Array()); } 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); termFirstEdge[b] = edgeTerm.length; termEdgeCount[b] = n; for (var k = 0; k < n; k += 1) { let rec = body.successorRecord(term, k); let target = body.extra[rec]; incoming[target].push(edgeTerm.length); edgeTerm.push(term); edgeTarget.push(target); edgeArgStart.push(rec + 2); edgeExec.push(false); } } // Def → users, for the SSA worklist. Branch arguments make the // terminator a user, which is what re-meets a target's parameters // when an argument lowers. let users = buildUseLists(body, scratch); let state = scratch.i32(); let value = new Array(); for (var i = 0; i < count; i += 1) { state.push(TOP); value.push(null); } let blockExec = scratch.bool(); for (var b = 0; b < nb; b += 1) { blockExec.push(false); } let ssaWork = scratch.i32(); let flowWork = scratch.i32(); // Moves an instruction's lattice value down to (s, v). Values only // descend: a constant that meets a different constant varies. let lower = (inst: i32, s: i32, v: IrConst | null) => { let old = state[inst]; if (old == BOTTOM || s == TOP) { return; } var newState = s; var newValue = v; if (old == CONST) { if (s == CONST) { let ov = value[inst]; if (ov != null) { if (v != null) { if (ov.equals(v)) { return; } } } } newState = BOTTOM; newValue = null; } state[inst] = newState; value[inst] = newValue; for (var k = 0; k < users.count(inst); k += 1) { ssaWork.push(users.at(inst, k)); } }; let markEdge = (e: i32) => { if (!edgeExec[e]) { edgeExec[e] = true; flowWork.push(e); } }; // A block parameter meets the arguments arriving on executed edges; // arguments not yet seen are ignored, which is the optimism. let visitParam = (p: i32, b: i32, j: i32) => { var s = TOP; var v: IrConst | null = null; for (let e in incoming[b]) { if (!edgeExec[e]) { continue; } let arg = body.extra[edgeArgStart[e] + j]; let argState = if (arg >= 0 && arg < count) state[arg] else BOTTOM; if (argState == TOP) { continue; } if (argState == BOTTOM) { s = BOTTOM; v = null; break; } let av = value[arg]; if (s == TOP) { s = CONST; v = av; continue; } var same = false; if (v != null) { if (av != null) { same = v.equals(av); } } if (!same) { s = BOTTOM; v = null; break; } } lower(p, s, v); }; let visitBlockParams = (b: i32) => { let params = body.blocks[b].params; for (var j = 0; j < params.length; j += 1) { visitParam(params[j], b, j); } }; let visitTerminator = (inst: i32, b: i32) => { let first = termFirstEdge[b]; let n = termEdgeCount[b]; if (n == 0) { return; } let op = body.op(inst); if (op == IrOp.br_if || op == IrOp.br_table) { let cond = body.a[inst]; let cs = state[cond]; if (cs == TOP) { return; } let cv = value[cond]; if (cs == CONST && cv != null) { if (op == IrOp.br_if) { markEdge(first + (if (cv.i != 0) 0 else 1)); } else { // wasm reads the selector as unsigned: negative picks the // default, which is the last successor. let v = cv.i; markEdge(first + (if (v >= 0 && v < n - 1) v else n - 1)); } } else { for (var k = 0; k < n; k += 1) { markEdge(first + k); } } } else { // br, try_br, br_on_cast, yield_, await_: every edge may run. for (var k = 0; k < n; k += 1) { markEdge(first + k); } } // The branch arguments may be what changed: re-meet the params of // every successor already executing (new ones meet from the flow // worklist). for (var k = 0; k < n; k += 1) { let e = first + k; if (edgeExec[e] && blockExec[edgeTarget[e]]) { visitBlockParams(edgeTarget[e]); } } }; let visitInst = (inst: i32) => { let op = body.op(inst); if (op == IrOp.nop) { return; } let b = body.instBlock[inst]; if (op == IrOp.param) { if (b == 0) { lower(inst, BOTTOM, null); return; } let params = body.blocks[b].params; for (var j = 0; j < params.length; j += 1) { if (params[j] == inst) { visitParam(inst, b, j); return; } } return; } let insts = body.blocks[b].insts; if (insts.length > 0 && insts[insts.length - 1] == inst) { visitTerminator(inst, b); return; } if (!body.producesValue(inst) || state[inst] == BOTTOM) { return; } let own = constOf(body, inst); if (own != null) { lower(inst, CONST, own); return; } let av = body.a[inst]; if (op == IrOp.ref_is_null) { let from = body.resultType(av); if (from != null && from is ValTypeRef) { lower(inst, CONST, IrConst.ofBool(false)); return; } lower(inst, BOTTOM, null); return; } if (op == IrOp.ref_test) { let from = body.resultType(av); if (from != null && body.b[inst] >= 0) { let outcome = castOutcome(from, body.typeTable[body.b[inst]]); if (outcome >= 0) { lower(inst, CONST, IrConst.ofBool(outcome == 1)); return; } } lower(inst, BOTTOM, null); return; } if (isFoldableBinary(op)) { let bv = body.b[inst]; if (state[av] == TOP || state[bv] == TOP) { return; // an operand is still to come } let x = value[av]; let y = value[bv]; if (x != null) { if (y != null) { let r = evalBinary(op, x, y); if (r != null) { lower(inst, CONST, r); return; } } } lower(inst, BOTTOM, null); return; } if (isFoldableUnary(op)) { if (state[av] == TOP) { return; } let x = value[av]; if (x != null) { let r = evalUnary(op, x); if (r != null) { lower(inst, CONST, r); return; } } lower(inst, BOTTOM, null); return; } lower(inst, BOTTOM, null); }; let visitBlock = (b: i32) => { visitBlockParams(b); for (let inst in body.blocks[b].insts) { visitInst(inst); } }; blockExec[0] = true; for (let p in body.blocks[0].params) { lower(p, BOTTOM, null); } visitBlock(0); while (flowWork.length > 0 || ssaWork.length > 0) { if (flowWork.length > 0) { let e = flowWork.pop(); let t = edgeTarget[e]; if (!blockExec[t]) { blockExec[t] = true; visitBlock(t); } else { visitBlockParams(t); } continue; } let inst = ssaWork.pop(); if (blockExec[body.instBlock[inst]]) { visitInst(inst); } } // A try's join block losing reachability is the case blockmerge // refuses to clean; refusing here too keeps the function verifiable. for (var i = 0; i < count; i += 1) { if (body.op(i) == IrOp.try_br && blockExec[body.instBlock[i]]) { if (let (true, join) = body.tryJoin.get(i)) { if (!blockExec[join]) { return 0; } } } } var rewrites = 0; // Constant instructions become constants in place. for (var i = 0; i < count; i += 1) { if (state[i] != CONST) { continue; } let op = body.op(i); if (op == IrOp.param || op == IrOp.const_i32 || op == IrOp.const_i64 || op == IrOp.const_f64) { continue; } let c = value[i]; if (c != null) { foldInstTo(body, i, c); rewrites += 1; } } // Constant block parameters: a constant at the head of the block // takes the parameter's uses, and the parameter and its arguments // go. Higher indices first, so a deletion leaves the lower ones. let repl = scratch.i32(); for (var i = 0; i < count; i += 1) { repl.push(i); } var paramsRemoved = 0; for (var b = 1; b < nb; b += 1) { if (!blockExec[b]) { continue; } let blk = body.blocks[b]; let heads = new Array(); var j = blk.params.length - 1; while (j >= 0) { let p = blk.params[j]; let c = value[p]; if (state[p] == CONST && c != null) { let id = newConst(body, b, body.typeId[p], c); heads.push(id); repl[p] = id; nopOut(body, p); dropParamAt(blk, j); for (let term in uniqueTerms(body, incoming[b], edgeTerm)) { dropBranchArg(body, term, b, j); } paramsRemoved += 1; } j -= 1; } if (heads.length > 0) { prependInsts(blk, heads); } } rewrites += paramsRemoved; // Branches with one executable edge become unconditional. for (var b = 0; b < nb; b += 1) { if (!blockExec[b] || termEdgeCount[b] < 2) { continue; } let insts = body.blocks[b].insts; let term = insts[insts.length - 1]; let op = body.op(term); if (op != IrOp.br_if && op != IrOp.br_table) { continue; } var live = -1; var liveCount = 0; for (var k = 0; k < termEdgeCount[b]; k += 1) { if (edgeExec[termFirstEdge[b] + k]) { live = k; liveCount += 1; } } if (liveCount == 1) { let succs = body.successors(term); rewriteToBr(body, term, succs[live]); rewrites += 1; } } if (paramsRemoved > 0) { let canon = (v: i32) => { var c = v; while (c >= 0 && c < count && repl[c] != c) { c = repl[c]; } return c; }; let total = body.instCount(); for (var i = 0; i < total; i += 1) { if (body.op(i) != IrOp.nop) { body.rewriteValueOperands(i, canon); } } } return rewrites; } /** A fresh constant instruction of the given type, owned by `block`. */ function newConst(body: IrBody, block: i32, typeId: i32, c: IrConst): i32 { let id = body.opcode.length; body.opcode.push(IrOp.nop as i32); body.typeId.push(typeId); body.a.push(-1); body.b.push(-1); body.instBlock.push(block); foldInstTo(body, id, c); return id; } /** Puts `ids` ahead of the block's existing instructions. */ function prependInsts(blk: IrBlock, ids: GrowableArray): void { let old = new Array(); for (let i in blk.insts) { old.push(i); } while (blk.insts.length > 0) { blk.insts.pop(); } for (let i in ids) { blk.insts.push(i); } for (let i in old) { blk.insts.push(i); } } /** * The distinct terminators behind a block's incoming edges, in edge * order: a branch both of whose edges reach the block has its * argument dropped once. */ function uniqueTerms(body: IrBody, edges: GrowableArray, edgeTerm: GrowableArray): GrowableArray { let terms = new Array(); for (let e in edges) { let t = edgeTerm[e]; if (terms.length == 0 || terms[terms.length - 1] != t) { terms.push(t); } } return terms; } function nopOut(body: IrBody, inst: i32): void { body.opcode[inst] = IrOp.nop as i32; body.typeId[inst] = -1; body.a[inst] = -1; body.b[inst] = -1; body.instBlock[inst] = -1; }