* Re: Graph coloring for register allocation
@ 2001-01-21 16:07 Brad Lucier
2001-01-21 17:56 ` Daniel Berlin
0 siblings, 1 reply; 3+ messages in thread
From: Brad Lucier @ 2001-01-21 16:07 UTC (permalink / raw)
To: dberlin, matzmich, m.hayes, gcc, shebs; +Cc: Brad Lucier
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.
Brad Lucier
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: Graph coloring for register allocation
2001-01-21 16:07 Graph coloring for register allocation Brad Lucier
@ 2001-01-21 17:56 ` Daniel Berlin
2001-01-21 17:59 ` Daniel Berlin
0 siblings, 1 reply; 3+ messages in thread
From: Daniel Berlin @ 2001-01-21 17:56 UTC (permalink / raw)
To: Brad Lucier; +Cc: dberlin, matzmich, m.hayes, gcc, shebs
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
>
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: Graph coloring for register allocation
2001-01-21 17:56 ` Daniel Berlin
@ 2001-01-21 17:59 ` Daniel Berlin
0 siblings, 0 replies; 3+ messages in thread
From: Daniel Berlin @ 2001-01-21 17:59 UTC (permalink / raw)
To: Daniel Berlin; +Cc: Brad Lucier, matzmich, m.hayes, gcc, shebs
>
> The weighting structure is done completely seperate from all the graph
> structures, and requires minimal modifications to 3 the iterated
^ stages of
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2001-01-21 17:59 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2001-01-21 16:07 Graph coloring for register allocation Brad Lucier
2001-01-21 17:56 ` Daniel Berlin
2001-01-21 17:59 ` Daniel Berlin
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).