Subroutines and the stack

The stack

Principle

The stack is an area of memory where values are stored temporarily: you push them, then pop them in reverse order, like a stack of plates. Register A7, also called SP (stack pointer), holds the address of the top of the stack.

On the 68000, the stack grows downwards: pushing makes SP move back. We use the modes of chapter 3:

A golden rule

Everything that is pushed must be popped, in reverse order, before leaving the piece of program that pushed it. An unbalanced stack means a program that crashes further on, far from the mistake.

Subroutines

Calling and returning

A subroutine is a piece of code called from several places, like a function.

• BSR ETIQ (branch to subroutine) pushes the return address (the address of the instruction following the BSR, a long word), then jumps to ETIQ. JSR does the same with any addressing mode.
• RTS (return from subroutine) pops a long word into PC: execution resumes just after the BSR.

That is why the golden rule matters: if the subroutine leaves something on the stack, RTS pops that value instead of the return address, and the program jumps anywhere.

Preserving registers

A subroutine uses registers; so does the caller. Convention: a subroutine leaves intact the registers it does not use to return a result. It saves them on entry and restores them on exit. MOVEM (move multiple) does it in one instruction:

SOUSPROG MOVEM.L D1-D3/A0,-(SP)  ; save D1, D2, D3 and A0
         ...                     ; the work
         MOVEM.L (SP)+,D1-D3/A0  ; restore them
         RTS

Passing parameters

In registers. The simplest way: the caller puts the parameters in agreed registers, and the result comes back in another one. This must be written at the top of the subroutine.

* STRLEN: length of a string terminated by 0
* input: A0 = address of the string
* output: D0.L = length; the other registers are preserved
STRLEN  MOVE.L  A0,-(SP)    ; A0 is going to move: save it
        MOVEQ   #0,D0
BCL     TST.B   (A0)+
        BEQ     FIN
        ADDQ.L  #1,D0
        BRA     BCL
FIN     MOVE.L  (SP)+,A0    ; restore it
        RTS

Call:

        LEA     MESSAGE,A0
        BSR     STRLEN      ; D0 <- length of MESSAGE

On the stack. When there are many parameters, or to write like a compiler, the caller pushes them before the BSR. In the subroutine, they are below the return address: the last one pushed is at 4(SP), the previous one at 6(SP) (for words). On return, the caller removes them by advancing SP.

* call: SOMME(3, 4)
        MOVE.W  #3,-(SP)    ; first parameter
        MOVE.W  #4,-(SP)    ; second parameter
        BSR     SOMMEP
        ADDQ.L  #4,SP       ; remove the two parameters
        ...                 ; D0.W is 7

* SOMMEP: D0.W <- sum of the two pushed words
SOMMEP  MOVE.W  4(SP),D0    ; second parameter (below the return address)
        ADD.W   6(SP),D0    ; first parameter
        RTS

The stack, just after the BSR:

Recursion

A subroutine can call itself. Each call needs its own values: they are stored on the stack, which keeps one per call in progress.

1
2
3
4
5
6
7
8
9
10
11* FACT: D1.L <- n!, for n = D0.W, with n <= 9
FACT    TST.W   D0
        BNE     RECUR
        MOVEQ   #1,D1       ; 0! = 1
        RTS
RECUR   MOVE.W  D0,-(SP)    ; save n: the next call will change D0
        SUBQ.W  #1,D0
        BSR     FACT        ; D1 <- (n-1)!
        MOVE.W  (SP)+,D0    ; get n back
        MULU.W  D0,D1       ; D1 <- n * (n-1)!
        RTS

For $n = 3$, three values of $n$ are pushed (3, 2, 1) before reaching $0! = 1$, then popped one by one, each one multiplying the result. The limit $n \le 9$ comes from MULU.W, which only multiplies the low word of D1: $(n-1)!$ must fit on 16 bits, that is at most 65535, and $8! = 40320$ fits, $9! = 362880$ does not.

Try it

The factorial, with input: the program asks for $n$ (service 4 of TRAP #15) and prints $n!$. Run it step by step and follow A7: it goes down by 6 bytes at each recursive call (the word for $n$ and the return address), then goes back up. Try $n = 10$: the result is wrong, for the reason given above.

        ORG     $1000
START   LEA     INVITE,A1
        MOVE.B  #14,D0          ; service 14: print the string (A1)
        TRAP    #15
        MOVE.B  #4,D0           ; service 4: read a number into D1.L
        TRAP    #15
        MOVE.W  D1,D0           ; n
        BSR     FACT            ; D1 <- n!
        MOVE.B  #3,D0           ; service 3: print D1.L
        TRAP    #15
        SIMHALT

* FACT: D1.L <- n!, for n = D0.W, with n <= 9
FACT    TST.W   D0
        BNE     RECUR
        MOVEQ   #1,D1           ; 0! = 1
        RTS
RECUR   MOVE.W  D0,-(SP)        ; save n
        SUBQ.W  #1,D0
        BSR     FACT            ; D1 <- (n-1)!
        MOVE.W  (SP)+,D0        ; get n back
        MULU.W  D0,D1           ; D1 <- n * (n-1)!
        RTS

INVITE  DC.B    'n = ',0
        END     START