Efficient and Safe-for-Space Closure Conversion
Last modified: Fri Sep 15 20:18:16 2000 GMT.
Modern compilers often 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 the compilation of functional languages. This paper presents a new algorithm that exploits the use of compile-time control and data flow information to optimize function calls. 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 and global variables by 43%; and improves the already efficient code generated by an earlier version of 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 ACM Transactions on Programming Languages and Systems (TOPLAS), 22(1), pages 129-161, January 2000.
TextGzipped Postscript [242k]
Copyright © 1996-2013 The FLINT Group
<flint at cs dot yale dot edu>
Yale University Department of Computer Science