Escape analysis
Encyclopedia
In programming language compiler optimization
Compiler optimization
Compiler optimization is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the amount of memory occupied...

 theory, escape analysis is a method for determining the dynamic scope of pointers. It is related to pointer analysis
Pointer analysis
In computer science pointer analysis, or points-to analysis, is a static code analysis technique that establishes which pointers, or heap references, can point to which variables or storage locations. It is often a component of more complex analyses such as escape analysis...

 and shape analysis
Shape analysis (software)
In program analysis, a shape analysis is a static code analysis technique that discovers and verifies properties of linked, dynamically allocated data structures in computer programs. It is typically used at compile time to find software bugs or to verify high-level correctness properties of...

.

When a variable (or an object) is allocated in a subroutine
Subroutine
In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....

, a pointer to the variable can escape to other thread
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...

s of execution, or to calling subroutines. 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:
  • Converting heap allocations to stack allocations
    Stack-based memory allocation
    Stacks in computing architectures are regions of memory where data is added or removed in a last-in-first-out manner.In most modern computer systems, each thread has a reserved region of memory referred to as its stack. When a function executes, it may add some of its state data to the top of the...

    . 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.

  • 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
Object-oriented programming language
This is a list of object-oriented programming programming languages.-Languages with object-oriented features:*ABAP*Ada 95*AmigaE*BETA*Blue*Boo*C++*C#*COBOL*Cobra*ColdFusion*Common Lisp*COOL*CorbaScript*Clarion*CLU*Curl*D*Dylan*E*Eiffel...

 programming languages, dynamic compiler
Dynamic compilation
Dynamic compilation is a process used by some programming language implementations to gain performance during program execution. Although the technique originated in the Self programming language, the best-known language that uses this technique is Java...

s are particularly good candidates for performing escape analysis. In traditional static compilation, 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
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...

 has made escape analysis a target of interest. Java's combination of heap-only object allocation, built-in threading, and the Sun HotSpot
HotSpot
HotSpot is a Java virtual machine for desktops and servers, maintained and distributed by Oracle Corporation. It features techniques such as just-in-time compilation and adaptive optimization designed to improve performance.-History:...

 dynamic compiler creates a candidate platform for escape analysis related optimizations (see Escape analysis in Java). Escape analysis is implemented in Java Standard Edition 6.

Example (Java)


class A {
final int finalValue;

public A( B b ) {
super;
b.doSomething( this ); // this escapes!
finalValue = 23;
}

int getTheValue {
return finalValue;
}
}

class B {
void doSomething( A a ) {
System.out.println( a.getTheValue );
}
}


In this example, the constructor for class A passes the new instance of A to B.doSomething. As a result, the instance of A—and all of its fields—escapes the scope of the constructor.

See also

  • Alias analysis
    Alias analysis
    Alias analysis is a technique in compiler theory, used to determine if a storage location may be accessed in more than one way. Two pointers are said to be aliased if they point to the same location....

  • Pointer analysis
    Pointer analysis
    In computer science pointer analysis, or points-to analysis, is a static code analysis technique that establishes which pointers, or heap references, can point to which variables or storage locations. It is often a component of more complex analyses such as escape analysis...

  • Shape analysis
    Shape analysis (software)
    In program analysis, a shape analysis is a static code analysis technique that discovers and verifies properties of linked, dynamically allocated data structures in computer programs. It is typically used at compile time to find software bugs or to verify high-level correctness properties of...

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK