Question

Below is a C function and a first attempt at translating it into equivalent ARM subroutine. However, while the ARM code assembles successfully, execution of it reveals that it regularly gets stuck within fact in what is apparently an infinite loop. Explain why and explain how you can repair the ARM code so that it returns correctly while preserving the recursive nature of the original C function.

int fact(int n) {   if (n == 0) {     return 1;   } else {     return n * fact(n - 1);   } } ARM code that needs to be fixed: fact    CMP R0, #0      ; if argument n is 0, return 1         MOVEQ R0, #1         MOVEQ PC, LR         MOV R3, R0      ; otherwise save argument n                          ;into R3         SUB R0, R0, #1  ; and perform recursive call                         ;on R3 - 1         BL fact         MUL R0, R3, R0  ; multiply returned value by n         MOV PC, LR      ; and return

Answer 1

The ARM code provided in here doesn't work as expected as it disregards the concept of Stack which is a crucial element when it comes to a recursive code. I am illustrating it with the flowchart of this factorial code below(The Register names are just for illustration purposes).

Let's look at your code step by step:

fact    CMP R0, #0      ; if argument n is 0, return 1
        MOVEQ R0, #1
        MOVEQ PC, LR
        MOV R3, R0      ; otherwise save argument n into R3
        SUB R0, R0, #1  ; and perform recursive call on R3 - 1

Till this point, your code does what it should as part of recursive iteration. However, comes here the fact that at the end of this iteration, the assembler would need to push the items into the stack and create room for another for next recursive call. Use stack pointer to decrement by 8 bytes or 2 words (that essentially grows the stack by 8 bytes)

ADD SP, SP, #-8 ;

Use the first word to save the R14 register's content(in ARM, we call it LR) and second to save R3.

STR LR, [SP,#4]

STR R3, [SP]

Now, we are good to proceed for next recursive call. So, Branch and link to the method name "fact".

        BL fact

Post this, we will have to load with immediate Offset on R3. Use LDR for the same. Also, we are good to proceed for the multiplication part.

LDR R3, [SP]
        MUL R0, R3, R0  ; multiply returned value by n

Let's do the reverse of what we did in the last-to-last step. This is important because we need to free up space that gets deallocated.

LDR LR, [SP,#4]

ADD SP, SP,#8
     MOV PC, LR      ; and return

Do let me know if any step is not clear enough and I will be glad to rephrase or re-try to assist.

Thanks.