Notes 9 & 10: Stacks, Subroutines, and Recursion - Study Notes

ARM: Stacks, Subroutines, and Recursion - Study Notes

INTRODUCTION

• Overview:

  • Previous implementation of subroutines using BL (branch with link) and return with MOV PC, R14.

  • Emphasized the need for careful register usage following APCS (ARM Procedure Call Standard).

  • Introduced the stack as temporary storage for register values.

  • Aim for this session: Tie together the concepts of stacks, subroutines, and recursion.

SUBROUTINES

Generic Subroutine Example

• Basic Structure:

  • Example call:
    plaintext main BL func1

• The BL instruction calls the function func1, storing the return address in the Link Register (R14).

Subroutine Call Flow

• Subroutine Call Sequence:

  • In main, call func1:
    plaintext main BL func1 MOV PC, R14

APCS REGISTER USE CONVENTION

• Register Roles:
  
  

  Register	APCS Name	APCS Role
  R0	A1	Argument 1 / Integer Result / Scratch Register
  R1	A2	Argument 2 / Integer Result / Scratch Register
  R2	A3	Argument 3 / Scratch Register
  R3	A4	Argument 4 / Scratch Register
  R4	V1	Register Variable 1
  R5	V2	Register Variable 2
  R6	V3	Register Variable 3
  R7	V4	Register Variable 4
  R8	V5	Register Variable 5
  R9	SB/V6	Static Base / Register Variable 6
  R10	SL/V7	Stack Limit / Register Variable 7
  R11	FP	Frame Pointer
  R12	IP	Scratch Register / Specialist Use by Linker
  R13	SP	Lower End of Current Stack Frame
  R14	LR	Link Address / Scratch Register
  R15	PC	Program Counter
  Preservation Rules:

  • Green registers (caller-saved) must be preserved by the caller.

  • Orange registers (callee-saved) must be preserved by the callee.

  • Purple (R14 - Link Register) needs to be stored if calling another subroutine/function.

STACK AND SUBROUTINES

• Stack Preservation:

  • Preserves register values using the stack.

  • Ensure valid stack pointer (R13) before manipulation: MOV R13, #0x10000.

  • Use STMFD to push and LDMFD to pop register values.

STMXX / LDMXX INSTRUCTIONS

• Instructions Overview:

  • The register list in operations like STMFD or LDMFD is enclosed in curly braces {}.

  • Commas separate individual registers, and hyphens specify ranges.

  • Example of push:
    plaintext STMFD R13!, {R0-R5, R8, R14}

  • Example of pop:
    plaintext LDMFD R13!, {R0-R5, R8, R14}

• Mapping Addresses to Registers:

  • The item at the lowest address maps to the lowest register number in the specified registers, facilitating register restoration.

LINK REGISTER (R14) STORAGE

• Storing Link Register:

  • If a function does not call other functions (leaf function), storing R14 is unnecessary.

  • If calling another function, it’s critical to store R14 to avoid overwriting it.

• Potential Problems:

  • Failing to store R14 can result in an infinite loop if a function tries to return to the wrong address.

STACK FRAMES

• Definition:

  • When a function is called, data such as register values and local variables are stored on the stack, forming the stack frame.

  • Each local variable instance for each function invocation is stored on the stack, ensuring uniqueness especially in recursive or multi-threaded scenarios.

• Return Behavior:

  • After a procedure exits, all data pushed to the stack must be popped, restoring the prior stack state and maintaining expected functionality.

LOCAL VARIABLES

• Storage Mechanism:

  • Local variables are stored on the stack to ensure unique instances for each invocation.

  • Space can be created by using a SUB instruction and can be cleaned up with an ADD later, using offsets to access variables.

FRAME POINTER USAGE

• Frame Pointer Role:

  • Another register can be used as a frame pointer to denote a fixed location on the stack frame.

  • This allows other registers, variables, and parameters to be accessed via fixed offsets from the frame pointer.

RECURSION

• General Concept:

  • Functions that invoke themselves; requires mechanism for base case to escape recursion to prevent infinite loops.

• Implementing Recursion in ARM:

  • Use BL to call a function and store the return address in R14.

  • Use MOV PC, R14 to return, utilizing stack for register preservation.

FACTORIAL FUNCTION

• Definition:

  • Factorial is recursively defined as follows:
    $<br>factorial(n) = n imes factorial(n-1) <br>$

  • Base case:
    $<br>factorial(0) = 1<br>$

• Example Calculation:

  • $<br>factorial(4) = 4 imes 3 imes 2 imes 1 imes 1 = 24<br>$

• C Implementation:
  c int factorial(int n) { if(n == 0) return 1; else return n * factorial(n-1); }

• Explore ARM assembler for implementing factorial while noting it’s not tail-recursive due to multiplication occurring after calling factorial.

ARM Implementation Details

• Requires storing both the argument n and the link register R14 on the stack to enable recursive and base case handling.

• Passing arguments: The input is passed in R0 and returned in R0.

FACTORIAL STACK FRAME

• Stack Layout:

  • Each instance of n during recursion is stored in a separate stack frame, ensuring uniqueness and avoiding interference between calls.

FINAL WORDS ON STACKS

• Uniqueness of Stack Instances:

  • Different instances of n exist in the factorial stack, emphasizing the necessity of storing values on the stack.

  • The appropriate function of the compiler is to generate correct stack frame code or ensuring manual coding does the same in machine code.