Frederick Chow
John Hennessy
ABSTRACT
The classic problem of global register allocation is treated in a heuristic and practical manner by adopting the notion of priorities in node-coloring. The assignment of priorities is based on estimates of the benefits that can be derived from allocating individual quantities in registers. Using the priorities, the exponential coloring process can be made to run in linear time. Since the costs involved in register allocation are taken into account, the algorithm does not over-allocate. The algorithm can be parameterized to cater to different fetch characteristics and register configurations among machines. Measurements indicate that the register allocation scheme is effective on a number of target machines. The results confirm that, using priority-based coloring, global register allocation can be performed practically and efficiently.
- 1.G.J. Chitin, "Register Allocation and Spilling via Graph Coloring," ACM SIGPLAN Notice#, 17, 6 (June 1982), (Proceeding# of the SIGPLAN 82 Symposium on Compiler Construction), pp. 201 - 207. Google Scholar
Digital Library
- 2.F. Chow, "A Portable Machine-independent Global Optimizer -- Design and Measurements," Ph.D. Thesis and Technical Report 83-254, Computer System Lab, Stanford University, Dec. 1983. Google ScholarDigital Library
- 3.R.A. Freiburghouse, "Register Allocation Via Usage Counts," Comm. ACM 17, 11, Nov. 74. Google ScholarDigital Library
- 4.B. W, Leverett, "Register Allocation in Optimizing Compilers," Ph.D. Thesis and Tcchnlcal Report CMU C8-81-103, Carnegie-Mellon University, February 1981. Google ScholarDigital Library
- 5.D. Perkins and R. Sites, "Machine-independent Pascal Code Optimization," ACM SIGPLAN Notices, 14, 8 (August 1979), (Proceedings on the SIG- PLAN 79 Symposium on Compiler Construction), pp. 201-207. Google ScholarDigital Library
- 6.R.L. Sites and D.R. Perkins, "Machine-independent Register Allocation," ACM SIGPLAN Notices, Vol. 14, Number 8 (August 1979), (Proceedings of the SIGPLAN 79 Symposium on Compiler Construction), pp. 221-225. Google ScholarDigital Library
- 7.J.T. Schwartl, "On Programming: An Interim Report on the SETL Project," Courant Institute of Math. Sciences, New York University, 1973.Google Scholar
- Register allocation by priority-based coloring
Recommendations
Register allocation by priority-based coloring
Proceedings of the SIGPLAN '84 symposium on compiler constructionThe classic problem of global register allocation is treated in a heuristic and practical manner by adopting the notion of priorities in node-coloring. The assignment of priorities is based on estimates of the benefits that can be derived from ...
The priority-based coloring approach to register allocation
Global register allocation plays a major role in determining the efficacy of an optimizing compiler. Graph coloring has been used as the central paradigm for register allocation in modern compilers. A straightforward coloring approach can suffer from ...
Register allocation by priority-based coloring
20 Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation 1979-1999: A SelectionThe classic problem of global register allocation is treated in a heuristic and practical manner by adopting the notion of priorities in node-coloring. The assignment of priorities is based on estimates of the benefits that can be derived from ...
Comments