A combined algorithm for graph-coloring in register allocation

Martin Allen
Giridhar Kumaran
Tong Liu

Abstract

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. For typical register-set sizes, the extended algorithm can color graphs using significantly less time and spilling significantly smaller numbers of nodes to memory than does the Chaitin algorithm; these advantages become less pronounced, as register-set size decreases, and Chaitin can offer some small measure of better performance for very small sizes. Our algorithm has some interesting additional features. On the one hand, it can be extended to the general graph-coloring problem, outside of the particular application considered. In addition, it makes available adjustable parameters for producing more or less-optimal executables during compiler runs. 

@InProceedings{Allen02a,
  author = 	 {Martin Allen and Giridhar Kumaran and Tong Liu},
  title = 	 {A Combined Algorithm for Graph-Coloring in Register Allocation},
  booktitle =    {Proceedings of Color-02: Computational Symposium on Graph Coloring},
  year = 	 2002,
  address = 	 {Ithaca, NY}
}

Download [pdf]