Optimal register allocation is an NP-complete problem. By doing away with it, you don't need to allocate registers.
How that compares on a practical level, I have no idea. But it's one of the reasons the JVM has a stack-based model and no registers: it makes writing compilers for JVM byte code a lot easier.
This isn't quite right - we don't in general really care whether we're allocating optimally (for example, if we have 16 registers we don't care if we can potentially allocate to 10), and heuristic based approaches are practically very useful (and cheap).
In terms of compiler writing, if you wanted to write any optimisations you'd probably want to manipulate 3-address code internally, if only because the data flow based analyses would be made easier (and then you would emit stack code in the last step).
This might be a reason why the JVM designers decided to use a stack machine, but I doubt it's an important one - they'd easily be able to get ahold of a few decent compiler writers if they needed to.
I don't doubt the JVM designers have good compiler writers. I rather think that they wanted the bytecode to be accessible to write for other compiler writers, such as the team that implemented JSP servlets a century ago, but also perhaps with a future vision for the alternative JVM languages.
Don't forget bytecode verification which is easier with just a stack rather than a stack + registers. Java was not originally envisioned to become the default server side + JIT technology it eventually became, it was meant for embedded apps which meant small simple bytecode.
Interesting. I agree with your statement regarding it being an NP-complete problem, as intuitively it seems that way, but do you have a reference by chance? Thanks!
Ok, so we can view register allocation as being a case of graph colouring; create a graph where the nodes are your 'virtual registers' and there's an edge between two nodes if those registers are both live at the same time. Then we can run on n registers iff we can colour the graph with n colours. This is one of the first identified NP-complete problems.
How that compares on a practical level, I have no idea. But it's one of the reasons the JVM has a stack-based model and no registers: it makes writing compilers for JVM byte code a lot easier.