In computer science, computer engineering and programming language implementations, a stack machine is a computer processor or a process virtual machine in which the primary interaction is moving short-lived temporary values to and from a push-down stack. In the case of a hardware processor, a hardware stack is used. The use of a stack significantly reduces the required number of processor registers. Stack machines extend push-down automata with additional load/store operations or multiple stacks and hence are Turing-complete.

Design

Most or all stack machine instructions assume that operands will be from the stack, and results placed in the stack. The stack easily holds more than two inputs or more than one result, so a rich set of operations can be computed. In stack machine code (sometimes called p-code), instructions will frequently have only an opcode commanding an operation, with no additional fields identifying a constant, register or memory cell, known as a zero address format. This greatly simplifies instruction decoding. Branches, load immediates, and load/store instructions require an argument field, but stack machines often arrange that the frequent cases of these still fit together with the opcode into a compact group of bits. The selection of operands from prior results is done implicitly by ordering the instructions. Some stack machine instruction sets are intended for interpretive execution of a virtual machine, rather than driving hardware directly.

Integer constant operands are pushed by or instructions. Memory is often accessed by separate or instructions containing a memory address or calculating the address from values in the stack. All practical stack machines have variants of the load–store opcodes for accessing local variables and formal parameters without explicit address calculations. This can be by offsets from the current top-of-stack address, or by offsets from a stable frame-base register.

The instruction set carries out most ALU actions with postfix (reverse Polish notation) operations that work only on the expression stack, not on data registers or main memory cells. This can be very convenient for executing high-level languages because most arithmetic expressions can be easily translated into postfix notation.

thumb|Binary syntax tree for the expression A*(B−C) + (D+E)

For example, consider the expression A*(B−C)+(D+E), written in reverse Polish notation as A B C − * D E + +. Compiling and running this on a simple imaginary stack machine would take the form:

  1. stack contents (leftmost = top = most recent):

push A # A

push B # B A

push C # C B A

subtract # B−C A

multiply # A*(B−C)

push D # D A*(B−C)

push E # E D A*(B−C)

add # D+E A*(B−C)

add # A*(B−C)+(D+E)

The arithmetic operations "subtract", "multiply", and "add" act on the two topmost operands of the stack. The computer takes both operands from the topmost (most recent) values of the stack. The computer replaces those two values with the calculated difference, sum, or product. In other words the instruction's operands are "popped" off the stack, and its result(s) are then "pushed" back onto the stack, ready for the next instruction.

Stack machines may have their expression stack and their call-return stack separated or as one integrated structure. If they are separated, the instructions of the stack machine can be pipelined with fewer interactions and less design complexity, so it will usually run faster.

Optimisation of compiled stack code is quite possible. Back-end optimisation of compiler output has been demonstrated to significantly improve code,

  • Tandem Computers T/16. Like HP 3000, except that compilers, not microcode, controlled when the register stack spilled to the memory stack or was refilled from the memory stack.
  • the Atmel MARC4 microcontroller The C API still is as of version 5.x.
  • the TON Virtual Machine (TVM) for The Open Network smart contracts
  • Apple's TrueType font system has a primarily stack based instruction set, with a separate storage section indexed by number.

Hybrid machines

Pure stack machines are quite inefficient for procedures which access multiple fields from the same object. The stack machine code must reload the object pointer for each pointer+offset calculation. A common fix for this is to add some register-machine features to the stack machine: a visible register file dedicated to holding addresses, and register-style instructions for doing loads and simple address calculations. It is uncommon to have the registers be fully general purpose, because then there is no strong reason to have an expression stack and postfix instructions.

Another common hybrid is to start with a register machine architecture, and add another memory address mode which emulates the push or pop operations of stack machines: "memaddress = reg; reg += instr.displ". This was first used in DEC's PDP-11 minicomputer.

</references>

  • Homebrew CPU in an FPGA &mdash; homebrew stack machine using FPGA
  • Mark 1 FORTH Computer &mdash; homebrew stack machine using discrete logical circuits
  • Mark 2 FORTH Computer &mdash; homebrew stack machine using bitslice/PLD
  • Second-Generation Stack Computer Architecture &mdash; Thesis about the history and design of stack machines.