Subroutine call convention (AAPCS) in ARM Architecture - Time & Space Complexity

Time Complexity: Subroutine call convention (AAPCS)

O(n)

Understanding Time Complexity

Analyzing the time complexity of subroutine calls helps us understand how the cost of calling functions grows as programs get larger or more complex.

We want to know how the number of instructions executed changes when calling subroutines following the ARM AAPCS rules.

Scenario Under Consideration

Analyze the time complexity of the following ARM assembly code snippet for a subroutine call using AAPCS.

    push {r4-r7, lr}    // Save registers and return address
    mov r0, r1          // Move argument
    bl  subroutine      // Branch with link (call subroutine)
    pop {r4-r7, pc}     // Restore registers and return
    

This code saves registers, passes an argument, calls a subroutine, then restores registers and returns.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The subroutine call and return instructions.
• How many times: Each call executes these instructions once per call.

How Execution Grows With Input

Each subroutine call involves a fixed number of instructions to save and restore registers and to branch.

Input Size (number of calls)	Approx. Operations
10	About 10 times the fixed call instructions
100	About 100 times the fixed call instructions
1000	About 1000 times the fixed call instructions

Pattern observation: The total instructions grow directly with the number of subroutine calls.

Final Time Complexity

Time Complexity: O(n)

This means the total execution time grows linearly with the number of subroutine calls made.

Common Mistake

[X] Wrong: "Calling a subroutine is free or constant time regardless of how many times it is called."

[OK] Correct: Each call requires saving/restoring registers and branching, so the total time increases with the number of calls.

Interview Connect

Understanding how subroutine calls scale helps you reason about program performance and efficient use of function calls in real projects.

Self-Check

What if the subroutine used more registers that need saving? How would that affect the time complexity?

Practice

1. According to the AAPCS, which registers are primarily used to pass the first four arguments to a subroutine?

easy

A. r0 to r3

B. r4 to r7

C. r8 to r11

D. lr and pc

Solution

1. Step 1: Understand argument passing in AAPCS

   The AAPCS specifies that the first four arguments to a subroutine are passed using registers r0, r1, r2, and r3.

2. Step 2: Identify the correct register range

   Registers r4 to r11 are used for other purposes, and lr (link register) stores the return address, not arguments.

3. Final Answer:

   r0 to r3 -> Option A

4. Quick Check:

   Arguments passed in r0-r3 [OK]

Hint: Remember: first 4 args in r0-r3 registers [OK]

Common Mistakes:

• Confusing argument registers with callee-saved registers
• Thinking lr or pc hold arguments
• Assuming stack is always used first

2. Which register is used to store the return address when a subroutine is called under AAPCS?

easy

A. lr

B. r0

C. pc

D. sp

Solution

1. Step 1: Identify the purpose of the link register (lr)

   In AAPCS, the link register (lr) holds the return address when a subroutine is called.

2. Step 2: Differentiate from other registers

   r0 is for return values, pc is the program counter (current instruction), and sp is the stack pointer, not for return addresses.

3. Final Answer:

   lr -> Option A

4. Quick Check:

   Return address stored in lr [OK]

Hint: Return address always saved in lr register [OK]

Common Mistakes:

• Confusing lr with pc (program counter)
• Thinking r0 holds return address
• Assuming sp stores return address

3. Consider a subroutine that takes 5 integer arguments. According to AAPCS, how are these arguments passed?

medium

A. All 5 arguments passed in r0 to r4

B. First 4 in r0 to r3, 5th on the stack

C. All 5 arguments passed on the stack

D. First 3 in r0 to r2, remaining 2 in r3 and r4

Solution

1. Step 1: Recall argument passing rules for more than 4 arguments

   AAPCS passes the first 4 arguments in registers r0 to r3. Any additional arguments are passed on the stack.

2. Step 2: Apply to 5 arguments

   For 5 arguments, the first 4 go into r0-r3, and the 5th argument is placed on the stack.

3. Final Answer:

   First 4 in r0 to r3, 5th on the stack -> Option B

4. Quick Check:

   Extra args beyond 4 go on stack [OK]

Hint: Only first 4 args in registers; rest go on stack [OK]

Common Mistakes:

• Assuming all args fit in registers
• Passing 5th arg in r4 incorrectly
• Ignoring stack usage for extra args

4. A programmer notices that after a subroutine call, the value in register r4 is unexpectedly changed. What is the most likely cause under AAPCS?

medium

A. r4 is a caller-saved register and was not preserved by the caller

B. r4 holds the return address and was corrupted

C. r4 is used to pass arguments and was overwritten

D. r4 is a callee-saved register and the callee did not save it

Solution

1. Step 1: Understand register saving responsibilities

   Under AAPCS, registers r4 to r11 are callee-saved, meaning the called function must save and restore them if it uses them.

2. Step 2: Identify the cause of unexpected change

   If r4 changed unexpectedly, it means the callee did not save and restore it properly, causing corruption.

3. Final Answer:

   r4 is a callee-saved register and the callee did not save it -> Option D

4. Quick Check:

   Callee must save r4-r11 [OK]

Hint: Callee saves r4-r11; caller saves r0-r3 [OK]

Common Mistakes:

• Thinking r4 is caller-saved
• Confusing argument registers with saved registers
• Assuming r4 holds return address

5. You need to write a subroutine that returns a 64-bit integer result. According to AAPCS, how should the return value be passed back to the caller?

hard

A. On the stack, not in registers

B. In r0 only, using 64 bits

C. In r0 and r1 combined

D. In r2 and r3 combined

Solution

1. Step 1: Recall return value passing rules for 64-bit values

   AAPCS specifies that 64-bit return values are passed using two registers: r0 and r1 combined.

2. Step 2: Eliminate incorrect options

   r0 alone holds 32 bits, so it cannot hold 64-bit values. Stack is not used for normal return values. r2 and r3 are not used for return values.

3. Final Answer:

   In r0 and r1 combined -> Option C

4. Quick Check:

   64-bit return uses r0 and r1 [OK]

Hint: 64-bit returns use r0 and r1 registers together [OK]

Common Mistakes:

• Assuming 64-bit fits in r0 alone
• Returning via stack unnecessarily
• Using wrong registers for return