求助：将求Floor平方根的C递归代码转为MIPS汇编遇问题

以下是你提供的C语言递归实现Floor平方根的代码：

uint32_t isqrt(uint32_t n) {
  if(n<2) return n;
    uint32_t s = isqrt(n >> 2) << 1;
    uint32_t l = s + 1;
  if (l * l > n) 
    return s;
  else
    return l;
}

你编写的MIPS汇编代码存在以下几个关键问题：

#isqrt
isqrt:
#prologue
subu    $sp, $sp, 12
sw  $ra, 8($sp)
sw  $s0,  4($sp)
sw  $s1, 0($sp)

#if(n<2) n Branch if Greater Than 2
blt     $a0, 2, lt2 #if(n<2) return n;
#else uint32_t small = isqrt(n >> 2) << 1;       
srl     $s0, $a0, 2  # small = isqrt(n >> 2)
jal     isqrt
sll   $s0, $s0, 1 # then  << 1 

add    $s1, $s0, 1 # large = small + 1
li     $s3, 0
mul     $s3, $s1, $s1 # large = large * large\
#if large * large > n return small else return large
bgt     $s3, $s0, small # if l * l > n return small
move    $v0, $t1 # else return large

lt2:
move $v0, $a0;
j end

small:
move $v0, $s0
j end

end:
lw $ra, 8($sp)
lw $s0, 4($sp)
lw $s1, 0($sp)
addi $sp, $sp, 12
jr      $ra                 

问题点及修正方案： #

• 递归调用参数传递错误：
  你将右移后的n存入s0后直接调用jal isqrt，但MIPS函数的参数是通过$a0传递的，递归调用时$a0仍为原输入值，导致递归逻辑完全错误。
  修正：将右移后的值放到$a0再调用递归，同时保存原$a0（后续比较需要用到原n）：

  # prologue中新增保存原n的逻辑
  subu    $sp, $sp, 16
  sw  $ra, 12($sp)
  sw  $s0,  8($sp)
  sw  $s1, 4($sp)
  sw  $s2, 0($sp)
  move    $s2, $a0  # 保存原n的值
  
  # 递归调用部分修改
  srl     $a0, $s2, 2  # 用原n右移2位作为递归参数
  jal     isqrt
  sll     $s0, $v0, 1  # 递归返回值存在$v0，左移后存入$s0
  

• 递归返回值处理错误：
  jal isqrt执行后，返回结果存在$v0，但你直接对s0进行左移操作，此时s0是右移后的原n值，并非递归返回的结果。修正如上，先将$v0的值存入s0再左移。

• 比较条件错误：
  原C代码是判断l*l > n，但你写的是bgt $s3, $s0, small，用s0（也就是s）和l*l比较，完全不符合逻辑，应该和原n（保存到s2的原$a0值）比较：

  bgt     $s3, $s2, small  # 用原n的值和l*l比较
  

• 返回large时寄存器错误：
  你写的move $v0, $t1，但t1从未被赋值，large的值存在s1中，应该改为：

  move    $v0, $s1  # 返回large
  

• 保存寄存器使用问题：
  你使用了s3但没有在prologue中将其保存到栈中，MIPS的s系列寄存器属于保存寄存器，必须在函数开头保存、结尾恢复，否则会破坏上层调用的寄存器值。可以改用t系列临时寄存器（比如t0）来存储l*l的结果，临时寄存器不需要入栈保存：

  mul     $t0, $s1, $s1  # 用t0存储l*l
  bgt     $t0, $s2, small
  

• 注释错误：
  mul行的注释最后有多余的反斜杠，且注释描述错误，应改为# 计算l*l。

修正后的完整示例片段： #

#isqrt
isqrt:
#prologue
subu    $sp, $sp, 16
sw  $ra, 12($sp)
sw  $s0,  8($sp)
sw  $s1, 4($sp)
sw  $s2, 0($sp)
move    $s2, $a0  # 保存原n的值

#if(n<2) return n
blt     $a0, 2, lt2

# 递归计算isqrt(n >> 2) << 1
srl     $a0, $s2, 2  # 用原n右移2位作为递归参数
jal     isqrt
sll     $s0, $v0, 1  # 递归返回值左移1位得到s

add    $s1, $s0, 1 # l = s + 1
mul     $t0, $s1, $s1 # 计算l*l

# 判断l*l > n ? 返回s : 返回l
bgt     $t0, $s2, small
move    $v0, $s1
j end

lt2:
move $v0, $s2
j end

small:
move $v0, $s0
j end

end:
lw $ra, 12($sp)
lw $s0, 8($sp)
lw $s1, 4($sp)
lw $s2, 0($sp)
addi $sp, $sp, 16
jr      $ra                 

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