www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - How does Rebindable suppress the compiler's optimizations for

reply SimonN <eiderdaus gmail.com> writes:
std.typecons.Rebindable!(immutable A) is implemented as:

     private union {
         immutable(A) original;
         A stripped;
     }

     ... trusted assignment operators...

      property inout(immutable(A)) get()  trusted pure nothrow 
 nogc inout
     {
         return original;
     }

     alias get this;

This conforms with the D safety spec: All access to the unsafe 
union goes through the  trusted get() and the trusted assignment 
operators.

     Rebindable!(immutable A) r = a1;
     // r.original is a1
     r = a2;
     // r.original is a2

But the compiler may assume that immutable variables -- such as 
the immutable(A) original -- never change and thus may optimize 
code. Since immutable(A) original is assignable in the union, 
such optimization would produce wrong behavior: In the final 
line, the compiler could think that r.original is a1 without 
examining r.original.

How does Rebindable prevent the compiler from optimizing 
according to immutable's rules?
Feb 14 2019
next sibling parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Thursday, 14 February 2019 at 23:55:18 UTC, SimonN wrote:

 std.typecons.Rebindable!(immutable A) is implemented as:

     private union {
         immutable(A) original;
         A stripped;
     }

     ... trusted assignment operators...

      property inout(immutable(A)) get()  trusted pure nothrow 
  nogc inout
     {
         return original;
     }

     alias get this;

 This conforms with the D safety spec: All access to the unsafe 
 union goes through the  trusted get() and the trusted 
 assignment operators.

     Rebindable!(immutable A) r = a1;
     // r.original is a1
     r = a2;
     // r.original is a2

 But the compiler may assume that immutable variables -- such as 
 the immutable(A) original -- never change and thus may optimize 
 code. Since immutable(A) original is assignable in the union, 
 such optimization would produce wrong behavior: In the final 
 line, the compiler could think that r.original is a1 without 
 examining r.original.

 How does Rebindable prevent the compiler from optimizing 
 according to immutable's rules?


It's easy. You cannot use immutable as the only basis of 
optimization.
You need to proof actual immutability via data-flow-analysis over 
the whole life-time of your immutable.
When you cannot guarantee actual immutability (within the frame 
of interest) don't perform optimizations which are dependent on 
it.

So much for the theory, in practice I think that most 
optimizations based on immutable are disabled.
Think of immutable as hint for the programmer, not for the 
compiler.
Feb 14 2019
parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Thursday, February 14, 2019 11:59:31 PM MST Stefan Koch via Digitalmars-
d-learn wrote:

 On Thursday, 14 February 2019 at 23:55:18 UTC, SimonN wrote:

 std.typecons.Rebindable!(immutable A) is implemented as:
     private union {

         immutable(A) original;
         A stripped;

     }

     ... trusted assignment operators...

      property inout(immutable(A)) get()  trusted pure nothrow

  nogc inout

     {

         return original;

     }

     alias get this;

 This conforms with the D safety spec: All access to the unsafe
 union goes through the  trusted get() and the trusted
 assignment operators.

     Rebindable!(immutable A) r = a1;
     // r.original is a1
     r = a2;
     // r.original is a2

 But the compiler may assume that immutable variables -- such as
 the immutable(A) original -- never change and thus may optimize
 code. Since immutable(A) original is assignable in the union,
 such optimization would produce wrong behavior: In the final
 line, the compiler could think that r.original is a1 without
 examining r.original.

 How does Rebindable prevent the compiler from optimizing
 according to immutable's rules?


 It's easy. You cannot use immutable as the only basis of
 optimization.
 You need to proof actual immutability via data-flow-analysis over
 the whole life-time of your immutable.
 When you cannot guarantee actual immutability (within the frame
 of interest) don't perform optimizations which are dependent on
 it.

 So much for the theory, in practice I think that most
 optimizations based on immutable are disabled.
 Think of immutable as hint for the programmer, not for the
 compiler.


The type system is supposed to guarantee and be able to rely on immutable
never mutating. That's pretty much the whole point. Honestly, I'm pretty
sure that Rebindable technically violates the type system to do what it
does. However, I would expect that the use of a union would tend to kill
compiler optimizations given how tricky things get with those, so I wouldn't
expect that to be a problem. But yeah, I suspect that the compiler doesn't
do a lot of optimizations based on immutable anyway. I don't know for sure,
but it usually seems to be the case that the optimizations that D could get
from its type system end up being theoretical rather than actual whenever
anyone looks into it.

- Jonathan M Davis
Feb 15 2019
prev sibling parent reply Kagamin <spam here.lot> writes:
Union is just a pretty cast, type system guarantees don't hold 
for it.
Feb 15 2019
next sibling parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Friday, February 15, 2019 3:06:34 AM MST Kagamin via Digitalmars-d-learn 
wrote:

 Union is just a pretty cast, type system guarantees don't hold
 for it.


