IT block for conditional execution (Thumb-2) in ARM Architecture - Time & Space Complexity

Time Complexity: IT block for conditional execution (Thumb-2)

O(1)

Understanding Time Complexity

We want to understand how the time cost changes when using the IT block for conditional execution in Thumb-2 assembly.

Specifically, how does the number of instructions executed grow as conditions are checked?

Scenario Under Consideration

Analyze the time complexity of the following IT block code snippet.

ITTE EQ
MOV R0, #1
MOV R1, #2
MOV R0, #3
    

This code executes instructions conditionally based on the EQ (equal) flag using an IT block.

Identify Repeating Operations

In this snippet, there are no loops or recursion; the instructions execute conditionally.

• Primary operation: Conditional instruction execution within the IT block.
• How many times: Each instruction runs once per execution, but only if its condition matches.

How Execution Grows With Input

The number of instructions executed does not increase with input size because the IT block controls up to four instructions conditionally.

Input Size (n)	Approx. Operations
10	Up to 3 instructions
100	Up to 3 instructions
1000	Up to 3 instructions

Pattern observation: Execution cost stays constant regardless of input size.

Final Time Complexity

Time Complexity: O(1)

This means the time to execute the IT block does not grow with input size; it remains constant.

Common Mistake

[X] Wrong: "The IT block causes multiple instructions to run repeatedly as input grows."

[OK] Correct: The IT block only controls a fixed number of instructions executed once per run, so execution time does not increase with input size.

Interview Connect

Understanding how conditional execution blocks work helps you reason about efficient code paths and predict performance in embedded systems.

Self-Check

"What if the IT block controlled a loop of instructions instead? How would the time complexity change?"

Practice

1. What is the main purpose of the IT block in Thumb-2 ARM architecture?

easy

A. To execute a few instructions conditionally without using jumps

B. To perform arithmetic operations faster

C. To switch between ARM and Thumb modes

D. To handle interrupts automatically

Solution

1. Step 1: Understand the IT block function

   The IT block allows conditional execution of up to four instructions without branching.

2. Step 2: Compare with other options

   Options B, C, and D describe unrelated features: arithmetic speed, mode switching, and interrupts.

3. Final Answer:

   To execute a few instructions conditionally without using jumps -> Option A

4. Quick Check:

   IT block = conditional execution without jumps [OK]

Hint: IT block runs instructions conditionally without branch jumps [OK]

Common Mistakes:

• Confusing IT block with interrupt handling
• Thinking IT block speeds up arithmetic
• Assuming IT block switches CPU modes

2. Which of the following is the correct syntax to start an IT block in Thumb-2 assembly?

easy

A. THUMB IT EQ

B. IF EQ

C. IT EQ

D. COND EQ

Solution

1. Step 1: Recall IT block syntax

   The IT instruction is followed by a condition code like EQ (equal).

2. Step 2: Check options

   Only IT EQ uses the correct keyword 'IT' followed by the condition 'EQ'. Others are invalid syntax.

3. Final Answer:

   IT EQ -> Option C

4. Quick Check:

   IT + condition code = IT EQ [OK]

Hint: IT block starts with 'IT' plus condition code (e.g., EQ) [OK]

Common Mistakes:

• Using 'IF' instead of 'IT'
• Adding extra keywords like 'COND' or 'THUMB'
• Omitting the condition code after IT

3. Consider the following Thumb-2 code snippet:

IT NE
MOVNE R0, #1
MOVNE R1, #2
MOVNE R2, #3
MOVNE R3, #4

How many instructions will execute if the condition NE (not equal) is false?

medium

A. Only the last MOV instruction executes

B. All 4 MOV instructions execute

C. Only the first MOV instruction executes

D. None of the MOV instructions execute

Solution

1. Step 1: Understand IT NE block behavior

   The IT NE block applies the NE condition to up to 4 following instructions.

2. Step 2: Evaluate condition false case

   If NE is false, none of the MOVNE instructions execute because they depend on NE condition.

3. Final Answer:

   None of the MOV instructions execute -> Option D

4. Quick Check:

   Condition false means no instructions run [OK]

Hint: If condition false, IT block instructions skip execution [OK]

Common Mistakes:

• Assuming some instructions run despite condition false
• Confusing NE with EQ condition
• Thinking IT block always executes instructions

4. Identify the error in this Thumb-2 IT block usage:

IT EQ
MOVNE R0, #1
MOVNE R1, #2

medium

A. Condition codes in IT and instructions do not match

B. Too many instructions in IT block

C. MOV instructions cannot be conditional

D. IT block must be followed by exactly 4 instructions

Solution

1. Step 1: Check IT condition and instruction conditions

   The IT block is started with EQ condition, but instructions use NE condition.

2. Step 2: Understand condition mismatch impact

   Instructions must use the same condition as IT block or its allowed variations; here they differ, causing an error.

3. Final Answer:

   Condition codes in IT and instructions do not match -> Option A

4. Quick Check:

   IT EQ but instructions use MOVNE = mismatch [OK]

Hint: Instruction conditions must match IT block condition [OK]

Common Mistakes:

• Thinking IT block requires exactly 4 instructions
• Believing MOV cannot be conditional
• Ignoring condition code mismatch

5. You want to conditionally execute three instructions only if the zero flag is set (EQ). Which IT block suffix correctly represents this?

hard

A. ITTEE EQ

B. ITTE EQ

C. ITTT EQ

D. ITTE NE

Solution

1. Step 1: Understand IT block suffix letters

   Each letter after IT indicates if the following instructions use the same (T) or inverse (E) condition.

2. Step 2: Match suffix to three instructions

   For three instructions, suffix length is 3 letters. 'ITTE' means first two instructions use EQ (T), third uses inverse (E).

3. Step 3: Choose correct suffix for three instructions all EQ

   'ITTE' is valid for three instructions with last inverted; 'ITTT' is for four instructions; 'ITTEE' is for four instructions; 'ITTE NE' uses wrong condition.

4. Final Answer:

   ITTE EQ -> Option B

5. Quick Check:

   Three instructions with correct suffix = ITTE EQ [OK]

Hint: Suffix length = number of instructions; T = same, E = inverse condition [OK]

Common Mistakes:

• Using suffix length not matching instruction count
• Confusing T and E letters
• Applying wrong condition code after IT