Escape analysis (full scope analysis proposal)

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Thu Nov 6 20:36:55 PST 2008


Michel Fortin wrote:
> 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.
>    }

Well how about this:

int * p;
float * q;
if (condition) {
     int x; p = &x;
} else {
     float y; q = &y;
}

Houston, we have a problem.

You can of course patch that little rule in a number of ways, but really 
at the end of the day what happens only inside a function is 
uninteresting. The main challenge is making the analysis scalable to 
multiple functions.

> 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;
>    }

Well this pretty much hamstrings pointers. You can take addresses of 
things inside a function but you can't pass them around. Moreover, 
people disliked the stealth dynamic allocation when delegates are being 
used; you are adding more of those.

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

IMHO this may be made to work. I personally prefer the system in which 
ref is safe and pointers are permissive. The system you are referring to 
makes ref and pointer of the same power, so we could as well dispense 
with either. But I'd be curious what others think of it. Notice how the 
discussion participants got reduced to you and me, and from what I saw 
that's not a good sign.


Andrei



More information about the Digitalmars-d mailing list