一、Procedures 和 Function Calls

1. 程序的基本結構：
   • 在 RISC-V 中，程序調用遵循標準的過程，這個過程的每個步驟包括：
     • 把參數放在函數可以讀取的位置（例如寄存器 a0-a7 用於參數傳遞）。
     • 使用 jal 指令將控制權轉移到函數，即跳轉並保存返回地址到 ra（返回地址 register。
     • 函數會在自己的記憶體空間中獲取所需的資源，如 register 和 stack。
     • 執行函數的邏輯，完成任務。
     • 將返回值放在指定的寄存器中（例如 a0 和 a1），以便呼叫者可以讀取結果。
     • 使用 jr ra 指令把控制權返回給呼叫者，並釋放所使用的資源（例如 register 和 stack 空間）。
2. RISC-V 的函數調用約定：
   • 在調用函數時，必須遵循 RISC-V 的調用約定。這些約定確保不同的函數可以協同工作，且呼叫者與被調用者之間的數據傳遞能夠順利進行。
   • 參數傳遞和返回值：
     • 使用 register a0-a7 來傳遞參數，最多可以傳遞 8 個參數。如果需要傳遞更多參數，會使用 stack 來傳遞。
     • 函數的返回值會存放在 a0 和 a1 中。
   • **ra register **：會保存返回地址，這樣函數執行完畢後可以回到呼叫程序的下一條指令繼續執行。

二、Instruction Support for Functions

1. 基本的指令支持：

   • RISC-V 使用 jal（Jump And Link）指令來跳轉並同時保存下一條指令的地址到 ra，這是一個關鍵的指令，能夠實現程序流程的控制。jal 會將當前 PC（程式計數器）的值加上 4，並將其保存到 ra，然後跳轉到指定的目標地址。
   • 當函數執行完畢後，使用 jr ra 指令跳回到返回地址，繼續執行呼叫程序中的下一條指令。

2. 為什麼要使用 jr 而不是 j：

   • 使用 jr ra 的原因是因為一個函數可能會從多個不同的地方被呼叫。如果使用固定的跳轉指令 j，那麼函數只能返回到一個固定的位置。jr 指令允許從 ra register 中讀取返回地址，確保函數可以正確返回到呼叫的源位置。

3. 例子：使用 jal 和 jr：

   jal ra, function_label  # 跳轉到 function_label 並將返回地址存入 ra
   ...
   function_label:
     # 函數的邏輯在此處
     jr ra  # 從 ra 中讀取返回地址並返回
   

三、Stack 和 register 管理

1. stack 的使用：

   • 在 RISC-V 中，stack 是用來存儲數據的 LIFO 結構，當函數呼叫其他函數時，會需要使用 stack 來保存當前的狀態，包括 register 的內容、局部變數以及返回地址。
   • 通常，sp（stack pointer）register 會指向當前 stack 的頂部。當需要存儲數據到 stack 中時，sp 會遞減，為數據騰出空間；當數據被取回時，sp 會遞增，釋放空間。

2. 例子：使用 stack 保存和恢復數據：

   • 當呼叫函數時，呼叫者可能需要保存一些寄存器的值，以免被覆蓋。

   addi sp, sp, -8   # 為 stack 分配 8 字節空間
   sw ra, 0(sp)      # 保存 ra 到 stack 頂
   sw s0, 4(sp)      # 保存 s0 到 stack 頂下一個位置
   ...
   lw ra, 0(sp)      # 從 stack 中恢復 ra
   lw s0, 4(sp)      # 從 stack 中恢復 s0
   addi sp, sp, 8    # 釋放 stack 空間
   jr ra             # 返回到呼叫者
   

四、Nested Calls 和 Register Conventions

1. 嵌套函數調用（Nested Calls）：

   • 當一個函數調用另一個函數時，ra 和 sp 的內容可能會被改寫，因此需要將這些重要的寄存器內容保存到 stack 中，以確保函數之間的數據不會互相干擾。
   • 如果一個函數在調用另一個函數之前保存了它的 ra 和其他重要的 register，那麼它必須在函數返回後恢復這些 register。

2. register 分類：

   • 在 RISC-V 的調用規範中，將 register 分為兩類：
     • Saved Registers（保留 register）：這些 register（如 s0-s11）在函數之間應保持不變，調用者期望它們在函數返回後仍然保持原樣。被調用者有責任在使用這些 register 時保存並恢復它們的值。
     • Caller-Saved Registers（非保留 register）：這些 register（如 a0-a7 和 ra）可能會在函數調用過程中被修改，因此呼叫者在調用之前應保存它們的值，如果需要在調用後使用這些值。

