Abstract
Since the mid ’80s, compiler writers for functional languages (especially lazy ones) have been writing papers about identifying and exploiting thunks and lambdas that are used only once. However, it has proved difficult to achieve both power and simplicity in practice. In this paper we describe a new, modular analysis for a higher-order language, which is both simple and effective. We prove the analysis sound with respect to a standard call-by-need semantics, and present measurements of its use in a full-scale, state-of-the-art optimising compiler. The analysis finds many single-entry thunks and one-shot lambdas and enables a number of program optimisations.
This paper extends our earlier conference publication (POPL’14) with proofs, expanded report on evaluation and a detailed examination of the factors causing the loss of precision in the analysis.
To appear in the Journal of Functional Programming