Efficient and safe-for-space closure conversion

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 trans ferred to the target by a "jump with arguments (or results)." Closure conve rsion-which decides where and how to represent closures at runtime-is a cru cial 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 al locating as many closures in registers as possible, our new closure-convers ion algorithm reduces heap allocation by 36% and memory fetches for local a nd global variables by 43%; and improves the already efficient code generat ed by an earlier version of the Standard NIL of New Jersey compiler by abou t 17% on a DECstation 5000. Moreover, unlike most other approaches, our new closure-allocation scheme satisfies the strong safe-for-space-complexity r ule, thus achieving good asymptotic space usage.