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 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 domina-tor tree of a program's call graph. We prove that the dom-inator 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.