Chow and Hennessy vs. Chaitin-Briggs Register Allocation: Using Adaptive Compilation to Fairly Compare Algorithms

Keith D. Cooper, Timothy J. Harvey, and David M. Peixotto
SMART’08 Workshop, 2008

When we set out to compare the performance of two algo- rithms against each other, the quality of the comparison is wholly de- pendent on the quality of the two implementations. If an algorithm is particularly difficult to implement correctly, if it is poorly understood or documented, or if its performance is highly variable based on any number of idiosyncratic settings, a comparison against another algorithm should normally be suspect.

In our case, we wanted to compare a Chaitin-Briggs graph-coloring regis- ter allocator against a Chow and Hennessy priority-based allocator, but it seemed impossible to get a fair comparison. The Chaitin-Briggs allo- cator is relatively well understood. It has been studied extensively. It has few parameters to guide its behavior. In contrast, Chow’s allocator, although often cited as a viable competitor to the graph-coloring allocator, is none of these. It has been implemented very few times. Its presence in the literature is more historic than an- alytic. Worst of all, it not only includes a number of implementation decisions that individually affect the quality of code, but these decisions interact unpredictably.

Adaptivity suggests a solution to this problem. By allowing a search technique to optimize an algorithm’s performance, we can make definitive statements comparing two algorithms.

In this paper, we present an implementation of a priority-based register allocator as described by Chow and Hennessy. We show how to imple- ment the allocator in an adaptive framework, and we show that the code produced consistently achieves the performance of a Chaitin-Briggs graph-coloring register allocator.

The Chaitin-Briggs algorithm has received so much attention in the liter- ature that we felt it would be fair to use a non-adaptive implementation as a baseline to compare against.

Our results show that the two algorithms give similar performance, but only when we use an adaptive search algorithm for the Chow allocator. We believe that this is the first time these two algorithms have been fairly tested side-by-side, and we argue that adaptivity is an effective tool for experimental computer science.

pdf bibtex