what exactly is a "register machine"?

Question

From http://code.google.com/p/unladen-swallow/wiki/ProjectPlan I quote:

"Using a JIT will also allow us to move Python from a stack-based machine to a register machine, which has been shown to improve performance in other similar languages (Ierusalimschy et al, 2005; Shi et al, 2005)."

In college I built a simple compiler for a language with recursive procedures - which maintained stack frames for each procedure called - so that they can be called recursively and so that parameters and return values would work....

2 things:

1) Am I right in thinking that what I implemented would be considered a "stack-based machine" given the terminology used in the quotation above?

2) If my assumption in point (1) was right, how does a "register machine" work? i.e. how is it different from a stack-based machine?

Thanks!

Answer 1

A register machine is a hardware or software unit that when working with data takes it from memory, puts it in a location where it can work with it quickly, and then returns the result.

For example a regular CPU is a register machine. Since the ALU (the unit that works with numbers in a CPU) can only work with numbers in a register.

A stack based machine adds the data onto a stack and then either pops or pushes stuff onto it.

For example, adding two numbers would be

Push 2 // Push 2 onto the stack Push 3 // Push 3 onto the stack Add // Add the top two things on the stack. 

When in a register machine it would be something like this.

Load x, r0 // Load x onto register 0 Load y, r1 // Load y onto register 1 Add r0, r1, r2 // Add 1 and 2 and store the result in register 2 

Answer 2

A register machine almost always has a stack, also.

But a stack machine rarely has architecturally visible registers, or it may only have one or two.

A register machine may have some stack ops and may even have a stack addressing mode.

The difference is one of orientation. The register machine will mostly have instructions that operate on registers, and will have a handful of ops for loading and storing between the registers and the stack or memory.

A stack machine .. and these are very rare as actual hardware devices .. will operate directly on the stack with its instructions and wll have a handlful of ops for loading and storing between the stack and memory.

Now, the reasons that hardware register machines are faster than hardware stack machines are possibly unrelated to the reasons that software "register" VM's are faster, according to the cited paper, than software "stack" machines.

For the software VM's, it's apparently the case that fewer instructions need to be executed. This was determined empirically according to claims in the cited paper, but I imagine it's because far fewer overhead instructions like push, pop, and exchange need to be done in the register machine, and because the register machine can reuse operands easily if they are still lying around in the register file, without needing load or push ops. Of course, it's all just memory really; they are virtual registers.