Lo stack è una struttura dati dinamica della memoria. Lo stack è gestito secondo una politica Last In First Out (LIFO, letteralmente: ultimo ad entrare primo ad uscire).
Operazioni dello stack:
- PUSH sullo stack, aggiunge un elemento in cima allo stack
- POP dallo stack, rimuove un elemento dalla cima dello stack
La cima dello stack è identificata dallo Stack Pointer (SP).
Lo stack è rappresentato come un pila. L'idea di utilizzare frasi come mettere in cima e togliere dalla cima fanno pensare ad una pila che cresce verso l'alto, la convenzione utilizzata da RISC-V per lo stack è del tipo grow-down, ovvero cresce verso il basso. Quindi nel caso di RISC-V lo stack è una pila la cui cima punta verso il basso.
Lo stack parte da indirizzi di memoria alti e cresce verso indirizzi di memoria bassi.
Lo Stack Pointer (SP) contiene l'indirizzo dell'ultima cella di memoria occupata nello stack.
Il valore di SP è salvato nel registro x2 chiamato anche sp.
PUSH
- decrementa SP
- scrive in nel punto della memoria a cui SP punta
addi sp, sp, -8
sd x20, 0(sp)
POP
- legge dal punto della memoria a cui SP punta
- incrementa SP
ld x20, 0(sp)
addi sp, sp, 8
Nell'esempio precedente sulla procedura somma:
int somma(int x, int y) {
int rst;
rst = x + y + 2;
return rst;
}
...
f = f + 1;
risultato = somma(f,g);
...
int somma(int x, int y) {
int rst;
rst = x + y + 2;
return rst;
}
...
f = f + 1;
risultato = somma(f,g);
...
Posti: x = x10, y = x11, rst = x20, f = x6
SOMMA:
add x5, x10, x11
addi x20, x5, 2
jalr x0, 0(x1)
...
addi x6, x6, 1
...
jal SOMMA
SOMMA:
add x5, x10, x11
addi x20, x5, 2
jalr x0, 0(x1)
...
addi x6, x6, 1
...
jal SOMMA
int somma(int x, int y) {
int rst;
rst = x + y + 2;
return rst;
}
...
f = f + 1;
risultato = somma(f,g);
...
Posti: x = x10, y = x11, rst = x20, f = x6
SOMMA:
add x5, x10, x11
addi x20, x5, 2
jalr x0, 0(x1)
...
addi x6, x6, 1
...
jal SOMMA
=== end-multi-column
C'era il problema di x5 che poteva essere stato utilizzato dal chiamante, la cui sovrascrittura da parte della procedura SOMMA, avrebbe portato alla perdita del dato per la procedura chiamante. La soluzione come abbiamo visto in sovrascrittura dei registri è quella di salvare il contenuto di x5 in memoria prima di utilizzarlo, per poi ripristinarlo una volta finito.
Il codice in RISC-V diventa:
SOMMA:
# update
addi sp, sp, -16
sd x5, 0(sp)
sd x20, 8(sp)
# end update
add x5, x10, x11
addi x20, x5, 2
addi x10, x20, 0
#update
ld x5, 0(sp)
ld x20, 8(sp)
addi sp, sp, 16
jalr x0, 0(x1)
# end update
...
addi x6, x6, 1
...
jal SOMMA
Quando la procedura viene chiamata lo stato dello stack è il seguente:
Quando vengono eseguite il primo blocco di update:
addi sp, sp, -16
sd x5, 0(sp)
sd x20, 8(sp)
Lo stack cambia:
Viene fatta una PUSH per salvare il contenuto di x5 e x20.
Una volta salvati i valori di quei registri sullo stack, si opera con essi:
add x5, x10, x11
addi x20, x5, 2
addi x10, x20, 0
In x5, viene fatta la somma tra x10 e x11 (i parametri della procedura).
Dopo di che:
ld x5, 0(sp)
ld x20, 8(sp)
addi sp, sp, 16
jalr x0, 0(x1)
Vengo caricati dalla memoria i vecchi valori di x5 e x20 localizzandoli nello stack.
Viene ripristinato il valore dello stack pointer (incrementando il valore degli indirizzi).
Viene salvato il valore di ritorno in x1 (con jalr x0, 0(x1)).
Ad ogni esecuzione di procedura corrisponde un blocco di memoria all'interno dello stack che viene chiamato record di attivazione o frame. Quando viene richiamata la funzione F, viene aggiunto un frame allo stack. Quando la funzione F termina, il corrispondente frame viene cancellato.
A questo punto siamo in grado di dare un nome ai registri e siamo in grado di distinguere quali sono i loro compiti specifici:
Nella chiamata a procedura sopra abbiamo visto che la procedura chiamata ha eseguito il salvataggio di alcuni registri per evitare di perdere il loro contenuto che poteva essere utile alla procedura chiamante. Il punto è che questa è solo una convenzione. In RISC-V, gli addetti al salvataggio dei registri sono le procedure chiamate, il motivo di questa scelta è ridurre al minimo i salvataggi dei registri, si verificano due scenari:
- la funzione chiamante sa quali registri sono importanti per sé, prima di effettuare la chiamata li salva, viene poi chiamata la procedura.
- la funzione chiamata sa quali registri andrà a modificare e, una volta chiamata, salva il contenuto dei registri che userà, ripristinandoli prima di ritornare dei valori.
Sono state stabilite delle convenzioni:
- i registri
x10-x17(a0-a7),x5-x7ex28-x31(t0-t6) possono essere modificati dal chiamato senza nessun meccanismo di ripristino, il chiamante se necessario dovrà salvare i valori dei registri prima dell'invocazione della procedura - i registri
x1(ra),x2(sp),x3(gp),x4(tp),x8(fp/s0),x9,x18-x27(s1-s11) se modificati devono essere salvati e poi ripristinati prima del ritorno al chiamante, il chiamante non è tenuto al loro salvataggio e ripristino.
Le fasi di invocazione di una procedura...
| Chiamante | Chiamata |
|---|---|
| 1. Pre-chiamata | |
| 2. Invocazione della procedura | |
| 3. Prologo della procedura chiamata | |
| 4. Corpo della procedura chiamata | |
| 5. Epilogo della procedura chiamata | |
| 6. Valore di ritorno alla procedura chiamata | |
| 7. Post-chiamata |
Nella fase 1:
- avviene l'eventuale salvataggio dei registri, per convenzione, come detto prima, si assume che i registri
x10-x17(a0-a7),x5-x7ex28-x31(t0-t6) possono essere sovrascritti dalla procedura chiamata, se si è a conoscenza del fatto che dopo la chiamata a procedura tali registri verranno riutilizzati è necessario salvarli nello stack, altrimenti non è necessario. - avviene la preparazione degli argomenti della funzione, i primi 8 argomenti vanno posti nei registri
x10-x17(a0-a7), eventuali argomenti extra vanno salvati nello stack (EXTRA_ARGS) così che si trovino subito sopra il frame della funzione chiamata.
Nella fase 2 si invoca la procedura: jal NOME_PROCEDURA
Nella fase 3: prologo procedura chiamata
- avviene l'eventuale allocazione del call-frame sullo stack (aggiornare
sp)- salvataggio di
x1(ra) nel caso in cui la procedura non sia una foglia - salvataggio di
x8(fp), solo se utilizzato all'interno della procedura - salvataggio di
x9,x18-x27(s1-s11) se utilizzati all'interno della procedura (il chiamante vuole ritrovarli intatti) - salvataggio degli argomenti
x10-x17(a0-a7) solo se la funzione li riuserà successivamente a ulteriori chiamate a procedura
- salvataggio di
- eventuale inizializzazione di
fp: punta al nuovo call-frame
Nella fase 4 si scrive il corpo della procedura chiamata
Nella fase 5: epiologo della procedura chiamata
- Se deve essere restituito un valore dalla funzione, esso viene posto in
x10(ex11) ovveroa0-a1 - I registri salvati devono essere ripristinati
x9,x18-x27(s1-s11)x1(ra)x8(fp)
- Notare che
spdeve essere solo aumentato dell'opportuno offset (lo stesso sottratto in fase 3)
Nella fase 6 si ritorna il valore al chiamante con jalr x0, 0(x1)
Nella fase 7 viene eventualmente utilizzato il valore ritornato dalla procedura chiamata e si ripristinano i valori dei registri x10-x17 (a0-a7), x5-x7 e x28-x31 (t0-t6) eventualmente salvati.
Come abbiamo già detto una viene chiamata una procedura viene allocato per la procedura invocata un record di attivazione o frame.
Se utilizzato il registro fp (frame pointer) viene inizializzato al valore di sp all'inizio della chiamata. Il frame pointer consente di avere un riferimento alle variabili locali che non muta con l'esecuzione della procedura. Se lo stack non contiene varaibili locali alla procedura, il compilatore risparmia tempo di esecuzione evitando di impostare e ripristinare il frame.
Nell'immagine è presentata una visualizzazione d'insieme dei passi da effettuare per effettuare una corretta chiamata ad una procedura.