In
compiler optimization, escape analysis is a method for determining the dynamic scope of
pointers where in the program a pointer can be accessed. It is related to
pointer analysis and
shape analysis.
When a variable (or an object) is allocated in a
subroutine, a
pointer to the variable can ''escape'' to other
threads of execution, or to calling subroutines. If an implementation uses
tail call
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recu ...
optimization (usually required for
functional languages), objects may also be seen as escaping to ''called'' subroutines. If a language supports first-class
continuation
In computer science, a continuation is an abstract representation of the control state of a computer program. A continuation implements ( reifies) the program control state, i.e. the continuation is a data structure that represents the computat ...
s (as do
Scheme A scheme is a systematic plan for the implementation of a certain idea.
Scheme or schemer may refer to:
Arts and entertainment
* ''The Scheme'' (TV series), a BBC Scotland documentary series
* The Scheme (band), an English pop band
* ''The Schem ...
and
Standard ML of New Jersey
Standard ML of New Jersey (SML/NJ; Standard Meta-Language of New Jersey) is a free and open-source compiler and programming environment for the Standard ML programming language. Aside from its runtime system, which is written in C, SML/NJ is writ ...
), portions of the
call stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, program stack, control stack, run-time stack, or ...
may 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:
[T. Kotzmann and H. Mössenböck, “Escape analysis in the context of dynamic compilation and deoptimization,” in Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, New York, NY, USA, 2005, pp. 111–120.]
* ''Converting
heap allocations to
stack 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 objects'' or ''scalar 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
In
object-oriented programming languages,
dynamic compilers are particularly good candidates for performing escape analysis. In traditional
static compilation
In computer science, a static library or statically-linked library is a set of routines, external functions and variables which are resolved in a caller at compile-time and copied into a target application by a compiler, linker, or binder, produc ...
,
method overriding can 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 the
Java programming language has made escape analysis a target of interest. Java's combination of heap-only object allocation, built-in threading, the Sun
HotSpot
Hotspot, Hot Spot or Hot spot may refer to:
Places
* Hot Spot, Kentucky, a community in the United States
Arts, entertainment, and media Fictional entities
* Hot Spot (comics), a name for the DC Comics character Isaiah Crockett
* Hot Spot (Tr ...
dynamic compiler, and
OpenJ9's
just-in-time compiler (JIT) creates a candidate platform for escape analysis related optimizations (see
Escape analysis in Java). Escape analysis is implemented in Java Standard Edition 6. Some JVMs support a stronger variant of escape analysis called ''partial escape analysis'' that makes scalar replacement of an allocated object possible even if the object escapes in some paths of a function.
Example (Java)
class Main
class Foo
class Bar
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 method
setFoo()
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 of
example()
. 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 vector ''p'' does not escape into ''g'', so it can be allocated on the stack and then removed from the stack before calling ''g''.
(define (f x)
(let ((p (make-vector 10000)))
(fill-vector-with-good-stuff p)
(g (vector-ref p 7023))))
If, however, we had
(define (f x)
(let ((p (make-vector 10000)))
(fill-vector-with-good-stuff p)
(g p)))
then either ''p'' would need to be allocated on the heap or (if ''g'' is known to the compiler when ''f'' is compiled, and behaves well) allocated on the stack in such a fashion that it can remain in place when ''g'' is 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) (cons next-object (get-numbers)))
(else (continuation #f)))))
(get-numbers))))
escape analysis will determine that the continuation captured by ''call/cc'' doesn't escape, so no continuation structure needs to be allocated, and invoking the continuation by calling ''continuation'' can be implemented by unwinding the stack.
See also
*
Alias analysis
Alias may refer to:
* Pseudonym
* Pen name
* Nickname
Arts and entertainment Film and television
* ''Alias'' (2013 film), a 2013 Canadian documentary film
* ''Alias'' (TV series), an American action thriller series 2001–2006
* ''Alias the J ...
*
Pointer analysis
*
Shape analysis
References
{{DEFAULTSORT:Escape Analysis
Static program analysis
Articles with example Java code