Re: coalescing in graph coloring register allocator

Clifford Click <cliff.click@Eng.Sun.COM> writes:
> jp wrote:
> > I'm studying the graph coloring register allocator. I'm wondering
> > which coalescing technique out of "aggressive coalescing" by Chaitin
> > and "conservative coalescing" by Briggs is preferred in general
> > environments that suffer from many copies generated by aggressive
> > optimizations like SSA as well as generated at normal compilation
> > stages.


We examined this problem extensively in the SML/NJ compiler that uses
an intermediate form that has several parallels to SSA.


The Chaitin aggressive coalescing technique may introduce spills in a
graph that would otherwise have been colored normally. This is
obviously bad as it replaces cheap copies with expensive spills.


The Briggs conservative technique alone is not powerful enough as it
may leave behind many copies that could be safely coalesced, but
gurantees not to introduce spills.


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


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:


@Article{george-appel-toplas96,
author={George, Lal and Appel, Andrew W.},
key={GA96},
title={Iterated Register Coalescing},
journal={{ACM} transacations on programming languages and systems.},
volume={18},
number={3},
pages={300-324},
month={May},
year={1996}
}
--

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