Escape analysis (full scope analysis proposal)

[Michel Fortin]

On 2008-11-04 12:36:15 -0500, Andrei Alexandrescu 
<SeeWebsiteForEmail at erdani.org> said:

>> I also belive we can completly avoid the use of named regions, such as:
>> 
>>     {
>>         int*`L p;
>>         L: { int x; p = x; }
>>     }
>> 
>> The problem illustrated above, of having a pointer outside the inner 
>> braces take the address of a variable inside it, solves itself if you 
>> allow a variable's region to be "promoted" automatically to a broader 
>> one. For instance, you could write:
>> 
>>     {
>>         int* p;
>>         { int x; p = x; }
>>     }
>> 
>> and p = x would make the compiler automatically extend the life of x up 
>> to p's region (local scope), although x wouldn't be accessible outside 
>> of the the inner braces other than by dereferencing p.
> 
> Cyclone has region subtyping which takes care of that.

Not the same way as I'm proposing. What cyclone does is make p 
undereferencable outside the scope of L. So if I add an assignment to p 
outside of L, it won't compile:

    {
        int*`L p;
        L: { int x; p = &x; }
		*p = 42; // error, dereferencing p outside of L.
    }

What I'm proposing is that such code extends the life of the storage of 
the local variable x to p's region:

    {
        int* p;
        { int x; p = &x; }
		*p = 42; // okay; per assignment to p, x lives up to p's scope.
		x; // error, x is not accessible in this scope, except through p.
    }

Follows that if p is outside of the local function, x needs to be 
allocated dynamically (just as closures currently do for each variable 
they use):

	void f(ref int* p)
    {
        int x;
		p = &x;
    }

If you want to make sure x never escapes the memory region associated 
to its scope, then you can declare x as scope and get a compile-time 
error when assigning it to p.

So, in essence, the system I propose is a little simpler because 
pointer variables just cannot point to values coming from a region that 
doesn't exist in the scope the pointer is declared. The guaranty I 
propose is that during the whole lifetime of a pointer, it points to 
either a valid memory region, or null. Cyclone's approach is to forbid 
you from dereferencing the pointer.

Combine this with my proposal to not have dynamic regions and we don't 
need named regions anymore. Perhaps the syntax could be made simpler 
with region names, but technically, we don't need them as we can always 
go the route of saying that a pointer value is "valid within the scope 
of variable_x". This is what I'm expressing with "scopeof(variable_x)" 
in my other examples, and I believe it is analogous to the 
"regions_of(variable_x)" in Cyclone, although Cyclone doesn't use it 
pervasively.

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