Local optimization in a compiler for stack-based Lisp machines

ABSTRACT

We describe the local optimization phase of a compiler for translating the INTERLISP dialect of LISP into stack-architecture (0-address) instruction sets. We discuss the general organization of the compiler, and then describe the set of optimization techniques found most useful, based on empirical results gathered by compiling a large set of programs. The compiler and optimization phase are machine independent, in that they generate a stream of instructions for an abstract stack machine, which an assembler subsequently turns into the actual machine instructions. The compiler has been in successful use for several years, producing code for two different instruction sets.

REFERENCES

• 1: Richard R. Burton, Larry M. Masinter, Daniel G. Bobrow, Willie Sue Haugeland, Ronald M. Kaplan and B. A. Sheil, "Overview and implementation status of DoradoLisp", to appear, 1980.
• 2: L. Peter Deutsch. "A Lisp machine with very compact programs". Proceedings of the Third International Joint Conference on Artificial Intelligence, Stanford, 1973.
• 3: L. Peter Deutsch, Experience with a microprogrammed Interlisp system, Proceedings of the 11th annual workshop on Microprogramming, p.128-129, November 19-22, 1978, Pacific Grove, California, United States
• 4: L. Peter Deutsch, ByteLisp and its Alto implementation, Proceedings of the 1980 ACM conference on LISP and functional programming, p.231-242, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802811]
• 5: Edward R. Fiala. "The Maxc Systems". IEEE Computer, 11:5, May 1978.
• 6: Martin L. Griss and Anthony C. Hearn. "A Portable LISP Compiler". Report UCP-76, Department of Computer Science, University of Utah, June 1979.
• 7: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 8: Warren Teitelman et al. INTERLISP Reference Manual. Xerox Palo Alto Research Center, October 1978.
• 9: Jaak Urmi, A machine independent lisp compiler and its implications for ideal hardware (instruction-set, architecture, hll), 1978

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: INTERLISP
      D.3.4 Processors
          Subjects: Compilers

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representation languages

General Terms:
Languages, Performance