Wed Oct 26, 11:00-12:00, 4760 Boelter Hall

Towards Register Allocation for Programs in SSA-form

Sebastian Hack
University of Karlsruhe, Germany

Graph coloring is a popular and successful technique for global 
register allocation. However, since graph coloring is NP-complete 
and each undirected graph can (theoretically) occur during register 
allocation, register allocation is also NP-complete. Even determining 
whether k registers will suffice for a given program is NP-complete. 
Furthermore, the coalescing phase which tries to eliminate useless 
copies may modify the program so that it will need more registers. 
If register pressure is high enough, this raise in demand causes 
memory traffic.  A lot of work has been done to prevent register 
allocators from trading copies with loads and stores.

However, if we restrict ourselves to programs in SSA-form the 
situation changes, since the interference graphs produced by SSA 
programs belong to a special class of graph, called the chordal graphs, 
whose most appealing feature is that they can be colored in quadratic time.

We will present some of the properties SSA-form programs and their 
interference graphs and how they might be used to built better 
register allocators.

About the speaker:  Sebastian Hack received his diploma degree in 2004 
from University of Karlsruhe.  Since then, he has been working as 
a PhD candidate in the group of Professor Goos at University of Karlsruhe.

Host: Jens Palsberg