Skip to content

Escape Analysis for Java

Jump to bottom
Artem Usov edited this page Nov 24, 2020 · 1 revision

Jong-Deok Choi, Mannish Gupta, Mauricio Serrano, Vugranam C. Sreedhar, Sam Midkiff

DOI: 10.1145/320385.320386

Create an abstraction such that escape/capture information can be summarized for each function/method, and so can be cached. This means that the same computed information can be used in different calling contexts.

They call this in the paper the connection graph, which is used to establish reachability relationships between objects and object references. The algorithm determines whether an object may escape the method and may escape the thread.

Method Escapement: Let O be an object instance and M be a method invocation. O is said to escape M, denoted as Escapes(O, M), if the lifetime of O may exceed the lifetime of M.

Thread Escapement: Let O be an object instance and T be a thread (instance). O is said to escape T, again denoted as Escapes(O, T), if another thread, T’ != T, may access O.

If M is a method invocation in T, and another thread T’ is created in M, all objects O’ reachable in T’ are set to be Escapes(O’, M).

We can then define three states in which an Object O may be. NoEscape, ArgEscape (object escapes method via arguments, but does not escape thread), and GlobalEscape. After analysis, if an object is in state NoEscape, then it be stack-allocated in the JVM. All objects either NoEscape or ArgEscape can get their thread synchronisation removed.

Connection Graph

A connection graph is a directed graph CG = No ∪ Nr ∪ Nf ∪ Ng, Er ∪ Ed ∪ Ef.

  • No represents the set of objects.
  • Nr represents the set of reference objects.
  • Nf represents the set of non-static field nodes.
  • Ng represents the set of static field nodes.
  • Er is the set of points-to edges.
  • Ed is the set of deferred edges.
  • Ef is the set of field edges.

We use deferred edges to model assignments that merely copy references from one variable to another Deferred edges defer computation during connection graph construction. Given a reference node m, the set of objects it points-to can be determined by traversing the deferred edges from m until we visit the first points-to edge in the path.

With each node, we associate an escape set. The initial state for each Ng is GlobalEscape and NoEscape for all other nodes, unless otherwise stated.

Escape Analysis

Let CG be a connection graph for a method M, and let O be an object node in CG. If O can be reached in CG from any node whose escape state is not NoEscape, then O escapes M

  • For new object creation (P = new T), we create an object node O and add a points-to edge from P to O.
  • For copying, (P = Q), we add a deferred edge from P to Q.
  • For field assignment (P.f = Q), if U = PointTo(P) is null, P is null or object that points to P was created outside of this method. We assume the later if U is null and create a phantom object node Oph and insert a points-to edge from p to Oph.
  • For field assignment of form (P = Q.f), similar procedure, see paper for full description.

During interprocedural analysis, phantom nodes will be mapped back to the actual nodes created by appropriate procedure.

The summary connection graph of a method is represented by the NonLocalGraph, which is the union of the subgraphs induces by the set of nodes that are reachable from a GlobalEscape node and the subgraph induces by the set of nodes reachable from a ArgEscape node but not from any GlobalEscape node. See the paper for the Reachability Analysis algorithm to obtain these subgraphs.

The objects in NonLocalGraph marked GlobalEscape need to have their original nodes marked GlobalEscape in the calling method.

Clone this wiki locally