Quicksilver: a quasi-static compiler for Java

ABSTRACT

This paper presents the design and implementation of the Quicksilver¹ quasi-static compiler for Java. Quasi-static compilation is a new approach that combines the benefits of static and dynamic compilation, while maintaining compliance with the Java standard, including support of its dynamic features. A quasi-static compiler relies on the generation and reuse of persistent code images to reduce the overhead of compilation during program execution, and to provide identical, testable and reliable binaries over different program executions. At runtime, the quasi-static compiler adapts pre-compiled binaries to the current JVM instance, and uses dynamic compilation of the code when necessary to support dynamic Java features. Our system allows interprocedural program optimizations to be performed while maintaining binary compatibility. Experimental data obtained using a preliminary implementation of a quasi-static compiler in the Jalapeño JVM clearly demonstrates the benefits of our approach: we achieve a runtime compilation cost comparable to that of baseline (fast, non-optimizing) compilation, and deliver the runtime program performance of the highest optimization level supported by the Jalapeño optimizing compiler. For the SPECjvm98 benchmark suite, we obtain a factor of 104 to 158 reduction in the runtime compilation overhead relative to the Jalapeño optimizing compiler. Relative to the better of the baseline and the optimizing Jalapeño compilers, the overall performance (taking into account both runtime compilation and execution costs) is increased by 9.2% to 91.4% for the SPECjvm98 benchmarks with size 100, and by 54% to 356% for the (shorter running) SPECjvm98 benchmarks with size 10.

REFERENCES

