Hi GCC and LLVM developers,
I am learning Register Allocation algorithms and I am clear that:
* Unlimited VirtReg (pseudo) -> limited or fixed or alias PhysReg (hard)
* Memory (20 - 100 cycles) is expensive than Register (1 cycle), but it has to spill code when PhysReg is unavailable
It might be much less if memory value is in L1 cache.
* Folding spill code into instructions, handling register coallescing, splitting live ranges, doing rematerialization, doing shrink wrapping are harder than RegAlloc
RegAlloc is in a wide sense includes all this tasks and more. For some architectures, other tasks like a right live range splitting might be even more important for generated code quality than just better graph coloring.
* LRA and IRA is default Passes in RA for GCC:
$ /opt/gcc-git/bin/gcc hello.c
DEBUG: ../../gcc/lra.c, lra_init_once, line 2441
DEBUG: ../../gcc/ira-build.c, ira_build, line 3409
* Greedy is default Pass for LLVM
But I have some questions, please give me some hint, thanks a lot!
* IRA is regional register allocator performing graph coloring on a top-down traversal of nested regions, is it Global? compares with Local LRA
IRA is a global RA. The description of its initial version can be found
LRA in some way is also global RA but it is a very simplified version of global RA (e.g. LRA does not use conflict graph and its coloring algoritm is closer to priority coloring). LRA does a lot of other very complicated things besides RA, for example instruction selection which is quite specific to GCC machine description. Usually code selection task is a separate pass in other compilers. Generally speaking LRA is more complicated, machine dependent and more buggy than IRA. But fortunately LRA is less complicated than its predecessor so called reload pass.
IRA and LRA names have a long history and they do not reflect correctly the current situation.
It would be possible to incorporate LRA tasks into IRA, but the final RA would be much slower, even more complicated and hard to maintain and the generated code would be not much better. So to improve RA maintainability, RA is divided on two parts solving a bit different tasks. This is a typical engineering approach.
* The papers by Briggs and Chaiten contradict themselves when examine the text of the paper vs. the pseudocode provided?
I don't examine Preston Briggs work so thoroughly. So I can not say that is true. Even so it is natural that there are discrepancy in pseudocode and its description especially for such size description.
For me Preston Briggs is famous for his introduction of optimistic coloring.
* Why interference graph is expensive to build?
That is because it might be N^2 algorithm. There are a lot of publications investigating building conflict graphs and its cost in RAs.
And I am practicing to use HEA, developed by Dr. Rhydian Lewis, for LLVM firstly.
When I just started to work on RAs very long ago I used about the same approach: a lot of tiny transformations directed by a cost function and using metaheuristics (I also used tabu search as HEA). Nothing good came out of this.
If you are interesting in RA algorithms and architectures, I'd recommend Michael Matz article
as a start point.