Demand-driven register allocation

ABSTRACT

A new global register allocation technique, demand-driven register allocation, is described. Demand-driven register allocation quantifies the costs and benefits of allocating variables to registers over live ranges so that high-quality allocations can be made. Local allocation is done first, and then global allocation is done iteratively beginning in the most deeply nested loops. Because local allocation precedes global allocation, demand-driven allocation does not interfere with the use of well-known, high-quality local register allocation and instruction-scheduling techniques.

REFERENCES

• 1: Thomas Ball , James R. Larus, Optimally profiling and tracing programs, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.59-70, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143180]
• 2: BEATTY, J. C. 1974. Register assignment algorithm for generation of highly optimized object code. IBM J. Res. Devel. 18, 1 (Jan.), 20-39.
• 3: P. Briggs , K. D. Cooper , K. Kennedy , L. Torczon, Coloring heuristics for register allocation, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.275-284, June 19-23, 1989, Portland, Oregon, United States
• 4: David Callahan , Brian Koblenz, Register allocation via hierarchical graph coloring, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.192-203, June 24-28, 1991, Toronto, Ontario, Canada
• 5: 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
• 6: CHAITIN, G. J., AUSLANDER, ~/{. t., CHANDRA, t. K., COOKE, J., HOPKINS, 54. E., AND 54ARK- STEIN, P. W. 1981. Register allocation via graph coloring. Comput. Lang. 6, 47-57.
• 7: 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]
• 8: Charles N. Fischer , Richard J. LeBlanc, Jr., Crafting a compiler, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1988
• 9: Christopher W. Fraser , David R. Hanson, A code generation interface for ANSI C, Software—Practice & Experience, v.21 n.9, p.963-988, Sept. 1991 [doi>10.1002/spe.4380210906]
• 10: Christopher W. Fraser, A retargetable compiler for ANSI C, ACM SIGPLAN Notices, v.26 n.10, p.29-43, Oct. 1991 [doi>10.1145/122616.122621]
• 11: R. A. Freiburghouse, Register allocation via usage counts, Communications of the ACM, v.17 n.11, p.638-642, Nov. 1974 [doi>10.1145/361179.361201]
• 12: Wei-Chung Hsu , Charles N. Fisher , James R. Goodman, On the Minimization of Loads/Stores in Local Register Allocation, IEEE Transactions on Software Engineering, v.15 n.10, p.1252-1260, October 1989 [doi>10.1109/TSE.1989.559775]
• 13: 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
• 14: E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
• 15: W. G. Morris, CCG: a prototype coagulating code generator, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.45-58, June 24-28, 1991, Toronto, Ontario, Canada
• 16: Todd A. Proebsting , Charles N. Fischer, Probabilistic register allocation, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.300-310, June 15-19, 1992, San Francisco, California, United States
• 17: 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:
  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: Code generation

General Terms:
Algorithms, Languages, Performance, Theory

Keywords:
optimizing compiler