Slashdot Mirror
Optimizing Stack Based Architectures?
An anonymous reader queries: "I'm currently writing a stack oriented interpreter (*ahem* Managed Code Environment) with complimentary compiler (that will be under MIT license), and was wondering if there have been any advances in stack architecture optimization? Some intense Googling turned up this paper, but it seems a bit dated, and focuses mainly on managing local variables, which is inapplicable to me because my interpreter directly supports local vars. Any thoughts or useful links on the topic would be appreciated."
Funny, but it's true, when the call is recursive. The tail call optimization causes a recursive function to execute in constant space, which is a pretty significant optimization.
You can even make this work if you've got a bunch of functions that call each other recursively with a tail call.
For more tips, I'd recommend reading the source code to another stack machine. Outside of some very hard to read dissertations on a dusty shelf, I doubt that the lore of stack machine optimization can be found anywhere else. This is just one of those cases where "did you Gooogle the thing?" just doesn't apply.
This is America, damnit. Speak Spanish!
four nine eighteen twenty-7 thirty-nine forty-7 fiftyeight sixty-nine seventy-9 eighty-8 one-hundred-and-nine one-twenty
You are asking the wrong question.
Don't get me wrong, stack machines are certainly the simplest and arguably the most elegant & compact format, and certainly nice to use if you final target is mostly JIT/native code.
If you are interpreting, your primary concern is _speed_. Speed in an interpreter on modern architectures (especially the P4!) is determined by almost constant branch mispredictions for every interpreted instruction (assuming a for(;;) switch(..) {..}; central interpreting loop, which sadly is still the fastest portable way of doing things). So your goal is to have the minimum amount of instructions generated for any particular language construct.
Generating code for a register machine can be just as easy as for a stack machine if you have the right infrastructure (assuming you don't work with a bounded set of registers, which you have no need to in an interpreter).
Register machines do much better here than stack machines, I would estimate about 1.5 times less instructions overal. Don't worry so much about the amount of work inside an instruction, aim to do as much as possible at once without branching as your VM design.
It may be even be worth it to integrate struct field and array indirection as part of your opcode, as once you switch to a register machine, "getfield" type instructions will become your most frequent ones. So having say an "add" instruction that can directly address struct fields for its 3 arguments is going to be a big win (i.e. compile a.b = c.d + e.f into a single instruction). By having a pointer in your stack frame that points to itself, you can even do this for single variables in the same instruction.