Evaluation of Briggs/Chaitin style register allocators

Important Note: This project does not require a formal background in compilers area. Both the papers are self explanatory and are simply written. We will understand the problem and the essence of their solutions through discussions. In case anyone is interested in evaluating the effectiveness of these techniques (see the project description) in a real compiler, we will be very happy to provide all the help; otherwise evaluation using randomly generated graphs is sufficient.

Sponsor	Prof. Santosh Pande
	santosh@cc.gatech.edu

Area	Systems

Project description

Register allocation for program variables is a very important problem in improving program performance. Registers allow holding program values and save memory traffic and heavily improve performance (remember directive in C/C++ to mark frequently used variables to be held in registers?)

Briggs, Cooper and others at Rice in 1994 came up with an interesting improvement over classical register allocation due to Chaitin. The way Chaitin's allocator works is that it first builds an interference graph of variables which simultaneously need registers. Then it performs graph coloring by first removing a node with least degree and by coloring it and then repeats this until registers are exhaustaed. Briggs improved this approach by putting nodes which could not be colored on a stack thereby defering some decisions. Their improvement essentially allows more cases of value interference graph to be colorable than Chaitin thereby generating less amount of spill code (spill code is due to uncolorable nodes which must reside in memory)

In this small assignment, you will first read the following two related papers and summarize the key contributions of both. Our goal would then be to measure how close are both of these algorithms to the optimal one (please note that optimal register allocation is NP-complete). It will be nice to evaluate this in a real compiler but to keep things simple we will randomly build interference graphs and attempt to color them for a given number of registers (typically 16 or 32 or so) by using these heuristic methods and also optimally using exhaustive graph coloring algorithm. The study should report what percentage of cases were indeed handled optimally by Briggs and Chaitin style allocators. This should serve as a first step in research in the register allocation area since we would know if there is indeed a gap between heuristic and optimal register allocation schemes which can be bridged by your work! This can be potentially published as a small study in SIGPLAN notices. As a further work, you can propose a new coloring algorithm comparing it with Briggs'.

Key references:

1. Preston Briggs, Keith Cooper and Linda Torczon, `Improvements to Graph Coloring Register Allocation', ACM Transactions on Programming
Languages and Systems, 16(3), May 1994, pp. 428-455.

2. G. Chaitin, `Register Allocation and Spilling via Graph Coloring', Proceedings of the 1982 Symposium on Compiler Construction, June 1982,
pp. 98-105.