Come trovare le root gc in una macchina stack?

Question

Sto scrivendo un compilatore per una macchina stack piuttosto standard. Ora voglio aggiungere un garbage collector. Posso vedere che potrei generare una sorta di 'pila di mappe' per sapere quali variabili sono root gc in ogni record di attivazione. Tuttavia, non ho idea di come gestire i valori intermedi inseriti nello stack durante l'esecuzione. Il linguaggio che sto compilando è di tipo Pascal, quindi non ho bisogno e non voglio usare i tag per identificare i puntatori da altri tipi di dati.

Gradirei eventuali suggerimenti/indicazioni su come

1. Trova radici GC nella pila in qualsiasi punto nel tempo (ad esempio, come identificare quale dei valori intermedi che sono stati spinti nella pila sono radici gc).
2. usuali codifica queste informazioni (vale a dire, come generare e codificare 'mappe pila')

ringrazio molto! Nicolas

Answer 1

Una soluzione semplice consiste nel memorizzare esplicitamente il tipo di ciascuna voce di stack. Quindi non hai bisogno di una mappa dello stack; se il tipo è "riferimento", la voce è una radice GC. Questo approccio è particolarmente utile per il debug, perché è possibile visualizzare facilmente i contenuti (tipizzati) dello stack.

Se si desidera utilizzare le mappe dello stack, una soluzione semplice consiste nel generare una mappa dello stack per ogni istruzione. Lo fai tenendo traccia del contenuto dello stack durante la compilazione, oppure eseguendo una seconda passata sulle istruzioni compilate. Quindi, quando cerchi le radici GC, per ogni fotogramma sulla pila, usi la mappa che segue l'istruzione corrente.

Answer 2

Un'altra opzione consiste nell'utilizzare una pila di ombre: una serie di riferimenti mantenuti. Questa è di gran lunga l'opzione più semplice da implementare.