Oh man, block-argument-SSA makes so much more sense to me than Φ-SSA. That alone is going to change my life. Thank you, Max!
A lot of this process is the same as graph-coloring register allocation on SSA, of which I found an extensive explanation in Appel's textbook. I think it's maybe time for me to go back to it and do the exercises so I really understand it. The book unfortunately predates the linear allocator age.
Because block-argument is actually the “right way”. The phi-node is very un-natural.. in the same sort of way that pi should have been tau.
Also, notice the connection here between Phi nodes and Continuation Passing Style (CPS). It because obvious with the block-arg form because it’s just the same thing. Jumps to blocks are just calls that don’t return.
> In fact, you might even consider not allocating a register greedily. What might that look like? I have no idea.
One case I'm aware of: if your ISA supports arbitrary memory operands like x86, rarely-used variables can be operated-on entirely on the stack. Historically this was something ICC did better than GCC, though it became much less relevant with the shift to 64-bit bringing more registers.
Most x86 instructions only support one memory operand so you can’t completely avoid register allocation. It isn’t a full-on hardcore CISC like 68k or VAX.
x86 memory operands are also nice for binary size, my amateur compiler sometimes produces smaller objects than peers despite having no load-store elimination, all by greedily opting for memory operands during instruction selection; kinda amusing 'cause I'm now worrying my future optimization backend might actually cause a regression in size.
A lot of this process is the same as graph-coloring register allocation on SSA, of which I found an extensive explanation in Appel's textbook. I think it's maybe time for me to go back to it and do the exercises so I really understand it. The book unfortunately predates the linear allocator age.
The link to https://brrt-to-the-future.blogspot.com/2019/03/reverse-line..., which is a learner's introduction to the LuaJIT reverse linear scan allocator, also seems valuable.