May the PDP-11's stack grow in either direction?

Question

According to this answer, the stack grows downward. It's in §4.4 of the cited document:

As another example, the DEC PDP11 range has a hardware stack which grows with decreasing store addresses.

Now, but the way this works is by the pre-decrement and post-increment addressing modes. We can just use (r6)+ for pop or -(r6) for push.

But isn't that just convention? From what I understand we could equally well reverse the direction and use (r6)+ for push or -(r6) for pop. Yet every document I see says the stack grows downward on the PDP-11. So what am I missing?

Answer 1

It seems that JSR and RTS expected a down growing stack. Stack addressing modes

R6, also written SP, is used as a hardware stack for traps and interrupts. A convention enforced by the set of modes the PDP-11 provides is that a stack grows downward—toward lower addresses—as items are pushed onto it. When a mode is applied to SP, or to any register the programmer elects to use as a software stack, the addressing modes have the following effects:

JSR and RTN

The JSR instruction could save any register on the stack. Programs that did not need this feature specified PC as the register (JSR PC,address) and the routine returned using RTS PC. If a routine were called with, for instance, "JSR R4, address", then the old value of R4 would be on the top of the stack and the return address (just after JSR) would be in R4. This let the routine gain access to values coded in-line by specifying (R4)+, or to in-line pointers by specifying @(R4)+. The autoincrementation moved past these data, to the point at which the caller's code resumed. Such a routine would have to specify RTS R4 to return to its caller.

So, as long as you use the stack pointed to by R6 (or SP) and anywhere in your program uses any of:

• JSR (jump to subroutine)
• RTS (return from subroutine)
• MARK (support of stack clean-up at return)
• EMT (emulator trap)
• TRAP, BPT (breakpoint trap)
• IOT (input/output trap)
• RTI & RTT (return from interrupt)

you have to follow the growing down idea, since they all expect the CPU controlled stack to be growing downwards.

If you never use any commands that uses the CPU controlled R6 (SP) stack, do as your like.

You could also set up your own data stack growing upwards. I've seen things like that on some systems. Two stacks sharing the same RAM area, one growing from bottom up, the other growing from top down. If they ever overlap the same area, you will get interesting results.

Answer 2

Apart from the R6 mechanisms in the hardware that expect the R6 stack to grow downwards (including the stack limit register), there's an implied bias for downward stack growth due to the predecrement/postincrement address modes.

It's preferable to have your stack pointer point to the logical top-of-stack rather than the next free word on the stack, for code-size reasons. With a downwards-growing stack,MOV thing,-(SP) results in the last pushed quantity being addressable as (SP). With an upwards-growing stack, MOV thing,(SP)+ results in the last pushed quantity being addressed as -2(SP), which is two bytes longer.

On a 16-bit machine one tends to obsess about a couple of bytes.

Answer 3

The PDP-11 was especially designed to allow code to be written in either of the three common addressing schemes:

• Zero Address (Stack)
• On Address (Acumulator)
• Two Address

There's a quite nice paper Gordon Bell (et. al) wrote describing the PDP-11 architecture (*1), which in great detail talks about the ability to handle a stack machine using either register - except R6 and R7 that is, as they are predefined as Hardware Stack and PC. It is the combination of features (*2) for their new mini-computer (*3), that may confuse a bit.

[...]the stack grows downward. [...] But isn't that just convention? From what I understand we could equally well reverse the direction[...]. Yet every document I see says the stack grows downward on the PDP-11. So what am I missing?

It's the hardware stack. While each register (*4) can be used to manage a stack structure, R6 is tied to certain instructions and hardware functions manipulating this stack. To keep it manageable two assumptions are common to all of them:

• The (R6) stack is word sized
• The (R6) stack grows downward

For example JSR pushes the return address down on R6, while RTS pulls it upward. Similar all hardware interrupts/trap will use the same fashion. So, unless one can take the risk of having the top of stack destroyed by any of those, going along and using R6 is a downward fashion is a must.

Of course, this does not hinder any programming (language) to let the hardware stack run for itself and use any other Register (R0..R5) for their own purpose - like one (or more) software stacks managing procedure passing and local data structures. Forth may be the best known example here.

The mentioned paper goes into great detail that the PDP-11 is well suited to handle stack orientated programming so due its auto-indexing instruction set.

Still, while the handling of a data stack can easy be implemented using any other register, the return stack is hard to be moved, as there are no simple instructions replacing JSR/RTS. Sure, one could use some /360-like mechanics, but missing a LINK type instruction each call would be something like

