Addressing modes (immediate, register, offset) in ARM Architecture - Time & Space Complexity

Time Complexity: Addressing modes (immediate, register, offset)

O(n)

Understanding Time Complexity

We want to understand how the time it takes to access data changes when using different addressing modes in ARM assembly.

Specifically, how does the choice of immediate, register, or offset addressing affect the number of steps the processor takes?

Scenario Under Consideration

Analyze the time complexity of the following ARM instructions using different addressing modes.

LDR R0, =0x1000      // Load immediate address
LDR R1, [R0]         // Load from memory using register
LDR R2, [R0, #4]     // Load from memory using offset
ADD R3, R1, R2       // Add values
    

This code loads a value from a fixed address, then loads another value from an address offset by 4 bytes, and finally adds them.

Identify Repeating Operations

Look for repeated steps or memory accesses that take time.

• Primary operation: Memory load instructions (LDR) that access data.
• How many times: Each load happens once here, but in a loop these could repeat many times.

How Execution Grows With Input

Imagine repeating these loads many times in a loop over data.

Input Size (n)	Approx. Operations
10	About 20 memory loads and adds
100	About 200 memory loads and adds
1000	About 2000 memory loads and adds

Pattern observation: The number of operations grows directly with the number of data items processed.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the operations grows linearly as the number of data items increases.

Common Mistake

[X] Wrong: "Using immediate addressing always makes the code run faster regardless of data size."

[OK] Correct: Immediate addressing loads fixed values quickly, but when accessing many data items, memory loads using register or offset addressing dominate time.

Interview Connect

Understanding how different addressing modes affect execution time helps you write efficient assembly and shows you can think about performance at a low level.

Self-Check

"What if we replaced the offset addressing with register indirect addressing inside a loop? How would that affect the time complexity?"

Practice

1. Which addressing mode uses a fixed number directly inside the instruction to provide data?

easy

A. Immediate addressing mode

B. Register addressing mode

C. Offset addressing mode

D. Indirect addressing mode

Solution

1. Step 1: Understand immediate addressing mode

   Immediate mode means the instruction contains the actual number (constant) to use.

2. Step 2: Compare with other modes

   Register mode uses CPU registers, offset mode calculates address by adding offset to a register, indirect mode uses memory address stored in a register.

3. Final Answer:

   Immediate addressing mode -> Option A

4. Quick Check:

   Fixed number inside instruction = Immediate mode [OK]

Hint: Immediate mode has the number right inside the instruction [OK]

Common Mistakes:

• Confusing immediate with register mode
• Thinking offset mode uses fixed numbers directly
• Mixing indirect addressing with immediate

2. Which of the following is the correct syntax for using register addressing mode in ARM assembly to move data from register R1 to R0?

easy

A. MOV R0, [R1]

B. MOV R0, #R1

C. MOV R0, R1

D. MOV [R0], R1

Solution

1. Step 1: Understand register addressing syntax

   Register addressing uses register names directly without # or brackets.

2. Step 2: Analyze options

   MOV R0, R1 uses MOV R0, R1 which copies data from R1 to R0 correctly. MOV R0, #R1 wrongly uses # which means immediate. MOV R0, [R1] uses brackets which means memory access. MOV [R0], R1 tries to move to memory location incorrectly.

3. Final Answer:

   MOV R0, R1 -> Option C

4. Quick Check:

   Register names without # or [] = Register mode [OK]

Hint: Register mode uses register names directly, no # or brackets [OK]

Common Mistakes:

• Using # before register name
• Using brackets [] for register mode
• Confusing immediate and register syntax

3. Given the ARM instruction LDR R2, [R3, #4], what does this instruction do?

medium

A. Loads the immediate value 4 into R2

B. Loads the value from memory address in R3 plus 4 into R2

C. Moves the value from R3 to R2

D. Stores the value of R2 into memory address R3 plus 4

Solution

1. Step 1: Identify addressing mode in LDR instruction

   The syntax [R3, #4] means offset addressing mode: base register R3 plus immediate offset 4.

2. Step 2: Understand LDR operation

   LDR loads data from memory address calculated by R3 + 4 into register R2.

3. Final Answer:

   Loads the value from memory address in R3 plus 4 into R2 -> Option B

4. Quick Check:

   Offset mode loads from (R3 + 4) into R2 [OK]

Hint: Brackets with # offset means load from memory address plus offset [OK]

Common Mistakes:

• Thinking #4 is immediate load into R2
• Confusing load with store instruction
• Ignoring the offset in brackets

4. Identify the error in this ARM instruction using addressing modes: ADD R1, R2, #R3

medium

A. Incorrect use of # before register R3

B. Missing brackets around R3

C. Wrong destination register

D. Immediate value cannot be used with ADD

Solution

1. Step 1: Analyze the use of # in ARM instructions

   The # symbol is used only before immediate (constant) values, not registers.

2. Step 2: Check the instruction syntax

   Here #R3 is invalid because R3 is a register, not an immediate value. Correct syntax is ADD R1, R2, R3 without #.

3. Final Answer:

   Incorrect use of # before register R3 -> Option A

4. Quick Check:

   # only for constants, not registers [OK]

Hint: # is only for numbers, never before register names [OK]

Common Mistakes:

• Using # before register names
• Adding brackets unnecessarily
• Confusing immediate and register operands

5. You want to load a value from memory address calculated by adding 8 to the value in register R4, then add an immediate value 5 to it and store in R0. Which sequence of ARM instructions correctly uses addressing modes?

hard

A. LDR R1, [R4, R5]
ADD R0, R1, #8

B. LDR R0, [R4, #5]
ADD R0, R0, #8

C. LDR R0, [R4]
ADD R0, R0, R5

D. LDR R1, [R4, #8]
ADD R0, R1, #5

Solution

1. Step 1: Load from memory address R4 + 8

   Use offset addressing mode: LDR R1, [R4, #8] loads from address R4 + 8 into R1.

2. Step 2: Add immediate 5 to loaded value

   ADD R0, R1, #5 adds immediate 5 to R1 and stores result in R0.

3. Final Answer:

   LDR R1, [R4, #8] ADD R0, R1, #5 -> Option D

4. Quick Check:

   Offset load then immediate add = LDR R1, [R4, #8] ADD R0, R1, #5 [OK]

Hint: Load with offset first, then add immediate value [OK]

Common Mistakes:

• Mixing immediate and offset values incorrectly
• Using register instead of immediate for offset
• Loading directly into R0 then adding wrong offset