Subroutines

#folder

Definition

Subroutines (procedures) are an abstraction that encapsulate reusable pieces of code

The caller must transfer control to callee (modify program counter), then return control to caller
The caller may pass arguments to the procedure
The procedure may return a value back to the caller.

Caller and Callee Save Conventions

Info

Caller/callee must agree on same conventions:

Where the arguments and return values are (Memory, registers)
Who allocates/frees memory, args, frame (caller or callee)
Which registers may change during the call?
- Caller-save registers: the caller must save this value in memory, the callee may change it
- Callee-save registers: the callee promises to preserve these registers, or revert them to their original value before returning control to the caller

Conventions

ARM V7 Assembly: ARM Application Procedure Call Standard (AAPCS)

CS241E MIPS Assembly:

Caller allocates param chunk, passes address in Reg.result (R3)
Callee allocates own frame
Callee frees both (param chunk frame)

Caller-save (callee modifies)	Callee-save
`link (R31)`	`framePointer (R29)`
	`stackPointer (R30)`

ECE222 (and in general for programming in assembly):

Subroutines should preserve any non-argument registers that they modify
- This preserves the execution context of the calling runtime
- Push these registers on entry, pop them on exit

Static and Dynamic Link

Definition

The dynamic link is a pointer to the frame of the caller of the currently executing procedure

Definition

The static link is a pointer to the frame of the statically enclosing procedure of the currently executing procedure

Example

Consider the code:

def f() = {
    def g() = {
        h()
    }
    def h() = {}
}

When we call h from g:

the static link of h will be the frame of f, since h is defined in f
The dynamic link will be g, since we called h from g

Prologue and Epilogue

Definition

Code at the beginning and end of a procedure that sets up and cleans up frame registers

Control Transfer

List

Mark the beginning of the procedure with a label
Load the procedure label value into Reg.targetPC (R8)
Use (MIPS JALR, ARM BL) to jump to the procedure
- Link register will also remember the current value of the program counter in Reg.link (MIPS R31, ARM R14)
After the procedure body, jump back to the caller by jumping (MIPS JR, ARM BX) to Reg.link

Code

Callee

Define(proc)

// Procedure body here

JR(Reg.link) // R31

Caller

LIS(Reg.targetPC) // R8
Use(proc)
JALR(Reg.targetPC)

For ARM V7 Assembly:

Use BL (branch and link) to call a subroutine
Use BX (branch exchange) to return from a subroutine

Implementation

Caller

__MAIN
    . . .
    BL MySub ; Stores the return address in R14 (LR)
    . . .

Callee

MySub
    . . .
    Bx LR    ; Puts the return address in R15 (PC)

Arguments are passed in R0, R1, R2, R3 (for MIPS, register 0 is reserved for the value 0)
Additional arguments are pushed on the stack
Return values are passed in R0

Allocating a Procedure Frame

List

In order to have local variables, we need to allocate a stack frame for the procedure's local variables
- We also need to pop this frame off before the procedure returns
Store the old frame pointer in some local variable on the frame of the callee (dynamic link, callee-save)
Store the new frame pointer in Reg.framePointer (R29)
- We need to restore the old frame pointer before returning

Code

Callee

Define(proc)
Stack.allocate(frame) // Allocates frame, then R3 <- stack pointer

dynamicLink = Reg.framePointer // dynamicLink <- R29
Reg.framePointer = Reg.result  // R29 <- R3

// Procedure body here

Reg.framePointer = dynamicLink // R29 <- dynamicLink

Stack.pop    // Pop frame
JR(Reg.link) // R31

Saving the Link Register

Info

In case the callee becomes a caller of another function, we need to save Reg.link (R31) so that we can still return to the caller of the current callee. This is because Reg.link is caller-save, due to function calls using JALR, and we have become the new caller.

Code

Callee

Define(proc)
Stack.allocate(frame) // Allocates frame, then R3 <- stack pointer

dynamicLink      = Reg.framePointer // dynamicLink <- R29
Reg.framePointer = Reg.result       // R29 <- R3
savedPC          = Reg.link         // savedPC <- R31

// Procedure body here

Reg.link         = savedPC     // R31 <- savedPC
Reg.framePointer = dynamicLink // R29 <- dynamicLink

Stack.pop    // Pop frame
JR(Reg.link) // R31

Passing Arguments

Info

Since we could have an arbitrary number of parameters, we will store them in a chunk. We need the caller to allocate this chunk, set the values, and then communicate the address of this chunk to the callee. We do this by storing the pointer to the param chunk in Reg.result (R3).

Code

Callee

Define(proc)
Reg.savedParamPtr = Reg.result // R5 <- R3
Stack.allocate(frame)          // Allocates frame, then R3 <- stack pointer

dynamicLink      = Reg.framePointer // dynamicLink <- R29
Reg.framePointer = Reg.result       // R29 <- R3
savedPC          = Reg.link         // savedPC <- R31

