TY - GEN
T1 - Space-efficient closure representations
AU - Shao, Zhong
AU - Appel, Andrew W.
PY - 1994
Y1 - 1994
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0028464101&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0028464101&partnerID=8YFLogxK
U2 - 10.1145/182590.156783
DO - 10.1145/182590.156783
M3 - Conference contribution
AN - SCOPUS:0028464101
SN - 0897916433
SN - 9780897916431
T3 - Proceedings of the ACM Conference on LISP and Functional Programming
SP - 150
EP - 161
BT - Proceedings of the ACM Conference on LISP and Functional Programming
PB - Publ by ACM
T2 - Proceedings of the 1994 ACM Conference on LISP and Functional Programming
Y2 - 27 June 1994 through 29 June 1994
ER -