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.
@PHDTHESIS{BlanchetPhd00,
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.}}
}