Previous: The Stacksystem
Up: The Stacksystem
Next: Stack Overflow/Underflow.
Previous Page: The Stacksystem
Next Page: Stack Overflow/Underflow.

Concept of a Stack.

Typically, stacks are realized as conventional register files with special addressing hardware. A stack pointer identifies the topmost element of the stack, and is modified during a push or pop operation implicitly. Since a stack can grow beyond the size of on--chip storage, the bottom part is held in memory. The stack on the processor realizes a circular buffer for the top elements. In the following ``on--chip stack'' means the on--chip section of the stack, and ``swap--area'' the part held in memory, unless otherwise stated.

To map a stack onto a register file it is necessary to define the bottom element of the on--chip stack which is usually done by a last-pointer. In the following, instead of stack pointer the term top-pointer is used as a complement to last-pointer. Both are abbreviated as and , respectively, in formulas. By convention, the stack grows to higher addresses, the top-pointer denotes the topmost element, the last-pointer points one cell below the bottom element of the on--chip stack, and denotes the size of the on--chip stack. should be a power of 2, thus allowing to use the last bits from the top-pointer to address the on--chip stack.

The basic stack operations - push or pop an element to or from the stack, respectively, and read or write the top of a stack - are not sufficient as a basis for an instruction set [2]. A more general approach incorporates the following operations:

1. read indexed: value := Stack[];
   special case: , read top element
2. write indexed: Stack[] := value;
   special case: , replace top element
3. create-frame: Stack[] := value, TopPt := ;
   special case: push
4. delete-frame: value := Stack[], TopPt :=

The delete-frame operation is not a generalization of the pop operation. A closer look unveils that during a push operation the address of the stack access and the new value of the top-pointer are identical but they are different for a pop operation. Here the index is the top-pointer itself, but the new value for it is . It does not matter whether the top-pointer addresses the topmost element or the free cell above it, or in which direction the stack grows. In either case one of the addresses does not match the new value of the top-pointer. However, there is a simple and elegant solution: A three address instruction consists of a destination and two source specifiers. The first source operand accesses the top element, the second the next element and this second address is taken as the new value for the top-pointer. The following example clarifies this:

value := Stack[TopPt] + Stack[TopPt - 1] , TopPt := TopPt - 1