A study of devirtualization techniques for a Java (TM) just-in-time compiler

Many devirtualization techniques have been proposed to reduce the runtime o verhead of dynamic method calls for various object-oriented languages, howe ver, most of them are less effective or cannot be applied for Java in a str aightforward manner. This is partly because Java is a statically-typed lang uage and thus transforming a dynamic call to a static one does not make a t angible performance gain (owing to the low overhead of accessing the method table) unless it is inlined, and partly because the dynamic class loading feature of Java prohibits the whole program analysis and optimizations from being applied. We propose a new technique called direct devirtualization with the code par ching mechanism. For a given dynamic call site, our compiler first determin es whether the call can be devirtualized, by analyzing the current class hi erarchy. When the call is devirtualizable and the target method is suitably sized, the compiler generates the inlined code of the method, together wit h the backup code of making the dynamic call. Only the inlined code is actu ally executed until our assumption about the devirtualization becomes inval idated, at which time the compiler performs code patching to make the backu p code executed subsequently. Since the new technique prevents some code mo tions across the merge point between the inlined code and the backup code, we have furthermore implemented recently-known analysis techniques, such as type analysis and preexistence analysis, which allow the backup code to be completely eliminated. We made various experiments using 16 real programs to understand the effectiveness and characteristics of the devirtualization techniques in our Java Just-In-Time (JIT) compiler. In summary, we reduced the number of dynamic calls by ranging from 8.9% to 97.3% (the average of 40.2%), and we improved the execution performance by ranging from -1% to 13 3% (with the geometric mean of 16%).