On-Stack Replacement

Methodenintegration ist ein wichtige Technik zur Optimierung von Methodenaufrufen. Dabei werden teilweise monomorphe Aufrufstellen integriert, die durch späteres dynamisches Laden neuen Programmcodes nicht länger eine eindeutige Zielmethode besitzen. Es muß also sichergestellt werden, daß der optimierte Aufruf nicht mit einem Exemplar der neu geladenen Klasse als Empfänger ausgeführt wird.

Ein Teil der Lösung besteht darin, bereits zur Ladezeit die betroffene Methode neu zu übersetzen, bzw. als interpretiert zu markieren, und in ihrer Klasse neu zu installieren. Erst dann können Exemplare der neuen Klasse erzeugt werden. Dieses Vorgehen läßt allerdings ein Problem unberücksichtigt: es können weiterhin Aktivierungen der alten, optimierten Methode existieren. Diese könnten ein Exemplar der neuen Klasse erreichen und mit diesem den bereits ungültigen Code ausführen. Es gilt also, auch die Aktivierungen der ungültigen Methode zu ersetzen. Dazu muß eine Zuordnung der Stack- und Registerinhalte der optimierten Methode zu den Variablen der Quellmethode erfolgen. Aufgrund von Platzerwägungen sind solche Zuordnungsstrukturen nicht für jede Instruktion, sondern nur an dedizierten Punkten, typischerweise Methodenprologe und Rückwärtssprünge, zur Verfügung zu stellen.

Abbildung 3.1: OSR-Beispiel

Abbildung 3.2: Optimierter Code

Abbildung 3.3: On-Stack Replacement

Ein Beispiel erläutert die Problematik. Gegeben sei folgende Methode dogs(3.1), die aus einer Sammlung von Tieren die Zahl der Hunde ermittelt. Da zum Übersetzungszeitpunkt nur die Tier-Klasse Cat mit Cat::isDog() = false geladen ist, kann der Compiler wie in Abbildung 3.2 optimieren. Insbesondere die lokale Variable dogs ist im optimierten Rahmen nicht vorhanden, so daß eine Aktivierung von dogs im optimierten Fall um eine lokale Variable kleiner ist als ihre Ersatzaktivierung. Wird nun eine Klasse Dog hinzugeladen, und wird ein Exemplar in das Array animals gespeichert, während eine Aktivierung von dogs in einem anderen Thread ausgeführt wird, so muß dieser Thread suspendiert und sein Laufzeit-Stack entsprechend angepasst werden (Abbildung 3.3). Ein Rahmen einer optimierten Methode kann aufgrund von Methodenintegration dabei sogar mehreren unoptimierten Rahmen entsprechen.

On-stack replacement ist ein sehr komplexes Verfahren, da Laufzeit-Stacks manipuliert werden und eine Rückwärtsabbildung von optimiertem Code auf die Programmgrößen implementiert werden muß. Aus diesem Grunde schlagen [Agesen and Detlefs, 1999a] eine Einschränkung für ungeschütztes Inlining vor: kann bewiesen werden, daß der fragliche Empfänger des integrierten Aufrufs vor Aktivierung der aufrufenden Methode bereits existierte, so wird diese Aktivierung auch durch das Laden neuer Klassen nicht ungültig gemacht. Die Methode muß zwar neu übersetzt werden, laufende Aktivierungen können jedoch intakt bleiben. Im obigen Beispiel wird der Empfänger aus einer externen Struktur entnommen; in diesem Fall würde die vorgeschlagene Vereinfachung daher nicht zutreffen.

On-stack replacement wird in der SELF-VM unter anderem zum Debugging verwendet [Hölzle et al., 1992]. Die HotSpot-VM deoptimiert Methoden, deren Voraussetzungen zur Methodenintegration invalidiert wurden, durch OSR.