Premium
Experimental evaluation and improvements to linear scan register allocation
Author(s) -
Sagonas Konstantinos,
Stenman Erik
Publication year - 2003
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.533
Subject(s) - register allocation , allocator , computer science , register (sociolinguistics) , processor register , compiler , parallel computing , programming language , operating system , linguistics , philosophy , semiconductor memory , memory address
We report our experience from implementing and experimentally evaluating the performance of various register allocation schemes, focusing on the recently proposed linear scan register allocator . In particular, we describe in detail our implementation of linear scan and report on its behavior both on register‐rich and on register‐poor computer architectures. We also extensively investigate how different options to the basic algorithm and to the compilation process as a whole affect compilation times and quality of the produced code. In a nutshell, our experience is that a well‐tuned linear scan register allocator is a good choice on register‐rich architectures. It performs competitively with graph coloring based allocation schemes and results in significantly lower compilation times. When compilation time is a concern, such as in just‐in‐time compilers, it can also be a viable option on register‐poor architectures. Copyright © 2003 John Wiley & Sons, Ltd.