Escape analysis (full scope analysis proposal)

[Michel Fortin]

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

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.


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