Improvements to graph coloring register allocation
- 1 May 1994
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 16 (3), 428-455
- https://doi.org/10.1145/177492.177575
Abstract
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 handle a larger class of values. These techniques are complementary. Optimistic coloring decreases the number of procedures that require spill code and reduces the amount of spill code when spilling is unavoidable. Rematerialization lowers the cost of spilling some values. This paper describes both of the techniques and our experience building and using register allocators that incorporate them. It provides a detailed description of optimistic coloring and rematerialization. It presents experimental data to show the performance of several versions of the register allocator on a suite of FORTRAN programs. It discusses several insights that we discovered only after repeated implementation of these allocators.Keywords
This publication has 16 references indexed in Scilit:
- Coloring register pairsACM Letters on Programming Languages and Systems, 1992
- Simple register spilling in a retargetable compilerSoftware: Practice and Experience, 1992
- Register allocation via hierarchical graph coloringACM SIGPLAN Notices, 1991
- Constant propagation with conditional branchesACM Transactions on Programming Languages and Systems, 1991
- Spill code minimization techniques for optimizing compliersACM SIGPLAN Notices, 1989
- Effectiveness of a machine-level, global optimizerACM SIGPLAN Notices, 1986
- Register allocation by priority-based coloringACM SIGPLAN Notices, 1984
- Smallest-last ordering and clustering and graph coloring algorithmsJournal of the ACM, 1983
- Register allocation via coloringComputer Languages, 1981
- ALPHA—An Automatic Programming System of High EfficiencyJournal of the ACM, 1966