Home › Compilers & runtimes › IR & program analysis
algorithm medium

Escape analysis

Problem A managed runtime allocates every object on a shared heap and lets a garbage collector clean up. Most short-lived objects never leave the function that made them, yet each still costs allocation, collector work and sometimes a lock.

Prove which allocations never outlive or leave their creator, then put them on the stack, split them into scalars, or drop their locks.

roughly linear in graph size for one pass over a function; a fixpoint over call summaries adds passes
escape-analysisstack-allocationscalar-replacementlock-elisionjitinterprocedural
Overview

Every object a function allocates is either private to it, visible to its callees, or reachable from global state. The analysis labels each allocation with one of these states. A private object needs no heap: it can live in the frame, dissolve into registers, and skip its locks. The proof must hold for every execution, so any doubt resolves to "escapes" and the program stays correct.

Key facts

Use when

  • JVM and Go backend services: fewer heap allocations, less collector work per request.
  • Latency-critical code on managed runtimes (order books, game loops, audio/frame callbacks): keep hot paths free of allocation.
  • Data pipelines on the JVM (iterators, tuples, boxed keys in map/filter chains): temporaries can vanish after inlining.
  • Related, not the same algorithm: static security tools track whether tainted data leaves a scope with the same escape-style reachability.

Avoid when

  • Objects are long-lived and shared anyway, or you need guaranteed placement (use value types or arenas).

Deep dive

How it works

Parts:

  • Escape lattice — NoEscape < ArgEscape < GlobalEscape, joined with max.
  • Connection graph (Choi et al. 1999) — nodes for objects, references, fields and actual arguments; edges for points-to, deferred (assignment) and field links.
  • Seeds — facts from instructions: return and call arguments give ArgEscape, a store to a static or global gives GlobalEscape.
  • Propagation — a holder's state flows to everything reachable through its fields until nothing changes.
  • Method summary — per parameter: leaks to heap, to result, or not; reused at call sites.
  1. Build the graph (or a "locations" graph, as Go does) from the function body: one node per allocation site, an edge per assignment or store.
  2. Seed states: returned values and call arguments to ArgEscape, globally stored values to GlobalEscape.
  3. Propagate along field edges to a fixpoint (finite lattice, monotone step: it terminates).
  4. For a call, use the callee summary if known; for an unknown or virtual callee assume the argument leaks.
  5. Rewrite: NoEscape objects are stack-allocated, or scalar-replaced if every use is a field access; their locks are removed. ArgEscape objects can still lose locks.
 A ──field f──► B        return A   =>  A: Arg,    B: Arg    (holder -> held)
 store global = B  =>  B: Global,  A stays Arg              (never held -> holder)

Flow-insensitive vs flow-sensitive. Flow-insensitive analysis (Go, the code below) ignores statement order: one state per allocation. Simple and fast, but imprecise when an object escapes on one branch only. Flow-sensitive analysis keeps a state per program point on the control-flow graph (often in SSA form) and is a dataflow analysis. Graal's partial escape analysis (Stadler et al., CGO 2014) goes further: the object stays virtual (scalar-replaced) on the paths where it does not escape and is materialized only on the branch that leaks it.

Interprocedural summaries. Compilers compute a summary per function once (Go calls them parameter tags: data flow from parameters to the heap and to results) and apply it at each static call site. Inlining has the same effect by pasting the callee in. Virtual calls need a call graph or a speculation; pointer disambiguation draws on alias analysis.

Why conservative is safe. Imprecision may only move an object up the lattice, which means "heap allocate as before". The unsafe error is the opposite: stack placement while a reference outlives the frame.

JIT interplay. A JIT compiles against the current class hierarchy and observed types. When an assumption breaks, deoptimization rebuilds interpreter frames, but a scalar-replaced object has no heap copy. The deopt metadata therefore records how to re-create each virtual object from its scalars (the theme of Kotzmann and Mössenböck, VEE 2005).

Code

A small IR and an intraprocedural, flow-insensitive analysis. Unknown calls give ArgEscape; return gives ArgEscape (leaves the method, not the thread).

