By: Linus Torvalds (torvalds.delete@this.linux-foundation.org), August 3, 2022 11:31 am
Room: Moderated Discussions
Anon (no.delete@this.spam.com) on August 3, 2022 9:25 am wrote:
>
> Wrong. Have you ever write a compiler? Targeting a stack is much easier than a register based
> architecture, Java and .Net intermediate languages are stack based exactly because of that.
No. Targeting a stack is much easier in a simplistic compiler.
If you do the kind of basic compiler with no optimizations between basic blocks, if you generate the code by just walking the expression tree with no CSE, then a stack looks very natural. You just walk the expression tree and output the operations, and you're done.
You can make the stack even more natural by actually expressing it in the language, and have something like FORTH, and then the compiler phase can get so straightforward that you start to blur the line between interpreting and compiling the language.
So in those kinds of situations, a stack-based ISA looks like a really natural thing.
But it is not true that targeting a stack is easier than a register-based architecture once you start doing any kind of even slightly more complicated optimizations and nontrivial control flow.
Don't get me wrong: register allocation is fundamentally hard, and doing it for a register based instruction isn't easy either. But at least you don't have the added complexity of having to worry about stack depth changes wrt control flow for everything.
The compiler still has to manage the function frame (and stack use for function call arguments etc), but at least it can then make its own choices about where and how to update it.
Stack-based architectures are nice for two things: code density and "portability".
FORTH machines were unquestionably considered quite dense (although it's hard to compare when you have to write the code in a different language). And while code density is probably part of it, I suspect the intermediate languages that are designed for interpreters and JIT engines also like using a stack is because that way they don't encode some arbitrary register file size in the virtual machine, and in the bytecode choice.
So saying "it's a stack based virtual machine" simplifies the design, and avoids making some arbitrary hw choice, but it's not necessarily simpler in general.
Linus
>
> Wrong. Have you ever write a compiler? Targeting a stack is much easier than a register based
> architecture, Java and .Net intermediate languages are stack based exactly because of that.
No. Targeting a stack is much easier in a simplistic compiler.
If you do the kind of basic compiler with no optimizations between basic blocks, if you generate the code by just walking the expression tree with no CSE, then a stack looks very natural. You just walk the expression tree and output the operations, and you're done.
You can make the stack even more natural by actually expressing it in the language, and have something like FORTH, and then the compiler phase can get so straightforward that you start to blur the line between interpreting and compiling the language.
So in those kinds of situations, a stack-based ISA looks like a really natural thing.
But it is not true that targeting a stack is easier than a register-based architecture once you start doing any kind of even slightly more complicated optimizations and nontrivial control flow.
Don't get me wrong: register allocation is fundamentally hard, and doing it for a register based instruction isn't easy either. But at least you don't have the added complexity of having to worry about stack depth changes wrt control flow for everything.
The compiler still has to manage the function frame (and stack use for function call arguments etc), but at least it can then make its own choices about where and how to update it.
Stack-based architectures are nice for two things: code density and "portability".
FORTH machines were unquestionably considered quite dense (although it's hard to compare when you have to write the code in a different language). And while code density is probably part of it, I suspect the intermediate languages that are designed for interpreters and JIT engines also like using a stack is because that way they don't encode some arbitrary register file size in the virtual machine, and in the bytecode choice.
So saying "it's a stack based virtual machine" simplifies the design, and avoids making some arbitrary hw choice, but it's not necessarily simpler in general.
Linus