Esercizio 34funzione ricorsiva in assembly ARM, Fibonacci

Registri e salvataggi

• Argomento e risultato in r0.
• fib(n) deve richiamare se stessa due volte e dopo la prima chiamata servono ancora due valori: $n$ (per calcolare $n-2$) e il risultato $\text{fib}(n-1)$. BL distrugge r0–r3 e lr, quindi questi due valori vanno in registri callee-saved: r4 per $n$ e r5 per $\text{fib}(n-1)$.
• Una funzione che usa r4, r5 li deve salvare all'ingresso e ripristinare all'uscita; e siccome contiene BL, deve anche salvare lr (altrimenti BL sovrascrive l'indirizzo di ritorno).
• PUSH {r4, r5, r6, lr} salva quattro registri: 16 byte. Si aggiunge r6 solo perché con tre registri (12 byte) sp non sarebbe multiplo di 8, e la convenzione richiede sp allineato a 8 byte alle chiamate.
• Il caso base ($n < 2$) non tocca il resto: ritorna subito con BX lr, senza PUSH: la funzione foglia più economica.

fib:    CMP   r0, #2
        BLT   base              @ n < 2: fib(n) = n (r0 resta n)
        PUSH  {r4, r5, r6, lr}  @ r6 solo per mantenere sp allineato a 8
        MOV   r4, r0            @ r4 = n
        SUB   r0, r4, #1
        BL    fib               @ r0 = fib(n-1)
        MOV   r5, r0            @ r5 = fib(n-1)
        SUB   r0, r4, #2
        BL    fib               @ r0 = fib(n-2)
        ADD   r0, r0, r5        @ fib(n-1) + fib(n-2)
        POP   {r4, r5, r6, pc}  @ ripristina e ritorna (pc <- lr salvato)
base:   BX    lr

BLT è un confronto con segno: per $n < 0$ ritorna direttamente $n$ (in C si assume $n \ge 0$). POP {..., pc} carica nel pc il valore di lr salvato dalla PUSH: equivale a un ritorno.

(a) Lo stack durante fib(3)

Partendo da sp = 0x8000 (lo stack cresce verso indirizzi minori; PUSH sottrae 16 e scrive r4 all'indirizzo più basso, poi r5, r6, lr). Chiamate nell'ordine, con il valore di sp all'ingresso di ciascuna:

Stato dello stack al punto più profondo (dentro fib(1) chiamata da fib(2)):

Dopo il ritorno di fib(3), sp = 0x8000 come all'ingresso e r4, r5, r6 valgono come prima.

(b) Numero di chiamate e stack massimo

• Chiamate totali: $C(n) = 1 + C(n-1) + C(n-2)$ con $C(0) = C(1) = 1$, quindi $C(n) = 2\,\text{fib}(n+1) - 1$. Per $n = 5$: 15 chiamate (per $n = 0, \dots, 5$ i valori sono 1, 1, 3, 5, 9, 15). Il tempo cresce come $\text{fib}(n)$, cioè esponenzialmente ($\approx 1{,}618^n$): fib(12) fa 465 chiamate.
• Stack: la catena di chiamate annidate più lunga è $\text{fib}(5) \to \text{fib}(4) \to \text{fib}(3) \to \text{fib}(2)$ (le prime quattro hanno un PUSH; fib(1) ritorna senza): 4 record da 16 byte = 64 byte. In generale $16\,(n-1)$ byte per $n \ge 2$: lo spazio sullo stack cresce linearmente con $n$ anche se il tempo è esponenziale.

(c) Registri preservati

All'uscita r4, r5, r6 hanno il valore che avevano all'ingresso, grazie al PUSH/POP simmetrico, e sp è tornato al valore iniziale. Una PUSH e una POP con registri diversi (o in numero diverso) o una POP mancante su un solo ramo lascerebbero lo stack sbilanciato e il programma tornerebbe a un indirizzo sbagliato.

Verifica

Il codice è stato assemblato ed eseguito in un emulatore ARM: fib(n) per $n$ da 0 a 12 restituisce i numeri di Fibonacci attesi ($0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144$); a ogni prova sp torna a 0x8000 e r4, r5, r6 (impostati a valori noti prima della chiamata) sono invariati; i conteggi delle chiamate e dello stack massimo nella tabella sono quelli misurati.

Errori comuni

• Non salvare lr: la seconda BL sovrascrive l'indirizzo di ritorno e POP {..., pc} o BX lr tornano nel posto sbagliato (ciclo infinito).
• Tenere $n$ o $\text{fib}(n-1)$ in r0–r3: BL e la funzione chiamata li modificano. Servono registri callee-saved.
• Usare r4/r5 senza salvarli: si corrompono i valori del chiamante (che a sua volta li usa).
• PUSH e POP con insiemi diversi di registri.
• Mettere il PUSH prima del test del caso base: il caso base costerebbe inutilmente un frame (e per $n < 2$ sarebbe la maggior parte delle chiamate).
• Scordare l'allineamento dello stack a 8 byte: con tre soli registri salvati sp non è multiplo di 8.