Efficient and safe-for-space closure conversion

Zhong Shao, Andrew W. Appel

Research output: Contribution to journalArticle

12 Scopus citations

Abstract

Modern compilera 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.

Original languageEnglish (US)
Pages (from-to)129-161
Number of pages33
JournalACM Transactions on Programming Languages and Systems
Volume22
Issue number1
DOIs
StatePublished - Jan 2000

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Algorithms
  • D.3.3 [Programming Languages]: Language Constructs and Features - Procedures, functions, and subroutines
  • D.3.4 [Programming Languages]: Processors - Compilers; optimization; closure conversion
  • Languages
  • Performance
  • Theory

Fingerprint Dive into the research topics of 'Efficient and safe-for-space closure conversion'. Together they form a unique fingerprint.

  • Cite this