Todd A. Proebsting
Abstract
A new global register allocation technique, probabilistic register allocation, is described. Probabilistic register allocation quantifies the costs and benefits of allocating variables to registers over live ranges so that excellent allocation choices can be made. Local allocation is done first, and then global allocation is done iteratively beginning in the most deeply nested loops. Because local allocation precedes global allocation, probabilistic allocation does not interfere with the use of well-known, high-quality local register allocation and instruction scheduling techniques.
- BCKT89 Preston Briggs, Keith D. Cooper, Ken Kennedy, and Linda Torczon. Coloring heuristics for register allocation. In Proceedings of the SlGPLAN '89 Conference on Programming Language Design and Implementation, pages 275-284, 1989. Google Scholar
Digital Library
- Bea74 J.C. Beatty. Register assignment algorithm for generation of highly optimized object code. IBM Journal of Research and Development, 18(1):20-39, January 1974.Google ScholarDigital Library
- BL92 Thomas Ball and James R. Larus. Optimally profiling and tracing programs. In Proceedings of the 19th Annual Symposium on Principles of Programming Languages, pages 59-70, January 1992. Google ScholarDigital Library
- CAC+81 G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cooke, M. E. Hopkins, and P. W. Markstein. Register allocation via graph coloring. Computer Languages, 6:47- 57, January 1981.Google ScholarDigital Library
- CH90 Fred C. Chow and John L. Hennessy. The priority-based coloring approach to register allocation. A CM Transactions on Programming Languages and Systems, 12(4):501- 536, January 1990. Google ScholarDigital Library
- Cha82 G.J. Chaitin. Register allocation &: spilling via graph coloring. In Proceedings of the A CM SIGPLAN '82 Symposium on Compiler Construction, pages 98-101, June 1982. Google ScholarDigital Library
- CK91 David Callahan and Brian Koblenz. Register allocation via hierarchical graph coloring. In Proceedings of the SIGPLAN '91 Conference on Programming Language Design and Implementation, pages 192-203, 1991. Google ScholarDigital Library
- FH91a Christopher W. Fraser and David R. Hanson. A code generation interface for ANSI C. Software--Practice and Experience, 21(9):963-988, September 1991. Google ScholarDigital Library
- FH91b Christopher W. Fraser and David R. Hanson. A retargetable compiler for ANSI C. $IGPLAN Notices, 26(10), October 1991. Google ScholarDigital Library
- FL88 Charles N. Fischer and Richard J. Leblanc, Jr. Crafting a Compiler. Benjamin/Cummings, Menlo Park, California, 1988. Google ScholarDigital Library
- Fre74 R.A. Freiburghouse. Register allocation via usage counts. Communications of the A CM, 17(11), November 1974. Google ScholarDigital Library
- HFG89 Wei-Chung Hsu, Charles N. Fischer, and James R. Goodman. On the minimization of loads/stores in local register allocation. IEEE Transactions on Software Engineering, 15(10):1252-1260, 1989. Google ScholarDigital Library
- LH86 J.R. Larus and P. N. Hilfinger. Register allocation in the SPUR lisp compiler. In Pro. ceedings of the $ICPLAN '86 Symposium on Compiler Construction, pages 255-263, 1986. Google Scholar
- Mor91 W.G. Morris. CCG: A prototype coagulating code generator. In Proceedings of the SIGPLAN '91 Conference on Programming Language Design and Implementation, pages 45-58, 1991. Google ScholarDigital Library
Index Terms
- Probabilistic register allocation
Recommendations
Probabilistic register allocation
PLDI '92: Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementationA new global register allocation technique, probabilistic register allocation, is described. Probabilistic register allocation quantifies the costs and benefits of allocating variables to registers over live ranges so that excellent allocation choices ...
Bytewise Register Allocation
SCOPES '15: Proceedings of the 18th International Workshop on Software and Compilers for Embedded SystemsTraditionally, variables have been considered as atoms by register allocation: Each variable was to be placed in one register, or spilt (placed in main memory) or rematerialized (recalculated as needed). Some flexibility arose from what would be ...
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 ...
Comments