11
\$\begingroup\$

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?

\$\endgroup\$

3 Answers 3

9
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Some earlier computers would write a jump instruction into the code to cause a return--not having indirect jumps--making reentrant functions impractical (theoretically one could branch over a jump but that adds complexity, in some cases especially when data addresses are completely encoded in instructions). \$\endgroup\$
    – user15426
    Mar 22, 2013 at 21:11
5
\$\begingroup\$

"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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Most RISC ISAs (e.g., MIPS [excluding MIPS16 and microMIPS], Alpha, SPARC, PA-RISC, Power, SuperH) do not have an explicit stack pointer register, defining such in the ABI instead. ARM is an exception (partially because it shadows the SP for several operating modes) as are MIP16 and microMIPS (for code density). \$\endgroup\$
    – user15426
    Mar 23, 2013 at 3:39
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.