Bruno Blanchet Back to publications
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.

Get the paper

.ps.gz, 992 Kb


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.


  AUTHOR = {Bruno Blanchet},
  TITLE = {Analyse d'échappement. Applications à ML et Java({TM}). Escape Analysis. Applications to ML and Java({TM})},
  SCHOOL = {École Polytechnique},
  YEAR = 2000,
  MONTH = {7 } # DEC,
  NOTE = {En anglais. In English. {\bf Prix de thèse de l'École Polytechnique. Thesis prize of Ecole Polytechnique.}}

E-mail/Courrier électronique : (remove trap-)