Space-efficient closure representations

ABSTRACT

Many modern compilers implement function calls (or returns) in two steps: first, a closure environment is properly installed to provide access for free variables in the target program fragment; second, the control is transferred to the target by a “jump with arguments (or results)”. Closure conversion, which decides where and how to represent closures at runtime, is a crucial step in compilation of functional languages. We have a new algorithm that exploits the use of compile-time control and data flow information to optimize closure representations. By extensive closure sharing and allocating as many closures in registers as possible, our new closure conversion algorithm reduces heap allocation by 36% and memory fetches for local/global variables by 43%; and improves the already-efficient code generated by the Standard ML of New Jersey compiler by about 17% on a DECstation 5000. Moreover, unlike most other approaches, our new closure allocation scheme satisfies the strong “safe for space complexity” rule, thus achieving good asymptotic space usage.

REFERENCES

• 1: Andrew W. Appel, Garbage collection can be faster than stack allocation, Information Processing Letters, v.25 n.4, p.275-279, June 17, 1987 [doi>10.1016/0020-0190(87)90175-X]
• 2: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 3: Andrew W. Appel and Trevor Jim. Optimizing closure environment representations. Technical Report 168, Dept. of Computer Science, Princeton University, Princeton, N J, 1988.
• 4: A. W. Appel , T. Jim, Continuation-passing, closure-passing style, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.293-302, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75303]
• 5: Andrew W. Appel and David B. MacQueen. Standard ML of New Jersey. In Martin Wirsing, editor, Third Int'I Syrup. on Prog. Lang. Implementation and Logic Programming, pages 1-13, New York, August 1991. Springer-Verlag.
• 6: Andrew W. Appel , Zhong Shao, Callee-save registers in continuation-passing style, Lisp and Symbolic Computation, v.5 n.3, p.191-221, Sept. 1992 [doi>10.1007/BF01807505]
• 7: Andrew W. Appel and Zhong Shao. An empirical and analytic study of stack vs. heap cost for languages with closures. Technical Report CS-TR-450-94, Princeton University, Department of Computer Science, Princeton, N J, March 1994.
• 8: Lennart Augustsson. Garbage collection in the < v,g >- machine. Technical Report PMG memo 73, Dept. of Computer Sciences, Chalmers University of Technology, Goteborg, Sweden, December 1989.
• 9: Henry G. Baker. The buried binding and stale binding problems of LISP 1.5. unpublished, undistributed paper, June 1976.
• 10: Luca Cardelli, Compiling a functional language, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.208-217, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802037]
• 11: D. R. Chase, Safety consideration for storage allocation optimizations, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.1-10, June 20-24, 1988, Atlanta, Georgia, United States
• 12: 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
• 13: Will Clinger , Anne Hartheimer , Eric Ost, Implementation strategies for continuations, Proceedings of the 1988 ACM conference on LISP and functional programming, p.124-131, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62692]
• 14: G. Cousineau , P. L. Curien , M. Mauny, The categorical abstract machine, Proc. of a conference on Functional programming languages and computer architecture, p.50-64, January 1985, Nancy, France
• 15: O. Danvy, Memory allocation and higher-order functions, Papers of the Symposium on Interpreters and interpretive techniques, p.241-252, June 24-26, 1987, St. Paul, Minnesota, United States
• 16: Amer Diwan , David Tarditi , Eliot Moss, Memory subsystem performance of programs using copying garbage collection, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.174710]
• 17: Lal George , Florent Guillame , John H. Reppy, A Portable and Optimizing Back End for the SML/NJ Compiler, Proceedings of the 5th International Conference on Compiler Construction, p.83-97, April 07-09, 1994
• 18: Carsten K. Gomard , Peter Sestoft, Globalization and live variables, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.166-177, June 17-19, 1991, New Haven, Connecticut, United States
• 19: 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]
• 20: Chris Hanson, Efficient stack allocation for tail-recursive languages, Proceedings of the 1990 ACM conference on LISP and functional programming, p.106-118, June 27-29, 1990, Nice, France [doi>10.1145/91556.91603]
• 21: R. Hieb , R. Kent Dybvig , Carl Bruggeman, Representing control in the presence of first-class continuations, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.66-77, June 1990, White Plains, New York, United States
• 22: Thomas Johnsson, Lambda lifting: transforming programs to recursive equations, Proc. of a conference on Functional programming languages and computer architecture, p.190-203, January 1985, Nancy, France
• 23: Norman P. Jouppi, Cache write policies and performance, Proceedings of the 20th annual international symposium on Computer architecture, p.191-201, May 16-19, 1993, San Diego, California, United States
• 24: R. Kelsey , P. Hudak, Realistic compilation by program transformation (detailed summary), Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.281-292, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75302]
• 25: David Kranz , Norman Adams , Richard Kelsey , Jonathan Rees , Paul Hudak , James Philbin, ORBIT: an optimizing compiler for scheme, ACM SIGPLAN Notices, v.21 n.7, p.219-233, July 1986
• 26: David Andrew Kranz , Paul Hudak, Orbit: an optimizing compiler for scheme, 1988
• 27: P. J. Landin. The mechanical evaluation of expressions. Computer Journal, 6(4):308-20, 1964.
• 28: Xavier Leroy, Unboxed objects and polymorphic typing, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.177-188, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143205]
• 29: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 30: Guillermo Juan Rozas. Liar, an algoblike compiler for scheme. S.B. thesis, MIT Dept. of Computer Science and Electrical Engineering, June 1984.
• 31: Barbara G. Ryder , Marvin C. Paull, Elimination algorithms for data flow analysis, ACM Computing Surveys (CSUR), v.18 n.3, p.277-316, Sept. 1986 [doi>10.1145/27632.27649]
• 32: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• 33: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 34: Robert E. Tarjan. Testing flow graph reducibility. Journal of Compuier and System Science, 9(3):355-365, December 1974.
• 35: Mads Tofte , Jean-Pierre Talpin, Implementation of the typed call-by-value λ-calculus using a stack of regions, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.188-201, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177855]
• 36: David Michael Ungar, The design and evaluation of a high performance Smalltalk system, MIT Press, Cambridge, MA, 1987

INDEX TERMS

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

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

          Nouns: Standard ML
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Languages, Measurement