Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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

• AH82: Marc Auslander , Martin Hopkins, An overview of the PL.8 compiler, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.22-31, June 23-25, 1982, Boston, Massachusetts, United States
• B85: Bollobas, B., Random Graphs, Academic Press, London, 1985.
• B79: Daniel Brélaz, New methods to color the vertices of a graph, Communications of the ACM, v.22 n.4, p.251-256, April 1979 [doi>10.1145/359094.359101]
• 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.
• C82: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• CH84: Frederick Chow , John Hennessy, Register allocation by priority-based coloring, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.222-232, June 17-22, 1984, Montreal, Canada
• DGP88: Ido Dagan , Martin Charles Golumbic , Ron Yair Pinter, Trapezoid graphs and their coloring, Discrete Applied Mathematics, v.21 n.1, p.35-46, September 1988 [doi>10.1016/0166-218X(88)90032-7]
• G80: Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57), North-Holland, 2004
• G85: Golumbic, M. C., ed., ~lnterval Graphs and Related Topics', a special issue of Discrete Math. 55 (1985), 113-243.
• LH86: James R. Larus , Paul N. Hilfinger, Register allocation in the SPUR Lisp compiler, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.255-263, June 25-27, 1986, Palo Alto, California, United States
• 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.
• W86: David W. Wall, Global register allocation at link time, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.264-275, June 25-27, 1986, Palo Alto, California, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Optimization

General Terms:
Algorithms, Experimentation