Escape Analysis and Scalar Replacement in Compiled Code

Allocation is the operation an object-oriented program performs most often and notices least. A short-lived object created inside a loop, passed to nothing, and read once costs an allocation, an initialization, a garbage collection’s worth of bookkeeping, and the cache pressure of touching a new address. If the compiler can prove the object never escapes the method that created it, none of that is necessary: the object’s fields can live in registers, and the allocation can disappear entirely.

The proof is a static analysis over a dynamically compiled method, and its conclusions are conditional on assumptions the runtime checks. The gap between the proof and its conditions is where the interesting failures live.

What Escape Means

An object escapes when a reference to it can be observed outside the scope in which the compiler can track it. The analysis classifies allocations into a few states, ordered by how much freedom the compiler has.

No escape: the object is created, used, and dropped within one method, and no reference to it is stored anywhere the compiler cannot follow. Its fields can be replaced by local variables, which is scalar replacement.

Argument escape: the object is passed to a call, but the callee does not store it and does not return it. The compiler can still scalarize if it inlines the callee, because then the callee’s use of the object is visible. Without inlining, the object must be allocated, since the call may do anything with it.

Return escape: the object is returned or stored into a field of another object that escapes. The allocation must happen, because the reference outlives the method.

Global escape: the object is stored into a static field, passed to a thread, or otherwise made reachable from outside the current thread. The allocation must happen and, in a runtime with moving collectors, must be registered with the collector.

The analysis computes the strongest state that holds for each allocation. It is a dataflow problem over the method’s intermediate representation, propagating reference reachability: a reference stored into a local is still trackable, a reference stored into a field of an object that does not escape is still trackable, and a reference passed to a call that is not inlined becomes untrackable.

Scalar Replacement and Its Bookkeeping

Once an allocation is proven non-escaping, the compiler replaces it with a set of virtual fields. Reads and writes to the object become reads and writes to those virtual fields, which the register allocator then treats as ordinary variables. A field that is written once and read once may vanish entirely, folded into the value it held.

The transformation is more delicate than it looks, for four reasons.

First, object identity. A program can compare two references and observe whether they are the same object. If both objects were scalarized, the comparison has to be answered from the analysis: two distinct allocations are never identical, and a scalarized object compared against itself is trivially identical. A scalarized object compared against an allocated one must be false unless the compiler can prove otherwise. The Java language specification makes reference equality observable, so a scalar replacement that changed the answer of == would change program semantics.

Second, synchronization. A scalarized object cannot be locked, because there is no object header to lock. Compilers either decline to scalarize objects that are synchronized on, or they prove that the lock is uncontended and elide it, which is a separate optimization with its own hazards.

Third, finalization and weak references. If the runtime permits a finalizer to observe an object, or a weak reference to it, the object must exist. Compilers exclude such objects from scalar replacement, which means the analysis needs to know which classes have finalizers and which allocations are registered with a reference queue.

Fourth, identity hash codes. A hash code computed from an object’s address, or stored in its header on first request, is observable. Scalarizing an object whose identity hash has been taken would require materializing a stable hash from nothing, so compilers either materialize the object when the hash is requested or decline to scalarize objects whose hash may be observed.

// Before: an allocation per iteration that escape analysis can eliminate.
Point sum(int[] xs) {
    Point total = new Point(0, 0);
    for (int x : xs) {
        Point p = new Point(x, x);   // p does not escape
        total = new Point(total.x + p.x, total.y + p.y);
    }
    return total;                    // total escapes; p does not
}

// After scalar replacement, the inner allocation is gone and so are the
// field loads: p.x and p.y are just x.
Point sum(int[] xs) {
    int tx = 0, ty = 0;
    for (int x : xs) { tx += x; ty += x; }
    return new Point(tx, ty);
}

The transformation looks like common subexpression elimination because, after scalarization, it is. The allocation was the only thing preventing the compiler from seeing that p.x and p.y were both x.

Guards Around the Proof

