www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Compiler analysis of single-use types? Escape analysis of types?

reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
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:

void foo(alias dg)() {
     dg();
}

struct S(alias dg) {
     void bar() {
         dg();
     }
}

void main() {
     int i;

     /* The following call can be marked as  nogc because foo() does
      * not escape the delegate. (It can indeed appear in  nogc
      * code today.) */
     foo!(() => i)();

     /* The following expression does not escape the delegate
      * either. (Note that object 's' is not escaped.) So, one would
      * expect the following code be  nogc as well. However, 2.071 does
      * allocate from the GC. */
     S!(() => i) s;

     /* Although one would expect that last line above to be  nogc as
      * well, I can see one potential issue there that warrants the GC
      * use: Although no reference to the local 'i' is escaped, the
      * *type* of 's' can be obtained perhaps by typeof() to make
      * another object of the same type, which may be escaped. */
     typeof(s) s2;

     /* s2 carries another alias to local 'i' through its *type*! */
}

If the compiler could see that 's' is not escaped *and* it's type is 
used only once, then the expression with the second lambda could be 
 nogc as well. Does that make sense? Is there such a thing?

Thank you,
Ali
Aug 17 2016
next sibling parent reply Dicebot <public dicebot.lv> writes:
From: Dicebot <public dicebot.lv>
Newsgroups: d,i,g,i,t,a,l,m,a,r,s,.,D
Subject: Re: Compiler analysis of single-use types? Escape analysis of types?
References: <np2knd$1r3k$1 digitalmars.com>
In-Reply-To: <np2knd$1r3k$1 digitalmars.com>

--exJMXgDSegalDuQD3tWEt3K9c6PRATIk5
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable

On 08/18/2016 12:25 AM, Ali =C3=87ehreli 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 typ=


e

 is used only once, it could apply optimizations.
=20
 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:
=20
 auto countAbove(int[] a, int limit) {
     return a.filter!(x =3D> x >=3D limit).count();
 }
=20
 The reason is due to the fact that filter() returns a struct object tha=


t

 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). This compiles just fin=
e:

auto countAbove(int[] a, int limit)  nogc {
    return a.filter!(x =3D> x >=3D 1).count();
}


--exJMXgDSegalDuQD3tWEt3K9c6PRATIk5--
Aug 17 2016
next sibling parent reply Yuxuan Shui <yshuiv7 gmail.com> writes:
On Thursday, 18 August 2016 at 00:59:43 UTC, Dicebot wrote:

 On 08/18/2016 12:25 AM, Ali Çehreli wrote:

 [...]


 I believe actual reason is that aliased lambda has to allocate 
 a closure because it refers to stack local variable (limit). 
 This compiles just fine:

 auto countAbove(int[] a, int limit)  nogc {
     return a.filter!(x => x >= 1).count();
 }


I wish we could have something like "scoped" delegates...
Aug 17 2016
parent reply Jacob Carlborg <doob me.com> writes:
On 2016-08-18 03:21, Yuxuan Shui wrote:


 I wish we could have something like "scoped" delegates...


You mean:

void foo(scope void delegate() dg);

Or:

void bar(void delegate() dg);

scope void delegate() a = {};
bar(a);

-- 
/Jacob Carlborg
Aug 18 2016
parent Yuxuan Shui <yshuiv7 gmail.com> writes:
On Thursday, 18 August 2016 at 07:04:41 UTC, Jacob Carlborg wrote:

 On 2016-08-18 03:21, Yuxuan Shui wrote:


 I wish we could have something like "scoped" delegates...


 You mean:

 void foo(scope void delegate() dg);

 Or:

 void bar(void delegate() dg);

 scope void delegate() a = {};
 bar(a);


Delegates are pretty much a struct that holds references, right? 
So they are kinda like pointers.

I wish I can enforce scope rules (DIP1000) on them. For example, 
scope delegate should not be able to hold reference to variables 
with shorter lifetime than the delegate itself. With this we then 
could have delegates in  nogc code.
Aug 18 2016
prev sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
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
Aug 17 2016
parent Dicebot <public dicebot.lv> writes:
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.
Aug 18 2016
prev sibling parent Meta <jared771 gmail.com> writes:
On Wednesday, 17 August 2016 at 21:25:00 UTC, 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:

 void foo(alias dg)() {
     dg();
 }

 struct S(alias dg) {
     void bar() {
         dg();
     }
 }

 void main() {
     int i;

     /* The following call can be marked as  nogc because foo() 
 does
      * not escape the delegate. (It can indeed appear in  nogc
      * code today.) */
     foo!(() => i)();

     /* The following expression does not escape the delegate
      * either. (Note that object 's' is not escaped.) So, one 
 would
      * expect the following code be  nogc as well. However, 
 2.071 does
      * allocate from the GC. */
     S!(() => i) s;

     /* Although one would expect that last line above to be 
  nogc as
      * well, I can see one potential issue there that warrants 
 the GC
      * use: Although no reference to the local 'i' is escaped, 
 the
      * *type* of 's' can be obtained perhaps by typeof() to make
      * another object of the same type, which may be escaped. */
     typeof(s) s2;

     /* s2 carries another alias to local 'i' through its 
 *type*! */
 }

 If the compiler could see that 's' is not escaped *and* it's 
 type is used only once, then the expression with the second 
 lambda could be  nogc as well. Does that make sense? Is there 
 such a thing?

 Thank you,
 Ali


If I understand correctly, this is exactly what linear types are 
(i.e., what Rust uses... or maybe that was affine types, which 
are similar). D actually does have fairly primitive support for 
affine types with ` disable this()`, opAssign and `this (this)`.
Aug 17 2016