Exception entry and exit sequence in ARM Architecture - Time & Space Complexity

Time Complexity: Exception entry and exit sequence

O(n)

Understanding Time Complexity

When the processor handles an exception, it runs a special sequence of steps to save its state and jump to the exception handler.

We want to understand how the time taken by this sequence changes as the system or input changes.

Scenario Under Consideration

Analyze the time complexity of the following ARM exception entry and exit sequence.

    SUB   SP, SP, #32       ; Make space on stack
    STMFD SP!, {R0-R3, LR} ; Save registers
    LDR   R0, =ExceptionHandler
    BX    R0               ; Branch to handler

    ; Exception exit sequence
    LDMFD SP!, {R0-R3, LR} ; Restore registers
    ADD   SP, SP, #32      ; Restore stack pointer
    BX    LR               ; Return from exception
    

This code saves some registers and stack space on exception entry, then restores them on exit.

Identify Repeating Operations

Look for repeated or costly steps in the sequence.

• Primary operation: Saving and restoring multiple registers using STMFD and LDMFD instructions.
• How many times: Each register saved/restored counts as one operation, done once per exception.

How Execution Grows With Input

The time depends on how many registers are saved and restored.

Input Size (number of registers)	Approx. Operations
4	10 (5 saved + 5 restored)
8	18 (9 saved + 9 restored)
16	34 (17 saved + 17 restored)

Pattern observation: The time grows linearly with the number of registers saved and restored.

Final Time Complexity

Time Complexity: O(n)

This means the time to enter and exit an exception grows directly with how many registers are saved and restored.

Common Mistake

[X] Wrong: "The exception entry time is always constant regardless of saved registers."

[OK] Correct: Saving more registers means more instructions run, so the time increases with the number of registers.

Interview Connect

Understanding how exception handling time grows helps you write efficient low-level code and reason about system responsiveness.

Self-Check

"What if the exception sequence saved only the minimum registers needed? How would that affect the time complexity?"

Practice

1. What is the main purpose of the exception entry sequence in ARM architecture?

easy

A. To increase the processor clock speed temporarily

B. To execute normal instructions without interruption

C. To save the current processor state and switch to exception mode

D. To reset the processor completely

Solution

1. Step 1: Understand what happens during exception entry

   When an exception occurs, the processor saves its current state to avoid losing information.

2. Step 2: Recognize the mode switch

   The processor switches to a special mode to handle the exception safely.

3. Final Answer:

   To save the current processor state and switch to exception mode -> Option C

4. Quick Check:

   Exception entry = Save state + switch mode [OK]

Hint: Exception entry always saves state and switches mode [OK]

Common Mistakes:

• Thinking exception entry resets the processor
• Confusing exception entry with normal instruction execution
• Assuming clock speed changes during exception

2. Which of the following correctly describes the first step in the exception exit sequence?

easy

A. Switch the processor to a special exception mode

B. Restore the saved processor state from the stack

C. Disable all interrupts permanently

D. Clear all registers to zero

Solution

1. Step 1: Identify the start of exception exit

   The processor begins exception exit by restoring the saved state to continue normal operation.

2. Step 2: Understand what is restored

   The saved registers and program counter are loaded back from the stack or special registers.

3. Final Answer:

   Restore the saved processor state from the stack -> Option B

4. Quick Check:

   Exception exit starts by restoring state [OK]

Hint: Exception exit begins by restoring saved state [OK]

Common Mistakes:

• Confusing mode switch with state restoration
• Thinking interrupts are disabled permanently
• Assuming registers are cleared during exit

3. Consider this simplified ARM exception entry sequence:

1. Save CPSR to SPSR
2. Save return address to LR
3. Switch to exception mode
4. Set PC to exception vector

What will be the value of PC after step 4 if the exception vector address is 0x00000010?

medium

A. Value of CPSR

B. 0x00000000

C. Value of LR

D. 0x00000010

Solution

1. Step 1: Understand the exception vector role

   The PC is set to the exception vector address to start executing the exception handler.

2. Step 2: Apply the given vector address

   The vector address given is 0x00000010, so PC will be set to this value.

3. Final Answer:

   0x00000010 -> Option D

4. Quick Check:

   PC after entry = exception vector address [OK]

Hint: PC points to exception vector after entry [OK]

Common Mistakes:

• Confusing PC with LR or CPSR values
• Assuming PC remains unchanged
• Mixing up saved registers with PC

4. A programmer notices that after an exception exit, the processor does not return to the original task but stays in exception mode. What is the most likely cause?

medium

A. The saved state was not restored correctly during exception exit

B. The exception entry sequence did not save the CPSR

C. The processor clock speed was changed during exception

D. The exception vector address was set incorrectly

Solution

1. Step 1: Analyze the problem

   If the processor stays in exception mode after exit, it means it did not restore the previous mode and state.

2. Step 2: Identify the cause

   Not restoring the saved state (including CPSR and PC) during exception exit causes the processor to remain in exception mode.

3. Final Answer:

   The saved state was not restored correctly during exception exit -> Option A

4. Quick Check:

   Incorrect state restore = stuck in exception mode [OK]

Hint: Restore saved state fully to exit exception mode [OK]

Common Mistakes:

• Blaming clock speed changes
• Confusing entry saving with exit restoring
• Assuming vector address affects exit mode

5. During an exception entry, the processor saves the CPSR to SPSR and the return address to LR. If the exception handler modifies the LR but forgets to restore it before exit, what will happen when the exception exit sequence runs?

hard

A. The processor will return to an incorrect address, causing unexpected behavior

B. The processor will reset automatically to fix the error

C. The exception handler will run again immediately

D. The processor will ignore the LR and continue normally

Solution

1. Step 1: Understand the role of LR in exception handling

   LR holds the return address to resume normal execution after the exception.

2. Step 2: Analyze the effect of modifying LR without restoring

   If LR is changed and not restored, the processor will jump to the wrong address on exit.

3. Step 3: Predict the outcome

   This causes unexpected behavior or crashes because the program flow is disrupted.

4. Final Answer:

   The processor will return to an incorrect address, causing unexpected behavior -> Option A

5. Quick Check:

   Unrestored LR = wrong return address [OK]

Hint: Always restore LR to return correctly after exception [OK]

Common Mistakes:

• Assuming processor resets automatically
• Thinking exception handler repeats immediately
• Believing LR can be ignored safely