• 1: Rolf Adams , Walter Tichy , Annette Weinert, The cost of selective recompilation and environment processing, ACM Transactions on Software Engineering and Methodology (TOSEM), v.3 n.1, p.3-28, Jan. 1994 [doi>10.1145/174634.174637]
• 2: B. Alpern , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
• 3: Bowen Alpern , C. R. Attanasio , Anthony Cocchi , Derek Lieber , Stephen Smith , Ton Ngo , John J. Barton , Susan Flynn Hummel , Janice C. Sheperd , Mark Mergen, Implementing jalapeño in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.314-324, November 01-05, 1999, Denver, Colorado, United States
• 4: 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
• 5: Matthew Arnold , Stephen Fink , David Grove , Michael Hind , Peter F. Sweeney, Adaptive optimization in the Jalapeño JVM, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.47-65, October 2000, Minneapolis, Minnesota, United States
• 6: A. Azevedo, A. Nicolau, and J. Hummel. An annotation aware Java virtual machine implementation. In Proc. ACM SIGPLAN I999 Java Grande Conference, June 1999.
• 7: S. J. Baylor , M. Devarakonda , S. J. Fink , E. Gluzberg , M. Kalantar , P. Muttineni , E. Barsness , R. Arora , R. Dimpsey , S. J. Munroe, Java server benchmarks, IBM Systems Journal, v.39 n.1, p.57-81, January 2000
• 8: Peter Buhler and Thomas Eirich. private communication.
• 9: Michael Burke , Linda Torczon, Interprocedural optimization: eliminating unnecessary recompilation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.3, p.367-399, July 1993 [doi>10.1145/169683.169678]
• 10: Craig Chambers , Jeffrey Dean , David Grove, A framework for selective recompilation in the presence of complex intermodule dependencies, Proceedings of the 17th international conference on Software engineering, p.221-230, April 24-28, 1995, Seattle, Washington, United States [doi>10.1145/225014.225035]
• 11: Hewlett-Packard Company. Chai products. http ://www.hp.com/emso/products/chaivm.
• 12: Charles Consel , François Noël, A general approach for run-time specialization and its application to C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.145-156, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237767]
• 13: Microsoft Corporation. MS SDK for Java 4.0. http ://www.microsoft.com/java/vm.htm.
• 14: The Standard Performance Evaluation Corporation. SPEC JVM98 Benchmarks, 1998. http ://www.spec.org/osg/jvm98.
• 15: 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
• 16: D. Dillenberger , R. Bordawekar , C. W. Clark, III , D. Durand , D. Emmes , O. Gohda , S. Howard , M. F. Oliver , F. Samuel , R. W. St. John, Building a Java virtual machine for server applications: the Jvm on 0S/390, IBM Systems Journal, v.39 n.1, p.194-210, January 2000
• 17: Encyclopedia Britannica Online. Information available via search at http://www.eb.com.
• 18: Proposed Federal Information Processing Standard for Secure Hash Standard. Federal Register, 57(21):3747-3749, 31, January 1992.
• 19: R. Fitzgerald, T. Knoblock, E. Ruf, B. Steensgard, and D. Tarditi. Marmot: An optimizing compiler for Java. Technical Report 33, Microsoft Research, June 1999.
• 20: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 21: Brian Grant , Matthai Philipose , Markus Mock , Craig Chambers , Susan J. Eggers, An evaluation of staged run-time optimizations in DyC, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.293-304, May 01-04, 1999, Atlanta, Georgia, United States
• 22: The Java Hotspot Pen%rmance Engine Architecture. http://java.sun.com/products/hotspot/ whitepaper, html.
• 23: NaturalBridge Inc. BuUetTrain optimizing compiler and rtmtime for JVM bytecodes. http://www.naturalbridge.com/bullettrain.html.
• 24: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 25: Mick Jordan , Malcolm Atkinson, Orthogonal Persistence for the Java[tm] Platform: Specification and Rationale, Sun Microsystems, Inc., Mountain View, CA, 2000
• 26: Jove. Jove, super optimizing deployment environment for Java. http://www.instantiations.com/javaspeed/ jovereport, htm.
• 27: Chandra Krintz , David Grove , Derek Lieber , Vivek Sarkar , Brad Calder, Reducing the Overhead of Compilation Delay, University of California at San Diego, La Jolla, CA, 2000
• 28: Mark Leone , Peter Lee, Dynamic specialization in the Fabius system, ACM Computing Surveys (CSUR), v.30 n.3es, Sept. 1998 [doi>10.1145/289121.289144]
• 29: Sheng Liang , Gilad Bracha, Dynamic class loading in the Java virtual machine, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.36-44, October 18-22, 1998, Vancouver, British Columbia, Canada
• 30: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 31: Sun Microsystems. Java2 Platform, Standard Edition Documentation. http://java.sun.com/docs/index.html.
• 32: Sun Microsystems. Embedded Java(TM) application environment. http://j ava. sun. com/product s/embeddedj ava/.
• 33: George C. Necula, Proof-carrying code, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.106-119, January 15-17, 1997, Paris, France [doi>10.1145/263699.263712]
• 34: Hirotaka Ogawa , Kouya Shimura , Satoshi Matsuoka , Fuyuhiko Maruyama , Yukihiko Sohda , Yasunori Kimura, OpenJIT: An Open-Ended, Reflective JIT Compiler Framework for Java, Proceedings of the 14th European Conference on Object-Oriented Programming, p.362-387, June 12-16, 2000
• 35: P. Richards and D. Hicks. Virtual integration. AS/400, pages 50-56, March 1998.
• 36: Bruce Schneier, Applied cryptography (2nd ed.): protocols, algorithms, and source code in C, John Wiley & Sons, Inc., New York, NY, 1995
• 37: V. Seshadri. IBM High Performance Compiler for Java. AIXpert Magazine, September 1997. http ://www.developer.ibm.com/library/aixpert.
• 38: Vugranam C. Sreedhar , Michael Burke , Jong-Deok Choi, A framework for interprocedural optimization in the presence of dynamic class loading, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.196-207, June 18-21, 2000, Vancouver, British Columbia, Canada
• 39: 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
• 40: Tower Technology Corporation. Tower J3 - a new generation native Java compiler and runtime environment. http://www.towerj.com/products/whitepapergnj.shtml.
• 41: Byung-Sun Yang , Soo-Mook Moon , Seongbae Park , Junpyo Lee , SeungIl Lee , Jinpyo Park , Yoo C. Chung , Suhyun Kim , Kemal Ebcioglu , Erik Altman, LaTTe: A Java VM Just-in-Time Compiler with Fast and Efficient Register Allocation, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.128, October 12-16, 1999

INDEX TERMS

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