Stack Based Virtual Machines (2015)

(The JVM design makes this harder than it really needs to be, since it doesn't insist on reducible control flow, iirc. You could say OTOH that irreducible control flow is more valuable than trivial analyzability, which is a reasonable take, but conflicts with the above comment's design point of a stack machine being both very simple for an interpreter and not an obstacle to quickly compiling to decent register-machine code. Needing a fancier stack-depth analysis would be that sort of obstacle.)

This precludes variable-stack-effect sequences as one might have in a Forth definition like:

    : ?drop  dup if drop then ;

One common way to design a stack-based instruction set is to refer to the local variables using stack offsets, just as in a register-based instruction set. The operation for reading a local variable makes a copy of the stack slot at the given offset and pushes it into the top of the stack, where it may be used as the input for subsequent operations. For example, to implement "X = X + Y" it might use the following code:

   LOAD 0 (pushes the contents of X to the stack)
   LOAD 1 (pushes the contents of Y to the stack)
   ADD    (pops two values and pushes the result)
   STORE 0 (pops one value, and stores it into X)

  ADD R0 R0 R1 (compute R0 + R1 and store in R0)

Well put. This is one of the key differences between a stack VM and a register VM. In register VM the instructions are larger, because they need to specify all their arguments. However, a stack VM may need to generate more instructions to fiddle with the top of the stack.

If you want to read more, one good example of a stack-based VM is the one in the Crafting Interpreters book. For a good example of a register based VM my suggestion would be the paper about the implementation of Lua (section 7 in particular).

https://craftinginterpreters.com/local-variables.html

http://www.jucs.org/jucs_11_7/the_implementation_of_lua

Another thing you have to take into consideration is how many registers you can index. This is relevant also when you're not constrained by hardware registers when you define a VM, because register references take up space in the instruction encoding, which have consequences in the instruction decoding performance and analysis (e.g. if all your instructions have the same length you are sure you cannot have jumps in the middle of an instruction and thus start executing a corrupt "unaligned" instruction stream)

Once you have more locals than available registers, you have to start emitting instructions to spill and load locals from and into registers which play a bit the role of the dance you have to do in stack machines to access any local.

In a way you can see a stack machine as a degenerate case of a register machine: a 2 register machine with some implicit operations on them every time an instruction is executed.