Contification is a compiler optimization that finds collections of functions
that return to the same place and turns those functions into continuations.
Compilers for functional languages use contification to expose the control-flow
information that is required by many optimizations, including traditional loop
optimizations.
This paper gives a formal presentation of contification in MLton, a
whole-program optimizing Standard ML compiler. We present two existing
algorithms for contification in our framework, as well as a new algorithm based
on the dominator tree of a program's call graph. We prove that the dominator
algorithm is optimal. We present benchmark results on realistic SML programs
demonstrating that contification has minimal overhead on compile time and
significantly improves run time.
