[MIPS] Stacks

In MIPS architecture, the stack grows downward in terms of memory -- when an element is pushed into a stack, it should be stored in an address lower than that of the previous element. We assume the address of the topmost (newest) element in the stack is the one stored in the stack pointer register $sp. There are several ways to implement the push or pop instructions. Below are some examples. 

Push():

#moving the pointer down and storing the element at the address
addi $sp, $sp, -4
sw $t1, 0($sp)

#storing an element and then moving the pointer to where it is stored
sw $t1, -4($sp)
addi $sp, $sp, -4

Pop():

#loading the element and then moving the pointer upwards
lw $t1, 0($sp)
addi $sp, $sp, 4

#loading two elements and moving the pointer to where the third element was stored
lw $t1, 0($sp)
lw $t2, 4($sp)
addi $sp, $sp, 8

Procedure Calls

In MIPS, a function that calls another function is the caller, and the function that receives the call is the callee. After the callee is executed, it returns the control back to the caller. The jal instruction is used to make a procedure call, and the jr instruction is used to make a procedure return. 

 

jal label: The jump and link instruction copies the address of the next instruction into the return address register $ra and then jumps to the address at label. 

jr $register: The jump register instruction jumps to the address in $register. We often use jr $ra to jump to the point saved as the return address. 

Basic procedure-calling

When a callee makes a procedure call, however, the $ra will be overwritten. To solve this issue, a stack is used to hold return addresses for nested procedure calls. Stack can also be used to pass on arguments, save local variables, and store return values.  

Leaf Procedure	Non-Leaf Procedure
Does not call any other procedures	Calls another procedure; MUST back up the return address before making the call using stack

Find the factorial 5!: 

main: 
	#pass arguments in registers $a0-$a3 
	lw $a0, 5 
    
	#call functions using jal 
	jal factorial 
	#$ra = line 7

fact:      
	#checking for basecase ----
	#if x <= 0, stop recursing 
	ble $a0, $zero, fact_zero

	#push n and $ra into stack 
	addi $sp, $sp, -8
	sw $ra, 4($sp) 
	sw $a0, 0($sp) 

	#call factorial(n-1)
	addi $a0, $a0, -1
	jal fact 
	#$ra = line 22

	#pop n and $ra from stack
	lw $a0, 0($sp)
	lw $ra, 4($sp)
	addi $sp, $sp, 8
    
	#return factorial(n-1)*n
	mul $v0, $v0, $a0 
    
	jr $ra 

fact_zero:    
	#return 1
	addi $v0, $zero, 1    
	jr $ra

Let's break down what's happening in the above code. 

1. For x = 5, we start by calling fact(5). $ra points to, say, 1024, the address of the next instruction in the main function at line 7. 
2. fact: If n is greater than 0, push the return address in $ra and the value of n into the stack. At first, the stack is [1024, 5]. Now call fact(n-1). The return address register now points to line 22 below the 'jal fact' instruction, $ra = 1084. fact(n-1) is called x(=5) times. The resulting stack is [1024, 5, 1084, 4, 1084, 3, 1084, 2, 1084, 1]. n is now zero, so we branch to fact_zero.
3. fact_zero: If n <= 0, we return 1, so set $v0 = 1 and jump to the address saved in $ra, 1084, to the instruction at line 22 in fact function.
4. fact (line 22~): Pop two values from stack so that the stack is [1024, 5, 1084, 4, 1084, 3, 1084, 2], $a0 = 1, and $ra = 1084. $v0 *= $a0, so $v0 = 1. Jump to $ra, which is line 22 again. Repeat this until $v0 = 1 * 2 * 3 * 4 * 5 and we make a jump to the first return address, $ra = 1024.