ComputingComputer ScienceAlgorithmsCompilersProgramming LanguagesAbstract Syntax TreesCode GenerationCompiler ConstructionControl-flow AnalysisData-flow AnalysisFunctional ProgrammingBenchmark AnalysisCall Graph ConstructionCompile-time OptimizationCompiler DesignControl Flow ControlDominator Tree ConstructionLoop OptimizationWhole-program Optimization
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.
18
Patrick Cousot, Radhia Cousot · 1977 · 6.2K citations
The essence of compiling with continuations
Cormac Flanagan, Amr Sabry, Bruce F. Duba et al. · 1993 · 533 citations
David Tarditi, Greg Morrisett, Pau-Chen Cheng et al. · 1996 · 316 citations · Full text