I have designed my own kind of vm, a sort of stack-register. It works by having a stack but instead of pushing and popping values, you simply store the values on the stack, and add together different addresses.

For example add would be #add addressTo, address1, address2. It might sound like a register machine, but everything is stored on the stack instead of register and local variables on the stack.

The reason I believe this is a good idea is because you don't have to load memory from and to registers, but have the advantages of a register machine. Is there a flaw in my design or why is it not already used or is it completely new which I doubt?

  • 1
    I believe this is called a en.wikipedia.org/wiki/Stack_machine. I believe no one makes machines like this in practice simply because registers are faster than the RAM where the stack is located. Whether this is true of VMs as well as physical machines I'm not sure, but I'm under the impression that making VMs as fast as their physical hosts requires giving them some kind of access to the underlying hardware, so the same issue applies.
    – Ixrec
    Dec 6 '15 at 21:01
  • 5
    It should be noted that virtual stack machines are fairly widespread including Java and Python's default runtimes.
    – user28988
    Dec 6 '15 at 21:10
  • 1
    It sounds similar to this vm: vitanuova.com/inferno/papers/hotchips.html where it uses #add address1, address2, addressTo as per your example. The analysis in the paper might be of interest.
    – imel96
    Dec 7 '15 at 0:28

Some early computers worked in the way you described, by addressing memory directly without any registers. The problem with this approach was that quite soon, accessing storage was much slower than the processor. Therefore, modern computer architectures use many levels of caching — from slow hard disks, RAM, various caches L3-L1, to the fast registers. Different architectures take this to different extremes. E.g. in MIPS, all instructions only operate on registers, and there are dedicated load and store instructions. In contrast, the x86 mov instruction is Turing-complete.

In VM design, we have more freedom when designing an architecture.

There are low-level VMs such as the LLVM that are concerned about being easily compilable to actual machine code. LLVM uses a kind of register architecture where each register can only be assigned once, but you have no restrictions on the number of registers. This makes it easy to produce efficient register allocations for actual CPUs. This LLVM representation also makes it easy to implement optimizations such as common-subexpression-elimination. The big disadvantage is that not having a built-in stack requires us to manually cope with memory when the local state does not fit into the available registers. Once your code actually writes to memory, it becomes much harder to optimize.

High-level register based VMs do exist (Parrot…), but are very uncommon.

There also are high-level VMs such as the Perl implementation. Here, instructions are extremely high-level such as “apply a regular expression” or “dispatch a method”. The Perl VM uses a stack architecture which simplifies a lot — compare “add the top two values on the stack” with “add registers A and B and store in C”. Code for a stack machine can be generated quite directly from an abstract syntax tree, but register allocations are more tricky (if you have a limited number of registers). More importantly, registers would not give us any advantages considering the Perl memory model — every value is represented as a pointer to a struct.

More low-level stack based languages do also exist, e.g. the class of concatenative languages (Forth, PostScript). Since operations always operate on the top few values of the stack, they can be composed quite flexibly. However, the stack is used as a semantic model here, not necessarily as an implementation strategy. For a low-level VM, stack machines are attractive because they have very compact object code (also why the JVM is stack based), since instructions do not need to store their argument locations. Unfortunately, they make it difficult to perform some optimizations, and can potentially require a lot of memory read/writes.

Your “hybrid” architecture (actually, more like a random access machine without any registers, that happens to have a stack) would certainly work, but it has none of the advantages of a register machine, being speed and relative optimizability. It also has none of the desirable qualities of a stack machine, since stack machines are more common in high-level VMs where direct memory access is not a thing, or in low-level scenarios where we need compact code.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.