L10 [Stack Subroutines]

Why do we have subroutines?

• Methods
• Functions
• Procedures

Fundamentally, subroutines are about reusing code.

What does JSR do?

JSR [ 0100 | 1 | PCOffset11 ]

R7 <- PC
PC <- PC + PCOffset11

Remember, PC has been incremented fro the fetch cycle

What does JSRR do?

JSRR [ 0100 | 0 | 00 | BaseR | 000000 ]

R7 <- PC
PC <- BaseR

What does RET do?

RET [1100 | 000 | 111 | 000000]

Jumps to R7

Short and Reach Subroutines

    jsr sub

sub xxx xxx xxx

...
...
...

    ret

    ld R2, far
	jsrr r2

far .fill sub
...
...
...

sub xxx xxx xxx
    ret

How do we write a subroutine

Issue 1: What if our subroutine calls another subroutine?

• What is R7 used for?
• What happens to R7 if our subroutine calls another subroutine

We’d better find a way for our subroutine to save its R7 return address somewhere. That way, we are safe to call another subroutine. Then, we can restore our original R7, and know where to return to when we are done.

Issue 2: We only have a few registers

• With only 8 registers (R0 - R7)

  • We run out of registers really quickly

• Our main program is using some registers

  • Our subroutine also needs to use some registers
  • So let’s save the old values from the registers we’ll use
  • And then we can “borrow” these registers to use our subroutine
  • When we’re done, we’ll put back the original values into those registers – like they were never changed!

Saving Registers In a Subroutine

• How much memory space is lost if every subroutine declares space to save registers?
• What happens if our subroutine calls itself?
  • Recursion
  • We'll step on those saved registers in memory and lose those values

What do we need to save?

• Old values from registers we will use
• Our return value from R7

Where should we save these values? In a stack!

How do we implement the Stack?

• Stack is locate in some designated area of memory
• We need to store the address of the top of the stack somewhere
• Stack could grow in either direction (up or down)

Top of the stack

We only need to keep track of one thing: the top of the stack

• Memory location where the last value was pushed onto the stack
• Also is the next thing to pop off the stack

Let's use R6 to store the "stack pointer" - the top of the stack

Where do we put the stack?

Since the heap grows up, let the stack grow down to the lower memory addresses.

Note: this diagram lists the memory addresses low to high, so the arrows are inverted

Push

• Decrement stack pointer (our stack is growing down to memory addresses)
• Write data in R0 to new Top of Stack

PUSH	ADD		R6, R6, #1
		STR		R0, R6, #0

Pop

• Read data at current Top of Stack into R0
• Then increment stack pointer

POP		LDR		R0, R6, #0
		ADD		R6, R6, #1

What happens when we run out of memory?

• When stack pointer runs into heap, we get StackOverFlow

Basically, we don't care about bounds checking cause that's for losers

Follow this specific stack frame because it's a communication protocol and they have to match in order for it to work

In practice, we always do return something even if the return type is void, we just ignore it.

How does a stack help with subroutines?

• We can push R7 onto the stack to save the return address
• We can push each of the registers onto the stack to save copies of their old values
  • Borrow those registers to re-use inside of our subroutine
• When our subroutine is done, we just pop return address and original registers back off the stack

What else might a subroutine need to know?

• We're already going to save on the stack
  • R7
  • Copies of registers
• What other data does a subroutine use or need?
• What else might we want to store on the stack?
  • Arguments
  • Return value
  • Local variables

Stack Frame

• Arguments
• Return value
• Local variables
• Saved return address (R7)
• Saved registers

Stack Frame Pointer

• Keep a known location in the stack frame in another register
• Which register? R5
• We're going to always point it to the first local variable
  • And we'll always reserve space for at least one local variable, even if we don't have any local variables
• The frame pointer, R5, is an anchor
  • At a predictable location in the stack

Special Purpose Register

• R0
• R1
• R2
• R3
• R4
• R5 (Frame Pointer)
• R6 (Stack Pointer)
• R7 (Return Pointer)

From now on (with subroutines), we only use R0 - R4 as general purpose registers!

LC-3 Stack Frame

The stack frame, also known as an activation record, is the collection of all data on the stack associated with one subprogram call.

The stack frame generally includes the following components:

• Return address
• Argument variables
• Local variables
• Saved copies of any register modified by the subroutines that need to be restored

Recitation Notes

Short Review at LC-3 Instructions

• Take a look at JSR and JSRR

Review: Pseudo-Ops

1. .blkw - allocates memory for the specified label
2. .orig - tells assembler to put block of code at desired address
3. .stringz - assembler will put a string of characters in memory followed by '\0'
4. .fill - puts value in memory location
5. .end - denotes end of block, closing tag for .orig

LC-3 Assembly File Layout

Common Assembly Techniques

