Contification using dominators

Contification is a compiler optimization that turns a function that always returns to the same place into a continuation. Compilers for functional lan guages use contification to expose the control-flow information that is req uired by many optimizations, including traditional loop optimizations. This paper gives a formal presentation of contification in MLton, a whole-p rogram 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 algo rithm is optimal. We present benchmark results on realistic SML programs de monstrating that contification has minimal overhead on compile time and sig nificantly improves run time.