Campus Event Calendar
Event Entry
What and Who
Register Allocation for SSA-Form Programs
Daniel Grund
IMPRS
Talk
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 21 February 2006
12:00
30 Minutes
46.1 - MPII
0.24
Saarbrücken
Abstract
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.
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.
Contact
Kerstin Kathy Meyer-Ross
9325-226
--email hidden
passcode not visible
logged in users only
Jennifer Weiler, 02/17/2006 09:56 -- Created document.