YETI: a graduallY extensible trace interpreter

ABSTRACT

The design of new programming languages benefits from interpretation, which can provide a simple initial implementation, flexibility to explore new language features, and portability to many platforms. The only downside is speed of execution, as there remains a large performance gap between even efficient interpreters and mixed-mode systems that include a just-in-time compiler (or JIT for short). Augmenting an interpreter with a JIT, however, is not a small task. Today, JITs used for Java™ are loosely-coupled with the interpreter, with callsites of methods being the only transition point between interpreted and native code. To compile whole methods, the JIT must duplicate a sizable amount of functionality already provided by the interpreter, leading to a "big bang" development effort before the JIT can be deployed. Instead, adding a JIT to an interpreter would be easier if it were possible to leverage the existing functionality.

In earlier work we showed that packaging virtual instructions as lightweight callable routines is an efficient way to build an interpreter. In this paper we describe how callable bodies help our interpreter to efficiently identify and run traces. Our closely coupled dynamic compiler can fall back on the interpreter in various ways, permitting an incremental approach in which additional performance gains can be realized as it is extended in two dimensions: (i) generating code for more types of virtual instructions, and (ii) identifying larger compilation units. Currently, Yeti identifies straight line regions of code and traces, and generates non-optimized code for roughly 50 Java integer and object bytecodes. Yeti runs roughly twice as fast as a direct-threaded interpreter on SPECjvm98 benchmarks.

REFERENCES

• 1: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 2: Marc Berndl , Benjamin Vitale , Mathew Zaleski , Angela Demke Brown, Context Threading: A Flexible and Efficient Dispatch Technique for Virtual Machine Interpreters, Proceedings of the international symposium on Code generation and optimization, p.15-26, March 20-23, 2005 [doi>10.1109/CGO.2005.14]
• 3: D. Bruening and E. Duesterwald. Exploring optimal compilation unit shapes for an embedded just-in-time compiler. In Proc. of the 3rd ACM Workshop on Feedback-Directed and Dynamic Optimization (FDDO-3), Dec. 2000.
• 4: Derek Bruening , Timothy Garnett , Saman Amarasinghe, An infrastructure for adaptive dynamic optimization, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 5: W.-K. Chen, S. Lerner, R. Chaiken, and D. Gillies. Mojo: A dynamic optimization system. In Proc. of the 3rd ACMWorkshop on Feedback-Directed and Dynamic Optimization (FDDO-3), Dec. 2000.
• 6: James C. Dehnert , Brian K. Grant , John P. Banning , Richard Johnson , Thomas Kistler , Alexander Klaiber , Jim Mattson, The Transmeta Code Morphing™ Software: using speculation, recovery, and adaptive retranslation to address real-life challenges, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 7: Karl Driesen , Karel Driesen, Efficient Polymorphic Calls, Kluwer Academic Publishers, Norwell, MA, 2001
• 8: Evelyn Duesterwald , Vasanth Bala, Software profiling for hot path prediction: less is more, ACM SIGPLAN Notices, v.35 n.11, p.202-211, Nov. 2000 [doi>10.1145/356989.357008]
• 9: M. Anton Ertl, Stack caching for interpreters, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.315-327, June 18-21, 1995, La Jolla, California, United States
• 10: M. Anton Ertl , David Gregg, Optimizing indirect branch prediction accuracy in virtual machine interpreters, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 11: E. Gagnon and L. Hendren. Effective inline threading of Java bytecode using preparation sequences. In Proc. of the 12th Intl. Conf. on Compiler Construction, volume 2622 of Lecture Notes in Computer Science, pages 170--184. Springer, Apr. 2003.
• 12: Andreas Gal , Christian W. Probst , Michael Franz, HotpathVM: an effective JIT compiler for resource-constrained devices, Proceedings of the 2nd international conference on Virtual execution environments, June 14-16, 2006, Ottawa, Ontario, Canada [doi>10.1145/1134760.1134780]
• 13: Kim Hazelwood , David Grove, Adaptive online context-sensitive inlining, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 14: David Hiniker , Kim Hazelwood , Michael D. Smith, Improving Region Selection in Dynamic Optimization Systems, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.141-154, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.22]
• 15: U. Hölzle. Adaptive Optimization For Self:Reconciling High Performance With Exploratory Programming. PhD thesis, Stanford University, 1994.
• 16: R. Lougher. JamVM {online}. Available from: http://jamvm.sourceforge.net/.
• 17: Michael Paleczny , Christopher Vick , Cliff Click, The java hotspot^TM server compiler, Proceedings of the Java^TM Virtual Machine Research and Technology Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.1-1, April 23-24, 2001, Monterey, California
• 18: Igor Pechtchanski , Vivek Sarkar, Dynamic optimistic interprocedural analysis: a framework and an application, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.195-210, October 14-18, 2001, Tampa Bay, FL, USA
• 19: I. Piumarta. Ccg: A tool for writing dynamic code generators. In OOPSLA'99 Workshop on simplicity, performance and portability in virtual machine design, Nov. 1999.
• 20: Ian Piumarta , Fabio Riccardi, Optimizing direct threaded code by selective inlining, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.291-300, June 17-19, 1998, Montreal, Quebec, Canada
• 21: SPECjvm98 benchmarks {online}. 1998. Available from: http://www.spec.org/osg/jvm98/.
• 22: D. Sugalski. Implementing an interpreter {online}. Available from: http://www.sidhe.org/%7Edan/presentations/Parrot%20Implementation.ppt. Notes for slide 21.
• 23: 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
• 24: Toshio Suganuma , Toshiaki Yasue , Toshio Nakatani, A region-based compilation technique for dynamic compilers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.1, p.134-174, January 2006 [doi>10.1145/1111596.1111600]
• 25: Vijay Sundaresan , Daryl Maier , Pramod Ramarao , Mark Stoodley, Experiences with Multi-threading and Dynamic Class Loading in a Java Just-In-Time Compiler, Proceedings of the International Symposium on Code Generation and Optimization, p.87-97, March 26-29, 2006 [doi>10.1109/CGO.2006.16]
• 26: David Ungar , Randall B. Smith , Craig Chambers , Urs Hölzle, Object, Message, and Performance: How they Coexist in Self, Computer, v.25 n.10, p.53-64, October 1992 [doi>10.1109/2.161280 ]
• 27: John Whaley, Partial method compilation using dynamic profile information, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.166-179, October 14-18, 2001, Tampa Bay, FL, USA

INDEX TERMS

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

General Terms:
Design, Languages, Performance

Keywords:
JIT compiler, interpreter, mixed-mode, trace