/// Variables are numbered; `New(v)` allocates an object held by variable `v`.
#[derive(Clone, Debug)]
pub enum Inst {
    New(usize),
    Store(usize, usize),    // obj.field = val
    Load(usize, usize),     // dst = obj.field
    Return(usize),
    Call(&'static str, Vec<usize>), // callee unknown: no summary
    StoreGlobal(usize),
}

/// Order matters: derive(PartialOrd) gives NoEscape < ArgEscape < GlobalEscape.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub enum Esc { NoEscape, ArgEscape, GlobalEscape }

pub fn analyze(code: &[Inst], nvars: usize) -> Vec<Esc> {
    let mut st = vec![Esc::NoEscape; nvars];
    // Flow-insensitive: seed states from the instructions, order ignored.
    for i in code {
        match i {
            Inst::Return(v) => st[*v] = st[*v].max(Esc::ArgEscape),
            Inst::Call(_, args) => for a in args { st[*a] = st[*a].max(Esc::ArgEscape) },
            Inst::StoreGlobal(v) => st[*v] = Esc::GlobalEscape,
            _ => {}
        }
    }
    // Edge holder -> held: whatever holder reaches, held reaches too.
    let mut edges: Vec<(usize, usize)> = Vec::new();
    for i in code {
        if let Inst::Store(o, v) = i { edges.push((*o, *v)); }
    }
    // A load result may be anything ever stored into that object.
    for i in code {
        if let Inst::Load(d, o) = i {
            let held: Vec<usize> =
                edges.iter().filter(|e| e.0 == *o).map(|e| e.1).collect();
            for h in held { edges.push((*d, h)); }
        }
    }
    loop {
        let mut changed = false;
        for &(from, to) in &edges {
            if st[to] < st[from] { st[to] = st[from]; changed = true; }
        }
        if !changed { return st; } // monotone on a finite lattice: terminates
    }
}

use Esc::*;
use Inst::*;
fn main() {
    // 0 = temp
    assert_eq!(analyze(&[New(0), Store(0, 0)], 1)[0], NoEscape);
    // 0 stored into returned 1
    let s = analyze(&[New(0), New(1), Store(1, 0), Return(1)], 2);
    assert_eq!((s[0], s[1]), (ArgEscape, ArgEscape));
    // global store
    assert_eq!(analyze(&[New(0), StoreGlobal(0)], 1)[0], GlobalEscape);
    // unknown call, and a purely local sibling stays NoEscape
    let s = analyze(&[New(0), New(1), Call("f", vec![0])], 2);
    assert!(s[0] >= ArgEscape && s[1] == NoEscape);
    // chain a -> b -> global, stores listed before the global store
    let s = analyze(&[New(0), New(1), New(2), Store(0, 1), Store(1, 2), StoreGlobal(0)], 3);
    assert_eq!(s, vec![GlobalEscape; 3]);
    // load: c = a.f where a.f = b; c returned => b escapes
    let s = analyze(&[New(0), New(1), Store(0, 1), Load(2, 0), Return(2)], 3);
    assert_eq!(s[1], ArgEscape);
    println!("ok");
}

Complexity and constants

  • Time: a seed pass plus sweeps over edges; the loop above is O(edges x lattice height), height 2. Graph size is linear in allocations plus stores.
  • Cost drivers: summaries (each function analysed once) and virtual calls (unknown targets collapse to "leaks"). Paid at compile time, not per request.
  • Payoff per eliminated allocation: no header or field bytes written, no later collection; measure with allocation counters.

Efficiency

  • Cost: analysis cost is compile-time work, order of linear in function size after inlining; the saved work is one heap allocation, its later collection and any monitor operations per eliminated object. Bound: allocation rate and memory bandwidth for the program, compiler speed for the analysis.
  • Levers:
    • Inline small callees — turns arg-escape into no-escape — when the callee is short and monomorphic.
    • Keep temporaries local, out of fields and collections — they stay no-escape — in hot code.
    • Inspect and A/B: go build -gcflags=-m; on HotSpot -XX:-DoEscapeAnalysis (default on in the JDK I checked, as are EliminateAllocations and EliminateLocks) — when tuning.
    • Partial escape analysis — keeps allocations off non-leaking paths — when objects escape only on rare branches.
  • Naive → standard → state of the art:
    • Allocate everything on the heap · one allocation and one collector visit per object.
    • Flow-insensitive per-function analysis with summaries (Go, HotSpot C2) · allocation removed only if it never escapes on any path.
    • Partial escape analysis with materialization at the escape point (Graal) · allocation removed on every non-escaping path.

Implementation notes

