Program counter (R15/PC) in ARM Architecture - Time & Space Complexity

Time Complexity: Program counter (R15/PC)

O(n)

Understanding Time Complexity

We want to understand how the program counter (R15/PC) affects the speed of instruction execution in ARM architecture.

Specifically, how does the program counter's behavior influence the number of steps the processor takes as instructions run?

Scenario Under Consideration

Analyze the time complexity of the following ARM assembly snippet using the program counter.

    MOV R0, #0        ; Initialize counter
    LOOP:
      ADD R0, R0, #1  ; Increment counter
      CMP R0, #10     ; Compare counter to 10
      BNE LOOP        ; Branch if not equal
    

This code uses the program counter to loop until R0 reaches 10.

Identify Repeating Operations

Look for repeated instructions controlled by the program counter.

• Primary operation: The loop increments R0 and checks its value.
• How many times: The loop runs 10 times, controlled by the program counter updating the instruction address.

How Execution Grows With Input

The number of loop iterations grows directly with the target count.

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

Pattern observation: The execution steps increase linearly as the input number grows.

Final Time Complexity

Time Complexity: O(n)

This means the number of instructions executed grows directly in proportion to the input size.

Common Mistake

[X] Wrong: "The program counter makes the loop run instantly regardless of input size."

[OK] Correct: The program counter only points to the next instruction; it does not speed up how many instructions run. More iterations mean more instructions executed.

Interview Connect

Understanding how the program counter controls instruction flow helps you explain how loops and branches affect performance in real processors.

Self-Check

"What if the loop used a conditional branch that sometimes skips multiple instructions? How would that affect the time complexity?"

Practice

1. What is the primary role of the Program Counter (PC) in ARM architecture?

easy

A. It holds the address of the next instruction to execute.

B. It stores the result of arithmetic operations.

C. It manages input/output operations.

D. It controls the power management of the processor.

Solution

1. Step 1: Understand the function of PC

   The Program Counter (PC) is a special register that keeps track of the address of the next instruction to be executed in the program.

2. Step 2: Compare with other options

   Other options describe functions of different registers or components, not the PC.

3. Final Answer:

   It holds the address of the next instruction to execute. -> Option A

4. Quick Check:

   PC = Next instruction address [OK]

Hint: PC always points to the next instruction address [OK]

Common Mistakes:

• Confusing PC with general-purpose registers
• Thinking PC stores data instead of addresses
• Mixing PC role with I/O or power control

2. Which register number corresponds to the Program Counter (PC) in ARM processors?

easy

A. R14

B. R13

C. R15

D. R12

Solution

1. Step 1: Recall ARM register naming

   In ARM architecture, the Program Counter is known as register R15.

2. Step 2: Verify other register roles

   R14 is the Link Register, R13 is the Stack Pointer, and R12 is a general-purpose register.

3. Final Answer:

   R15 -> Option C

4. Quick Check:

   PC = R15 [OK]

Hint: PC is always R15 in ARM [OK]

Common Mistakes:

• Confusing PC with Link Register (R14)
• Mixing up Stack Pointer (R13) with PC
• Assuming PC is a general-purpose register

3. Consider this ARM assembly snippet:

ADD R0, R0, #4
MOV PC, R0

What happens when the MOV PC, R0 instruction executes?

medium

A. The program jumps to the address stored in R0.

B. The value in R0 is added to the PC without changing flow.

C. The PC is set to zero, causing a reset.

D. The instruction causes a syntax error.

Solution

1. Step 1: Understand MOV PC, R0

   Moving a value into PC changes the program flow to the address in R0, causing a jump.

2. Step 2: Analyze the ADD instruction

   ADD R0, R0, #4 increments R0 by 4, so PC will jump to this new address.

3. Final Answer:

   The program jumps to the address stored in R0. -> Option A

4. Quick Check:

   Setting PC = R0 causes jump [OK]

Hint: MOV to PC changes program flow to that address [OK]

Common Mistakes:

• Thinking MOV PC,R0 just copies value without jump
• Assuming PC increments automatically ignoring MOV
• Believing MOV PC,R0 causes error

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

MOV PC, #1000

What is wrong with this instruction?

medium

A. The immediate value #1000 is too large for MOV instruction.

B. You cannot move an immediate value directly into PC.

C. PC cannot be used as a destination register.

D. MOV instruction requires two registers, not immediate values.

Solution

1. Step 1: Understand MOV limitations with PC

   In ARM, you cannot move an immediate value directly into PC; it must come from a register.

2. Step 2: Check other options

   PC can be destination, MOV can use immediate but not directly to PC, and #1000 size is not the main issue here.

3. Final Answer:

   You cannot move an immediate value directly into PC. -> Option B

4. Quick Check:

   Immediate to PC invalid [OK]

Hint: MOV immediate to PC is invalid; use register first [OK]

Common Mistakes:

• Trying to load PC directly with immediate values
• Confusing PC with general-purpose registers
• Assuming MOV always accepts immediate to any register

5. In ARM assembly, how can you implement a conditional jump to address stored in R4 only if R1 equals zero, using the Program Counter (PC)?

hard

A. Use JMP R4 if R1 equals zero.

B. Use BEQ R4 to jump if R1 is zero.

C. Use MOV PC, R4 unconditionally after checking R1.

D. Use CMP R1, #0 followed by MOVEQ PC, R4.

Solution

1. Step 1: Compare R1 with zero

   The CMP R1, #0 instruction sets condition flags based on R1's value.

2. Step 2: Use conditional move to PC

   MOVEQ PC, R4 moves R4 into PC only if the zero flag is set (R1 == 0), causing a conditional jump.

3. Final Answer:

   Use CMP R1, #0 followed by MOVEQ PC, R4. -> Option D

4. Quick Check:

   Conditional MOV to PC enables jump [OK]

Hint: Use CMP then conditional MOV to PC for jumps [OK]

Common Mistakes:

• Using BEQ with a register operand (invalid syntax)
• Unconditionally moving PC ignoring condition
• Using JMP which is not an ARM instruction