Escape Analysis and Scalar Replacement of Aggregates

An allocation is observable only through the references that reach it. If no reference to an object ever leaves the function that created it, and no reference is stored anywhere another thread can read, then the object has no identity that the program can detect: it cannot be compared against another allocation, it cannot be freed by anyone else, and its lifetime is exactly the region of code that uses it. Under those conditions the object does not need to exist at all. Its fields can become ordinary scalar variables, and the allocation disappears.

Escape analysis is the analysis that establishes those conditions. Scalar replacement is the transformation that consumes them. Together they are the main reason a language with mandatory heap allocation for every object can still compile a tight loop to register operations.

Three escape states, not two

The useful classification is not “escapes” versus “does not”. Implementations distinguish at least three outcomes per allocation, and the distinction drives what transformation is legal.

NoEscape. The object is used only within the allocating function, and no reference to it is stored into a location that outlives the function, passed to a call that might retain it, or returned. The object can be scalar-replaced.

ArgEscape. A reference is passed as an argument to a call, but the analysis has established that the callee does not let it escape — it may read and write the object during the call but retains no reference afterwards. The object can still be replaced if the callee is inlined or if the call is modelled precisely, but not by the simplest version of the transformation.

GlobalEscape. A reference is stored to a static field, returned, captured by a closure that outlives the frame, or published to another thread. The object must be allocated, and its identity is observable.

The classification is per allocation site and, in the more precise formulations, per connection between an allocation and a use. A single new inside a loop can be NoEscape on one path through the function and GlobalEscape on another, and the transformation must then either split the paths or decline.

Computing the escape state

The analysis is a propagation over the program’s reference graph, and the classical formulation by Choi and colleagues builds a connection graph: nodes are allocation sites and reference variables, edges record that a reference may flow from one node to another. Field stores add edges through the field, array stores add edges through the array element, and a call adds edges from actual parameters to the callee’s formal parameters and back from the return value.

Escape then falls out of reachability from the roots:

• A node reachable from a static field, a thread-local, or an object that itself escapes is GlobalEscape.
• A node reachable from a formal parameter of a method that is not analysed, or from the return value of such a method, is at least ArgEscape.
• Otherwise the node is NoEscape.

The subtle part is that the analysis must be conservative about anything it cannot see. A call to a function outside the analysed set — a native method, a virtual call with an unknown target, a reflective invocation — is a hole through which any argument may escape. Implementations either treat every such call as making all reachable nodes GlobalEscape, or, more usefully, maintain a per-parameter summary: “this method does not retain its first argument” is a fact that survives separate compilation and can be checked cheaply at the call site.

/* Monotone propagation over points-to edges; the lattice has height two. */
enum esc { NO_ESCAPE, ARG_ESCAPE, GLOBAL_ESCAPE };

static void raise(alloc_site **work, int *nwork, alloc_site *n) {
    for (int k = 0; k < *nwork; k++)              /* already queued, skip */
        if (work[k] == n) return;
    work[(*nwork)++] = n;
}

static void propagate(alloc_site **sites, int nsites) {
    alloc_site *work[MAX_SITES];
    int nwork = 0;
    for (int k = 0; k < nsites; k++) raise(work, &nwork, sites[k]);

    while (nwork > 0) {
        alloc_site *a = work[--nwork];
        if (a->stored_to_static || a->returned_unknown || a->published)
            a->esc = GLOBAL_ESCAPE;
        else if (a->passed_to_unknown && a->esc < ARG_ESCAPE)
            a->esc = ARG_ESCAPE;                  /* may still be scalar-replaced */

        for (edge *e = a->out; e; e = e->next)    /* aliases inherit the state */
            if (a->esc > e->dst->esc) {
                e->dst->esc = a->esc;
                raise(work, &nwork, e->dst);
            }
    }
}

The propagation must run to a fixpoint over cycles in the reference graph, which is the usual monotone iteration with a lattice of height two. Cycles form readily — an object whose field points to itself, a linked list built locally — and a naive traversal recurses forever on them. The fixpoint formulation handles them because a node’s state only ever increases and stops at GlobalEscape.

From analysis result to transformation

Scalar replacement rewrites each field of a NoEscape object into an SSA name. A load of p.f becomes a use of the name for f; a store p.f = v becomes a definition. The object’s allocation is deleted once no references to it remain, and its constructor is inlined so that the initial field values become definitions of the names.

Two conditions must hold for this to be valid, and both are easy to violate.

The field must be accessed with a statically known offset. That is true for a monomorphic object of known type and false for anything reached through an interface or a polymorphic field. Implementations rely on class hierarchy analysis or profile data to prove monomorphism, and the transformation fails silently when the assumption is wrong only if the compiler did not check — a checked implementation falls back to the allocation.

The object must not be compared by identity. Two distinct allocations have distinct references, and a program that compares them, uses them as hash keys by identity, or synchronizes on them observes the difference. Escape analysis must therefore treat identity comparison as an escape, and the simplest sound rule is to treat any use that is not a field access, a call argument with a known summary, or a local copy as an escape.

Arrays add a third condition. Replacing an array requires the indices to be constant or provably in range, and the element type to be known. A small fixed-size array indexed by a loop induction variable is replaceable after unrolling; an array of unknown length is not.

Partial escape analysis

The whole-object classification is coarse. A common shape allocates an object, uses it locally, and only on an error path stores it into a field for later inspection. Treating the whole allocation as GlobalEscape because of the error path gives up the optimization on the hot path.

Partial escape analysis, described by Stadler and colleagues, defers the decision to the point of escape. The object is scalar-replaced along every path that does not escape, and materialized — that is, allocated as a real object with its scalar fields copied into it — immediately before the point where it does. The result is a conditional allocation on the cold path and pure scalar code on the hot path.

The cost is a more complex transformation: the compiler must insert the materialization at the right point on the right edges, and must ensure that the object’s identity is not observed before materialization. The benefit is largest for the pattern that motivates the technique: allocate, fill, use, and escape only on failure, which is the shape of code that returns structured error information without paying for it on the success path.

Where it fails

Reflection and dynamic dispatch defeat the analysis. Any call the compiler cannot resolve is a hole, and languages with reflection make almost every call potentially unresolvable. The usual mitigation is to specialize on the observed receiver types, which is the same mechanism used for inline caches in dynamic runtimes.

Concurrency defeats it in a different way. An object published to another thread has its fields written by two threads, and scalar replacement would remove the memory locations through which the threads communicate. The analysis must treat publication — a store to a field another thread can read, a store into a concurrent data structure, a call to a method that publishes — as GlobalEscape. This is why escape analysis and the memory model interact: the transformation is valid only under the language’s rules about when a reference becomes visible to another thread.

Stack allocation is the alternative transformation, and it has different costs. Allocating the object in the frame avoids the heap allocation and the garbage collector’s work but requires the object’s lifetime to be bounded by the frame and requires the address of the object not to be captured. It also changes the cost profile: a stack object that is large increases frame size, and a frame that grows past a page boundary costs a stack probe on some platforms. Scalar replacement avoids the object entirely and is strictly better when it applies; stack allocation is the fallback when the object’s address must exist but its lifetime is local.

The analysis result also feeds other passes. Knowing that a variable does not escape licenses removing the synchronization around it — lock elision — because no other thread can contend for the lock. Knowing that a parameter does not escape lets the callee’s writes be treated as local, which improves the alias information that constant propagation and store-to-load forwarding depend on, as described in Constant Propagation over a Flat Lattice. And knowing which allocations are hot is an input to the inlining and splitting decisions covered in Profile-Guided Optimization and Hot-Cold Code Splitting.