Recursive Fibonacci Implementation on ARM Cortex-M4: Infinite Loop Issue and Fixes

ARM Cortex-M4 Recursive Fibonacci Code Fails to Terminate

The core issue revolves around a recursive implementation of the Fibonacci sequence on an ARM Cortex-M4 processor, where the code fails to terminate after computing the first four Fibonacci numbers. Instead, it enters an infinite loop, continuously branching back to the recursive subroutine. The goal is to compute the first five Fibonacci numbers, store them in register R3, and then enter an endless loop (Stop B Stop). However, the code does not correctly manage the return flow from the recursive subroutine, leading to unintended behavior.

The provided assembly code attempts to emulate the following C code:

int fibbonacci(int n) {
  if(n == 0){
    return 0;
  } else if(n == 1) {
    return 1;
  } else {
    return (fibbonacci(n-1) + fibbonacci(n-2));
  }
}

The assembly implementation uses a recursive approach, leveraging the BL (Branch with Link) instruction to call the Sum subroutine. However, the code fails to properly handle the base cases and the return flow, resulting in an infinite loop. The primary issue lies in the mismanagement of the stack and the Link Register (LR), which is critical for recursive function calls in ARM assembly.

Stack and Link Register Mismanagement in Recursive Subroutine

The root cause of the infinite loop can be traced to two main issues: improper stack management and incorrect handling of the Link Register (LR). In ARM assembly, recursive functions rely heavily on the stack to store intermediate results and the return address. The Link Register (LR) holds the return address for subroutine calls, and its value must be preserved across recursive calls.

In the provided code, the Sum subroutine uses PUSH and POP instructions to save and restore registers. However, the stack operations are not correctly aligned with the recursive logic. Specifically:

1. Incorrect Stack Usage for Recursive Calls: The PUSH and POP instructions are used to save and restore registers, but the stack is not properly managed to handle multiple recursive calls. Each recursive call should save the current state (including the return address) and restore it upon returning. However, the code does not consistently preserve the LR across recursive calls, leading to incorrect return behavior.

2. Mismatch Between Push and Pop Operations: The POP {R1, R2} instruction is used to restore registers, but the corresponding PUSH operation does not match. This mismatch causes the stack to become unbalanced, leading to undefined behavior when returning from the recursive subroutine.

3. Base Case Handling: The base cases for the Fibonacci sequence (n = 0 and n = 1) are not correctly implemented in the assembly code. The done label attempts to handle these cases, but the logic is flawed, and the code does not properly return from the recursive calls.

4. Unnecessary Register Usage: The code uses register R4 as a counter, but this is commented out and not utilized effectively. This adds unnecessary complexity without contributing to the solution.

Correcting Stack Management and Implementing Base Cases

To resolve the infinite loop issue and ensure the code terminates correctly after computing the first five Fibonacci numbers, the following steps must be taken:

1. Proper Stack Management: Ensure that the stack is correctly managed across recursive calls. Each recursive call should save the current state, including the return address (LR), and restore it upon returning. This can be achieved by using PUSH {LR} at the beginning of the Sum subroutine and POP {LR} before returning.

2. Align Push and Pop Operations: Ensure that the PUSH and POP operations are correctly aligned. For example, if PUSH {R0, R1} is used, the corresponding POP operation should be POP {R0, R1}. This ensures that the stack remains balanced and the correct values are restored.

3. Implement Base Cases Correctly: The base cases for the Fibonacci sequence (n = 0 and n = 1) must be correctly implemented. This involves checking the value of n and returning the appropriate result without making further recursive calls.

4. Simplify Register Usage: Remove unnecessary register usage, such as the commented-out R4 counter, to simplify the code and reduce potential sources of error.

5. Termination Logic: Add logic to ensure that the code terminates after computing the required number of Fibonacci numbers. This can be achieved by decrementing a counter and branching to the Stop loop when the counter reaches zero.

Here is the corrected assembly code:

; Recursive implementation - Print Fibonacci sequence for first 5 numbers in R3
; 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
; R4 = counter

__main
    MOV   R0, #4          ; Initialize n = 4 (compute Fibonacci(4))
    BL    Sum             ; Call Sum subroutine
    B     Stop            ; Branch to Stop loop after computation

Sum
    PUSH  {LR}            ; Save return address
    CMP   R0, #1          ; Check if n == 1
    BEQ   done            ; If n == 1, branch to done
    CMP   R0, #0          ; Check if n == 0
    BEQ   done            ; If n == 0, branch to done

    SUBS  R0, R0, #1      ; Decrement n (n = n - 1)
    BL    Sum             ; Recursive call: Sum(n-1)
    POP   {LR}            ; Restore return address
    PUSH  {R0}            ; Save result of Sum(n-1)

    SUBS  R0, R0, #1      ; Decrement n (n = n - 2)
    BL    Sum             ; Recursive call: Sum(n-2)
    POP   {LR}            ; Restore return address
    POP   {R1}            ; Restore result of Sum(n-1)
    ADD   R0, R0, R1      ; Compute Sum(n-1) + Sum(n-2)
    MOV   R3, R0          ; Store result in R3
    PUSH  {R0}            ; Save result for next iteration
    BX    LR              ; Return from subroutine

done
    MOV   R0, #0          ; Base case: Fibonacci(0) = 0
    MOV   R3, R0          ; Store result in R3
    PUSH  {R0}            ; Save result for next iteration
    BX    LR              ; Return from subroutine

Stop
    B     Stop            ; Infinite loop to stop execution
    ALIGN
    END

Explanation of Fixes

1. Stack Management: The PUSH {LR} and POP {LR} instructions ensure that the return address is preserved across recursive calls. This prevents the infinite loop by ensuring that the subroutine returns to the correct location.

2. Base Case Handling: The done label correctly handles the base cases for n = 0 and n = 1. The code returns the appropriate result without making further recursive calls.

3. Simplified Register Usage: The unnecessary use of R4 as a counter has been removed, simplifying the code and reducing potential sources of error.

4. Termination Logic: The code now correctly terminates after computing the required number of Fibonacci numbers. The Stop loop is entered after the computation is complete.

By addressing these issues, the corrected code ensures that the recursive Fibonacci implementation on the ARM Cortex-M4 terminates correctly and produces the expected results.