Efficient register allocation via coloring using clique separators

ABSTRACT

Although graph coloring is widely recognized as an effective technique for register allocation, memory demands can become quite high for large interference graphs that are needed in coloring. In this paper we present an algorithm that uses the notion of clique separators to improve the space overhead of coloring. The algorithm, based on a result by R. Tarjan regarding the colorability of graphs, partitions program code into code segments using clique separators. The interference graphs for the code partitions are constructed one at a time and colored independently. The colorings for the partitions are combined to obtain a register allocation for the entire program. This approach can be used to perform register allocation in a space-efficient manner. For straight-line code (e.g., local register allocation), an optimal allocation can be obtained from optimal allocations for individual code partitions. Experimental results are presented demonstrating memory demand reductions for interference graphs when allocating registers using clique separators.

REFERENCES

• 1: 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
• 2: ~CHAITIN, G. J., AUSLANDER, M. A., CHANDRA, A. K., COCKE, J., HOPKINS, M. E., AND MARKSTEIN, ~P.W. 1981. Register allocation via coloring. Comput. Lang 6, 1, 47-57.
• 3: C.-H. Chi , H. G. Dietz, Register allocation for GaAs computer systems, Proceedings of the Twenty-First Annual Hawaii International Conference on Architecture Track, p.266-274, January 1988, Kailua-Kona, Hawaii, United States
• 4: Jong-Deok Choi , Ron Cytron , Jeanne Ferrante, Automatic construction of sparse data flow evaluation graphs, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.55-66, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99594]
• 5: 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
• 6: ~DONGARRA, J. J. AND JINDS, n.R. 1979. Unrolhng loops in Fortran. Soflw. Pract. Exper. 9, 3 ~(Mar.), 219-226.
• 7: ~FISHER, J.A. 1981. Trace scheduling: A technique for global mlcrocode compaction. IEEE ~Trans. Comput. C-30, 7 (July), 478-490.
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: ~GAVRIL, F. 1977. AJgorlthms on chque separable graphs. Dtscrete Math. 19, 159-165.
• 10: ~GOLUMBlC, M.C. 1980. Algorzthmtc Graph Theory and Perfect Graphs. Academic Press, New ~York.
• 11: R. Gupta , M. L. Soffa , T. Steele, Register allocation via clique separators, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.264-274, June 19-23, 1989, Portland, Oregon, United States
• 12: 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
• 13: M. Donald MacLaren, Inline routines in VAXELN Pascal, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.266-275, June 17-22, 1984, Montreal, Canada
• 14: ~TaRJAN, R.E. 1985. Decomposition by clique separators. Discrete Math. 55, 2, 221-231

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Hardware/software interfaces

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Code generation

General Terms:
Algorithms, Design, Languages, Performance

Keywords:
clique separators, graph coloring, interference graph, node priorities, spans, spill code