Flow-Analysis-Based Closure Optimization

One of the key implementation challenges for higher-order functional languages is managing the representation of first-class function values. The standard approach to this problem is closure conversion, which is a compiler transformation that introduces an explicit data structure to represent the environment of a function value. Constructing the closure for a nested function usually involves copying data from the enclosing function’s closure. To avoid this copying, one might use linked representations, but that choice makes variable access slow and can introduce space leaks. Shao and Appel developed an effective closure converter that reduces copying and is safe-for-space, but their converter is based on a weak, first-order analysis. In this paper, we present a new safe-for-space closure converter that uses a higher-order flow analysis to inform closure-representation decisions. We describe how this information can be used to improve two aspects of closure optimization: sharing heap-allocated tuples of variables and spreading variables into argument registers. We have implemented our converter in the Standard ML of New Jersey system and demonstrated that it produces better code on average than the Shao and Appel converter, with significant performance gains for some benchmarks.