如何使用RISC-V对斐波那契递归算法进行优化

因为递归需要的时间很长且重复调用，因此要对其进行优化
如何对以下代码进行优化
优化后仍然是递归算法

a0: parameter, initially n

s0: placeholder for parameter n

s1: fib(n-1)

s2: fib(n-2)

fib部分

fib:
    ##Part 1. Prologue as a callee
    addi  sp,  sp,  -16     #create its stack frame 
    sw    ra,  12(sp)       #save the return address to caller
    sw    s0,  8(sp)        #callee saved registers
    sw    s1,  4(sp)       
    sw    s2,  0(sp) 
    
    ##Part 2. Main body
    mv    s0,  a2            #addi  s0,  a2,  0  (parameter n saved in s0)
    li    t0,  2            #addi  t0,  x0,  2  (t0 = 2)
    blt   s0,  t0, fib_base #if n < 2, do the base case

    addi   a2,  s0, -1        #compute fib(n-1)
    jal   fib               #jal ra, fib
    mv    s1,  a0            #s1 = fib(n-1)

    addi  a2,  s0,  -2      #compute fib(n-2)
    jal   fib               #jal ra, fib
    mv    s2,  a0            #s2 = fib(n-2)

    add   a0,  s1,  s2      #a0 = fib(n-1) + fib(n-2)
    b     fib_ret           #beq  x0, x0, fib_ret
fib_base:
    li    a0,  1

    ##Part 3. Epilogue as a callee
fib_ret:
    lw    ra,  12(sp)        #restore the return address
    lw    s0,  8(sp)        #restore $s0
    lw    s1,  4(sp)        #restore $s1
    lw    s2,  0(sp)        #restore $s2
    addi  sp,  sp,  16      #restore the stack pointer
    jr    ra                #jalr zero, ra, 0

main部分：

main:
    li    a7,  5    #load syscall read_int into a7
    ecall        #make the syscall
    mv    a2,  a0   #move the number read into a2
    jal   fib
    
    li    a7,  1    #load syscall print_int into $a7
    ecall        #make the syscall

    li    a7,  10   #progam exit system call
    ecall

.include "fib.s"

提供一个优化思路，看你是否可以用指令写出
用一个中间缓存，示例代码如下：

int buf[52] = {0};  //中间buf存放中间结果，避免重复计算
int fib(n)
{
    int tmp=0;
    if(buf[n] != 0 ) return buf[n];
    if(n==1 || n==2) return 1;
    tmp = fib(n-1)+fib(n-2);
    buf[n] = tmp;
    return tmp;
}

该回答引用ChatGPT
斐波那契递归算法的效率一般比较低，因为它会有很多重复计算，可以通过记忆化搜索、循环等方式进行优化。在RISC-V中，有一种特殊的指令bgezal，可以实现递归函数的尾递归优化，这样可以减少栈的使用，提高效率。

下面是对斐波那契递归算法进行尾递归优化的示例代码：


fib:
    ##Part 1. Prologue as a callee
    addi  sp, sp, -16  #create its stack frame 
    sw    ra, 12(sp)   #save the return address to caller
    sw    s0, 8(sp)    #callee saved registers
    sw    s1, 4(sp)       
    sw    s2, 0(sp) 
    
    ##Part 2. Main body
    mv    t0, a2       #copy n to t0
    li    t1, 2        #load 2 to t1
    blt   t0, t1, fib_base  #if n < 2, do the base case

fib_loop:
    addi  a2, t0, -1   #compute fib(n-1)
    mv    a0, s1
    mv    s1, s2
    mv    s2, a0
    jal   fib
    add   a0, s1, s2   #a0 = fib(n-1) + fib(n-2)
    bgezal   x0, fib_ret  #tail call optimization

fib_base:
    li    a0, 1

    ##Part 3. Epilogue as a callee
fib_ret:
    lw    ra, 12(sp)   #restore the return address
    lw    s0, 8(sp)    #restore $s0
    lw    s1, 4(sp)    #restore $s1
    lw    s2, 0(sp)    #restore $s2
    addi  sp, sp, 16   #restore the stack pointer
    jr    ra           #jump back to the caller

在这个示例代码中，我们将递归调用改为循环调用，并使用了尾递归优化，这样可以减少栈的使用，提高效率。

下面是调用代码：


main:
    li    a7, 5        #load syscall read_int into a7
    ecall              #make the syscall
    mv    a2, a0       #move the number read into a2
    jal   fib
    
    li    a7, 1        #load syscall print_int into $a7
    ecall              #make the syscall

    li    a7, 10       #program exit system call
    ecall

.include "fib.s"

调用方式与之前没有变化。

你看下这篇博客吧, 应该有用👉 ：RISC-V-中断和异常笔记
除此之外, 这篇博客: C语言编译成RISC-V汇编代码后的执行步骤中的 3.5 C语言与对应的RISC-V汇编语言 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

C语言程序

int g(int x)
{
	return x+3;
}
int f(int x)
{
	return g(x);
}
int main(void)
{
	return f(8)+1;
}

RISC-V汇编语言伪代码

g:
addi x10,x10,3  //x10=x10+3,传入的参数加3
jalr x0,0(x1)   //函数返回

f:
jal x1,g		//调用函数g
jalr x0,0(x1)	//返回

main:
addi sp,sp,-16	//sp增长16位，用来保存x1和x10的旧值
sd x1,8(sp)		//保存x1的值
sd x10,0(sp)	//保存x10的值
addi x10,x0,8	//x10=0+8,将立即数8放入寄存器x10中
jal x1,f		//调用函数f，返回地址存在x1	

addi x10,x10,1  //x10=x10+1,即f(8)+1
ld x10,0(sp)	//恢复x10的值
ld x1,8(sp)		//恢复x1的值
addi sp,sp,16	//恢复栈针