Do VMs use one stack for everything?

Question

Most VMs have a "call stack" to keep track of where to return from each function that was called. This is often simply regarded as "the stack".

However often a stack is needed for operations that aren't related to function calling, such as performing arithmetic. My question is: is the same stack (i.e. the call stack) used also for these kinds of operations? Or do operations such as performing arithmetic use a different stack?

(I'm talking about most VMs).

see also: [Why do we need a Heap if everything can be done much more efficiently on the Stack?](http://programmers.stackexchange.com/questions/113289/why-do-we-need-a-heap-if-everything-can-be-done-much-more-efficiently-on-the-sta) — gnat, Jul 29 '14 at 08:11
If you code works on an expression which has multiple arithmetic operation, then the compile will turn this into a sequence of operations for you. The compiler might need a stack to do this. When the VM runs your code, the arithmetic expression has become a series of arithmetic operations. You no longer need to use stack. — InformedA, Jul 29 '14 at 08:22
@randomA Quite the opposite for many VMs, which use a stack (though not necessarily the *same* stack) all the time, even in cases where a machine code compiler could and would use registers. — , Jul 29 '14 at 10:38
@delnan That's not what I meant. "You no longer need to use stack" meaning you no longer need to use a separate stack to perform something like Arithmetic Parsing algorithm using stack. http://en.wikipedia.org/wiki/Shunting-yard_algorithm Of course, you need to use a stack to manage the stack frame for current method's invocation context. — InformedA, Jul 29 '14 at 10:43
@randomA Where does parsing enter the picture? This question seems to be exclusively about the execution of the program, not analysis. — , Jul 29 '14 at 10:59
@delnan He has "However often a stack is needed for operations that aren't related to function calling, such as performing arithmetic", so my natural assumption is that he was talking about the stack needed to parse arithmetic exception — InformedA, Jul 29 '14 at 11:01
@randomA I think you're wrong. Stack machines are a thing (in fact, probably the single most popular design for VMs) and they fit that exactly. It also meshes better with the actual question (whether that is the same stack as the call stack). — , Jul 29 '14 at 11:09
@delnan Ok, then I will assume you are right as with many JVMs, you can also have JIT that looks at multiple JVM instructions to execute faster. I am aware that when things go into the physical CPU (pass the virtual part), your code becomes another set of micro-instructions to maximize performance further. (Yes there are instructions even lower level than machine instructions, over there, you have another 'stack' as well if you want to go that far) — InformedA, Jul 29 '14 at 11:21
way too broad. Is it possible to create a VM like that? Sure. Are ALL VMs like that? Impossible to answer as it's certainly possible to use other mechanisms and impossible to prove that's never been actually done. — jwenting, Jul 29 '14 at 12:22

Jörg W Mittag · Answer 1 · 2014-07-29T12:20:48.223

This depends entirely on the VM.

The JVM has a single stack for everything. (More precisely: a single stack per thread for everything.)

The Dalvik VM is register-based, it only has a call stack, all data is held in registers.

The Parrot VM has no stack at all: it is register-based, i.e. all data is held in registers, and its control flow is based on continuations, so it doesn't have a call stack either.

There are also VMs which conceptually have a stack but actually allocate all stackframes as regular objects on the heap. So, from the point of the instruction set, there is a stack, but in the actual implementation, there isn't. (The JVM specification, for example, allows this. There is nothing in there, which forces you to have a single contiguous area of memory for your stack. In fact, the spec explicitly mentions that they do not specify such level of detail and even mentions allocating stack frames on the heap as an example.)

Many Smalltalk and Lisp VMs have a "spaghetti stack", which is required to support call/cc, since this can conceptually "fork" the call stack.

Forth has two stacks: a return address stack for control flow and a data stack. Both stacks can be freely manipulated by the programmer.

score 0 · Answer 2 · answered Jul 29 '14 at 10:10

Most VM's mimic the most common CPU architectures in this and use only a single stack for temporary values, intermediate results, function arguments, function return values and return addresses.

This is generally easiest, because you only need one administration of where the stack is located and how much space there is.
With only one stack, you also have only two data structures that can dynamically grow (the stack and the heap), which are conveniently arranged such that there is no need to determine beforehand how large each of them will be. The can start at opposite ends of the (available) address space and grow towards each other. They will only meet if the address space is exhausted.
With two or more stacks, that arrangement isn't possible, so you need to guess how much memory each will need.

Do VMs use one stack for everything?

2 Answers2