- Kennedy, Andrew
- CPS is better than ANF because it allows easier inlining (ANF requires re-normalization after inlining)
- this paper presents a contification transformation
Recently, the author has re-implemented all stages of the SML.NET compiler pipeline to use a CPS-based intermediate language. […] There are many benefits: the language is smaller and more uniform, simplification of terms is more straightforward and extremely efficient, and advanced optimizations such as contification are more easily expressed. We use CPS only because it is a good place to do optimization; we are not interested in first-class control in the source language (call/cc), or as a means of implementing other features such as concurrency. Indeed, as SML.NET targets .NET IL, a callstack-based intermediate language with support for structured exception handling, the compilation process can be summarized as “transform direct style (SML) into CPS; optimize CPS; transform CPS back to direct style (.NET IL)”
- re-normalization after inlining in ANF leads to complexity
Adding conditional expressions to ANF introduces more complexity.
Inlining either duplicates the term :
or introduces a “join-point” function for term M: (where is basically a continuation)
separation of functions and continuations (both in definition
f k x)
local continuations are basic blocks
but this means that
f k xis not a tail call if
kis a local continuation
kcan be lifted to closure after escape analysis)
k xcompiles to either jump (local continuation) or tail call (if returning from function)
- §4 describes graph representation with better performance characteristics compared to usual tree
- Continuations are always compiled to simple jumps or function returns. Functions, however, are lambda lifted (if known) or compiled to closure (if escaping). Therefore, it is always good to convert functions to continuations (a process called contification).
The contification is possible if a function always returns to the same place.
- In CPS that means that (1) function is known, (2) all call sites pass the same continuation.