You can spill in SSA form, they said. SSA-based spilling is amazing, they said. Linear time, they said. How do you handle phis? Apparently, that's an exercise lift to the reader. 🙄
@gfxstrand why would you do register allocation in ssa form?, I mean register allocation should be one of the last step, as it is very hardware dependent.
@ekg Why? Because, in SSA form, you can do competent spilling and RA in linear(ish) time, as opposed to graph coloring which is NP-hard. It's WAY faster and yields good results. Maybe a few extra moves but ALU is typically cheap.
Follow
@gfxstrand alu is certainly cheap. But why do you need ssa after register allocation?
@ekg The other big advantage to doing RA in SSA form is that it can allocate optimally with 100% predictable register pressure. This is what allows you to spill before RA, as opposed to spilling as a fall-back when graph coloring RA fails.
Getting optimal again involves occasionally shuffling values around to satisfy hardware constraints and any time you do this you end up with some moves. The more headspace you have in your register file the less likely you are to need shuffling.