Hoopl: Dataflow Optimization Made Simple

Norman Ramsey, João Dias, and Simon Peyton Jones

We present Hoopl, a Haskell library that makes it easy for compiler writers to implement program transformations based on dataflow analyses. The compiler writer must identify (a) logical assertions on which the transformation will be based; (b) a representation of such assertions, which should form a lattice of finite height; (c) transfer functions that approximate weakest preconditions or strongest postconditions over the assertions; and (d) rewrite functions whose soundness is justified by the assertions. Hoopl uses the algorithm of Lerner, Grove, and Chambers (2002), which can compose very simple analyses and transformations in a way that achieves the same precision as complex, handwritten ``super-analyses.'' Hoopl will be the workhorse of a new back end for the Glasgow Haskell Compiler (version 6.12, forthcoming).

This paper has been superseded by a paper about the implementation of Hoopl, but if you are interested in using Hoopl, this paper is still worth reading—it contains more explanations and examples about how to use the library.

Full paper

The paper is available as US Letter PostScript (436K), US Letter PDF (201K), and US Letter TeX DVI (234K).