c-MIPS中的这种快速排序有什么问题

Question

这是我在MIPS上进行快速排序时使用的C代码，在Mars编辑器上，我在运行这些代码时遇到问题

#include <stdio.h>
void QuickSort(int *array, int first, int last){
int q;
if (first<last){
int value = array[last];
int i = first-1;
int tmp;
int j = first;
while(j<=last){
if (array[j] <= value) {
i++;
tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
j++;
}
q = i;
QuickSort(array,first,q-1);
QuickSort(array,q+1,last);
}
}

到目前为止，这是我的MIPS翻译，我得到了一个无限循环

.data
numArray: 30, 15, 11, 40, 75, 80, 70, 60
first: 0
last: 7
.text
main:
la $a0, numArray
lw $a1, first
lw $a2, last
jal quick_sort
li $v0, 10
syscall
quick_sort:
subi $sp, $sp, 4        #reserving memory in the stack
sw $ra, 4($sp)          #storing the return adress in the stack
xor $t0, $t0, $t0       #int q
bge $a1, $a2, label1    #if (first<last)
sll $t1, $a2, 2         #int value = array[last];
add $t1, $t1, $a0       #callculating array[last] in $t1
lw $t1, 0($t1)          #array[last] = array direction + 4 * last
or $t2, $t1, $zero      #$t2 will be value
subi $t3, $a1, 1        #int i = first-1;
xor $t4, $t4, $t4       #int tmp
or $t5, $a1, $zero      #int j=first
j label2                #while(j<=last)
label3: sll $t6, $a2, 2     #calculating array[j] adress
add $t6, $t6, $a0
lw $t7, 0($t6)          #calculating array[j] value
bgt $t7, $t1, label4    #if (array[j] <= value)
addi $t3, $t3, 1        #i++
sll $s0, $t3, 2         #calculating array[i] adress
add $s0, $s0, $a0   
lw $s1, 0($s0)          #calculating array[i] value
or $t4, $s1, $zero      #tmp = array[i]
sw $t7, 0($s0)          #array[i] = array[j];
sw $t4, 0($t6)          #array[j] = tmp;
label4: addi $t5, $t5, 1    #end if; j++
label2: ble $t5, $a2, label3    #while condition
or $t0, $t3, $zero      #q = i
lw $a1, first           #first value on the second parameter
subi $a2, $t0, 1        #q-1
jal quick_sort          #QuickSort(array,first,q-1)
addi $a1, $t0, 1        #q+1
lw $a2, last            #last value on the third parameter
jal quick_sort          #QuickSort(array,q+1,last);
label1: lw $ra, 4($sp)      #Recovering the return address from the stack 
addi $sp, $sp, 4        #releasing memory
jr $ra                  #going to the return address

也许我需要在堆栈上存储更多的东西或我缺少的东西，谢谢你的帮助，如果你在那里看到任何奇怪的东西，请让我知道检查一下。

Answer 1

编辑：
正如Minn在评论中指出的，我错过了以下两行：

sll $t1, $a2, 2         #int value = array[last];

因此，虽然这一行与其中的注释不匹配，但值的加载似乎是正确的。

结束编辑

我不熟悉这个特定的程序集，但问题似乎是所谓的"寄存器撞击"：

根据文档，jal只存储返回地址，但不存储任何寄存器。

lw $a1, first           #first value on the second parameter
subi $a2, $t0, 1        #q-1
jal quick_sort          #QuickSort(array,first,q-1)
addi $a1, $t0, 1        #q+1
lw $a2, last            #last value on the third parameter
jal quick_sort

您使用$t0作为q局部变量，但从未将其保存在堆栈中。

在第一次调用jal quick_sort #QuickSort(array,first,q-1)之后，$t0的值会有所不同，但您会立即在addi $a1, $t0, 1 #q+1行中使用它，就好像它从未更改过一样，然后将结果传递给第二次对QuickSort的调用。

与此错误等效的C将使q全局化，并在函数的开头添加q = 0;。

您必须记住，当在程序集中工作并为局部变量使用寄存器时，在从当前函数调用任何其他函数之前，必须将它们的状态保存到堆栈中，否则您将丢失状态，代码将无法按预期工作！

老实说，这是我第一次看到这种特定的汇编语言，所以我可能还错过了其他错误，但这些是最明显的错误，所以很容易发现。