The Stack

A "stack" is a basic data structure used to store data. A stack is a predefined area of memory and a variable containing the address to the "top" of the stack. A stack provides two operations, called "push" and "pop", that allow a program to manipulate this structure.

Typically, a PDP-11 program implements a stack by designating some area of memory as the stack, and setting the "top" of the stack to the highest address of the memory area. A "push" operation decrements the top of the stack, and moves the pushed value to that address. A "pop" operation returns the value at the top of the stack, and increments the top of the stack. In effect, a stack "grows" downward from the top.

Stacks are used in many algorithms as a temporary storage area for small peices of data. For example, if there's a value in R0, a program can push the value of R0 on to the stack, use R0 however it needs, and can pop the value from the stack into R0.

The PDP-11 addressing modes make implementing a stack in a very natural way. Let's say we want to designate addresses 400 through 1000 to be memory area for the stack, and we can use R0 to hold the address of the top of the stack. A "push" operation can be performed by using the autodecrement addressing mode with R0, and the pop operation can be performed by using the autoimcrement addressing mode with R0. For example:

        MOV     #1000,R0        ; R0 IS TOP OF STACK, SET IT TO 1000

        MOV     'A,R1           ; PUT ASCII A INTO R1

        MOV     R1,-(R0)        ; DECREMENT THE TOP OF STACK TO 776, MOVE
                                ; THE VALUE OF R1 TO THAT LOCATION.
                                ; THIS IS THE PUSH OPERATION

        CLR     R1              ; SET R1 TO ZERO

        MOV     (R0)+,R1        ; GET THE VALUE AT TOP OF STACK (776), AND
                                ; INCREMENT THE TOP OF STACK TO 1000. MOVE
                                ; THE VALUE INTO R1

The PDP-11 processor reserves the R6 register to be the top of stack for system usage, primarily for holding addresses for subroutine linkage, and also often used to pass parameter values to subroutines, or for other temporary storage. As a result, the R6 register is also called the "stack pointer", or SP. Programs are free to use this stack for its own purposes; as a result, code such as the above example would typically use -(SP) and (SP)+. There is nothing otherwise special about R6/SP. Some architectures, such as the MOS 6502, have special instructions to manipulate the stack pointer. In the PDP-11, however, the stack pointer is just another register.

There is an exception to that last statement. The top of the stack can be set to any value; typically it's set to 1000 or higher, depending on the needs of the program. If the SP register is autodecremented below 400, the "stack overflow trap" is raised by the processor, which is considered an error condition, and the processor will pass control to the routine at the address stored at address 4. More information about this is provided in the article about interrupts.