A compiler structured as a small number of monolithic passes is difficult to understand and difficult to maintain. The steep learning curve is daunting, and even experienced developers find that modifying existing passes is difficult and often introduces 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 fine-grained passes, each of which performs a single task. This structure aligns the implementation of a compiler with its logical organization, simplifying development, testing, and debugging. This paper describes the methodology and tools comprising a framework for constructing such compilers.

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.

The benefits of module systems and lexically scoped syntactic abstraction (macro) facilities are well-established in the literature. This paper presents a system that seamlessly integrates modules and lexically scoped macros. The system is fully static, permits mutually recursive modules, and supports separate compilation. We show that more dynamic module facilities are easily implemented at the source level in the extended language supported by the system.

Profiling can provide the information needed to identify performance bottlenecks in a program, but the programmer must understand its relation to the program source in order to use this information. This is di#cult due to the tremendous volume of data collected. Moreover, program transformations such as macro expansion and procedure inlining can obscure the relationship between the source and object code. Higher-order programs present additional challenges due to complex control flow and because they often consist of many small, often anonymous, procedures whose individual performance properties may be less interesting than their characteristics as a group. To address these challenges we have implemented a profiler and interactive profile visualizer and integrated them into an optimizing Scheme compiler. The profiler instruments target code and maintains correlation with the original source despite compiler optimizations that can eliminate, duplicate, or move code. The visualizer oper...

Traditional first-class continuation mechanisms allow a captured continuation to be invoked multiple times. Many continuations, however, are invoked only once. This paper introduces one-shot continuations, shows how they interact with traditional multi-shot continuations, and describes a stack-based implementation of control that handles both one-shot and multi-shot continuations. The implementation eliminates the copying overhead for one-shot continuations that is inherent in multi-shot continuations. 1 Introduction Scheme [5] and some implementations of ML [17] provide continuations as first-class data objects. Continuations can be used to implement, at the source level, a number of interesting control features, such as loops, nonlocal exits, nonblind backtracking [22], nondeterministic computations [10, 14], and coroutines [7]. Source-level implementations of thread systems [9, 15, 21], especially in the area of graphical user interfaces (GUIs) [12, 13, 20, 23], are an important ...

This paper presents a fast and effective linear intraprocedural register allocation strategy that optimizes register usage across procedure calls. It capitalizes on our observation that while procedures that do not contain calls (syntactic leaf routines) account for under one third of all procedure activations, procedures that actually make no calls (effective leaf routines) account for over two thirds of all procedure activations. Well-suited for both caller-and calle-save registers, our strategy employs a “lazy” save mechanism that avoids saves for all effective leaf routines, an “eager” restore mechanism that reduces the effect of memory latency, and a “greedy” register shuffling algorithm that does a remarkbly good job of minimizing the need for temporaries in setting up procedure calls.