Linus Torvalds (torvalds.delete@this.linux-foundation.org) on August 4, 2022 11:03 am wrote:
> Adrian (a.delete@this.acm.org) on August 4, 2022 4:56 am wrote:
> >
> > With multiple stacks, it is likely that many cases when shuffling was required
> > in a single stack can better be done with copying/moving the top of one stack
> > to another stack, at appropriate times, instead of using shuffling.
>
> You are entirely ignoring the issue of control flow.
>
> A stack works wonderfully well for a trivial single expression evaluation
> (and by obvious extension, for iterating multiple linear expressions).
>
> And multiple stacks work for you when the expression isn't quite as trivial, and you have CSE
> and want parallelism. Or, more commonly, you simply have multiple independent things going on:
> I think the most traditional case for separate stacks is to simple allow things like independent
> function call frames and expression frames - a data stack and separate call stack.
>
> Again FORTH being the really traditional case - people think of it as only
> one stack, because that's the most obvious and visible one, but FORTH actually
> had two stacks, it's just that the second one was not as in-your-face.
>
> But multiple stacks only make things more complicated when you have internal control flow.
>
> Again: stacks work wonderfully well for function calls. Function calls are fundamentally
> nested (ok, even that is a huge simplification, and is only really true of the traditional
> model, and ignores coroutines etc). There's a reason people use stacks.
>
> But stacks work horribly badly for any situation that isn't "pure nesting". That's kind of the definition
> of a stack, after all. That very fundamental LIFO behavior is what makes a stack a stack.
>
> And most code isn't "pure nesting". Most control flow isn't function call and return. Most control flow is
> basically arbitrary conditional branches back and forth. Even if you are a disciple of Dijkstra and you use
> purely structured language constructs and you never have a single "goto" or "break" or early "return" in
> your code, the compiler will still want to generate that mess of conditional branches back and forth.
>
> And within the context of this messy control flow, a stack is a horrible idea. Sure, you can make it work,
> but you can make it work the same way you can make pigs fly: sufficient thrust makes anything fly.
>
> But the pig may not survive, and similarly, I can pretty much
> guarantee that you won't be happy with your stack thing.
>
> And multiple stacks really do not help. Quite the reverse. They just make things worse, because each
> of those stacks will still be all about that LIFO behavior that real code simply does not have.
>
> So give it up. Stacks are wonderfully useful data structures. You find them everywhere.
> They are great for many things. There's a reason people use them for function calls.
>
> But they are not great in general.
>
> So there are fundamental conceptual reasons why people don't use stacks everywhere.
> There's a reason memory is accessed as an "array" - you can turn array accesses into
> a stack, but doing the reverse is simply not practical. Stacks are fundamentally only
> useful and great for things that have that LIFO behavior, and not everything does.
>
> There are also very practical and immediate reasons people don't use stacks when it comes to
> registers: the best-of-breed compiler optimization model is SSA, which gives you lots of very
> fundamental optimizations very naturally, and I suspect that every single compiler out there
> worth its salt is using SSA internally for a large portion of the generic optimizations.
>
> And SSA is very much not about a stack model. Compiling to a stack model may seem
> natural if you use a pure parse tree, and only do simple optimizations on that tree,
> but that's simply not what any sane compiler has done in the last few decades.
>
> "Toto, I have a feeling we're not in the 1960s any more"
>
> Linus

The SSA compiler approach reminds of the register renaming CPU uarch technique.