Compiler analysis of single-use types? Escape analysis of types?

[Dicebot via Digitalmars-d]

On Thursday, 18 August 2016 at 06:29:07 UTC, Ali Çehreli wrote:
> On 08/17/2016 05:59 PM, Dicebot wrote:
> > On 08/18/2016 12:25 AM, Ali Çehreli wrote:
> >> I'm wondering whether there is such a thing as single-use of
> a type in
> >> compiler technology. I think if the compiler could determine
> that a type
> >> is used only once, it could apply optimizations.
> >>
> >> A colleague of mine raised the issue of D's use of the GC
> even for
> >> seemingly local delegates. For example, even though
> everything remains
> >> local for the following lambda, countAbove() cannot be @nogc:
> >>
> >> auto countAbove(int[] a, int limit) {
> >>     return a.filter!(x => x >= limit).count();
> >> }
> >>
> >> The reason is due to the fact that filter() returns a struct
> object that
> >> takes the delegate as an alias template parameter. Here is a
> reduction
> >> of the issue with my understanding in comments:
> >
> > I believe actual reason is that aliased lambda has to
> allocate a closure
> > because it refers to stack local variable (limit).
>
> Right.
>
> > This compiles just fine:
> >
> > auto countAbove(int[] a, int limit) @nogc {
> >     return a.filter!(x => x >= 1).count();
> > }
>
> However, as my test code demonstrates, even when the lambda 
> refers to stack local variable, closure is NOT allocated in the 
> case of the function call. As far as I can tell, the actual 
> reason for the allocation is the struct object that filter() 
> returns.
>
> I am trying to understand why the struct object requires the 
> closure allocation. I made myself believe that this is the 
> reason: Being an alias template parameter, the lambda is a part 
> of the type (the instantiation of the struct template). Even 
> though the compiler could determine that the single object does 
> not escape, its type can be used again.

Your main mistake seems to be an expectation of complete flow 
analysis in compiler while in fact it is virtually non-existent. 
DMD frontend can't prove that references to stack don't escape in 
all but most simple cases (where all involved code is fully 
inlined and no actual function/struct has to be generated).

For example, in your struct case it can't know that you won't 
eventually return that struct instance from function or do 
something similar. Such analysis is simply not performed, thus it 
has to generate code conservatively. The problem you mention is 
likely to be present with current frontend too but that is not a 
crucial technical limitation on its own because fully qualified 
type of such S instantiation would include function-local context 
and compiler can use it to tell that type can be optimized as 
function-local unless any references escape.

 From my own encounters vast majority of issues of that kind could 
be solved by one of two relatively simple solutions:

1) Being able to capture context in lambda by value (Right now I 
tend to use custom structs with `opCall` instead of built-in 
lambdas for such cases)

2) Allowing compiler to treat `pragma(inline, true)` functions as 
ones that never generate own object code and thus can be analyzed 
in usage contexts separately.