A dynamically compiled method is optimized under assumptions about what its callees do. If escape analysis concluded that a callee does not store its argument, and the runtime later loads a subclass that overrides the callee with a method that does store it, the conclusion is no longer valid.

The guard for this is the same class-identity check used for speculative inlining: the compiler inlined the callee under a check that the receiver is of the profiled class, and the escape analysis’s conclusion is conditional on that check. When the check fails, control leaves the compiled code through deoptimization, and the deoptimization must reconstruct the scalarized object as a real one, because the interpreted code it resumes in will allocate it.

That last point is where escape analysis and deoptimization meet most tightly. A scalarized object has no address and no header. The frame state at a deoptimization point inside a region where the object is live must describe it as an object, with each field’s location given as a register or a stack slot. The reconstruction allocates a real object and fills it from those locations. If the compiler forgot to describe a scalarized object in the frame state, the reconstructed frame would have a null where the interpreter expects a live reference, and the failure would appear as a null dereference in code that never contained one.

The requirement is easy to violate during optimization. A field that the compiler folded into a constant is still part of the object’s state; a field that was dead and removed is still part of it, if the object is materialized and read by code the compiler did not see. Compilers handle this by treating the frame state as a use of every field of every scalarized object that is live at that point, which prevents the field’s value from being discarded.

Why the Analysis Fails in Practice

Escape analysis has a reputation for underdelivering, and the reasons are structural rather than implementation bugs.

Virtual calls defeat it. An object passed to a virtual method that is not inlined must be assumed to escape, because the callee is unknown. In code with many small virtual calls, most allocations are passed to something, and the analysis concludes that they escape. The fix is inlining, which is why escape analysis and inlining are usually discussed together: the analysis is only as strong as the inliner’s reach.

Collections defeat it. An object stored into a list, a map, or a queue escapes by construction, since the container is reachable. Programs allocate for the purpose of storing, and those allocations are exactly the ones the analysis cannot remove.

Loops that allocate accumulate. Even with scalar replacement, an object created inside a loop and stored into a scalarized aggregate requires the aggregate’s fields to be updated per iteration, which is fine, but an object created inside a loop and stored into an array cannot be scalarized because the array is a heap object. The allocation may still be removable by a different optimization that reuses the same object across iterations, which changes identity semantics and is therefore only valid when the analysis proves the object does not escape in the identity-observable sense.

Large methods defeat it. The analysis is quadratic in the worst case over the number of allocations and references, and runtimes bound it by method size. A method large enough to have many allocations is often compiled with the analysis disabled, on the grounds that the compile time is not repaid.

Threads defeat it. An object published to another thread escapes by definition, and proving that a publish does not happen requires reasoning about synchronization that most analyses do not attempt. The conservative answer is that any object passed to a thread-creating call escapes.

The Payoff, and the Alternative

When the analysis succeeds, the payoff is not merely the allocation. The removed allocation also removes a write barrier, a potential garbage collection trigger, and a cache line’s worth of memory traffic. In a loop that allocates a small object per iteration, scalar replacement can turn a sequence of dependent memory operations into arithmetic on registers, which is the same transformation inlining achieves for call overhead.

The alternative to scalar replacement is a cheaper allocator. A bump-pointer allocator with a young generation makes allocation a pointer increment and a bounds check, on the order of a few instructions, and a copying collector reclaims short-lived objects at a cost proportional to the survivors rather than the garbage. That combination reduces the cost of an allocation enough that removing it is worth less than it once was, which is why the optimization’s value depends on the collector’s design rather than on the compiler alone.

The two mechanisms are complements, not substitutes. A collector makes allocation cheap; escape analysis makes it unnecessary. The cases where allocation remains expensive even with a good collector, namely large objects, objects that survive, and objects that trigger collection, are mostly the cases where the object escapes and the analysis cannot help. The cases where the analysis helps are the small, short-lived, non-escaping ones, which are exactly the ones a generational collector handles most cheaply. The optimization therefore pays best when the collector is weak, which is an uncomfortable fact for any runtime that has invested in both.