Recursive Procedure Calls

1Learning Outcomes¶

Identify the prologue and epilogue of a procedure.
Practice procedure calls, using recursive procedures as an example.
Identify use cases for unconditional jump instructions and pseudoinstructions–in particular, know how to jump to procedures and return from procedures.

We recommend pulling up the register convention section of the RISC-V Green Card. We also recommend referencing the Fundamental Steps (revisited version) of procedure calls.

2Recursive Example: `factorial`¶

Consider the below assembly implementation of factorial. We have omitted some lines for simplicity; see the full code at the end of this section.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
main:
  li a0 3
  jal ra factorial
  …
factorial:
  addi sp sp -8
  sw ra 0(sp)
  sw s0 4(sp)
  mv s0 a0
  li t0 1
  bne s0 t0 recurse
  li a0 1
  j epilogue
recurse:
  addi a0 s0 -1
  jal ra factorial
  mul a0 s0 a0
epilogue:
  lw ra 0(sp)
  lw s0 4(sp)
  addi sp sp 8
  jr ra

Show Answer

Start with the epilogue, which is labeled (the label epilogue on line 18 is tied to the lw instruction on line 19). Instructions on lines 19, 20, and 21 load values back into saved register s0 and return address ra. and increment the stack pointer sp. Finally, line 22 jr ra returns to the caller function.

If the epilogue is “tear down,” the prologue is “set up.” We can see that instructions on lines 6, 7, and 8 decrement the stack pointer sp and store callee-saved* registers s0 and ra on the stack, which are used in the procedure itself.

2.1Discussion Questions¶

Hover here for the RISC-V assembly.

Show Answer

8B
Our own ra, because we (may) do a recursive function call. Our caller’s s0

Show answer

Recursive factorial (for positive numbers) computes $\text{factorial}(n) = n! = n \cdot (n - 1)!$ , for $n > 1$ . $\text{factorial}(1) = 1! = 1.$

The calling convention means saved registers like s0 are preserved across the recursive call, so copy argument a0 ( $n$ ) to saved register s0 so we can still use this value after the recursive call $(n-1)!$ completes.

Show answer

The branch instruction bne compare two registers. This instruction checks for our base case, which (as per Line 10) is 1. We therefore load the immediate 1 into register t0.^[1] ^[2]

Show Answer

First restore registers, whose values are stored on the stack. Then, pop the stack frame, right before returning to the caller.

Show Answer

When returning, the callee is always responsible for preserving calling convention: restoring saved registers and deallocating the stack frame (e.g., restoring sp). While Lines 12 and 13 imply the callee has reached the base case, the base case must also complete the epilogue before returning to the caller.

2.2Run Demo¶

The below code is for reference.

Expand for recursive.s

#### Recursive factorial
.globl factorial

.text
main:
    li a0 4
    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 takes one argument:
# a0 contains the number which we want to compute the factorial of
# The return value should be stored in a0

factorial:
    # Prologue
    addi sp sp -8
    sw ra 0(sp)
    sw s0 4(sp)
    
    # Body
    mv s0 a0
    li t0 1
    
    bne s0 t0 recurse
    
    # Base Case
    li a0 1
    j epilogue
    
recurse:
    addi a0 s0 -1
    jal ra factorial
    mul a0 s0 a0

epilogue:
    lw ra 0(sp)
    lw s0 4(sp)
    addi sp sp 8
    jr ra

Expand for suggested Venus simulator settings

In main:
- jal ra, factorial (e.g., factorial(4) function call)
- update li a0 3 to simulate factorial(3)
Set breakpoints in factorial:
- the start of the procedure, i.e., factorial label
- Base case
- recursive call

Check register values a0 and s0; suggest switching to Decimal view of register values

3Another Recursive Example¶

Check it out!

1
2
3
4
5
6
7
8
int foo(int i) {
  if (i == 0) return 0;
  int a = i + foo(i-1);
  return a;
}
int j = foo(3);
int k = foo(100);
int m = j+k;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
  j main
foo:          # int foo(int i)
  addi sp sp -8 # Prologue
  sw ra 0(sp)   # Prologue
  sw s0 4(sp)   # Prologue
  mv s0 a0      # Move i
  bne s0 x0 Next# if i != 0, skip this
  li a0 0       # int a = 0;
  j Epilogue    # Go to Epilogue
              # (to restore stack)
Next: 
  addi a0 s0 -1 # int j = i - 1;
  jal ra foo    # j = foo(j);
  add a0 s0 a0  # int a = i + j;
Epilogue: 
  lw ra 0(sp)   # Epilogue
  lw s0 4(sp)   # Epilogue
  addi sp sp 8  # Epilogue
  jr ra         # return a;
main:
  li a0 3       # int j = foo(3);
  jal ra foo    # call foo
  mv s0 a0      # mv rd rs1 sets rd = rs1
  li a0 100     # int k = foo(100);
  jal ra foo    # call foo
  mv s1 a0      # Saves return value in s1
  add a0 s0 s1  # int m = j+k;

Footnotes¶

Given the mv s0 a0 instruction, we could have equivalently replaced the branch instruction bne s0 t0 recurse with bne a0 t0 recurse. The code likely uses the former to distinguish register naming conventions for register a0, which is both the first function argument and the return value. The register s0 is designated as the value of $n$ in $\text{factorial}(n)$ , and the register a0 will soon become the return value (as per line 12).
↩
Factorially is mathematically defined over all non-negative numbers, including $0!= 1$ . The lecture code pedagogically chooses to ignore the zero case to show you bne with two non-zero register values.
↩

1Learning Outcomes¶

2Recursive Example: factorial¶

2.1Discussion Questions¶

2.2Run Demo¶

3Another Recursive Example¶

2Recursive Example: `factorial`¶