[jcoffland]

I'd like to see such an article on a register based VM. Pawn and Lua are nice examples. Most VMs are stack based but this is mainly because they are conceptually easier to understand. Register based machines have some real advantages, like requiring far fewer instructions inside tight loops.

[tptacek]

Stack VMs aren't used just because they're easier to understand:

* In interpreted environments, registers are stored in memory anyways, so the advantage of simulating them isn't as great

* It is easier to generate code for stack machines, because you don't need to run register allocation

* There's a tradeoff in instruction complexity versus number of instructions between stack and register machines

[rdc12]

This paper [1] (thou it is a tad old now) shows that the register machine approach does still outperform the stack machine by a fair margin. Largely from the reduction of needed instructions.

Wonder which is a better source represntation for a JIT thou.

[1] https://www.usenix.org/legacy/events/vee05/full_papers/p153-...

[gsg]

JIT compilers aren't really an argument either way, as you can do tracing or transform to an SSA graph from either representation quite easily. All the real complexity is further down the compilation pipeline.

I (half) wrote a toy trace compiler based on a register bytecode a while back. Writing the front end was quite pleasant - the difficult parts were back end stuff like figuring out how to support trace exit information. (The difficulty there is that you might want to perform stores, materialize objects etc as you go off trace as part of store and allocation sinking.)

[userbinator]

In interpreted environments, registers are stored in memory anyways, so the advantage of simulating them isn't as great

...unless the interpreter maps VM registers directly onto machine registers. With some VMs it's possible, and then you can get very good performance.

[gsg]

That would be very inefficient, because registers cannot be indexed. The dispatch you have to introduce to jump to code that references the right physical regs would murder you with mispredictions.

Also, register VMs typically have three operands. Specialising each instruction for each possible register for three operands would result in a ridiculous volume of code.

Special purpose instructions that access fixed registers would be fine, but general purpose operand references cannot be sanely implemented in this way. Existing register VMs use memory because it's faster.

[rurban]

> Also, register VMs typically have three operands.

Wrong. Only SSA VMs (with an optimizing compiler) need three operands. Simple register VMs as well as hardware CPUs have two operands only, and you can easily fit them into one word then.

You cannot do better SSA based optimizations then, but the VM speed is much faster than with two or multi word ops, which blow up your instruction cache. lua has to use shorter ranges to get 3 operands into one word.

Writing a JIT with two-address ops is also trivial. It's a straightforward conversion using fixed registers.

Sample: https://github.com/perl11/potion

> Specialising each instruction for each possible register for three operands would result in a ridiculous volume of code.

Nobody does that, it's not needed.

> Special purpose instructions that access fixed registers would be fine, but general purpose operand references cannot be sanely implemented in this way. Existing register VMs use memory because it's faster.

No. You need general purpose operand insns for only one or two fixed registers (eax, edx typically). Nobody implements all possible combinations. And you use the stack to shuffle values around, not memory.

[gsg]

Multiple real implementations of register VMs have three operand instructions. Lua, Luajit and Guile are examples that I'm familiar with. For that matter, many ISAs feature three operand instructions. Even some of the recent extensions to x86-64 are three operand versions of (some of) the vector instructions.

If you think three-operand instructions aren't common in both hardware and interpreter design, you are simply misinformed.

None of this has anything to do with SSA. SSA IR can be reasonably constructed from any of stack, accumulator, two-operand register or three operand register bytecode. All of the usual optimizations follow from that.

> the VM speed is much faster than with two or multi word ops

While variable length encodings are best avoided, that doesn't rule out three operand instructions. For a good example of an extremely fast interpreter that uses such instructions, have a look at luajit.

> Nobody does that, it's not needed.

That's what the OP was suggesting, so that's what I was discussing.

[crzwdjk]

Registers are stored in memory, but ideally "memory" means L1 cache, and it seems to me like register VMs would have better cache locality. This might be why they're getting more popular relative to stack VMs as the speed advantage of cache increases.

[barrkel]

Stack machines are constantly using the same absolute offsets into the stack when evaluating in a loop, or evaluating different branches of a big expression. In fact, one of the simplest register allocators you can use in an expression code generator is a stack; pop to allocate, push to deallocate, and spill if you run out. On a CPU, this will have benefits, but in a VM, it's just a relabeling scheme for the same memory slots a stack VM would use.

What you potentially gain with a register VM is reduced accounting overhead; a stack machine will be constantly adjusting the stack pointer on every operation. It's a tradeoff for less complexity at codegen time. It's swings and roundabouts in the lowlands of performance, though; no loop and switch VM will be super-fast.

[voidiac]

Register based VMs are not more complex than stack based VMs. You can even have a stack and the only difference is that your instructions operate on registers and not directly on the stack. I only consider generating code more complex with a register based VM.

If you are interested here is a toy vm I wrote myself: https://github.com/byo3rn/ire

PS: I suck at documentation.

[bch]

You can see a project switch from a stack-based VM to a register-based VM here[0] [1].

For [1], search page for "vdbe" (virtual database engine). Hopefully you find interesting things.

[0] https://www.sqlite.org/vdbe.html

[1] http://www.sqlite.org/src/timeline?c=2007-11-11&n=400

[ddfreyne]

I created a register-based VM named RCPU, for educational purposes. You can find it at https://github.com/ddfreyne/rcpu. It has most of what you’d expect from a register-based VM, and even has video output (rcpu-assemble samples/video.rcs and then rcpu-emulate the resulting file with --video).

I intend to write up my findings, but haven’t gotten around to it yet. I do have slides for a talk for this project though: https://speakerdeck.com/ddfreyne/simulating-a-cpu-with-ruby

[rednovae]

Not an article, but this is a register-based VM that should be simple and straight-forward to understand. Also comes with an assembler, disassembler and debugger.

https://github.com/endeav0r/hsvm