P. Briggs
K. D. Cooper
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.
- AuHo 82.M. Auslander and M. Hopkins. An overview of the PL.8 compiler. Proceeding8 of the SIGPLAN '82 Symposium on Compiler Construction, SIC- PLAN Notices 17(6), June, 1982. Google Scholar
Digital Library
- CCHK 87.A. Carle, K.D. Cooper, R.T. Hood, K. Kennedy, L. Torczon, a~d S.K. Warren. A practical environment for scientific programming. IEEE Computer 20(11), November, 1987. Google ScholarDigital Library
- 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, editom), SIAM, 1984.Google Scholar
- Chai 82.G.J. Chaitin. Register allocation and spilling via graph coloring. Proceedings of the $1~PLAN '82 Symposium on Compiler Construction, $IGPLAN Notices 17(6), June, 1982. Google ScholarDigital Library
- 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 Language8 6, January, 1981.Google Scholar
- Chow 83.F. Chow. A portable machine-independent global optimizer--design and measurements. Phi). Thesis. Technical Note No. 83-254, Computer Systems Laboratory, Stanford University, Dec. 1983. Google ScholarDigital Library
- ChHe 84.F. Chow and J. Hennessy. Register allocation by priority based coloring. Proceedings of the SIC- PLAN '84 Symposium on Compiler Construction, SIGPLAN Notices 19(6), June, 1984. Google ScholarDigital Library
- CoKT 86.K.D. Cooper, K. Kennedy, and L. Torczon. The impact of interprocedural analysis and optimiza~ tion in the IRa programming environment. A CM Transactions on Programming Languages and Systems 8(4), October, 1986. Google ScholarDigital Library
- DBMS 82.J.J. Dongarra, J.R. Bunch, C.B. Moler, and G.W. Stewart. LINPACK Users' Guide, SIAM, Philadelphia, PA., 1982.Google Scholar
- Dong 83.J.J. Dong~ra. Performance of various computers using standard linear equations software in a Fortran environment. Argonne National Laborstory Technical Memorandum 28, August 1983 and subsequent revisions.Google Scholar
- FoMM 77.G.E. Forsythe, M.A. Malcolm, and C.B. Moler. Computer Methods for Mathematical Computations, Prentice-Hall, Inc., Englewood Cliffs, N J, 1977. Google ScholarDigital Library
- LaHi 86.J.R. Larus and P.N. Hilfinger. Register alloca~ tion in the SPUR Lisp compiler. Proceedings of the $IGPLAN '86 Symposium on Compiler Corstruction, $IGPLAN Notices 21(7), June, 1986. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- Wirt 76.N. Wirth. Algorithms + Data Structures = Programs. Prentice-Hall, Inc., Englewood Cliffs, N J, 1976. Google ScholarDigital Library
Index Terms
- Coloring heuristics for register allocation
Recommendations
Register allocation & spilling via graph coloring
SIGPLAN '82: Proceedings of the 1982 SIGPLAN symposium on Compiler constructionIn a previous paper we reported the successful use of graph coloring techniques for doing global register allocation in an experimental PL/I optimizing compiler. When the compiler cannot color the register conflict graph with a number of colors equal to ...
Coloring heuristics for register allocation
Proceedings of the SIGPLAN '89 symposium on Interpreters and interpretive techniquesWe 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 ...
Improvements to graph coloring register allocation
We describe two improvements to Chaitin-style graph coloring register allocators. The first, optimistic coloring, uses a stronger heuristic to find a k-coloring for the interference graph. The second extends Chaitin's treatment of rematerialization to ...
Comments