This is the mail archive of the
mailing list for the GCC project.
Re: Graph coloring for register allocation
- To: Brad Lucier <lucier at math dot purdue dot edu>
- Subject: Re: Graph coloring for register allocation
- From: Daniel Berlin <dberlin at redhat dot com>
- Date: Sun, 21 Jan 2001 20:55:40 -0500 (EST)
- cc: <dberlin at redhat dot com>, <matzmich at cs dot tu-berlin dot de>, <m dot hayes at elec dot canterbury dot ac dot nz>, <gcc at gcc dot gnu dot org>, <shebs at apple 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.
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
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
> Brad Lucier