/** * Jump threading through a block that only branches on its own * parameter. After an iterator's `next()` inlines into a protocol * loop and its object dissolves, what remains of the call is its * continuation: a block whose parameters are the returned values — * a done flag and an element — and whose one instruction is the * `br_if` on the flag that picks the loop body or the exit. Every * predecessor passes a constant for the flag (1 from the arm that * found an element, 0 from the arm that ran out), so each of them * already knows which way the branch goes. This pass sends each such * predecessor straight to that arm. * * The values matter more than the jump. The arm's blocks read the * continuation's parameters (the body reads the element), and a * predecessor that jumps past the continuation must deliver them * another way: the arm gets a parameter of its own for each * continuation parameter its blocks use, the continuation's edge to * the arm passes its parameter through, and a threaded edge passes * what it would have passed to the continuation. Uses inside the arm * move to the arm's parameter. When the threaded edges were all the * continuation had, it loses its last predecessor and the block * cleanup pass removes it, and the arm's new parameter is trivial * (one edge, one value) and goes the same way. The loop is then the * hand-written one: test, element, body, back. * * Preconditions, all checked: the block has parameters and no * instruction but the branch (an `i32.eqz` of the parameter, used * only by the branch, is allowed as the condition); the two targets * are distinct and neither is the block itself; at least one * incoming edge passes a constant; every use of every parameter, * besides the branch, lies in a block one of the two targets * dominates; and a target that needs parameters has the block as its * only predecessor (another predecessor would have nothing to pass). * A try's join block is never threaded through. * * Determinism: blocks in id order, one threading per CFG rebuild. */ import { IrBody, IrOp, buildUseLists, IrScratch } from './ir.zena'; import { IrCfg } from './cfg.zena'; import { retarget } from './blockmerge.zena'; import { i32ToString, growable } from 'zena:core'; /** Runs the pass; returns the number of blocks threaded through. */ export function runJumpThreading(body: IrBody, scratch: IrScratch): i32 { scratch.enter(); let result = runJumpThreadingOn(body, scratch); scratch.exit(); return result; } function runJumpThreadingOn(body: IrBody, scratch: IrScratch): i32 { var threaded = 0; while (threaded < 64 && threadStep(body, scratch)) { threaded += 1; } return threaded; } /** One threading, in its own scope: the CFG it builds goes back to the pool. */ function threadStep(body: IrBody, scratch: IrScratch): boolean { scratch.enter(); let cfg = new IrCfg(body, scratch); let c = findCandidate(body, cfg, scratch); if (c >= 0) { threadThrough(body, cfg, c, scratch); } scratch.exit(); return c >= 0; } /** The first block eligible for threading, or -1. */ function findCandidate(body: IrBody, cfg: IrCfg, scratch: IrScratch): i32 { let joins = new Array(); for (let k in body.tryJoin.keys()) { joins.push(body.tryJoin[k]); } let nb = body.blocks.length; for (var c = 1; c < nb; c += 1) { if (!cfg.isReachable(c)) { continue; } var isJoin = false; for (let j in joins) { if (j == c) { isJoin = true; } } if (isJoin) { continue; } if (eligible(body, cfg, c, scratch)) { return c; } } return -1; } /** * The branch's condition as a parameter of `c`: the parameter id, or * -1. `negated` reports an `i32.eqz` between the two. */ function conditionParam(body: IrBody, c: i32): i32 { let blk = body.blocks[c]; let term = blk.insts[blk.insts.length - 1]; let cond = body.a[term]; if (body.op(cond) == IrOp.param && body.instBlock[cond] == c) { return cond; } if (body.op(cond) == IrOp.i32_eqz && body.instBlock[cond] == c) { let inner = body.a[cond]; if (body.op(inner) == IrOp.param && body.instBlock[inner] == c) { return inner; } } return -1; } function conditionNegated(body: IrBody, c: i32) { let blk = body.blocks[c]; let term = blk.insts[blk.insts.length - 1]; return body.op(body.a[term]) == IrOp.i32_eqz; } function eligible(body: IrBody, cfg: IrCfg, c: i32, scratch: IrScratch): boolean { let blk = body.blocks[c]; if (blk.params.length == 0 || blk.insts.length == 0) { return false; } let term = blk.insts[blk.insts.length - 1]; if (body.op(term) != IrOp.br_if) { return false; } let p = conditionParam(body, c); if (p < 0) { return false; } let cond = body.a[term]; // Nothing but the branch and, when negated, the eqz. for (let inst in blk.insts) { if (inst == term || body.op(inst) == IrOp.nop || inst == cond) { continue; } return false; } let t = body.extra[body.successorRecord(term, 0)]; let f = body.extra[body.successorRecord(term, 1)]; if (t == f || t == c || f == c) { return false; } // At least one incoming edge passes a constant for the parameter. var j = -1; for (var k = 0; k < blk.params.length; k += 1) { if (blk.params[k] == p) { j = k; } } var anyConstant = false; for (var predK = 0; predK < cfg.predCount(c); predK += 1) { let pred = cfg.pred(c, predK); let pInsts = body.blocks[pred].insts; let pTerm = pInsts[pInsts.length - 1]; let sN = body.successorCount(pTerm); for (var sK = 0; sK < sN; sK += 1) { let sRec = body.successorRecord(pTerm, sK); if (body.extra[sRec] == c && body.op(body.extra[(sRec + 2) + j]) == IrOp.const_i32) { anyConstant = true; } } } if (!anyConstant) { return false; } // Every other use of a parameter sits under one of the targets, and // a target that would need parameters has no other predecessor. let users = buildUseLists(body, scratch); if (cond != p) { // The eqz belongs to the branch alone. for (var k = 0; k < users.count(cond); k += 1) { let u = users.at(cond, k); if (u != term) { return false; } } } var needT = false; var needF = false; for (let q in blk.params) { for (var k = 0; k < users.count(q); k += 1) { let u = users.at(q, k); if (u == term || u == cond) { continue; } let arm = armOf(cfg, t, f, body.instBlock[u]); if (arm == 0) { needT = true; } else if (arm == 1) { needF = true; } else { return false; } } } if (needT && !onlyPredIs(cfg, t, c)) { return false; } return !(needF && !onlyPredIs(cfg, f, c)); } /** * Which arm a use in block `bu` belongs to: 0 for the first target's * region, 1 for the second's, -1 for neither. One arm can lie inside * the other's region (the second is a loop header and the first sits * in its loop, say); a use dominated by both belongs to the inner arm, * whose parameter is the one that reaches it. */ function armOf(cfg: IrCfg, t: i32, f: i32, bu: i32): i32 { if (bu < 0) { return -1; } let inT = cfg.dominates(t, bu); let inF = cfg.dominates(f, bu); if (inT && inF) { return if (cfg.dominates(f, t)) 0 else 1; } if (inT) { return 0; } if (inF) { return 1; } return -1; } function onlyPredIs(cfg: IrCfg, b: i32, c: i32): boolean { for (var pK = 0; pK < cfg.predCount(b); pK += 1) { let p = cfg.pred(b, pK); if (p != c) { return false; } } return true; } function threadThrough(body: IrBody, cfg: IrCfg, c: i32, scratch: IrScratch): void { let blk = body.blocks[c]; let term = blk.insts[blk.insts.length - 1]; let p = conditionParam(body, c); let negated = conditionNegated(body, c); let targets = growable([ body.extra[body.successorRecord(term, 0)], body.extra[body.successorRecord(term, 1)], ]); let users = buildUseLists(body, scratch); let count = body.instCount(); var j = -1; for (var k = 0; k < blk.params.length; k += 1) { if (blk.params[k] == p) { j = k; } } // Which of the continuation's parameters each target's region uses, // and the parameter the target gets for each. let fwd = new Array(count); for (var i = 0; i < count; i += 1) { fwd.push(-1); } for (var side = 0; side < 2; side += 1) { let s = targets[side]; let used = new Array(); for (let q in blk.params) { var usedHere = false; for (var k = 0; k < users.count(q); k += 1) { let u = users.at(q, k); if (u == term || u == body.a[term]) { continue; } if (armOf(cfg, targets[0], targets[1], body.instBlock[u]) == side) { usedHere = true; } } if (usedHere) { used.push(q); } } if (used.length == 0) { continue; } for (var i = 0; i < count; i += 1) { fwd[i] = -1; } for (let q in used) { let id = body.opcode.length; body.opcode.push(IrOp.param as i32); body.typeId.push(body.typeId[q]); body.a.push(-1); body.b.push(-1); body.instBlock.push(s); body.blocks[s].params.push(id); fwd[q] = id; } // Uses in the target's region move to the target's parameter. let stack = growable([s]); while (stack.length > 0) { let b = stack.pop(); for (let inst in body.blocks[b].insts) { if (body.op(inst) != IrOp.nop) { body.rewriteValueOperands(inst, (v) => { if (v >= 0 && v < count && fwd[v] >= 0) { return fwd[v]; } return v; }); } } for (var childK = 0; childK < cfg.domChildCount(b); childK += 1) { let child = cfg.domChild(b, childK); stack.push(child); } } // The continuation's own edge passes its parameters through. appendArgs(body, term, side, used); } // Each predecessor edge with a constant flag goes straight to the // arm the flag selects, passing what that edge passes to the // continuation wherever the arm's record names a continuation // parameter. let edges = new Array(); let edgeIndex = new Array(); for (var predK = 0; predK < cfg.predCount(c); predK += 1) { let pred = cfg.pred(c, predK); let pInsts = body.blocks[pred].insts; let pTerm = pInsts[pInsts.length - 1]; var seen = false; for (let t in edges) { if (t == pTerm) { seen = true; } } if (seen) { continue; } let psN = body.successorCount(pTerm); for (var k = 0; k < psN; k += 1) { if (body.extra[body.successorRecord(pTerm, k)] == c) { edges.push(pTerm); edgeIndex.push(k); } } } for (var e = 0; e < edges.length; e += 1) { let pTerm = edges[e]; let k = edgeIndex[e]; let incoming = body.successorRecord(pTerm, k); if (body.extra[incoming] != c) { // A predecessor with both arms into the block is listed once per // arm; each (terminator, slot) pair is handled once. continue; } if (body.extra[incoming + 1] != blk.params.length) { throw new Error('thread: edge into b' + i32ToString(c) + ' passes ' + i32ToString(body.extra[incoming + 1]) + ' args for ' + i32ToString(blk.params.length) + ' params'); } let flag = body.extra[incoming + 2 + j]; if (body.op(flag) != IrOp.const_i32) { continue; } var taken = body.a[flag] != 0; if (negated) { taken = !taken; } let side = if (taken) 0 else 1; let armRecord = body.successorRecord(term, side); let armArgc = body.extra[armRecord + 1]; let newArgs = new Array(); var i = 0; while (i < armArgc) { let v = body.extra[armRecord + 2 + i]; var mapped = v; for (var q = 0; q < blk.params.length; q += 1) { if (blk.params[q] == v) { mapped = body.extra[incoming + 2 + q]; } } newArgs.push(mapped); i += 1; } retarget(body, pTerm, k, body.extra[armRecord], newArgs); } } /** Appends `values` to the arguments of successor `k` of `term`. */ function appendArgs(body: IrBody, term: i32, k: i32, values: GrowableArray): void { let s = body.successorRecord(term, k); let argc = body.extra[s + 1]; let args = new Array(argc); var i = 0; while (i < argc) { args.push(body.extra[s + 2 + i]); i += 1; } for (let v in values) { args.push(v); } retarget(body, term, k, body.extra[s], args); }