Coloring register pairs

ABSTRACT

Many architectures require that a program use pairs of adjacent registers to hold double-precision floating-point values. Register allocators based on Chaitin's graph-coloring technique have trouble with programs that contain both single-register values and values that require adjacent pairs of registers. In particular, Chaitin's algorithm often produces excessive spilling on such programs. This results in underuse of the register set; the extra loads and stores inserted into the program for spilling also slow execution. An allocator based on an optimistic coloring scheme naturally avoids this problem. Such allocators delay the decision to spill a value until late in the allocation process. This eliminates the over-spilling provoked by adjacent register pairs in Chaitin's scheme. This paper discusses the representation of register pairs in a graph coloring allocator. It explains the problems that arise with Chaitin's allocator and shows how the optimistic allocator avoids them. It provides a rationale for determining how to add larger aggregates to the interference graph.

REFERENCES

• 1: D. Bernstein , M. Golumbic , y. Mansour , R. Pinter , D. Goldin , H. Krawczyk , I. Nahshon, Spill code minimization techniques for optimizing compliers, ACM SIGPLAN Notices, v.24 n.7, p.258-263, July 1989
• 2: P. Briggs , K. D. Cooper , K. Kennedy , L. Torczon, Coloring heuristics for register allocation, ACM SIGPLAN Notices, v.24 n.7, p.275-284, July 1989
• 3: 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
• 4: CHAITIN, G. J., AUSLANDER, M. A., CHANDRA, A. K., COCKE, J., HOPKINS, M. E., AND MARKSTEIN, P.W. Register allocation via coloring. Comput. Lang. 6, (Jan. 1981), 47-57.
• 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: Fred C. Chow , John L. Hennessy, The priority-based coloring approach to register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.4, p.501-536, Oct. 1990 [doi>10.1145/88616.88621]
• 7: Janet Fabri, Automatic storage optimization, Proceedings of the 1979 SIGPLAN symposium on Compiler construction, p.83-91, August 06-10, 1979, Denver, Colorado, United States
• 8: FABRI, J. Automatic Storage Optimization. UMI Research Press, Ann Arbor, Mich., 1982.
• 9: GOLUMBIC, M.C. Algorithmic Graph Theory and Perfect Graphs. Academic Press, 1980.
• 10: HOPKINS, M.E. Compiling for the RT PC ROMP. In IBM RT Personal Computer Technology. IBM, 1986, 76-82.
• 11: INTEL CORPORATION. i860TM XP Microprocessor, 1991.
• 12: Brian R. Nickerson, Graph coloring register allocation for processors with multi-register operands, ACM SIGPLAN Notices, v.25 n.6, p.40-52, Jun. 1990
• 13: SETHI, R.Complete register allocation problems. SIAM J. Comput. 4, 3 (Sept. 1975), 226-248.

INDEX TERMS

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

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

General Terms:
Algorithms, Languages, Performance

Keywords:
graph coloring, register allocation