Menu
Compilers often choose intermediate representations (IRs) that are either stack-based or infinite register. What are the advantages of these over expression trees?
564
Under non-JIT settings, a stack-based VM will be popping and then pushing the same operands many times, while a register-based VM will simply allocate the right amount of registers and operate on them, which can significantly reduce the amount of operations and CPU time.
Stack machines have higher code density. In contrast to common stack machine instructions which can easily fit in 6 bits or less, register machines require two or three register-number fields per ALU instruction to select operands; the densest register machines average about 16 bits per instruction plus the operands.
What's a stack based virtual machine then? It's an abstraction of a computer, that emulates a real machine. Generally it is built as an interpreter of a special bytecode, that translates its in real time for execution on the CPU.
A stack-based design makes very few assumptions about the target hardware (registers, CPU features), so it's easy to implement a VM on a wide variety of hardware. Since the operands for instructions are largely implicit, the object code will tend to be smaller.
Expression trees work for expressions, but aren't effective for modeling the entire program. In particular, a good representation of a program is really a graph (of operations and actions) connected by control and data flows. Usually people talk about using "triples" which form exactly such a graph.
Stack machine code is easy for the front end to generate, but harder for the eventual register allocation process needed to generate real code, because it has a set of temp locations ("the stack") that have nothing clearly to do with the target architecture, and make the dataflows inconvenient to process. ("which code uses the result of this add?").
Register machines are a bit harder to generate code for, but tend to preserve the dataflow by using those infinite registers as essentially data flow wires. That dataflow and the ability to allocate it easily to real registers (there's a standard register allocation "by graph coloring") makes it relatively easy to generate good code.
If you decide to generate virtual machine code directly from these, you get different performance characteristics. Essentially, stack machines tend to get smaller code footprints. Infinite register machines tend to get fast interpretive execution. Google's Dalvik is different from the JVM for precisely this reason. (Maybe they didn't want to get sued by Sun/Oracle over class file formats, too.)
I suggest the following document: Virtual Machine Showdown: Stack Versus Registers. (PS: anything with Anton Ertl as an author tends to be an interesting read).
197
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
