ASM [MIPS] Ricorsione: concetti e convenzioni

[Ov3rlord]

Salve ragazzi, premetto che conosco la sintassi del linguaggio macchina MIPS, che da qui in poi chiamerò mips.
Avendo fin ora scritto solo funzioni iterative (per lo più su array o alberi binari definiti come dati statici), sono alle prese con la ricorsione. Capite che in un linguaggio a basso livello essa può essere particolarmente rompiscatole, ed è per questo che chiedo il vostro aiuto:
Ho deciso di esercitarmi con la ricorsione in mips utilizzando Mars 4.5 come simulatore, ma mi sono accorto che sia le convenzioni di scrittura dei registri (usare gli $s al posto dei $t) sia i ragionamenti per "abbozzare" il programma (con l'induzione) sono diversi. Chiedo a qualcuno di voi di illuminarmi un po' sulla ricorsione, di dirmi perlomeno cosa c'è da sapere per scrivere ricorsivamente in mips, come si ragiona ricorsivamente in mips (per esempio, lo stack pointer, come diavolo funziona? Perchè lo si usa nella ricorsione?).
Generalmente: vi chiedo umilmente una panoramica generale sulla ricorsione in mips, per poter iniziare ad esercitarmi.
Grazie in anticipo.

 

[St3ve]

Per convenzione le subroutine:

1. Sono viste come black box: sai cosa prendono in input (a0-a3), sai cosa ritornano in output (v0,v1), ma non sai cosa fanno al loro interno. Immagina che qualcuno possa prendere la tua subroutine e reimplementarla a suo piacimento.
2. Possono modificare i registri temporanei. Nel momento in cui usi chiami una subroutine devi assumere che il valore dei registri temporanei sia diventato spazzatura. Per via del punto precedente non ha importanza se nella tua implementazione non succede, lo devi comunque dare per assunto.
3. Preservano il valore dei registri saved. Nel caso vuoi far uso dei registri saved nella tua subroutine, devi ricordarti di pushare il valore precedente nello stack e recuperarlo prima di uscire dalla subroutine. In caso chiamano altre funzioni, devi ricordarti di salvare e ricaricare il return address (ra).
   
4. Non modificano lo stack. Nel caso devi pushare qualcosa sullo stack, lo abbassi (lo stack cresce verso il basso), salvi quello che devi salvare e lo rialzi. Se la dimensione dello stack è da determinare a runtime puoi far uso del registro $fp ($s8) per calcolare l'offset, ma il più delle volte non ti servirà.

Le funzioni ricorsive le possiamo spezzare in 4 fasi:

• prologo: abbassi lo stack, salvi il return address (è necessario pusharlo sullo stack) e salvi tutti i registri saved che andrai ad utilizzare;
• if caso base: se sei nel caso base, stoppi la ricorsione e ritorni il valore del caso base;
• else passo induttivo: se non sei nel caso base, calcoli quello che devi calcolare e richiami la stessa funzione su un caso più semplice;
• epilogo: rialzi lo stack, recuperi il return address precedente e recuperi il vecchio contenuto dei registri saved che hai utilizzato.

Ad esempio, questa è una possibile implementazione della sequenza di fibonacci (chiaramente ottimizzabile):

# input: a0 -> n
# output v0 -> fib(n)
fib:
    # PROLOGO
    addi $sp, $sp, -12
    sw $ra, 0($sp)
    sw $s0, 4($sp)
    sw $s1, 8($sp)

    # CASO BASE
    slti $t0, $a0, 2
    beq $t0, $zero, fib_else  # if (n < 2) {
    addi $v0, $zero, 1        #     return 1
    j fib_end                 # }
                              #
    # PASSO INDUTTIVO         #
    fib_else:                 # else {
        addi $s0, $a0, -1     #     s0 = n-1
        addi $s1, $a0, -2     #     s1 = n-2
                              #
        move $a0, $s0         #
        jal fib               #
        move $s0, $v0         #     s0 = fib(n-1)
                              #
        move $a0, $s1         #
        jal fib               #
        move $s1, $v0         #     s1 = fib(n-2)
                              #
        add $v0, $s0, $s1     #     v0 = fib(n-1) + fib(n-2)
                              # }

    # EPILOGO
    fib_end:
    lw $ra, 0($sp)
    lw $s0, 4($sp)
    lw $s1, 8($sp)
    addi $sp, $sp, 12

    jr $ra

 

[Ov3rlord]

Ciao!! Grazie per avermi risposto!
Non ho ben capito cosa intendi con la prima parte, con la seconda però ho iniziato ad avere qualche lume di speranza. Praticamente questa cosa del salvare i registri nello stack, giocando con lo stack pointer, serve per preservare i valori dei miei registri tra una parte di codice e un'altra? O sbaglio?

rialzi lo stack, recuperi il return address precedente e recuperi il vecchio contenuto dei registri saved che hai utilizzato.

Inoltre, rimettere lo stack a posto quando ho finito è una convenzione o c'è qualche tipo di conflitto se non lo faccio?
Sto iniziando a capire qualcosa, anche se sto iniziando ad esercitarmi con gli alberi e ancora non entro nell'ottica.

 

[St3ve]

Non ho ben capito cosa intendi con la prima parte

Intendi il punto 1? Prendiamo ad esempio la subroutine fib che ti ho scritto. Come puoi vedere non utilizzo nessun registro temporaneo, non ne ho bisogno. Se nel main uso $t0 e richiamo quella subroutine, il valore di $t0 non cambierà e potrei utilizzarlo senza assegnargli un nuovo valore (so quello che contiene). In pratica posso farlo, ma se voglio rispettare le convenzioni devo assumere che $t0 sia cambiato (anche se non è vero).
Perché devo assumere che $t0 sia cambiato? Perché tu potresti reimplementare la subroutine fib in modo più efficiente, nel tuo codice potresti utilizzare il registro $t0 e il mio main deve funzionare senza alcuna modifica. È uno dei vantaggi che si ha se si rispettano le convenzioni.

Praticamente questa cosa del salvare i registri nello stack, giocando con lo stack pointer, serve per preservare i valori dei miei registri tra una parte di codice e un'altra? O sbaglio?

Generalmente i registri sono pochissimi e nelle tue funzioni hai bisogno di tante variabili. Invece di creare CPU con tanti registri, si utilizza una memoria centrale (RAM) in grado di memorizzare molti dati. Ti servono tante variabili? Le salvi nella memoria centrale e li ricarichi nei registri della CPU quando li devi effettivamente utilizzare.

Inoltre, rimettere lo stack a posto quando ho finito è una convenzione o c'è qualche tipo di conflitto se non lo faccio?

La memoria centrale è grande, ma non è infinita. Quando hai terminato di utilizzare un dato devi ricordarti che quella porzione di RAM è utilizzabile per altri dati. Quindi dobbiamo:

• ricordarci quali sono le porzioni di RAM occupate;
• sapere quale porzione di RAM è libera;
• ricordarci di liberare la porzione di RAM occupata dalle variabili che non ci servono più.

Non è semplice, quindi si cerca di automatizzare il tutto ed ecco che entra in gioco lo stack. Lo stack è un area della memoria che funziona con un meccanismo LIFO (Last In First Out): il primo dato inserito è l'ultimo che verrà eliminato.
Come faccio a sapere quale aree di memoria sono occupate e quali no? Tutto quello che sta sopra allo stack pointer è occupato, tutto quello che sta sotto è libero.
Come evito di utilizzare troppa RAM? Le allocazioni sullo stack avvengono all'entrata di una funzione (prologo), le deallocazioni avvengono all'uscita di una funzione (epilogo).

Questo sistema di gestione della memoria (stack) non è prerogativa dell'assembly MIPS. In ogni altro linguaggio di programmazione che stai utilizzando, le variabili sono gestite con questo sistema. Quando questo sistema non è applicabile (eg. nel prologo non sono a conoscenza della dimensione dei dati che andrò ad utilizzare) si utilizza un'altra area di memoria chiamata heap, ma questa è un'altra storia.

 

[Ov3rlord]

Perfetto, quindi lo stack è come un archivio. Ci sono, grazie mille.
Ora, se volessi per esempio calcolare l'altezza di un albero binario, ricorsivamente, potrei spezzare la mia funzione nei tuoi 4 punti? Ho provato a scrivere codice, ma non sta nè in cielo nè in terra.
Non capisco ancora le logiche. Ti chiedo troppo se ti dico di spiegarmi come scrivere una funzione del genere?

EDIT:
nel programma da te postato qualche messaggi fa, inizializzi lo stack a -12. Perchè quella dimensione? Come faccio a sapere a quanto ammonta e quanti registri ci devo salvare?

 

[St3ve]

nel programma da te postato qualche messaggi fa, inizializzi lo stack a -12. Perchè quella dimensione? Come faccio a sapere a quanto ammonta e quanti registri ci devo salvare?

Ho assunto che il processore MIPS fosse a 32 bit, quindi ogni registro è formato da 32/8=4 byte. Salvo 3 registri ($s0, $s1 e $ra) quindi riservo 3*4=12 byte nello stack.

Perfetto, quindi lo stack è come un archivio.

Stai over-semplificando. La memoria centrale è il posto in cui salvi la roba, lo stack è la regione della memoria centrale dove le allocazioni sono gestite seguendo il modello LIFO. In generale "stack" è tutto ciò che segue questo modello LIFO.

Ora, se volessi per esempio calcolare l'altezza di un albero binario, ricorsivamente, potrei spezzare la mia funzione nei tuoi 4 punti? Ho provato a scrivere codice, ma non sta nè in cielo nè in terra.
Non capisco ancora le logiche. Ti chiedo troppo se ti dico di spiegarmi come scrivere una funzione del genere?

Dovrei sapere in che modo stai gestendo i dati. Come lo stai rappresentando questo albero binario? Fammi vedere il codice.
In ogni caso, questo è il codice (ad alto livello) che devi convertire in assembly:

procedure max(a, b)
    if (a > b)
        return a
    else
        return b


procedure height(Tree)
    if (Tree == null)
        rertun -1
    else
        left = 1 + height(Tree.lchild)
        right = 1 + height(Tree.rchild)
        return max(left, right)

 

[Ov3rlord]

Mi hanno inviato questo codice

.text
    la $a0, roota
   
    jal equals
   
    exit:
        li $v0, 10
        syscall
   
    #########
   
    equals:
        addi $sp, $sp, -8
       
        sw $ra, 0($sp)
        sw $a0, 4($sp)
        # left node
        lw $a0, 4($a0)
       
        beq $a0, 0, left
        jal equals
       
    left:
        # if empty get left node
        # from the stack, then
        # get right node
        lw $a0, 4($sp)
        lw $a0, 8($a0)
       
        beq $a0, 0, right
        jal equals
       
    right:
        # got a leaf, go back
        lw $ra, 0($sp)
        addi $sp, $sp, 8
        jr $ra

Dicendo che fa la bfs. Ma non essendo commentato non riesco a capire quello che fa.

 

[St3ve]

A prima vista mi sembra che faccia DFS, non BFS, e a dire il vero non mi trovo d'accordo con quei pochi commenti che ci sono. Magari sto capendo male io.
Comunque se non riesci a fare sta roba prova con cose più semplici. Non so quanto sei pratico di programmazione e non voglio darti il codice bello e pronto.

Sai come si implementano gli alberi binari in un linguaggio con i puntatori? Nel codice che hai postato sta visitando l'albero utilizzando lo stesso sistema. Se non sai implementare un albero binario in MIPS, non ha senso chiedersi quale sia la sua altezza.