Re: Register Allocation via Hiearachical Graph Coloring

Sapna Jain <sapna@cse.iitb.ac.in> 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.


    Regards, jason.

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