Escape analysis (full scope analysis proposal)

[Michel Fortin]

On 2008-11-09 08:59:18 -0500, Christopher Wright <dhasenan at gmail.com> said:

> Michel Fortin wrote:
>> I don't see a problem at all. The compiler would expand the lifetime of 
>> x to the outer scope, and do the same for y. Basically, the compiler 
>> would make it this way in the compiled code:
>> 
>>     int * p;
>>     float * q;
>>     int x;
>>     float y;
>>     if (condition) {
>>         p = &x;
>>     } else {
>>         q = &y;
>>     }
> 
> In point of fact, it's expensive to extend the stack, so any compiler 
> would do that, even without escape analysis.

Indeed.


> On the other hand, what about nested functions? I don't think they'd 
> cause any trouble, but I'm not certain.

If you mean there could be a problem with functions referring to the 
pointer, I'd say that with properly propagated escape constrains, it's 
safe. But it's an interesting case nonetheless. Consider this:

    int * p;
    if (condition) {
    	int x;
    	p = &x;
    } else {
    	int y;
    	p = &y;
    }
	int f() { return *p; }
	return &f;

Now returning &f forces p to dynamically allocate on the heap, which 
puts a constrain on p forcing it to point only to variables on the 
heap, which in turn forces x and y to be allocated on the heap.

I haven't verified, but I'm pretty certain this doesn't work correctly 
with the current dynamic closures in D2 however (because escape 
analysis doesn't see through pointers).

Also, if you made p point to a value it received in argument, and the 
scope of that argument isn't the global scope, it'd be an error. For 
instance, this wouldn't work:

	int delegate() foo1(int* arg) {
		int f() { return *arg; }
		return &f; // error, returned closure may live longer than *arg; need 
constraint
	}

Constraining the lifetime of the returned value to be no longer than 
the one of the argument would allow it to work safely (disregard the 
bizarre syntax for expressing the constrain on the delegate):

	int delegate(arg)() foo2(int* arg) {
		int f() { return *arg; }
		return &f;
		// ok, returned closure lifetime guarantied to be
		// at most as long as the lifetime of *arg.
	}

	int globalInt;
	int delegate() globalDelegate;

	void bar() {
		int localInt;
		int delegate() localDelegate;

		globalDelegate = foo2(globalInt); // ok, same lifetime
		localDelegate = foo2(globalInt); // ok, delegate lifetime shorter
		localDelegate = foo2(localInt); // ok, same lifetime

		globalDelegate = foo2(localInt);
		// ok, but forces bar to allocate localInt on the heap since otherwise
		// localInt lifetime would be shorter than lifetime of the delegate
	}

Note that what I want to demonstrate is that the compiler can see 
pretty clearly what needs and what doesn't need to be allocated on the 
heap to guaranty safety. Whether we decide it does allocate 
automatically or it generate an error is of lesser concern to me. (And 
I'll add that some other issues with templates may make this automatic 
allocation scheme unworkable.)

-- 
Michel Fortin
michel.fortin at michelf.com
http://michelf.com/