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.

This technical report has been published as

Space-Efficient Closure Representations. Zhong Shao and Andrew
W. Appel, Proc. 1994 ACM Conf. on Lisp and
Functional Programming, June 1994.