Preserving callee-saved registers in ARM Architecture - Time & Space Complexity

Time Complexity: Preserving callee-saved registers

O(n)

Understanding Time Complexity

When preserving callee-saved registers, we want to understand how the work grows as the number of registers or instructions increases.

We ask: How does saving and restoring registers affect execution time as the code changes?

Scenario Under Consideration

Analyze the time complexity of the following ARM assembly snippet that saves and restores callee-saved registers.

    push {r4-r7, lr}    // Save registers on stack
    ...                 // Function body instructions
    pop {r4-r7, pc}     // Restore registers and return
    

This code saves four registers before the function runs and restores them before returning.

Identify Repeating Operations

Look for repeated actions that take time.

• Primary operation: Saving and restoring each callee-saved register to/from the stack.
• How many times: Once per function call, for each register saved.

How Execution Grows With Input

As the number of callee-saved registers increases, the time to save and restore grows linearly.

Number of Registers (n)	Approx. Operations
4	8 (4 push + 4 pop)
8	16 (8 push + 8 pop)
16	32 (16 push + 16 pop)

Pattern observation: Doubling registers doubles the save and restore operations.

Final Time Complexity

Time Complexity: O(n)

This means the time to preserve registers grows directly with how many registers you save and restore.

Common Mistake

[X] Wrong: "Saving registers takes constant time no matter how many are saved."

[OK] Correct: Each register requires a separate save and restore step, so more registers mean more work.

Interview Connect

Understanding how saving registers scales helps you write efficient low-level code and shows you grasp how function calls impact performance.

Self-Check

What if we used a different calling convention that saves fewer registers? How would the time complexity change?

Practice

1. What is the main purpose of preserving callee-saved registers in ARM architecture?

easy

A. To speed up the execution of the program

B. To allow the caller to modify registers freely

C. To keep the values intact across function calls

D. To reduce the number of registers used

Solution

1. Step 1: Understand the role of callee-saved registers

   Callee-saved registers must keep their values unchanged after a function call to avoid breaking the caller's data.

2. Step 2: Identify the purpose of preserving these registers

   Preserving means saving and restoring their values so the caller sees no change.

3. Final Answer:

   To keep the values intact across function calls -> Option C

4. Quick Check:

   Preserving registers = keeping values intact [OK]

Hint: Remember: callee saves to protect caller's data [OK]

Common Mistakes:

• Thinking callee-saved registers speed up execution
• Confusing callee-saved with caller-saved registers
• Believing registers can be freely modified without saving

2. Which ARM assembly instruction is commonly used to save callee-saved registers at the start of a function?

easy

A. MOV

B. ADD

C. CMP

D. PUSH

Solution

1. Step 1: Identify instruction to save registers

   The PUSH instruction stores registers onto the stack, preserving their values.

2. Step 2: Confirm PUSH is used at function start

   Functions use PUSH to save callee-saved registers before modifying them.

3. Final Answer:

   PUSH -> Option D

4. Quick Check:

   Save registers = PUSH [OK]

Hint: PUSH saves registers on stack at function start [OK]

Common Mistakes:

• Using MOV which copies but doesn't save to stack
• Using ADD which changes values, not saves
• Using CMP which compares values, not saves

3. Consider this ARM function snippet:

func:
  PUSH {r4, r5}
  MOV r4, #10
  MOV r5, #20
  POP {r4, r5}
  BX lr

What will be the value of registers r4 and r5 after returning to the caller?

medium

A. r4 and r5 unchanged from caller

B. r4 and r5 contain random values

C. r4 = 0, r5 = 0

D. r4 = 10, r5 = 20

Solution

1. Step 1: Analyze PUSH and POP effect

   PUSH saves original r4 and r5 values on stack; POP restores them before return.

2. Step 2: Understand MOV instructions inside function

   Inside function, r4 and r5 are changed, but POP restores original values before returning.

3. Final Answer:

   r4 and r5 unchanged from caller -> Option A

4. Quick Check:

   Saved and restored registers = unchanged after call [OK]

Hint: PUSH then POP restores original register values [OK]

Common Mistakes:

• Assuming MOV changes persist after POP
• Ignoring that POP restores saved registers
• Thinking registers reset to zero automatically

4. A function modifies callee-saved registers but forgets to restore them before returning. What problem can this cause?

medium

A. The program may crash or behave unpredictably

B. The function will run faster

C. The caller's registers remain unchanged

D. The stack pointer will not be affected

Solution

1. Step 1: Understand callee-saved register role

   These registers must be restored to keep caller's data intact.

2. Step 2: Consequence of not restoring

   If not restored, caller sees wrong values, causing crashes or wrong behavior.

3. Final Answer:

   The program may crash or behave unpredictably -> Option A

4. Quick Check:

   Not restoring callee-saved = crashes/unpredictable [OK]

Hint: Not restoring callee-saved causes crashes [OK]

Common Mistakes:

• Thinking it improves speed
• Believing caller's registers stay safe without restore
• Ignoring stack pointer effects

5. You have a function that uses registers r4, r5, and r6 (all callee-saved). Which sequence correctly preserves and restores these registers?

hard

A. MOV r4, #0
MOV r5, #0
MOV r6, #0
...function body...
BX lr

B. PUSH {r4, r5, r6}
...function body...
POP {r4, r5, r6}

C. PUSH {r4}
PUSH {r5}
PUSH {r6}
...function body...
POP {r4}
POP {r5}
POP {r6}

D. POP {r4, r5, r6}
...function body...
PUSH {r4, r5, r6}

Solution

1. Step 1: Identify correct saving method

   Registers must be pushed together at function start to save their original values.

2. Step 2: Identify correct restoring method

   Registers must be popped in the same order before returning to restore original values.

3. Step 3: Check options for correct sequence

   PUSH {r4, r5, r6} ...function body... POP {r4, r5, r6} pushes all three registers at once and pops them before return, which is correct.

4. Final Answer:

   PUSH {r4, r5, r6} ...function body... POP {r4, r5, r6} -> Option B

5. Quick Check:

   Push all then pop all = correct preservation [OK]

Hint: Push all callee-saved at start, pop all before return [OK]

Common Mistakes:

• Pushing and popping registers separately in wrong order
• Using POP before PUSH
• Overwriting registers without saving