Register Allocation Graph Coloring algorithm and Others

[Leslie Zhai <lesliezhai at llvm dot org dot cn>]

Hi GCC and LLVM developers,

I am learning Register Allocation algorithms and I am clear that:

* Unlimited VirtReg (pseudo) -> limited or fixed or alias[1] PhysReg (hard)

* Memory (20 - 100 cycles) is expensive than Register (1 cycle), but it 
has to spill code when PhysReg is unavailable

* Folding spill code into instructions, handling register coallescing, 
splitting live ranges, doing rematerialization, doing shrink wrapping 
are harder than RegAlloc

* 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

* The papers by Briggs and Chaiten contradict[2] themselves when examine 
the text of the paper vs. the pseudocode provided?

* Why  interference graph is expensive to build[3]?

And I am practicing[4] to use HEA, developed by Dr. Rhydian Lewis, for 
LLVM firstly.


[1] https://reviews.llvm.org/D39712

[2] http://lists.llvm.org/pipermail/llvm-dev/2008-March/012940.html

[3] https://github.com/joaotavio/llvm-register-allocator

[4] https://github.com/xiangzhai/llvm/tree/avr/include/llvm/CodeGen/GCol

--
Regards,
Leslie Zhai - https://reviews.llvm.org/p/xiangzhai/