Re: Register Allocation

[Peter Bergner <bergner@vnet.ibm.com>]

On Thu, 2005-11-17 at 11:53 -0500, Andrew MacLeod wrote:
> I have been contemplating building a GCC register allocator from scratch
> for some time.  To that end, I have put together a bit of a document
> given a high level overview of the various components I think would
> benefit GCC, and a rough description of how they would work together.  

First off, let me join the others in thanking you for submitting
your document for review.  I'm particularly glad to see you included
early instruction selection in your design, since I view the lack of
that as one of the major problems with the current register allocator.
Let me also say that I look forward to helping out anyway I can with
this project.

Peter


Live Range Disjointer [page(s) 6]:
    * As an FYI for others, this is also know in Chaitin's paper as
      "Right Number of Names" and also as "web analysis".

Instruction Selection [page(s) 7-8]:
    * Yes!  IMHO, the lack of early instruction selection is one of
      the major problems with the current allocator.
    * Note, better instruction scheduling could make good use
      of early instruction selection too.
    * Cost model (which includes register pressure info) for determining
      which native register class to use is good.

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.

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'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.

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.
    * I can also envision someone wanting to spill only a subset
      of the unallocated pseudos, so we should handle that scenario.
    * Now that I think of it, Vlad's idea seems vaguely familiar to
      Load/Store Range Analysis from PLDI93.  It's been so long since
      I read the paper, so am not 100% certain.  I don't recall hearing
      of anyone actually using Load/Store Range Analysis.

Spill Location Optimizer [page(s) 11]:
    * The IBM iSeries backend has this optimization.  During spilling,
      it inserts copies to/from spill pseudos (essentially like another
      register class) which represent the stores/loads from the stack.
      These spill pseudos can then be dead code eliminated, coalesced
      and colored (using an interference graph) just like any other
      normal pseudo.  Normal Chaitin coloring (using k = infinity) does
      a good job of minimizing the amount of stack space used for
      spilled pseudos.

Reg_Info [page(s) 16-17]:
    * I have some questions about how your register group mechanism
      will work in practice, but that can probably wait for a while.

Insn Annotations [page(s) 17-18]:
    * I like the idea of easy access to the register usage info
      provided by the insn annotations.  RTL isn't really setup
      for making that easy.
    * 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
      volatile registers being clobbered on a function call.  Also,
      for register classes with distinct subclasses (eg, GPRS and a
      subset of GPRS capable of acting as index registers), would you
      have separate counters?

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
      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.