Why did post-8008 CPUs not keep the on-chip stack idea?

Question

Ken Shirriff writes in his blog entry about the 8008:

The 8008's seven registers are in the upper right. In the lower right is the address stack, which consists of eight 14-bit address words. Unlike most processors, the 8008's call stack is stored on the chip instead of in memory. The program counter is just one of these addresses, making subroutine calls and returns very simple. The 8008 uses dynamic memory for this storage

That is an interesting idea, that would presumably make calls and returns faster, at the cost of only being able to nest them eight levels deep. (Less, if you want to save registers other than the program counter.)

But some 8-bit programs could get by well enough with that restriction.

The idea was abandoned after the 8008; no subsequent mainstream CPU (by which I mean basically excluding Forth chips, and tiny embedded chips that only use on-die memory anyway) went with the on-chip stack.

Was this purely about deciding that support for more complex programs was more important than fast subroutine calls? Or did the on-chip stack take more die area than the logic to save/load the program counter to RAM? Or both, or some other reason?

Answer 1

In short, to better support interrupts, because interrupts were arguably broken (or at least very limited in usability) on the 8008.

The direct answer to the question of why you'd move the stack off-die is "space": they needed a bigger stack and dedicating a lot of die space for a larger stack on the 8080 was basically a non-starter. But the question underneath that is, "why did they see a need for a bigger stack?"

The Re-entrancy Problem

Subroutines in general on the 8008 had a re-entrancy problem: in order to use any registers in the routine you needed to save the current values so that they could be restored on return. But worse yet, interrupt routines in particular could make the system unreliable if they used any instructions that changed any flags, since those might change flags set and about to be (but not yet) tested in the interrupted code.

Practically, these values could be saved only in fixed locations, meaning that you could have only one level of interrupts, and non-trivial subroutines could not be called from interrupts. (Nor from themselves, directly or indirectly, unless care was taken to be careful of registers and flags destroyed by the call, but this at least was a more soluble problem for the programmer.)

This problem was solved in the 8080 by extending the stack operations to be able to store not only program counter values (for returning from interrupts and subroutines) but also register pair values (including the flags). This provides a convenient and efficient way to save register values and restore them later, and makes writing re-entrant routines much easier.

The Intel 8080 Assembly Language Programming Manual gives some clear evidence that this is what was on the minds of the designers:

• "Fully programmable stacks, allowing unlimited subroutine nesting and full interrupt handling capability." (p. v)
• "The stack pointer, a register which enables various portions of memory to be used as stacks. These in turn facilitate execution of subroutines and handling of interrupts as described later." (p. 1)
• "...any interrupt subroutine should save at least the condition bits and restore them before performing a RETURN operation. (The obvious and most convenient way to do this is to save the data in the stack, using PUSH and POP operations.)" (p. 60)

The Need for More Stack Space

There's no particular indication that eight levels of nested subroutines/interrupts was a major problem. Modern developers, used to using a lot of stack space, often perceive small stacks as a likely problem, but experienced developers of code for 8-bit systems of this nature well know that you use a lot less stack than modern developers think.

That said, whether 8 levels of subroutine nesting was an issue or not, it's clear that as soon as you start using stack space for temporary storage of registers you're going to need a lot more than eight words of it. Just storing the A register and flags pair alone significantly reduces your nesting capacity, and it's not unreasonable that an interrupt routine might also want to use at least one other register pair.

Aiming for something like 32 to 64 words (64 to 128 bytes) of stack is probably reasonable if you're looking at the 8080 as a relatively similar, but somewhat larger and cleaner, version of the 8008 architecture. But once you've made the decision to move it off-chip, increasing the size beyond that is cheap, and in some ways it's easier to have a full 8-bit or 16-bit stack pointer than to use an odd size.

I've found no particular evidence that the stack pointer was made a full 16 because they felt any need for a stack to be that large. It's clear that at least some experienced microprocessor developers (the MOS 6502 team) felt that an 8 bit stack pointer (256 byte stack) was plenty. It's possible that the 8080 designers disagreed, or it's possible that they felt they couldn't force a particular area to be RAM, as the 6502 designers could. (Even more than the MC6800, the 6502 design strongly encouraged page $00 to be RAM, so forcing page $01 to be RAM was no hardship.) Or perhaps it just didn't occur to them that registers pointing into memory could be any less than 16 bits.

