Lambda the Ultimate

Taming the IXP network processor, Lal George and Matthias Blume. PLDI 2003.

We compile Nova, a new language designed for writing network processing applications, using a back end based on integer-linear programming (ILP) for register allocation, optimal bank assignment, and spills. The compiler's optimizer employs CPS as its intermediate representation; some of the invariants that this IR guarantees are essential for the formulation of a practical ILP model.

Appel and George used a similar ILP-based technique for the IA32 to decide which variables reside in registers but deferred the actual assignment of colors to a later phase. We demonstrate how to carry over their idea to an architecture with many more banks, register aggregates, variables with multiple simultaneous register assignments, and, very importantly, one where bank- and register-assignment cannot be done in isolation from each other. Our approach performs well in practise--without causing an explosion in size or solve time of the generated integer linear programs.

This is a nice paper showing how to design and compile a small functional language in a high-performance domain with a very irregular underlying machine model.