Tuning a Priority-Based Register Allocator Using Adaptive Compilation

David M. Peixotto
Master’s Thesis, Rice University, 2008

Register allocation is a long studied optimization in compiler construction because it provides great opportunity for improving execution time. Adaptive compilation is a relatively new technique that uses repeated compilation and search to find effective parameters for compiler optimizations. We examine the priority-based graph-coloring register-allocation algorithm in the context of an adaptive compiler. The priority-based algorithm was selected because it is well known, but little information exists on how it should be tuned to produce good results or how it compares with competing algorithms.

We show that adaptive compilation can be used to improve the performance of a priority-based allocator. Aggressive tuning through adaptive compilation enables us to fairly compare against the Chaitin-Briggs algorithm for register allocation. We found the standard priority-based allocator was, on average, 16-9% worse than Chaitin-Briggs. Adaptive compilation enabled the priority-based allocator to close this performance gap and slightly outperform Chaitin-Briggs by an average of 1%.

pdf bibtex