Re: coalescing in graph coloring register allocator

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

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