EscapeAnalysis

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

_C2 implemented 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

It 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.