9

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?

  • 1
    That is very probably a problem with the definition of "stack". Generic data structure (can grow in any direction) vs. how does the CPU implicitly uses a stack for call and return, interrupts,... (grows downwards only) – tofro Oct 20 '18 at 8:03
9

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.

  • 1
    It's not just the extra bytes, the instruction will need an extra read cycle to get them too. – JeremyP Oct 24 '18 at 10:50
21

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.

  • Good answer, the minor thing that bothers me how you distinguish between "hardware stack" and "own data stack" - These are both "hardware stacks" and I would rather use terminology like "generic data structure" vs. "CPU implicitly using this structure" – tofro Oct 20 '18 at 8:08
  • 1
    @tofro St start with, the Term was inserted by the OP, not the Answer, but more importent, the Stack controled by R6 is a hardware stack, as it is use and management is implied by certain instruction (JSR, RTS), as well as by the CPU hardware itself (interrupts, instruction fault, etc.) in contrast to any stack run by using general puropse instructions (MOVE) and direct register manipulaten (for MARK) is a software stack Also, softwarestacks can be byte or word on a PDP-11, while hardwarestack is always words. – Raffzahn Oct 20 '18 at 9:52
  • @Raffzahn Are you trying to argue that MOV #100,-(R6) is "hardware" and `MOV #100,-(R1) is "software"? That sounds pretty weird. DEC didn't use that distinction in their manuals. They call a stack a stack. – tofro Oct 20 '18 at 10:29
  • 4
    @tofro it is more that JSR, RET on the PDP-11etc allways uses the hardware stack, since the CPU internally decides what stack pointer to use and in what direction to move the pointer. If you use MOV you decide yourself what pointer to use, and if you consider it to be a stock or not. – UncleBod Oct 20 '18 at 11:25
  • 3
    @tofro JSR and RTS and TRAPs are hardware. The softwarestack can only handle a subset of what the hardware stack can do - while at the same time the hardware stack adds restrictions to its use as growing downward and word-organization. – Raffzahn Oct 20 '18 at 11:41
7

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 :))

  • Your first paragraph is a bit misleading: While "classic" architectures before the PDP-11 had chosen one or two of the addressing schemes in your bullet list as their programming model, the PDP-11 was one of the first architectures that could do all of them with a true set of GPR registers. – tofro Oct 20 '18 at 16:24
  • @tofro That's exactly what I say, code could be written to fit either scheme. While mixng is possible, it wouldn't know of any language requireing it. – Raffzahn Oct 20 '18 at 16:31
  • Your assembly is initially confusing to an -11 user because -11 assembly uses src,dst order; TTBOMK this was unique at the time, although the spread of Unix and especially GNU has carried what is now often called 'AT&T' syntax to other ISAs. More substantively but still minor, the size of 'JMP subr' (that you need to skip on return) is 4 bytes not 2. – dave_thompson_085 Feb 4 at 23:27
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.

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.

-3

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.

  • 5
    No, it does not as growing down is not a grraphic issue, but means growing down to a lower address, and no matter what machine is used, 0000h is always lower than FFFF (asaddresses are unsigned). – Raffzahn Oct 20 '18 at 10:11
  • 1
    @Raffzahn from a certain POV, on x86_64 addresses might be considered signed (there's a gap between canonical addresses with MSB=1 and those with MSB=0, while if we treat them as signed, the address space is continuous). They are officially not, of course. – Ruslan Oct 20 '18 at 11:25
  • @Ruslan Nop. The addres space is aways unsigend, no matter which CPU, as there is no negative memory build in, or is it? What you're referign to are addressing modes. A programm can of course (well, depending on the CPU) use signed addressing modes relative to some base. Just it doesn't change that a resulting address will be unsigned. – Raffzahn Oct 20 '18 at 11:46
  • 1
    @Raffzahn that's why I say "from a central POV". In practice address space is neither signed nor unsigned, since the only arithmetic operation which distinguishes between these on two's complement CPUs (which x86_64 is) is division, and addresses are never divided. And the mapping of an address (that particular bit pattern) doesn't change whether you consider it signed on not. – Ruslan Oct 20 '18 at 13:20
  • When you are at the bottom of the stack, it normally means you are the last one and the top of the stack, you are the first one. To explain that, the diagram will need to be drawn with the 0 on top and terms like growing downwards are not normally used because the lowest address is the top and the highest address is the bottom. – cup Oct 20 '18 at 15:35

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.