五、Leaf Procedures 和 Non-leaf Procedures

1. Leaf Procedures：

   • 葉子程序指的是不調用其他程序的函數。在這種情況下，這類函數不需要保存 ra，因為它們不會跳轉到其他函數，因此返回地址不會被覆蓋。這樣可以簡化 register 的管理。

2. Non-leaf Procedures：

   • 非葉子程序則會調用其他函數。由於每個非葉子程序都會改變 ra 的內容，因此需要將 ra 保存到 stack 中，以確保返回時能夠回到正確的位置。非葉子程序還需要管理 stack，確保每次調用函數時，register 和 stack 的狀態都能夠正確恢復。

3. 例子：葉子程序：

   • 這是一個簡單的葉子程序，它不會調用其他函數，因此不需要保存 ra：

   addi a0, a0, 1    # 將 a0 增加 1
   jr ra             # 返回呼叫者
   

4. 例子：非葉子程序：

   • 這是一個非葉子程序，它會調用其他函數，因此需要保存 ra 和 s0：

   addi sp, sp, -8   # 為 stack 分配 8 字節空間
   sw ra, 0(sp)      # 保存 ra 到 stack
   sw s0, 4(sp)      # 保存 s0 到 stack
   jal ra, subroutine   # 調用子程序
   lw ra, 0(sp)      # 恢復 ra
   lw s0, 4(sp)      # 恢復 s0
   addi sp, sp, 8    # 釋放 stack 空間
   jr ra             # 返回呼叫者
   

六、Caller vs Callee Saved Registers

1. Caller-Saved Registers（呼叫者保存的 register）：

   • 呼叫者保存 register 是指呼叫者在調用其他函數之前，負責保存這些 register 的值，因為被調用者可能會覆蓋它們。
   • 這些 register 包括 t0-t6 和 a0-a7，這些 register 通常用於傳遞參數或作為暫時性的數據存儲。

2. Callee-Saved Registers（被調用者保存的 register）：

   • 被調用者保存 register 是指被調用者有責任在使用這些 register 時保存它們的值，並在返回前恢復它們。
   • 這些 register 包括 s0-s11，它們在函數之間應保持不變。

3. 為什麼區分這兩類 register：

   • 這種區分的目的是減少不必要的存儲操作，保留那些在函數調用之間應保持不變的 register 內容。同時，這也提高了效率，因為 register 的保存與恢復操作只在必要時進行。

4. 例子：

   • 在下面的例子中，s0 是被調用者保存的 register，因此被調用者在使用它之前會先保存它的值。

   addi sp, sp, -4   # 為 stack 分配 4 字節空間
   sw s0, 0(sp)      # 保存 s0 到 stack
   # 使用 s0 執行一些操作
   lw s0, 0(sp)      # 從 stack 中恢復 s0
   addi sp, sp, 4    # 釋放 stack 空間
   jr ra             # 返回呼叫者
   

七、Example of Recursive Function

1. 遞歸函數的特點：

   • 遞歸函數會呼叫自己，這意味著每次呼叫時，ra 和其他 register 的值都會發生變化。因此，遞歸函數必須小心管理 stack，以確保每次返回時 register 的內容能夠正確恢復。

2. 例子：計算階乘的遞歸函數：

   • 這是一個用 RISC-V 組合語言寫的遞歸函數，它計算一個整數 n 的階乘：

   factorial:
     addi sp, sp, -8    # 為 stack 分配空間
     sw ra, 0(sp)       # 保存 ra
     sw a0, 4(sp)       # 保存參數 a0
   
     addi t0, a0, -1    # t0 = a0 - 1
     bge t0, zero, recurse   # 如果 a0 >= 1，則跳轉到 recurse
     li a0, 1           # 返回 1（base case）
     addi sp, sp, 8     # 釋放 stack
     jr ra              # 返回
   
   recurse:
     jal ra, factorial  # 遞歸呼叫 factorial
     lw a0, 4(sp)       # 恢復原參數 a0
     mul a0, a0, t0     # 計算 a0 * t0
     lw ra, 0(sp)       # 恢復 ra
     addi sp, sp, 8     # 釋放 stack
     jr ra              # 返回