What does it mean for a CPU to support a stack?

Question

How can a CPU not support a stack? Doesn't any architecture that uses subroutines (I'm pretty sure that's all architectures) have to push the return address onto the stack so it can return to where it called the subroutine from? The stack just means a section of memory with a pointer that grows in a certain direction and acts as a stack data structure no? I just don't understand how an architecture could not support a stack.

To what extent is automatic memory storage (automatic variables vs. static variables) determined by the compiler vs. the hardware architecture?

Answer 1

There are many low-level microcontrollers that have hardware stacks for subroutine call/return and interrupt handling, but make it difficult if not impossible to store data (variables) there, and implementing a purely software data stack would be terribly inefficient. The 8051 is one classic example, and low-end PICs (PIC12/PIC16) are another. On these machines, the data stack is emulated by assigning static storage locations for automatic variables, with the amount of reuse of these locations being dependent on the sophistication of the compiler.

Note that if stack emulation is being done this way, it means that recursion — a function that calls itself, either directly or indirectly — does not work, since each instance of the function reuses the same static locations for its supposedly "private" variables. Some compilers do allow the limited use of recursion (typically implemented by means of a #pragma of some sort), which will cause it to create a true data stack no matter how much it slows things down.

Just as an aside, there have been CPU architectures that did not have a hardware stack at all, not even for subroutine/interrupt handling, including the DEC PDP-8 and the IBM System/360. On these machines, the PC (return address) and status register (for interrupts) were saved in registers or memory locations, but in every instance I can think of, the machine also had sufficiently flexible address modes that made it easy to create a stack with software.

Answer 2

"supporting a stack" means

1. having an explicit stack pointer register, and
2. having primitive machine code instructions for manipulating / using the stack pointer register (like reti, which changes the program counter based on the stack pointer in order to return from a function call).

You can emulate this without hardware support through emulation, which is compiler generated code that the same sort of things in RAM using variables. It's rare / uncommon to not have direct support for stack in any modern computer architecture.

Semantics of variables in programming languages have almost nothing to do with the target hardware architecture, for any language higher than straight assembly. The compilers job is to generate machine code that is compliant with the semantic contract of the programming language.

Answer 3

Some architectures (e.g. PIC) have a hardware stack that's limited in capability (can only be used for return addresses, not variables). Some extremely small architectures don't have a store-and-increment or PUSH instruction, so it's more fiddly to do a stack.

'auto' variables in C should always be compiled to something with 'auto' initialisation behaviour, and 'static' with static behaviour; on some architectures you're not allowed to do recursion, in which case the compiler can statically allocate all the variables.