Optimal spilling for CISC machines with few registers
Authors:
Open Access
- 1 May 2001
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 36 (5) , 243-253
Abstract
Many graph-coloring register-allocation algorithms don't work well for machines with few registers. Heuristics for live-range splitting are complex or suboptimal; heuristics for register assignment rarely factor the presence of fancy addressing modes; these problems are more severe the fewer registers there are to work with. We show how to optimally split live ranges and optimally use addressing modes, where the optimality condition measures dynamically weighted loads and stores but not register-register moves. Our algorithm uses integer linear programming but is much more efficient than previous ILP-based approaches to register allocation. We then show a variant of Park and Moon's optimistic coalescing algorithm that does a very good (though not provably optimal) job of removing the register-register moves. The result is Pentium code that is 9.5% faster than code generated by SSA-based splitting with iterated register coalescing.Keywords
This publication has 8 references indexed in Scilit:
- Iterated register coalescing1996
- Improvements to graph coloring register allocationACM Transactions on Programming Languages and Systems, 1994
- Static branch frequency and program profile analysis1994
- A portable and optimizing back end for the SML/NJ compilerLecture Notes in Computer Science, 1994
- Standard ML of New Jersey1991
- The priority-based coloring approach to register allocationACM Transactions on Programming Languages and Systems, 1990
- A Modeling Language for Mathematical ProgrammingManagement Science, 1990
- On the Geographical Problem of the Four ColoursAmerican Journal of Mathematics, 1879