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.
