Implementation of stack-based languages on register machines

Abstract

Languages with programmer-visible stacks (stack-based languages) are used widely, as intermediate languages (e.g., JavaVM), and as languages for human programmers (e.g., Forth, PostScript). However, the prevalent computer architecture is the register machine. This poses the problem of efficiently implementing stack-based languages on register machines. A straight-forward implementation of the stack consists of a memory area that contains the stack items, and a pointer to the top-of-stack item. The basic optimizations explored in this thesis are: Caching the frequently-accessed top-of-stack items in registers reduces stack access overhead, and combining stack-pointer updates eliminates most of them. This thesis examines these optimizations in the context of three basic implementation techniques: interpretation, compilation to native machine code, and translation to C. For interpreters, the optimizations eliminate about two real machine instructions per virtual machine instruction, resulting in speedups of 17%-31% (for Forth on a DecStation 3100). The techniques presented here for native-code compilation and translation to C achieve a speedup factor of 1.3-3 over traditional native code compilers and more than 3 over a straight-forward translator to C (for Forth on a 486DX2/66).