Coloring heuristics for register allocation

ABSTRACT

We describe an improvement to a heuristic introduced by Chaitin for use in graph coloring register allocation. Our modified heuristic produces better colorings, with less spill code. It has similar compile-time and implementation requirements. We present experimental data to compare the two methods.

REFERENCES

• 1: J. W. Backus, R. J. Beeber, S. Best, R. Goldberg, L. M. Haibt, H. L. Herrick, R. A. Nelson, D. Sayre, P. B. Sheridan, H. Stern, I. Ziller, R. A. Hughes, and R. Nutt. The FORTRAN automatic coding system. In Proceedings of the Western Joint Computer Conference, pages 188--198. Institute of Radio Engineers, NY, NY, USA, Feb. 1957.
• 2: Peter Bergner , Peter Dahl , David Engebretsen , Matthew O'Keefe, Spill code minimization via interference region spilling, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.287-295, June 16-18, 1997, Las Vegas, Nevada, United States
• 3: D. Bernstein , M. Golumbic , y. Mansour , R. Pinter , D. Goldin , H. Krawczyk , I. Nahshon, Spill code minimization techniques for optimizing compliers, ACM SIGPLAN Notices, v.24 n.7, p.258-263, July 1989
• 4: Preston Briggs , Keith D. Cooper , Linda Torczon, Coloring register pairs, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.3-13, March 1992 [doi>10.1145/130616.130617]
• 5: Preston Briggs , Keith D. Cooper , Linda Torczon, Rematerialization, ACM SIGPLAN Notices, v.27 n.7, p.311-321, July 1992
• 6: Preston Briggs , Linda Torczon, An efficient representation for sparse sets, ACM Letters on Programming Languages and Systems (LOPLAS), v.2 n.1-4, p.59-69, March–Dec. 1993 [doi>10.1145/176454.176484]
• 7: David Callahan , Brian Koblenz, Register allocation via hierarchical graph coloring, ACM SIGPLAN Notices, v.26 n.6, p.192-203, June 1991
• 8: G. J. Chaitin, Register allocation & spilling via graph coloring, ACM SIGPLAN Notices, v.17 n.6, p.98-101, June 1982
• 9: G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, M. E. Hopkins, and P. W. Markstein. Register allocation via graph coloring. Computer Languages, 6(1):47--57, Jan. 1981.
• 10: Jong-Deok Choi , Ron Cytron , Jeanne Ferrante, Automatic construction of sparse data flow evaluation graphs, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.55-66, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99594]
• 11: Frederick Chow , John Hennessy, Register allocation by priority-based coloring, ACM SIGPLAN Notices, v.19 n.6, p.222-232, June 1984
• 12: Keith D. Cooper , Timothy J. Harvey , Linda Torczon, How to build an interface graph, Software—Practice & Experience, v.28 n.4, p.425-444, April 10, 1998 [doi>10.1002/(SICI)1097-024X(19980410)28:4<425::AID-SPE160>3.0.CO;2-2]
• 13: Keith D. Cooper , L. Taylor Simpson, Live Range Splitting in a Graph Coloring Register Allocator, Proceedings of the 7th International Conference on Compiler Construction, p.174-187, March 28-April 04, 1998
• 14: Lal George , Andrew W. Appel, Iterated register coalescing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.300-324, May 1996 [doi>10.1145/229542.229546]
• 15: R. Gupta , M. L. Soffa , T. Steele, Register allocation via clique separators, ACM SIGPLAN Notices, v.24 n.7, p.264-274, July 1989
• 16: James R. Larus , Paul N. Hilfinger, Register allocation in the SPUR Lisp compiler, ACM SIGPLAN Notices, v.21 n.7, p.255-263, July 1986
• 17: S. S. Lavrov. Store economy in closed operator schemes. Journal of Computational Mathematics and Mathematical Physics, 1(4):687--701, 1961. English translation in U.S.S.R. Computational Mathematics and Mathematical Physics 3:810--828, 1962.
• 18: D. Matula and L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. Technical Report CSE-8104, Department of Computer Science and Engineering, Southern Methodist University, July 1981.
• 19: Brian R. Nickerson, Graph coloring register allocation for processors with multi-register operands, ACM SIGPLAN Notices, v.25 n.6, p.40-52, Jun. 1990
• 20: Cindy Norris , Lori L. Pollock, Register allocation over the program dependence graph, ACM SIGPLAN Notices, v.29 n.6, p.266-277, June 1994
• 21: J. Park , S.-M. Moon, Optimistic Register Coalescing, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.196, October 12-18, 1998
• 22: Marc Auslander , Martin Hopkins, An overview of the PL.8 compiler, ACM SIGPLAN Notices, v.17 n.6, p.22-31, June 1982
• 23: Alan Carle , Keith D. Cooper , Robert T. Hood , Ken Kennedy , Linda Torczon, A practical environment for scientific programming, Computer, v.20 n.11, p.75-89, Nov. 1987 [doi>10.1109/MC.1987.1663418]
• 24: {CeDT 84} M. R. Celis, J. E. Dennis, and R. A. Tapia. A trust region strategy for equality constrained optimization. In Numerical Optimization 1984 (P. T. Boggs, R. H. Byrd, and R. B. Schnabel, editors), SIAM, 1984.
• 25: G. J. Chaitin, Register allocation & spilling via graph coloring, ACM SIGPLAN Notices, v.17 n.6, p.98-101, June 1982
• 26: {CACC 81} G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, M. E. Hopkins, and P. W. Markstein. Register allocation via coloring. Computer Languages 6, January, 1981.
• 27: Frederick Chi-Tak Chow, A portable machine-independent global optimizer--design and measurements, 1984
• 28: Frederick Chow , John Hennessy, Register allocation by priority-based coloring, ACM SIGPLAN Notices, v.19 n.6, p.222-232, June 1984
• 29: Keith D. Cooper , Ken Kennedy , Linda Torczon, The impact of interprocedural analysis and optimization in the Rⁿ programming environment, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.4, p.491-523, Oct. 1986 [doi>10.1145/6465.6489]
• 30: {DBMS 82} J. J. Dongarra, J. R. Bunch, C. B. Moler, and G. W. Stewart. LINPACK Users' Guide, SIAM, Philadelphia, PA., 1982.
• 31: {Dong 83} J. J. Dongarra. Performance of various computers using standard linear equations software in a Fortran environment. Argonne National Laboratory Technical Memorandum 23, August 1983 and subsequent revisions.
• 32: George E. Forsythe , Michael A. Malcolm , Cleve B. Moler, Computer Methods for Mathematical Computations, Prentice Hall Professional Technical Reference, 1977
• 33: James R. Larus , Paul N. Hilfinger, Register allocation in the SPUR Lisp compiler, ACM SIGPLAN Notices, v.21 n.7, p.255-263, July 1986
• 34: {MaBe 81} D. Matula and L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. TR CSE 8104, Dept. of Computer Science and Engineering, Southern Methodist University, Dallas, TX, July, 1981.
• 35: {Torc 89} V. J. Torczon. Nonlinear optimization by parallel searches on simplex edges. PhD. Thesis, Department of Mathematical Sciences, Rice University, Houston, TX, expected May, 1989.
• 36: Niklaus Wirth, Algorithms + Data Structures = Programs, Prentice Hall PTR, Upper Saddle River, NJ, 1978