Escape analysis (full scope analysis proposal)

[Andrei Alexandrescu]

Michel Fortin wrote:
> On 2008-11-03 11:21:08 -0500, Andrei Alexandrescu 
> <SeeWebsiteForEmail at erdani.org> said:
> 
>> Michel Fortin wrote:
>>> On 2008-11-03 00:39:34 -0500, Andrei Alexandrescu 
>>> <SeeWebsiteForEmail at erdani.org> said:
>> [snip]
>>> If you want more details, I can provide them as I've thought of the 
>>> matter a lot in the last few days. I just don't have the time to 
>>> write about everything about it right now.
>>
>> It may be wise to read some more before writing some more. As far as I
>> understand it, your idea, if taken to completion, is very much like
>> region analysis as defined in Cyclone.
>>
>> http://www.research.att.com/~trevor/papers/pldi2002.pdf
>>
>> Here are some slides:
>>
>> http://www.cs.washington.edu/homes/djg/slides/cyclone_pldi02.ppt
> 
> Pretty interesting slides.
> 
> Yeah, that looks pretty much like my idea, in concept, where I call 
> regions scopes. But I'd have made things simpler by having only local 
> function regions (on the stack) and the global region 
> (dynamically-allocated garbage-collected heap), which mean you don't 
> need templates at all for dealing with them.

I don't understand that part.

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

> If the pointer was copied outside of the function, then the only 
> available broader region to promote x to would be the heap. I think this 
> should be done automatically, although it could be decided to require 
> dynamic allocation to be explicit too; this is of little importance to 
> the escape analysis and scopre restriction problem.
> 
> 
>> My hope was that we can obtain an approximation of that idea by defining
>> only two regions - "inside this function" and "outside this function".
>> It looks like that's not much gain for a lot of pain.
>>
>> So the question is - should we introduce region analysis to D, or not?
> 
> I think we should at least try. I don't think we need everything Cyclone 
> does however; we can and should keep things simpler.

I'm not sure how to read this. For what I can tell, Cyclone's region 
analysis does not introduce undue complexity. It does the minimum 
necessary to prove that function manipulating pointers are safe. So if 
you suggest a simpler scheme, then either it is more limiting, less 
safe, or both. What are the tradeoffs you are thinking about, and how do 
they compare to Cyclone?


Andrei