30

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?

5
  • 3
    "Less, if you want to save registers other than the program counter." The call stack always had the full eight levels available because the 8008 had no push/pop instructions: the only thing that could be saved on the stack was the program counter, via a call instruction or RST, used for interrupts. (This seriously limited what you could safely do in interrupts becuase the flags were not preserved; I go into detail about this in my answer below.)
    – cjs
    Jun 5, 2020 at 8:48
  • 2
    It wouldn't be the only feature on early MCUs that got quietly dropped. Post COSMAC 1802, most CPUs haven't had 16 Program Counters... Jun 6, 2020 at 11:28
  • 1
    MIPS 32/64 as recently as the mid 2000s kept return addresses in one of the r registers on chip (by convention). Any register could be used but the return address register was part of the branch instruction IIRC. Jun 6, 2020 at 13:06
  • 1
    @PeterSmith The same is true for ARM if I'm reading your comment correctly - BL (Branch with Link) instruction saves the return address in the LR register, which is just one of the general registers. For a nesting call, though, you have to save it somewhere...
    – tum_
    Jun 7, 2020 at 18:05
  • 1
    SPARC has a register window that's stack-like. It's way smarter than the 8008 of course; it overflows the window to RAM
    – MSalters
    Jan 15, 2021 at 14:34

8 Answers 8

40

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)

11
  • Argument in hindsight rarely work. Reentrance isn't a criteria, especially for machines with a single interrupt level. Likewise saving in fixed location works quite well in such situations. Recursion is a rare special case either, nothing a basic CPU needs to worry about.
    – Raffzahn
    Jun 5, 2020 at 11:39
  • 12
    @Raffzahn First, please do not fall into the common confusion that re-entrancy is partciular to recursion. While recursion does indeed require reentrancy, non-recusrive routines with strictly bounded call graphs may require it too. Second, you appear to have missed my point that even with interrupt and non-interrupt code both not requiring re-entrancy alone, using them together can introduce a re-entrancy requirement if they share any subroutines.
    – cjs
    Jun 5, 2020 at 12:22
  • 1
    @Quuxplusone Given a routine print-char(c): if col >40: print-newline(); output(terminal, c). Given print-newline(): output(terminal, '\n'), all is fine. But change it to print-newline(): print-char('\n') and print-char (and everything it calls) must now be reentrant. Technically, this is indirect recursion, but a lot of programmers wouldn't think of it as recursion: it doesn't directly call itself, is not iterating over anything, there's no test and base case, and the call depth is strictly bounded. In even slightly more complex systems, situations like this will often not be obvious.
    – cjs
    Jun 10, 2020 at 3:45
  • 1
    @cjs: Ah. I would call that "mutual recursion": print-newline calls print-char and print-char calls print-newline. For correctness, all recursion must eventually "bottom out" in a base case somewhere. The fact that this code is recursive is not in any way canceled out by the fact that it's correct. :) Jun 10, 2020 at 15:34
  • 2
    @Raffzahn Regarding interrupts on the 8008, it was far worse than having to use a direct memory location to store an interrupt. You must save through HL. So you must leave one of DE or BC always free for the ISR to save the previous HL before you can save the registers to a memory address. You can still do general purpose programming with this restriction, but it's brutal.
    – RETRAC
    Mar 6, 2021 at 4:28
21

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

19
  • 3
    On a SPARC, register stack is an optional feature. You can simply not use it. GCC has an option to generate SPARC code without using register stack. Also, оn modern CPUs, there is also a fast hardware return stack as a separate unit to predict return addresses :)
    – lvd
    Jun 4, 2020 at 16:01
  • 3
    I know, but that doesn’t change the fact that they were implemented, and it turned out that they weren’t very useful. Jun 4, 2020 at 16:03
  • How do you determine whether they are not useful? At least, they decrease code size (in most cases), as prologues and epilogues of every procedure get smaller. Context switch is an argument, but yet something like AVX512 has even more insane amount of data to context switch, and nobody complains :)
    – lvd
    Jun 4, 2020 at 16:05
  • 1
    Nobody complains about AVX512 in context switches now, but the cost would be different with memory bandwidths in the SPARC era. And yes, the added cost in context switches is the main disadvantage. Jun 4, 2020 at 16:08
  • 1
    Yes, and modern CPUs effectively have their own register windows anyway, but not under program control. But full register windows in the SPARC style would be rather expensive nowadays ;-). Jun 4, 2020 at 16:10
10

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.

