Branch and link (BL) for subroutines in ARM Architecture - Time & Space Complexity

Time Complexity: Branch and link (BL) for subroutines

O(N)

Understanding Time Complexity

When using the BL instruction in ARM, we want to understand how calling subroutines affects the total steps the processor takes.

We ask: How does the time to run grow when the subroutine is called multiple times?

Scenario Under Consideration

Analyze the time complexity of the following ARM code snippet.

LOOP:
  BL SUBROUTINE
  ADD R0, R0, #1
  CMP R0, #N
  BLT LOOP

SUBROUTINE:
  ; some instructions
  BX LR
    

This code calls a subroutine repeatedly in a loop until a counter reaches N.

Identify Repeating Operations

Look for repeated instructions and calls.

• Primary operation: The BL instruction calls the subroutine inside the loop.
• How many times: The loop runs N times, so the subroutine is called N times.

How Execution Grows With Input

Each time the loop runs, it calls the subroutine once.

Input Size (N)	Approx. Operations
10	About 10 subroutine calls
100	About 100 subroutine calls
1000	About 1000 subroutine calls

Pattern observation: The total steps grow directly with N, the number of loop iterations.

Final Time Complexity

Time Complexity: O(N)

This means the total time grows in a straight line as the number of subroutine calls increases.

Common Mistake

[X] Wrong: "Calling a subroutine with BL inside a loop only takes constant time regardless of N."

[OK] Correct: Each BL instruction causes the processor to jump and return, so the time adds up with each call.

Interview Connect

Understanding how subroutine calls affect execution time helps you reason about program speed and efficiency in real projects.

Self-Check

What if the subroutine itself contains a loop that runs M times? How would that change the overall time complexity?

Practice

1. What does the BL instruction do in ARM architecture?

easy

A. It jumps to a subroutine and saves the return address in the link register.

B. It loads a value into a register.

C. It performs a bitwise AND operation.

D. It returns from a subroutine without saving the return address.

Solution

1. Step 1: Understand the purpose of BL

   The BL instruction is used to jump to a subroutine while saving the return address.

2. Step 2: Identify where the return address is saved

   The return address is saved in the link register (LR) to allow returning after the subroutine finishes.

3. Final Answer:

   It jumps to a subroutine and saves the return address in the link register. -> Option A

4. Quick Check:

   BL saves return address in LR [OK]

Hint: BL jumps and saves return address in LR [OK]

Common Mistakes:

• Confusing BL with simple jump instructions
• Thinking BL does not save return address
• Mixing BL with data load instructions

2. Which of the following is the correct syntax to return from a subroutine in ARM assembly?

easy

A. BX PC

B. MOV PC, LR

C. BX LR

D. BL LR

Solution

1. Step 1: Identify the instruction to return from subroutine

   Returning from a subroutine requires branching to the address stored in the link register (LR).

2. Step 2: Choose the correct instruction

   The instruction BX LR branches to the address in LR, effectively returning control.

3. Final Answer:

   BX LR -> Option C

4. Quick Check:

   Return uses BX LR [OK]

Hint: Return with BX LR to jump back [OK]

Common Mistakes:

• Using BX PC instead of BX LR
• Confusing BL with return instruction
• Using MOV PC, LR which is valid but less common

3. Consider this ARM assembly snippet:

BL subroutine
MOV R0, #0
B end
subroutine:
MOV R0, #1
BX LR
end:

What value will register R0 hold after execution?

medium

A. 1

B. 0

C. Undefined

D. The program will crash

Solution

1. Step 1: Follow the BL instruction

   The BL instruction jumps to subroutine and saves the return address (address of MOV R0, #0) in LR.

2. Step 2: Execute subroutine and return

   Inside subroutine, MOV R0, #1 sets R0 to 1, then BX LR returns to MOV R0, #0.

3. Step 3: Continue after BL

   MOV R0, #0 overwrites R0 to 0, followed by B end.

4. Final Answer:

   0 -> Option B

5. Quick Check:

   Post-return MOV R0, #0 overwrites subroutine value [OK]

Hint: BL returns to next instr MOV R0, #0 overwriting subroutine's R0=1 [OK]

Common Mistakes:

• Assuming R0 remains 1 after subroutine return
• Misidentifying the BL return address
• Thinking instructions after BL are skipped

4. Identify the error in this ARM assembly code snippet:

BL subroutine
MOV R0, #5
B end
subroutine:
MOV R0, #10
BX PC
end:

medium

A. No error; code is correct.

B. BL instruction is missing a label.

C. MOV R0, #5 should be before BL.

D. Using BX PC instead of BX LR to return causes incorrect return.

Solution

1. Step 1: Check return instruction in subroutine

   The subroutine uses BX PC to return, which branches to the current PC, not the saved return address.

2. Step 2: Understand correct return usage

   Correct return uses BX LR to jump back to the caller address saved by BL.

3. Final Answer:

   Using BX PC instead of BX LR to return causes incorrect return. -> Option D

4. Quick Check:

   Return must use BX LR, not BX PC [OK]

Hint: Return with BX LR, not BX PC [OK]

Common Mistakes:

• Using BX PC to return from subroutine
• Ignoring the link register usage
• Assuming BL needs no label

5. You want to call two subroutines in sequence using BL instructions. Which sequence correctly preserves the return addresses so both subroutines return properly?

hard

A. Use BL to first subroutine, then BL to second subroutine inside the first subroutine before returning.

B. Use BL to first subroutine, then BL to second subroutine without returning from the first.

C. Use two BL instructions one after another without returning in between.

D. Use BX LR to call subroutines instead of BL.

Solution

1. Step 1: Understand BL saves return address in LR

   Each BL saves the return address in LR, so calling BL twice in a row overwrites LR.

2. Step 2: Preserve return addresses by nesting calls

   Calling the second BL inside the first subroutine preserves the first return address until both return.

3. Step 3: Avoid overwriting LR by sequential BL calls without return

   Calling BL twice in sequence without returning overwrites LR, losing the first return address.

4. Final Answer:

   Use BL to first subroutine, then BL to second subroutine inside the first subroutine before returning. -> Option A

5. Quick Check:

   Nest BL calls to preserve return addresses [OK]

Hint: Nest BL calls to keep return addresses safe [OK]

Common Mistakes:

• Calling BL twice in a row without nesting
• Using BX LR to call subroutines
• Ignoring LR overwrite on multiple BL calls