递归过程要将呼叫在MIPS

Question

我工作的分配类似于二叉树时遇到困难，了解如何正确C.编写以下问题

int choose(int n, int k){ 
    if (k == 0) { 
     return 1; 
    } else if (n == k) { 
     return 1; 
    } else if (n < k) { 
     return 0; 
    } else { 
     return choose(n-1, k-1) + choose(n-1, k); 
    } 
} 

我的想法是使用三个寄存器每次调用$s0, $s1, $s2时将值存储到堆栈中，其中$s0将包含更新后的值n; $s1将维持值k;并且$s2将在第二个choose(n-1, k)中保留值k，因为该值只会在父呼叫改变时才会降低。我选择这个的原因是因为k的值不是从这个函数中的每个调用中减去的，它应该是相同的，直到父进程在先前的调用中递减它为止。

这是我试图做的Choose程序。问题是我没有得到正确的答案，当然。

Choose: 
    #store current values onto stack 
    addi $sp, $sp, -16 
    sw $ra, 0($sp) 
    sw $s0, 4($sp) 
    sw $s1, 8($sp) 
    sw $s2, 12($sp) 

    #check values meet criteria to add to $v0  
    beq $s1, $0, one 
    beq $s0, $s1, one 
    blt $s0, $s1, zero 
    beq $s2, $0, one 

    #no branches passed so decrement values of n and k 
    subi $s0, $s0, 1 
    subi $s1, $s1, 1 

    #move values of registers to $a's for argument passing 
    move $a0, $s0 
    move $a1, $s1 

    jal Choose #call procedure again 

    #this is where I'm having my problems 
    #not sure how to loop the procedure to get 
    #the second half of the equation Choose(n-1,k) 
    #which is the reason for the next 2 lines of code 
    move $a2, $s2 
    jal Choose 

    add $v0, $v0, $v1 
    j Choose_Exit 


#add one to $v1 from branch passed 
one: 
    addi $v1, $v1, 1 
    j Choose_Exit 

#branch returns 0 
zero: 
    addi $v1, $v1, 0 
    j Choose_Exit 

#return values to caller from stack 
Choose_Exit: 
    lw $s2, 12($sp) 
    lw $s1, 8($sp) 
    lw $s0, 4($sp) 
    lw $ra, 0($sp) 
    addi $sp, $sp, 16 
    jr $ra 

所以我在了解如何正确地实现两倍于该递归过程将它们加在一起的问题。我可以理解如何在MIPS中创建递归过程来执行阶乘，因为这总是任何语言的递归定义。但是，使用不同论点的递归，然后将它们加在一起会让我困惑不已。

当写在纸上时，我明白这个过程可以用父母和孩子的二叉树来表示。父母是单功能Choose(n,k)，孩子是Choose(n-1, k-1) + Choose(n-1, k)，并且叶子孩子从if声明中分支一次，它将一个数字传递给等待另一个被呼叫者部分的加数的父母返回其值等。等等

任何帮助指出我在正确的方向，我做错了什么我的方法会很好。我明白了一开始，我明白了最后，只需要一些帮助来帮助理解中间最重要的部分。

Answer 1

你非常接近。

您用四个字建立了堆栈帧：返回地址，arg1，arg2和保存返回值。

你的主要障碍是在第一次打电话给你的函数之后，你必须将$v0保存到堆栈中[就像上面提到的Margaret]。

这里有一些我相信会起作用的代码。这与你的非常相似，但我从头开始写。它具有第一个调用返回值的正确“push”/“pop”。

我没有为早期转义[非递归]情况添加一个小优化：它们省略了创建堆栈帧。

不管怎么说，那就是：

#@+ 
# int 
# choose(int n, int k) 
# { 
# 
#  if (k == 0) 
#   return 1; 
# 
#  if (n == k) 
#   return 1; 
# 
#  if (n < k) 
#   return 0; 
# 
#  return choose(n - 1,k - 1) + choose(n - 1,k); 
# } 
#@- 

    .text 

