|Register Allocation via Hiearachical Graph Coloring firstname.lastname@example.org (Sapna Jain) (2004-09-21)|
|Re: Register Allocation via Hiearachical Graph Coloring email@example.com (Richard F. Man) (2004-09-24)|
|Re: Register Allocation via Hiearachical Graph Coloring firstname.lastname@example.org (2004-09-24)|
|Re: Register Allocation via Hiearachical Graph Coloring email@example.com (2004-10-02)|
|From:||firstname.lastname@example.org (Jason Lee Eckhardt)|
|Date:||24 Sep 2004 00:25:23 -0400|
|Organization:||Rice University, Houston, TX|
|Posted-Date:||24 Sep 2004 00:25:23 EDT|
Sapna Jain <email@example.com> wrote:
>I have read David Callahan & Brian Koblenz's paper of "Register
>Allacation via hierarchical Graph Coloring, & find that it works
>better in all condition than Chaitin's & Brigg's method.
Interestingly, a colleague at Rice and I (with substantial
input from Brian Koblenz) are in the process of performing an
in-depth analysis and comparison of these two techniques. While
Chaitin-Briggs has been extensively studied, and numerous empirical
results presented, no such study has been published for Callahan-Koblenz.
I find the latter part of your statement above interesting-- are
you saying 1) you've implemented CK; and 2) you've seen that it
outperforms CB on every possible benchmark you've tried? While
I won't comment on our preliminary results, your statement seems
suspect simply due to the heuristic nature of most global register
allocation techniques. I'd like to know more about your implementation,
and your benchmarks.
>Do you know any compiler which uses that technique, or have u worked
>on any compiler using the technique.
Other than the author's compiler (Cray, formerly Tera), I'm not
aware of any current _commercial_ compiler using it. This is
probably due in large part to a lack of empirical data, and a
lack of deep understanding in the community about the behavior of CK.
However, we have implemented it in a research compiler here at Rice.
>And if U may tell me some pitfalls of the technique, and some other
>register allocation method better than it, also the condition in which
>that method will be better.
Most register allocation techniques are heuristics. One will rarely
_always_ be the best. One of the primary contributions of CK is
to incorporate program structure into the allocation process. There
are numerous other articles that attempt to do the same-- some with
reasonable success. See, for example, Bergner, et al's paper in
PLDI'97, or Lueh's "Fusion-based" register allocator paper in
TOPLAS (in 2000) and go from there. Try keywords such as "live range
splitting", etc. in your favorite search engine.
Finally, it is our intention to eventually publish data that may give
insight into CK including strengths, weaknesses, and pitfalls.
Return to the
Search the comp.compilers archives again.