Sticking it to the Stack

Stacking it up — general background on stacks

In abstract terms, a stack is an area of memory that holds all local variables and parameters used by any function, and remembers the order in which functions are called so that function returns occur correctly.

One way of describing the stack is as a last in, first out (LIFO) abstract data type and linear data structure.

A stack can have any abstract data type as an element, but is characterized by two fundamental operations, called push and pop (or pull).

The push operation adds a new item to the top of the stack, or initializes the stack if it is empty. If the stack is full and does not contain enough space to accept the given item, the stack is then considered to be in an overflow state.

The pop operation removes an item from the top of the stack. A pop either reveals previously concealed items, or results in an empty stack, but if the stack is empty then it is considered to be in an underflow state.

A stack pointer is the register which holds the value of the stack. The stack pointer always points to the top value of the stack.

A stack is a restricted data structure, because only a small number of operations are performed on it. The nature of the pop and push operations also means that stack elements have a natural order. Elements are removed from the stack in the reverse order to the order of their addition: therefore, the lower elements are those that have been on the stack the longest.

Stacks in Y86

In Y86, the push operation is accomplished using the pushl instruction, the pop operation is accomplished using the popl instruction, and a stack pointer must be set explicitly through the esp register.

The program below illustrates how to use the stack in Y86 to swap two registers.

Function calls in Y86 — Manipulating the stack

In assembler, the stack is used extensively in function calls — particularly when recursive function calls are required.

As a matter of practicality, each time a function is called, its local variables and parameters are “pushed onto” the stack. When the function returns, these locals and parameters are “popped.” Because of this, the size of a program’s stack fluctuates constantly as the program is running, but it has some maximum size.

You can read more about how to use the stack to store variables and parameters when performing function calls in Y86 here.