Re: coalescing in graph coloring register allocator

Lal George wrote:
>
> 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.


I probably have a different criterion for 'slow' than most.
Compile-time is run-time for me; allocations for large graphs (15000+
live ranges) need to happen in less than a second (well, more like in
a tenth of a second).


Also, a few leftover copies aren't worth trying to coalesce away.
I.e., the cost of removing the copies has to be paid back by improved
runtime. Since copies are fast (typically 1/2 clock or less) they
need to be executed a lot of times to be worth removing. Thus I don't
re-run the entire allocator to scrape away at the last few extra
copies.




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


Adds more complexity but doable (and weight to the live-range data
structure, which means more compile time).


How do you handle the case of needing to 'freeze' copies? Freezing
copies in low frequency blocks may not get you progress on the
low-degree list (may not make any particular live range lose all its
copies). Do you visit all low-degree-with-copy live ranges and sum
the expected costs of freezing all those copies? Then pick the least
cost live-range, freeze 'em all and put the winning live range on the
low-degree list?


I might try the above combination; my previous attempt just picked
"cheap" cqopies to freeze; I had to freeze a lot of copies before
I ended up getting some live range to lose all its copies.


Cliff


--
Cliff Click Compiler Designer and Researcher
cliffc at acm.org JavaSoft
(408) 863-3266 MS UCUP02-302
--

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