• Use a semicolon to write comments
• Clearing a register - AND R1, R1, 0; R1 = R1 & 0
  • You don’t necessarily have to clear a register before you use it!
  • Example: ADD R3, R2, R1 does not require you to clear R3 first
  • Remember, you CANNOT do set Rx=6 with ST Rx, 6
    • This just gets the value at memory 6 and puts it in Rx
• If-statements and while-loops use BR statements to conditionally jump (follow the templates provided in lecture!)
  • E.g. BRz will branch when condition codes are 0
  • BR or BRnzp will branch unconditionally
• Setting condition codes – ADD R1, R1, 0 ; R1 = R1 + 0
• Subtraction/negation - use NOT (flip the bits) and ADD 1

NOT R3, R1      ; R3 = ~R1
ADD R3, R3, 1   ; R3 = ~R1+1 = -R1
ADD R3, R2, R3  ; R3 = R2 + (-R1) = R2-R1

• Copy a value to another register

ADD R2, R1, 0   ; R2 = R1 + 0

Definitions

1. Caller – The code that will call a subroutine (e.g. m = mult(a, b);)
2. Callee – The subroutine definition

int mult(a, b) {
    return a * b;
}

Caller

What do we do to call a subroutine?

• Push arguments (in reverse order)
• JSR

What do we do after the subroutine returns?

• Pop return value
• Pop the arguments

At the moment a subroutine returns, what can we say about the stack?

• Answer: The stack pointer is one less than its value before the call

Callee

When a subroutine is called (stack buildup)

• Save some registers (callee-saved)
• Make room for local variables
• Save old frame pointer
• Push the return address

Do the work of the subroutine

When the procedure is about to return (stack teardown)

• Prepare return value
• Restore registers
• RET

Three Oddities

• We always allocate space for at least one local variable, even when we don't need any
• The caller always pushes N words of arguments but always pops N+1 words (which includes return value)
• Which means the callee pushes M words of stack frame, but pops M-1 to leave the Return Value on top of the stack

How might the stack frame change?

• If you only have one local variable, your stack frame will always look like the prior examples.
• If you have two or more local variables, you’ll need to allocate more space and move the saved register locations up – to make room for the additional local vars

Saving Registers

You always save R7 and R5

• The old Return Address, and old Frame Pointer

Easy answer: always save R0-R4 on the stack frame

Optional

• If your subroutine only needs to use two registers (e.g. R1,R2), then you don’t have to save the other regs (R0, R3, R4)
• But you have to know which registers you’ll use first
• It is easier just to always save all five (R0-R4) in your stack frame

Not only should you feel free to copy the code for your own programs, I strongly recommend that you copy this code.

Stack Buildup -- Callee: mult(int a, int b)

Callee – the subroutine itself

First, lay out the stack frame! This is always the same for 2 args, 1 local variable, and 5 saved registers. For other counts, just adjust the amount of stack space as needed.

MULT  ADD   R6, R6, -4  ; push 4 wds    
                        ; set rv later
      STR R7, R6, 2     ; save RA
      STR R5, R6, 1     ; save old FP
                        ; set local var later
      ADD R5, R6, 0     ; FP = SP
      ADD R6, R6, -5    ; push 5 words

      STR R0, R5, -1    ; save SR1
      STR R1, R5, -2    ; save SR2
      STR R2, R5, -3    ; save SR3
      STR R3, R5, -4    ; save SR4
      STR R4, R5, -5    ; save SR5

Implementation -- Callee: mult(int a, int b)

;int mult(int a, int b) {

         AND R0, R0, #0  ;R0 = 0
         STR R0, R5, #0  ;answer = R0

          ;; while(a > 0)
W1        LDR R0, R5, 4  ;R0 = a
          BRnz END_W1
          
          ;; answer += b
          LDR R0, R5, 0   ;R0 = answer
          LDR R1, R5, 5   ;R1 = b
          ADD R0, R0, R1  ;R0 = answer + b
          STR R0, R5, 0   ;answer = R0

          ;; a--
          LDR R0, R5, #4
          ADD R0, R0, #-1 
          STR R0, R5, #4

          BR W1

          ;return answer
END_W1    LDR R0, R5, 0
          STR R0, R5, 3

Stack Teardown -- Callee: mult(int a, int b)

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   ; pop saved regs and local vars
LDR R7, R5, 2   ; R7 = ret addr
LDR R5, R5, 1   ; FP = Old FP
ADD R6, R6, 3   ; pop 3 words
RET             ; mult() is done!

Attendance Quiz 10/14

Today's Number: 63,636

1. In what order does a subroutine push items to create its stack frame?

Return value, Return address, Saved FP, local variables, saved R0-R4

• Remember, we don't want to reinvent the wheel so we just follow this calling convention

2. On the LC-3, where does R5 point in the stack frame during the execution of a subroutine?

First local variable

3. When calculating a factorial using the algorithm described in this side deck, what is the maximum number of instances of FACT’s stack frame on the stack while calculating fact(n)?

n+1