3 ms·
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 architect
by sb 17y ago
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])
- jganetsk 17y agoCan'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?
- daeken 17y agoYou 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.
- ori_b 17y agoThey 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)
- sb 17y agoyeah, 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...
- ori_b 17y ago> 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 http://www.tecgraf.puc-rio.br/~lhf/ftp/doc/jucs05.pdf