Cranelift, Part 2: Compiler Efficiency, CFGs, and a Branch Peephole Optimizer
cfallin.org
cfallin.org
// The jump_if emits shuffle/spill/fill code before the
// conditional jump to conform to the L1 register/stack
// map. If the L1 map hasn't been created yet, we use
// the intersection of our map with the conservative
// live set (perhaps from the lexical scope) for L1
// in which case there's nothing to emit except the jump.
jump_if(value, L1);
// The fall-through block starts here.
// The join emits shuffle/spill/fill code to conform
// our current map (which is equal to the L1 map) to
// the L2 map. It then backpatches any existing refs
// to L2 and updates L2's address to point here. As with
// jump_if, if this is the first ref to L2 we just set
// our current map as L2's map and emit no code.
join(L2);
The next sweet spot seems to be a two-pass pipeline so you get a full forward and backward dataflow pass: your forward pass does SSA generation integrated with the forward dataflow analyses and the backward pass does machine code generation integrated with backward regalloc and dead code elimination. SSA with backward codegen/regalloc gives you an optimal coloring since the backward order for structured code matches the reverse postorder of the corresponding reducible CFG, and the greedy backward approach gives you decent splitting/coalescing for free. This is basically LuaJIT's approach but it can be extended beyond traces to reducible control flow if you replace the linear trace ordering with the dominator tree ordering. With two passes you should also be able to do something like Cliff Click's style of global code motion (as used in the HotSpot server compiler) with the early-schedule/late-schedule steps integrated into the two passes.
The main limitation of a pure two-pass approach is that you can't do precise SSA generation for loops at the same time you're doing your forward dataflow pass, so you have to be conservative. That blocks most LICM opportunities, so an extra micro-pass per loop is easy to justify, either an SSA pre-pass per loop or something like LuaJIT's loop peeling where you fully peel off the first iteration while identifying loop invariant variables before processing the loop a second time. Then LICM happens automatically via CSE since the peeled iteration dominates the loop body.
I wish that we (collectively) did a better job of reporting statistically significant performance comparisons, and in that light using "substantially" is a reminder to myself to think about whether it would be hard to go the extra mile and collect the data to actually report significance properly.