A Generalized Algorithm for Graph-Coloring Register Allocation

Dr. Michael D. Smith

Harvard University

Friday, April 16, 2004
10:00am - SENSQ 5317

(Refreshments at 9:30am in SENSQ 5319)

Abstract

Graph-coloring register allocation is an elegant and extremely popular optimization for modern machines. However, as currently formulated, it does not directly handle two characteristics commonly found in commercial architectures. First, a single register name may appear in multiple register classes, where a class is a set of register names that are interchangeable in a particular role. Second, multiple architectural register names may be aliases for a single hardware register. We present a generalization of graph-coloring register allocation that directly handles these problematic characteristics while preserving the elegance and practicality of the traditional graph-coloring paradigm. Our generalization adapts easily to a new target machine, requiring only the sets of names in the register classes and a map of the register aliases. We also show that our generalization drops easily into a well-known graph-coloring allocator, is efficient at compile time, and produces high-quality code.

This research was done in collaboration with Norman Ramsey and Glenn Holloway at Harvard University.

Bio

Mike Smith is a Gordon McKay Professor of Computer Science and Electrical Engineering in the Division of Engineering and Applied Sciences at Harvard University. His research interests include dynamic optimization, machine-specific compilation, high-performance computer architecture, and practical applications of security. Mike is also Chief Scientist and co-founder of Liquid Machines, Inc., a provider of unique solutions for enterprise rights management. He is a member of the IEEE and ACM professional societies, and holds degrees from Stanford University, WPI, and Princeton University.