Re: Register Allocation

[Andrew MacLeod <amacleod at redhat dot com>]

On Tue, 2005-11-22 at 13:26 -0600, Peter Bergner wrote:

> Register Coalescing [page(s) 8]:
>     * We will probably need some method for telling the coalescer
>       that a particular copy (or type of copy/copies) should either
>       be completely ignored (ie, do not coalesce it even if it looks
>       coalescable) or to think very hard before it does.  Examples of
>       copies we might want to skip would be copies inserted to satisfy
>       instruction constraints or some type of spilling/splitting code.
>       Examples of copies we might want to think about before blindly
>       coalescing might be pseudo - hard register copies, or copies
>       that would lead to an unacceptable increase in register 
>       constraints.

sure, this wouldn't be hard to do.  that could be flagged right in the
insn annotation of the copy.

> 
> Global Allocation [page(s) 10]:
>     * I'd like to keep the design flexible enough (if it's at all
>       possible) in case we want to attempt interprocedural register
>       allocation in the future.

I see no reason why that couldn't be done.

>     * I'd also like to allow Classic Chaitin and Briggs algorithms
>       which do iterative spilling (ie, color -> spill -> color ...).
>       This would be beneficial in that it gives us a well known
>       baseline to which all other algorithms/spilling heuristics can
>       be compared to.  It has the added benefit of making publishing
>       easier if your baseline allocator is already implemented.
> 

The very very first cut may well do this. It avoids writing much of
spiller and gets you going. Just spew out stores to spill :-)
Regardless, it would be trivial to do this after the fact when you
already have the pass written.


> Spiller [page(s) 10-11]:
>     * If we are doing a single pass Chaitin style allocation, then
>       I agree that the spiller would map all unallocated pseudos
>       into hardware registers.  However, if we are doing a multi
>       pass Chaitin style allocation, then the spiller should not
>       map the unallocated pseudos to hardware registers, but simply
>       insert the required spill code leaving the spilled pseudos as
>       pseudos.  The spiller should be flexible enough to do both.

That would be pretty straightforward. 

>     * I can also envision someone wanting to spill only a subset
>       of the unallocated pseudos, so we should handle that scenario.

You could easily do this by flagging pseudos you don't want spill code
generated for.  The spiller would simply ignore those so flagged. Or
vice versa.


> Insn Annotations [page(s) 17-18]:

>     * Encoding register pressure summary info as +1, -2 or 0 is fine,
>       but it is not a total solution.  In particular, it doesn't
>       handle register clobbers adequately.  An example would be the

True. we might need an additional value to represent that, or some other
mechanism. I figured we could work out those kinds of details when we
get closer to actually implementing it. The register pressure engine is
a bit further out than some of the rest of them, so I didn't put much
brainpower into it. It could evolve into something else easily. This
just seemed like a quick and dirty way to go.


>       for register classes with distinct subclasses (eg, GPRS and a
>       subset of GPRS capable of acting as index registers), would you
>       have separate counters?

I wasn't planning to track class subranges.  It might be an enhancement
someone may find interesting to try, and the intent is stated (perhaps
subtly) to make sure that adding additional register pressure values is
not difficult.  There is the expectation that at some point we may want
to track FPRs, GPRs and possibly all classes at the same time.  There is
no reason that couldn't be extended to include any particular subset you
found interesting.  This would have to be a separate value.
    
> 
> Spill Cost Engine [page(s) 26-29]:
>     * The register allocator should not be estimating the execution
>       frequency of a basic block as 10^nesting level.  That information
>       should be coming from the cfg which comes from profile data or
>       from a good static profile.  The problem with 10^loop nesting

Absolutely correct. That was simply thrown in as as simple starting
point.  I had forgotten that we now have static/dynamic CFG info always
available, so certainly we use those values rather than an ancient
mechanism that assumed nothing was available.  I will update the
document.

>       level is that we can overestimate the spill costs for some
>       pseudos.  For example:
>     	while (...) {
>     	  <use of "a">
>     	  if (...)
>     	    <use of "b">
>     	  else
>     	    <use of "b"
>     	}
>       In the code above, "b"'s spill cost will be twice that of "a",
>       when they really should have the same spill cost.

yes, using the CFG info they will be almost the same. B would have a
slightly higher instruction count, so if that is used to break ties, it
will be ever so slightly less favored, all other things being equal.

Thanks for the comments!

Andrew