Re: Register classes

[Michael Matz <matz at suse dot de>]

Hi,

On Wed, 18 Aug 2004, Daniel Berlin wrote:

> Just so nobody has any doubts, i have no current plans to do anything to
> the register allocator. I'm just trying to gather more information in
> case i decide to mount another future assault on it.
> 
> I should point out something from the below paper though:

As this paper didn't yet show up in citeseer (it seems), I would be 
thankful for this paper.

Note that new-ra does not really use register classes for the interference 
graph, but instead register sets.

Trivially colorable nodes are still trivially colorable also in new-ra,
_as long_ as they only require one register, so I'm not exactly sure what
you were speaking about in your first mail.

The problem with multi-reg pseudos is a tradeoff.  If you exactly count 
the necessary registers you make your nodes unnesessarily non-trivial.  
One example:  suppose R needs two _consecutive_ hardregs and that there 
are N colors.  This node is only trivially colorable if it has N/2-1 
neighbors (instead of N-2 which on would think at first).  The problem is 
the consecutivness.  If it has N-2 neighbors that we can be sure that 
there are two arbitrary hardregs available, but not two consecutive.
N/2-1 is a big hammer to ensure trivial colorability, which makes much too 
many nodes spilled than later necessary.

So, I choose another solution, by also popping it off the stack if it has 
<= N-2 neighbors.  But then I have to live and cope with the fact that 
this node might not get its two free consecutive hardregs.  And to make 
the effect of this less noticable (i.e. increasing the probability of it 
finding the two colors) there are some heuristics added.

Maybe you speak about this complexity.  But IMHO the coloring of the graph 
itself is still reasonable clean.  The other complexity is due to the way 
how it tries to avoid spilling must-get-a-color webs (which are of 
different classes, like short-living ones, or those with only one register 
possible and such).  Due to the above some simplified webs do not fall 
into the category, and some do.

> "One of our key insights is that coloring constraints on each
> interference-graph node should be expressed in terms of the set

Without having read the paper, at least this part I think is basically 
implemented in new-ra.  Sometimes we still use the regclasses for 
preferring some regs.  And of course when looking on the constraints of an 
insn you have to deal with regclasses.


Ciao,
Michael.