Channels ▼

Walter Bright

Dr. Dobb's Bloggers

Escape Analysis

October 30, 2008

Consider the following code in the D programming language:

int* foo()
{
    int x = 3;
    return &x;
}

For most of us, this kind of thing causes the red lights and sirens to go off, bad programmer! What's happening is that variable x is allocated on the stack, and once the function foo() returns that allocation is no longer valid, and that slot in
memory that used to hold x may be used for something else. Still referring to it
through the pointer will cause erratic behavior, memory corruption, and sometimes very hard to find bugs. This problem is known as a reference escaping its scope.

A decent compiler will diagnose such code - the D compiler spits out:

test.d(4): Error: escaping reference to local variable x

And you and I would never write such code, no sirree. But it can happen in less obvious ways:

int* bar(int* p) { return p; }

int* foo()
{
    int x = 3;
    return bar(&x);
}

or:

void abc(int x, int** p) { *p = &x; }

I don't know of any compiler that will pick these up. The more complicated the code, the harder it is to follow the logic and see if there are any escaping
references. Although I illustrated the issue using pointers, code that uses references is just as vulnerable.

We care about this because escaping reference bugs, though rare, are very expensive in terms of trying to detect, track down, and correct. Given a million line program, how can we verify that it does not have such problems?

Trying to detect such cases is called escape analysis.

One way to do it is the way Java does - by simply not allowing pointers or references to local variables. That works, but one is giving up a powerful feature. Maybe we can have our cake and eat it, too.

Consider the function declaration:

T foo(int* p);

How can we tell if it is safe to pass the address of a local to it? We can't. Hopefully, the documentation for foo() will say if it squirrels away the pointer or not, but I wouldn't want to bet on that documentation being correct. We could examine the implementation of foo(), but that isn't always possible. foo() could be implemented by some library we don't have the source code to. It could be a virtual function, so by definition we don't know what any overriding function might do. It might be a pointer to a function where we cannot know the implementation.

The only solution is to make the escaping characteristic part of the function signature. For D, we are looking at a design that creates a parameter storage class called scope:

T foo(scope int* p);

The presence of scope means that the function will not allow the parameter,
or anything reachable through that parameter, to escape from the scope of the function. The scope storage class can be applied to the parameters or the 'this' reference (for member functions). Initially, this will be a promise by the implementor of foo(), but it should be entirely possible for the compiler to perform escape analysis using data flow analysis techniques on the implementation of foo() to ensure it. The caller of the function will know that a reference to a local variable can be safely passed as a scope parameter. A million line program can be automatically verified as being free of escaping reference bugs.

Thanks to Bartosz Milewski for his help in reviewing this.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video