Re: Graph coloring for register allocation?

["Zack Weinberg" <zackw at Stanford dot EDU>]

On Wed, Jan 24, 2001 at 08:21:11PM +0100, Michael Matz wrote:
> Hi,
> 
> On Wed, 24 Jan 2001, Daniel Berlin wrote:
> > > SMALL_REGISTER_CLASSES (and therefore all kinds of cruft all over the place).
> > > Inability to run the scheduler before register allocation on some machines.
> > 
> > Unless i'm mistaken, all the papers i've looked at(save one or two, i
> > think Chow and Hennessy didn't, it's hard to recall) require that
> > scheduling be run before register allocation.
> 
> There is still no good knowledge how the connection between RA and
> scheduling is. Either the papers develop a merged algorithm for RA and
> scheduling, or they run scheduling before and after RA. Exclusively
> running it before wouldn't make sense, as spill insertions would destroy
> (or change) dependence relationship and therefore scheduling assumbptions,
> and if there was no spill insertion, running scheduling after RA would
> make no difference. So, we would still have sched and sched2.

I've just been reading the Morgan book, which describes what I think
is a clever approach.  You do register coalescing and renaming, plus
"peephole" optimization (not the same thing as our peepholes), as you
come out of SSA form.  Then you walk the flow graph and calculate the
register pressure in all blocks; if it's bigger than the number of
architectural registers, you spill pseudos.  Then you do lazy code
motion to get the spills and reloads as far apart as possible.

Now you're ready to run the scheduler.  You've got a pretty good
guarantee that whatever it does, it won't crank up the register
pressure to the point where the allocator can't handle it.  The
register allocator still might have to spill things, but it's less
likely.  (But there's still a second scheduling pass after allocation
just in case.  It can be skipped if there were no additional spills.)

The problem I see, as with most things in Morgan, is that he assumes a
symmetric, RISCy target chip.  One big set of integer registers, one
big set of float registers.  I don't know how well the idea will map
to machines with odd register classes.

zw