Robert G. Burger
ABSTRACT
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 calle-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 remarkbly good job of minimizing the need for temporaries in setting up procedure calls.
- 1.Andrew W. Appel and Zhong Shao. CaUee-save registers in continuation-passing style. Lisp and Symbolic Computation, 5(3):191-221, 1992. Google Scholar
Digital Library
- 2.Anders Bondorf. Similiz Manual, System Version 5.0. DIKU, University of Copenhagen, Denmark, 1993.Google Scholar
- 3.Bhaskar Bose. DDD--A transformation system for Digital Design Derivation. Technical Report 331, Indiana University, Computer Science Department, May 1991.Google Scholar
- 4.Robert G. Burger. The Scheme Machine. Technical Report 413, Indiana University, Computer Science Department, August 1994.Google Scholar
- 5.G. J. Chaitin, M. A. Auslander, A. K. Cocke, M. E. Hopkins, and P. W. Markstein. Register allocation via coloring. Computer Languages, 6:47-57, 1981.Google ScholarDigital Library
- 6.F. Chow. Minimizing register usage penalty at procedure calls. In Proceedings o/the SIGPLAN '88 Conference on Programming Language Design and Implementation, June 1988. Google ScholarDigital Library
- 7.Fred C. Chow and John L. Hennessy. The prioritybased coloring approach to register allocation. Transactions on Programming Languages and Systems, 12(4):501-536, October 1990. Google ScholarDigital Library
- 8.William Clinger and Jonathan Rees (editors). Revised4 report on the algorithmic language Scheme. LISP Pointers, IV(3):1-55, July-September 1991. Google ScholarDigital Library
- 9.William D. Clinger and Lars Thomas Hansen. Lambda, the ultimate label, or a simple optimizing compiler for Scheme. In Proceedings of the I994 A CM Conference on LISP and Functional Programming, pages 128-139, 1994. Google ScholarDigital Library
- 10.Richard P. Gabriel. Performance and Evaluation of LISP Systems. MIT Press series in computer systems. MIT Press, Cambridge, MA, 1985. Google ScholarDigital Library
- 11.Robert Hieb, R. Kent Dybvig, and Carl Bruggeman. Representing control in the presence of first-class continuations. In Proceedings of the SIGPLAN '90 Conference on Programming Language Design and Implementation, pages 66-77, June 1990. Google ScholarDigital Library
- 12.David Kranz. Orbit' an optimizing compiler for Scheme. Technical Report 632, Yale University, Computer Science Department, 1988.Google Scholar
- 13.Zhong Shao and Andrew W. Appel. Space-efficient closure representations. In Proceedings of the 199~ A CM Conference on LISP and Functional Programming, pages 150-161, 1994. Google ScholarDigital Library
- 14.P. A. Steenkiste and J. L. Hennessy. A simple interprocedural register allocation algorithm and its effectiveness for Lisp. Transactions on Programming Languages and Systems, 11(1):1-32, January 1989. Google ScholarDigital Library
- 15.Andrew K. Wright and Robert Cartwright. A practical soft type system for Scheme. In Proceedings of the 199d A CM Conference on LISP and Functional Programming, pages 250-262, 1994. Google ScholarDigital Library
Index Terms
- Register allocation using lazy saves, eager restores, and greedy shuffling
Recommendations
Register allocation using lazy saves, eager restores, and greedy shuffling
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)...
Differential register allocation
PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementationMicro-architecture designers are very cautious about expanding the number of architected registers (also the register field), because increasing the register field adds to the code size, raises I-cache and memory pressure, complicates processor ...
Differential register allocation
Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementationMicro-architecture designers are very cautious about expanding the number of architected registers (also the register field), because increasing the register field adds to the code size, raises I-cache and memory pressure, complicates processor ...
Comments