Type analysis in a Java Virtual Machine

Abstract

Obwohl virtuelle Methoden in objektorientierten Programmiersprachen beim Aufruf an viele unterschiedliche Definitionen gebunden werden können, wird oft nur eine Methodendefinition wirklich verwendet. Der Einsatz von Analysealgorithmen zur Bestimmung des statischen Typs in einer Java Virtual Machine (JVM), um konservativ die erreichbaren Klassen und Methoden abzuschätzen, kann einem Übersetzer mehr Möglichkeiten zur Optimierung geben. Das Laden von Klassen bei Bedarf in der JVM hat dynamische Analyse mit Profiling zur Laufzeit gefordert.<br />Die Typ-Analyse Algorithmen CHA, RTA, XTA, und VTA wurden in CACAO verglichen. CACAO ist eine Forschungs-JVM, die an der Technischen Universität Wien entwickelt wird. Drei Modi wurden getestet: statische Analyse (SA), dynamische Analyse (DA), und eine neue hybride Analyse (HPA). Alle Algorithmen bauen ihre Klassendatenflussdiagramme (CFGs) dynamisch während der Analyse auf. Klassen werden nach Bedarf geladen.<br />Daher müssen alle Analysen das Einfügen von zusätzliche Klassen in ihre Klassenhierarchien behandeln. Die Notwendigkeit von Devirtualization für Inlining und die Implementierung von Inlining in CACAO wird diskutiert.<br />

Although in object-oriented programming (OOP) languages, virtual methods may resolve to multiple method definitions during runtime, often only one method definition is actually used. Use of static type analysis algorithms in the Java Virtual Machine (JVM) to conservatively estimate classes used and methods reachable can give more opportunities for optimizations like inlining. Lazy loading of classes by the JVM has encouraged dynamic analysis with profiling during an application run.<br />The type analysis algorithms, CHA, RTA, XTA, and VTA are compared in CACAO, a research Java Virtual Machine (JVM) developed at Technical University of Vienna, in three modes: static analysis (SA) mode, dynamic analysis (DA) mode, and a new hybrid pickup analysis (HPA) mode. All algorithms build their class flow graphs (CFGs) on-the-fly during the analysis. Classes are loaded on-demand as needed, so all modes and algorithms must handle classes inserted into their class hierarchy. The usefulness of devirtualization for use by inlining based on the implementation of inlining in CACAO is discussed.<br />%The usefulness of inlining devirtualized methods based on the implementation of inlining in CACAO is discussed.<br />Fewer extra classes loaded gives better precision and improved runtime.<br />VTA is most precise with the fewest unneeded classes loaded and methods found reachable in all three analysis modes. HPA loaded fewer classes and yields more precise results than SA. Between RTA, XTA and VTA, there is no clear fastest algorithm, but XTA used the least instructions.<br />Costs to make the analysis more precise were offset by having fewer reachable methods to analyze and vice versa for less precision and more reachable methods.<br />