/** * CFG cleanup (docs/design/optimization-pipeline.md, cleanup set): * removes blocks unreachable from the entry after branch folding. The * verifier requires every block reachable, so folding a `br_if` on a * constant is only legal paired with this pass. * * Removal is physical — the block list is compacted and every * surviving terminator's targets are renumbered — because block ids * are indices. The target of every successor sits exactly two `extra` * slots before its first branch arg (the [target, argc, args…] layout * every terminator shares, see successors() in ir.zena), so * renumbering writes through IrSuccessor.argStart - 2 rather than * re-decoding each terminator shape. * * Two more cleanups keep the graph in the shape the emitter reads * best. A block whose only instruction is a `br` forwards every edge * into it straight to its target (jump to jump), and a block whose * sole predecessor ends in an unconditional `br` to it fuses into that * predecessor. Both matter to the emitter's loop-exit placement: it * puts an exit block after the loop's `end`, behind a label, only * when the exit is a dominator child of the loop header, and an * inlined body leaves the header holding one jump into the inlined * test, whose exhausted arm is one more jump to the exit. Without the * two cleanups the exit sits two levels down and the emitter falls * back to an if/else with the exit's code inside the loop, which * wasmtime compiles a good deal worse. */ import { IrBlock, IrBody, IrOp, IrScratch } from './ir.zena'; import { isValSubtype } from '../wasm-module.zena'; /** * Runs the cleanups; returns the number of blocks removed plus the * number of block parameters deleted plus the number of edges * forwarded and blocks fused. */ export function runBlockCleanup(body: IrBody, scratch: IrScratch): i32 { scratch.enter(); let result = runBlockCleanupOn(body, scratch); scratch.exit(); return result; } function runBlockCleanupOn(body: IrBody, scratch: IrScratch): i32 { var n = removeUnreachable(body, scratch) + removeTrivialParams(body, scratch); let forwarded = forwardEmptyBlocks(body, scratch); let fused = fuseStraightLine(body, scratch); if (forwarded > 0 || fused > 0) { n += forwarded + fused + removeUnreachable(body, scratch) + removeTrivialParams(body, scratch); } return n; } /** The join blocks of the function's user tries, which stay as they are. */ function tryJoins(body: IrBody, scratch: IrScratch) { let joins = scratch.i32(); for (let k in body.tryJoin.keys()) { joins.push(body.tryJoin[k]); } return joins; } function isIn(list: GrowableArray, b: i32): boolean { for (let x in list) { if (x == b) { return true; } } return false; } /** * Sends every edge into a block whose only instruction is a `br` * straight to that br's target, with the br's arguments substituted * for the block's parameters. Only edges from br/br_if/br_table are * moved (a try_br's targets keep their shape for the emitter); a * block some other edge still reaches keeps working as it was. */ function forwardEmptyBlocks(body: IrBody, scratch: IrScratch): i32 { let nb = body.blocks.length; let joins = tryJoins(body, scratch); // Users of every value: a parameter of a forwarded block must feed // nothing but the block's own br, since a block it dominates could // otherwise read it and the forwarded edges would carry no value. let count = body.instCount(); let useCount = scratch.i32(); for (var i = 0; i < count; i += 1) { useCount.push(0); } let operands = scratch.i32(); for (var i = 0; i < count; i += 1) { if (body.op(i) == IrOp.nop) { continue; } operands.clear(); body.appendValueOperands(i, operands); for (let v in operands) { if (v >= 0 && v < count) { useCount[v] += 1; } } } // The predecessors of every block along the edges this pass moves, // kept current as it moves them, so each candidate looks only at // the terminators that reach it rather than at every block's. let preds = new Array>(nb); for (var b = 0; b < nb; b += 1) { preds.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 op = body.op(term); if (op != IrOp.br && op != IrOp.br_if && op != IrOp.br_table) { continue; } 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) { preds[target].push(b); } } } var forwarded = 0; for (var e = 1; e < nb; e += 1) { let blk = body.blocks[e]; if (blk.insts.length == 0 || isIn(joins, e)) { continue; } let term = blk.insts[blk.insts.length - 1]; if (body.op(term) != IrOp.br) { continue; } var empty = true; for (let inst in blk.insts) { if (inst != term && body.op(inst) != IrOp.nop) { empty = false; } } if (!empty) { continue; } let onward = body.successorRecord(term, 0); let onwardTarget = body.extra[onward]; let onwardArgc = body.extra[onward + 1]; // Each parameter's uses are all in the br's argument list. var paramsLocal = true; for (let p in blk.params) { var inArgs = 0; var i = 0; while (i < onwardArgc) { if (body.extra[onward + 2 + i] == p) { inArgs += 1; } i += 1; } if (useCount[p] != inArgs) { paramsLocal = false; } } if (!paramsLocal) { continue; } if (onwardTarget == e) { continue; } let ps = preds[e]; for (let b in ps) { if (b == e) { continue; } let pInsts = body.blocks[b].insts; let pTerm = pInsts[pInsts.length - 1]; // Successor slots are re-decoded after every rewrite, since a // rewrite appends a fresh record. var k = 0; while (true) { if (k >= body.successorCount(pTerm)) { break; } let rec = body.successorRecord(pTerm, k); if (body.extra[rec] != e) { k += 1; continue; } let args = new Array(); var i = 0; while (i < onwardArgc) { let v = body.extra[onward + 2 + i]; var mapped = v; for (var q = 0; q < blk.params.length; q += 1) { if (blk.params[q] == v) { mapped = body.extra[rec + 2 + q]; } } args.push(mapped); i += 1; } retarget(body, pTerm, k, onwardTarget, args); preds[onwardTarget].push(b); forwarded += 1; k += 1; } } } return forwarded; } /** * Appends a block to its sole predecessor when that predecessor ends * in an unconditional `br` to it and the block has no parameters * (a single edge's parameters are trivial and already gone). Chains * fuse in one call: the predecessor's new terminator is checked again. */ function fuseStraightLine(body: IrBody, scratch: IrScratch): i32 { let nb = body.blocks.length; let joins = tryJoins(body, scratch); var fused = 0; var progress = true; let incoming = scratch.i32(); while (progress) { progress = false; // Incoming edge counts. incoming.clear(); for (var b = 0; b < nb; b += 1) { incoming.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) { incoming[body.extra[body.successorRecord(term, k)]] += 1; } } for (var p = 0; p < nb; p += 1) { let pBlk = body.blocks[p]; if (pBlk.insts.length == 0) { continue; } let pTerm = pBlk.insts[pBlk.insts.length - 1]; if (body.op(pTerm) != IrOp.br) { continue; } let s = body.extra[body.successorRecord(pTerm, 0)]; if (s == p || s == 0 || incoming[s] != 1 || isIn(joins, s)) { continue; } let sBlk = body.blocks[s]; if (sBlk.params.length > 0 || sBlk.insts.length == 0) { continue; } // Move: the predecessor's br goes, the block's instructions // follow, the block empties (unreachable, removed afterwards). nopOut(body, pTerm); pBlk.insts.pop(); for (let inst in sBlk.insts) { pBlk.insts.push(inst); body.instBlock[inst] = p; } while (sBlk.insts.length > 0) { sBlk.insts.pop(); } incoming[s] = 0; fused += 1; progress = true; // The next pass recounts edges; a chain continues from p. break; } } return fused; } /** * Rebuilds a terminator's successor records with successor `k` * replaced by `target(args)`. Records live inline in `extra`, so the * rebuilt record is appended and the terminator repointed; every * branch shape is [prefix] ([target, argc, args…])*. */ export function retarget(body: IrBody, term: i32, k: i32, target: i32, args: GrowableArray): void { let op = body.op(term); let prefixLen = if (op == IrOp.br_on_cast || op == IrOp.br_on_cast_fail || op == IrOp.br_table) { 1 } else { 0 }; let recordStart = if (op == IrOp.br) body.a[term] else body.b[term]; let count = body.successorCount(term); let idx = body.extra.length; var p = 0; while (p < prefixLen) { body.extra.push(body.extra[recordStart + p]); p += 1; } // The old records are read as the new ones are appended; the // terminator still points at the old ones until the end. var rec = body.successorRecord(term, 0); for (var n = 0; n < count; n += 1) { let argc = body.extra[rec + 1]; if (n == k) { body.extra.push(target); body.extra.push(args.length); for (let v in args) { body.extra.push(v); } } else { body.extra.push(body.extra[rec]); body.extra.push(argc); var i = 0; while (i < argc) { body.extra.push(body.extra[rec + 2 + i]); i += 1; } } rec += 2 + argc; } if (op == IrOp.br) { body.a[term] = idx; } else { body.b[term] = idx; } } function removeUnreachable(body: IrBody, scratch: IrScratch): i32 { let nb = body.blocks.length; if (nb == 0) { return 0; } let reachable = scratch.bool(); for (var i = 0; i < nb; i += 1) { reachable.push(false); } let stack = scratch.i32(); reachable[0] = true; stack.push(0); while (stack.length > 0) { let b = stack.pop(); let insts = body.blocks[b].insts; 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 (!reachable[target]) { reachable[target] = true; stack.push(target); } } } var removedCount = 0; for (var i = 0; i < nb; i += 1) { if (!reachable[i]) { removedCount += 1; } } if (removedCount == 0) { return 0; } // A try's join block (IrBody.tryJoin) is where emission ends the // protected region. It dies when folding or inlining leaves the try // body no way to complete, as when the body calls a function that // only throws; the try_br survives without it (renumbering drops // the entry). No block is then reached through the body's normal // exit, so nothing can be placed inside the try_table that belongs // after it, which is what the join is there to prevent. let instCount = body.instCount(); let map = scratch.i32(); var next = 0; for (var i = 0; i < nb; i += 1) { if (reachable[i]) { map.push(next); next += 1; } else { map.push(-1); } } // Nop every instruction (params included) of the dead blocks so use // counts, stats, and emission never see them again. for (var i = 0; i < nb; i += 1) { if (reachable[i]) { continue; } let blk = body.blocks[i]; for (let p in blk.params) { nopOut(body, p); } for (let inst in blk.insts) { nopOut(body, inst); } } // Renumber: instBlock for survivors, successor targets, tryJoin. for (var i = 0; i < instCount; i += 1) { let ob = body.instBlock[i]; if (ob >= 0 && ob < nb) { body.instBlock[i] = map[ob]; } } for (var i = 0; i < nb; i += 1) { if (!reachable[i]) { continue; } let insts = body.blocks[i].insts; let term = insts[insts.length - 1]; let sN = body.successorCount(term); for (var sK = 0; sK < sN; sK += 1) { let sRec = body.successorRecord(term, sK); body.extra[(sRec + 2) - 2] = map[body.extra[sRec]]; } } let newJoin = new Map(); for (var i = 0; i < instCount; i += 1) { if (body.op(i) == IrOp.try_br) { if (let (true, join) = body.tryJoin.get(i)) { if (map[join] >= 0) { newJoin[i] = map[join]; } } } } // tryJoin's field is immutable; rebuild its contents in place, in // instruction-id order for determinism. let oldKeys = scratch.i32(); for (let k in body.tryJoin.keys()) { oldKeys.push(k); } for (let k in oldKeys) { body.tryJoin.delete(k); } for (var i = 0; i < instCount; i += 1) { if (body.op(i) == IrOp.try_br) { if (let (true, join) = newJoin.get(i)) { body.tryJoin[i] = join; } } } // Compact the block list in place (the field itself is immutable). let survivors = new Array(); for (var i = 0; i < nb; i += 1) { if (reachable[i]) { survivors.push(body.blocks[i]); } } while (body.blocks.length > 0) { body.blocks.pop(); } for (let blk in survivors) { body.blocks.push(blk); } return removedCount; } /** * Deletes every block parameter that every incoming edge passes the * same value for (a back edge passing the parameter itself does not * count): uses of the parameter become that value, the parameter * leaves the block, and its argument leaves every incoming branch. * The value dominates the block because it dominates each * predecessor. * * The common case is the continuation block an inlined callee returns * through: its parameter is the callee's one returned value, and once * the parameter is gone the forwarding rules in simplify see the * allocation behind it. (Redirecting uses while leaving the parameter * in place was tried first and made emission worse — the emitter * coalesces a parameter with its incoming copies, and a redirected * use defeats that — so the parameter and the arguments go too.) */ function removeTrivialParams(body: IrBody, scratch: IrScratch): i32 { let nb = body.blocks.length; let incoming = new Array>(nb); for (var i = 0; i < nb; i += 1) { incoming.push(new Array()); } for (let blk in body.blocks) { if (blk.insts.length == 0) { continue; } let term = blk.insts[blk.insts.length - 1]; let n = body.successorCount(term); for (var k = 0; k < n; k += 1) { // Once per terminator: a branch whose edges both reach the same // block would otherwise have the argument dropped twice. let list = incoming[body.extra[body.successorRecord(term, k)]]; if (list.length == 0 || list[list.length - 1] != term) { list.push(term); } } } let count = body.instCount(); let repl = scratch.i32(); for (var i = 0; i < count; i += 1) { repl.push(i); } let canon = (v: i32) => { var c = v; while (c >= 0 && c < count && repl[c] != c) { c = repl[c]; } return c; }; var removed = 0; // Block 0 holds the function's parameters, which have no incoming // edges; every other block's parameters are candidates. Higher // indices first, so removing one leaves the lower indices intact. for (var b = 1; b < nb; b += 1) { let edges = incoming[b]; if (edges.length == 0) { continue; } let params = body.blocks[b].params; var j = params.length - 1; while (j >= 0) { let p = params[j]; var value = -1; var trivial = true; for (let term in edges) { let n = body.successorCount(term); for (var k = 0; k < n; k += 1) { let rec = body.successorRecord(term, k); if (body.extra[rec] != b) { continue; } let arg = canon(body.extra[rec + 2 + j]); if (arg == p) { continue; } if (value < 0) { value = arg; } else if (arg != value) { trivial = false; } } } if (trivial && value >= 0) { let from = body.resultType(value); let to = body.resultType(p); if (from != null && to != null && isValSubtype(from, to)) { repl[p] = value; nopOut(body, p); dropParamAt(body.blocks[b], j); for (let term in edges) { dropBranchArg(body, term, b, j); } removed += 1; } } j -= 1; } } if (removed > 0) { for (var i = 0; i < count; i += 1) { if (body.op(i) != IrOp.nop) { body.rewriteValueOperands(i, canon); } } } return removed; } export function dropParamAt(blk: IrBlock, j: i32): void { let kept = new Array(); for (var k = 0; k < blk.params.length; k += 1) { if (k != j) { kept.push(blk.params[k]); } } while (blk.params.length > 0) { blk.params.pop(); } for (let p in kept) { blk.params.push(p); } } /** * Rebuilds a terminator's successor records without argument `j` of * every successor targeting `target`. Records live inline in `extra`, * so the rebuilt record is appended and the terminator repointed. * Every branch shape is [prefix] ([target, argc, args…])*: no prefix * for br/br_if/try_br, the target type for br_on_cast, the count for * br_table (see the encoding table in ir.zena). */ export function dropBranchArg(body: IrBody, term: i32, target: i32, j: i32): void { let op = body.op(term); let prefixLen = if (op == IrOp.br_on_cast || op == IrOp.br_on_cast_fail || op == IrOp.br_table) { 1 } else { 0 }; let recordStart = if (op == IrOp.br) body.a[term] else body.b[term]; let sN = body.successorCount(term); let idx = body.extra.length; var p = 0; while (p < prefixLen) { body.extra.push(body.extra[recordStart + p]); p += 1; } for (var sK = 0; sK < sN; sK += 1) { let sRec = body.successorRecord(term, sK); body.extra.push(body.extra[sRec]); let drop = body.extra[sRec] == target; body.extra.push(if (drop) body.extra[sRec + 1] - 1 else body.extra[sRec + 1]); var i = 0; while (i < body.extra[sRec + 1]) { if (!(drop && i == j)) { body.extra.push(body.extra[(sRec + 2) + i]); } i += 1; } } if (op == IrOp.br) { body.a[term] = idx; } else { body.b[term] = idx; } } 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; }