Hoopl: Dataflow Optimization Made Simple
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).