遞歸過程要將呼叫在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