4 ms·

In a register-allocating one-pass backend you by necessity decide the register/stack map for a given label the first time you emit a branch that targets it. As

In a register-allocating one-pass backend you by necessity decide the register/stack map for a given label the first time you emit a branch that targets it. As a result you never have a problem with critical edges for two-way branches because the fall-through cannot be targeted directly by other branches; you always have a (possibly trivial) block for the fall-through edge with only one predecessor. Example: // 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); Multi-way branches (typically from switch jump tables) with critical edges are much rarer and can be handled in a one-pass backend by splitting on demand (by inserting jump pads) when a multi-way branch target has already been referenced and had its map assigned. That's rare enough in practice that doing something more global to decide where to place the splits probably isn't worth it in a one-pass backend.

cfallin 6y ago
Integrating regalloc with a more streaming approach is something we may want to look at in the future in our backend -- for now we have a more conventional regalloc that extracts live ranges and either does a backtracking allocation or linear scan. That happens between lowering, which is where empty crit-edge blocks are created, and final emission, where the branch peepholing happens and empty blocks disappear, so the blocks exist during regalloc if needed. Anyway, there's an interesting design-space here!
- psykotic 6y ago
  Yeah, I'm happy to see more experimentation in the lightweight compiler space! My one-pass pipeline does forward greedy regalloc integrated with the approach I outlined in my post. 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.

cfallin 6y ago

Integrating regalloc with a more streaming approach is something we may want to look at in the future in our backend -- for now we have a more conventional regalloc that extracts live ranges and either does a backtracking allocation or linear scan. That happens between lowering, which is where empty crit-edge blocks are created, and final emission, where the branch peepholing happens and empty blocks disappear, so the blocks exist during regalloc if needed. Anyway, there's an interesting design-space here!

psykotic 6y ago
Yeah, I'm happy to see more experimentation in the lightweight compiler space! My one-pass pipeline does forward greedy regalloc integrated with the approach I outlined in my post. 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.