next up previous contents
Next: Generationale Garbage Collection Up: Exakte Garbage Collection für Previous: Paralleles Führen eines Markierungs-Stack   Inhalt

Abstrakte Interpretation von Bytecode

Der Java-Bytecode besitzt neben seiner Typisierung eine weiter Eigenschaft, welche die Erstellung von Stackmaps stark vereinfacht: Der Typ einer Variablen ist nicht vom Programmablauf (control path) sondern lediglich von der Programmposition (control point) abhängig, d.h. er enthält keine control path dependency. Im Kontext von Java wird diese Eigenschaft als ,,Gosling Property`` nach James Gosling bezeichnet. Diese ermöglicht es einem bestimmten Programmpunkt innerhalb einer Methode fest eine Stackmap zuzuordnen, unabhängig davon, über welchen Pfad der betreffende Programmpunkt erreicht wurde.

Die Variablen i und s in Abbildung 4.6 werden durch den Compiler (hier javac) der gleichen Stackzelle 0 zugeordnet. Trotzdem ist der Typ jeder Stackzelle allein vom der aktuellen Bytecode-Position abhängig. Fände zum Beispiel an Instruktion 12 eine Garbage Collection statt, so müßte Zelle 0 als Skalar behandelt werden, an Instruktion 25 müßte sie als Referenz behandelt werden und an Instruktion 32 gälte sie als ununerreichbar.



Kontrollfluß-unabhängige Eigenschaften von Programmvariablen lassen sich mit Mitteln der Datenflußanalyse berechnen. Dazu wird der Wertebereich der betrachteten Variablen wird auf die Knoten eines Gitters (lattice) approximiert. Durch iterative abstrakte Interpretation des Programms lassen sich dann die betrachteten Werte gewinnen [Aho et al., 1986,Muchnick, 1997].

Diese Standardtechnik wird von [Agesen and Detlefs, 1997] und in erweiterter Form in [Agesen et al., 1998] eingesetzt, um die Typen lokaler Variablen in Java zu ermitteln. Das eingesetzte Typgitter ist in Abbildung 4.7 dargestellt. Die folgende Tabelle erklärt die Bedeutung der einzelnen Typen:

top Der Zelle wurden unterschiedliche Typen zugeordnet. Es ist also ein Konflike aufgetreten.
pc Die Zelle wurde zum Zwischenspeichern einer Rücksprungadresse in einem jsr-Call verwendet.
val Die Zelle enthält einen Skalar.
ref Die Zelle enthält eine Referenz.
uninit Die Zelle ist uninitialisiert.
bottom Die Zelle wurde noch nicht verwendet.

Abbildung 4.7: Typgraph der abstrakten Interpretation von Java-Bytecode nach Agesen
\begin{figure}
\begin{center}
\epsfig{file=garbage-collection/figures/type-lattice,width=5cm} \end{center}\end{figure}

Für gültigen Java-Bytecode, der die ,,Gosling Property`` beachtet, ergibt die Flußanalyse für alle Variablen einen Zustand $\not = top$, d.h. es treten keine Typkonflikte auf. Leider gibt es jedoch einen Java-Bytecode, der die ,,Gosling Property`` nicht einhält: jsr. Er wird verwendet, um den finally-Block des try { ... } finally { ... }-Konstruktes von unterschiedlichen Punkten innerhalb des try-Blocks als Subroutine auszuführen. Innerhalb dieser Subroutine der Zustand des Stacks jedoch mehrdeutig sein. Zur Lösung dieses ,,jsr-Problems`` schlagen [Agesen and Detlefs, 1997] ein Umschreiben des Bytecodes vor, indem Variablen mit einem Konflikt in eine Referenz- und eine Skalar-Variable aufgespalten werden. Andere virtuelle Maschinen expandieren die Subroutine einfach an alle Aufrufstellen und lösen so den Konflikt auf. Nach [Freund, 1998] ist der zusätzliche Platzbedarf vernachlässigbar.


next up previous contents
Next: Generationale Garbage Collection Up: Exakte Garbage Collection für Previous: Paralleles Führen eines Markierungs-Stack   Inhalt

2001-02-28