Escape Analysis

From: Vladimir Kozlov
Date: May 15, 2009 1:47:21 PM PDT

_C2 implements the flow-insensitive escape analysis algorithm described in:

[Choi99] Jong-Deok Shoi, Manish Gupta, Mauricio Seffano,
         Vugranam C. Sreedhar, Sam Midkiff,
         "Escape Analysis for Java", Procedings of ACM SIGPLAN
         OOPSLA  Conference, November 1, 1999

The analysis requires construction of a "connection graph" (CG) for the method being analyzed. The nodes of the connection graph are:

    -  Java objects (JO)
    -  Local variables (LV)
    -  Fields of an object (OF),  these also include array elements

C2 does not have local variables. However for the purposes of constructing the connection graph, the following IR nodes are treated as local variables:

    Phi       (pointer values)
    LoadP, LoadN
    Proj#5    (value returned from call nodes including allocations)
    CheckCastPP, CastPP, EncodeP, DecodeN
    Return    (GlobalEscape)

The LoadP, Proj and CheckCastPP behave like variables assigned to only once. Only a Phi can have multiple assignments. Each input to a Phi is treated as an assignment to it.

The following node types are JavaObject:

    top()
    Allocate
    AllocateArray
    Parm                  (for incoming object arguments, GlobalEscape)
    CastX2P               ("unsafe" operations, GlobalEscape)
    CreateEx              (GlobalEscape)
    ConP, ConN            (GlobalEscape except for null)
    LoadKlass, LoadNKlass (GlobalEscape)
    ThreadLocal           (ArgEscape)

AddP nodes are fields.

After building the graph, a pass is made over the nodes, deleting deferred nodes and copying the edges from the target of the deferred edge to the source. This results in a graph with no deferred edges, only:

   LV -P> JO
   OF -P> JO (the object whose oop is stored in the field)
   JO -F> OF

After that escape analysis makes a pass over the nodes and determines nodes escape state:

• GlobalEscape - An object escapes the method and thread (stored into a static field or stored into a field of an escaped object or returned as the result of the current method).
• ArgEscape - An object passed as argument or referenced by argument but not globally escape during a call (by analyzing the bytecode of called method).
• NoEscape - A scalar replaceable object.

After escape analysis C2 eliminates scalar replaceable object allocations and associated locks. C2 also eliminates locks for all non globally escaping objects. C2 does NOT replace a heap allocation with a stack allocation for non globally escaping objects.