I am trying to convert below C Code to RISC-V, although the code worked, but the result is not correct, and I cannot figure out the problem.

A recursive function writing in 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;
}

Part of my RISC-V Code

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

In func, I seperate them into six cases according to the value of a0 (represent x) , let them branch to different label.

Take two of the labels as an example

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)

After excuting, I find if input is 0 or 1 or <0, and the result is correct, I think is because they are leaf procedure, but if my input is larger than 3, the result is not correct, I don't where my problem is, Where should I look into to try and fix the error?

CodePudding user response：

If your intent is to follow the proper calling convention, rather than create your own, your register analysis is off.  The calling convention defines parameter registers, return registers, call preserved registers, and call clobbered registers; also return value passing and some requirements on stack handling.

In the following I make some notes below:

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 is a call-clobbered register, so it is not guaranteed to survive the subsequent call — as it happens to be a recursive call, we know who potentially clobbers t1: it is func in at least case 3.  Here t1 potentially clobbered by a call is a feature of mere calling anything — it does not necessarily require recursion to be clobbered as any callee is allowed to assume use of t1 without preserving it (by definition of the calling convention, which designates t1 as call-clobbered).

In the simplest approach, the value returned from the first call to func should be stored in stack memory (which will require an additional word in the stack frame) and reloaded after the 2nd call to func.

In an alternate approach it can be stored in an sN register, but that will still require an additional stack frame slot, plus some save & restore added to prologue and epilogue.  (Stack memory is designated to survive function calls, whereas the call-clobbered registers aren't.)  The sN register are an advantage if the variable's value is used repeatedly, such as is the case, for example, when there are loops involved, but for only one usage(consumption of the value) as is the case here, a simple stack slot is appropriate.  Once preserved (and later restored) sN registers can be used as regular registers, so can remove stack frame loads & stores that might be found inside the loops using the other approach — this works by putting a load & a store in function prologue and epilogue (which are done only once per function's invocation).

(2) There's no point to reloading the ra register here, it will immediately be clobbered by your own jal two instructions later.

(3) There's no good reason to move a1 to another register (e.g. t2), as when the return value from the 2nd call to func is needed (4 instructions later), that value is still freely available in a1.

(4) The calling convention does not require restoration of the aN registers — the caller is supposed to assume these registers are also call clobbered, and your code rightly does not rely on them being the same after a call.  So, this is unnecessary, but harmless.

(5) You're choosing to return values in a1, which is fine as long as you're consistently doing/expecting that; however, to be clear it is contrary to the standard calling convention, which would return values in a0.

How do you debug functions that call other functions:

If things are so broken that the a called function doesn't return to where it was called, then you have to single step, keeping in mind, in particular, the ra register and how that is working.

On a machine where the return address linkage is done in a register (RISC V, MIPS, ARM), a nested call done without having preserved the return address value may itself succeed, but the caller has lost its return address and instead will return to its own last call site (as that's where the clobbered ra refers) rather to its caller.

Other times, the stack gets messed up so returning properly won't work, so we pay attention to ra and to sp.  Once the calling and returning is working you can focus on other calling-related issues, and then algorithmic issues.

Assuming things aren't too broken and the function you're calling returns:

Watch your function calls:

1. Stop at the call instruction itself (jal) and before stepping over, make note of the values in the registers holding your live variables (e.g. ones that are to be used after the call), verify the proper parameters are being passed (e.g. the arg registers), and also note the sp value.  In your case t1 is a live variable before the 2nd recursive call in case 3, so you should here make a note of that value.

2. Step over the function that is being called.  The advantage of step-over, if available in your environment is that it can ignore further recursion to step over the entire call.  In some environments, however, there is no step-over debugging operation, so you have to simulate it, and that might mean setting a break point immediately after the call (and doing run or continue), or else single step until it comes back.  When it is back to the proper invocation as if step-over, the sp should have the same value noted in the step just above.

3. Upon return verify the return value: that the sp register has the value noted before the call, and same for your live variables in registers.  In your case, you should be able to observe that t1 is altered upon return from the 2nd recursive call of case 3 when the input value is large enough to trigger more than one case 3 in recursion.

Alternately, if you are knowledgeable of the calling convention and can perform live variable analysis (where defined, where used, and if there is an intervening call or not) you can find calling convention violations by code review.