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

[Vladimir Makarov via llvm-dev]

On 12/18/2017 07:07 PM, Michael Clark wrote:
> Hi Leslie,
>
> I suggest adding these 3 papers to your reading list.
>
> 	Register allocation for programs in SSA-form
> 	Sebastian Hack, Daniel Grund, and Gerhard Goos
> 	http://www.rw.cdl.uni-saarland.de/~grund/papers/cc06-ra_ssa.pdf
>
> 	Simple and Efficient Construction of Static Single Assignment Form
> 	Matthias Braun , Sebastian Buchwald , Sebastian Hack , Roland Leißa , Christoph Mallon , and Andreas Zwinkau
> 	https://www.info.uni-karlsruhe.de/uploads/publikationen/braun13cc.pdf
>
> 	Optimal register allocation for SSA-form programs in polynomial time
> 	Sebastian Hack, Gerhard Goos
> 	http://web.cs.ucla.edu/~palsberg/course/cs232/papers/HackGoos-ipl06.pdf
>
> A lot of the earlier literature regarding the register allocation problem describes the general graph colouring problem as NP-complete, however previous research in Register Allocation has been in the context of programs that were not in SSA form. i.e. the Chaitin-Briggs paper states that register allocation is NP-complete and proposes an iterative algorithm.
>
>
I am sceptical about SSA-register allocators for high quality code 
generation.  But I should acknowledge although I tried a lot of RA 
algorithms I never tried SSA one.

One task of RA is to deal with moves but when you are destroying SSA you 
are creating moves or swaps.  Of course there are optimizations to 
decrease its number when you are going out of SSA.  But IMHO a good RA 
should see all moves created before or during own work.

As I already wrote coloring is just one out of many task of RA.  All 
these tasks in a good RA should be solved in cooperation. Optimistic 
coloring is good and fast enough (although building a conflict graph for 
it takes a lot of time).  I think better results can be obtained by 
improving other tasks than by improving optimistic coloring.

For example, nobody mentioned irregular file architectures (with 
subregisters and register subclasses) like x86/x86-64.  Even regular 
file architectures with caller/callee saved hard registers have 
irregularity because it creates register subclasses, e.g. class of saved 
general registers is a subclass of the overall general register class.  
Usually hard registers are present in IR and if some pseudos conflict 
with the hard registers, it also create a lot (intersected) subclasses.

Taking such irregularity, e.g. in coloring criteria based on Kempe's 
heuristic, can improve the final RA significantly (as I remember GCC 
generated code for SPECInt2000 even on ppc64 with mostly regular 
register file was improved by 1% by taking such subclasses into account 
during coloring). A classical article about this 
https://www.researchgate.net/publication/2440424_Graph-Coloring_Register_Allocation_for_Irregular_Architectures 
could be a start point for such implementation.