Stack Frames Were Not Anticipated

Some minicomputer systems of the day, notably the PDP-11 using BCPL and C, had the concept of a "stack frame," where space for parameters to and local storage for a function were allocated on the stack.

This was pretty clearly not the intent of the 8080 designers. While they make it easy to load the stack pointer (via SPHL), there is no simple way to retrieve it, much less SP-relative indexing instructions as provided by the PDP-11. (This was true of other early 8-bit processors as well; the first major processor to provide stack-relative addressing modes was perhaps the MC6809.) Further, the manual makes it clear that they intended parameters to be passed in registers, using HL as a pointer to further data when there was more than could fit into the registers:

Sometimes it is more convenient and economical to let the subroutine load its own registers. One way to do this is to place a list of the required data (called a parameter list) in some data area of memory, and pass the address of this list to the subroutine in the H and L registers. ("Transferring Data To Subroutines," p. 51)

Answer 2

The 8008 inherited its on-CPU stack from the 4004; as you mention, its successor, the 8080, replaced that with a stack pointer and an in-memory stack.

(Less, if you want to save registers other than the program counter.)

I suspect this is the main problem in the immediate aftermath of the 8008. If you want to push anything other than the return address to the stack, you end up needing more stack space, and the room required grows quickly. At the time, transistor budgets were very tight, and I suspect “adding more features” trumped “provide fast subroutine calls in some cases”. (Admittedly, most 8-bit systems get by with small stacks, but they’re still large compared to transistor budgets; once you get to the 8088/8086, with its explicit focus on support for high-level languages in a still-small transistor budget, an in-memory stack is pretty much required.)

It’s worth bearing in mind too that memory access costs were very different at the time, and 8-bit CPUs like the 6502 were slow enough that memory accesses weren’t much of a problem. Moving the stack to memory instantly increases your transistor budget substantially, along with any limits on call depth and stack sizes. Other implementation tricks could be used to make typical use cases faster: the 8080’s RST instruction (a precursor to the general-purpose software interrupts in the 8088), the 6502’s page zero...

A variation on the idea did come back later on, in the SPARC designs: SPARC CPUs have register windows, which are designed to provide something akin to an on-CPU stack (see this overview of SPARC register windows for details). This is an excellent idea on paper, when looking at individual program behaviour, but in practice it’s not, because on SPARC-sized systems, programs don’t run individually, and multitasking killed the benefits of register windows.

Nowadays stacks are typically on the CPU again, in general-purpose caches...

Answer 3

First, obviously on-chip stack takes LOTS of die area. Roughly, memory stack takes as much as single extra 16bit register and somewhat larger PLA to perform pops and pushes (on a basis of already existing micro-operations, such as reading/writing 16-bit values in memory and incrementing/decrementing 16bit registers). On the other hand, even 8-level deep hardware return stack takes the size of, well, eight 16bit registers.

Then, obviously, being able to run complex programs was (in retrospection) a huge win for 8080 and its successor, Z80. CP/M and all its applications would simply be not possible with a 8-level hardware return stack. A truly wise and future-proof decision.

Answer 4

What the processor provided was a stack for return addresses, not a stack for procedure activation records (stack frames).

While that's a workable arrangement, most programming languages do use a stack for activation records, especially for languages which support recursive activation. You can allocate from the heap, but that is slower. And once you've got such a stack in memory, the attraction of an in-processor return-address stack is much less.

The venerable KDF9 had a 16-deep return-address stack in the hardware, aka the Subroutine Jump Nesting Store (SJNS), but languages of the day (Algol in particular) still needed to manage a software stack for activation records.

Answer 5

TL;DR;

There were others, mostly micro controllers, but 8 bit CPUs, like the Valvo/Signetics 2650 as well.

There are good reasons for a RAM based stack:

• A RAM based stack allows deeper nesting.
• A RAM based stack enables additional use (like register save).
• A RAM based stack needs less logic (*3).
• Logic for memory access exists already on chip.

But most important:

• The savings are rather marginal as soon as called routines are more than a few instructions.

