Contification using Dominators

Matthew Fluet Stephen Weeks

To appear at International Conference on Functional Programming (ICFP01), Firenze, Italy, 3-5 September 2001


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.

Server START Conference Manager
Update Time 11 May 2001 at 15:31:50
Start Conference Manager
Conference Systems