RISC-V递归函数调试

Question

我正在尝试将以下 C++ 代码转换为 RISC-V，虽然代码有效，但结果不正确，我无法找出问题所在。

一个用C++写的递归函数

int func(int x)
{
    if(x>20)                             //case1
        return 2*x+func(x/5);
    else if (10<x&&x<=20)                //case2
        return func(x-2)+func(x-3);      
    else if (1<x&&x<=10)                 //case3
        return func(x-1)+func(x-2);
    else if (x==0)                       //case4
        return 1;
    else if(x==1)                        //case5
        return 5;
    else                                 //case6
        return -1;
}

我的部分 RISC-V 代码

main:
    li a7,5            #get input and store in register a0
    ecall
    jal ra,func        #jump to func
    addi a0,a1,0       #move return value of func to a0
    li a7,1            #print integer in a0
    ecall
func:
    addi sp,sp,-8
    sw ra,4(sp)
    sw a0,0(sp)
    blt a0,zero,case6 #otherwise
    beq a0,zero,case4 #x=0
    addi t0,zero,1  #t0=1
    beq a0,t0,case5 #x=1
    addi t0,t0,9    #t0=10
    ble a0,t0,case3 #1<x<=10
    addi t0,t0,10   #t0=20
    ble a0,t0,case2 #10<x<=20
    beq zero,zero,case1 #x>20

在func中，我根据a0（代表x）的值将它们分成了6个case，让它们分支到不同的label。

以其中两个标签为例

case3:
    addi a0,a0,-1          #x-1
    jal ra,func            #func(x-1)
    addi t1,a1,0           #move result of func(x-1) to t1
    lw a0,0(sp)            #load orginal x
    lw ra,4(sp)            #load orginal return address
    addi a0,a0,-2          #x-2
    jal ra,func            #func(x-2)
    addi t2,a1,0           #move result of func(x-2) to t2
    lw a0,0(sp)            #load orginal x
    lw ra,4(sp)            #load orginal return address
    addi sp,sp,8           #pop up the stack
    add a1,t1,t2           #return value a1 = func(x-1)+ func(x-2)
    jalr zero,0(ra)
case4:
    addi a1,zero,1         #return result 1 in a1
    addi sp,sp,8
    jalr zero,0(ra)

执行后，我发现如果输入是0或1或<0，结果是正确的，我想是因为它们是叶子过程，但如果我的输入大于3，结果就不正确，我不知道我的问题出在哪里，我应该在哪里查看以尝试修复错误？

Answer 1

如果您的意图是遵循正确的调用约定，而不是创建您自己的调用约定，则您的寄存器分析已关闭。调用约定定义了参数寄存器、return寄存器、调用保留寄存器和调用破坏寄存器；还有 return 值传递和堆栈处理的一些要求。

下面我做一些笔记如下：

addi a0,a0,-1          #x-1
jal ra,func            #func(x-1)
addi t1,a1,0           #move result of func(x-1) to t1 ******(1)
lw a0,0(sp)            #load orginal x
lw ra,4(sp)            #load orginal return address    ******(2)
addi a0,a0,-2          #x-2
jal ra,func            #func(x-2)
addi t2,a1,0           #move result of func(x-2) to t2 ******(3)
lw a0,0(sp)            #load orginal x                 ******(4)
lw ra,4(sp)            #load orginal return address
addi sp,sp,8           #pop up the stack
add a1,t1,t2           #return value a1 = func(x-1)+ func(x-2) ******(5)
jalr zero,0(ra)

(1) t1 是一个 call-clobbered 寄存器，所以不能保证它在后续调用中存活——因为它恰好是一个递归调用，我们知道谁可能破坏 t1：至少在情况 3 中是 func。这里 t1 可能被调用破坏是仅仅调用任何东西的一个特性——它不一定需要递归被破坏，因为任何被调用者都被允许假定使用 t1 而不保留它（根据调用约定的定义，它将 t1 指定为 call-clobbered）。

在最简单的方法中，从第一次调用 func 得到的值 return 应该存储在堆栈内存中（这将需要在堆栈帧中添加一个字）并在调用之后重新加载第二次调用 func.

在另一种方法中，它可以存储在 sN 寄存器中，但这仍然需要额外的堆栈帧槽，以及添加到序言和结尾的一些保存和恢复。（堆栈内存被指定用于函数调用，而 call-clobbered 寄存器则不然。）如果变量的值被重复使用，sN 寄存器是一个优势，例如，当涉及循环时，但只有一种用法（值的消耗），就像这里的情况一样，一个简单的堆栈槽是合适的。一旦保存（并稍后恢复）sN 寄存器可以用作常规寄存器，因此可以使用其他方法删除可能在循环内找到的堆栈帧加载和存储——这通过将加载和存储放在函数序言和结尾（每次函数调用只执行一次）。

(2) 在这里重新加载 ra 寄存器没有意义，它会立即被你自己的 jal 两条指令破坏。

(3) 没有充分的理由将 a1 移动到另一个寄存器（例如 t2），就像第二次调用 func 的 return 值一样需要（4 条指令之后），该值仍然可以在 a1.

中免费获得

(4) 调用约定不需要恢复 aN 寄存器——调用者应该假设这些寄存器也被调用破坏，并且您的代码正确地不依赖于它们在之后是相同的一个电话。所以，这是不必要的，但无害。

(5) 您选择 return a1 中的值，只要您始终如一 doing/expecting 就可以；但是，需要明确的是，它违反了标准调用约定，即 a0.

中的 return 值

如何调试调用其他函数的函数：

如果事情太糟糕以至于被调用的函数没有 return 到它被调用的地方，那么你必须单步执行，特别要记住 ra 寄存器以及它是如何工作的。

在 return 地址链接在寄存器中完成的机器上（RISC V、MIPS、ARM），在没有保留 return 地址值的情况下完成的嵌套调用本身可能会成功，但是调用者已经丢失了它的 return 地址，而是将 return 到它自己的最后一个调用站点（因为那是被破坏的 ra 所指的地方）而不是它的调用者。

其他时候，堆栈会变得混乱，因此 return 无法正常工作，所以我们要注意 ra 和 sp。一旦调用和 returning 正常工作，您就可以专注于其他 calling-related 问题，然后是算法问题。

假设事情并不太坏，并且您正在调用的函数 returns:

观察你的函数调用：

停在调用指令本身 (jal) 并在跳过之前，记下寄存器中保存您的活动变量的值（例如，在调用之后要使用的变量）调用），验证是否传递了正确的参数（例如 arg 寄存器），并注意 sp 值。在您的情况下，t1 是情况 3 中第二次递归调用之前的实时变量，因此您应该在此处记下该值。
步骤调用的函数。 step-over 的优点是，如果在您的环境中可用，它可以忽略进一步的递归以跨过整个调用。然而，在某些环境中，没有 step-over 调试操作，因此您必须模拟它，这可能意味着在调用后立即设置断点（并执行运行或继续），否则一步，直到它回来。当它返回到正确的调用时，就好像 step-over，sp 应该具有与上面步骤中记录的相同的值。
在 return 验证 return 值时：sp 寄存器具有调用前记录的值，寄存器中的实时变量也是如此。在您的情况下，当输入值足够大以触发递归中的多个案例 3 时，您应该能够观察到 t1 从案例 3 的第二次递归调用 return 改变。

或者，如果您了解调用约定并且可以执行实时变量分析（在哪里定义，在哪里使用，以及是否有中间调用），您可以通过代码审查发现调用约定违规。

RISC-V递归函数调试

RISC-V recursive function debugging

assembly

riscv