Virtual Machines – How Does a Stack VM Manage with Only One Stack?

low-levelvirtual machine

Lately I've been asking a lot of questions here about VMs. Here's another one:

I understand that often stack based VMs use only one stack – the call stack – for everything. E.g. it is also used for evaluation of arithmetic expressions.

What I don't understand is, how doesn't this complicate things a whole lot? I'll demonstrate what I mean with an example.

Please consider the following psuedocode program:

func main:
    funcA()

func funcA:
    2 + 4 * 8

This would compile to the following bytecode:

main:
call funcA
end
funcA:
push 2
push 4
push 8
mult
add
end

(In this bytecode, the program starts at main:. call pushes the program counter onto the stack and jumps to the specified label. When an end is reached, the top of the stack – assumed to be a line number – is popped and we jump there.)

So let's see what happens here:

In call funcA, we push the program counter (i.e. next line number) onto the stack. Then we jump to funcA.

In funcA some computation is made. After the computation, the number 34 is left at the top of the stack.

When we reach end, we pop the top of the stack, assuming it's the line number we should return to
But it isn't, the line number to return to is buried underneath. How should end know about this?

To avoid all this mess, we can just have a separate data stack and call stack, and not mix the two.

So my question is: why do some VMs (such as the JVM) use one stack for everything, and when the do: how do they handle situations such as the one described above?

Best Answer

When we reach end, we pop the top of the stack, assuming it's the line number we should return to But it isn't, the line number to return to is buried underneath. How should end know about this?

You compiled the source to the wrong opcodes. There are two ways to solve this:

  1. Put a swap before each end. Because the return address sits immediately underneath the return value, this will put the return address onto the top. After end has performed the return, the return value will be the top value.

  2. Define an operation return which pops two values off the stack. The second value is the return address, the first value is the return value. After updating the instruction pointer to point to the return address, the return value is pushed back onto the stack. Then use this sane return instead of end.

The compiler is responsible for emitting correct instructions.

It is possible to write a VM using only one stack. However, this vastly restricts the expressiveness. When using multiple stacks, it becomes far more easy to implement more advanced control flow such as coroutines, continuations, error handlers. In a multi-stack architecture, there would typically be a value stack, and a separate call stack which stores not only the return address but possibly also debugging data, or cleanup actions to perform when the current scope is left. If you're already using multiple stacks, it also becomes easier to use segmented stacks, which are a technique to avoid stack overflows. Essentially, the stack is actually a linked lists of smaller stacks. If one segment is full and would overflow, then another segment is allocated and added to the list.

For a well-studied multi-stack VM look at the SECD machine, essentially a lambda calculus interpreter.

Related Topic