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

[Ali Çehreli via Digitalmars-d]

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.

I'm wondering whether that's the reason. If so, the compiler could prove 
that the type is used only once and not allocate the closure.

Note that although they look the same to us, S!(() => i) and S!(() => i) 
are different types to the compiler because the two lambdas are 
different anonymous objects, effectively making the struct template 
instances different.

Ali