25

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?

  • 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 at 8:48
  • 1
    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... – Brian Drummond Jun 6 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. – Peter Smith Jun 6 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 at 18:05
32

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)

| improve this answer | |
  • 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 at 11:39
  • 11
    @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 at 12:22
  • @cjs: I see how interrupts can lead to re-entering: F is interrupted; the interrupt handler G calls F as a subroutine. But I don't understand your first sentence— "While recursion does indeed require reentrancy, non-recursive routines with strictly bounded call graphs may require it too." Can you elaborate, or link to an elaboration, on this point? – Quuxplusone Jun 9 at 14:31
  • @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 at 3:45
  • @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. :) – Quuxplusone Jun 10 at 15:34
18

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

| improve this answer | |
  • 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 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. – Stephen Kitt Jun 4 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 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. – Stephen Kitt Jun 4 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 ;-). – Stephen Kitt Jun 4 at 16:10
7

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.

| improve this answer | |
  • 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 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 at 16:22
3

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.

| improve this answer | |
2

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.

| improve this answer | |
  • 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? – Michael Graf Jun 4 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 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 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 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 at 3:58
1

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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