Per la garbage collection dobbiamo sapere due cose:
- Quali aree di memoria sono state allocate?
- Data un'area di memoria, è raggiungibile?
Se nel tuo set di istruzioni S deve essere un valore letterale, allora tutti gli indirizzi di memoria sarebbero staticamente noti. Se S può anche leggere da ACC , allora hai puntatori senza restrizione e puoi scrivere in indirizzi di memoria arbitrari. Quindi neanche la tua VM ha un concetto di allocazione di memoria, né è possibile discutere di raggiungibilità.
È utile confrontare questo con altri sistemi.
C sa quali aree di memoria sono state allocate perché è un comportamento indefinito scrivere in indirizzi arbitrari - puoi accedere agli oggetti nello stack, puoi malloc (), oppure puoi usare le chiamate di sistema mmap () per creare un'area di memoria a disposizione. In particolare, malloc () / free () gestisce necessariamente informazioni che sono in gran parte paragonabili a un sistema GC.
La raggiungibilità in C è più complicata perché qualsiasi informazione sul tipo viene cancellata in fase di esecuzione: non si sa se una data parola di memoria debba essere un puntatore. Un sistema GC deve quindi essere prudente e assumere che qualsiasi cosa possa essere un puntatore. Tuttavia, è possibile accedere alla memoria senza comportamento non definito se si tiene un puntatore in tale area di memoria. Pertanto, un sistema GC per C non deve risolvere il problema di interruzione, a meno che non si stiano facendo cose davvero serie come la compressione manuale dei puntatori.
In un linguaggio progettato per GC, l'aritmetica del puntatore di solito non è consentita. Puoi solo puntare i puntatori, non incrementarli. L'unico caso speciale è rappresentato dagli array, che possono contenere metadati per consentire il controllo dei limiti di runtime. Poiché questo è più limitato, è più facile ragionare su tali indicatori e compiere un'analisi di raggiungibilità più sicura.
Molte implementazioni del linguaggio GC mantengono anche le informazioni sul tipo di runtime. Data una regione di memoria arbitraria che è stata correttamente allocata dalle regole di quel sistema, possiamo dire che tipo ha, quali membri ha, .... Un sistema GC può quindi essere esatto e non deve essere conservativo.
Se tali informazioni sono disponibili in fase di esecuzione, abbiamo anche altre opzioni per migliorare GC:
- Dato un grafico delle dipendenze tra le regioni di memoria, possiamo spostare una regione di memoria in una nuova posizione e aggiornare tutti i puntatori che puntano ad essa. Questo è utile per compattare i garbage collector: poiché impedisce la frammentazione della memoria, le allocazioni possono diventare molto più veloci.
- Se ogni area di memoria contiene metadati di tipo, è facile aggiungere anche metadati GC, ad es. per tracciare GC o per il conteggio dei riferimenti.
Sarebbe possibile adattare il set di istruzioni per rendere possibile un GC conservativo simile a C: basta introdurre istruzioni per allocare memoria, possibilmente memoria libera e accedere alla memoria con un offset variabile su un puntatore (saranno necessari due registri per quello). Se è un comportamento non definito eseguire aritmetica del puntatore arbitrario, è possibile implementare GC. Tuttavia, quel sistema non è sicuro per la memoria e potrebbe ancora essere utilizzato per accedere alla memoria non allocata.
Se vuoi fare meglio, dovrai taggare ogni cella di memoria con i metadati GC. Un flag a bit singolo per indicare se questa cella è un puntatore o un altro valore è sufficiente per eseguire un'analisi esatta della raggiungibilità.