Re: Register Allocation via Hiearachical Graph Coloring

koes@cmu.edu (David Koes)
2 Oct 2004 01:14:50 -0400

          From comp.compilers
Related articles
Register Allocation via Hiearachical Graph Coloring sapna@cse.iitb.ac.in (Sapna Jain) (2004-09-21)
Re: Register Allocation via Hiearachical Graph Coloring richard@imagecraft.com (Richard F. Man) (2004-09-24)
Re: Register Allocation via Hiearachical Graph Coloring jle@ural.owlnet.rice.edu (2004-09-24)
Re: Register Allocation via Hiearachical Graph Coloring koes@cmu.edu (2004-10-02)
| List of all articles for this month |
From: koes@cmu.edu (David Koes)
Newsgroups: comp.compilers
Date: 2 Oct 2004 01:14:50 -0400
Organization: http://groups.google.com
References: 04-09-129 04-09-135
Keywords: registers
Posted-Date: 02 Oct 2004 01:14:50 EDT

You may want to check out this master's thesis:


@misc{ wu96register,
    author = {Q. Wu},
    title = "Register Allocation via Hierarchical Graph Coloring",
    text = "Qunyan Wu. Register Allocation via Hierarchical Graph
Coloring.
Masters thesis, Michigan Technological University, 1996.",
    year = "1996",
    url = "citeseer.nj.nec.com/wu96register.html",
  }


An excerpt from the abstract:
This thesis examines the effectiveness of Callahan and Koblenz's
algorithm and shows that when register pressure is high,
Callahan and Koblenz's method generates worse code than Briggs'
method -- the generally accepted method of graph coloring register
allocation. The performance degradation of Callahan and Koblenz's
method
is due to reserving registers in the graph coloring process. Also,
by performing register allocation hierarchically, compensation move
and jump
instructions are required to ensure the correctness of program
semantics. Furthermore, the experimental results suggest that without
considering
the degree of conflict in the spill cost, more values can be spilled
than necessary.
---


-Dave

Post a followup to this message

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