A Combined Algorithm for Graph-coloring in Register Allocation

Martin Allen, Giridhar Kumaran, and Tong Liu

To appear at Computational Symposium on Graph Coloring and Generalizations (COLOR02), Ithaca, NY, 7-8 September 2002


Our research involves improved algorithms for graph-coloring, in the context of register allocation. We extend the usual algorithm, first proposed by Chaitin, adding two further routines, one a form of semi-randomized greedy allocation of colors, and the second using local search with random restarts, a method developed in the context of logical satisfiability problems. While time comparisons are hard to make at this point, the extended algorithm can color graphs while spilling significantly less numbers of nodes to memory than does the Chaitin algorithm. Such an algorithm can be extended to the general graph-coloring problem, outside of the particular application considered. In addition, the resulting algorithm makes available adjustable parameters for producing more- or less-optimal executables during compiler runs.

Server START Conference Manager
Update Time 23 Jul 2002 at 13:35:57
Maintainer trick@cmu.edu.
Start Conference Manager
Conference Systems