Lambda-Splitting: A Higher-Order Approach to Cross-Module Optimizations

Abstract:

We describe an algorithm for automatic inline expansion across module
boundaries that works in the presence of higher-order functions and
free variables; it rearranges bindings and scopes as necessary to move
nonexpansive code from one module to another. We describe - and
implement - the algorithm as transformations on lambda-calculus. Our
inliner interacts well with separate compilation and is efficient,
robust, and practical enough for everyday use in the SML/NJ compiler.
Inlining improves performance by 4--8% on existing code, and makes it
possible to use much more data abstraction by consistently eliminating
penalties for modularity.

This technical report has been published as

Lambda-Spliting: A Higher-Order Approach to Cross-Module
Optimization. Matthias Blume and Andrew W. Appel,
Proc. ACM SIGPLAN Int'l Conf. on Functional
Programming (ICFP '97), pp. 112-124, June
1997.