And:

• Modern cache structure delivers a one size fits all approach, leveling out all remaining disadvantage of a memory based (return) stack.

---

The Long Read:

That is an interesting idea, that would presumably make calls and returns faster,

Essentially it may turn call and return into register-renaming, making either zero clock (*1).

at the cost of only being able to nest them eight levels deep.

That's rather implementation specific. There's no reason to extend this to more than 8

(Less, if you want to save registers other than the program counter.)

It's a strict return stack, alone due the fact that it needs to be word aligned. Restricting it to return addresses gives the most gain with least effort. After all, a return address is always needed, thus putting it on chip makes sense. Everything else is optional, so any ROI will be lower.

But some 8-bit programs could get by well enough with that restriction.

Since it's about address size, it works with any word length.

Also more modern CPUs, like SPARC did rediscover this, now with dynamic offloading.

The idea was abandoned after the 8008; no subsequent mainstream CPU (by which I mean basically excluding Forth chips, and tiny embedded chips that only use on-die memory anyway) went with the on-chip stack.

That's not really true. For example the Valvo/Signetics 2650 featured as well an 8 level (14 bit wide) return stack. While not seen in many home computers, the 2650 was quite successful in embedded all the way to game consoles and arcade machines like Space Invader - even Atari used it for their Quiz Show. So most definite main stream (*2). There have been others as well.

Was this purely about deciding that support for more complex programs was more important than fast subroutine calls? Or did the on-chip stack take more die area than the logic to save/load the program counter to RAM? Or both, or some other reason?

Some of all. See above.

---

*1 - Heck, one could even use pre- or still loaded registers to make jumping to a much used routines single byte single cycle instructions. A bit like the SC/MP or a /370 which doesn'T feature a stack at all.

*2 - There was even a 2650 based S100 system in Australia ... still top of my wishlist.

*3 - An 8 levels of 16 bit is already 128 bits. Done static this will require more than 750 transistors - plus several hundred for decoding and buffers. A considerable share in mid 1970s CPUs featuring a total transistor count of 2-6000. While on the other hand, all logic for RAM access is needed anyway, so all needed in addition is a way to serialize/deserialize the PC content - which may as well be used to de-/serialize any 16 bit register aka allowing 16 bit load and store.

Answer 6

A similar idea is used on ARM processors. They have one high priority interrupt, FIQ, which has 7 banked registers (R8-R14), which is enough in many cases to avoid having to save anything on a stack.

Answer 7

The 8008 had an on-chip stack in order to allow the use of higher-density, cheaper shift-register memory. Subsequent processors went with a stack in off-chip memory because dynamic RAM had quickly supplanted shift-register memory.

Ken Shiriff covers this in detail here: http://www.righto.com/2017/03/analyzing-vintage-8008-processor-from.html

Shift-register memory is unusual to modern sensibilities. The memory is constantly shifted in a circle and presented to the processor a bit at a time. To access any particular part of memory the processor will have to wait until the bits they want come around. This is OK for a program as it marches through memory. But a jump becomes much more expensive. And a CALL doubly-so as it would have to wait until the memory shifts around to save the return address and then wait again for the CALL destination to come around.

Thus a on-chip stack was a practical necessity in order to support shift-register memory.

Subsequent microprocessors were designed when RAM had taken over. An off-chip stack was much more flexible and just as fast as on-chip. And it saved on CPU chip costs.

The real question was not why the other microprocessors had off-chip stacks but why the 8008 had an on-chip stack at all.

Answer 8

The MCS-51 family of microprocessors are post 8008 and do support a dedicated stack in hardware registers. Stack sizes of 128 and 256 bytes were common.

As other people have said, it is very prone to stack overflow during interrupt handling. But also it is very awkward for RTOS support. For CPUs that support a stack pointer to some unique, external memory, only that stack pointer need be saved and restored on a context switch.

But if there is only one stack in hardware, then the entire stack must be copied in and out on a context switch. There is really no simple, efficient way of achieving multi-tasking solutions on these architectures.

Which is not to say that you cannot develop great single thread/interrupt driven solutions or that you cannot develop good solutions based on some kind of cooperative scheduling. Life is full of choices; that is one of them.