Jak znaleźć korzenie gc w maszynie stosu?

Question

Piszę kompilator dla dość standardowej maszyny stosu. Teraz chcę dodać śmieciarz. Widzę, że mogę wygenerować jakieś "mapy stosów", aby wiedzieć, które zmienne są pierwiastkami gc w każdym rekordzie aktywacji. Jednak nie mam pojęcia, jak radzić sobie z wartościami pośrednimi wciśniętymi w stos podczas wykonywania. Język, który kompiluję, jest podobny do Pascala, więc nie potrzebuję i nie chcę używać znaczników do identyfikowania wskaźników z innych typów danych.

Byłbym wdzięczny za wszelkie wskazówki/wskazówek, w jaki sposób

1. Znajdź gc korzenie w stosie w dowolnym momencie w czasie (czyli w jaki sposób określić, które z wartości pośrednich, które zostały zepchnięte na stosie są korzenie gc).
2. Zwyczajowe kodowania informacji (czyli jak generować i zakodować „mapy stos”)

Dziękuję bardzo! Nicolas

Answer 1

Prostym rozwiązaniem jest jawne zapisywanie typu każdego wpisu stosu. Wtedy nie potrzebujesz mapy stosu; jeśli typ to "reference", to wpis jest katalogiem głównym GC. Takie podejście jest szczególnie przydatne w przypadku debugowania, ponieważ można łatwo wyświetlić (wpisaną) zawartość stosu.

Jeśli naprawdę chcesz korzystać z map stosu, prostym rozwiązaniem jest wygenerowanie mapy stosu, która pasuje do każdej instrukcji. Robisz to, śledząc zawartość stosu podczas kompilacji lub wykonując drugie przejście przez skompilowane instrukcje. Następnie, szukając korzeni GC, dla każdej ramki na stosie, używasz mapy zgodnej z bieżącą instrukcją.

Answer 2

Inną opcją jest użycie stosu cieni: stos odniesień, które sam się utrzymuje. Jest to zdecydowanie najłatwiejsza opcja do wdrożenia.