Escape analysis (full scope analysis proposal)

[Robert Jacques]

On Fri, 31 Oct 2008 11:11:26 -0400, Steven Schveighoffer  
<schveiguy at yahoo.com> wrote:

> "Michel Fortin" wrote
>> Basically, by documenting better the interfaces in a machine-readable  
>> way,
>> we are freed of other burdens the compiler can now take care of. In
>> addition, we have better defined interfaces and the compiler has a lot
>> more room to optimize things.
>
> But the burden you have left for the developer is a tough one.  You have  
> to
> analyze the inputs and function calls from a function and determine which
> variable depends on what.  This is a perfect problem for a tool to solve.

Tools can't handle function pointers, which is why escape analysis has  
been limited to dynamic laguages like Java so far.

>> The problem is that as soon as you have a function declaration without  
>> the
>> body, the lint tool won't be able to tell you if it escapes or not.
>
> This I agree is a problem.  In fact, without specifications in the  
> function
> things like interfaces would be very difficult to determine scope-ness at
> compile time.
>
> The only way I can see to solve this is to do it at link time.  When you
> link, piece together the parts of the graph that were incomplete, and  
> see if
> they all work.  It would be a very radical change, and might not even  
> work
> with the current linkers.  Especially if you want to do shared libraries,
> where the linker is builtin to the OS.

One option is link time compilation, although that doesn't apply to shared  
libs.

> A related question: how do you handle C functions?

Hope and pray? (i.e. The same way C functions and immutable types are  
handled now.)

>> So, without a way to specify the requested scope of the parameters,  
>> you'll
>> very often have holes in your escape analysis that will propagate down  
>> the
>> caller chain, preventing any useful conclusion.
>
> Yes, and if a function has mis-specified some of its parameters, then you
> have code that doesn't compile.  Or the function itself won't compile,  
> and
> you need to do some more manual analysis.  Imagine a function that calls  
> 5
> or 6 other functions with its parameters.  And there are multiple  
> different
> dependencies you have to resolve.  That's a lot of analysis you have to  
> do
> manually.

Well, the same problem occurs with const today and just like const you'd  
have specific compilier errors to guide you.

>> I don't think it's bad to force interfaces to be well documented, and
>> documented in a format that the compiler can understand to find errors
>> like this.
>
> I think this concept is going to be really hard for a person to decipher,
> and really hard to get right.  We are talking about a graph dependency
> analysis, in which many edges can exist, and the vertices do not  
> necessarily
> have to be parameters.  This is not stuff for the meager developer  
> looking
> to get work done to have to think about.  I'd much rather have a tool  
> that
> does it, if not the compiler, then something else.  Or partial  
> analysis.  Or
> no analysis.  I agree it's good to have bugs caught by the compiler, but
> this solution requires too much work from the developer to be used.

Well, I'd guess most functions are either no escape or heap escape. Only  
functions that permit escape and want to play nice with stack variables  
need to do actual graph analysis. You'll note Walter's blog ignores this  
usage.

> Some fun puzzles for you to come up with a proper scope syntax to use:
>
> void f(ref int *a, int *b, int *c) { if(*b < *c) a = b;  else a = c;}

if( a.scope <= b.scope && a.scope <= c.scope )

> struct S
> {
>    int *v;
> }
>
> int *f2(S* s) { return s.v;}

int* f2(S* s) if( return.scope >= s.scope )

> void f3(ref int *a, ref int *b, ref int *c)
> {
>    int *tmp = a;
>    a = b; b = c; c = tmp;
> }

if ( a.scope == b.scope && a.scope == c.scope )

> -Steve
>
>

This is actually pretty straight forward as a = b implies a.scope <=  
b.scope.