# choose -- choose 
# 
# RETURNS: 
# v0 -- return value 
# 
# arguments: 
# a0 -- n 
# a1 -- k 
# 
# registers: 
# t0 -- temp for 1st return value 
choose: 
    beqz $a1,choose_one   # k == 0? if yes, fly 
    beq  $a0,$a1,choose_one  # n == k? if yes, fly 
    blt  $a0,$a1,choose_zero  # n < k? if yes, fly 

    # establish stack frame (preserve ra/a0/a1 + space for v0) 
    sub  $sp,$sp,16 
    sw  $ra,12($sp) 
    sw  $a0,8($sp) 
    sw  $a1,4($sp) 

    addi $a0,$a0,-1    # get n - 1 (common to both calls) 

    # choose(n - 1,k - 1) 
    addi $a1,$a1,-1    # get k - 1 
    jal  choose 
    sw  $v0,0($sp)    # save 1st return value (on _stack_) 

    # choose(n - 1,k) 
    addi $a1,$a1,1    # get k (from k - 1) 
    jal  choose 

    lw  $t0,0($sp)    # "pop" first return value from stack 
    add  $v0,$t0,$v0    # sum 1st and 2nd values 

    # restore from stack frame 
    lw  $ra,12($sp) 
    lw  $a0,8($sp) 
    lw  $a1,4($sp) 
    add  $sp,$sp,16 
    jr  $ra      # return 

choose_one: 
    li  $v0,1 
    jr  $ra 

choose_zero: 
    li  $v0,0 
    jr  $ra 

---

UPDATE：

首先，我喜欢你如何注意该过程，你做你打电话之前。我要偷了！

做我的客人！这是来自多年的写作技巧。对于我关于如何写好asm的思考，请参阅我的回答：MIPS linked list

我试过这个，它的工作原理。我需要试验你的代码，以理解为什么堆栈被操纵时（总是认为它必须在一个proc的开始和结束）。

通常，堆栈帧被在PROC开始时建立，并从在PROC端恢复。您处理“快速转义”[非递归]个案的代码是正确，基于已建立的框架。

这只是一个小小的优化。但是，它来自这样一个事实，因为mips有很多寄存器，对于小函数，我们甚至不需要堆栈帧，特别是如果函数是“叶”或“尾”（即它没有调用任何其他功能）。

对于较小的[非递归]功能，有时我们可以逃脱，仅仅保留$ra（例如）一个一个字堆栈帧：fncA调用fncB，但fncB是叶。 fncA需要一帧但fncB确实不是。事实上，如果我们控制两种功能，我们知道是fncB不不修改给定温度寄存器（例如$t9），我们可以在那里保存，而不是在fncA创建堆栈帧中的返回地址：

fncA: 
    move $t9,$ra     # preserve return address 
    jal  fncB     # call fncB 
    jr  $t9      # return 

fncB: 
    # do stuff ... 
    jr  $ra      # return 

通常情况下，我们不能依赖fncB保持$t9，因为，根据ABI的mips，fncB是随意修改/垃圾任何寄存器是不$sp或$s0-$s7。但是，如果我们制作的功能使得我们认为fncB对于fncA是“私人”的（例如像只有fncA有权访问的C static功能），我们可以做，无论我们想要什么。

信不信由你，fncA以上是 ABI符合。

给定被叫（例如fncA）不不需要保留$ra为[起见]其呼叫者，只是为了本身。而且，重要的是值里面$ra，而不是具体的寄存器。被叫方只需要保留$s0-$s7，确保$sp在退出时具有相同的值作为条目，并且它返回到主叫方的正确地址[​​所做的 - 因为它的值在$ra中时被称为]。

我喜欢你使用临时寄存器。

一个额外的寄存器是需要因为，在MIPS，我们可以不从内存操作数做算术运算。 mips只能做lw/sw。 （即）有没有这样的事情：

add  $v0,$v0,0($sp) 

我用$t0为了简单/清晰度，因为，当你需要一个临时REG，$t0-$t9是平常的人使用。当使用$t0时代码“读取更好”。但是，这是只是的一个约定。

