Order of optimizations

Most of Twobit's optimizations are performed by a single pass, with minimal cleanup after each transformation of the code. This makes the order in which optimizations are performed fairly critical. This order is determined by the procedure that optimizes a lambda expression L.

When the body of L is optimized, any lambda expressions that may be contained within L are optimized recursively. This optimization may detect known local procedures, which are recorded as internal definitions and hoisted to the outermost of the inner lambda expressions. After all of the nested lambda expressions have been optimized, incremental lambda lifting hoists their internal definitions to L.

Single assignment analysis then examines the body of L to find known local procedures, which it records as additional internal definitions. Single assignment elimination attempts to convert assignments to the formal parameters of L into LET bindings. All assignments to the formal parameters of L that remain after single assignment elimination are eliminated by assignment elimination. Calls to newly detected known local procedures may then be inlined. The optimized form of L is then returned.

The internal definitions of L are not lifted out of L until after all of the above optimizations have been performed and the optimized form of L has been returned. Lambda lifting is thus the very last optimization to be performed on a lambda expression.