Escape analysis

[Steven Schveighoffer]

"Sergey Gromov" wrote
> Walter Bright wrote:
>> The first step is, are function parameters considered to be escaping by
>> default or not by default? I.e.:
>>
>> void bar(noscope int* p);    // p escapes
>> void bar(scope int* p);      // p does not escape
>> void bar(int* p);            // what should be the default?
>>
>> What should be the default? The functional programmer would probably
>> choose scope as the default, and the OOP programmer noscope.
>
> I'm for safe defaults.  Programs shouldn't crash for no reason.

If safe defaults means 75% performance decrease, I'm for using unsafe 
defaults that are safe 99% of the time, with the ability to make them 100% 
safe if needed.

> Here are my thoughts on escape analysis.  Sorry if they're obvious.
>
> I think it is possible to detect whether a reference escapes or not in
> the absence of function calls by analyzing an expression graph.

Yes, but not in D, since import uses uncompiled files as input.

> Assigning to a global state variable is an ultimate escape.

Agree there.

> In the worst case, when only the current function can be analyzed and no
> meta-info is available about other functions, the compiler must assume a
> reference escapes if it is passed as an argument to another function.
> This is the current D2 behavior.

This leads to the current situation, where you have a huge performance 
decrease for little or no gain in reliability.

> Pure functions provide some meta-info because any reference passed as an
> argument can only escape via a reference return value or other mutable
> reference arguments.  This makes escape analysis possible even after an
> unknown pure function is called.

Good point.  Easy analysis on pure functions.

> For any function in a tree of imported modules the compiler could keep
> some meta-data about which argument escapes where, if at all.  This way
> even regular functions can participate in escape analysis without
> blowing it up.

Where is the data kept?  It must be in the object file, and d imports must 
then read the object file for api instead of the source file.  I don't think 
it's worth anything to break the single file for imports/code model. 
Requiring a .di file is a little iffy as it is today.

> An argument to a virtual function call always escapes by default.  It
> may be possible to declare an argument as non-escaping (scope?) and
> compiler should then enforce non-escaping contract upon any overriding
> functions.

This is tricky, because most class member functions are virtual, so you are 
forced to litter all your functions with escaping/non-escaping syntax.  To 
be accurate you need to define the escape graph in the signature, which will 
be a PITA.  What would be worse is to not have a way to express the complete 
graph.

Another solution is that a derived function must have the same expression 
graph or a tighter one than the base class'.  But without being able to 
store the graph with the compiled code (and having the compiler import the 
metadata instead of the source file), this is a moot point.

> An argument to a function declared as a prototype always escapes by
> default.  It may be possible for the compiler to export some meta-info
> along with the prototype when a .di file is generated, whether an
> argument is guaranteed to not escape, or maybe even detailed info about
> which argument escapes where, to mimic the compile-time meta-info.

No, the di file might not be auto-generated.  You also now back to a 
separate import and source file, like C has.  I think in order for this to 
work, the graph and object code must be stored in the same file that is 
imported.

> The expression graph analysis should be the first step towards safe
> stack closures.

I would agree with this.  But I don't think it's happening in the near 
future.  And I hope it's not done through .di files.

In the meantime, to make D2 a systems language again, it should drop 
conservative closures.

-Steve