I hope this kind of question isn't off-topic on this site.

I'm finally getting the hang of what a stack based machine is, and how to compile code for it. For example, the following code: 2 * 5 + 1 would compile to this bytecode:

push 2
push 5
push 1

However what I want to understand is, the fundamental differences between compiling for a stack based machine and compiling for a register based machine.

Basically I want to see what a register-machine's bytecode would look like, as opposed to a stack-machine's bytecode.

To understand this, I'd like to ask you to show me what the bytecode for the above expression would look like, for a register machine. I.e. what this: 2 * 5 + 1 would compile to.

  • Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask – gnat Aug 1 '14 at 9:15

Register machine bytecode often comes in three-address form, that is, it talks about data flow relationships between registers, and operations take explicit destination registers. So a basic instruction set may look like this:

set register, constant
mul out, in1, in2
add out, in1, in2

You could assume you have an infinite number of registers r0, r1, etc. and rewrite this in SSA form:

set r0, 2       // int r0 = 2;
set r1, 5       // int r1 = 5;
mul r2, r0, r1  // int r2 = r0 * r1;
set r3, 1       // int r3 = 1;
add r4, r2, r3  // int r4 = r2 + r3;

Then various analyses and optimisations become easy. You can reuse registers that are no longer active:

set r0, 2       // int r0 = 2;
set r1, 5       // int r1 = 5;
mul r0, r0, r1  // r0 *= r1;
set r1, 1       // r1 = 1;
add r0, r0, r1  // r0 += r1;

You can also allow instructions to take immediate constants, rather than loading everything into registers:

set r0, 2      // int r0 = 2;
mul r0, r0, 5  // r0 *= 5;
add r0, r0, 1  // r0 += 1;

When you do that, you notice a resemblance with existing register architectures such as x86, and indeed you can perform register allocation to map your virtual register machine onto real hardware:

mov eax, 2
mul eax, 5
add eax, 1

In either case, the bytecode is a flat representation of a data and control flow graph:

| 2 |
  | +---+
  | | 5 |
  | +---+
  |   r1
  |   |
|   ×   |
  | +---+
  | | 1 |
  | +---+
  |   r3
  |   |
|   +   |

In the stack notation, each stack operation corresponds to one row of this diagram, and the width of the diagram at any point corresponds to the maximum stack depth at that point. In the SSA form, each register corresponds to a point in the graph where a value is produced. They’re simply different structures for talking about the same thing.

  • Since a stack is practically 'infinite' but the numver oc registers is very limited, is it harder to compile to a register machine than a stack machine? – Aviv Cohn Aug 1 '14 at 9:00
  • @Prog: Parrot has arbitrarily many registers. Dalvik, too. I suspect that's the case for most register-based VMs. In Dalvik, the number of registers is specified in the method header, I believe Parrot scans the code of the method and figures out an upper bound on its own. – Jörg W Mittag Aug 1 '14 at 11:27
  • @JörgWMittag So register VMs can just 'make up' whatever number of registers they need? – Aviv Cohn Aug 1 '14 at 12:14
  • 1
    @Prog: If it's a virtual machine, the whole thing is "made up". :) – Greg Hewgill Aug 1 '14 at 20:04
  • 1
    @Prog: Since there is a limit on the actual number of registers available in hardware, what a compiler typically does is try to keep everything in registers, and “spill” to memory when that’s not possible. That’s something you need to do for good performance in either a stack VM or a register VM. Which one is “harder to compile to” depends more on your style of thinking. – Jon Purdy Aug 1 '14 at 20:17

Fortunately, there are a variety of well-known real register machines that you can look at. For example, x86 code for the above might be:

mov eax, 2
mul eax, 5
add eax, 1

(In x86 Intel notation, the destination is the left operand.)

  • 1
    you can use inc eax instead of add 1 to it – phuclv Aug 1 '14 at 4:59
  • 2
    That's true, there are many ways to write functionally equivalent code. I could have used a register other than eax, for example. The example I gave matches the original arithmetic expression pretty well. – Greg Hewgill Aug 1 '14 at 6:06
  • @GregHewgill Or for proper abominations, MOV EAX, 5 followed by LEA EAX, [EAX*2 + 1] – Vatine Aug 1 '14 at 11:32

Actually you don't need a multiplication to do 2*5. To multiply any number with a power of 2, use left shift instead. But assume you really must do a multiply, the result depends on whether how many operands an instruction have in that architecture, and whether that architecture has immediate multiplying instruction or not.

For example in a 1-operand machine or accumulator architecture it's possibly done like this

load 2   # load accumulator with 2
mult 5   # multiply accumulator with 5
add  1

In 2-operand architectures:

move r0, 2
mult r0, 5
add  r0, 1

That's the idea for an abstract instruction set. Real architectures may not support all that operations and you may need more instructions to achieve that. For example 8051 is an accumulator architecture but it doesn't have multiply-by-constant instruction so you need one more instruction:

MOV A, #2
MOV B, #5

In AVR to get the result in R0 you can do like this

ldi R2, 2
ldi R3, 5
mul R2, R3
inc R0

In MIPS where most instructions have 3 operands (but multiplies have only 2 operands) you can do like this

addi $t0, $zero, 2    # t0 = 2
addi $t1, $zero, 5    # t1 = 5
mult $t0, $t1         # {hi, lo} = t0*t1
mfhi $a0              # high part, maybe unneccessary
mflo $t2              # t2 = LOW(t0*t1)
addi $t2, $t2, 1      # t2 = t0*t1 + 1

In x86 you have much more choice. Originally multiplication in x86 has only 1 operand and must be achieved through the accumulator ax

mov ax, 2
mov bx, 5
mul bx
inc ax

You can also use 3-operand imul to shorten the program

mov  eax, 2
imul eax, eax, 5
inc  eax

Or even shorter using LEA instruction:

mov rax, 5
lea rax, [rax + rax + 1] ; or possibly lea rax, [rax*2 + 1] although I'm not sure about the syntax
; or
mov rax, 2
lea rax, [rax + rax*4 + 1] ; rax = rax*5 + 1
  • any reason for the downvotes? – phuclv Aug 3 '14 at 4:57

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.