Microprocessor Design
Back To Introduction



The Stack

by

James Adrian


      Indentation areas (like the one at the start of this paragraph) are links to Google. This allows you to conveniently search for any unfamiliar words or phrases by copying the text in question and clicking on an indentation.


      The stack is a last-in-first-out storage mechanism. A section of system memory is set aside to be used to store numbers (whatever their meaning) in such a way that the next item to be retrieved from the stack is the most recent item to be stored in it. Microprocessors facilitate this by including a hardware stack pointer. Storing a number on the stack is said to be a push. Retrieving a number from the stack is said to be a pop. Names of program instructions use these terms. An instruction such as PUSH REGISTER X can store a named register in the stack. An instruction such as POP REGISTER X can read a number from the stack and place that number in the named register. In both kinds of cases, the system address indicated by the stack pointer is the address used to read from or write to the stack.

      If each new item that is pushed onto the stack is to be stored in the next higher address, the stack pointer is then incremented. One could invert this and decide that each new item pushed onto the stack is to be stored in the next lower address. The choice is arbitrary.

      The contents of the stack pointer can be managed by changing the address in the stack pointer just ahead of a push and just after a pop. When an instruction calls for an item to be pushed onto the stack, the contents of the stack pointer is first change (incremented or decremented) and then the item is stored at that location. When an instruction calls for an item to be read from the stack, it is read from the address pointed to be the stack pointer and then the stack pointer is changed (decremented or incremented). This would require initializing the stack pointer to an address just outside the stack address range that is actually used for storage and retrieval. It would also require preventing a pop from being the first access. One possible implementation would be to initialize the stack at zero and use addresses 1 through 1023 as the range of the stack. The first push would write into address 1. The stack pointer would be a ten-bit counter.

      The stack pointer must be capable of being incremented and also must be capable of being decremented. If this is done by the ALU, and if the stack pointer is a general register, the contents of that register would frequently need to be moved to the ALU and then moved to the system address bus. This motivates the use of a hardware counter. A resettable and presettable up/down counter would be a reasonable choice to serve as the stack pointer.

      Because there are only a fixed number of memory cells devoted to the stack, it is possible that a program may mistakenly attempt to pop an item from a stack that is empty. This would be called an stack underflow error. It is also possible to attempt to push an item onto a stack that is full. This would be called an stack overflow error.

      A programmer may wish to implement an additional stack, or for some reason implement a stack other than the one provided by the microprocessor. This would be called a software stack.

      Because software is often written as a system of subroutines, the stack is useful in storing a system memory address that must be returned to when the subroutine is finished. At the initiation of the subroutine, the next address to be accessed in the calling program (the program that calls the subroutine) is pushed onto the stack. When the subroutine is finished, the microprocessor must pop that address from the stack.

      Typically, the address that must be returned to is not the only item stored on the stack during a subroutine. The processor status register must be restored whenever a program invokes a subroutine that might (an almost always does) change the status bits. Many times it is also critical to preserve certain registers being used by the calling program.

      The stack is also used to facilitate hardware interrupts. A signal from system hardware, such as a peripheral device, constitutes a request that a particular program be executed. This requires that the microprocessor include an input reserved for this purpose and a status bit that indicates whether the microprocessor is allowed by the current program to acknowledge and service an interrupt. Typically the bit is named I, the interrupt disable bit. If this bit is set to 1, the processor does not check the interrupt input form the system upon completion of each instruction. If this status bit is 0, the processor checks the interrupt input form the system upon completion of each instruction. The status bit could just as well be made to work with these binary values reversed. The bit could be called it the interrupt enable bit if the microprocessor logic were made consistent with that.


Contact       https://www.futurebeacon.com/jamesadrian.htm