Quicksort from C to MIPS - How to pass parameters and maintaining variables for stack frame?

Question

I am creating a Quicksort algorithm on an array of integers. I am using this C algorithm and translating it into MIPS. However, MIPS and recursion is very tough indeed.

I am unsure how to send parameters into the recursive call QS. I recently discovered that I can change my $s registers for each frame in the call stack, by moving the stack pointer 4 bytes. This will allow me to change the $s registers for each stack frame such that I don't need a million variables for each QS frame.

My problem is that I don't really understand how and when to set and get these $sx values during recursion.

Answer 1

Recursion is implemented by moving the stack pointer register ($sp).

First of all, let's understand the point of moving the stack pointer: When you use recursion in a high level language, what it does, basically, is to "save" the state of the current function call in the "stack memory". To achieve this, you will have to:

1. Save the current state of your program (all the variables/registers you are using within the scope of the "function"), in the stack memory;
2. Call the function "recursively" (which might modify all the registers you were using);
3. When the function finishes, you have to restore the previous state and "free" the space you allocated.

But besides that, we have to save the value of $ra, to keep track of where we're supposed to go when the upper function ends.

Here's a simple example of a program that calculates factorial(n) recursively:

.text
main:
  # Calls Fact with Input ($a0) N = 10
  li $a0, 10
  jal fact
  # prints the Output ($v0) Factorial(N)
  move $a0, $v0
  li $v0, 1
  syscall
  # exit
  li $v0, 10
  syscall

# Input: $a0 - N
# Output: $v0 - Factorial(N)
fact:
  # Fact(0) = 1
  beq $a0, 0, r_one
  # Fact(N) = N * Fact(N-1) use recursion
  # allocate 8 bytes in the stack for storing N, and $ra
  addi $sp, $sp, -8
  # stores N in the first, and $ra in the last position
  sw $a0, 4($sp)
  sw $ra, 0($sp)
  # call Fact(N-1)
  addi $a0, $a0, -1
  jal fact
  # Restore the values of N and $ra
  lw $a0, 4($sp)
  lw $ra, 0($sp)
  # Free the 8 bytes used
  addi $sp, $sp, 8
  # Set the return value to be N * Fact(N-1) and return
  mul $v0, $a0, $v0
  jr $ra
  # return 1;
  r_one:
    li $v0, 1
    jr $ra

This is what you should keep in mind when implementing your code, basically. Just pay attention to:

• The stack pointer is decremented;
• How many bytes you need to allocate. In this example I use 2 32-bits integers, 8 bytes in total. It will deppend on how many variables you need to store, and their size.
• How to access them with lw and sw, using the correct index. Also, be aware of memory alignment;
• This does not only apply for recursion. You can use the stack memory to call another function that uses registers that are being used (basically the same thing as recursion, except that you don't need to save $ra). And also store an array, a struct, etc.

Edit:

Some considerations:

• The right place to do that is where your code calls the function (allocate and save), and after this call (restore and free).
• Understand your code to know which variables need to be saved (might be used).