Higher-Order Cardinality Analysis

Since the mid 80’s, 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. We describe a new, modular analysis for a higher-order language, which is both simple and effective, and present measurements of its use in a full-scale, state of the art optimising compiler. The analysis indeed finds many single-entry thunks and one-shot lambdas, although the wall-clock speedups are modest.