Partial Escape Analysis and Scalar Replacement for Java

Lukas Stadler

Abstract

Escape Analysis allows a compiler to determine whether an object is accessible outside the allocating method or thread. This information is used to perform optimizations such as Scalar Replacement, Stack Allocation and Lock Elision, allowing modern dynamic compilers to remove some of the abstractions introduced by advanced programming models.

The all-or-nothing approach taken by most Escape Analysis algorithms prevents all these optimizations as soon as there is one branch where the object escapes, no matter how unlikely this branch is at runtime.

This thesis presents a new, practical algorithm that performs control flow sensitive Partial Escape Analysis in a dynamic Java compiler. It allows Escape Analysis and Scalar Replacement to be applied on individual branches. We implemented the algorithm on top of an open-source Java just-in-time compiler, and it performs well on a diverse set of benchmarks.

In this thesis, we evaluate the effect of Partial Escape Analysis on the DaCapo, ScalaDaCapo and SPECjbb2005 benchmarks, in terms of run-time, number and size of allocations and number of locking operations. It performs particularly well in situations with additional levels of abstraction, such as code generated by the Scala compiler. It reduces the amount of allocated memory by up to 58,5%, and improves performance by up to 33%.

Kurzfassung

Escape Analysis ermöglicht es Compilern festzustellen, ob auf ein Objekt von außerhalb der allokierenden Methode oder des allokierenden Threads zugegriffen werden kann. Basierend darauf können Optimierungen wie Scalar Replacement, Stack Allocation und Lock Elision durchgeführt werden, die es modernen Compilern erlauben, die Abstraktionen moderner Programmiertechniken zu entfernen.

Der Alles-oder-Nichts - Ansatz der meisten Escape Analysis Algorithmen verhindert alle diese Optimierungen, sobald das Objekt auch nur in einem Pfad entkommt, egal wie unwahrscheinlich dieser Pfad zur Laufzeit ist.

Diese Arbeit stellt einen neuen, praktikablen Algorithmus vor, der kontrollflusssensitive Partial Escape Analysis in dynamischen Java Compilern durchführt. Dieser erlaubt es, Escape Analysis und Scalar Replacement auf einzelne Pfade anzuwenden. Die Implementierung dieses Algorithmus ist Teil eines Open-Source Java Just-in-Time Compilers, wobei dieses System eine Vielzahl unterschiedlicher Benchmarks effizient ausführt.

Diese Arbeit evaluiert den Effekt von Partial Escape Analysis basierend auf den DaCapo, ScalaDaCapo und SPECjbb2005 Benchmarks in Hinblick auf Laufzeit, Anzahl und Größe der Allokationen und Anzahl der Lock-Operationen. Partial Escape Analysis arbeitet besonders gut in Situationen mit zusätzlichen Abstraktionsebenen, wie sie z.B. der Scala Compiler erzeugt. Die Größe des allokierten Speichers wird um bis zu 58,5% verringert, die Laufzeit um bis zu 33% verbessert.

PhD thesis, Johannes Kepler University Linz, Mai 2014