Cecil Project Overview

2 Language Implementation Research

Much of our research efforts are focused on developing better implementation technology for object-oriented languages. Our current research strives to achieve excellent performance for large, heavily object-oriented programs. We are targeting whole-program analysis and optimization, enlarging the scope of analysis and optimization to the interprocedural level, potentially to include the entire program being implemented. These techniques are embodied in the Vortex optimizing compiler infrastructure. At present, Vortex has a Cecil front-end, with front-ends for C++ and Modula-3 front-ends under construction. We are investigating the following approaches:

Profile-guided optimization. We are studying how dynamic execution profile information can be applied to understanding and optimizing object-oriented programs. Execution profiles can inform the compiler of those concrete argument types that occurred at the program's call sites; this information can then be exploited when recompiling the program or when compiling new programs with similar call sites. We are first studying how well profiles predict future behavior, both for runs of the same program on different data sets and for different versions of a program. Initial results indicate that concrete type profiles are quite stable. Next, we are exploring ways of incorporating the profile data into the compilation process, including recompiling a call site exploiting its particular profile data and recompiling new call sites using averages of the profiles of similar call sites. More traditionally, the profiles indicate the program's hot spots, and the compiler can use this information to help it make decisions about where to be more aggressive in its optimization. Finally, we are studying how well static compilation augmented with dynamic profile information compares to dynamic compilation as incorporated in SELF. An OOPSLA '95 paper describes our results [Grove et al. 95].
Interprocedural class analysis. Previous work on optimizing compilers for object-oriented languages developed an intraprocedural data flow analysis that computes the concrete classes of the receivers of messages. While this worked well for small programs, its restriction to operating only intraprocedurally turned out to be a severe weakness when compiling larger programs. We are investigating ways of enlarging the scope of static analysis beyond procedure boundaries. One simple but effective technique, class hierarchy analysis, examines the program's inheritance hierarchy to extract information about the possible subclasses of a given class and the possible implementations of a given message. This analysis subsumes the effect of specifying a C++ method as non-virtual and sealing a class in Dylan. An ECOOP '95 paper describes class hierarchy analysis in more detail [Dean et al. 95b]. Beyond class hierarchy analysis, we are studying full interprocedural static class analysis. Our experience is that simple strategies work reasonably well for smaller programs (under 10,000 lines long, say), but do not scale to large programs (say of 50,000 lines or more). We are working on developing efficient and effective techniques for performing interprocedural static class analysis that scale well, both in analysis time and in impact on run-time performance, to reasonably large programs.
Procedure specialization. Previous research investigated applying a simple form of procedure specialization to replicate a single source method for each inheriting concrete class used by the program. In Vortex compiler, we are exploring more general forms of specialization, including specializing on arguments other than the first (as needed by multi-methods) and determining automatically, with the help of profile information, those method and argument combinations that are profitable to specialize. Results of this work appear in a PEPM '94 paper [Dean et al. 94] and a PLDI '95 paper [Dean et al. 95a].
Automatic inlining. Vortex exploits static class information to drive optimizations that eventually lead to replacing dynamically-dispatched message sends with direct procedure calls. These calls are then amenable to traditional optimizations, in particular to inlining and interprocedural analysis. To reduce the programmer burden, Vortex incorporates techniques for automatically choosing good candidates for inlining. An LFP '94 paper describes some techniques for making inlining decisions automatically that take into account the effects of post-inlining optimizations [Dean & Chambers 94].
Selective recompilation. Because Vortex is pursuing whole-program analyses, separate compilation becomes difficult. Accordingly, to support a decent programming environment with quick turnaround for programming changes, Vortex includes mechanisms to automatically track cross-module compilation dependencies and selectively identify modules that must be recompiled after a programming change. This support is described in an ICSE '95 paper [Chambers et al. 95].

We are implementing the Vortex compiler in Cecil. This decision ensures that we will have at least one large, real, heavily object-oriented program with which to evaluate and guide our implementation research and will allow the implementation to exploit the expressive language features available in Cecil. Conversely, the language design research will benefit from the experience we gain using Cecil in a real application. As of Spring 1995, around 50,000 lines of Cecil have been written in the Vortex implementation and the Cecil standard library, and we have used the Vortex infrastructure to compile and optimize Cecil programs for over a year. One of our short-term goals is to develop the Cecil/Vortex language implementation to the point that it is efficient enough to release to the outside research community.

We currently are adapting existing front-ends for C++ and Modula-3 to produce the Vortex compiler's intermediate language. This will allow us to assess how effective our optimization techniques are for hybrid languages, and provide us access to a large array of large benchmark programs. Since we are focusing on well-written, heavily-object-oriented programs even in hybrid languages, we believe that the advanced implementation techniques developed originally for pure object-oriented languages will make a substantial impact on performance of hybrid object-oriented programs. From another perspective, the advanced implementation techniques incorporated in Vortex can enable a more flexible, expressive programming style to be followed.

Cecil Project Overview - 11 MAY 95

[Next] [Previous] [Top]