is a very interesting read, for those who are too lazy or just looking for a gist, here it is:
instead of using the prevalent stack-based interpreter architecture, register based interpreters need fewer instructions, since all those load & store instructions are not necessary anymore. however, the amount of information cannot become less, therefore the information is replaced by using quadruple code, i.e., the tuple (opcode, destination register, source register 1, source register 2). the quadruple code requires more space, alas the bytecode binaries become bigger, whereas the code requires fewer instruction dispatches than its stack based counterpart.
NOTE: this paper implements the optimization for the jvm, but lua uses a register based architecture, too! (AFAIR google's dalvik [of android fame] uses a register based approach, too--probably to save energy [since dispatches in interpreters require indirect branches, which are quite expensive])
Can't stack-based bytecode languages get compiled to code that doesn't have lots of load & store instructions, by using registers to represent the top several words of the stack?
You could use that route, but it's easier to just convert to an SSA form and allocate registers intelligently when you compile the code. Compiling stack-based code, even in an optimized way, is very simple.
They can, but now you have register spilling, register allocation, and your instruction sizes aren't significantly smaller, since you still refer to registers.
All in all, it's a bad idea unless you're doing it in hardware (where you simply can't have enough registers due to cost [in money and die area] issues)
yeah, i think i know what you mean, there are two ways:
1) explicit top of stack elements (e.g. the a-stack architecture of ocaml always keeps the TOS element in a register)
2) implicit top of stack element handling; the technique is called "stack caching" and the paper to read there is from ertl in 1995.
PS: by jit compiling this code can be easily eliminated.
PPS: the points i mentioned are only "easily" implementable when your host programming language supports primitive types (such as ints, longs, floats, etc.). whenever you are dealing with "objects" (i.e. pointers to structs) you have to do (un-)boxing which lessens the advantage of stack caching...
Comments
is a very interesting read, for those who are too lazy or just looking for a gist, here it is:
instead of using the prevalent stack-based interpreter architecture, register based interpreters need fewer instructions, since all those load & store instructions are not necessary anymore. however, the amount of information cannot become less, therefore the information is replaced by using quadruple code, i.e., the tuple (opcode, destination register, source register 1, source register 2). the quadruple code requires more space, alas the bytecode binaries become bigger, whereas the code requires fewer instruction dispatches than its stack based counterpart.
NOTE: this paper implements the optimization for the jvm, but lua uses a register based architecture, too! (AFAIR google's dalvik [of android fame] uses a register based approach, too--probably to save energy [since dispatches in interpreters require indirect branches, which are quite expensive])
> NOTE: this paper implements the optimization for the jvm, but lua uses a register based architecture, too!
Lua 5 uses a register based VM, it seems. There's a paper on it - and more - here: http://www.tecgraf.puc-rio.br/~lhf/ftp/doc/jucs05.pdf
Can't stack-based bytecode languages get compiled to code that doesn't have lots of load & store instructions, by using registers to represent the top several words of the stack?
You could use that route, but it's easier to just convert to an SSA form and allocate registers intelligently when you compile the code. Compiling stack-based code, even in an optimized way, is very simple.
They can, but now you have register spilling, register allocation, and your instruction sizes aren't significantly smaller, since you still refer to registers.
All in all, it's a bad idea unless you're doing it in hardware (where you simply can't have enough registers due to cost [in money and die area] issues)
yeah, i think i know what you mean, there are two ways: 1) explicit top of stack elements (e.g. the a-stack architecture of ocaml always keeps the TOS element in a register) 2) implicit top of stack element handling; the technique is called "stack caching" and the paper to read there is from ertl in 1995.
PS: by jit compiling this code can be easily eliminated. PPS: the points i mentioned are only "easily" implementable when your host programming language supports primitive types (such as ints, longs, floats, etc.). whenever you are dealing with "objects" (i.e. pointers to structs) you have to do (un-)boxing which lessens the advantage of stack caching...