A study of devirtualization techniques for a Java Just-In-Time compiler

ABSTRACT

Many devirtualization techniques have been proposed to reduce the runtime overhead of dynamic method calls for various object-oriented languages, however, most of them are less effective or cannot be applied for Java in a straightforward manner. This is partly because Java is a statically-typed language and thus transforming a dynamic call to a static one does not make a tangible 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 patching mechanism. For a given dynamic call site, our compiler first determines whether the call can be devirtualized, by analyzing the current class hierarchy. When the call is devirtualizable and the target method is suitably sized, the compiler generates the inlined code of the method, together with the backup code of making the dynamic call. Only the inlined code is actually executed until our assumption about the devirtualization becomes invalidated, at which time the compiler performs code patching to make the backup code executed subsequently. Since the new technique prevents some code motions 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 133% (with the geometric mean of 16%).

REFERENCES

• 1: Brad Calder , Dirk Grunwald, Reducing indirect function call overhead in C++ programs, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.397-408, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177973]
• 2: David Grove , Jeffrey Dean , Charles Garrett , Craig Chambers, Profile-guided receiver class prediction, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.108-123, October 15-19, 1995, Austin, Texas, United States
• 3: Gerald Aigner , Urs Hölzle, Eliminating Virtual Function Calls in C++ Programs, Proceedings of the 10th European Conference on Object-Oriented Programming, p.142-166, July 08-12, 1996
• 4: Urs H~lze. Adaptive Optimization For SELF: Reconciling High Performance With Exploratory Programming, PhD thesis, Stanford University, 1994
• 5: Jeffrey Dean , David Grove , Craig Chambers, Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis, Proceedings of the 9th European Conference on Object-Oriented Programming, p.77-101, August 07-11, 1995
• 6: Mary F. Fernández, Simple and effective link-time optimization of Modula-3 programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.103-115, June 18-21, 1995, La Jolla, California, United States
• 7: David F. Bacon , Peter F. Sweeney, Fast static analysis of C++ virtual function calls, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.324-341, October 06-10, 1996, San Jose, California, United States
• 8: Frank Tip , Jens Palsberg, Scalable propagation-based call graph construction algorithms, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.281-293, October 2000, Minneapolis, Minnesota, United States
• 9: Vijay Sundaresan , Laurie Hendren , Chrislain Razafimahefa , Raja Vallée-Rai , Patrick Lam , Etienne Gagnon , Charles Godin, Practical virtual method call resolution for Java, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.264-280, October 2000, Minneapolis, Minnesota, United States
• 10: Kazuaki Ishizaki , Motohiro Kawahito , Toshiaki Yasue , Mikio Takeuchi , Takeshi Ogasawara , Toshio Suganuma , Tamiya Onodera , Hideaki Komatsu , Toshio Nakatani, Design, implementation, and evaluation of optimizations in a just-in-time compiler, Proceedings of the ACM 1999 conference on Java Grande, p.119-128, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304111]
• 11: David Detlefs , Ole Agesen, Inlining of Virtual Methods, Proceedings of the 13th European Conference on Object-Oriented Programming, p.258-278, June 14-18, 1999
• 12: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 13: Urs Hölzle , Craig Chambers , David Ungar, Debugging optimized code with dynamic deoptimization, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.32-43, June 15-19, 1992, San Francisco, California, United States
• 14: Jens Palsberg , Michael I. Schwartzbach, Object-oriented type inference, Conference proceedings on Object-oriented programming systems, languages, and applications, p.146-161, October 06-11, 1991, Phoenix, Arizona, United States
• 15: Ole Agesen , Urs Hölzle, Type feedback vs. concrete type inference: a comparison of optimization techniques for object-oriented languages, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.91-107, October 15-19, 1995, Austin, Texas, United States
• 16: Paul R. Carini, Hirini Srinivasan, and Michael Hind. Flow- Sensitive Type Analysis for C++, IBM Research Report, RC 20267, 1995
• 17: Etienne Gagnon , Laurie J. Hendren , Guillaume Marceau, Efficient Inference of Static Types for Java Bytecode, Proceedings of the 7th International Symposium on Static Analysis, p.199-219, June 29-July 01, 2000
• 18: Urs Hölzle , Craig Chambers , David Ungar, Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches, Proceedings of the European Conference on Object-Oriented Programming, p.21-38, July 15-19, 1991
• 19: David Francis Bacon , Susan L. Graham, Fast and effective optimization of statically typed object-oriented languages, 1997
• 20: Junpyo Lee, Byung-Sun Yang, Suhyun Kim, SeungIl Lee, Yoo C. Chung, Heungbok Lee, Je Hyung Lee, Soo-Mook Moon, Kemal Ebcioglu, Erik Altman. Reducing Virtual Call Overheads in a Java VM Just-In-Time Compiler, The 4th Annual Workshop on Interaction between Compilers and Computer Architectures, pp.21-33, 2000
• 21: Sun Corp. The Java HotSpot Performance Engine Architecture, Available at http://java.sun.com/products/hotspot/whitepaper.html.
• 22: Bowen Alpern , Mark Charney , Jong-Deok Choi , Anthony Cocchi , Derek Lieber, Dynamic Linking on a Shared-Memory Multiprocessor, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.177, October 12-16, 1999
• 23: Intel Corp. Intel Architecture Software Developer's Manual, order number 243192, 1997.
• 24: Michał Cierniak , Guei-Yuan Lueh , James M. Stichnoth, Practicing JUDO: Java under dynamic optimizations, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.13-26, June 18-21, 2000, Vancouver, British Columbia, Canada
• 25: Motohiro Kawahito , Hideaki Komatsu , Toshio Nakatani, Effective null pointer check elimination utilizing hardware trap, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.139-149, November 2000, Cambridge, Massachusetts, United States
• 26: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.224-234, June 15-19, 1992, San Francisco, California, United States
• 27: Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-19, November 01-05, 1999, Denver, Colorado, United States
• 28: John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.187-206, November 01-05, 1999, Denver, Colorado, United States
• 29: IBM Corp. Jikes, available at http://oss.software.ibm.com/developerworks/opensource/jike s/project/index.html.
• 30: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 31: Craig Chambers , David Ungar, Interactive type analysis and extended message splitting; optimizing dynamically-typed object-oriented programs, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.150-164, June 1990, White Plains, New York, United States
• 32: T. Suganuma , T. Ogasawara , M. Takeuchi , T. Yasue , M. Kawahito , K. Ishizaki , H. Komatsu , T. Nakatani, Overview of the IBM Java just-in-time compiler, IBM Systems Journal, v.39 n.1, p.175-193, January 2000
• 33: F. C. Chow, Minimizing register usage penalty at procedure calls, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.85-94, June 20-24, 1988, Atlanta, Georgia, United States
• 34: Standard Performance Evaluation Corp. SPEC JVM98 Benchmarks, available at http://www.spec.org/osg/jvm98/.
• 35: Standard Performance Evaluation Corp. SPECjbb2000 Benchmarks, available at http://www.spec.org/osg/jbb2000/.
• 36: IBM Corp. XML Parser for Java, available at http://alphaworks.ibm.com/tech/xml4j.
• 37: Sun Corp. JavaServerTM Web Development Kit (JSWDK) 1.0.1 Reference Implementation, available at http://java.sun.com/products/jsp/download.html.
• 38: Norman Hendrich. jfig, available at http://techwww.informatik.uni-hamburg.de/applets/javafig/
• 39: ICEsoft. ICE Browser, available at http://www.icesoft.no/
• 40: Sun Corp. HotJavaTM Browser, available at http://java.sun.com/products/hotjava/index.html
• 41: JUSTSYSTEM Corp. ICHITARO ARK for Java, available at http://www.justsystem.com/ark/index.html.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Java

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Design, Experimentation, Languages, Measurement, Performance, Theory