Stack frame setup in ARM Architecture - Time & Space Complexity

Time Complexity: Stack frame setup

O(1)

Understanding Time Complexity

When a function runs on ARM architecture, it sets up a stack frame to keep track of data like return addresses and local variables.

We want to understand how the time to set up this stack frame changes as the function's needs grow.

Scenario Under Consideration

Analyze the time complexity of the following ARM code snippet for setting up a stack frame.

    push {fp, lr}       // Save frame pointer and return address
    mov fp, sp          // Set frame pointer
    sub sp, sp, #16     // Allocate space for locals
    // Function body ...
    add sp, sp, #16     // Deallocate locals
    pop {fp, pc}        // Restore frame pointer and return
    

This code saves important registers, sets up space for local variables, and restores everything before returning.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Fixed number of push, pop, add, and sub instructions for stack setup and teardown.
• How many times: Each instruction runs once per function call; no loops or recursion in setup.

How Execution Grows With Input

The number of instructions to set up the stack frame stays the same regardless of input size.

Input Size (n)	Approx. Operations
10	5 instructions
100	5 instructions
1000	5 instructions

Pattern observation: The setup cost does not grow with input size; it remains constant.

Final Time Complexity

Time Complexity: O(1)

This means the time to set up the stack frame stays the same no matter how big the input is.

Common Mistake

[X] Wrong: "Stack frame setup time grows with the size of input data or number of local variables."

[OK] Correct: The setup instructions run a fixed number of times; space for locals is reserved by adjusting the stack pointer, which is a single instruction regardless of size.

Interview Connect

Understanding stack frame setup time helps you appreciate how function calls work efficiently at a low level, a useful skill when discussing performance or debugging.

Self-Check

"What if the function had to save many more registers or allocate a very large local array? How would the time complexity of stack frame setup change?"

Practice

1. What is the primary purpose of setting up a stack frame in ARM architecture during a function call?

easy

A. To save the return address and local variables safely

B. To increase the CPU clock speed

C. To clear all registers before execution

D. To allocate memory for global variables

Solution

1. Step 1: Understand stack frame role

   A stack frame stores important data like return address and local variables for each function call.

2. Step 2: Identify the main purpose

   This setup ensures the function can return correctly and use local data safely.

3. Final Answer:

   To save the return address and local variables safely -> Option A

4. Quick Check:

   Stack frame purpose = Save return address and locals [OK]

Hint: Stack frame saves return address and locals [OK]

Common Mistakes:

• Confusing stack frame with CPU speed control
• Thinking it clears all registers
• Mixing local and global variable storage

2. Which ARM instruction is commonly used to save the link register (return address) onto the stack during stack frame setup?

easy

A. MOV LR, SP

B. POP {LR}

C. PUSH {LR}

D. ADD SP, SP, #4

Solution

1. Step 1: Identify instruction to save LR

   The link register (LR) holds the return address and is saved on the stack using PUSH.

2. Step 2: Match correct instruction

   PUSH {LR} stores LR on the stack; POP {LR} restores it. MOV and ADD do not save LR on stack.

3. Final Answer:

   PUSH {LR} -> Option C

4. Quick Check:

   Save LR with PUSH {LR} [OK]

Hint: Use PUSH to save LR on stack [OK]

Common Mistakes:

• Using POP instead of PUSH to save
• Confusing MOV with stack operations
• Adding to SP instead of saving LR

3. Consider this ARM assembly snippet for function entry:

SUB SP, SP, #16
PUSH {LR}

What is the effect on the stack pointer (SP) after these instructions?

medium

A. SP increases by 16 bytes

B. SP decreases by 16 bytes, then by 4 bytes

C. SP decreases by 20 bytes

D. SP remains unchanged

Solution

1. Step 1: Analyze SUB SP, SP, #16

   This subtracts 16 from SP, moving it down by 16 bytes to allocate space.

2. Step 2: Analyze PUSH {LR}

   PUSH stores LR on stack, which decreases SP by 4 bytes (ARM uses 4-byte words).

3. Final Answer:

   SP decreases by 16 bytes, then by 4 bytes -> Option B

4. Quick Check:

   SP moves down 16 + 4 bytes = 20 bytes total [OK]

Hint: SUB reduces SP, PUSH reduces SP by 4 bytes [OK]

Common Mistakes:

• Adding to SP instead of subtracting
• Ignoring PUSH effect on SP
• Assuming SP stays same after PUSH

4. In this ARM function prologue, what is the error?

SUB SP, SP, #8
POP {LR}

medium

A. LR should not be used in function prologue

B. SUB should add to SP, not subtract

C. SP should not be changed in prologue

D. POP should be PUSH to save LR first

Solution

1. Step 1: Understand stack frame setup order

   Function prologue saves LR by PUSH before changing SP to allocate space.

2. Step 2: Identify incorrect instruction

   POP removes data from stack; here it tries to restore LR before saving it, which is wrong.

3. Final Answer:

   POP should be PUSH to save LR first -> Option D

4. Quick Check:

   Save LR with PUSH before POP [OK]

Hint: Save LR with PUSH before POP [OK]

Common Mistakes:

• Using POP instead of PUSH to save LR
• Changing SP incorrectly
• Ignoring function prologue conventions

5. You want to create a stack frame that saves LR and allocates 24 bytes for local variables. Which sequence correctly sets up the stack frame in ARM assembly?

hard

A. SUB SP, SP, #24
PUSH {LR}

B. PUSH {LR}
SUB SP, SP, #24

C. PUSH {LR, R4}
SUB SP, SP, #20

D. SUB SP, SP, #28
PUSH {LR}

Solution

1. Step 1: Save LR before allocating locals

   Correct order is to allocate space first by subtracting from SP, then save LR with PUSH.

2. Step 2: Check options for correct order and size

   SUB SP, SP, #24 PUSH {LR} subtracts 24 bytes first, then saves LR, which is the correct order to allocate space and save registers.

3. Step 3: Re-examine options carefully

   SUB SP, SP, #24 PUSH {LR}: SUB SP, SP, #24 then PUSH {LR} - correct order and size.
   PUSH {LR} SUB SP, SP, #24: PUSH {LR} then SUB SP, SP, #24 - wrong order.
   PUSH {LR, R4} SUB SP, SP, #20: PUSH {LR, R4} then SUB SP, SP, #20 - wrong registers and size.
   SUB SP, SP, #28 PUSH {LR}: SUB SP, SP, #28 then PUSH {LR} - wrong size.

4. Final Answer:

   SUB SP, SP, #24 PUSH {LR} -> Option A

5. Quick Check:

   Allocate locals first, then save LR [OK]

Hint: SUB SP first to allocate locals, then PUSH LR [OK]

Common Mistakes:

• Allocating space after saving LR
• Using wrong register sets in PUSH
• Mismatching allocated bytes and saved registers