[llvm-dev] Register Allocation Graph Coloring algorithm and Others

[Leslie Zhai via llvm-dev]

Hi Vladimir,

Thanks for your kind and very detailed response!


在 2017年12月15日 12:40, Vladimir Makarov 写道:
>
>
> On 12/14/2017 10:18 PM, Leslie Zhai wrote:
>> 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
>>
> 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
>
> https://vmakarov.fedorapeople.org/vmakarov-submission-cgo2008.pdf
I am reading this paper at present :)


>
>
> 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.
I am debugging by printf to be familiar with LRA and IRA.


>
>>
>> * The papers by Briggs and Chaiten contradict[2] 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[3]?
>>
> 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[4] 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.
Thanks for your lesson! But are there some benchmarks when you used Tabu 
search as HEA, AntCol, etc. such as 
https://pbs.twimg.com/media/DRD-kxcUMAAxZec.jpg


>
>
> If you are interesting in RA algorithms and architectures, I'd 
> recommend Michael Matz article
>
> ftp://gcc.gnu.org/pub/gcc/summit/2003/Graph%20Coloring%20Register%20Allocation.pdf 
>
>
> as a start point.
Thanks! I am reading it.


>>
>> [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/