Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

GCC and LLVM do not retain SSA form by the time register allocation happens (they both convert to a non-SSA low-level IR before then).

It's also worth pointing out that "optimal" in theory doesn't necessarily correspond to optimal in practice. The hard problem of register allocation isn't coloring the interference graph (since there's not enough registers most of the time), it's deciding how best to spill (or split live ranges, or insert copies, or rematerialize, or ...) the excess registers. Plus, real-world architectures also have issues like requiring specific physical registers for certain instructions and subregister aliasing which are hard to model.

In practice, the most important criterion tends to be to avoid spilling inside loops. This means that rather simple heuristics are generally sufficient to optimally achieve that criterion, and in those cases, excessive spilling outside the loops isn't really going to show up in performance numbers. Thus heuristics are close enough to optimal that it's not worth the compiler time or maintenance to achieve optimality.




Yes, the fun in compilers: Even if every phase and every optimization actually produces optimal results, the combination is probably not optimal.

One deep problem is that there is no good optimization goal. Today's CPUs are too complex and unpredictable performance-wise.

Another problem is: Register pressure is one of the most important things to minimize, but how can the phases before register allocation do that? They use a surrogate, like virtual registers, and thus become heuristics even if they solve their theoretical problem optimally.




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: