Revisiting Register Allocation
Staff - Faculty of Informatics
Start date: 21 July 2011
End date: 22 July 2011
The Faculty of Informatics is pleased to announce a seminar given by Nigel Horspool
DATE: Thursday, July 21st, 2011
PLACE: USI Università della Svizzera italiana, room SI-006, Black building (Via G. Buffi 13)
TIME: 11.00
ABSTRACT:
Where execution performance is concerned, memory accesses are expensive.
A good register allocation strategy will help reduce the number of memory accesses by maintaining frequently used values in registers.
In a traditional compiler, register allocation algorithms based on graph colouring techniques are typically used. The register allocator has to map a set of values onto a set of registers, usually smaller in size, so as to minimize the number of memory accesses. However these algorithms do not fully take execution frequency into account, and may make some choices which turn out to be bad at run-time.
In a JIT-based compiler, the speed at which code can be generated is an issue and quick-and-dirty register allocation schemes based on a linear scan have become popular. However, the JIT environment makes it possible to obtain information about the executing program; perhaps in the form of execution traces or perhaps in the form of execution frequencies for basic blocks. In JIT systems where hot regions of code may be successively recompiled to apply increasing levels of optimization, it makes sense to apply more and more sophisticated register allocation strategies. Perhaps traces or execution frequencies are useful when allocating registers?
This talk will explore some possibilities for trace-based and frequency-based register allocation strategies, with references to some work by others.
This is ongoing work and any experimental results will be very preliminary.
BIO:
Nigel Horspool is a Professor of Computer Science at the University of Victoria in Canada. He received his PhD from the University of Toronto in 1976 for work in virtual memory and cache memory management policies.
His first academic appointment was at McGill University in Montreal, but he moved to Victoria in 1983.
During his career, he has authored or co-authored 3 books, he has served on Canada's research granting council, NSERC, in three different roles, he has had a string-searching algorithm named after him, he has been head of his department, and he is currently a co-editor of the international journal Software: Practice and Experience.
HOST: Prof. Walter Binder
