Robert G. Burger, Oscar Waddell, and R. Kent Dybvig, Register allocation using lazy Saves, eager restores, and greedy shuffling, ACM SIGPLAN 1995 Conference on Programming Language Design and Implementation, pp. 130-138, June 1995 (bibtex).
This paper presents a fast and effective linear intraprocedural register allocation strategy that optimizes register usage across procedure calls. It capitalizes on our observation that while procedures that do not contain calls (syntactic leaf routines) account for under one third of all procedure activations, procedures that actually make no calls (effective leaf routines) account for over two thirds of all procedure activations. Well-suited for both caller- and callee-save registers, our strategy employs a "lazy" save mechanism that avoids saves for all effective leaf routines, an "eager" restore mechanism that reduces the effect of memory latency, and a "greedy" register shuffling algorithm that does a remarkably good job of minimizing the need for temporaries in setting up procedure calls.