BlanchetToplas

Bruno Blanchet Back to publications

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

Copyright

Copyright© 2003 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page or intial screen of the document. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.

If you agree with this copyright notice, you can get the paper:

Get the paper

.ps.gz, 266 Kb

Links

Official ACM version (you can download the full text from there):

Escape analysis for Java^TM: Theory and practice

Bruno Blanchet
ACM Transactions on Programming Languages and Systems (TOPLAS), 2003

Abstract

Escape analysis is a static analysis that determines whether the lifetime of data may exceed its static scope.

This paper first presents the design and correctness proof of an escape analysis for Java(TM). This analysis is interprocedural, context sensitive, and as flow sensitive as the static single assignment form. So, assignments to object fields are analyzed in a flow-insensitive manner. Since Java is an imperative language, the effect of assignments must be precisely determined. This goal is achieved thanks to our technique using two interdependent analyses, one forward, one backward. We introduce a new method to prove the correctness of this analysis, using aliases as an intermediate step. We use integers to represent the escaping parts of values, which leads to a fast and precise analysis.

Our implementation, which applies to the whole Java language, is then presented. Escape analysis is applied to stack allocation and synchronization elimination. In our benchmarks, we stack allocate 13% to 95% of data, eliminate more than 20% of synchronizations on most programs (94% and 99% on two examples) and get up to 43% runtime decrease (21% on average). Our detailed experimental study on large programs shows that the improvement comes more from the decrease of the garbage collection and allocation times than from improvements on data locality, contrary to what happened for ML. This comes from the difference in the garbage collectors.

Bibtex


@ARTICLE{BlanchetToplas,
  AUTHOR = {Bruno Blanchet},
  TITLE = {Escape {A}nalysis for {J}ava({TM}). {T}heory and {P}ractice},
  JOURNAL = {ACM Transactions on Programming Languages and Systems},
  YEAR = {2003},
  VOLUME = {25},
  NUMBER = {6},
  PAGES = {713--775},
  MONTH = NOV
}

E-mail/Courrier électronique : Bruno.Blanchet@trap-inria.fr (remove trap-)