Optimizing an ANSI C interpreter with superoperators

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimizing an ANSI C interpreter with superoperators

Full text

Pdf (952 KB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

San Francisco, California, United States

Pages: 322 - 332

Year of Publication: 1995

ISBN:0-89791-692-1

Author

Todd A. Proebsting

Department of Computer Science, University of Arizona, Tucson, AZ

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 33, Citation Count: 46

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/199448.199526 What is a DOI?

ABSTRACT

This paper introduces superoperators, an optimization technique for bytecoded interpreters. Superoperators are virtual machine operations automatically synthesized from smaller operations to avoid costly per-operation overheads. Superoperators decrease executable size and can double or triple the speed of interpreted programs. The paper describes a simple and effective heuristic for inferring powerful superoperators from the usage patterns of simple operators.The paper describes the design and implementation of a hybrid translator/interpreter that employs superoperators. From a specification of the superoperators (either automatically inferred or manually chosen), the system builds an efficient implementation of the virtual machine in assembly language. The system is easily retargetable and currently runs on the MIPS R3000 and the SPARC.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Bel73	James R. Bell, Threaded code, Communications of the ACM, v.16 n.6, p.370-372, June 1973 [doi>10.1145/362248.362270]
	DG87	J. W. Davidson , J. V. Gresh, Cint: a RISC interpreter for the C programming language, Papers of the Symposium on Interpreters and interpretive techniques, p.189-198, June 24-26, 1987, St. Paul, Minnesota, United States
	Feu85	Alan R. Feuer. si # an interpreter for the C language. In Proceedings of the 1985 Usenix Summer Conference, Portland, OR, June 1985.
	FH88	Anthony J. Field and Peter G. Harrison. Functional Programming. Addison Wesley, 1988.
	FH91a	Christopher W. Fraser , David R. Hanson, A code generation interface for ANSI C, Software—Practice & Experience, v.21 n.9, p.963-988, Sept. 1991 [doi>10.1002/spe.4380210906]
	FH91b	Christopher W. Fraser, A retargetable compiler for ANSI C, ACM SIGPLAN Notices, v.26 n.10, p.29-43, Oct. 1991 [doi>10.1145/122616.122621]
	FHP92	Christopher W. Fraser , Robert R. Henry , Todd A. Proebsting, BURG: fast optimal instruction selection and tree parsing, ACM SIGPLAN Notices, v.27 n.4, p.68-76, April 1992 [doi>10.1145/131080.131089]
	GG90	Ralph E. Griswold , Madge T. Griswold, The ICON Programming Language, 2nd Ed., Prentice Hall Professional Technical Reference, 1990
	GJ79	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	KH92	Gerry Kane , Joe Heinrich, MIPS RISC architectures, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
	Kli81	Paul t#lint.. Interpretation techniques. \|Software--Practice and Experience,#1(10):963-973, October 1981. !
	KLP88	StephenlKaufer, Russell Lopez, and Sesha Pra#ap.# Saber-C: An interpreterbased programming environment for the C language. In Proceedings of the 1988 Usenix Summer Conference, San Francisco, CA, June 1988.
	Pit87	T. Pittman, Two-level hybrid interpreter/native code execution for combined space-time program efficiency, Papers of the Symposium on Interpreters and interpretive techniques, p.150-152, June 24-26, 1987, St. Paul, Minnesota, United States
	Sun91	Sun Microsystems, Inc. The SPARC Architec!ure Manual (Version 8), 1991.

CITED BY 46

	Kevin Casey , M. Anton Ertl , David Gregg, Optimizing indirect branch prediction accuracy in virtual machine interpreters, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.6, p.37-es, October 2007
	Jens Ernst , William Evans , Christopher W. Fraser , Todd A. Proebsting , Steven Lucco, Code compression, ACM SIGPLAN Notices, v.32 n.5, p.358-365, May 1997
	William S. Evans , Christopher W. Fraser, Bytecode compression via profiled grammar rewriting, ACM SIGPLAN Notices, v.36 n.5, p.148-155, May 2001
	Norman Ramsey, Relocating machine instructions by currying, ACM SIGPLAN Notices, v.31 n.5, p.226-236, May 1996
	Michael P. Plezbert , Ron K. Cytron, Does “just in time” = “better late than never”?, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.120-131, January 15-17, 1997, Paris, France
	Christopher W. Fraser, Automatic inference of models for statistical code compression, ACM SIGPLAN Notices, v.34 n.5, p.242-246, May 1999
	Matthai Philipose , Craig Chambers , Susan J. Eggers, Towards automatic construction of staged compilers, ACM SIGPLAN Notices, v.37 n.1, p.113-125, Jan. 2002
	Henrik Nässén , Mats Carlsson , Konstantinos Sagonas, Instruction merging and specialization in the SICStus Prolog virtual machine, Proceedings of the 3rd ACM SIGPLAN international conference on Principles and practice of declarative programming, p.49-60, September 05-07, 2001, Florence, Italy
	Lars Ræder Clausen , Ulrik Pagh Schultz , Charles Consel , Gilles Muller, Java bytecode compression for low-end embedded systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.3, p.471-489, May 2000
	Saumya K. Debray , William Evans , Robert Muth , Bjorn De Sutter, Compiler techniques for code compaction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.378-415, March 2000
	Ben Stephenson , Wade Holst, Multicodes: optimizing virtual machines using bytecode sequences, Companion of the 18th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 26-30, 2003, Anaheim, CA, USA
	Mario Latendresse , Marc Feeley, Generation of fast interpreters for Huffman compressed bytecode, Proceedings of the 2003 workshop on Interpreters, virtual machines and emulators, p.32-40, June 12-12, 2003, San Diego, California
	Milenko Drinić , Darko Kirovski , Hoi Vo, Code optimization for code compression, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
	M. Anton Ertl , David Gregg, Optimizing indirect branch prediction accuracy in virtual machine interpreters, ACM SIGPLAN Notices, v.38 n.5, May 2003
	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
	Andrew Beatty , Kevin Casey , David Gregg , Andrew Nisbet, An optimized Java interpreter for connected devices and embedded systems, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
	Uwe Kastens , Dinh Khoi Le , Adrian Slowik , Michael Thies, Feedback driven instruction-set extension, ACM SIGPLAN Notices, v.39 n.7, July 2004
	Kelvin Lin , Jean Jyh-Jiun Shann , Chung-Ping Chung, Code compression by register operand dependency, Journal of Systems and Software, v.72 n.3, p.295-304, August 2004
	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
	Brian Davis , John Waldron, A survey of optimisations for the Java Virtual Machine, Proceedings of the 2nd international conference on Principles and practice of programming in Java, June 16-18, 2003, Kilkenny City, Ireland
	Ana Azevedo , Arun Kejariwal , Alex Veidenbaum , Alexandru Nicolau, High performance annotation-aware JVM for Java cards, Proceedings of the 5th ACM international conference on Embedded software, September 18-22, 2005, Jersey City, NJ, USA
	Bjorn De Sutter , Bruno De Bus , Koen De Bosschere, Link-time binary rewriting techniques for program compaction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.5, p.882-945, September 2005
	Saumya Debray , William Evans, Profile-guided code compression, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Joel Koshy , Raju Pandey, VMSTAR: synthesizing scalable runtime environments for sensor networks, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA
	Ben Stephenson , Wade Holst, A quantitative analysis of Java bytecode sequences, Proceedings of the 3rd international symposium on Principles and practice of programming in Java, June 16-18, 2004, Las Vegas, Nevada
	Jinzhan Peng , Gansha Wu , Guei-Yuan Lueh, Code sharing among states for stack-caching interpreter, Proceedings of the 2004 workshop on Interpreters, virtual machines and emulators, June 07-07, 2004, Washington, D.C.
	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
	Mathew Zaleski , Marc Berndl , Angela Demke Brown, Mixed mode execution with context threading, Proceedings of the 2005 conference of the Centre for Advanced Studies on Collaborative research, p.305-319, October 17-20, 2005, Toranto, Ontario, Canada
	Jeffery von Ronne , Ning Wang , Michael Franz, Interpreting programs in static single assignment form, Proceedings of the 2004 workshop on Interpreters, virtual machines and emulators, June 07-07, 2004, Washington, D.C.
	William S. Evans , Christopher W. Fraser, Grammar-based compression of interpreted code, Communications of the ACM, v.46 n.8, August 2003
	Christopher W. Fraser, An instruction for direct interpretation of LZ77-compressed programs, Software—Practice & Experience, v.36 n.4, p.397-411, April 2006
	M. Anton Ertl , David Gregg, Retargeting JIT Compilers by using C-Compiler Generated Executable Code, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.41-50, September 29-October 03, 2004
	Guido Araujo , Paulo Centoducatte , Mario Cartes , Ricardo Pannain, Code compression based on operand factorization, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.194-201, November 1998, Dallas, Texas, United States
	Geoff A. Cohen , Jeffrey S. Chase , David L. Kaminsky, Automatic program transformation with JOIE, Proceedings of the Annual Technical Conference on USENIX Annual Technical Conference, 1998, p.14-14, June 15-19, 1998, New Orleans, Louisiana
	Bertrand Anckaert , Mariusz Jakubowski , Ramarathnam Venkatesan, Proteus: virtualization for diversified tamper-resistance, Proceedings of the ACM workshop on Digital rights management, October 30-30, 2006, Alexandria, Virginia, USA
	Mario Latendresse , Marc Feeley, Generation of fast interpreters for Huffman compressed bytecode, Science of Computer Programming, v.57 n.3, p.295-317, September 2005
	David Gregg , Andrew Beatty , Kevin Casey , Brain Davis , Andy Nisbet, The case for virtual register machines, Science of Computer Programming, v.57 n.3, p.319-338, September 2005
	Milenko Drinić , Darko Kirovski , Hoi Vo, PPMexe: Program compression, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.1, p.3-es, January 2007
	K. S. Venugopal , Geetha Manjunath , Venkatesh Krishnan, sEc: A Portable Interpreter Optimizing Technique for Embedded Java Virtual Machine, Proceedings of the 2nd Java™ Virtual Machine Research and Technology Symposium, p.127-138, August 01-02, 2002
	O. Ozturk , H. Saputra , M. Kandemir , I. Kolcu, Access Pattern-Based Code Compression for Memory-Constrained Embedded Systems, Proceedings of the conference on Design, Automation and Test in Europe, p.882-887, March 07-11, 2005
	Carmen Badea , Alexandru Nicolau , Alexander V. Veidenbaum, A simplified java bytecode compilation system for resource-constrained embedded processors, Proceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems, September 30-October 03, 2007, Salzburg, Austria
	David Wakeling, The dynamic compilation of lazy functional programs, Journal of Functional Programming, v.8 n.1, p.61-81, January 1998
	Joel Koshy , Ingwar Wirjawan , Raju Pandey , Yann Ramin, Balancing computation and communication costs: The case for hybrid execution in sensor networks, Ad Hoc Networks, v.6 n.8, p.1185-1200, November, 2008
	Dominique Chanet , Bjorn De Sutter , Bruno De Bus , Ludo Van Put , Koen De Bosschere, Automated reduction of the memory footprint of the Linux kernel, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.4, p.23-es, September 2007
	Carmen Badea , Alexandru Nicolau , Alexander V. Veidenbaum, Impact of JVM superoperators on energy consumption in resource-constrained embedded systems, ACM SIGPLAN Notices, v.43 n.7, July 2008
	Ozcan Ozturk , Mahmut Kandemir , Guangyu Chen, Access pattern-based code compression for memory-constrained systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.13 n.4, p.1-30, September 2008