Adaptive inlining and on-stack replacement in a Java virtual machine

Abstract

Methoden-Inlining ist eine bekannte und wirkungsvolle Technik f¨ur die Optimierung objekt-orientierter Programme. Im Zusammenhang mit dynamischer ¨Ubersetzung kann Methoden-Inlining als adaptive Optimierung verwendet werden, um den Mehraufwand von h¨aufig ausgef¨uhrten Methodenaufrufen zu vermeiden. Diese Arbeit stellt eine Umsetzung von Methoden-Inlining in CACAO vor, einem just-in-time ¨Ubersetzer f¨ur Java. Das Ersetzen von Methoden im Aufrufstapel erm¨oglicht die Installation von optimiertem Maschinencode und das R¨uckg¨angigmachen von Optimierungen, wenn optimistische Annahmen des Optimierers durch dynamisches Nachladen von Klassen ung¨ultig werden. Drei Heuristiken f¨ur Methoden-Inlining werden anhand empirischer Messungen an einem Satz von Benchmarkprogrammen verglichen. Ein typenbasierter Algorithmus zum Entfernen lokaler Unterprogramme wird beschrieben.

Method inlining is a well-known and effective optimization technique for object-oriented programs. In the context of dynamic compilation, method inlining can be used as an adaptive optimization in order to eliminate the overhead of frequently executed calls. This work presents an implementation of method inlining in CACAO, a just-in-time compiler for Java. On-stack replacement is used for installing optimized code and for deoptimizing code when optimistic assumptions of the optimizer are broken by dynamic class loading. Three inlining heuristics are compared using empirical results from a set of benchmark programs. A type-based algorithm for the elimination of local subroutines is described.