Escape Analysis
written by Walter Bright
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.
Acknowledgements
Thanks to Bartosz Milewski for his help in reviewing this.