Home » forums » LtU Forum

Hoopl: A Modular, Reusable Library for Dataflow Analysis and Transformation

Hoopl: A Modular, Reusable Library for Dataflow Analysis and Transformation, by Simon Peyton Jones, João Dias and Norman Ramsey (ICFP 2010.)

Abstract. Dataflow analysis and transformation of control-flow graphs is pervasive in optimizing compilers, but it is typically tightly interwoven with the details of a particular compiler. We describe Hoopl, a reusable Haskell library that makes it unusually easy to define new analyses and transformations for any compiler. Hoopl's interface is modular and polymorphic, and it offers unusually strong static guarantees. The implementation is also far from routine: it encapsulates state-of-the-art algorithms (interleaved analysis and rewriting, dynamic error isolation), and it cleanly separates their tricky elements so that they can be understood independently.

A vastly different paper than the last one by the same trio (available here,) this one is more of an example of how to write a client for the Hoopl optimization library, and describes some of Hoopl's innovative static guarantees for making sure the analysis is correct. It also describes the newer implementation of the Lerner/Grove/Chambers algorithm for interleaving analysis and transformations. There's even more good news: Hoopl is now on hackage, so you can get started writing your own optimizers!

By Austin Seipp at 2010-04-09 16:08 | LtU Forum | previous forum topic | next forum topic | other blogs | 54665 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

One thing I particularly like about this approach

Hoopl implements a technique known as 'Optimization Fuel' (ref: here - it's a pdf.) Essentially, every rewrite of the input graph describing the program takes 1 point of fuel. Once there's no more fuel, there ceases to be any further rewrites. Because Hoopl is pure, this means you can find a faulty optimization by doing a binary search on the amount of optimization fuel to determine exactly which phase of the optimizer given what input produced unsound results. Combined with source code support for this workflow (like `git bisect`) and a good test suite, this seems like a fine means of testing/refining new experimental optimizations for your compilers.

By Austin Seipp at Fri, 2010-04-09 16:16 | login or register to post comments

Can you please update the link?

The paper linked above was submitted at 7am after the first two authors had been up all night. Since the submission, a number of errors and infelicities have been repaired. I would be grateful if you would link to

http://www.cs.tufts.edu/~nr/pubs/hoopl-abstract.html

or to

http://www.cs.tufts.edu/~nr/pubs/hoopl.pdf

Also, we have eliminated a number of bugs in the software. We are quite keen to have people check out the library and the sample client, which implements the optimizations discussed in the paper. Code up to the minute is available by

  git clone -o tufts git://ghc.cs.tufts.edu/hoopl/hoopl.git

If you are not familiar with git, we recommend the tutorial 'Git Magic'
by Ben Lynn.

The code will continue to be available on Hackage and will be installable by cabal install hoopl, but our plan is to update Hackage a good deal less frenetically than we have done in the last week :-)

By Norman Ramsey at Sat, 2010-04-10 02:54 | login or register to post comments

Done

Link updated to the abstract page, thanks. Also appreciate the link to git - I'll be sure to check out the repository!

By Austin Seipp at Sat, 2010-04-10 04:15 | login or register to post comments

Hoopl guided tour

I thought it might be worth mentioning:

There's a series of blog posts on Hoopl now, starting with this one — Hoopl guided tour: Base system.

By Rehno Lindeque at Sat, 2011-04-23 12:41 | login or register to post comments