Design of a Reversible Stack Machine
Abstract
The architectures of current reversible low-level machines largely follow those of traditional register-based machines. Machines with a stack-based architecture provide an alternative to register-based machines in classical environments and promise improvements such as an unlimited number of simultaneously available operands, a more straightforward translation to machine code, or improved performance. A novel stack-based low-level machine for reversible environments will be presented in this work.
The novel machine’s instruction set is based on pairs of inverse instructions, which provide access to machine operations in both execution directions and ensure clean reversibility. The presented machine utilises five special-purpose registers and memory regions for the operand stack, executed instructions and runtime data. The machine’s instruction set consists of 36 instruction pairs, which allow the implementation of arithmetic, control flow, memory management, stack frames and recursive routine calls. A formal definition of every instruction variant is provided.
Furthermore, a translation scheme for the automated translation of RSSA programs into stack machine instructions is presented and analysed. All RSSA features can be mapped to stack machine instructions. Performance comparisons show that a virtual machine implementation of the novel machine is capable of achieving higher execution rates and reduced program execution times when compared to existing reversible runtime environments.