Re: Graph coloring for register allocation

[Daniel Berlin <dberlin at redhat dot com>]

On Sun, 21 Jan 2001, Brad Lucier wrote:

> I hope you guys do a survey of the grungy requirements for
> register allocation on various machines before finalizing your plans.
> The "The output register conflicts with all input registers in
> alpha 21264 IEEE arithmetic" constraint really causes the current register
> allocator to stumble, and it would seem that grafting this
> requirement onto a beautiful graph-coloring register
> allocator algorithm after the fact may cause the new code to be just
> as complicated as the existing code in places.
Not really.
To say that it interferes, you simply add the approriate edges.

I also have a paper on graph coloring allocation for irregular
architectures that was submitted to PLDI '01, but isn't officially
published yet.

They actually specifically cite the alpha  (along with the m68k register
banks) as examples.

The way Briggs took care of this was with multigraphs. They (it's used in
Machine SUIF) take care of it through weighting, which is a much easier
way to do it.

The weighting structure is done completely seperate from all the graph
structures, and requires minimal modifications to 3 the iterated
register coalescing algorithm i'm working on right now (which will
eventually become an optimistic register coalescing allocator)

It's pretty simple to implement, which is why i figured we'd graft it on
later.



>
> Brad Lucier
>