skip to main content
article

A nanopass infrastructure for compiler education

Published: 19 September 2004 Publication History

Abstract

Compilers structured as a small number of monolithic passes are difficult to understand and difficult to maintain. Adding new optimizations often requires major restructuring of existing passes that cannot be understood in isolation. The steep learning curve is daunting, and even experienced developers find it hard to modify existing passes without introducing subtle and tenacious bugs. These problems are especially frustrating when the developer is a student in a compiler class.An attractive alternative is to structure a compiler as a collection of many small passes, each of which performs a single task. This "micropass" structure aligns the actual implementation of a compiler with its logical organization, simplifying development, testing, and debugging. Unfortunately, writing many small passes duplicates code for traversing and rewriting abstract syntax trees and can obscure the meaningful transformations performed by individual passes.To address these problems, we have developed a methodology and associated tools that simplify the task of building compilers composed of many fine-grained passes. We describe these compilers as "nanopass" compilers to indicate both the intended granularity of the passes and the amount of source code required to implement each pass. This paper describes the methodology and tools comprising the nanopass framework.

References

[1]
G. Aigner, A. Diwan, D. Heine, M. Lam, D. Moore, B. Murphy, and C. Sapuntzakis. An overview of the SUIF2 compiler infrastructure. Technical report, Stanford University, 2000.
[2]
G. Aigner, A. Diwan, D. Heine, M. Lam, D. Moore, B. Murphy, and C. Sapuntzakis. The SUIF2 compiler infrastructure. Technical report, Stanford University, 2000.
[3]
J.R. Allen and K. Kennedy. Pfc: A program to convert fortran to parallel form. Technical Report MASC-TR82-6, Rice University, Houston, TX, 1982.
[4]
Cliff Click and Keith D. Cooper. Combining analyses, combining optimizations. ACM Transactions on Programming Languages and Systems, 17(2), 1995.
[5]
R. Kent Dybvig. The Scheme Programming Language. MIT Press, third edition, 2002.
[6]
R. Kent Dybvig, Robert Hieb, and Carl Bruggeman. Syntactic abstraction in Scheme. Lisp and Symbolic Computation, 5(4):295--326, 1993.
[7]
Wilf R. LaLonde and Jim des Rivieres. A flexible compiler structure that allows dynamic phase ordering. In Proceedings of the ACM SIGPLAN Symposium on Compiler Construction, pages 134--139, 1982.
[8]
Sorin Lerner, David Grove, and Craig Chambers. Composing data flow analyses and transformations. In Proceedings of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 270--282, 2002.
[9]
N. Nystrom, M. Clarkson, and A. Myers. Polyglot: An extensible compiler framework for Java. In Proceedings of the 12th International Conference on Compiler Construction, volume 2622 of Lecture Notes in Computer Science, pages 138--152. Springer-Verlag, 2003.
[10]
Anthony Pioli and Michael Hind. Combining interprocedural pointer analysis and conditional constant propagation. Research Report 21532, IBM T. J. Watson Center, 1999.
[11]
D. Tarditi, G. Morrisett, P. Cheng, C. Stone, R. Harper, and P. Lee. TIL: a type-directed optimizing compiler for ML. In Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, pages 181--192, 1996.
[12]
C. van Reeuwijk. Tm: a code generator for recursive data structures. Software Practice and Experience, 22(10):899--908, 1992.
[13]
C. van Reeuwijk. Rapid and robust compiler construction using template-based metacompilation. In Proceedings of the 12th International Conference on Compiler Construction, volume 2622 of Lecture Notes in Computer Science, pages 247--261. Springer-Verlag, 2003.
[14]
Oscar Waddell and R. Kent Dybvig. Fast and effective procedure inlining. In Pascal Van Hentenryck, editor, Fourth International Symposium on Static Analysis, volume 1302 of Lecture Notes in Computer Science, pages 35--52. Springer-Verlag, 1997.
[15]
P. Wadler. Deforestation: Transforming programs to eliminate trees. In ESOP '88: European Symposium on Programming, volume 300 of Lecture Notes in Computer Science, pages 344--358. Springer-Verlag, 1988.
[16]
D.C. Wang, A.W. Appel, J.L. Korn, and C.S. Serra. The zephyr abstract syntax description language. In Proceedings of the USENIX Conference on Domain-Specific Languages, pages 213--228, 1997.
[17]
M. N. Wegman and F. K. Zadeck. Constant propagation with conditional branches. ACM Transactions on Programming Languages and Systems, 3(2):181--210, 1991.
[18]
D. Whitfield and M. L. Soffa. An approach to ordering optimizing transformations. In Proceedings of the Second ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming, pages 137--146, 1990.

Cited By

View all
  • (2023)Nanopass Attribute GrammarsProceedings of the 16th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3623476.3623514(70-83)Online publication date: 23-Oct-2023
  • (2021)Abstracting gradual typing moving forward: precise and space-efficientProceedings of the ACM on Programming Languages10.1145/34343425:POPL(1-28)Online publication date: 4-Jan-2021
  • (2021)Automatic differentiation in PCFProceedings of the ACM on Programming Languages10.1145/34343095:POPL(1-27)Online publication date: 4-Jan-2021
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices
ACM SIGPLAN Notices  Volume 39, Issue 9
ICFP '04
September 2004
254 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1016848
Issue’s Table of Contents
  • cover image ACM Conferences
    ICFP '04: Proceedings of the ninth ACM SIGPLAN international conference on Functional programming
    September 2004
    264 pages
    ISBN:1581139055
    DOI:10.1145/1016850
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 September 2004
Published in SIGPLAN Volume 39, Issue 9

Check for updates

Author Tags

  1. compiler writing tools
  2. domain-specific languages
  3. nanopass compilers
  4. syntactic abstraction

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)28
  • Downloads (Last 6 weeks)4
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Nanopass Attribute GrammarsProceedings of the 16th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3623476.3623514(70-83)Online publication date: 23-Oct-2023
  • (2021)Abstracting gradual typing moving forward: precise and space-efficientProceedings of the ACM on Programming Languages10.1145/34343425:POPL(1-28)Online publication date: 4-Jan-2021
  • (2021)Automatic differentiation in PCFProceedings of the ACM on Programming Languages10.1145/34343095:POPL(1-27)Online publication date: 4-Jan-2021
  • (2021)Dijkstra monads forever: termination-sensitive specifications for interaction treesProceedings of the ACM on Programming Languages10.1145/34343075:POPL(1-28)Online publication date: 4-Jan-2021
  • (2021)Modeling and analyzing evaluation cost of CUDA kernelsProceedings of the ACM on Programming Languages10.1145/34343065:POPL(1-31)Online publication date: 4-Jan-2021
  • (2021)Asynchronous effectsProceedings of the ACM on Programming Languages10.1145/34343055:POPL(1-28)Online publication date: 4-Jan-2021
  • (2021)egg: Fast and extensible equality saturationProceedings of the ACM on Programming Languages10.1145/34343045:POPL(1-29)Online publication date: 4-Jan-2021
  • (2021)On the semantic expressiveness of recursive typesProceedings of the ACM on Programming Languages10.1145/34343025:POPL(1-29)Online publication date: 4-Jan-2021
  • (2021)Simplifying dependent reductions in the polyhedral modelProceedings of the ACM on Programming Languages10.1145/34343015:POPL(1-33)Online publication date: 4-Jan-2021
  • (2021)Data flow refinement type inferenceProceedings of the ACM on Programming Languages10.1145/34343005:POPL(1-31)Online publication date: 4-Jan-2021
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media