Reducing the cost of indirect function calls generated by a C++ compiler is addressed by Calder and Grunwald [3], and Pande and Ryder [10]. Similar optimization goals have been studied for the languages SELF [8] and Cecil [4]. In contrast to our work, which attempts to reuse optimizations already implemented as part of the compiler, previous techniques perform new analyses. The C++ techniques are complimentary. In particular, the technique of Pande and Ryder may be useful in providing heuristics that estimate the best approach for optimizing a given virtual function call.
Calder and Grunwald investigated using branch prediction to reduce the cost of indirect function calls. Branch prediction attempts to predict the direction taken by a branch instruction based on previous executions of the same branch instruction. This optimization can be done in software [1] or in hardware [7]. Calder and Grunwald focus on two techniques: the first is a 2-bit branch target buffer (a small cache which records the direction that the branch last took). The second uses static profile-driven prediction, which stores information on the directions that branches took in a previous execution of the program. In subsequent compilations this profile information is used to predict branch directions. Their results indicate that the first method tends to be very expensive while the second holds some promise.
Pande and Ryder investigated type determination at the call site to statically choose the correct virtual function [10]. Their algorithm attempts to find the type of an object (class instance) at each virtual function call site. The algorithm, based on an interprocedural control flow graph, traces pointer variables and type information through the graph and attempts to match up static type information with pointer variables. If the system can make a definite match between a pointer and its type, the virtual functions called using the pointer can be statically determined. Pande and Ryder are currently gathering data from their implementation to determine its practicality. In contrast, our optimization hopes to enable existing constant propagation (of class types) to determine essentially the same information without requiring a separate optimization.
Hölzle describes several techniques for improving the efficiency of virtual-function lookups4 in SELF: a dynamically typed object-oriented programming language in which every operation (including assignment) involves a virtual-function lookup [8]. Hölzle's techniques include an expandable per-call-site cache that is updated on the fly and a runtime system that dynamically compiles code similar to the code described in Section 2. These techniques work well for SELF programs because executing virtual-function lookups is an expensive operation in a dynamically typed language, where standard dispatch tables, used in statically typed languages, cannot be employed. Hölzle is able to bring the performance of SELF programs to within a factor of two of the comparable C++ program. Unfortunately, many of these techniques are too costly to be applied in a statically typed language such as C++, where dispatch tables already provide an efficient implementation.
Dean et al. describe a profile driven system for specializing virtual function calls in Cecil programs [4]. Comparison of run-time improvements are difficult as they apply to different languages. Dean et al. state that they are currently working on a C++ implementation, but presently have no data. In comparison with our work, they appear to get less code size expansion at the cost of using run-time profile information. This information is used to selectively specialize heavily used virtual functions while ignoring (not creating a copy of the function for) seldom used functions. Our approach lacks such data and therefore cannot make such decisions. The cost for this improvement is an increase in compiler complexity and compile time.
Copyright © 1995, 1996 Bradley M. Kuhn, David W. Binkley.
Verbatim copying and distribution of this entire paper is permitted in any medium, provided this notice is preserved.