Procedures, the stack and calling conventions

Procedures, also called functions, subroutines or methods, are the main tool for structuring programs: they hide details behind a name, let code be reused, and make recursion possible. In a high-level language a call looks effortless, but at the machine level several things must happen. The caller must put the arguments where the callee can find them, transfer control while remembering where to come back to, and keep its own values safe; the callee must find space for its local variables, do its work, leave the result where the caller expects it and return. This lesson shows how RISC-V does all of this with two jump instructions, the stack and the calling convention introduced in lesson 5. CMPUT-201 lesson 4 described the stack from the C programmer's side; here you will build and inspect stack frames yourself.

Calling and returning

RISC-V has no dedicated call or return instruction. A call is jal ra, label (usually written with the pseudo-instruction call label, or jal label), which jumps to the label and saves the address of the following instruction, the return address, in register ra. A return is jalr x0, 0(ra) (written ret), which jumps to the address in ra and saves nothing. Because jal stores its return address in a register rather than in memory, a leaf procedure, one that calls no other procedure, needs no memory traffic at all for the call. x86-64 does it differently: its call instruction pushes the return address onto the stack in memory and its ret instruction pops it.

Arguments go in a0 to a7, in order, and the result comes back in a0, with a1 used as well when the result needs 64 bits. A procedure with more than eight integer arguments receives the rest on the stack. Here is a leaf procedure that returns the sum of the squares of its two arguments, called twice from main.

    .data
nl:     .asciz "\n"
    .text
    .globl main
main:
    li   a0, 3
    li   a1, 4
    call sumsq          # a0 = sumsq(3, 4)
    li   a7, 1
    ecall               # prints 25
    la   a0, nl
    li   a7, 4
    ecall
    li   a0, -5
    li   a1, 12
    call sumsq          # a0 = sumsq(-5, 12)
    li   a7, 1
    ecall               # prints 169
    li   a7, 10
    ecall

# int sumsq(int x, int y): a leaf procedure, so it needs no stack frame
sumsq:
    mul  t0, a0, a0     # t0 = x * x  (t registers may be used freely)
    mul  t1, a1, a1     # t1 = y * y
    add  a0, t0, t1     # return value in a0
    ret

25
169

sumsq overwrote t0 and t1 without saving them. That is allowed: under the calling convention, t registers and a registers are caller-saved, meaning a caller that needs their values after a call must save them itself. The s registers and sp are callee-saved: a procedure that changes them must restore them before returning. The convention balances the two costs. Leaf procedures, which are the majority of calls in most programs, can usually do all their work in t and a registers and never touch memory; procedures that need values to survive across their own calls use s registers and pay the cost of saving them once, at entry and exit.

The stack

When a procedure does need memory of its own, to save registers or to hold local arrays and variables that do not fit in registers, it uses the stack. The stack is a region at the top of memory that grows downward, and sp always points to the lowest address in use, the top of the stack. A procedure allocates space by subtracting from sp and frees it by adding the same amount back. The block of stack a procedure allocates is its stack frame or activation record. The RISC-V ABI requires sp to stay a multiple of 16 bytes at procedure boundaries, so frames are rounded up to multiples of 16 even when they need less.

A non-leaf procedure must save ra before making its own calls, because each call overwrites ra. The code that sets up a frame at the start of a procedure is its prologue, and the code that dismantles it before returning is its epilogue. A typical prologue subtracts the frame size from sp and stores ra and any s registers the procedure will use; the epilogue reloads them in reverse and adds the frame size back. Some compilers also keep a frame pointer, s0 (also called fp), pointing to the top of the frame, which makes it easier for debuggers to walk the chain of frames; optimizing compilers usually omit it to free another register.

Nested calls

The program below has main call total, which loops over an array and calls a helper, clamp, on every element. total is not a leaf, so it saves ra. It also keeps its loop pointer, end address and running sum in s registers, because the calls to clamp may overwrite any t or a register, so it must save and restore those s registers for its own caller.

    .data
