Interpreting programs in static single assignment form

ABSTRACT

Optimizing compilers, including those in virtual machines, commonly utilize Static Single Assignment Form as their intermediate representation, but interpreters typically implement stack-oriented virtual machines. This paper introduces an easily interpreted variant of Static Single Assignment Form. Each instruction of this Interpretable Static Single Assignment Form, including the Phi Instruction, has self-contained operational semantics facilitating efficient interpretation. Even the array manipulation instructions possess directly-executable single-assignment semantics. In addition, this paper describes the construction of a prototype virtual machine realizing Interpretable Static Single Assignment Form and reports on its performance.

REFERENCES

• 1: Ole Agesen , David Detlefs, Mixed-mode Bytecode Execution, Sun Microsystems, Inc., Mountain View, CA, 2000
• 2: B. Alpern , M. N. Wegman , F. K. Zadeck, Detecting equality of variables in programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73561]
• 3: Wolfram Amme , Niall Dalton , Jeffery von Ronne , Michael Franz, SafeTSA: a type safe and referentially secure mobile-code representation based on static single assignment form, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.137-147, June 2001, Snowbird, Utah, United States
• 4: W. Amme, J. von Ronne, and M. Franz. Using the SafeTSA representation to boost the performance of an existing java virtual machine. In 10th International Workshop on Compilers for Parallel Computers, Jan. 2003.
• 5: C. S. Ananian. The static single information form. Master's thesis, Massachusetts Institute of Technology, Cambridge, Massachussetts, Sept. 1999.
• 6: Karl J. Ottenstein , Robert A. Ballance , Arthur B. MacCabe, The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.257-271, June 1990, White Plains, New York, United States
• 7: James R. Bell, Threaded code, Communications of the ACM, v.16 n.6, p.370-372, June 1973 [doi>10.1145/362248.362270]
• 8: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 9: Brian Davis , Andrew Beatty , Kevin Casey , David Gregg , John Waldron, The case for virtual register machines, Proceedings of the 2003 workshop on Interpreters, virtual machines and emulators, p.41-49, June 12-12, 2003, San Diego, California [doi>10.1145/858570.858575]
• 10: Robert B. K. Dewar, Indirect threaded code, Communications of the ACM, v.18 n.6, p.330-331, June 1975 [doi>10.1145/360825.360849]
• 11: 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
• 12: 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
• 13: 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]
• 14: Etienne Gagnon , Laurie J. Hendren, A portable research framework for the execution of java bytecode, 2003
• 15: A. Hartmann, W. Amme, J. von Ronne, and M. Franz. Code annotation for safe and efficient dynamic object resolution. In 2nd International Workshop on Compiler Optimization Meets Compiler Verification, Apr. 2003.
• 16: P. Klint. Interpretation techniques. In Software-Practice and Experience, pages 11:963--973, 1981.
• 17: Kathleen Knobe , Vivek Sarkar, Array SSA form and its use in parallelization, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.107-120, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268956]
• 18: Chandra Krintz, Improving mobile program performance through the use of a hybrid intermediate representation, Proceedings of the inaugural conference on the Principles and Practice of programming, 2002 and Proceedings of the second workshop on Intermediate representation engineering for virtual machines, 2002, June 13-14, 2002, Dublin, Ireland
• 19: Robert Morgan, Building an optimizing compiler, Digital Press, Newton, MA, 1998
• 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: 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]
• 22: B. K. Rosen , M. N. Wegman , F. K. Zadeck, Global value numbers and redundant computations, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-27, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73562]
• 23: J. von Ronne, M. Franz, N. Dalton, and W. Amme. Compile time elimination of null- and bounds-checks. In 9th Workshop on Compilers for Parallel Computers, June 2001.
• 24: J. von Ronne, A. Hartmann, W. Amme, and M. Franz. Efficient online optimization by utilizing offline analysis and the SafeTSA representation. In J. F. Power and J. T. Waldron, editors, Recent Advances in Java Technology: Theory, Application, Implementation, chapter 27, pages 233--241. Computer Science Press, Trinity College Dublin, 2002.
• 25: J. von Ronne, N. Wang, A. Apel, and M. Franz. A virtual machine for interpreting programs in static single assignment form. Technical Report 03-19, Information and Computer Science, Univeristy of California, Irvine, Oct. 2003.