时间戳

首页 > 解决方案 > MIPS - 不返回预期结果

assembly - MIPS - 不返回预期结果

问题描述

我刚开始研究 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,$0,2
addi $a1,$0,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,$0,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。

但是对我来说一切都很好，我觉得我的程序应该可以正常运行

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

标签： assemblymips

解决方案

您在（递归）调用之前计算 k+2+8*n ，这在理论上是好的 - 但不能将结果留在$t0调用中，因为它会被调用清除。

你有两个选择：

  • 在调用之前保存$t0（在计算该子表达式之后），并在之后恢复它。
    如果你这样做，你将需要另一个字的堆栈空间（但你也不需要保存n( $a0) ，因为它在调用后不使用）。

  • 在调用后计算 k+2+8*n，这不需要额外的堆栈空间，尽管这将使用调用后保存的n( $a0)。

当您将参数寄存器原样保存在序言中时，它们不需要在结语中恢复，因此只需要$ra为返回而恢复。

用于addiu您的堆栈分配/释放。地址算术应该使用无符号来完成。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

推荐阅读