MIPS

Question

我刚开始研究MIPS，我正在尝试将一个用C 编写的递归程序转换为MIPS，但遇到了一些问题。

C语言程序如下：

int calculate (int n, int k){
  int b;
  b = k+2;
  if (n == 0)
     b = 10;
  else
     b = b + 8*n + calculate (n-1,k+1);
  return b*k;

}

这是我用 MIPS 编写的程序：


main:

addi $a0,[=11=],2
addi $a1,[=11=],3

jal calculate
addi $t3,$v0,0
li $v0,10
syscall

calculate:
    #a0 = n, a1 = k, t0 = b
    addiu $sp,$sp,-12
    sw $a0,0($sp) # save a0 to stack
    sw $a1,4($sp) # save a1 to stack
    sw $ra,8($sp) # save return address to stack
    
    # Base case
    bne $a0,[=11=],else # n!=0
    li $t0,10 # b = 10
    mul $v0,$t0,$a1 # v0 = b*k
    j return # Go to Return
else:
    addi $a0,$a0,-1 # n - 1
    addi $a1,$a1,1 # k + 1
    jal calculate
    add $t0,$t0,$v0 # b += calculate(n-1,k+1)
    lw $a0,0($sp)  # Retrive the original n
    lw $a1,4($sp) # Retrieve the original k
    addi $t0,$a1,2 # b += k+2
    li $t1,8 # load 8 as constant
    mul $t1, $t1,$a0 # 8*n
    add $t0,$t0,$t1 # b = b + 8*n
    mul $v0,$t0,$a1 # v0 = b*k
    
return:
    lw $a0,0($sp) # retrive a0 from stack
    lw $a1,4($sp) # retreive a1 from stack
    lw $ra,8($sp) # retrive return address to stack
    addiu $sp,$sp,12
    jr $ra

我正在使用 MARS 模拟器，它显示我的结果寄存器 $t3 的值为 0x384，十进制为 900。当我运行C程序时，结果是831.

但是我觉得一切都很好，我觉得我的程序应该运行ning 正确

我的程序还有其他问题吗？用MIPS写递归程序对我来说确实有点复杂

Answer 1

您在（递归）调用之前计算 k+2+8*n，这在理论上是可以的 — 但将结果留在调用中的 $t0 中是不行的，因为它将被擦除打电话出去。

你有两个选择：

在调用之前保存 $t0（在计算该子表达式和之后），并在之后恢复它。
如果你这样做，你将需要另一个堆栈词space（但你也不需要保存n（$a0），因为它在打电话）。
调用后计算k+2+8*n，这不需要额外的堆栈字space，尽管那会使用保存的n ($a0) 后调用。

当你在序言中原样保存参数寄存器时，它们不需要在结语中恢复，所以只需要为return恢复$ra。

使用 addiu 作为堆栈 allocation/deallocation。地址算术应该使用无符号来完成。（请注意 addi 和 addiu 之间的唯一区别是 addi 检查有符号算法中的溢出，我们不希望地址 b/c 它们是无符号的。）

在您最近的编辑中：

jal calculate
add $t0,$t0,$v0 # b += calculate(n-1,k+1)  #### $t0 not good to source here
lw $a0,0($sp)  # Retrive the original n
lw $a1,4($sp) # Retrieve the original k
addi $t0,$a1,2 # b += k+2

建议先做b = k+2:

jal calculate
lw $a0,0($sp)   # Retrive the original n
lw $a1,4($sp)   # Retrieve the original k
addi $t0,$a1,2  # b = k+2                  ##### b=k+2 do that first
add $t0,$t0,$v0 # b += calculate(n-1,k+1)  ##### now  b +=  will work

MIPS - 未返回预期结果

MIPS - Not returning the expected result

assembly