data:   .word 12, -7, 250, 40, 99, 300, -1
msg:    .asciz "clamped total = "
    .text
    .globl main
main:
    la   a0, data
    li   a1, 7
    call total
    mv   s0, a0
    la   a0, msg
    li   a7, 4
    ecall
    mv   a0, s0
    li   a7, 1
    ecall
    li   a7, 10
    ecall

# int clamp(int x): limit x to the range 0..255 (a leaf)
clamp:
    bge  a0, zero, 1f
    li   a0, 0
    ret
1:  li   t0, 255
    ble  a0, t0, 2f
    mv   a0, t0
2:  ret

# int total(int *a, int n): sum of clamp(a[i])
total:
    addi sp, sp, -16        # prologue
    sw   ra, 12(sp)
    sw   s0, 8(sp)
    sw   s1, 4(sp)
    sw   s2, 0(sp)
    mv   s0, a0             # s0 = pointer to the current element
    slli a1, a1, 2
    add  s1, a0, a1         # s1 = end address
    li   s2, 0              # s2 = sum
loop:
    beq  s0, s1, done
    lw   a0, 0(s0)
    call clamp              # may change t and a registers, not s registers
    add  s2, s2, a0
    addi s0, s0, 4
    j    loop
done:
    mv   a0, s2
    lw   s2, 0(sp)          # epilogue
    lw   s1, 4(sp)
    lw   s0, 8(sp)
    lw   ra, 12(sp)
    addi sp, sp, 16
    ret

clamped total = 656
deepest stack use: 16 bytes

The labels 1f and 2f are numeric local labels: 1f means the next label 1 forward, and 1b would mean the previous one backward. They avoid inventing names for tiny branches. The stack report shows that the deepest the stack ever went was total's 16-byte frame; clamp, as a leaf, used none. Check the sum yourself: 12 + 0 + 250 + 40 + 99 + 255 + 0 = 656.

If total had forgotten to save ra, its first call to clamp would have overwritten ra with an address inside total's own loop, and total's final ret would have jumped back into the loop instead of returning to main, an infinite loop or a crash depending on the code. Forgetting to restore an s register is subtler: the caller's value is silently corrupted, and the symptom appears later, far from the cause. Both are among the most common bugs in hand-written assembly, and the calling convention exists to make them avoidable.

Recursion

Recursion needs nothing new: a recursive procedure is simply a non-leaf procedure that happens to call itself, and each activation gets its own stack frame holding its own saved registers. The classic example is factorial. Because n is still needed after the recursive call returns, it must be kept in a saved register or on the stack.

    .data
sp1:    .asciz "! = "
nl:     .asciz "\n"
    .text
    .globl main
main:
    li   s0, 1
mloop:
    li   t0, 8
    bgt  s0, t0, mdone
    mv   a0, s0
    li   a7, 1
    ecall
    la   a0, sp1
    li   a7, 4
    ecall
    mv   a0, s0
    call fact
    li   a7, 1
    ecall
    la   a0, nl
    li   a7, 4
    ecall
    addi s0, s0, 1
    j    mloop
mdone:
    li   a7, 10
    ecall

# int fact(int n): n! by recursion
fact:
    li   t0, 1
    bgt  a0, t0, recurse
    li   a0, 1              # base case: fact(0) = fact(1) = 1
    ret
recurse:
    addi sp, sp, -16
    sw   ra, 12(sp)
    sw   s0, 8(sp)
    mv   s0, a0             # keep n across the call
    addi a0, a0, -1
    call fact               # a0 = fact(n - 1)
    mul  a0, a0, s0         # n * fact(n - 1)
    lw   s0, 8(sp)
    lw   ra, 12(sp)
    addi sp, sp, 16
    ret

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
deepest stack use: 112 bytes