paramPtr = Reg.savedParamPtr // paramPtr <- R5

// Procedure body here

Reg.link         = savedPC     // R31 <- savedPC
Reg.framePointer = dynamicLink // R29 <- dynamicLink

Stack.pop    // Pop callee frame from above
Stack.pop    // Pop parameter frame
JR(Reg.link) // R31

Caller

// Evaluate arguments and put result into temp vars on caller frame here.
Stack.allocate(params)
// Copy args from temp vars into param chunk (i.e param 1 = temp 1, param 2 = temp 2, etc)

LIS(Reg.targetPC) // R8
Use(proc)
JALR(Reg.targetPC)

All Together

Code

Callee

Define(proc)
Reg.savedParamPtr = Reg.result // R5 <- R3
Stack.allocate(frame)          // Allocates frame, then R3 <- stack pointer

dynamicLink      = Reg.framePointer // dynamicLink <- R29
Reg.framePointer = Reg.result       // R29 <- R3
savedPC          = Reg.link         // savedPC <- R31

paramPtr = Reg.savedParamPtr // paramPtr <- R5

// Procedure body here

Reg.link         = savedPC     // R31 <- savedPC
Reg.framePointer = dynamicLink // R29 <- dynamicLink

Stack.pop    // Pop callee frame from above
Stack.pop    // Pop parameter frame
JR(Reg.link) // R31

Caller

// Evaluate arguments and put result into temp vars on caller frame here.
Stack.allocate(params)
// Copy args from temp vars into param chunk (i.e param 1 = temp 1, param 2 = temp 2, etc)

LIS(Reg.targetPC) // R8
Use(proc)
JALR(Reg.targetPC)

Figure - Frames

Note - ARM Assembly

With raw assembly, we need to preserve certain registers too, but instead of using variables, we will use push/pop.

__MAIN
    ...
    BL SBR1  ; LR <- L1
L1 ...

SBR1
    ...
    BL SBR2  ; LR <- L2
L2 ...
    BX LR    ; PC <- L2, not good

SBR2
    ...
    BX LR    ; PC <- L2

__MAIN
    ...
    BL SBR1  ; LR <- L1
L1 ...

SBR1
    PUSH {LR}
    ...
    BL SBR2  ; LR <- L2
L2 ...
    POP {PC} ; Equivalent to POP {PC}; BX LR

SBR2
    ...
    BX LR    ; PC <- L2

__MAIN
    ...
    BL SBR1  ; LR <- L1
L1 ... 

SBR1
+   PUSH {LR}
    ...
    BL SBR2  ; LR <- L2
L2 ...
+   POP {PC} ; Equivalent to POP {PC}; BX LR
-   BX LR    ; PC <- L2, not good

SBR2
    ...
    BX LR    ; PC <- L2

Eliminating Variable Accesses

elimiateVarAccesses (A5)
    if v is not a parameter
        access var at offset in frame (A3)
    else
        read paramPtr into a register (Reg.scratch)
        access var in parameter chunk (different register)

Nested Procedures

Nesting Depth

Definition

The nesting depth of a procedure is the number of outer procedures enclosing it

Static vs Dynamic Scope

Example

def f() = {
    val w = 5

    def g() = {
        val w = 7

        h()
    }

    def h() = {
        val z = 4

        z + w // Which w should we use?
    }

    g()
}

Dynamic Scope

If we use dynamic scoping, then w = 7

Definition

Dynamic scoping resolves names in the execution context of the caller at runtime

Rarely used anymore, for good reason

Static Scope (Lexical Scope)

If we use static scoping, then w = 5 (as we would probably expect)

Definition

Static scoping resolves names in execution context of the enclosing procedure at compile time

Implementing Nested Procedures

The main issue with implementing static scoping is that we need to be able to access variables in the outer enclosing procedures.

Figure

Note: staticLink is considered a parameter, which is prepared by the caller, since the caller has the information necessary to determine the correct static link.

Accessing a Variable

Steps

Access a variable v:

Follow static link times
Then access v at that frame

Formula

Computing Static Links for a Call

First, we know: , which is the enclosing procedure of the callee. Then we find , which represents how many static links we need to follow from the caller to the appropriate frame/static link.

That is, we take the difference between the scopes, and then head back one more to get its enclosing procedure

Example

def f() = {
    val x
    
    def g() = {
        h()
    }
    
    def h() = {
        k()

        def k() = {
            x
        }
    }

    g()
}

f calls g: n = 0, sl = f's frame pointer
g calls h: n = 1, sl = g's static link
- g's static link is f's frame pointer. However, we're calling from g so we don't have f's frame pointer anywhere else
h calls k: n = 0, sl = h's frame pointer
k calls g: n = 2, sl = h's static link (by following k's static link)
f calls k: n = -1, not allowed