我的MIPS版partition函数报错：无输出或内存地址错误，求排查

原始需求与代码 #

目标C代码 #

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);
}

自行编写的MIPS汇编代码 #

swap:                           # swap entry point
        sll $t0, $a0, 2         # make i into address
        sll $t1, $a1, 2         # make j into address
        
        la  $t2, v              # load vector address
        
        add $t3, $t2, $t0       # get address of v[i]
        add $t4, $t2, $t1       # get address of v[j]
        
        lw  $t5, 0($t3)         # get v[i]
        lw  $t6, 0($t4)         # get v[j]
        
        sw  $t5, 0($t4)         # set v[j] = v[i]
        sw  $t6, 0($t3)         # set v[i] = v[j]

        jr      $ra             # return to caller

partition:
        la  $t0, v              # load vector address
        
        add  $sp, $sp, -16      # pop 2 items from stack
        sw   $s0, 0($sp)
        sw   $s1, 4($sp)
        sw   $s2, 8($sp)
        sw   $s3, 12($sp)
        
        sll  $t2, $a1, 2        # make l into address
        add  $t3, $t0, $t2      # find address of v[l]
        lw   $s2, 0($t3)        # load v[l] into $s2 (pivot)

        add  $s0, $a0, $zero    # int ($s0) i = f
        
        add  $s1, $a0, $zero    # int ($s1) j = f
        
        add  $s3, $a1, $zero
        
Loop:                           # "for" loop
        slt  $t7, $s1, $s3      # check j < l
        beq  $t7, $zero, EndLoop # exit loop if j >= l
        
        sll  $t2, $s1, 2        # make j into address
        add  $t3, $t0, $t2      # find address of v[j]
        lw   $t5, 0($t3)        # load v[j] into $t5
        
        
        slt  $t6, $t5, $s2      # if (v[j] < pivot) set $t6 = 1
        beq  $t6, $zero, continueLoop 
        add  $a0, $s0, $zero
        add  $a1, $s1, $zero
        jal  swap
        
        addi $s0, $s0, 1        # i++
        
continueLoop:
        addi $s1, $s1, 1        # j++
        j    Loop               # go to start of Loop
        
EndLoop:
        
        add  $v0, $s0, $zero
        jr   $ra

错误点与修复方案 #

1. 未保存返回地址$ra且栈操作错误 #

• 问题：调用swap时会覆盖$ra寄存器，但partition函数未将$ra保存到栈中，导致从swap返回后，partition的jr $ra会跳转到无效地址，触发内存访问错误。同时开头的栈操作注释错误（实际是分配栈空间而非弹出），且未在函数结束时恢复栈指针和保存的寄存器，破坏调用者栈环境。
• 修复：
  • 调整栈空间为20字节，新增保存$ra的操作：

    add  $sp, $sp, -20      # 为寄存器分配栈空间
    sw   $ra, 0($sp)        # 保存返回地址
    sw   $s0, 4($sp)
    sw   $s1, 8($sp)
    sw   $s2, 12($sp)
    sw   $s3, 16($sp)
    

  • 在函数返回前恢复所有寄存器并重置栈指针：

    lw   $ra, 0($sp)
    lw   $s0, 4($sp)
    lw   $s1, 8($sp)
    lw   $s2, 12($sp)
    lw   $s3, 16($sp)
    add  $sp, $sp, 20       # 释放栈空间
    

2. 遗漏核心的swap(i, l)调用 #

• 问题：C代码末尾的swap(i, l)是partition逻辑的关键步骤，你的MIPS代码完全缺失该调用，不仅功能错误，还可能导致数据未正确处理引发异常。
• 修复：在EndLoop块中、返回之前添加该调用：

  EndLoop:
      add  $a0, $s0, $zero    # 传入swap参数i
      add  $a1, $a1, $zero    # 传入swap参数l
      jal  swap
  

3. 数组v未正确定义 #

• 问题：如果汇编代码中没有在.data段声明全局数组v，或数组大小不足，la $t2, v会指向无效内存，触发Bad Memory Address错误。
• 修复：在代码开头添加.data段并定义数组：

  .data
  v: .word 3, 1, 4, 1, 5, 9, 2, 6  # 根据测试用例调整数组内容和大小
  

修复后的完整MIPS代码示例 #

.data
v: .word 3, 1, 4, 1, 5, 9, 2, 6  # 测试用数组

.text
.globl main, partition, swap

swap:                           # swap entry point
        sll $t0, $a0, 2         # 计算i的字节偏移量
        sll $t1, $a1, 2         # 计算j的字节偏移量
        
        la  $t2, v              # 加载数组基地址
        
        add $t3, $t2, $t0       # 获取v[i]的地址
        add $t4, $t2, $t1       # 获取v[j]的地址
        
        lw  $t5, 0($t3)         # 读取v[i]
        lw  $t6, 0($t4)         # 读取v[j]
        
        sw  $t5, 0($t4)         # 将v[i]存入v[j]
        sw  $t6, 0($t3)         # 将v[j]存入v[i]

        jr      $ra             # 返回调用者

partition:
        la  $t0, v              # 加载数组基地址
        
        add  $sp, $sp, -20      # 为寄存器分配栈空间
        sw   $ra, 0($sp)        # 保存返回地址
        sw   $s0, 4($sp)
        sw   $s1, 8($sp)
        sw   $s2, 12($sp)
        sw   $s3, 16($sp)
        
        sll  $t2, $a1, 2        # 计算l的字节偏移量
        add  $t3, $t0, $t2      # 获取v[l]的地址
        lw   $s2, 0($t3)        # 加载pivot = v[l]

        add  $s0, $a0, $zero    # i = f
        add  $s1, $a0, $zero    # j = f
        add  $s3, $a1, $zero    # 保存l到$s3
        
Loop:                           # 循环开始
        slt  $t7, $s1, $s3      # 判断j < l
        beq  $t7, $zero, EndLoop # j >= l时退出循环
        
        sll  $t2, $s1, 2        # 计算j的字节偏移量
        add  $t3, $t0, $t2      # 获取v[j]的地址
        lw   $t5, 0($t3)        # 读取v[j]
        
        slt  $t6, $t5, $s2      # 判断v[j] < pivot
        beq  $t6, $zero, continueLoop 
        
        add  $a0, $s0, $zero    # 设置swap参数i
        add  $a1, $s1, $zero    # 设置swap参数j
        jal  swap
        
        addi $s0, $s0, 1        # i++
        
continueLoop:
        addi $s1, $s1, 1        # j++
        j    Loop               # 回到循环开头
        
EndLoop:
        add  $a0, $s0, $zero    # 设置swap参数i
        add  $a1, $a1, $zero    # 设置swap参数l
        jal  swap
        
        add  $v0, $s0, $zero    # 设置返回值为i
        
        # 恢复寄存器和栈
        lw   $ra, 0($sp)
        lw   $s0, 4($sp)
        lw   $s1, 8($sp)
        lw   $s2, 12($sp)
        lw   $s3, 16($sp)
        add  $sp, $sp, 20       # 释放栈空间
        
        jr   $ra                 # 返回调用者

内容的提问来源于stack exchange，提问作者Panagiotis