MIPS堆棧可視化

Question

下面是一個階乘函數的c代碼。 我清楚地知道遞歸函數是如何工作的。 但我無法想象或不知道如何在MIPS堆棧上工作。

MIPS CODE

我的問題是， 我們如何保存遞歸函數的棧（保存返回地址&參數）的遞歸的每一步？

我知道，對於每個遞歸函數，我們保存參數和返回地址，然後重新調整堆棧指針。

有人可以幫助我想象過程如何工作。

Answer 1

前提 MIPS中的堆棧與任何其他架構中的堆棧一樣，因此您可以僅使用Google。

---

假設堆點的內存的任意位置：

| xxx |    xxx = Undefined 
| xxx | <- $sp 
|  | 
|  | | Free area, stack moves down 
|  | V 

現在只是模擬，比方說，fact(3)通話。
^{_{您粘貼了代碼的圖像，因此此處不顯示任何代碼。一個可複製的代碼會使這個答案更加清晰。}}

fact的每次調用按此順序推送返回地址和參數。
我們假設fact位於0x1000，而fact的調用位於0x1ffc。

fact(3) 

| xxx | 
| xxx | 
| 0x2000 | Return address to caller of fact(3) 
| 3 | <- $sp   Argument of fact(3) 
|  | 

fact(2) called from fact(3) 

| xxx | 
| xxx | 
| 0x2000 | Return address to caller of fact(3) 
| 3 | Argument of fact(3) 
| 0x1028 | Return address to L1+8 label 
| 2 | <- $sp   Argument of fact(2) 

fact(1) called from fact(2) 

| xxx | 
| xxx | 
| 0x2000 | Return address to caller of fact(3) 
| 3 | Argument of fact(3) 
| 0x1028 | Return address to L1+8 label 
| 2 | Argument of fact(2) 
| 0x1028 | Return address to L1+8 label 
| 1 | <- $sp   Argument of fact(1) 

fact(0) called from fact(1) 

| xxx | 
| xxx | 
| 0x2000 | Return address to caller of fact(3) 
| 3 | Argument of fact(3) 
| 0x1028 | Return address to L1+8 label 
| 2 | Argument of fact(2) 
| 0x1028 | Return address to L1+8 label 
| 1 | Argument of fact(1) 
| 0x1028 | Return address to L1+8 label 
| 0 | <- $sp   Argument of fact(0) 

fact(0) return 1並從堆棧中移除兩個項目。
fact(0)是一個葉調用，即最後一次調用，所以沒有其他調用改變$ra，此外$a0（參數）不需要，因此保存在堆棧上的這兩個值通過增加$sp來簡單地丟棄。

Just before "jr $ra" in fact(0) 

| xxx | 
| xxx | 
| 0x2000 | Return address to caller of fact(3) 
| 3 | Argument of fact(3) 
| 0x1028 | Return address to L1+8 label 
| 2 | Argument of fact(2) 
| 0x1028 | Return address to L1+8 label 
| 1 | <- $sp   Argument of fact(1) 

其他收益從堆棧恢復的$a0和$ra值來計算n*fact(n-1)並返回到調用者。

Just before "jr $ra" in fact(1) 

| xxx | 
| xxx | 
| 0x2000 | Return address to caller of fact(3) 
| 3 | Argument of fact(3) 
| 0x1028 | Return address to L1+8 label 
| 2 | <- $sp   Argument of fact(2) 

Just before "jr $ra" in fact(2) 

| xxx | 
| xxx | 
| 0x2000 | Return address to caller of fact(3) 
| 3 | <- $sp   Argument of fact(3) 

Just before "jr $ra" in fact(3) 

| xxx | 
| xxx | <- $sp 

請注意堆棧如何返回到遞歸鏈末尾的原始位置。