Simple and Effective Link-Time Optimization of Modula-3 Programs

Abstract:

Object-oriented languages have features that help develop modular
programs and libraries of reusable software. Opaque types and
methods, two such features in Modula-3, incur a runtime cost, because
to implement them, the Modula-3 compiler must generate code for
various runtime computations and checks. Incomplete information at
compile time necessitates these computations; their runtime
overhead, however, can be reduced at link time when the entire
program and its type hierarchy become available.
We describe the opportunities for link-time optimization of Modula-3
and present two link-time optimization techniques. Data-driven
simplification is a new technique that uses a program's type
hierarchy to recover completely the cost of opaque types and to
reduce the runtime overhead of methods. It also reveals other
opportunities for optimization, such as constant and type propagation
and procedure inlining and cloning. Profile-driven optimization
uses profile data to identify and transform those procedures that can
benefit most from optimizations made possible by data-driven
simplification. Moreover, our techniques make it as easy to optimize
procedures in libraries as to optimize those in applications. it
converts as many as 78% of the indirect calls executed to direct
calls. Profile-driven optimization reduces the total number of
instructions executed by up to 14% and the number of loads executed
by up to 19%.