2
  • 1
    A small on-chip stack which is wired direct to the PC may require less die area than the hardware necessary to automatically stack the PC to memory, especially on machines whose program counter is wider than the memory bus, or on dynamic-logic NMOS machines where the number of clocks per cycle sufficiently exceeds the number of stack levels. If a machine with a 4-level stack takes 8 cycles for a normal instruction or two for a call, it could use a four-deep two-phase-clocked shift register for the stack. Drive phase 1 on every other cycle, drive phase 2 on all of the remaining cycles for...
    – supercat
    Jun 5, 2020 at 16:18
  • 1
    ...most instructions, on five of the eight remaining cycles for a "call", and on three of the four remaining cycles for a "return". Such an approach would only be usable with a small stack that doesn't need to support random access, but for decades after the release of the 8080 some architectures where a small stack would be sufficient have continued to use hardware stacks.
    – supercat
    Jun 5, 2020 at 16:22
5

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.

4

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.

12
  • 1
    Calling the 2650 "mainstream" definitely stretches the definition of mainstream to the limit. Released in mid-1975, it was a contemporary of the 8080, the 6800, the 6502, and, for most of its life, the Z80, all of which were, shall we say, slightly more mainstream? Jun 4, 2020 at 19:44
  • 1
    @MichaelGraf of course, you may go on and add a bunch of adjectives to narrow everything down to your favorite CPU. The 2650 was used way into the 90s and chances are good you owned a TV set with one. Keep in mind, CPU use in (home) computers have always bee just a tiny slice of what really happened. Most important here, mainstream is not about singling out some top runners, but was has been used in large numbers - much like a Trabbi is as well mainstream, from 1964 to 1990 quite some units were build and used :)
    – Raffzahn
    Jun 4, 2020 at 20:19
  • 1
    "It's a strict return stack, alone due the fact that it needs to be word aligned." But the 8080 stack was also word-aligned, and was not a "strict return" stack.
    – cjs
    Jun 5, 2020 at 4:19
  • 1
    My point is that the 8080 demonstrates that strict word alignment of the stack (in the sense that only words are pushed or popped) is not something that forces a stack to be strictly return-addresses only, which directly contradicts the statement of yours I quoted.
    – cjs
    Jun 5, 2020 at 11:56
  • 1
    @Raffzahn I have read the paragraph as a whole. I think that both the individual sentence and the whole paragraph would be improved by removing, _"alone due the fact that it needs to be word aligned," because I think that is both misleading and irrelevant to the point the paragraph is making.
    – cjs
    Jun 6, 2020 at 3:58
3

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.

8
  • 1
    Most ARMs push the return address and other data on the stack when servicing an interrupt, but their architecture is interesting for how ordinary function calls are handled. When calling a function that doesn't call any other functions, the call instruction will save PC to R14, so a branch to R14 will return. A function that calls other functions, will usually want to push multiple registers on entry and pop them on exit, so it can use a push-multiple instruction to push R14 along with the other registers, and pop those registers along with PC (which will receive the pushed R14 value).
    – supercat
    Mar 6, 2021 at 19:27
  • 1
    The net effect is to save a push and pop when calling/returning from a function which doesn't call any other functions, without adding any extra cost to those that do.
    – supercat
    Mar 6, 2021 at 19:31
  • 1
    @supercat - on older ARM processors, such as ARM v4, FIQ and IRQ store return address in their shadow copies of R14. There are also shadow copies of R13 and CPSR. FIQ also has shadow copies of R8-R12. I wasn't aware that this was changed on some later versions of ARM.
    – rcgldr
    Mar 6, 2021 at 19:31
  • 1
    Do they store the address of the interrupted code in R14, or do they switch to a shadow R15 (PC)? The CDP1802 switches program counters to handle interrupts, though it typically makes use of a pointer-based stack to keep track of which register was being used as a program counter before that.
    – supercat
    Mar 6, 2021 at 19:35
  • 1
    @supercat - return address is stored in R14. There is no shadow for R15, since return address is stored in R14. R15 is set to the address stored in the exception vector table. Note that some exceptions set R14 to the instruction that caused the exception, rather than to the next instruction as with IRQ or FIQ.
    – rcgldr
    Mar 6, 2021 at 19:41
3

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.

2
  • 1
    Reading the article that you linked, it's not the stack itself that was implemented in shift registers, but the generation of the stack index. Rather than simple binary counting, it generated the sequence 000, 001, 010, 101, 011, 111, 110, 100. Per the article, "The 8008 uses dynamic RAM (DRAM) to for its stack storage and its registers."
    – DrSheldon
    Mar 6, 2021 at 15:48
  • 1
    @DrSheldon The article also states that the 8008 allowed the use of shift register memory as the off-chip main memory storage. An on-chip stack allows that configuration to function more efficiently. The stack index does use a shift register but that's not the one I'm talking about. Mar 6, 2021 at 22:32
3

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.

1
  • Sure, you could make the same argument with any microcontroller, as the purpose of a microcontroller is to provide a system on one chip, stack included. Such an answer may technically answer the question, but I don't believe it is in the spirit of the question.
    – DrSheldon
    Apr 11, 2021 at 21:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .