c++ - MIPS速溶

Question

我已经根据C++代码在MIPS汇编中编写了快速排序算法。在C++中，它工作得很好，但在MIPS中，它不起作用。我调试了它，问题是递归。这是算法:

QuickSort(Data[], l , r)
{
    // If the first index less or equal than the last index
    if l <= r:
    {
        // Create a Key/Pivot Element
        key = Data[r]

        // Create temp Variables to loop through array
        i = l;
        j = r;

        while i <= j:
        {
            while Data[i] < key AND i < r:
                i = i + 1
            while Data[j] > key AND j > 0:
                j = j - 1
            if i <= j:
            {
                swap Data[i], Data[j]
                i = i + 1 
                j = j + 1
            }
        }

        if l < j:
            QuickSort(Data, l, j);
        if r > i:
            QuickSort(Data, i, r);
    }
}

这是MIPS代码。在某些情况下它可以工作。例如:array = {6，5，4，4，3，2，1}。
MIPS代码:

#-function QuickSort(arr, left,right)
    #parameter
    #          $a0: array
    #          $a1: left
    #          $a2: right

QuickSort:
    subu $sp, $sp, 16
    sw   $a0, 0($sp)
    sw   $a1, 4($sp)
    sw   $a2, 8($sp)
    sw   $ra, 12($sp)

    la   $s0, 0($a0)
    move $s1, $a1
    move $s2, $a2

    bgt  $s1, $s2, done

    sll  $t3, $s2, 2
    add  $t3, $s0,$t3
    lw   $t2, 0($t3)

    move $t0, $s1
    move $t1, $s2

    WhileOuter:
        While_i:
            sll $t3, $t0, 2
            add $t3, $s0, $t3
            lw  $t4, 0($t3)

            bge $t4, $t2, EndWhile_i
            bge $t0, $s2, EndWhile_i
            addi $t0, $t0, 1    
            j While_i
        EndWhile_i:

        While_j:
            sll $t3, $t1, 2
            add $t3, $s0, $t3
            lw $t4, 0($t3)

            ble $t4, $t2, EndWhile_j
            blez $t1, EndWhile_j
            addi $t1, $t1, -1
            j While_j
        EndWhile_j:

        bgt $t0, $t1, EndWhileOuter

        #swap arr[i], arr[j]
        sll $t4, $t0, 2
        sll $t5, $t1, 2

        add $s3, $s0, $t4
        add $s4, $s0, $t5

        lw $t4, 0($s3)
        lw $t5, 0($s4)

        sw $t4, 0($s4)
        sw $t5, 0($s3)

        addi $t0, $t0, 1
        addi $t1, $t1, -1
        j WhileOuter
    EndWhileOuter:

    bge $s1, $t1, call2
    lw $a1, 4($sp)
    move $a2, $t1
    move $a0, $s0
    jal QuickSort

    call2:
    ble $s2, $t0, done
    move $a1, $t0
    lw $a2, 8($sp)
    move $a0, $s0
    jal QuickSort
    done:
    addu $sp, $sp, 16
    lw $a0, 0($sp)
    lw $a1, 4($sp)
    lw $a2, 8($sp)
    lw $ra, 12($sp) 

    jr $ra

任何人都可以在此代码中找到错误吗？谢谢你的帮助。

Answer 1

您正在使用保存的寄存器$s0，$s1，$s2，但不遵循为调用者保留这些寄存器中的值的要求。

因此，不能保证QuickSort的调用方将保留其$s寄存器。

您没有显示其余的代码，例如main。

但是，我们知道QuickSort会自我调用，并且在对其进行第一次递归调用之后，它依赖于$s0和$s2寄存器，这应该没问题，但是我们知道QuickSort无法正确保留它们。

您需要更仔细地分析您的寄存器用法和要求。在第一次(递归)调用QuickSort之后，将运行以下代码。它正确地期望保留$s0和$s2，但也期望保留$ t0 －这是一个临时寄存器，表示不被调用保留，因此这是一个错误。

        jal QuickSort       # this call wipes out $t0
     call2:
        ble $s2, $t0, done  # what's supposed to be in $t0 here?
        move $a1, $t0
        lw $a2, 8($sp)
        move $a0, $s0

您不需要保存的寄存器$s1，而应为此选择一个临时寄存器。我将在原始$a1寄存器中使用该变量。

您将$a0寄存器保存到内存中，但未使用该内存位置的值。

它不存在，或者您更改了外部while循环退出条件的位置。它不再位于循环的顶部。现在看起来像这样:

  while true:
        {
            while Data[i] < key AND i < r:
                i = i + 1
            while Data[j] > key AND j > 0:
                j = j - 1
            if i > j break;

Python代码可以

    if i <= j:
    {
        swap Data[i], Data[j]
        i = i + 1 
        j = j + 1
    }

而在交换之后，汇编代码将i ++变为j--。

您正在使用$s3和$s4，但出于简单的临时用途-出于这些目的，请使用$t寄存器。