L11 [Stack Subroutines]

Let's say we want to write a recursive fact function

int fact(int n) {
    int answer;

    if(n <= 0) answer = 1;
    else answer = n * fact(n - 1);

    return answer;
}

Initial Part

Building the stack frame is always the same

FACT    ADD R6, R6, -4      ; Allocate Space
        STR R7, R6, 2       ; Save Ret Addr
        STR R5, R6, 1       ; Save Old FP
        ADD R5, R6, 0       ; Copy SP to FP
        ADD R6, R6, -5      ; Room for 5 registers

        ;; Save the registers
        STR R0, R5, -1
        STR R1, R5, -2
        STR R2, R5, -3
        STR R3, R5, -4
        STR R4, R5, -5

Let's write the teardown first and then go into the middle and write the code for factorial

The Ending

Let's use R0 as the scratch register first. So, where does answer live? R5 + 0.

Where does the return value live? R5 + 3

LDR R0, R5, 0   ; Return value = answer
STR R0, R5, 3   ; Return Addr is R5 + 3
LDR R4, R5, -5  ; restore R4
LDR R3, R5, -4  ; restore R3
LDR R2, R5, -3  ; restore R2
LDR R1, R5, -2  ; restore R1
LDR R0, R5, -1  ; restore R0
ADD R6, R5, 0   ; Restore SP
LDR R5, R6, 1   ; Restore FP
LDR R7, R6, 2   ; Restore Return Address
ADD R6, R6, 3   ; Pop ra, fp, 1v1
RET

The Code In-Between Stack Buildup and Teardown

Where does the first parameter live? R5 + 4

; if (n <= 0) {
LDR R0, R5, 4   ; Load n into R0
BRP IFELSE1     ; Branch on failure

; answer = 1
AND R0, R0, 0
ADD R0, R0, 1
STR R0, R5, 0

; } else {
BR ENDIF1

; answer = n * fact(n - 1);
; rewrite: R0 = fact(n - 1); answer = mult(n, R0)

IFELSE1     LDR R0, R5, 4   ; Push n - 1
            ADD R0, R0, -1

            ;; Starting a new stack frame
            ADD R6, R6, -1
            STR R0, R6, 0

            JSR FACT        ; fact(n - 1)
            LDR R0, R6, 0   ; R0 = return value
            ADD R6, R6, 2   ; Pop return value and arg1
                            ; Note that the stack frame is now gone

            ;; answer = mult(n, R0)
            ADD R6, R6, -1  ; Push R0
            STR R0, R6, 0
            ADD R6, R6, -1  ; Push n
            LDR R0, R5, 4
            STR R0, R6, 0

            JSR MULT        ; mult(n, R0)
            LDR R0, R6, 0   ; answer = return value
            STR R0, R5, 0
            ADD R6, R6, 3   ; Pop return value and arg1-2

To call a subroutine, just push the argument in reverse order

Equality of stack buildup and teardown