A nanopass infrastructure for compiler education

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 , Keith D. Cooper, Combining analyses, combining optimizations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.181-196, March 1995 [doi>10.1145/201059.201061]
• 5: R. Kent Dybvig, The SCHEME programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 6: R. Kent Dybvig , Robert Hieb , Carl Bruggeman, Syntactic abstraction in Scheme, Lisp and Symbolic Computation, v.5 n.4, p.295-326, Dec. 1992 [doi>10.1007/BF01806308]
• 7: Wilf R. LaLonde , Jim des Rivieres, A flexible compiler structure that allows dynamic phase ordering, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.134-139, June 23-25, 1982, Boston, Massachusetts, United States
• 8: Sorin Lerner , David Grove , Craig Chambers, Composing dataflow analyses and transformations, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.270-282, January 16-18, 2002, Portland, Oregon
• 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 , P. Lee, TIL: a type-directed optimizing compiler for ML, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.181-192, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 12: C. Van Reeuwijk, Tm: a code generator for recursive data structures, Software—Practice & Experience, v.22 n.10, p.899-908, Oct. 1992 [doi>10.1002/spe.4380221008]
• 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 , R. Kent Dybig, Fast and Effective Procedure Inlining, Proceedings of the 4th International Symposium on Static Analysis, p.35-52, September 08-10, 1997
• 15: Philip Wadler, Deforestation: Transforming Programs to Eliminate Trees, Proceedings of the 2nd European Symposium on Programming, p.344-358, March 21-24, 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: Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]
• 18: D. Whitfield , M. L. Soffa, An approach to ordering optimizing transformations, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.137-146, March 14-16, 1990, Seattle, Washington, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Translator writing systems and compiler generators

General Terms:
Design, Languages, Reliability

Keywords:
compiler writing tools, domain-specific languages, nanopass compilers, syntactic abstraction