Escape analysis

[Steven Schveighoffer]

"Sergey Gromov" wrote
> Wed, 29 Oct 2008 11:52:14 -0400, Steven Schveighoffer wrote:
>
>> "Sergey Gromov" wrote
>>> Tue, 28 Oct 2008 23:33:53 -0400, Steven Schveighoffer wrote:
>>>> A very very common technique in Tango to save using heap allocation is 
>>>> to
>>>> declare a static array as a buffer, and then pass that buffer to be 
>>>> used
>>>> as
>>>> scratch space in a function (which is possibly virtual).
>>>>
>>>> This would be my golden use case that has to not allocate anything and
>>>> has
>>>> to work in order for any solution to be viable.
>>>>
>>>> Saying all reference types are noscope would prevent this, no?
>>>
>>> Allocation only happens when a stack variable reference escapes via a
>>> delegate.  A static array is not a stack variable, therefore the 
>>> compiler
>>> doesn't care if it escapes.
>>
>> A static array declared on the stack absolutely is a stack variable.
>>
>> An example (from Tango's integer to text converter):
>>
>> char[] toString (long i, char[] fmt = null)
>> {
>>         char[66] tmp = void;
>>         return format (tmp, i, fmt).dup;
>> }
>>
>> Without the dup, toString returns a pointer to it's own stack.  With a 
>> full
>> graph analysis, it can be proven that tmp doesn't escape, but without 
>> either
>> that or some crazy scope scheme, it would either allocate a closure, or 
>> fail
>> to compile.  Neither of those options are acceptable.
>
> There is no delegate, therefore nothing to allocate a closure for.  If
> tmp escapes, it is a compile-time error.

I was under the impression that closures are currently allocated if you 
return a reference to a stack variable, not just for delegates.  Maybe I'm 
wrong...

> If format() were pure it would be trivial to prove that tmp didn't
> escape.  If format() is not pure, and escape graph for it is not known,
> then issuing an error here would be too much of a breaking change, I
> agree.

format cannot be pure because it accepts mutable reference data.  It happens 
to be in the same file, so it probably would not be an issue because a graph 
is generated for the current file, but these are not the only cases that 
Tango has.

>>>> I think the graph has to be complete for this to be usable.  Otherwise,
>>>> it
>>>> becomes an unused feature.  Using .di files is optional.  I generally
>>>> don't
>>>> use them.
>>>
>>> For the incomplete graph to be usable, the compiler must assume the 
>>> worst
>>> for nodes with absent meta-info.  Therefore if you don't care to provide
>>> meta-info for your modules, it'll still work, though not as efficiently.
>>> On the other hand, if you supply .di files with your library and you do
>>> care enough, or you generate your .di files automatically, the meta-info
>>> will be present there saving some allocations for the user.
>>
>> This doesn't cover virtual functions or runtime-determined delegates. 
>> I'd
>> rather just have a separate meta file or have the meta data included in 
>> the
>> object file.  What is wrong with that?  Why must it be in the .di file? 
>> If
>> the compiler always generates these meta files, then the graph is always
>> complete.
>
> If you compile two files for the first time, and the first file imports
> the second one, where do you get that meta-data for the second file?
> What if you compile only one file, and that file imports another which
> wasn't compiled yet?  Either you construct meta-data on the fly, or
> require it included in the source, or assume it's not present (worst
> case).

My vote would be for compiling it on the fly.  The compiler already does 
parsing of the source file, so it can also generate this graph data.  It 
shouldn't be too hard a task.

Look, I agree that a graph analysis is the best possible solution.  It 
requires no work from the user, no extra specification, and it will solve 
the problem accurately.

But the current mode of compliation doesn't allow for that easily.  That's 
all I was saying.

-Steve