Research

People

Publications

Software

Support

Links

Internal

Space-Efficient Closure Representations

Last modified: Tue Mar 14 19:28:27 2000 GMT.

Authors

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.

Published

In Proc. 1994 ACM Conf. on Lisp and Functional Programming, Orlando, FL, page 150-161, June 1994. ©1994 ACM.

Text