The case for virtual register machines

ABSTRACT

Virtual machines (VMs) are a popular target for language implementers. Conventional wisdom tells us that virtual stack architectures can be implemented with an interpreter more efficiently, since the location of operands is implicit in the stack pointer. In contrast, the operands of register machine instructions must be specified explicitly. In this paper, we present a working system for translating stack-based Java virtual machine (JVM) code to a simple register code. We describe the translation process, the complicated parts of the JVM which make translation more difficult, and the optimisations needed to eliminate copy instructions. Experimental results show that a register format reduces the number of executed instructions by 34.88%, while increasing the number of bytecode loads by an average of 44.81%. Overall, this corresponds to an increase of 2.32 loads for each dispatch removed. We believe that the high cost of dispatches makes register machines attractive even at the cost of increased loads.

REFERENCES

• 1: M. Bull, L. Smith, M. Westhead, D. Henty, and R. Davey. Benchmarking Java Grande applications. In Second International Conference and Exhibition on the Practical Application of Java, Manchester, UK, April 2000.
• 2: 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
• 3: M. Anton Ertl , David Gregg, The Behavior of Efficient Virtual Machine Interpreters on Modern Architectures, Proceedings of the 7th International Euro-Par Conference Manchester on Parallel Processing, p.403-412, August 28-31, 2001
• 4: M. Anton Ertl , David Gregg , Andreas Krall , Bernd Paysan, Vmgen: a generator of efficient virtual machine interpreters, Software—Practice & Experience, v.32 n.3, p.265-294, March 2002 [doi>10.1002/spe.434]
• 5: Etienne Gagnon , Laurie J. Hendren, A portable research framework for the execution of java bytecode, 2003
• 6: E. Gagnon and L. Hendren. SableVM: A research framework for the efficient execution of Java bytecode. In First USENIX Java Virtual Machine Research and Technology Symposium, Monterey, California, April 2001.
• 7: E. Gagnon and L. Hendren. Effective inline-threaded interpretation of java bytecode using preparation sequences. In Proceedings of the 12th International Conference on Compiler Construction, LNCS 2622, pages 170--184, April 2003.
• 8: D. Gregg, A. Ertl, and A. Krall. A fast java interpreter. In Proceedings of the Workshop on Java optimisaton strategies for embedded systems (JOSES), Genoa, April 2001.
• 9: Jan Hoogerbrugge , Lex Augusteijn , Jeroen Trum , Rik Van De Wiel, A code compression system based on pipelined interpreters, Software—Practice & Experience, v.29 n.11, p.1005-2023, Sept. 1999 [doi>10.1002/(SICI)1097-024X(199909)29:11<1005::AID-SPE270>3.0.CO;2-F]
• 10: Glenford J. Myers, The case against stack-oriented instruction sets, ACM SIGARCH Computer Architecture News, v.6 n.3, p.7-10, August 1977 [doi>10.1145/859402.859403]
• 11: 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
• 12: Todd A. Proebsting, Optimizing an ANSI C interpreter with superoperators, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.322-332, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199526]
• 13: Vítor Santos Costa, Optimising Bytecode Emulation for Prolog, Proceedings of the International Conference PPDP'99 on Principles and Practice of Declarative Programming, p.261-277, September 29-October 01, 1999
• 14: SPEC. SPEC releases SPEC JVM98, first industry-standard benchmark for measuring Java virtual machine performance. Press Release, August 19 1998. http://www.specbench.org/osg/jvm98/press.html.
• 15: D. Sugalski. http://www.parrotcode.org/.
• 16: John Waldron, Dynamic Bytecode Usage by Object Oriented Java Programs, Proceedings of the Technology of Object-Oriented Languages and Systems, p.384, June 07-10, 1999

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.0 General

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

Keywords:
interpreter, register architecture, stack architecture, virtual machine