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?