Wie findet man GC-Wurzeln in einer Stapelmaschine?

Question

Ich schreibe einen Compiler für eine ziemlich Standard-Stack-Maschine. Jetzt möchte ich einen Garbage Collector hinzufügen. Ich kann sehen, dass ich eine Art von "Stack-Maps" erzeugen könnte, um zu wissen, welche Variablen in jedem Aktivierungs-Record GC-Wurzeln sind. Ich habe jedoch keine Ahnung, wie man mit Zwischenwerten umgehen soll, die während der Ausführung in den Stapel geschoben werden. Die Sprache, die ich kompiliere, ist Pascal-ähnlich, also brauche ich nicht und ich möchte keine Tags verwenden, um Zeiger von anderen Datentypen zu identifizieren.

würde ich irgendwelche Hinweise/Zeiger auf schätzen, wie man

1. Finden gc Wurzeln in dem Stapel an jedem beliebigen Punkt in der Zeit (dh, wie die der Zwischenwerte zu identifizieren, die in dem Stapel geschoben worden sind, sind GC Wurzeln).
2. Übliche diese Information zu codieren (das heißt, wie zu generieren und zu kodieren ‚Stapel Karten‘)

Vielen Dank! Nicolas

Answer 1

Eine einfache Lösung besteht darin, den Typ jedes Stackeintrags explizit zu speichern. Dann brauchst du keine Stapelkarte; Wenn der Typ "Referenz" ist, ist der Eintrag ein GC-Root. Dieser Ansatz ist besonders praktisch zum Debuggen, da Sie den (getippten) Inhalt des Stapels leicht anzeigen können.

Wenn Sie wirklich Stapelkarten verwenden möchten, besteht eine einfache Lösung darin, eine Stapelkarte zu erstellen, die zu jeder Anweisung gehört. Sie tun dies, indem Sie den Stapelinhalt während des Kompilierens verfolgen oder indem Sie einen zweiten Durchlauf über die kompilierten Anweisungen durchführen. Wenn Sie nach GC-Wurzeln suchen, verwenden Sie für jedes Bild auf dem Stapel die Karte, die zu der aktuellen Anweisung gehört.

Answer 2

Eine weitere Option ist die Verwendung eines Schattenstapels: ein Stapel von Referenzen, den Sie selbst verwalten. Dies ist bei weitem die einfachste zu implementierende Option.