icfp01.pdf
(with Stephen Weeks; Appeared at ICFP'01;
20010903-ICFP01.ppt)
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 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.