当前位置：首页 > article >正文

深入解析 RISC-V 递归函数的栈使用：以阶乘函数为例

article 2024/10/5 20:19:33

在处理递归函数时，RISC-V 体系架构的寄存器数量有限。为了确保每次递归调用能正确保存和恢复寄存器的状态，栈（stack）提供了灵活的解决方案。本文将结合具体的汇编代码和递归的阶乘函数 fact 来讲解 RISC-V 中如何利用栈进行寄存器管理。

阶乘函数 C 代码

首先，来看一个计算阶乘的简单递归函数：

int fact(int n) {
    if (n < 1) return 1;
    else return n * fact(n - 1);
}

这个函数 fact 计算整数 n 的阶乘。如果 n 小于 1，它返回 1，否则递归调用自身来计算 n-1 的阶乘，并将结果乘以 n。

在函数调用过程中，寄存器会用于存储参数和返回地址等信息。由于递归调用会不断嵌套，RISC-V 的寄存器可能不足以保存所有信息。因此，栈在这种情况下非常有用。

对应的 RISC-V 汇编代码

以下是 fact 函数对应的 RISC-V 汇编代码，解释了如何利用栈来管理递归调用时的寄存器状态：

fact:
    addi sp, sp, -8         # 栈指针向下移动 8 字节，为 x1（返回地址）和 x10（参数 n）分配空间
    sw x1, 4(sp)            # 将返回地址 x1 保存到栈中
    sw x10, 0(sp)           # 将参数 n（x10）保存到栈中
    
    addi x5, x10, -1        # 计算 n - 1，结果存入 x5
    bge x5, x0, L1          # 如果 n - 1 >= 0，则跳转到 L1（递归调用）
    
    addi x10, x0, 1         # 如果 n < 1，将 x10 设为 1（返回值 1）
    addi sp, sp, 8          # 恢复栈指针
    jalr x0, 0(x1)          # 返回到调用者
    
L1:
    addi x10, x10, -1       # 减少 n 的值
    jal x1, fact            # 递归调用 fact(n - 1)

    addi x6, x10, 0         # 将递归调用的结果存入 x6
    lw x10, 0(sp)           # 从栈中恢复参数 n
    lw x1, 4(sp)            # 从栈中恢复返回地址
    addi sp, sp, 8          # 恢复栈指针
    
    mul x10, x10, x6        # 计算 n * fact(n - 1)
    
    jalr x0, 0(x1)          # 返回到调用者

详细解析

栈的初始化：
- addi sp, sp, -8：栈指针 sp 向下移动 8 字节，分配空间保存两个寄存器（返回地址 x1 和参数 x10）。
- sw x1, 4(sp) 和 sw x10, 0(sp)：将返回地址 x1 和参数 x10（即参数 n）保存到栈中，避免在后续递归调用中丢失它们。
递归基（Base Case）处理：
- addi x5, x10, -1：计算 n - 1 并存入寄存器 x5。
- bge x5, x0, L1：检查 n-1 是否大于或等于 0。如果是，说明 n >= 1，跳转到 L1，继续递归。否则，函数返回 1（递归基）。
- addi x10, x0, 1：如果 n < 1，直接返回 1。
- jalr x0, 0(x1)：从函数中返回，恢复调用者的状态。
递归调用：
- 在 L1 标签处，函数递归调用 fact(n - 1)：
  - addi x10, x10, -1：将 n 减 1。
  - jal x1, fact：跳转到 fact 函数，递归调用。
恢复状态与计算：
- addi x6, x10, 0：将递归调用 fact(n - 1) 的返回值存入 x6。
- lw x10, 0(sp) 和 lw x1, 4(sp)：从栈中恢复之前保存的参数 n 和返回地址 x1。
- mul x10, x10, x6：计算 n * fact(n - 1)，将结果存入 x10。
返回调用者：
- jalr x0, 0(x1)：返回到调用函数。