A simple interprocedural register allocation algorithm and its effectiveness for LISP

ABSTRACT

Register allocation is an important optimization in many compilers, but with per-procedure register allocation, it is often not possible to make good use of a large register set. Procedure calls limit the improvement from global register allocation, since they force variables allocated to registers to be saved and restored. This limitation is more pronounced in LISP programs due to the higher frequency of procedure calls. An interprocedural register allocation algorithm is developed by simplifying a version of interprocedural graph coloring. The simplification corresponds to a bottom-up coloring of the interference graph. The scheme is evaluated using a number of LISP programs. The evaluation considers the scheme's limitations and compares these “software register windows” against the hardware register windows used in the Berkeley RISC and SPUR processors.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: BASART, E., AND FOLGER, D. RIDGE 32 Architecture--A RISC Variation. In Proceedings of the International Conference on Computer Design VLS! in Computers (Port Chester, N.Y., Oct., 1983). IEEE, New york, 1983.
• 4: BATALI, J., GOODHUE, E., HANSON, C., SHROBE, H., STALLMAN, R., AND SUSSMAN, G. The SCHEME-81 architecture--System and chip. In Proceedings of the 1982 Con{erence on Advanced Research in VLSI (Boston, Mass., Jan. 1982). MIT, Cambridge, Mass., 1982, pp. 69-77.
• 5: BAWDEN, A., GREENBLATT, R., HOLLOWAY, J., KNIGHT, T., MOON, D., AND WEINREB, D. LISP machine progress report. Tech. Rep. Memo 444, MIT Artificial Intelligence Laboratory, Cambridge, Mass., Aug. 1977.
• 6: BERENBAUM, A., DITZEL, D., AND MCLELLAN, H. Architectural innovations in the CRISP microprocessor. In Spring 1987 COMPCON Digest of Papers (San Francisco, Calif., Feb. 1987). IEEE, New York, 1987, pp. 91-95.
• 7: 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
• 8: Eugene Charniak , Drew McDermott, Introduction to artificial intelligence, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 9: Frederick Chi-Tak Chow, A portable machine-independent global optimizer--design and measurements, 1984
• 10: F. C. Chow, Minimizing register usage penalty at procedure calls, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.85-94, June 20-24, 1988, Atlanta, Georgia, United States
• 11: CHOW, F., HIMELSTEIN, M., KILLIAN, E., AND WEBER, L. Engineering a RISC compiler system. In Spring 1986 COMPCON Digest of Papers (San Francisco, Calif., Mar. 1986). IEEE, New York, 1986, pp. 132-137.
• 12: 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
• 13: Paul Chow, MIPS-X instruction set and programmer''s manual, Stanford University, Stanford, CA, 1986
• 14: Keith D. Cooper , Ken Kennedy , Linda Lorczon, Interprocedural optimization: eliminating unnecessary recompilation, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.58-67, June 25-27, 1986, Palo Alto, California, United States
• 15: COUTANT, D., HAMMOND, C., AND KELLY, W. Compilers for the new generation of Hewlett- Packard computers. Hewlett-Packard J. I (Jan. 1986), 4-18.
• 16: David R. Ditzel , Hubert R. McLellan , Alan D. Berenbaum, Design tradeoffs to support the C programming language in the CRISP microprocessor, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.158-163, October 1987, Palo Alto, California, United States
• 17: David R. Ditzel , H. R. McLellan, Register allocation for free: The C machine stack cache, Proceedings of the first international symposium on Architectural support for programming languages and operating systems, p.48-56, March 01-03, 1982, Palo Alto, California, United States
• 18: Charles N. Fischer , Richard J. LeBlanc, Jr., Crafting a compiler, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1988
• 19: Michael J. Flynn , Chad L. Mitchell , Johannes M. Mulder, And now a case for more complex instruction sets, Computer, v.20 n.9, p.71-83, Sept. 1987 [doi>10.1109/MC.1987.1663696]
• 20: Richard P. Gabriel, Performance and evaluation of LISP systems, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 21: GRISS, M. L., AND HEARN, A.C. A portable LISP compiler. Softw. Pract. Exper. 11, 6 (June 1981), 541-605.
• 22: Martin L. Griss , Eric Benson , Anthony C. Hearn, Current status of a portable LISP compiler, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.276-283, June 23-25, 1982, Boston, Massachusetts, United States
• 23: Martin L. Griss , Eric Benson , Gerald Q. Maguire, Jr., PSL: A Portable LISP System, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.88-97, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802139]
• 24: HAUCK, E., AND DENT, B. Burroughs' B6500/B7500 stack mechanism. In Computer Structures: Principles and Examples. D. Siewiorek, C. Bell, and A. Newell, Eds., McGraw-Hill, New York, 1982, chap. 16, pp. 244-259.
• 25: HENNESSY, J. L., JOUPPl, N., BASKETT, F., AND GILL, J. MIPS: A VLSI processor architecture. In Proceedings of the CMU Conference on VLSI Systems and Computations (Pittsburgh, Pa., Oct. 1981). CMU, Pittsburgh, Pa., 1981, pp. 337-346.
• 26: HOROWITZ, M., HENNESSY, J., CHOW, P., GULAK, P., ACKEN, J., AGARWAL, A., CHU, C. Y., MCFARLING, S., PRZYBYLSKI, S., RICHARDSON, S., SALZ, A., SIMONI, R., STARK, D., STEENKISTE, P., TZIANC, S., AND WING, M. A 32b microprocessor with on-chip 2K byte instruction cache. In Digest 1987 International Solid-State Circuits Conference (New York, Feb. 1987). IEEE, New York, 1987, pp. 30-31.
• 27: HUGUET, M. A C-oriented register set design. Tech. Rep. CSD-850019, Computer Science Dept., UCLA, June 1985.
• 28: Richard Karl Johnsson, An approach to global register allocation., 1976
• 29: R. R. Kessler , J. C. Peterson , H. Carr , G. P. Duggan , J. Knell, EPIC - a retargetable, highly optimizing Lisp compiler, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.118-130, June 25-27, 1986, Palo Alto, California, United States
• 30: Tomás Lang , Miquel Huguet, Reduced register saving/restoring in single-window register files, ACM SIGARCH Computer Architecture News, v.14 n.3, p.17-26, June 1 1986 [doi>10.1145/381711.381714]
• 31: 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
• 32: Bruce W. Leverett, Register Allocation in Optimizing Compilers, University Microfilms International (UMI), Ann Arbor, MI, 1983
• 33: David A. Moon, Architecture of the Symbolics 3600, ACM SIGARCH Computer Architecture News, v.13 n.3, p.76-83, June 1985
• 34: Johannes M. Mulder, Tradeoffs in processor-architecture and data-buffer design, Stanford University, Stanford, CA, 1988
• 35: Thomas P. Murtagh, A less dynamic memory allocation scheme for algol-like languages, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.283-289, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800540]
• 36: PATTERSON, D. A., AND SEQUIN, C.H. A VLSI RISC. Computer 15, 9 (Sept. 1982), 8-22.
• 37: PENDLETON, J. A design methodology for VLSI processors. Ph.D. thesis, Computer Science Div. (EECS), Un~. of California, Berkeley, Calif., Sept. 1985.
• 38: REINER, A. Cost-minimization in register assignment for retargetable compilers. Tech. Rep. CMU-CS-84-137, Carnegie-Mellon Univ., Pittsburgh, Pa., June 1985.
• 39: RICHARDSON, S., AND GANAPATHI, M. Interprocedural Observations. Stanford Univ., Stanford, Calif., Jan. 1988.
• 40: SITES, R. L. How to use 1000 registers. In Proceedings of the Caltech Conference on VLSI (Pasadena, Calif., Jan. 1979). California Institute of Technology, Pasadena, 1979, pp. 527-532.
• 41: Guy Lewis Steele, Jr. , Gerald Jay Sussman, The dream of a lifetime: A lazy variable extent mechanism, Proceedings of the 1980 ACM conference on LISP and functional programming, p.163-172, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802802]
• 42: P. A. Steenkiste, Lisp on a reduced-instruction-set processor: characterization and optimization, Stanford University, Stanford, CA, 1987
• 43: Peter Steenkiste , John Hennessy, LISP on a reduced-instruction-set-processor, Proceedings of the 1986 ACM conference on LISP and functional programming, p.192-201, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319862]
• 44: Peter Steenkiste , John Hennessy, Lisp on a Reduced-Instruction-Set Processor: Characterization and Optimization, Computer, v.21 n.7, p.34-45, July 1988 [doi>10.1109/2.67]
• 45: G. S. Taylor , P. N. Hilfinger , J. R. Larus , D. A. Patterson , B. G. Zorn, Evaluation of the SPUR Lisp architecture, Proceedings of the 13th annual international symposium on Computer architecture, p.444-452, June 02-05, 1986, Tokyo, Japan
• 46: David Michael Ungar, The design and evaluation of a high performance SMALLTALK system, University of California at Berkeley, Berkeley, CA, 1986
• 47: David Ungar , Ricki Blau , Peter Foley , Dain Samples , David Patterson, Architecture of SOAR: Smalltalk on a RISC, Proceedings of the 11th annual international symposium on Computer architecture, p.188-197, January 1984
• 48: William M. Waite, Code Generation, Compiler Construction, An Advanced Course, 2nd ed., p.302-332, January 1976
• 49: 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
• 50: D. W. Wall, Register windows vs. register allocation, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.67-78, June 20-24, 1988, Atlanta, Georgia, United States
• 51: Thomas Richard Wilcox, Generating machine code for high-level programming languages, 1971
• 52: P. H. Winston , B. K. Horn, LISP, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 53: William Allan Wulf , Richard K. Johnsson , Charles B. Weinstock , Steven O. Hobbs , Charles M. Geschke, The Design of an Optimizing Compiler, Elsevier Science Inc., New York, NY, 1975

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.2 Language Classifications

          Nouns: LISP
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Design, Measurement, Performance