bearophile wrote:
There are two groups of register allocation algorithms. The very fast ones, and the more precise ones. You even have perfect ones. Experience has shown that the difference in runtime performance between the precise algorithm and the perfect ones is often about 5% (this measured on LLVM(. This means that with LLVM you will probably never see a significant improvement of automatic register allocation, because it's as good as it gets, it's kind of a solved problem.
I've seen those papers on "precise" or even "perfect" register allocation. They're only precise within a certain set of assumptions the compiler makes about usage patterns. Those assumptions are, just that, assumptions. For example, assumptions are made about how many times this loop executes relative to that loop.
An asm programmer who knows his salt can do a better job, because he knows what the usage patterns are. Of course it's only rarely worth his while to do so, but nevertheless, calling such an algorithm "perfect" is misleading.
