Re: Graph coloring register allocation

Preston Briggs <preston@rice.edu>
Thu, 16 Nov 89 01:20:33 CST

          From comp.compilers

Related articles
Re: Graph coloring register allocation preston@rice.edu (Preston Briggs) (1989-11-16)
| List of all articles for this month |

Date: Thu, 16 Nov 89 01:20:33 CST
From: Preston Briggs <preston@rice.edu>
Newsgroups: comp.compilers
References: <1989Nov15.010209.11362@esegue.segue.boston.ma.us>
Organization: Rice University, Houston

rfg@ics.uci.edu writes:
>preston@rice.edu writes:
>>I don't know which is more effective. I suspect (with no evidence) that
>>Chow's method will be better on constrained machines (not many registers) and
>>Chaitin's better otherwise. Neither seems worthwhile without some global
>>optimization to provide grist for the mill.


>Chow's method is always at least as good as Chaitin's graph coloring
>(and sometimes better).


You need a little explanation here. I don't think anyone's published
a comparison, so what's your justification?


I spoke briefly with James Larus this summer, and he was curious too.
(see "Register Allocation for the Spur Lisp Compiler"
Larus and Hilfinger
Sigplan Compiler Construction Conference, 1986
  for a description of his version of Chow's allocator.)


Chow's claims in his paper are a little inaccurate. For example,
he claimed Chaitin didn't account for loop nesting level; but loop
nesting depth *is* accounted for. I expect Chow was referencing only
Chaitin's 1st paper, though his bibliography mentions the 2nd.


The priority-based coloring heuristic (just the coloring heuristic, not the
entire register allocation scheme) is less effective than Chaitin's coloring
heuristic (makes more spill code) according to Bernstein, et al. in Sigplan
89. Additionally, we've published an improved version of Chaitin's
heuristic (also Sigplan 89), so the gap may be larger. Chow's advantage is
live range splitting, and even that advantage has been cut down by the
"clean spilling" ideas of Berstein and friends.


The big win for Chaitin is the coalescing (subsumption) phase he uses just
before coloring (after computing the interference graph). Chaitin searches
for register-to-register copies where the source and destination do not
interfere and eliminates the copy, renaming one live range to another
globally. Chow's can't easily be extended since he computes his
interferences based on basic blocks. (two live ranges connected by a copy
will always interfere since they are live in the same basic block.)


Additionally, since Chow's interferences are computed only to the nearest
basic block, only one live range per block can be given a color. Chaitin's
interference graph is accurate to the (very low level) intermediate language
statement level; therefore, a single color (register) can be used for many
live ranges in a single block.


>It is likely that it will only be significantly
>better on machines *without* lots of registers.


Right. Chow will be better (maybe) when things are really tight.
*Significantly* is the question.


>If you have a zillion registers,
>you never spill with either method, so they're equal in that case.


Chaitin won't spill, but Chow will in some cases. A very long live range,
with very few references, will be split and some portions spilled.
Additionally, the lack of coalescing in Chow causes different code (extra
copies). Finally, the coarser interference graph and inferior coloring
heuristic produce worse colorings. Practically (less than a zillion
registers), this means that Chow will spill when Chaitin can still color.


On the other hand, the coarser interference graph is much smaller
which suggest that Chow's method will be quicker. However, Chaitin's
isn't too bad.


I also wonder if Chow's method works over bizzare register sets (overlapping
integer and floats, base registers, instructions returning register pairs,
paired double precision floats, ad naseum)? Chow mentions these as areas
for future research, but I've read no results. I'll state without proof
that Chaitin's method extends naturally to handle all of the above cases.


If anyone's feeling really energetic, implement both, with all the known
improvements, and try them out on a variety of machines. (and tell us what
happened!)


Preston Briggs





Post a followup to this message

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