M. Anton Ertl
ABSTRACT
An interpreter can spend a significant part of its execution time on accessing arguments of virtual machine instructions. This paper explores two methods to reduce this overhead for virtual stack machines by caching top-of-stack values in (real machine) registers. The dynamic method is based on having, for every possible state of the cache, one specialized version of the whole interpreter; the execution of an instruction usually changes the state of the cache and the next instruction is executed in the version corresponding to the new state. In the static method a state machine that keeps track of the cache state is added to the compiler. Common instructions exist in specialized versions for several states, but it is not necessary to have a version of every instruction for every cache state. Stack manipulation instructions are optimized away.
- Bel73.James R. Bell. Threaded code. Communications of the A CM, 16(6):370-372, 1973. Google Scholar
Digital Library
- Bla77.Russell P. Blake. Exploring a stack architecture, iEEE Computer, 10(5):30-39, May 1977.Google ScholarDigital Library
- cc.comp. compilers. Usenet Newsgroup; archives available from ftp://primost, cs. wisc.edu.Google Scholar
- DM82.David R. Ditzel and H. R. McLellan. Register allocation for free: The C machine stack cache. In Symposium on Architectural Support/or Programming Languages and Systems, pages 48-56, 1982. Google ScholarDigital Library
- DV90.Eddy H. Debaere and Jan M. Van Campenhout. Interpretation and Instruction Path Coprocessing. The MIT Press, 1990. Google ScholarDigital Library
- FHP91.Christopher W. Fraser, Robert R. Henry, and Todd A. Proebsting. BURG Fast Optimal Instruction Selection and Tree Parsing, 1991. Available via anonymous ftp from kaese.cs.wisc.edu, file pub/burg, shar. Z.Google Scholar
- HFWZ87.John R. Hayes, Martin E. Fraeman, Robert L. Williams, and Thomas Zaremba. An architecture for the direct execution of the Forth programming language. In Architectural Support/or Programming Languages and Operating Systems (ASPLOS- II), pages 42-48, 1987. Google Scholar
- HL89.John Hayes and Susan Lee. The architecture of the SC32 Forth engine. Journal o/ Forth Application and Research, 5(4):493- 5O6, 1989.Google Scholar
- HP90.John L. Hennessy and David A. Patterson. Computer Architecture. A Quantitative Approach. Morgan Kaufman Publishers, 1990. Google ScholarDigital Library
- HS85.Makoto Hasekawa and Yoshiharu Shigei. High-speed top-of-stack scheme for interpreters: A management algorithm and its analysis. In International Symposium on Computer Archictecture (ISCA), pages 48- 54, 1985. Google ScholarDigital Library
- Kli81.Paul Klint. Interpretation techniques. Software--Practice and Experience, 11:963- 973, 1981.Google ScholarCross Ref
- Koo89.Philip J. Koopman, Jr. Stack Computers. Ellis Horwood Limited, 1989.Google Scholar
- Kra83.Glen Krasner, editor. Smalltalk-80: Bits of History, Words o/Advice. Addison-Wesley, 1983. Google ScholarDigital Library
- Pit87.Thomas Pittman. Two-level hybrid interpreter/native code execution for combined space-time efficiency. In Symposium on interpreters and Interpretive Techniques (SIGPLAN '87), pages 150-152, 1987. Google ScholarDigital Library
- PLG88.Eduardo Pelegrf-Llopart and Susan L. Graham. Optimal code generation for expression trees: An application of the BURS theory. In Fifteenth Annual A CM Symposium on Principles o/Programming Languages, pages 294-308, 1988. Google ScholarDigital Library
Index Terms
- Stack caching for interpreters
Recommendations
Stack caching for interpreters
An interpreter can spend a significant part of its execution time on accessing arguments of virtual machine instructions. This paper explores two methods to reduce this overhead for virtual stack machines by caching top-of-stack values in (real machine) ...
Stack Caching Using Split Data Caches
ISORCW '15: Proceedings of the 2015 IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing WorkshopsIn most embedded and general purpose architectures, stack data and non-stack data is cached together, meaning that writing to or loading from the stack may expel non-stack data from the data cache. Manipulation of the stack has a different memory access ...
Selective Victim Caching: A Method to Improve the Performance of Direct-Mapped Caches
Although direct-mapped caches suffer from higher miss ratios as compared to set-associative caches, they are attractive for today's high-speed pipelined processors that require very low access times. Victim caching was proposed by Jouppi [1] as an ...
Comments