The Stack

Does not refer to the same thing as the stack ADT, but is implemented with the stack ADT.

The stack stores static memory, unlike the heap. The stack is faster than the heap, but we must be able to determine the sizes of memory at compiler time.

Implement the Stack

We implement stack memory with the stack ADT.

Stack Pointer

Definition

We designate a register to hold the address of the top of the stack (MIPS register 30, ARM register 13), known as the stack pointer

In MIPS, when the CPU starts running, register 30 has the value of the size of memory (i.e the end of memory, not a valid address)

Full vs Empty, Ascending vs Descending Stack

A stack can be "full" or "empty" (note this does not refer to the capacity at all), and can be ascending or descending. For now (CS241E, ECE222, and most microprocessors) we only care about full descending stacks.

Info

A "full" stack has its stack pointer at the last element
An "empty" stack has its stack pointer at the next empty space
An ascending stack has its stack pointer growing as more elements are pushed
A descending stack has its stack pointer shrinking as more elements are pushed (i.e it grows towards 0)

Figure

Pushing and Popping

Push: decrement SP by 4, store value at address in SP
- ARM V7 Assembly: STR Rn, [SP, #-4]!
Pop: read word at SP, increment SP by 4
- ARM V7 Assembly: LDR Rn, [SP], #4

Example

In CS241E MIPS Assembly in Scala:

// Push
LIS(Reg.result) // alias for R3
Word(encodeSigned(4))
SUB(Reg.stackPointer, Reg.stackPointer, Reg.result)
SW(Reg(1), 0, Reg.stackPointer)

// Pop
LW(Reg(1), 0, Reg.stackPointer)
LIS(Reg.result)
Word(encodeSigned(4))
ADD(Reg.stackPointer, Reg.StackPointer, Reg.result)

Rule of thumb: for every push, you need a pop

Example

ARM V7 Assembly:

MOV R0, #1         ; push
STR R0, [SP, #-4]!

MOV R0, #2         ; push
STR R0, [SP, #-4]!

LDR R1, [SP, #4]   ; read (peek), reg[1] <- 0000 0001 (doesn't change the stack)

LDR R0, [SP], #4   ; pop, reg[0] <- 0000 0002

LDR R0, [SP], #4   ; pop

We can use ADD SP, #8 instead of two pop operations if we don't need the values.

Pushing and Popping Multiple Registers

Only applicable for ARM Assembly at the moment. Would recommend using some sort of chunk instead.

We can take advantage of the load and store multiple instructions.

Table

Stack Type	Push	Pop
Full descending	`STMFD (STMDB)`	`LDMFD (LDMIA)`
Full ascending	`STMFA (STMIB)`	`LDMFA (LDMDA)`
Empty descending	`STMED (STMDA)`	`LDMED (LDMIB)`
Empty ascending	`STMEA (STMIA)`	`LDMEA (LDMDB)`

Note that there are also alternate names for the address modes (i.e DB -> decrement before, IA -> increment after).

We also have our aliases PUSH and POP which are used more frequently.

Example

PUSH {R1, R4-R6, R10, LR}

Registers 1, 4, 5, 6, and 10 are Pushed onto stack from high register # to low register #

POP {R1, R4-R6, R10, PC}

Note we can pop back into different registers.

Stack Frame (Activation Record) and Frame Pointer

Definition

A frame pointer is a copy of SP made at the beginning of a procedure that does not change during execution of the procedure.
A stack frame or activation record is an area of the stack reserved for the variable instances of an invocation of a procedure.

In CS241E, register 29 will be the frame pointer.
Each variable will be an offset from the frame pointer

Example

Symbol table:

Variable	Offset from FP
a	0
b	4
c	8

To read variable c into Reg(1):

LW(Reg(1), 8, Reg(29))

To write Reg(1) to b:

SW(Reg(1), 4, Reg(29))

Chunk

CS241E convention, not common.

Definition

A chunk is a block of consecutive memory addresses. Words are indexed by a symbol table that maps variables to offsets.

Always push/pop entire chunks at the same time.

Chunk header: 2 words

1st word = size of chunk in bytes
2nd word = number of pointers

Example

Note that this requires pointer words to be first, then non-pointers to be after.