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