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?

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.

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

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

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

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.

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.