Re: coalescing in graph coloring register allocator

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


Lal George wrote:
> Briggs, Click, and others have used a combination of techniques,
> however the order in which to apply the aggressive and conservative
> strategies is adhoc, and there is no guarantee against additional
> spills being introduced.
>
> Our algorithm, on the other hand, guarantees not to introduce spills,
> and is often much better than the conservative technique alone, and is
> very simple to implement. The fully pseudo-code for the algorithm is
> given in the article:


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.


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.


People doing static compilers probably do not care about the speed problem.


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.