在mips ABI中，$a0-$a3可以修改，$v1也可以修改，因为只有$s0-$s7需要保留。而且，“修改”意味着它们可以用于保存任何价值或用于任何目的。

在上面的链接中，请注意strlen直接增加$a0以查找字符串的结尾。它使用$a0作为一个有用的用途，但就其来说，$a0正在被“废弃”[由strlen]。此用法是符合ABI。

在choose，我可以使用几乎任何注册：$v1的$a2-$a3代替$t0。实际上，在choose的那个特定点上，$a0不再需要，所以它可以用来代替$t0。虽然对于choose，我们是非 -ABI符合（因为我们保存/恢复$a0-$a1），这将工作在choose，因为我们从函数epilog [stack frame pop]恢复原始值$a0，保留递归性质功能。

正如我所说的，$t0-$t9是通常用于临时空间的寄存器。但是，我已经编写了使用全部10个函数的函数，并且仍然需要更多（例如，使用Bresenham圆算法绘制到帧缓冲区中）。 $v0-$v1和$a0-$a3可以用作临时寄存器以获得额外的6.如果需要，$s0-$s7可以保存在堆栈帧中，仅用于释放它们以用作更多临时寄存器。

Answer 2

声明：我重写汇编代码而不是检查它。

1. 有些延时槽要考虑如何更好地使用它们，并使它们更明确，以避免在分支指令后聚合隐式nop指令。
2. 将选择（n - 1，k - 1）和选择（n - 1，k）之间的调用顺序颠倒，以更智能地使用$ a0和$ a1以及堆栈。
3. 通过调用choose（n-1，k-1）来限制堆栈使用，并使用tail调用select（n-1，k-1）。
4. 堆栈a0-1而不是a0的值更有意义。
5. 我们将所有内容累加到$ v0中，而不是堆叠它。我们保留$ t0作为本地结果添加到$ v0，因为它很便宜，而我们可以用$ v0做直接的东西来放弃它。
6. 因此，整体变化应该使icache更快乐，更少的指令和更快的堆栈空间更快乐。

的汇编代码：

#@+ 
# int 
# choose(int n, int k) 
# { 
# 
#  if (k == 0) 
#   return 1; 
# 
#  if (n == k) 
#   return 1; 
# 
#  if (n < k) 
#   return 0; 
# 
#  return choose(n - 1,k - 1) + choose(n - 1,k); 
# } 
#@- 

    .text 

# choose -- choose 
# 
# RETURNS: 
# v0 -- return value 
# 
# arguments: 
# a0 -- n 
# a1 -- k 
# 
# registers: 
# t0 -- temp for local result to accumulate into v0 
choose: 
    j  choose_rec 
    addui $v0, $zr, 0    # initialize $v0 to 0 before calling 
choose_rec: 
    beqz $a1,choose_one   # k == 0? if yes, fly 
    addui $t0,$zr,1    # branch delay-slot with $t0 = 1 
    beq  $a0,$a1,choose_one  # n == k? if yes, fly 
    nop        # branch delay-slot with $t0 = 1 already done 
    blt  $a0,$a1,choose_zero  # n < k? if yes, fly 
    addui $t0,$zr,0    # branch delay-slot with $t0 = 0 

    # establish stack frame (preserve ra/a0/a1) 
    sub  $sp,$sp,12 
    addui $a0,$a0,-1    # get n - 1 (common to both calls) 
    sw  $ra,8($sp) 
    sw  $a0,4($sp)   
    jal  choose_rec    # choose(n - 1,k) 
    sw  $a1,0($sp) 

    # restore from stack frame 
    lw  $ra,8($sp) 
    lw  $a0,4($sp) 
    lw  $a1,0($sp) 
    add  $sp,$sp,12 

    # choose(n - 1,k - 1) 
    j  choose_rec    # tail call: jump instead of call 
    addi $a1,$a1,-1    # get k - 1 

choose_one: 
choose_zero: 
    jr  $ra      # return 
    addui $v0,$v0,$t0    # branch delay-slot with $v0 += $t0