Loop Headers in Lambda-Calculus or CPS

Abstract:

As is well known, the introduction of a ``loop header'' block
facilitates the hoisting of loop-invariant code from a loop.
But in a $lambda$-calculus intermediate representation, which
has a notion of scope, this transformation is particularly useful.
Loop headers with scope also solve an old problem with
in-line expansion of recursive functions or loops: if done
naively, only the first iteration is inlined. A loop header
can encapsulate the loop or recursion for better in-line expansion.
This optimization improves performance by about 5\% in Standard ML
of New Jersey.

This technical report has been published as

Loop Headers in Lambda-Calculus or CPS. Andrew W. Appel, Lisp
and Symbolic Computation 7, 337-343,
1994.