DEA training and PhD thesis: Escape Analysis

[Français] [Index]

Recent programming languages such as ML and Java often use an automatic mechanism to recover the memory dynamically allocated in the heap, the garbage collector. The garbage collection takes some time during the execution of the programs. My DEA training and my PhD thesis aim at studying escape analysis, which is an abstract interpretation technique that can be used to allocate data on the stack instead of the heap, therefore decreasing the garbage collector workload.

My DEA training took place from April to September 1996 at INRIA Rocquencourt, under Alain Deutsch's supervision. I have continued this work during my PhD thesis, still with Alain Deutsch at INRIA Rocquencourt, under Patrick Cousot's supervision. Here is its abstract.

Escape analysis is a static analysis that aims at determining whether the lifetime of values exceeds their static scope or not. If not, the values can be stack allocated. This thesis extends the previous works on escape analysis by fully handling two realistic languages for the first time: Objective Caml and Java. Our contributions are both theoretical and practical.

The main theoretical contribution is the correctness proof of the analyses from a semantics of the analyzed language, using the techniques of abstract interpretation. For ML, the imperative operations (assignments), polymorphism, higher-order functions, recursive types are handled. Two representations of the escape abstract values are proposed: one, very efficient, uses integers, the other, more precise but also more costly, uses annotated types. The comparison between these two representations indicates which one yields the best tradeoff. For Java, we propose a new technique to take into account assignments more precisely than in ML, while keeping a fast analysis.

The analyses have been fully implemented in compilers, to study two applications of escape analysis: stack allocation and synchronization elimination. (This last optimization does not apply to ML.) A detailed experimental study of the effects of these optimizations has been performed on large programs. This study has shown that stack allocation improves data locality, decreases the GC (garbage collector) workload and the allocation time, and that the effects of stack allocation highly depend on the kind of GC and of cache. The analysis algorithms have been chosen to obtain particularly efficient analyses. The experiments have shown that the representation using integers yields the best cost/precision tradeoff.

Publications about this subject

[1]
Bruno Blanchet. Escape Analysis for Java(TM). Theory and Practice. ACM Transactions on Programming Languages and Systems, 25(6):713-775, November 2003.

[2]
Bruno Blanchet. Analyse d'échappement. Applications à ML et Java(TM). Escape Analysis. Applications to ML and Java(TM). PhD thesis, École Polytechnique, 7 December 2000. En anglais. In English. Prix de thèse de l'École Polytechnique. Thesis prize of Ecole Polytechnique.

[3]
Bruno Blanchet. Escape Analysis for Object Oriented Languages. Application to Java(TM). In Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA'99), pages 20-34, Denver, Colorado, November 1999.

[4]
Bruno Blanchet. Escape Analysis: Correctness Proof, Implementation and Experimental Results. In 25th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL'98), pages 25-37, San Diego, California, January 1998. ACM Press.

[5]
Bruno Blanchet. Garbage Collection statique. Rapport de DEA, INRIA, Rocquencourt, September 1996. En français.

Software

You can download my stack allocator for ML (copyright INRIA), file in .tar.gz format, to install according to the instructions contained in the distribution. This file contains a modified version of the Objective Caml compiler, version 1.05, that performs stack allocation. For more information about Objective Caml, a version of ML implemented at INRIA, in the Cristal Project, see http://caml.inria.fr. The stack allocator has been tested only under Unix (Linux, Solaris, Digital Unix, ...). If you try this software, please leave me a short message at Bruno dot Blanchet at ens dot fr to give your impressions.
Bruno Blanchet