Lambda, the Ultimate Label

Twobit is based on viewing lambda expressions as assembly language labels that have been augmented by a list of symbolic names for the registers that are live at that label. The simplicity of this view results from allocating all non-local, non-global variables on the heap. Aggressive lambda lifting makes this practical by eliminating all non-local variables except for those that would have to be allocated on the heap anyway. The eliminated non-local variables become additional arguments to lambda expressions, which means they will be allocated in registers.

Most optimizations used in Twobit are well-known, but a few are new or unusual:

• Incremental lambda lifting gives the compiler more flexibility than global lambda lifting, without the complexity of global lambda lifting followed by lambda dropping.
• Interprocedural register targeting is performed by reordering arguments during lambda lifting. This optimization relies upon parallel assignment optimization during flow analysis or code generation.
• Single assignment analysis is a Scheme-specific first order closure analysis. This optimization was used in MacScheme and possibly in the Orbit compiler but had not been described.
• Single assignment elimination is complicated by the existence of call-with-current-continuation.
• Frame optimization tends to reduce the number of continuation frames that are allocated by a procedure.
• Redundant loads and stores are eliminated by a backpatching algorithm similar to that used for frame optimization.

Pass structure

1. Standardization of syntax
2. Optimization
3. Flow analysis (prototype, not yet released)
4. Code generation
5. Local optimization
6. Assembly

Examples

Obsolete benchmarks

Last updated 4 January 1999.