Notes on the Call Stack in MIPS

MIPS Calling Conventions

• Register Usage:
  • Arguments: Stored in $a0</code>, <code>$a1, $a2</code>, <code>$a3.
  • Return values: Stored in $v0</code>, <code>$v1.
  • Return address: Stored in $ra.
• Calling a Subroutine: Use jal Label instruction.
• Returning from a Subroutine: Use jr $ra instruction.
• Preservation: Subroutines must always preserve registers $s0</code> to <code>$s7, $ra</code>, <code>$sp, $fp</code>, and <code>$gp.
• Caller Assumptions: Callers must not assume that $t0</code> to <code>$t9, $a0</code> to <code>$a3, $v0</code>, or <code>$v1 are preserved.
• Stack Pointer: The stack pointer is managed through $sp.

Understanding the Stack

• Definition: A stack is a data structure that allows access to the top item only.
  • Operations:
  • Push: Add an element to the top of the stack.
  • Pop: Remove the top element from the stack.
  • Cannot pop an element if the stack is empty.

The Call Stack

• Characteristics:
  • Located at the top of the memory; structured like a stack.
  • Grows downwards (the top of the stack is at the bottom).
  • Contains stack frames, where each frame holds data for subroutine execution.
  • The stack pointer ($sp) indicates the end of the stack and points to the last byte of the last stack frame.

Stack Pointer ($sp)

• Functionality:
  • A 32-bit register that tracks the stack's top.
  • It is preserved by subroutines (callee-saved); they must restore it before returning.
  • Changes to $sp effectively manage the stack size.

Importance of the Call Stack

• Subroutine Calls: When a subroutine (e.g., red) calls another (blue), the return address ($ra) must be saved and restored to return correctly.
• Each subroutine needs its stack frame to manage its local state correctly, especially when calling other subroutines.

Stack Frame Management

• Creation and Destruction:
  • Stack frames must be created upon entering a subroutine and destroyed before returning.
  • Example of stack frame management:
  • addi $sp, $sp, -4: Move $sp down to create space for a new frame.
  • sw $ra, ($sp): Store return address on the stack.
  • After using the stack, restore the frame and increment $sp back to release space.

What to Save in a Stack Frame

• Registers:
  • Preserved Registers: $s0</code> to <code>$s7, $ra must always be stored.
  • Unpreserved Registers: $t0</code> to <code>$t9, $a0</code> to <code>$a3, $v0</code>, <code>$v1 should be saved by the caller if used after the call.
• Local Variables: Larger variables like arrays or structures not fitting in registers must be saved in the stack frame.
• Excess Arguments: If more than four arguments are used, these should also be pushed to the stack.

Stack Frame Structure Example

• General layout of a stack frame on entry and exit:

mySubroutine:
 addi $sp, $sp, -12  # Adjust stack for 3 saved registers
 sw $ra, ($sp)       # Store return address
 sw $s0, 4($sp)     # Store $s0
 sw $s1, 8($sp)     # Store $s1
 # Execute subroutine tasks
 lw $s0, 4($sp)     # Restore $s0
 lw $s1, 8($sp)     # Restore $s1
 addi $sp, $sp, 12   # Release stack space
 jr $ra              # Return to caller

Call Stack Example

• When functions are called sequentially:
  • funA() calls funB() and funC(), potentially leading to calls from funC() to other subroutines like funD().
• The stack holds the state of all active functions, preserving their return points until they return to the caller.

Conditions for Stack Frame Usage

• A stack frame is essential when a subroutine calls another.
• A stack frame is unnecessary for a leaf function that does not modify preserved registers or call others.
• If relevant preserved registers are saved into unpreserved registers without new calls, this could simplify management.