CODEWITHSUNDEEP
recursionassemblystackriscv
Gurvinder Singh
Gurvinder Singh

Reputation: 111

Recursive program in RISC-V assembly

I am trying to create a recursive program in RISC-V but I can't get it to get me the right result. It looks like it is calling itself only two times max, but I tried running it on paper and everything seems correct: 

addi x31, x0, 4
addi x30, x0, 2

addi x2, x0, 1600               //initialize the stack to 1600, x2= stackpointer
ecall x5, x0, 5                 //read the input to x5
jal x1, rec_func
ecall x0, x10, 2                //print the result
beq x0, x0, end

rec_func:
addi x2, x2, -16               //make room in stack
sd x1, 0(x2)                   //store pointer and result in stack
sd x10, 8(x2)
bge x5, x31, true             // if i > 3, then go to true branch
addi x10, x0, 1              // if i <= 3, then return 1
addi x2, x2, 16              // reset stack point
jalr x0, 0(x1)

true:
addi x5, x5, -2                // compute i-2
jal x1, rec_func                // call recursive func for i-2
ld x1, 0(x2)                    // load the return address
ld x10, 8(x2)                  // load result from last function call
addi x2, x2, 16                // reset stack point
mul x10, x10, x30               // multiply by 2
addi x10, x10, 1               // add 1
jalr x0, 0(x1)                 // return

end:

This is the original program logic:

if i<= 3 return 1
else return 2 * rec_func(i-2) +1

Upvotes: 2

Views: 12169

Answers (2)

Gurvinder Singh
Gurvinder Singh

Reputation: 111

I got it working now. The changes that I made were following:

  • In the part where I was returning 1, I wasn't loading the stack pointer of the return call
  • I removed the storing of x10 into the memory as @Michael pointed it out that I was returning it and I didn't need it.

The final code looks like this:

addi x31, x0, 4
addi x30, x0, 2

addi x2, x0, 1600               // initialize the stack to 1600, x2= stackpointer
ecall x5, x0, 5                 // read the input to x5
jal x1, rec_func
ecall x0, x10, 2                // print the result
beq x0, x0, end

rec_func:
    addi x2, x2, -8                 // make room in stack
    sd x1, 0(x2)                    // store pointer and result in stack
    bge x5, x31, true               // if i > 3, then go to true branch
    ld x1, 0(x2)
    addi x10, x0, 1                 // if i <= 3, then return 1
    addi x2, x2, 8                  // reset stack point
    jalr x0, 0(x1)

true:
    addi x5, x5, -2                 // compute i-2
    jal x1, rec_func                // call recursive func for i-2
    ld x1, 0(x2)                    // load the return address
    addi x2, x2, 8                  // reset stack point
    mul x10, x10, x30               // multiply by 2
    addi x10, x10, 1                // add 1
    jalr x0, 0(x1)                  // return

end:

Upvotes: 0

muodostus
muodostus

Reputation: 151

I don't have enough reputation to add a comment but have you tried running this with a debugger (GDB ?) instead of on paper? That should show what's actually in the registers and why it's not branching as you might expect. I'm not familiar enough with these instructions (learning x86 assembly) to figure the source out at the moment.

Upvotes: 1

Related Questions