/** * Loop-invariant code motion (docs/design/optimization-pipeline.md * §LICM): an instruction inside a loop whose operands are all defined * outside it computes the same value every iteration, so it moves to * just before the loop, into the block that immediately dominates the * loop header. * * Only pure instructions that cannot trap move freely: arithmetic, * tests, immutable global reads, and loads through a receiver whose * type is non-null (an immutable field, an array length, a fat * pointer's two fields). A moved instruction may then run on a path * that never enters the loop, which is harmless for exactly these. * Allocations stay, since one object per iteration and one object * shared by all iterations are different programs. * * A pure instruction that can trap (a cast, a load through a nullable * receiver) moves only out of the loop header, only when nothing kept * ahead of it in the header has an effect, and only when the * destination block jumps straight to the header: then the header * runs on every entry to the loop, so the instruction would have run, * and trapped or not, before anything the loop does. This is the cast of * an interface-typed array's instance in `while (i < xs.length)`, * which every inlined accessor repeats. * * The dominating block is the right destination without building a * preheader: every value defined outside the loop that a use in the * loop can see dominates the header, so it lies on the header's * dominator chain and is available at the end of the header's * immediate dominator. * * Loops are the natural loops of the back edges (an edge to a block * that dominates its source). The pass repeats while something moved, * so an instruction hoisted out of an inner loop can leave the outer * one on the next pass. * * The client this exists for: a loop over an interface-typed array, * whose fat-pointer unpack and vtable-slot load happen once instead * of every iteration (array-mutability.md, "Required optimizations"). * * Determinism: blocks in reverse postorder, instructions in block * order. */ import { IrBody, IrOp, IrRefField, IrRefGlobal, isBinaryNumericOp, isUnaryNumericOp, IrScratch } from './ir.zena'; import { IrCfg } from './cfg.zena'; import { ValTypeRef } from '../wasm.zena'; /** Runs the pass; returns the number of instructions moved. */ export function runLicm(body: IrBody, scratch: IrScratch): i32 { scratch.enter(); let result = runLicmOn(body, scratch); scratch.exit(); return result; } function runLicmOn(body: IrBody, scratch: IrScratch): i32 { var total = 0; var pass = 0; while (pass < 3) { let moved = hoistOnce(body, scratch); total += moved; if (moved == 0) { break; } pass += 1; } return total; } function hoistOnce(body: IrBody, scratch: IrScratch): i32 { scratch.enter(); let result = hoistOnceOn(body, scratch); scratch.exit(); return result; } function hoistOnceOn(body: IrBody, scratch: IrScratch): i32 { let cfg = new IrCfg(body, scratch); let nb = body.blocks.length; let dominates = (a: i32, b: i32): boolean => { var cur = b; while (cur >= 0) { if (cur == a) { return true; } if (cur == 0) { return false; } cur = cfg.idom[cur]; } return false; }; var moved = 0; // Headers in reverse postorder; each header's loop is the union of // its back edges' natural loops. for (let h in cfg.rpo) { let inLoop = new Array(nb); for (var i = 0; i < nb; i += 1) { inLoop.push(false); } var isHeader = false; for (var pK = 0; pK < cfg.predCount(h); pK += 1) { let p = cfg.pred(h, pK); if (!cfg.isReachable(p) || !dominates(h, p)) { continue; } isHeader = true; // Everything that reaches the back edge's source without // passing the header is in the loop. inLoop[h] = true; let work = new Array(); if (!inLoop[p]) { inLoop[p] = true; work.push(p); } while (work.length > 0) { let b = work.pop(); for (var qK = 0; qK < cfg.predCount(b); qK += 1) { let q = cfg.pred(b, qK); if (cfg.isReachable(q) && !inLoop[q]) { inLoop[q] = true; work.push(q); } } } } if (!isHeader || h == 0) { continue; } let dest = cfg.idom[h]; if (dest < 0) { continue; } let destBlk = body.blocks[dest]; // A trap-capable instruction may move only when the destination // falls straight into the header: with blocks in between (a null // check that leaves early, say) the instruction would run on a // path that never reaches the loop. var straightIn = destBlk.insts.length > 0; if (straightIn) { let sN = body.successorCount(destBlk.insts[destBlk.insts.length - 1]); for (var sK = 0; sK < sN; sK += 1) { let sRec = body.successorRecord(destBlk.insts[destBlk.insts.length - 1], sK); if (body.extra[sRec] != h) { straightIn = false; } } } let outside = (v: i32): boolean => { if (v < 0) { return true; } let b = body.instBlock[v]; return b < 0 || !inLoop[b]; }; let operands = new Array(); // Two sweeps over the loop's blocks, so a chain of invariant // instructions moves together even when a later block defines // what an earlier one (in reverse postorder) uses. var sweep = 0; while (sweep < 2) { for (let b in cfg.rpo) { if (!inLoop[b]) { continue; } let blk = body.blocks[b]; let kept = new Array(); // In the header, a trap-capable candidate may move while every // instruction kept ahead of it is pure. var headerPure = b == h && straightIn; for (let inst in blk.insts) { if (body.op(inst) == IrOp.nop) { kept.push(inst); continue; } let pure = hoistable(body, inst); let trapping = !pure && headerPure && trapHoistable(body, inst); if (!pure && !trapping) { kept.push(inst); headerPure = false; continue; } while (operands.length > 0) { operands.pop(); } body.appendValueOperands(inst, operands); var invariant = true; for (let o in operands) { if (!outside(o)) { invariant = false; } } if (!invariant) { kept.push(inst); if (trapping) { headerPure = false; } continue; } // Move: out of this block, in before the destination's // terminator. let term = destBlk.insts.pop(); destBlk.insts.push(inst); destBlk.insts.push(term); body.instBlock[inst] = dest; moved += 1; } if (kept.length != blk.insts.length) { while (blk.insts.length > 0) { blk.insts.pop(); } for (let k in kept) { blk.insts.push(k); } } } sweep += 1; } } return moved; } /** Pure, trap-free, and not an allocation: safe to run speculatively. */ function hoistable(body: IrBody, inst: i32): boolean { if (body.typeId[inst] < 0) { return false; } let op = body.op(inst); if (op == IrOp.const_i32 || op == IrOp.const_i64 || op == IrOp.const_f32 || op == IrOp.const_f64) { return true; } if (isBinaryNumericOp(op)) { return op != IrOp.i32_div_s && op != IrOp.i32_div_u && op != IrOp.i32_rem_s && op != IrOp.i32_rem_u && op != IrOp.i64_div_s && op != IrOp.i64_div_u && op != IrOp.i64_rem_s && op != IrOp.i64_rem_u; } if (isUnaryNumericOp(op)) { return true; } if (op == IrOp.ref_null || op == IrOp.ref_is_null || op == IrOp.ref_test || op == IrOp.ref_eq || op == IrOp.ref_func || op == IrOp.extern_convert_any || op == IrOp.any_convert_extern) { return true; } if (op == IrOp.global_get) { let r = body.refTable[body.b[inst]]; if (r is IrRefGlobal) { return !r.target.isMutable; } return false; } if (op == IrOp.struct_get || op == IrOp.array_len || op == IrOp.iface_vtable || op == IrOp.iface_instance) { let receiver = body.a[inst]; if (receiver < 0) { return false; } let t = body.resultType(receiver); if (t == null || !(t is ValTypeRef)) { return false; } if (op == IrOp.struct_get) { return fieldIsImmutable(body, inst); } return true; } return false; } /** * Pure but able to trap: a cast, a null assertion, or a load of an * immutable field, an array length or a fat pointer's fields through * a nullable receiver. Movable from a loop header alone. */ function trapHoistable(body: IrBody, inst: i32): boolean { if (body.typeId[inst] < 0) { return false; } let op = body.op(inst); if (op == IrOp.ref_cast || op == IrOp.ref_as_non_null) { return true; } if (op == IrOp.array_len || op == IrOp.iface_vtable || op == IrOp.iface_instance) { return body.a[inst] >= 0; } if (op == IrOp.struct_get) { return body.a[inst] >= 0 && fieldIsImmutable(body, inst); } return false; } function fieldIsImmutable(body: IrBody, inst: i32): boolean { let r = body.refTable[body.b[inst]]; if (r is IrRefField) { let idx = r.owner.fieldIndexByName(r.fieldName); return idx >= 0 && !r.owner.fields[idx].isMutable; } return false; }