Towards a More Principled Compiler

Tuesday April 11, 2006
Hamerschlag Hall D-210
4:30 pm

Dave Koes
Carnegie Mellon University

Although in the past, the effect of compiler optimizations on performance was overshadowed by exponential increases in clock frequencies, as processor speeds stagnate and computer architects look for new ways to buy performance with their growing transistor budget, compiler optimizations will play an increasingly important role in future processor performance gains. Existing compiler optimizations are typically heuristic-driven and lack a detailed model of the target architecture. More principled optimization approaches are necessary in order to fully exploit the performance potential of modern architectures. I will present one such principled approach to the fundamental compiler optimization of register allocation.

I present a global progressive register allocator (GPRA). GPRA represents the register allocation problem with an explicit and expressive model that is based on multi-commodity network flow. This formulation can be solved quickly using simple heuristics and progressively using the theory of Lagrangian relaxation. The advantage of a progressive solver is that, as more time is allowed for compilation, not only is a better solution found, but certain optimality bounds guarantees can be computed. When optimizing for code size, GPRA demonstrates code size improvements as large as 16.75% compared to a traditional graph allocator.

There is a high likelihood that snacks will appear at this talk.

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 a fourth year (seems like longer) graduate student in the computer science department and his advisor is Seth Goldstein.