Re: Register Allocation Graph Coloring algorithm and Others

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

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/