Abstract:

Register allocation is a fundamental part of any optimizing compiler. Effectively managing the limited register resources of the constrained architectures commonly found in embedded systems is essential in order to maximize code quality. In this paper we deconstruct the register allocation problem into distinct components: coalescing, spilling, move insertion, and assignment. Using an optimal register allocation framework, we empirically evaluate the importance of each of the components, the impact of component integration, and the effectiveness of existing heuristics. We evaluate code quality both in terms of code performance and code size and consider four distinct instruction set architectures: ARM, Thumb, x86, and x86-64. The results of our investigation reveal general principles for register allocation design.

Published:

"Register Allocation Deconstructed"
David Ryan Koes and Seth Copen Goldstein
Proceedings of the 12th International Workshop on Software and Compilers for Embedded Systems (SCOPES'09) , Nice, France, April 2009.

Download:

Paper:

• Register Allocation Deconstructed (PDF)

BibTeX Entry:

@inproceedings{1543824,
 author = {Koes, David Ryan and Goldstein, Seth Copen},
 title = {Register allocation deconstructed},
 booktitle = {SCOPES '09: Proceedings of th 12th International Workshop on Software and Compilers for Embedded Systems},
 year = {2009},
 isbn = {978-1-60558-696-0},
 pages = {21--30},
 location = {Nice, France}},
 }