Register Allocation Deconstructed

Tuesday April 21, 2009
Location: HH D-210
4:00 pm

David Koes
Carnegie Mellon University, School of Computer Science


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 talk I deconstruct the register allocation problem into distinct components: coalescing, spilling, move insertion, and assignment. An optimal register allocation framework is used to empirically evaluate the importance of each of the components, the impact of component integration, and the effectiveness of existing heuristics. Code quality is evaluated both in terms of code performance and code size and four distinct instruction set architectures are considered: ARM, Thumb, x86, and x86-64. The results of this investigation reveal general principles for register allocation design.


Dave doesn't think computers are fast enough or that compilers are good enough. After working as a compiler writer for Green Hills Software in dreary Santa Barbara, CA, he entered grad school in an attempt to remedy that situation. He is an Nth year graduate student in the computer science department with a thesis topic on the principled integration of register allocation and instruction selection in a progressive backend optimizer. His advisor is Seth Goldstein.

Back to the seminar page