Link register (R14/LR) in ARM Architecture - Time & Space Complexity

Time Complexity: Link register (R14/LR)

O(n)

Understanding Time Complexity

When working with the link register (R14/LR) in ARM assembly, it's important to understand how its use affects the flow of a program.

We want to see how the number of instructions executed grows when using the link register for function calls and returns.

Scenario Under Consideration

Analyze the time complexity of the following ARM code snippet using the link register.

    BL function  ; Branch with link to function
    ...
    function:
      ; function body
      BX LR       ; Return using link register
    

This code calls a function using the link register to store the return address, then returns back to the caller.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Each function call uses the link register to jump and return.
• How many times: The number of calls depends on how many times the function is invoked.

How Execution Grows With Input

Each function call adds a fixed number of instructions for branching and returning.

Input Size (n)	Approx. Operations
10	About 20 instructions (10 calls and 10 returns)
100	About 200 instructions
1000	About 2000 instructions

Pattern observation: The total instructions grow linearly with the number of function calls.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows directly in proportion to how many times the function is called.

Common Mistake

[X] Wrong: "Using the link register makes function calls take constant time regardless of how many calls happen."

[OK] Correct: Each call and return still uses instructions, so total time grows with the number of calls.

Interview Connect

Understanding how the link register works helps you explain how function calls manage return addresses efficiently in ARM assembly.

Self-Check

"What if the function called itself recursively many times? How would that affect the time complexity related to the link register usage?"

Practice

1. What is the primary purpose of the link register (R14/LR) in ARM architecture?

easy

A. To manage stack pointer operations

B. To hold the current instruction being executed

C. To store general-purpose data temporarily

D. To store the return address during function calls

Solution

1. Step 1: Understand the role of the link register

   The link register (R14/LR) is specifically designed to hold the return address when a function call is made.

2. Step 2: Differentiate from other registers

   Other registers like the program counter hold the current instruction, and the stack pointer manages the stack, but LR stores the return address.

3. Final Answer:

   To store the return address during function calls -> Option D

4. Quick Check:

   Link register = return address storage [OK]

Hint: LR always holds return address after a function call [OK]

Common Mistakes:

• Confusing LR with the program counter
• Thinking LR stores general data
• Mixing LR with stack pointer

2. Which ARM instruction saves the return address into the link register (LR)?

easy

A. BL

B. ADD

C. MOV

D. STR

Solution

1. Step 1: Identify the instruction for function calls

   The BL (Branch with Link) instruction branches to a function and saves the return address in LR.

2. Step 2: Understand other instructions

   MOV moves data, ADD adds values, and STR stores data to memory; none save return addresses.

3. Final Answer:

   BL -> Option A

4. Quick Check:

   BL saves return address in LR [OK]

Hint: BL means branch and link (save return) [OK]

Common Mistakes:

• Choosing MOV as it moves data
• Confusing STR with saving return address
• Thinking ADD saves addresses

3. Consider this ARM code snippet:
BL function
...
function:
MOV R0, #5
BX LR
What happens when the instruction BX LR executes?

medium

A. The program jumps back to the instruction after BL

B. The program jumps to the start of function

C. The program halts execution

D. The program jumps to an undefined address

Solution

1. Step 1: Understand what BL does

   BL saves the return address (next instruction after BL) into LR and jumps to 'function'.

2. Step 2: Analyze BX LR instruction

   BX LR branches to the address stored in LR, which is the return address after BL.

3. Final Answer:

   The program jumps back to the instruction after BL -> Option A

4. Quick Check:

   BX LR returns to caller address [OK]

Hint: BX LR returns to saved return address [OK]

Common Mistakes:

• Thinking BX LR jumps to function start
• Assuming program halts on BX LR
• Believing BX LR jumps to random address

4. In this ARM code, what is the error?
BL function
...
function:
MOV R0, #10
MOV PC, R0

medium

A. BL instruction is invalid

B. MOV PC, R0 does not return to caller correctly

C. MOV R0, #10 is not allowed

D. Function label is missing

Solution

1. Step 1: Check the return method

   To return from a function, the program must jump to the address in LR, not to a fixed value in R0.

2. Step 2: Identify the problem with MOV PC, R0

   MOV PC, R0 sets the program counter to 10, which is not a valid return address, causing incorrect behavior.

3. Final Answer:

   MOV PC, R0 does not return to caller correctly -> Option B

4. Quick Check:

   Return must use LR, not arbitrary register [OK]

Hint: Return by jumping to LR, not arbitrary register [OK]

Common Mistakes:

• Thinking BL is invalid
• Assuming MOV R0, #10 is wrong
• Ignoring the need to use LR for return

5. You want to write a function in ARM that calls another function and then returns correctly. Which sequence correctly uses the link register (LR)?

hard

A. Use B to call the function, then return with BX R14

B. Use B to call the function, then return with MOV PC, LR

C. Use BL to call the function, then return with BX LR

D. Use BL to call the function, then return with MOV PC, R0

Solution

1. Step 1: Understand function call with BL

   BL saves the return address in LR and branches to the called function.

2. Step 2: Understand correct return instruction

   Returning is done by branching to LR using BX LR, which jumps back to the saved return address.

3. Step 3: Evaluate other options

   B does not save return address in LR; MOV PC, R0 returns to wrong place; BX R14 is equivalent to BX LR but using B (not BL) means LR is not saved.

4. Final Answer:

   Use BL to call the function, then return with BX LR -> Option C

5. Quick Check:

   BL + BX LR = correct call and return [OK]

Hint: Call with BL, return with BX LR always [OK]

Common Mistakes:

• Using B instead of BL for calls
• Returning with MOV PC, R0 instead of BX LR
• Confusing BX R14 and BX LR usage