Spill code minimization techniques for optimizing compliers

ABSTRACT

Global register allocation and spilling is commonly performed by solving a graph coloring problem. In this paper we present a new coherent set of heuristic methods for reducing the amount of spill code generated. This results in more efficient (and shorter) compiled code. Our approach has been compared to both standard and priority-based coloring algorithms, universally outperforming them.

In our approach, we extend the capability of the existing algorithms in several ways. First, we use multiple heuristic functions to increase the likelihood that less spill code will be inserted. We have found three complementary heuristic functions which together appear to span a large proportion of good spill decisions. Second, we use a specially tuned greedy heuristic for determining the order of deleting (and hence coloring) the unconstrained vertices. Third, we have developed a “cleaning” technique which avoids some of the insertion of spill code in non-busy regions.

References

1. AH82.Auslander, M.A. and Hopkins, M.E., 'An overview of the PL.8 compiler', Proceedings of the A CM Symposium on Compiler Construction (June 1982), 22-31.
2. B85.Bollobas, B., Random Graphs, Academic Press, London, 1985.
3. B79.Brelas, D., 'New methods to color the vertices of a graph', Commun. ACM 22 (1979), 251-256.
4. C81.Chaitin, G.J., Auslander, M.A., Chandra, A.K., Cocke, J., Hopkins, M.E., and Markstein, P.W., 'Register allocation via coloring', Computer Languages 6 (1981), 47-57.
5. C82.Chaitin, G.J., *Register allocation and spilling via graph coloring', Proceedings of the A CM Symposium on Compiler Construction (June 1982), 98-105.
6. CH84.Chow, F., and Hennessy, J., 'Register allocation by priority-based coloring', Proceedings of the A CM Symposium on Compiler Construction (June 1984), 222-232.
7. DGP88.Dagan, I., Golumbic, M.C., and Pinter, R.Y., 'Trapezoid graphs and their coloring', D/screte Applied Math. 21 (1988), 35-46.
8. G80.Golumbie, M.C., Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.
9. G85.Golumbic, M. C., ed., ~lnterval Graphs and Related Topics', a special issue of Discrete Math. 55 (1985), 113-243.
10. LH86.Larus, J.R., and Hilfinger, P.N., 'Register allocation in the SPUR Lisp compiler', Proc~edings of the A CM Symposium on Compiler Construction (June 1986), 255-263.
11. M72.Matula, D.W., Marble, G., and Isaacson, J.D., 'Graph coloring algorithms', in Graph Theory and Computing, (Read, R.C., ed.), Academic Press, New York, 1972.
12. W86.Wall, D.W., 'Global register allocation at link time', Proceedings of the A CM Symposium on Compiler Construction (June 1986), 264-275.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

• Theory of computation

  • Randomness, geometry and discrete structures