Escape analysis (full scope analysis proposal)

[Michel Fortin]

On 2008-11-03 00:39:34 -0500, Andrei Alexandrescu 
<SeeWebsiteForEmail at erdani.org> said:

> But syntax is so little a part of it. I knew since age immemorial that 
> escape analysis is a bitch. I mean, everybody knows. Every once in a 
> while, I'd get lulled into the belief that things can get "a little 
> pregnant" in a sweet spot where the implementation isn't too hard, 
> limitations aren't too severe, and the language doesn't get too 
> complex. A couple of weeks ago was the (n + 1)th time that that 
> happened; I got encouraged that Walter was willing to tackle the task 
> of writing even a context/flow insensitive escape analyzer, and I also 
> got hope from "scope" being an easy way to express something about a 
> function. Ironically, it was your example that disabused me of my 
> mistaken belief.

Studying things more in depth often at first leave you with the 
impression that things are more complicated than they are. But after 
some time, you start to see a few common patterns and you can start to 
simplify and unify the concepts. Who would have thought some centuries 
ago that you could use the same math formulas to understand how an 
apple falls from a tree and how the Moon is orbiting around the Earth?

Perhaps it's a wise choice to forget about the idea and avoid wasting 
time on making things more complicated *if* they'll indeed make things 
more complicated. But right now I have the feeling that you're bailing 
out after a first try seeing things are more complicated than they 
first looked like, without even digging further to see if there are 
common patterns that would allow simplification and unification with 
other concepts further down the line.


> That leaves me in the position that if someone wants to show me there 
> *is* such a sweet spot, they better come with a very airtight argument.

I believe I have a complete solution by placing the scope annotations 
on the type as I will explain below, alghouth I don't have a good 
syntax for it. My solution doesn't revolve around escape analysis but 
more about explicit scoping constrains (which could and should be made 
implicit through escape analysis, but that isn't stricly needed for the 
scoping system to work).

And, as a bonus, it can provide a way for the compiler to completly 
free the programmer from having to explicity dynamically allocate 
things in his program (because all scopes are known at compile-time, 
the compiler can tell what needs to be dynamically allocated and what 
doesn't need to).

So, are you interested?

 - - -

Personally, I'd implement scoping rules by reusing the framework that 
was built for const. I'd make scope like const (a type modifier, is it 
called like that?), but with the additional variation that each scope 
qualifier could be bound to another variable's scope that would become 
a child scope (needed for a swap function for instance).

Basically, each pointer or reference in a type can get its own scope 
qualifier. Scope restriction work in the reverse direction however: the 
data you point to impose scoping restrictions to pointers leading to 
it, not the other way around like with transitive const. You can have a 
scope pointer to no-scope data. You can't have a no-scope pointer 
pointing to scope data. So "scope(char)*" makes little sense, since 
"char" being scope, the pointer needs to be scope too. This makes more 
sense: "char scope(*)", a scope pointer to non-scope data. Basically, 
scope should be more and more restricted while reading a type from left 
to right, so you could have something like "char scope(* 
scopeof(x)(*))".

There's of course a need for a better syntax than the above. But, I 
think the ugly syntax above conceptualize pretty well a good solution 
to the scoping problem that could extend arrays, structs and classes. 
We sure should make it prettier, perhaps by imposing restrictions like 
forcing all pointers in the type to be of the most restrictive scope 
which would avoid placing scope annotations everywhere in it. But in 
essence, I think this solution is workable.

>From there, we can define scope comparisons, and scope restriction 
checks to apply when asigning variables to one another. Scope 
restriction checks could allow restriction propagation when doing 
escape analysis.

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.


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