Re: Graph coloring for register allocation?

[Daniel Berlin <dberlin at redhat dot com>]

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

Also, a few compilers i know of use more than one type of ssa form
(pruned, minimal, etc), because it's better to have duplicates adn whatnot
when doing certain ssa optimizations, like code motion, etc.

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

Yeah, that's a problem.
One upside of the new allocator is that we can now leave around as many
copies/moves as we want, and we know the allocatgor will clean them up.

This is very nice for some optimizations, where you generate a lot of
copies, and then would waste time cleaning them up.

>
> zw
>