Towards Automatic Construction of Staged Compilers

M. Philipose, C. Chambers, and S. Eggers

Department of Computer Science and Engineering
University of Washington

In the proceedings of the ACM SIGPLAN Conference on Principles of Programming Languages (POPL), January 2002.

ACM's Copyright Policy.

  • PDF (261kB)
  • To save the paper to a file using Netscape Navigator, right click on one of the links at the left and select "Save Link As..."


    Some compilation systems, such as offline partial evaluators and selective dynamic compilation systems, support staged optimizations. A staged optimization is one where a logically single optimization is broken up into stages, with the early stage(s) performing preplanning set-up work, given any available partial knowledge about the program to be compiled, and the final stage completing the optimization. The final stage can be much faster than the original optimization by having much of its work performed by the early stages. A key limitation of current staged optimizers is that they are written by hand, sometimes in an ad hoc manner. We have developed a framework called the Staged Compilation Framework (SCF) for systematically and automatically converting single-stage optimizations into staged versions. The framework is based on a combination of aggressive partial evaluation and dead-assignment elimination. We have implemented SCF in Standard ML. A preliminary evaluation shows that SCF can speed up classical optimization of some commonly used C functions by up to 12x (and typically between 4.5x and 5.5x).

    Last updated February 22, 1999.
    Matthai Philipose (