Advantages of stack-based bytecodes or infinite register machines

compiler-construction expression-trees intermediate-code

Question

Compilers often choose intermediate representations (IRs) that are either stack-based or infinite register. What are the advantages of these over expression trees?

Popular Answer

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).



Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Is this KB legal? Yes, learn why
Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Is this KB legal? Yes, learn why