Re: coalescing in graph coloring register allocator

Lal George <george@research.bell-labs.com>
16 Aug 1998 22:41:39 -0400

          From comp.compilers

Related articles
coalescing in graph coloring register allocator jp@altair.snu.ac.kr (jp) (1998-08-03)
Re: coalescing in graph coloring register allocator max@gac.edu (Max Hailperin) (1998-08-04)
Re: coalescing in graph coloring register allocator cliff.click@Eng.Sun.COM (Clifford Click) (1998-08-05)
Re: coalescing in graph coloring register allocator george@research.bell-labs.com (Lal George) (1998-08-10)
Re: coalescing in graph coloring register allocator cliff.click@Eng.Sun.COM (Clifford Click) (1998-08-13)
Re: coalescing in graph coloring register allocator george@research.bell-labs.com (Lal George) (1998-08-16)
Re: coalescing in graph coloring register allocator cliff.click@Eng.Sun.COM (Clifford Click) (1998-08-19)
| List of all articles for this month |

From: Lal George <george@research.bell-labs.com>
Newsgroups: comp.compilers
Date: 16 Aug 1998 22:41:39 -0400
Organization: Bell Laboratories, Lucent Technologies
References: 98-08-021 98-08-037 98-08-074 98-08-091
Keywords: registers, optimize

Clifford Click <cliff.click@Eng.Sun.COM> writes:


> > > My compiler is a run-time compiler for Java and has strict
> > > compile-time constraints. I'm running 1 round of agressive
> > > coalescing, and 1 round of conservative coalescing each time I split
> > > live ranges.
>
> Let me add that I tried the George/Lal/Appel approach and found it was
> too slow for my purposes. I couldn't dream up a way to effeciently
> flip-flop between coalescing copies related to live ranges that just
> recently become of low degree and Simplifying.


I don't believe the algorithm is slow, especially when you consider
that the adhoc approach may require re-running the entire graph
coloring algorithm one last time in order to invoke one or the other
coalescing strategy.


> That is, after you Simplify some low degree live range, what is the
> set of copies that should be reinspected to see if they can be
> coalesced? Inspecting them all is quite slow.


A node is move-related if it is involved in a copy. Every node has a
list of moves that it is move-related to. When the degree of a node (V
say) transitions from K to K-1, all the moves associated with active
neighbors of V are put onto the move worklist for consideration.


All moves start out in the move worklist. If one does simplification
first (highly recommended) then one could make use of the fact that
all the moves are already in the move worklist to avoid looking at
active neighbors. We don't do this, but I think it may help.


By active neighbor, I mean a node that has not been removed from the
graph (yet).
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.