Ph.D. Thesis: Whole-Program Optimization of Object-Oriented Languages

Jeffrey Dean
This dissertation examines the use of whole-program optimization as a way of improving the performance of object-oriented programming languages. Although object-oriented pro gramming conveys a number of software engineering benefits, heavy application of its trade mark feature, dynamic dispatching, imposes severe performance penalties when programs are compiled using traditional compilation techniques. Several new techniques that rely on whole-program optimization are described, and these techniques substantially improve the performance of object-oriented programs written in Cecil, Java, C++, and Modula-3.

Among the new techniques is class hierarchy analysis, which provides the compiler with knowledge of the class hierarchy of the entire program. This is an especially important optimization, because it allows programmers to write their programs using dynamic dispatching for all operations, which preserves maximal flexibility and extensibility, but permits the compiler to optimize away this flexibility when it is unused by a particular program. Exhaustive class testing allows the compiler to optimize message sends that have a limited degree of poly morphism by inserting tests to partition the potential classes of objects that can appear at a call site. A selective specialization algorithm combines static information with dynamic profile data to determine where it is profitable to compile multiple, specialized versions of a single source routine. Inlining trials provide a means of making inlining decisions that take into account the effects of post-inlining optimizations. Whole-program optimization in an interactive programming environment is made possible through the use of selective recompilation, a technique for invalidating only compiled code that is affected by a programming change. The techniques described in the thesis have been implemented in the Vortex compiler, a whole-program optimizing compiler developed as part of this dissertation.

Whole-program not only speeds up existing features of object-oriented languages, but it also allows new features to be added to languages with little or no cost, enabling more general models of dispatching that result in more natural and uniform programming languages. The benefits of the optimization techniques described in this thesis are shown to already be important, and their importance is likely to only increase as people adopt more and more object-oriented programming styles.

University of Washington Department of Computer Science and Engineering Technical Report UW-CSE-96-11-05. 169 pages.

To get the PostScript file, click here. Because I am unable to get Frame 5 on the PC to cooperate with me, the Postscript file is formatted as a double-sided document but always seems to print as a single-sided document on any printer that I try it on. Any suggestions for changes to the Postscript to get it to print double-sided on common printers are welcome (send them to

Note: A University of Washington Dept. of Computer Science technical report with this same title was published as UW-CSE-TR 96-06-02. These two technical reports are quite different, despite having the same title.

Cecil/Vortex Project