The Broadway Compiler

  

Figure: Annotations are incorporated into each phase of the compilation process.

This section describes the compiler's overall optimization strategy. The compiler consists mostly of traditional analysis and optimization algorithms, extended to use information from our annotation language. The individual transformations are straightforward and are not discussed. During a particular pass, the compiler refers to the annotations to find the information needed. Figure  shows the internal structure of the compiler and how the annotations are incorporated. We use a particular ordering of the passes that provides the most information for specialization, and then cleans up the customized code using traditional optimizations.

Pointer analysis.

The first phase of the compiler performs pointer analysis. It not only tracks pointers in the application code, but also uses the on_entry and on_exit annotations to determine the data structures manipulated by the library calls. Our pointer analysis algorithm builds a flow-sensitive ``points-to'' graph using the strategy described by Chase, et al [7].

Abstract interpretation.

The second phase solves the analysis problems specified by the property annotations. The analysis framework assigns an abstract state to each object in the program and uses the analyze annotations to propagate this information through the program.

Enabling transformations.

Dataflow analysis often loses interesting information because it acts conservatively with respect to control flow. For example, if a library procedure is used in two different ways, the analyzer will attempt to unify the information from both contexts. Thus, in the third phase the compiler uses any loss of information as a heuristic to drive enabling transformations, such as procedure integration, procedure cloning, loop peeling and node splitting. Since the properties are used to trigger specializations, using them to trigger these transformations is likely to enable many more specializations.

Specialization.

In the fourth phase, the compiler uses the results of analysis along with specialize annotations to perform code customization. At each call site, the compiler looks for a specialization that matches the state of the variables. If a match is found, the call site is replaced. We have found that after specialization, it is often beneficial to repeat the abstract interpretation phase because the program modifications reveal new opportunities for optimization.

Traditional optimizations.

Specialization often enables many opportunities for traditional optimizations. When a general library call is replaced by a special-case call, any arguments that are no longer used become candidates for dead-code elimination. Similarly, inlining a library procedure often reveals redundant computations and unnecessary copies of objects. Thus, in the final phase, we iterate over a small group of traditional optimization passes until no more improvements can be made.

The traditional optimization passes are extended to include library procedures. The basic annotations make this possible by providing the necessary information. During copy propagation, the copyof terms tell the compiler when copies of objects are created, and the modify annotation tells the compiler when those copies become invalid. Similarly, the basic annotations indicate the lifetimes of the objects, allowing the dead-code elimination pass to properly identify dead library calls.