Fast and Effective Optimization of Statically Typed Object-Oriented Languages

David Francis Bacon

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-98-1017
December 1997

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1998/CSD-98-1017.pdf

In this dissertation, we show how a relatively simple and extremely fast interprocedural optimization algorithm can be used to optimize many of the expensive features of statically typed, object-oriented languages -- in particular, C++ and Java.

We present a new program analysis algorithm, Rapid Type Analysis, and show that it is fast both in theory and in practice, and significantly out-performs other "fast" algorithms for virtual function call resolution.

We present optimization algorithms for the resolution of virtual function calls, conversion of virtual inheritance to direct inheritance, elimination of dynamic casts and dynamic type checks, and removal of object synchronization. These algorithms are all presented within a common framework that allows them to be driven by the information collected by Rapid Type Analysis, or by some other type analysis algorithm.

Collectively, the optimizations in this dissertation free the programmer from having to sacrifice modularity and extensibility for performance. Instead, the programmer can freely make use of the most powerful features of object-oriented programming, since the optimizer will remove unnecessary extensibility from the program.

Advisor: Susan L. Graham


BibTeX citation:

@phdthesis{Bacon:CSD-98-1017,
    Author = {Bacon, David Francis},
    Title = {Fast and Effective Optimization of Statically Typed Object-Oriented Languages},
    School = {EECS Department, University of California, Berkeley},
    Year = {1997},
    Month = {Dec},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1997/5791.html},
    Number = {UCB/CSD-98-1017},
    Abstract = {In this dissertation, we show how a relatively simple and extremely fast interprocedural optimization algorithm can be used to optimize many of the expensive features of statically typed, object-oriented languages -- in particular, C++ and Java. <p>We present a new program analysis algorithm, Rapid Type Analysis, and show that it is fast both in theory and in practice, and significantly out-performs other "fast" algorithms for virtual function call resolution. <p>We present optimization algorithms for the resolution of virtual function calls, conversion of virtual inheritance to direct inheritance, elimination of dynamic casts and dynamic type checks, and removal of object synchronization. These algorithms are all presented within a common framework that allows them to be driven by the information collected by Rapid Type Analysis, or by some other type analysis algorithm. <p>Collectively, the optimizations in this dissertation free the programmer from having to sacrifice modularity and extensibility for performance. Instead, the programmer can freely make use of the most powerful features of object-oriented programming, since the optimizer will remove unnecessary extensibility from the program.}
}

EndNote citation:

%0 Thesis
%A Bacon, David Francis
%T Fast and Effective Optimization of Statically Typed Object-Oriented Languages
%I EECS Department, University of California, Berkeley
%D 1997
%@ UCB/CSD-98-1017
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1997/5791.html
%F Bacon:CSD-98-1017