13 ms·

Follow-up question: Is the difference between a stack + locals and registers just the instruction set? I imagine locals are allocated to and stored on the sta

Follow-up question: Is the difference between a stack + locals and registers just the instruction set? I imagine locals are allocated to and stored on the stack, exactly like you discuss for the registers. But in a stack VM, you can't work on them directly. Instead you have to load them into this special other place (the stack) and work on them there. Instruction set is simpler but at the cost of requiring additional operations.

ufo 6y ago
Yes, the main difference is the instruction set. One common way to design a stack-based instruction set is to refer to the local variables using stack offsets, just as in a register-based instruction set. The operation for reading a local variable makes a copy of the stack slot at the given offset and pushes it into the top of the stack, where it may be used as the input for subsequent operations. For example, to implement "X = X + Y" it might use the following code: LOAD 0 (pushes the contents of X to the stack) LOAD 1 (pushes the contents of Y to the stack) ADD (pops two values and pushes the result) STORE 0 (pops one value, and stores it into X) Meanwhile, in a register-based VM the ADD operation manipulates the relevant stack slots directly: ADD R0 R0 R1 (compute R0 + R1 and store in R0) > Instruction set is simpler but at the cost of requiring additional operations. Well put. This is one of the key differences between a stack VM and a register VM. In register VM the instructions are larger, because they need to specify all their arguments. However, a stack VM may need to generate more instructions to fiddle with the top of the stack. If you want to read more, one good example of a stack-based VM is the one in the Crafting Interpreters book. For a good example of a register based VM my suggestion would be the paper about the implementation of Lua (section 7 in particular). https://craftinginterpreters.com/local-variables.html https://craftinginterpreters.com/local-variables.html http://www.jucs.org/jucs_11_7/the_implementation_of_lua http://www.jucs.org/jucs_11_7/the_implementation_of_lua
ithkuil 6y ago
> I imagine locals are allocated to and stored on the stack, exactly like you discuss for the registers. But in a stack VM, you can't work on them directly. Instead you have to load them into this special other place Another thing you have to take into consideration is how many registers you can index. This is relevant also when you're not constrained by hardware registers when you define a VM, because register references take up space in the instruction encoding, which have consequences in the instruction decoding performance and analysis (e.g. if all your instructions have the same length you are sure you cannot have jumps in the middle of an instruction and thus start executing a corrupt "unaligned" instruction stream) Once you have more locals than available registers, you have to start emitting instructions to spill and load locals from and into registers which play a bit the role of the dance you have to do in stack machines to access any local. In a way you can see a stack machine as a degenerate case of a register machine: a 2 register machine with some implicit operations on them every time an instruction is executed.

ufo 6y ago

Yes, the main difference is the instruction set. One common way to design a stack-based instruction set is to refer to the local variables using stack offsets, just as in a register-based instruction set. The operation for reading a local variable makes a copy of the stack slot at the given offset and pushes it into the top of the stack, where it may be used as the input for subsequent operations. For example, to implement "X = X + Y" it might use the following code: LOAD 0 (pushes the contents of X to the stack) LOAD 1 (pushes the contents of Y to the stack) ADD (pops two values and pushes the result) STORE 0 (pops one value, and stores it into X) Meanwhile, in a register-based VM the ADD operation manipulates the relevant stack slots directly: ADD R0 R0 R1 (compute R0 + R1 and store in R0) > Instruction set is simpler but at the cost of requiring additional operations. Well put. This is one of the key differences between a stack VM and a register VM. In register VM the instructions are larger, because they need to specify all their arguments. However, a stack VM may need to generate more instructions to fiddle with the top of the stack. If you want to read more, one good example of a stack-based VM is the one in the Crafting Interpreters book. For a good example of a register based VM my suggestion would be the paper about the implementation of Lua (section 7 in particular). https://craftinginterpreters.com/local-variables.html https://craftinginterpreters.com/local-variables.html http://www.jucs.org/jucs_11_7/the_implementation_of_lua http://www.jucs.org/jucs_11_7/the_implementation_of_lua

ithkuil 6y ago

> I imagine locals are allocated to and stored on the stack, exactly like you discuss for the registers. But in a stack VM, you can't work on them directly. Instead you have to load them into this special other place Another thing you have to take into consideration is how many registers you can index. This is relevant also when you're not constrained by hardware registers when you define a VM, because register references take up space in the instruction encoding, which have consequences in the instruction decoding performance and analysis (e.g. if all your instructions have the same length you are sure you cannot have jumps in the middle of an instruction and thus start executing a corrupt "unaligned" instruction stream) Once you have more locals than available registers, you have to start emitting instructions to spill and load locals from and into registers which play a bit the role of the dance you have to do in stack machines to access any local. In a way you can see a stack machine as a degenerate case of a register machine: a 2 register machine with some implicit operations on them every time an instruction is executed.