Flow-directed Space-efficient Closure Conversion

In higher-order languages, a function captures its free variables in a closure, often implemented as a flat record. While this simple structure is effective, more sophisticated representations can significantly reduce overhead. To manage the multiplicity of possible closure representation decisions, this paper introduces a model that represents closure decisions and a transformation that applies these decisions to a program. This paper presents several optimization passes that rewrite the closure representations, each of which greedily minimizes the dynamic allocation required for closures. Higher-order control-flow analysis provides more information about the flows of function values. This information is used both to justify the soundness for some of the proposed rewriting passes and to provide heuristics for others. This paper presents an efficient implementation of 0-CFA with supports for ref-cells and separate compilation. This novel approach is implemented in the Standard ML of New Jersey compiler and evaluated against the existing implementation. The results show that this approach is scalable to large programs and effective in reducing dynamic allocations.