  • Go: go build -gcflags=-m prints decisions such as moved to heap: x, &x escapes to heap, x does not escape and leaking param: p (strings taken from the compiler source; repeat -m for more detail).
  • Scalar replacement needs every use to be a field access at a known offset; a non-inlined call taking the object blocks it.
  • Lock elision applies to objects that never leave the thread: monitors on them are removed (HotSpot EliminateLocks).
  • Record deopt state for every virtual object live at a safepoint.

Pitfalls

  • Storing an object into a field, a collection or a channel makes it escape: the idiom you thought was cheap is not.
  • Interface calls hide the callee; variables captured by a closure escape if it does.
  • Flow-insensitive means a global store on any branch makes the object global everywhere.
  • Arg-escape is not "safe to share across threads"; it only means the object left its creator.
  • Not a guarantee: a compiler update or a larger method can bring allocations back.

Variants and alternatives

Region or arena allocationwins when you want explicit, guaranteed lifetimes (Rust, C++, Go arenas where available).
Value types and structswin when the language has them: no identity, no analysis.
Generational GCcheap young-object collection; makes eliminated allocations a smaller win, but not zero.Mark-sweepnon-moving collector; every removed object also saves marking and sweeping.
Ownership typesprove lifetimes in the type system instead of by analysis.

In production

  • HotSpot C2 (JVM) — escape analysis with scalar replacement and lock elision, on by default in the checked JDK.
  • Graal compiler — partial escape analysis (Stadler et al.).
  • Go gc compiler — stack versus heap decision per variable, with -gcflags=-m diagnostics.
  • V8 TurboFan — has an escape-analysis pass for JavaScript.

Implementations

namelangrepoinstallverdictlicencehealthas_ofnotes
HotSpot C2C++openjdk/jdkbrew install openjdk————opto/escape.cpp; EA + scalar replacement + lock elision
Graal compilerJavaoracle/graal—————partial escape analysis; part of GraalVM
Go gc compilerGogolang/gobrew install go————cmd/compile/internal/escape
V8 TurboFanC++v8/v8—————src/compiler/escape-analysis.cc

Sources

  • Choi, Gupta, Serrano, Sreedhar, Midkiff, Escape analysis for Java, OOPSLA 1999. paper
  • Stadler, Würthinger, Mössenböck, Partial Escape Analysis and Scalar Replacement for Java, CGO 2014. paper
  • Kotzmann, Mössenböck, Escape analysis in the context of dynamic compilation and deoptimization, VEE 2005. paper
  • Go FAQ, "How do I know whether a variable is allocated on the heap or the stack?" go.dev/doc/faq
  • Go compiler escape analysis source. code

Builds on

SSA formOptimizing compilers must know, for every use of a variable, which assignment produced its value; with variables reassigned across branches and loops this gets expensive and error-prone. SSA makes that link explicit.
call graph construction · plannedBuilding call graphs with dynamic dispatch resolution (CHA, RTA)
Dataflow analysisOptimizers and checkers must know facts that hold at every point of a function, such as which variables may still be read or which values were already computed. This is for computing such whole-function facts.

Used by

Systems (1):

jit vm

Alternatives and related

alias analysis · plannedDecide whether two pointers may refer to the same memory (Andersen, Steensgaard, type-based) to enable optimizations
Control-flow graphA compiler or analysis tool that needs to know which code can run after or before a given instruction has only a flat list of instructions. This gives it the structure that optimization and checking passes work on.JIT compilationA program is executed from a compact form (bytecode, an AST, a query plan, a regex) that is slow to run but starts at once. Most of it runs rarely, a small part runs constantly, and compiling everything up front costs too much startup time and memory.DeoptimizationA runtime compiles fast code that bets on how a program behaves (types, call targets, class layout). When a bet turns out wrong mid-execution, the program must continue correctly from exactly where it was, not crash or give wrong answers.Generational garbage collectionA long-running program allocates huge numbers of short-lived objects next to a few long-lived ones; tracing the whole heap every cycle wastes time on data that has not changed, so reclaiming memory is too slow or pauses too long.Mark-sweep garbage collectionA long-running program allocates linked objects and cannot say when each is dead; it must reclaim unreachable memory automatically, including cyclic structures, without the programmer freeing anything.Closures and upvaluesA function body uses a variable from an enclosing function, and the function value is called after the enclosing call has returned. Language implementors must keep that variable alive and shared without heap-allocating every local.