RISC-V Recursive Factorial Function Debugging

Question

Im trying to create a recursive factorial function in RISCV but having some problems.

Here's what we have so far:

.globl factorial

.data
n: .word 8

.text
main:
    la t0, n
    lw a0, 0(t0)
    jal ra, factorial

    addi a1, a0, 0
    addi a0, x0, 1
    ecall # Print Result

    addi a1, x0, '\n'
    addi a0, x0, 11
    ecall # Print newline

    addi a0, x0, 10
    ecall # Exit
factorial: 
        la t1, n
        beq x0, t1, finish
        addi t0, t1, -1
        mul a0, t0, a0
        j factorial
finish:
        ret
        ecall

We tried adding and changing around the registers to use, but its still not loading the correct values to the correct registers. We're also kinda stuck on how to do this recursively. Would love some help!

TheThirdOne · Accepted Answer · 2021-02-18T10:06:41.687

Your main code looks fine. All of the issues I see are in the factorial function. First, there are four clear issues with your factorial function:

factorial: 
        # This loads the address of n not the value at label n
        # You need to additionally lw t1, 0(t1) to get the value
        la t1, n 
        # t1 is never getting modified so why would this loop ever terminate?
        beq x0, t1, finish
        # You should do these two operations in the opposite order
        # if t1 = 1, a0 would become 0
        addi t0, t1, -1
        mul a0, t0, a0
        j factorial
    finish:
        ret
        # Why ecall here? You have already returned. This is unreachable.
        ecall

However, you can't just fix those and expect it to work. Your current implementation is lacking a plan of how to actually compute the factorial. I assume you were trying to make an implementation like the following:

int factorial_recursive(int n) {
    if (n == 0) {
        return 1;
    }
    int recursive = factorial_recursive(n-1);
    return n * recursive;
}

A direct translation of that C code would need to use the stack to save n and the return address and properly follow calling convention. I am not prepared to write out a complete explanation of that though, so I will explain how to convert the looping version of factorial to get you started in the right direction.

The C code I will implement is RISC-V assembly:

int factorial_loop(int n) {
    int out = 1;
    while (n > 0) {
        out *= n;
        n -= 1;
    }
    return out;
}

For this code, n will start out in a0, but eventually it will need to be moved out so we can return out so we will allocate our registers so the function will look like:

int factorial_loop(int a0) {
    int a1 = 1;
    while (a0 > 0) {
        a1 *= a0;
        a0 -= 1;
    }
    a0 = a1;
    return a0;
}

From here it is pretty easy to do a direct conversion.

factorial_loop:
    li a1, 1          # int a1 = 1;
loop:
    beq a0, x0, finish # while (a0 > 0) {
    mul a1, a1, a0    # a1 *= a0;
    addi a0, a0, -1   # a0 -= 1;
    j loop            # }
finish:
    mv a0, a1         # a0 = a1;
    ret               # return a0;

If you're going to use a loop, you can save an instruction in the loop body by putting the conditional at the bottom. `bne a0, x0, loop` instead of `j loop`. (To get 0! = 1 instead of 0, you'd need a `beq` to skip over the loop, but that beq at the top can be *outside* the loop instead of running every iteration). [Why are loops always compiled into "do...while" style (tail jump)?](https://stackoverflow.com/q/47783926) — Peter Cordes, Feb 18 '21 at 03:53
That is an excellent link to explain why not to write the loop like I did. I wrote it with a jump to be most similar to the provided code (and match C line by line). I should have included a note about the while vs if do-while loop formats, but I think the comment serves that purpose now. — TheThirdOne, Feb 18 '21 at 10:10

RISC-V Recursive Factorial Function Debugging

1 Answers1