Title: Department of Computer Science Seminar
Date: Feb. 16, 2000
Time: 4:00 pm to 5:00 pm
Venue: Room N101, CSIT Building [108]
Speaker: Dr Jan Arne Telle (Visiting Fellow, DCS at ANU)
Description: "Linear-Time Register Allocation"


                        Abstract


Abstract: The register allocation problem of 
assigning variables of a program to the registers 
of a machine while avoiding conflicts, 
is well-known to involve graph coloring. 
In its most abstract form, as we view it in this talk, 
it can be reduced to coloring an intersection graph 
of subgraphs of the control-flow graph of the program. 

It was recently shown by Mikkel Thorup that 
the control-flow graph of a structured, i.e. GOTO-free, 
program has bounded treewidth. We apply the 
algorithmic techniques for bounded treewidth graphs 
to show that, for any fixed number of registers, 
there is a linear-time algorithm which takes a structured 
program and finds, if possible, an allocation of variables 
to registers without using intermediate storage. 
Our algorithm allows for rescheduling, i.e. the 
straight-line sequences of statements of the program 
are reordered, while observing data dependencies, 
to minimize register usage.

This is joint work with Hans Bodlaender and Jens Gustedt.

Biography: Dr Jan Arne Telle is currently a Visiting Fellow 
at DCS, ANU until June 2000. He is an Associate Professor 
at the Department of Informatics, University of Bergen, Norway. 
His main area of research is graph algorithms. 
You can access his CV from http://www.ii.uib.no/~telle.



URL: http://cs.anu.edu.au/lib/seminars/seminars00/dept2000021