error in partition function (mips assembly)

Question

This is the code I wrote trying to implement the c partition function in mips. There seems to be an error because the program doesn't work, yet I can't find where it is. I know it would be best to debug it, but I don't know how to debug. Also I am kind of confused about storing and restoring registers, perhaps the problem lies there.

Also I installed a mips assembly debugger in visual studio but the application doesn't recognize it and there seems to be no other options for mips.

partition:

#int partition(int f, int l) {
# int pivot = v[l];
# int i = f;

# for (int j = f; j < l; j++) 
#   if (v[j] < pivot) 
#    swap(i++,j);

# swap(i, l );
# return (i);
#}

addi $sp, $sp, -24 #make room for 6

    sw $a0, 0($sp)  #store f
    sw $a1, 4($sp)  #store l
    sw $ra, 8($sp)      #store return address
    sw $t2, 12($sp) #store i
    #sw $t3, 16($sp) #store j
    sw $t1, 16($sp) #store pivot
    sw $s0, 20($sp) #store s0

    la $s0, v    # s0 = address of v

sll $t0, $a1, 2 # t0 = 4*l
add $t0, $s0, $t0   # t0 = address of v[l]
lw $t1, 0($t0)  # t1 = v[l], t1 = pivot

move $t2, $a0 # t2 = i, t2 is f
move $t3, $a0 # t3 = j, t3 is f

for1:

    slt $t4, $t3, $a1   #if(j<l) t4=1
    beq $t4, $zero, end1 #goto end1 if t4 = 0

    sll $t4, $a0, 2      # t4 = 4*j
    add $t4, $s0, $t4       #t4 = address of v[j]
    lw $t5, 0($t4)      #t5 = v[j]

    slt $t6, $t5, $t1   # if (v[j] < pivot) t6=1 else t6=0


    bne $t6, $zero, else 
    move $a0, $t2 #a0 = i 
    move $a1, $t3 # a1 = j
    jal swap                #    swap(i++,j);
    addi $t2, $t2,1 # i++

    else:
        addi $t3, 1 #j++

        j for1
#here stops the for1 loop

end1: #come here when exiting the for1 loop

    # a0=f & a1=l
    move $a0, $t2 #a0 = i
    lw $a1, 4($sp) #a1= l
    jal swap

    move $v0, $a0 #v0=i / return i 

    lw $ra, 8($sp) #restore ra
    lw $s0, 20($sp) #restore s0
    lw $a0, 0($sp) #restore a0
    lw $a1, 4($sp) #restore a1
    #lw $s1, 4($sp) #restore s1

    addi $sp, $sp, 24 #restore stack
    jr $ra

Answer 1

Also I am kind of confused about storing and restoring registers, perhaps the problem lies there.

Yes, your register usages diverge from the standard calling convention.  We don't see the caller of your partition function, nor do we see the swap function, so we cannot comment on them.

By the MIPS calling convention, $s registers, if a function uses any of them, must have their original values preserved / restored before returning to the caller.  By contrast, the other registers ($a, $t, $v) don't require such preservation, so can be freely used without further consideration.

$s registers are useful to hold variables that are used in loops that have function calls.  This is because function calls are allowed to wipe out the non-$s registers, but must preserve the $s registers.  So, a variable stored in an $s register will survive a function call.

The alternative to $s registers is stack memory as that will also survive a function call.  To use stack memory we must store and reload, and that is ok for non-looping non-repetitive code but for looping code those loads & stores represent overhead.

By contrast, $s registers are also stored and loaded, but only once per function invocation, instead of in the body of the function.  So if the body of the function has looping then doing a load & store in prologue/epilogue is more efficient than doing loads & stores inside the function body.

So, the rule of thumb is: if there's function calls but no loops, consider stack memory for the variables that need to survive function calling.  If there's no function calls, then don't use $s registers.  if there's loops or lots of function calls, consider $s registers for variables that need to survive function calling.

You need to be able to analyze whether a variable is live across a function call.  The analysis is: is the value held in a variable present/existent before a function call, and then used after that function call?  If so, that variable must survive function calling, so must use either stack memory or an $s register.

You're using $t registers for variables used in loops with function calling — that is incorrect and potentially a problem (we don't see swap so cannot say for sure).

You are also preserving in prologue (and restoring in epilogue) registers that don't merit such preservation, which is wasteful but otherwise harmless.