Article

A nanopass infrastructure for compiler education

Authors:

Dipanwita Sarkar,

Oscar Waddell,

R. Kent DybvigAuthors Info & Claims

ICFP '04: Proceedings of the ninth ACM SIGPLAN international conference on Functional programming

Pages 201 - 212

https://doi.org/10.1145/1016850.1016878

Published: 19 September 2004 Publication History

Get Access

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.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[4]

Cliff Click and Keith D. Cooper. Combining analyses, combining optimizations. ACM Transactions on Programming Languages and Systems, 17(2), 1995.

Digital Library

Google Scholar

[5]

R. Kent Dybvig. The Scheme Programming Language. MIT Press, third edition, 2002.

Digital Library

Google Scholar

[6]

R. Kent Dybvig, Robert Hieb, and Carl Bruggeman. Syntactic abstraction in Scheme. Lisp and Symbolic Computation, 5(4):295--326, 1993.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[10]

Anthony Pioli and Michael Hind. Combining interprocedural pointer analysis and conditional constant propagation. Research Report 21532, IBM T. J. Watson Center, 1999.

Google Scholar

[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.

Digital Library

Google Scholar

[12]

C. van Reeuwijk. Tm: a code generator for recursive data structures. Software Practice and Experience, 22(10):899--908, 1992.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

Cited By

View all

Abdallah MSalem AYousef A(2024)Improved Cross-Platform Mobile Applications to Native Applications ConvertersProceedings of the 10th International Conference on Advanced Intelligent Systems and Informatics 202410.1007/978-3-031-71619-5_9(88-97)Online publication date: 13-Oct-2024
https://doi.org/10.1007/978-3-031-71619-5_9
Hubers AMorris J(2023)Generic Programming with Extensible Data Types: Or, Making Ad Hoc Extensible Data Types Less Ad HocProceedings of the ACM on Programming Languages10.1145/36078437:ICFP(356-384)Online publication date: 31-Aug-2023
https://dl.acm.org/doi/10.1145/3607843
Koparkar CRainey MVollmer MKulkarni MNewton R(2021)Efficient tree-traversals: reconciling parallelism and dense data representationsProceedings of the ACM on Programming Languages10.1145/34735965:ICFP(1-29)Online publication date: 19-Aug-2021
https://dl.acm.org/doi/10.1145/3473596
Show More Cited By

Index Terms

A nanopass infrastructure for compiler education
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Translator writing systems and compiler generators

Recommendations

A nanopass framework for commercial compiler development
ICFP '13: Proceedings of the 18th ACM SIGPLAN international conference on Functional programming

Contemporary compilers must typically handle sophisticated high-level source languages, generate efficient code for multiple hardware architectures and operating systems, and support source-level debugging, profiling, and other program development ...
A nanopass framework for commercial compiler development
ICFP '13

Contemporary compilers must typically handle sophisticated high-level source languages, generate efficient code for multiple hardware architectures and operating systems, and support source-level debugging, profiling, and other program development ...
A nanopass infrastructure for compiler education
ICFP '04

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 ...

Reviews

Reviewer: Benjamin Rayborn Seyfarth

Sarkar, Waddell, and Dybvig present their solution to the problem of how to implement a compiler project in a classroom. The general problem is that compilers are usually constructed to be of a few passes, and each pass is relatively complex, making it difficult for students to write or modify a complete pass. The authors discuss two solutions: a micropass compiler and a nanopass compiler. Both of these allow students to focus on a small portion of the compiler as a smaller pass. The authors' micropass compiler project involves students writing a 50-pass compiler, in Scheme. The project is organized into 15 phases, where students' work is tested after each phase. The authors consider the micropass structure to be a bit troublesome, since students must write code for traversals of abstract syntax trees for each pass. This leads to a large amount of code, which obscures the process. Furthermore, the compiler is slow. The authors' nanopass project involves using a specialized language for writing the compiler passes, and requires the use of grammars for all intermediate languages. The grammars are defined using extensions to Scheme, and represent s-expressions. Overall, this is an interesting concept, with value for teaching compilers. The use of Scheme as an implementation language, and as the source language for the project, is surely of interest to some instructors and not others. For example, some instructors would prefer to have a compiler project targeting languages like Pascal. The authors' project uses the Sparc assembly language as the output of the compiler. In addition, they include some optimization passes, which is certainly positive. The concept of using many small passes is of interest to anyone teaching compilers, regardless of whether they favor Scheme or some other language. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICFP '04: Proceedings of the ninth ACM SIGPLAN international conference on Functional programming

September 2004

264 pages

ISBN:1581139055

DOI:10.1145/1016850

General Chair:
Chris Okasaki
United States Military Academy, West Point
,
Program Chair:
Kathleen Fisher
AT&T Labs Research

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

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

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ICFP04

Sponsor:

ICFP04: ACM SIGPLAN International Conference on Functional Programming

September 19 - 21, 2004

UT, Snow Bird, USA

Acceptance Rates

Overall Acceptance Rate 333 of 1,064 submissions, 31%

Upcoming Conference

ICFP '25

Sponsor:
sigplan

ACM SIGPLAN International Conference on Functional Programming

October 12 - 18, 2025

Singapore , Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
762
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)3

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Abdallah MSalem AYousef A(2024)Improved Cross-Platform Mobile Applications to Native Applications ConvertersProceedings of the 10th International Conference on Advanced Intelligent Systems and Informatics 202410.1007/978-3-031-71619-5_9(88-97)Online publication date: 13-Oct-2024
https://doi.org/10.1007/978-3-031-71619-5_9
Hubers AMorris J(2023)Generic Programming with Extensible Data Types: Or, Making Ad Hoc Extensible Data Types Less Ad HocProceedings of the ACM on Programming Languages10.1145/36078437:ICFP(356-384)Online publication date: 31-Aug-2023
https://dl.acm.org/doi/10.1145/3607843
Koparkar CRainey MVollmer MKulkarni MNewton R(2021)Efficient tree-traversals: reconciling parallelism and dense data representationsProceedings of the ACM on Programming Languages10.1145/34735965:ICFP(1-29)Online publication date: 19-Aug-2021
https://dl.acm.org/doi/10.1145/3473596
Ruffy FWang TSivaraman ALu SHowell J(2020)GauntletProceedings of the 14th USENIX Conference on Operating Systems Design and Implementation10.5555/3488766.3488805(683-699)Online publication date: 4-Nov-2020
https://dl.acm.org/doi/10.5555/3488766.3488805
Bissyandé TRéveillère LLawall JBromberg YMuller G(2015)Implementing an embedded compiler using program transformation rulesSoftware—Practice & Experience10.1002/spe.222545:2(177-196)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1002/spe.2225
Holk ENewton RSiek JLumsdaine A(2014)Region-based memory management for GPU programming languagesACM SIGPLAN Notices10.1145/2714064.266024449:10(141-155)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2714064.2660244
Holk ENewton RSiek JLumsdaine ABlack AMillstein T(2014)Region-based memory management for GPU programming languagesProceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications10.1145/2660193.2660244(141-155)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2660193.2660244
Keep ADybvig R(2013)A nanopass framework for commercial compiler developmentACM SIGPLAN Notices10.1145/2544174.250061848:9(343-350)Online publication date: 25-Sep-2013
https://dl.acm.org/doi/10.1145/2544174.2500618
Keep ADybvig RMorrisett GUustalu T(2013)A nanopass framework for commercial compiler developmentProceedings of the 18th ACM SIGPLAN international conference on Functional programming10.1145/2500365.2500618(343-350)Online publication date: 25-Sep-2013
https://dl.acm.org/doi/10.1145/2500365.2500618
Adams MDuBuisson T(2012)Template your boilerplateACM SIGPLAN Notices10.1145/2430532.236450947:12(13-24)Online publication date: 13-Sep-2012
https://dl.acm.org/doi/10.1145/2430532.2364509
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A nanopass framework for commercial compiler development

A nanopass framework for commercial compiler development