Computing 8! needs seven nested activations of the recursive case, each with a 16-byte frame, which is exactly what the stack report shows: 7 × 16 = 112 bytes. Deep recursion multiplies this cost, and every system has a limit on stack size, 8 MiB by default for a Linux process's main thread. Exceed it and the program crashes with a stack overflow. Recursion that is natural for a tree a few dozen levels deep is dangerous for a linked list a million nodes long.

void print_int(int);
void print_str(const char *);

static int calls;

int fib(int n) {
    calls++;
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

int cmain(void) {
    for (int n = 5; n <= 20; n += 5) {
        calls = 0;
        int f = fib(n);
        print_str("fib("); print_int(n); print_str(") = "); print_int(f);
        print_str(" using "); print_int(calls); print_str(" calls\n");
    }
    return 0;
}

fib(5) = 5 using 15 calls
fib(10) = 55 using 177 calls
fib(15) = 610 using 1973 calls
fib(20) = 6765 using 21891 calls
instructions executed: 373094
  ALU 144423, loads 84219, stores 84219, branches 24060 (12033 taken), jumps 36144, system 29
deepest stack use: 688 bytes

This program was written in C, compiled with clang for RV32IM, linked with a tiny runtime that provides print_int and print_str through ecall, and run on the same simulator. The number of calls grows exponentially, as CMPUT-204 discussed, and the instruction count follows it. The stack, in contrast, never gets deeper than the longest chain of active calls, about n frames, so recursion depth and recursion cost are different things.

Tail calls

When the last thing a procedure does is call another procedure and return its result, the call is a tail call. The caller's frame is no longer needed at that point, so the compiler can tear it down first and jump to the callee with a plain j, reusing the caller's return address: the callee returns directly to the original caller. A tail-recursive procedure compiled this way becomes a loop and uses constant stack space. Clang does this at -O1 and above for RISC-V; the Euclidean algorithm below is written recursively, but the generated code contains a backward branch and no call at all.

unsigned gcd(unsigned a, unsigned b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);     /* a tail call */
}

$ clang --target=riscv32 -march=rv32im -O1 -S gcd.c -o -
gcd:
    beqz    a1, .LBB0_2
.LBB0_1:
    remu    a2, a0, a1
    mv      a0, a1
    mv      a1, a2
    bnez    a1, .LBB0_1
.LBB0_2:
    ret

By contrast, at -O0 the same compiler keeps every variable in the stack frame and emits a real recursive call, which makes debugging easier because every variable has a memory address the debugger can show. That is the main reason unoptimized code is so much slower: most of its instructions are loads and stores to the stack.

int add3(int a, int b, int c) {
    return a + b + c;
}

$ clang --target=riscv32 -march=rv32im -O0 -S add3.c -o -
add3:
    addi    sp, sp, -32
    sw      ra, 28(sp)
    sw      s0, 24(sp)
    addi    s0, sp, 32
    sw      a0, -12(s0)
    sw      a1, -16(s0)
    sw      a2, -20(s0)
    lw      a0, -12(s0)
    lw      a1, -16(s0)
    add     a0, a0, a1
    lw      a1, -20(s0)
    add     a0, a0, a1
    lw      ra, 28(sp)
    lw      s0, 24(sp)
    addi    sp, sp, 32
    ret

Stack frames and security

Because the saved return address sits in the stack frame right next to local arrays, a program that writes past the end of a local array can overwrite it. When the procedure returns, it jumps wherever the corrupted value points. This stack buffer overflow was for decades the most common way to take over programs, beginning with the Morris worm of 1988. Modern systems defend in layers: compilers insert a secret canary value between locals and the saved registers and check it before returning; the operating system marks the stack as non-executable and randomizes its address; and newer hardware adds shadow stacks that keep a protected second copy of return addresses, which x86-64 processors and the RISC-V Zicfiss extension both provide. CMPUT-331 covers these attacks and defenses in detail; the point here is that they follow directly from the frame layout in this lesson.