General purpose registers (R0-R12) in ARM Architecture - Time & Space Complexity

Time Complexity: General purpose registers (R0-R12)

O(n)

Understanding Time Complexity

We want to understand how using general purpose registers affects the speed of ARM code.

Specifically, how does the number of instructions using these registers impact execution time?

Scenario Under Consideration

Analyze the time complexity of the following ARM code snippet.

MOV R0, #0
MOV R1, #10
LOOP:
ADD R0, R0, R1
SUBS R1, R1, #1
BNE LOOP

This code adds the value in R1 to R0 repeatedly, decreasing R1 until it reaches zero.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop that adds and subtracts using registers R0 and R1.
• How many times: The loop runs as many times as the initial value in R1 (here 10 times).

How Execution Grows With Input

As the starting value in R1 increases, the loop runs more times, so execution grows linearly.

Input Size (n)	Approx. Operations
10	About 10 loop cycles
100	About 100 loop cycles
1000	About 1000 loop cycles

Pattern observation: Doubling the input roughly doubles the number of operations.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows directly in proportion to the number of times the loop runs.

Common Mistake

[X] Wrong: "Using more registers makes the code run faster regardless of loop size."

[OK] Correct: The number of loop cycles depends on input size, not just how many registers are used.

Interview Connect

Understanding how loops and registers affect execution time helps you explain performance in low-level code clearly and confidently.

Self-Check

"What if the loop used two registers to add values instead of one? How would the time complexity change?"

Practice

1. Which of the following registers are considered general purpose registers in ARM architecture?

easy

A. R0 to R12

B. R13 to R15

C. Program Counter and Status Register

D. Floating Point Registers

Solution

1. Step 1: Identify general purpose registers in ARM

   Registers R0 through R12 are used for general data storage and manipulation.

2. Step 2: Differentiate special registers

   Registers R13 to R15 and others like Program Counter are special purpose, not general.

3. Final Answer:

   R0 to R12 -> Option A

4. Quick Check:

   General purpose registers = R0-R12 [OK]

Hint: General purpose registers are R0 to R12 only [OK]

Common Mistakes:

• Confusing R13-R15 as general purpose
• Including special registers like Program Counter
• Thinking floating point registers are general purpose

2. Which of the following is the correct way to refer to the 5th general purpose register in ARM assembly?

easy

A. R6

B. R5

C. R4

D. R7

Solution

1. Step 1: Understand register numbering

   Registers start at R0, so the 1st is R0, 2nd is R1, and so on.

2. Step 2: Count to the 5th register

   Counting from R0: R0(1), R1(2), R2(3), R3(4), R4(5). So the 5th register is R4.

3. Step 3: Verify options

   R5 is R5, which is actually the 6th register, so the correct is R4 (R4).

4. Final Answer:

   R4 -> Option C

5. Quick Check:

   5th register = R4 [OK]

Hint: Count from R0 to find the register number [OK]

Common Mistakes:

• Starting count from R1 instead of R0
• Mixing register numbers with their positions
• Choosing R5 thinking it is the 5th register

3. Given the ARM assembly instructions:
MOV R0, #10
ADD R1, R0, #5
SUB R2, R1, R0
What is the final value stored in register R2?

medium

A. 5

B. 15

C. 10

D. 0

Solution

1. Step 1: Execute MOV and ADD instructions

   MOV R0, #10 sets R0 = 10. ADD R1, R0, #5 sets R1 = 10 + 5 = 15.

2. Step 2: Execute SUB instruction

   SUB R2, R1, R0 sets R2 = 15 - 10 = 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   R2 = R1 - R0 = 15 - 10 = 5 [OK]

Hint: Calculate step-by-step register values [OK]

Common Mistakes:

• Mixing up source and destination registers
• Forgetting immediate values in ADD
• Assuming R2 equals R1 or R0 directly

4. Identify the error in the following ARM assembly snippet:
MOV R13, #20
ADD R0, R13, #5
What is the issue?

medium

A. ADD instruction requires three registers, not two registers and an immediate

B. Immediate value #5 is invalid

C. MOV instruction cannot move immediate values

D. R13 is not a general purpose register and should not be used like this

Solution

1. Step 1: Check register usage

   R13 is the stack pointer, a special purpose register, not general purpose.

2. Step 2: Validate instruction correctness

   Using R13 like a general purpose register is incorrect; MOV and ADD with immediate values are valid.

3. Final Answer:

   R13 is not a general purpose register and should not be used like this -> Option D

4. Quick Check:

   R13 is special purpose, not general [OK]

Hint: Remember R13-R15 are special, not general registers [OK]

Common Mistakes:

• Assuming R13 is general purpose
• Thinking immediate values are invalid
• Believing ADD can't use immediate values

5. You want to swap the values of registers R2 and R3 using only R0 as a temporary register. Which sequence of instructions correctly achieves this?

hard

A. MOV R2, R3MOV R3, R2MOV R0, R2

B. MOV R0, R2MOV R2, R3MOV R3, R0

C. MOV R0, R3MOV R3, R2MOV R3, R0

D. MOV R0, R2MOV R3, R2MOV R2, R0

Solution

1. Step 1: Save R2 value temporarily

   MOV R0, R2 stores R2's value in R0 to keep it safe.

2. Step 2: Move R3 value to R2

   MOV R2, R3 copies R3's value into R2, overwriting original R2.

3. Step 3: Restore original R2 value to R3

   MOV R3, R0 moves saved R2 value from R0 into R3, completing the swap.

4. Final Answer:

   MOV R0, R2; MOV R2, R3; MOV R3, R0 -> Option B

5. Quick Check:

   Use temp register R0 to swap R2 and R3 [OK]

Hint: Use R0 as temp: save R2, copy R3 to R2, restore R2 to R3 [OK]

Common Mistakes:

• Overwriting R2 before saving it
• Swapping without a temporary register
• Mixing source and destination registers