Most of Twobit's optimizations occur during Pass 2, which consists of one post-order pass over the expression tree output by Pass 1.
That expression tree contains no internal definitions. The main goal of optimization is to detect known local procedures, to record them as internal definitions, and to hoist these internal definitions to a more global scope where they will be evaluated less frequently.
The two most important optimizations in Pass 2 are single assignment analysis, which detects assignments that can be converted into internal definitions of known local procedures, and incremental lambda lifting, which hoists the known local procedures of nested lambda expressions to their enclosing lambda expression.
These are also the most original of the optimizations used in Twobit. They are variations of two well-known optimizations, closure analysis and lambda lifting, which are used by most compilers for higher order languages.
For the
reverse-map
example, the output of Pass 2 is
(begin
(set! reverse-map
(lambda (.f|1 .l|1)
(define .loop|2
(lambda (.f|1|6 .l|3 .x|3)
(if (pair? .l|3)
(.loop|2
.f|1|6
(cdr .l|3)
(cons (.f|1|6 (car .l|3)) .x|3))
.x|3)))
(begin (unspecified)
(.loop|2 .f|1 .l|1 '()))))
'reverse-map)
An optional Pass 3, to perform flow analysis and representation inference, has not yet been released. For these notes we will assume that the output of Pass 2 goes directly to the code generator.