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.