Ph.D. Thesis: Effective Interprocedural Optimization of Object-Oriented Languages

David Grove

This dissertation demonstrates that interprocedural analysis can be both practical and effective for sizeable object-oriented programs. Although frequent procedure calls and message sends are important structuring techniques in object-oriented languages, they can also severely degrade application run-time performance. A number of analyses and transformations have been developed that attack this performance problem by enabling the compile-time replacement of message sends with procedure calls and of procedure calls with inlined copies of their callees. Despite the success of these techniques, even after they are applied it is extremely likely that some message sends and non-inlined procedure calls will remain in the program. These remaining call sites can force an optimizing compiler to make pessimistic assumptions about program behavior, causing it to miss opportunities for potentially profitable optimizations. Interprocedural analysis is one well-known technique for enabling an optimizing compiler to more precisely model the effects of non-inlined calls, thus reducing their impact on application performance.

Interprocedural analysis of object-oriented and functional languages is quite challenging because message sends and/or applications of computed function values complicate the construction of the program call graph, a critical data structure for interprocedural analyses. Therefore, the core of this dissertation is an in-depth examination of the call graph construction problem for object-oriented languages. It consists of the following components:

A general parameterized algorithm that encompasses many well-known and novel call graph construction algorithms is defined.
The general algorithm is implemented in the Vortex compiler infrastructure, a mature, multi-language, optimizing compiler. The Vortex implementation provides a "level playing field" for meaningful cross-algorithm performance comparisons.
The costs and benefits of a number of call graph construction algorithms are empirically assessed by applying their Vortex implementation to a suite of sizeable (5,000 to 50,000 lines of code) Cecil and Java programs. Two small Smalltalk programs are also considered.

For many of the benchmark applications, interprocedural analysis enabled substantial speed-ups over an already highly optimized baseline. Furthermore, a significant fraction of these speed-ups can be obtained through the use of a scalable, near-linear time call graph construction algorithm.

To get the PostScript file, click here.

Cecil/Vortex Project