MOV [Rmystack]+,PC
JMP subroutine

while returning would translate to

MOV R0,-[Rmystack]
ADD R0,2
MOV PC,R0

Doesn't look great with just the little memory they had back then, not to mention execution time.

Bottom line: The Hardware Stack (R6) is quite useful due it's implied use of R6 but ties it's working to being downward and word sized.

So, why do we then not use a different software stack for parameter passing, growing upward or being of different (byte) size? Well, as so often 'Hail C' is the answer. When C was developed, they decided to accept the limitations and go with the hardware stack. It removes the need to use a separate register and, at least for simple issues, it's as good as any other. As a result we got stuck with a downward growing word sized stack and the evil mix-up of program flow management and data management.

---

*1 - Made for a speech during the Minicomputers - the profile of tomorrow's components track at the AFIPS Spring Joint Computer Conference in May 1970 in Atlantic City and published in Volume 36 of their proceedings.

*2 - They tried to dance on as many weddings as possible. Process control as well as scientific computing and general purpose. Hardware supported CISC structure as well as simple and symmetric instruction set for high level (synthetic) programming.

*3 - The paper starts with a real nice definition of what a micro-, mini- and midi-computer is by defining them by number of registers, word length, memory size, memory speed and cost. A worthwhile metric to be copied here to not only show that these terms weren't (and aren't) as settled as one assumes today, as well, as it's about capabilities, not size.

       Address     Word         CPU        Cost  Data
         Space     Size       State              Types
       (Words)   (Bits)  (Register)  (1970 USD)
Micro       8k     8~12           2          5k  Integer, bit Vector
Mini       32k    12~16         2-4       5~10k  Indexing
Midi   65~128k    16~24        4-16      10~20k  Floating Point

It also shows that even the most basic of today's microcontrollers (AVR, PIC, not to mention ARM) may well be placed in the Midi category of 1970, if not Mainframe :)

*4 - Using R7 can as well be a bit ... well, lets say complicated :))

Answer 4

On a PDP-11, stacks can grow both upwards and downwards according to the choice of the programmer. As any of the GPR (General Purpose Registers) can be a stack pointer, they generally behave all the same, stacks can grow upwards or downwards in memory.

When the PDP-11 is servicing an interrupt or trap, however, the implementors of the machine had to save the PSW and current PC somewhere to be able to return to the user program after the ISR, they decided to use R6 for that, which thus became SP. And they also had to make a design decision how they wanted to use this stack, and they decided to grow it downwards. As SP must be able to push and pop words at any time (because the CPU needs to be able to push a word address and PSW when servicing an interrupt), they also had to make sure SP is word-aligned at any time, thus, when you push a byte to SP, SP will be decremented by 2 to keep it word-aligned, unlike all other registers that are used as stacks. All other instructions that implicitly use R6/SP (like JSR and traps, for example) also use to the same convention. R6/SP is thus special in that any user program needs to comply with this decision. That is why other answers call R6 "the hardware stack", which I find sortof wierd, because there's just as much "hardware" to R6 as to the other registers, R6 is only special as the CPU itself uses it for housekeeping through interrupts. DEC themselves also never used this term.

Just for completeness: There are actually some CPU architectures where it is the choice of a system implementor to have the stack used by the CPU itself for storing intermediate state grow upwards or downwards (generic ARM, or HPPA, for example). The PDP-11 is not one of them.

Answer 5

Doesn't it really depend on how you draw your memory.

     ________               ________
FFFF|        |         0000|        |
    | map 1  |down         | map 2  | ^
    |        | v           |        |up
0000|________|         FFFF|________|

If it is a decreasing address, then in map1, it grows downwards but in map2, it grows upwards.

Map1 is typically drawn like a normal graph, where 0 is at the bottom and the higher address is on top. Hardware engineers and mathematicians would normally draw the memory graph like this.

Map2 is typically drawn by software people who normally sort things in ascending order.

It also depends on the person's background. Some people find it difficult to visualise if the graph is drawn upside down from what they are used to thinking.

Look at the hardware manual - I have seen manuals where the map is drawn both ways. Some manufacturers draw it with 0 on top, others draw it with 0 at the bottom. Sometimes, both conventions are used by the same manufacturer (Intel): typically chapters written by different people. It really depends on which convention you are used to when you say the stack grows upwards or downwards.