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 is an abstract machine whose opcodes are defined by reference to their operation on a set of named registers, rather than by their operation on the top portion of a stack.

In a register machine: add could be defined to take three register names as operands, add the contents of the first two, and place the result in the third. (More common is the design where only one or two are named and the result always goes in a special accumulator register, but that's not the point.)

In a stack machine: add could be defined to pop two operands from the stack, add them, and push the result onto the stack.

Answer 3

A register machine uses a fixed number of registers or buckets for storing intermediate values for computation. For example the "add" instruction could add the values in two specific registers and store the result in another register.

A stack based machine uses a stack for storing intermediate values during computation. For example, to add two numbers the "add" instructions pops off two values from the stack, adds them, and pushes the result back onto the stack.

Answer 4

Did your compiler generate machine code? If so, then its target was a register machine (nearly all CPU designs are register machines).

Stack machines store all values on a stack, whereas register machines have a fixed number of storage slots whose "addresses" do not change (unlike stack machines).

Answer 5

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?

Not really. A stack of some sort is pretty much the only way to implement recursive function calls. But a "stack-based machine" goes much further in doing everything via the stack. Not just function calls, but also arithmetic operations. In a way, they behave as if every machine instruction is a function call handled via the stack. It makes for a very simple machine design, but rather hard-to-write assembler/machine code.

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?

A register machine has some fast internal storage (registers) and performs most of its operations on data in these registers. There are additional machine instructions for copying data between registers and main memory.

IIRC there are two kinds of stack machines:

• Accumulator machines have an "accumulator", which is basically a single register that holds the result of calculations (and may also supply an operand), with most machine instructions operating on the accumulator.
• "Pure" stack machines put the result of calculations on top of the stack after consuming the operands.

Answer 6

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.