Escape analysis

Incompiler optimization,escape analysisis a method for determining the dynamic scope ofpointers– where in the program a pointer can be accessed. It is related topointer analysisandshape analysis.

When a variable (or an object) is allocated in asubroutine,apointerto the variable canescapeto otherthreadsof execution, or to calling subroutines. If an implementation usestail calloptimization (usually required forfunctional languages), objects may also be seen as escaping tocalledsubroutines. If a language supports first-classcontinuations(as doSchemeandStandard ML of New Jersey), portions of thecall stackmay also escape.

If a subroutine allocates an object and returns a pointer to it, the object can be accessed from undetermined places in the program – the pointer has "escaped". Pointers can also escape if they are stored in global variables or other data structures that, in turn, escape the current procedure.

Escape analysis determines all the places where a pointer can be stored and whether the lifetime of the pointer can be proven to be restricted only to the current procedure and/or thread.

Optimizations

A compiler can use the results of escape analysis as a basis for optimizations:

• Convertingheap allocationstostack allocations.If an object is allocated in a subroutine, and a pointer to the object never escapes, the object may be a candidate for stack allocation instead of heap allocation. In garbage-collected languages this can reduce how often the collector needs to run.
• Synchronization elision.If an object is found to be accessible from one thread only, operations on the object can be performed without synchronization.
• Breaking up objectsorscalar replacement.An object may be found to be accessed in ways that do not require the object to exist as a sequential memory structure. This may allow parts (or all) of the object to be stored in CPU registers instead of in memory.

Practical considerations

Inobject-orientedprogramming languages,dynamic compilersare particularly good candidates for performing escape analysis. In traditionalstatic compilation,method overridingcan make escape analysis impossible, as any called method might be overridden by a version that allows a pointer to escape. Dynamic compilers can perform escape analysis using the available information on overloading, and re-do the analysis when relevant methods are overridden by dynamic code loading.

The popularity of theJava programming languagehas made escape analysis a target of interest. Java's combination of heap-only object allocation, built-in threading, the SunHotSpotdynamic compiler, andOpenJ9'sjust-in-time compiler(JIT) creates a candidate platform for escape analysis related optimizations (seeEscape analysis in Java). Escape analysis is implemented in Java Standard Edition 6. Some JVMs support a stronger variant of escape analysis calledpartial escape analysisthat makes scalar replacement of an allocated object possible even if the object escapes in some paths of a function.

Example (Java)

classMain{
publicstaticvoidmain(String[]args){
example();
}
publicstaticvoidexample(){
Foofoo=newFoo();//alloc
Barbar=newBar();//alloc
bar.setFoo(foo);
}
}

classFoo{}

classBar{
privateFoofoo;
publicvoidsetFoo(Foofoo){
this.foo=foo;
}
}

In this example, two objects are created (commented with alloc), and one of them is given as an argument to a method of another. The methodsetFoo()stores a reference to a received Foo object. If the Bar object was on the heap then the reference to Foo would escape. But in this case a compiler can determine, with escape analysis, that the Bar object itself does not escape the invocation ofexample().As a result, the reference to Foo cannot escape either, and the compiler can safely allocate both objects on the stack.

Examples (Scheme)

In the following example, the vectorpdoes not escape intog,so it can be allocated on the stack and then removed from the stack before callingg.

(define(fx)
(let((p(make-vector10000)))
(fill-vector-with-good-stuffp)
(g(vector-refp7023))))

If, however, we had

(define(fx)
(let((p(make-vector10000)))
(fill-vector-with-good-stuffp)
(gp)))

then eitherpwould need to be allocated on the heap or (ifgis known to the compiler whenfis compiled, and behaves well) allocated on the stack in such a fashion that it can remain in place whengis called.

If continuations are used to implement exception-like control structures, escape analysis can often detect this to avoid having to actually allocate a continuation and copy the call stack into it. For example, in

;;Reads scheme objects entered by the user. If all of them are numbers,
;;returns a list containing all of them in order. If the user enters one that
;;is not a number, immediately returns #f.
(define(getnumlist)
(call/cc(lambda(continuation)
(define(get-numbers)
(let((next-object(read)))
(cond
((eof-object?next-object)'())
((number?next-object)(consnext-object(get-numbers)))
(else(continuation#f)))))
(get-numbers))))

escape analysis will determine that the continuation captured bycall/ccdoesn't escape, so no continuation structure needs to be allocated, and invoking the continuation by callingcontinuationcan be implemented by unwinding the stack.

See also

• Alias analysis
• Pointer analysis
• Shape analysis