Linear scan register allocation on SSA
bernsteinbear.com37 points by surprisetalk 4 days ago
37 points by surprisetalk 4 days ago
> 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.
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.
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.
Another great overview of Go compiler's register allocation: https://developers.redhat.com/articles/2024/09/24/go-compile...