Re: coalescing in graph coloring register allocator

jp <jp@altair.snu.ac.kr> writes:


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


In his thesis work[1], Briggs actually used agressive coalescing, just
like Chaitin, for the normal case of pre-existing copies, such as
those from SSA form. He used his conservative coalsescing only for
the special case of eliminating the extra copies his allocator
introduced in order to split live ranges. If he had used aggressive
coalescing there as well, it would have immediately undone all the
splitting.


Later George and Appel[2] eliminated agressive coalescing entirely
(because it was overconstraining coloring in their compiler), and
instead used exclusively conservative coalescing. (However, they used
a different "conservativeness" test for copies involving precolored
nodes.) What they discovered was that they were left with too many
copies, if they did all the coalescing before the graph simplification
started, a la Chaitin and Briggs. They showed that by intermixing
conservative coalescing with simplification, however, they were able
to get much better results -- some coalesces which weren't initially
conservative became conservative after some simplification was done.


This doesn't really answer your question, it just tells you that your
statement of the question was a bit oversimplified.


[1] Briggs, P., 1992.
        Register allocation via graph coloring.
        Tech. Rep. CRPC-TR92218
        Center for Research on Parallel Computation, Rice University.
        Ph.D. Dissertation.


[2] George, L. and Appel, A. W., 1996.
        Iterated register coalescing.
        ACM Trans. Program. Lang. Syst. 18, 3 (May), 300-324.


  -Max Hailperin
    Associate Professor of Computer Science
    Gustavus Adolphus College
    800 W. College Ave.
    St. Peter, MN 56082
    USA
    http://www.gustavus.edu/~max/
--

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