Well, technically, what's supposed to be the case is that when you cast, the
type system guarantees still hold but it's up to the programmer to make sure
that they do - just like how it's up to the programmer to ensure that
 trusted code is really  safe.

Rebindable is a pretty weird case with what it's doing, but I'm pretty sure
that it's actually violating the type system with what it does in that you
can't rely on the value of the immutable reference itself not being mutated
even though it's immutable. The type system guarantees for what the
reference refers to are maintained but not the guarantees for the actual
reference. In practice, I don't think that it's actually a problem, but in
principle, it's violating the type system, and a particularly aggressive
optimizer could make a bad assumption. However, given that a union is
involved, and as such the "cast" is built into the type, I question that any
optimizer would ever make the wrong assumption about Rebindable.

- Jonathan M Davis
Feb 15 2019
prev sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Fri, Feb 15, 2019 at 03:50:33AM -0700, Jonathan M Davis via
Digitalmars-d-learn wrote:

 On Friday, February 15, 2019 3:06:34 AM MST Kagamin via Digitalmars-d-learn 
 wrote:

 Union is just a pretty cast, type system guarantees don't hold for
 it.


 
 Well, technically, what's supposed to be the case is that when you
 cast, the type system guarantees still hold but it's up to the
 programmer to make sure that they do - just like how it's up to the
 programmer to ensure that  trusted code is really  safe.


Currently the compiler will automatically mark any code as  system that
tries to access a union field that involves a pointer overlapping with a
non-pointer.  So you cannot just get away from  safe just by using a
union.

In the same vein, I think any attempt to access a union that contains
overlapping immutable / non-immutable fields should automatically taint
the immutable value somehow so that no unsafe optimizations happen based
on immutability.  But that gets into the tricky territory of what
happens if you assign an overlapping immutable field to an immutable
local variable, and then access the local variable -- will the compiler
optimize based on immutable, which may be invalid because of the union?

I'm tempted to say that a union that mixes immutable / mutable ought to
be illegal.  How can you possibly guarantee anything about immutability
if it overlaps with mutable fields??  It makes no sense.  At the very
least, such code should be automatically  system.  At the  system level
sometimes you have to do exactly this -- e.g., the GC may allocate a
segment of memory for an immutable variable, but during the pointer scan
the GC has a mutable reference to the immutable memory (it has to, since
at some point when the memory is collected the GC has to be able to
reassign it to mutable data again), and it's basically a matter of trust
that that GC doesn't go about modifying immutable data.  (Which brings
up interesting questions about how immutability might interact with a
moving / compacting GC that may need to rewrite potentially immutable
pointers. But that's tangential to this discussion.)

So anyway, all of this seems to suggest that optimizations based on
immutable really only can take place meaningfully within  safe code,
provided we make accessing immutables in union with mutables a  system
operation.  All interactions between immutable-optimized  safe code and
potentially immutable-breaking  system code would then be forced to take
place through  trusted APIs, which would seem to be the correct design.



 Rebindable is a pretty weird case with what it's doing, but I'm pretty
 sure that it's actually violating the type system with what it does in
 that you can't rely on the value of the immutable reference itself not
 being mutated even though it's immutable. The type system guarantees
 for what the reference refers to are maintained but not the guarantees
 for the actual reference. In practice, I don't think that it's
 actually a problem, but in principle, it's violating the type system,
 and a particularly aggressive optimizer could make a bad assumption.
 However, given that a union is involved, and as such the "cast" is
 built into the type, I question that any optimizer would ever make the
 wrong assumption about Rebindable.


[...]

It probably only means that current D compilers aren't optimizing based
on immutable like they're supposedly able to.  If/when optimizers start
taking advantage of this, we're going to see UB in many more places than
we may realize currently.

I think the correct approach is to restrict immutable optimizations to
only  safe code, and force all immutable casts, including accessing
immutables in unions where they might overlap with mutables, a  system
operation, thus mandating any interaction with immutable optimizations
via  trusted interfaces.


T

-- 
In order to understand recursion you must first understand recursion.
Feb 15 2019
parent SimonN <eiderdaus gmail.com> writes:
Thanks for the detailed answers!

Yes, I accept that immutable guarantees should be implemented 
only during  safe that doesn't call into  trusted.

On Friday, 15 February 2019 at 18:59:36 UTC, H. S. Teoh wrote:

 At the very least, such [union] code should be automatically 
  system.


Sensible.


 Honestly, I'm pretty sure that Rebindable technically
 violates the type system to do what it does.


Hmm, I remember we discussed this, and I feel the same now about 
Rebindable. Either the spec gets extra rules for  trusted or 
unions, or Rebindable generates latent bugs.


 Think of immutable as hint for the programmer, not for the 
 compiler.


Right, if the compilers don't use it yet, I'm fine with that 
interpretation. It's merely strange that we have this very 
restrictive const/immutable that is advertized to help 
optimization, but then the compiler won't take advantage. Let's 
see how this develops in the long term, whether the spec gets 
clearer on the allowed optimization.
Feb 15 2019