Campus Event Calendar

Event Entry

What and Who

Register Allocation for SSA-Form Programs

Daniel Grund
AG 1, AG 2, AG 3, AG 4, AG 5  
AG Audience

Date, Time and Location

Tuesday, 21 February 2006
30 Minutes
46.1 - MPII


Register allocation is an important optimization in compilers. It maps the
variables of the program to the registers of the target machine. Graph
coloring is a popular and successful technique for doing so. However, since
graph coloring is NP-complete and each graph may (theoretically) occur
during register allocation, register allocation is also NP-complete. In
addition to register assignment other aspects of the problem such as
spilling of variables and coalescing of copies have to be treated by the
register allocator.

Our new approach requires that the processed programs are first transformed
into SSA-form, which restricts the class of graphs occurring during register
allocation. This insight permits the separation of the subproblems of
spilling, assigning and coalescing leading to faster allocators and possibly
a better allocation quality. In this talk we present this new architecture
with main focus being the coalescing part.


Kerstin Kathy Meyer-Ross
--email hidden
passcode not visible
logged in users only

Jennifer Weiler, 02/17/2006 09:56 -- Created document.