Space-Efficient Closure Representations
Last modified: Tue Mar 14 19:28:27 2000 GMT.
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.
In Proc. 1994 ACM Conf. on Lisp and Functional Programming, Orlando, FL, page 150-161, June 1994. ©1994 ACM.
TextGzipped Postscript [174k]
Copyright © 1996-2019 The FLINT Group
<flint at cs dot yale dot edu>
Yale University Department of Computer Science