> On Oct 11, 2016, at 4:48 PM, Andrew Trick <atr...@apple.com> wrote: >> On Oct 11, 2016, at 2:14 PM, John McCall <rjmcc...@apple.com> wrote: >> >>> On Oct 11, 2016, at 11:49 AM, Joe Groff <jgr...@apple.com> wrote: >>>> On Oct 11, 2016, at 11:44 AM, John McCall <rjmcc...@apple.com> wrote: >>>> >>>>> On Oct 11, 2016, at 11:22 AM, Joe Groff <jgr...@apple.com> wrote: >>>>>> On Oct 11, 2016, at 11:19 AM, Andrew Trick <atr...@apple.com> wrote: >>>>>> >>>>>> >>>>>>> On Oct 11, 2016, at 11:02 AM, Joe Groff <jgr...@apple.com> wrote: >>>>>>> >>>>>>> >>>>>>>> On Oct 11, 2016, at 10:50 AM, John McCall <rjmcc...@apple.com> wrote: >>>>>>>> >>>>>>>>> On Oct 11, 2016, at 10:10 AM, Joe Groff via swift-dev >>>>>>>>> <swift-dev@swift.org> wrote: >>>>>>>>>> On Oct 10, 2016, at 6:58 PM, Andrew Trick <atr...@apple.com> wrote: >>>>>>>>>> >>>>>>>>>> >>>>>>>>>>> On Oct 10, 2016, at 6:23 PM, Joe Groff <jgr...@apple.com> wrote: >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>>> On Oct 7, 2016, at 11:10 PM, Andrew Trick via swift-dev >>>>>>>>>>>> <swift-dev@swift.org> wrote: >>>>>>>>>>>> ** World 1: SSA @inout >>>>>>>>>>>> >>>>>>>>>>>> Projecting an element produces a new SILValue. Does this SILValue >>>>>>>>>>>> have >>>>>>>>>>>> it's own ownership associated with it's lifetime, or is it derived >>>>>>>>>>>> from it's parent object by looking through projections? >>>>>>>>>>>> >>>>>>>>>>>> Either way, projecting any subelement requires reconstructing the >>>>>>>>>>>> entire aggregate in SIL, through all nesting levels. This will >>>>>>>>>>>> generate a massive amount of SILValues. Superficially they all need >>>>>>>>>>>> their own storage. >>>>>>>>>>>> >>>>>>>>>>>> [We could claim that projections don't need storage, but that only >>>>>>>>>>>> solves one side of the problem.] >>>>>>>>>>>> >>>>>>>>>>>> [I argue that this actually obscures the producer/consumer >>>>>>>>>>>> relationship, which is the opposite of the intention of moving to >>>>>>>>>>>> SSA. Projecting subelements for mutation fundamentally doesn't make >>>>>>>>>>>> sense. It does make sense to borrow a subelement (not for >>>>>>>>>>>> mutation). It also makes sense to project a mutable storage >>>>>>>>>>>> location. The natural way to project a storage location is by >>>>>>>>>>>> projecting an address...] >>>>>>>>>>> >>>>>>>>>>> I think there's a size threshold at which SSA @inout is manageable, >>>>>>>>>>> and might lead to overall better register-oriented code, if the >>>>>>>>>>> aggregates can be exploded into a small number of individual >>>>>>>>>>> values. The cost of reconstructing the aggregate could be mitigated >>>>>>>>>>> somewhat by introducing 'insert' instructions for aggregates to >>>>>>>>>>> pair with the projection instructions, similar to how LLVM has >>>>>>>>>>> insert/extractelement. "%x = project_value %y.field; %x' = >>>>>>>>>>> transform(%x); %y' = insert %y.field, %x" isn't too terrible >>>>>>>>>>> compared to the address-oriented formulation. Tracking ownership >>>>>>>>>>> state through projections and insertions might tricky; haven't >>>>>>>>>>> thought about that aspect. >>>>>>>>>>> >>>>>>>>>>> -Joe >>>>>>>>>> >>>>>>>>>> We would have to make sure SROA+mem2reg could still kick in. If that >>>>>>>>>> happens, I don’t think we need to worry about inout ownership >>>>>>>>>> semantics anymore. A struct_extract is then essentially a borrow. >>>>>>>>>> It’s parent’s lifetime needs to be guaranteed, but I don’t know if >>>>>>>>>> the subobject needs explicit scoping in SIL since there’s no inout >>>>>>>>>> scopes to worry about and nothing for the runtime to do when the >>>>>>>>>> scope ends . >>>>>>>>>> >>>>>>>>>> (Incidentally, this would never happen to a CoW type that has a >>>>>>>>>> uniqueness check—to mutate a CoW type, it’s value needs to be in >>>>>>>>>> memory). >>>>>>>>> >>>>>>>>> Does a uniqueness check still need to be associated with a memory >>>>>>>>> location once we associate ownership with SSA values? It seems to me >>>>>>>>> like it wouldn't necessarily need to be. One thing I'd like us to >>>>>>>>> work toward is being able to reliably apply uniqueness checks to >>>>>>>>> rvalues, so that code in a "pure functional" style gets the same >>>>>>>>> optimization benefits as code that explicitly uses inouts. >>>>>>>> >>>>>>>> As I've pointed out in the past, this doesn't make any semantic sense. >>>>>>>> Projecting out a buffer reference as a true r-value creates an >>>>>>>> independent value and therefore requires bumping the reference count. >>>>>>>> The only query that makes semantic sense is "does this value hold a >>>>>>>> unique reference to its buffer", which requires some sort of language >>>>>>>> tool for talking abstractly about values without creating new, >>>>>>>> independent values. Our only existing language tool for that is >>>>>>>> inout, which allows you to talk about the value stored in a specific >>>>>>>> mutable variable. Ownership will give us a second and more general >>>>>>>> tool, borrowing, which allows you abstractly refer to immutable >>>>>>>> existing values. >>>>>>> >>>>>>> If we have @owned values, then we also have the ability to do a >>>>>>> uniqueness check on that value, don't we? This would necessarily >>>>>>> consume the value, but we could conditionally produce a new >>>>>>> known-unique value on the path where the uniqueness check succeeds. >>>>>>> >>>>>>> entry(%1: @owned $X): >>>>>>> is_uniquely_referenced %1, yes, no >>>>>>> yes(%2: /*unique*/ @owned $X): >>>>>>> // %2 is unique, until copied at least >>>>>>> no(%3: @owned %X): >>>>>>> // %3 is not >>>>>>> >>>>>>> -Joe >>>>>> >>>>>> You had to copy $X to make it @owned. >>>>> >>>>> This is the part I think I'm missing. It's not clear to me why this is >>>>> the case, though. You could have had an Array return value that has never >>>>> been stored in memory, so never needed to be copied. If you have an >>>>> @inout memory location, and we enforce the single-owner property on >>>>> inouts so that they act like a Rust-style mutable borrow, then you should >>>>> also be able to take the value out of the memory location as long as you >>>>> move a value back in before the scope of the inout expires. >>>> >>>> I'm not sure what your goal is here vs. relying on borrowing. Both still >>>> require actual analysis to prove uniqueness at any given point, as you >>>> note with your "until copied at least" comment. >>>> >>>> Also, from a higher level, I'm not sure why we care whether a value that >>>> was semantically an r-value was a unique reference. CoW types are >>>> immutable even if the reference is shared, and that should structurally >>>> straightforward to take advantage of under any ownership representation. >>> >>> My high-level goal was to get to a point where we could support in-place >>> optimizations on unique buffers that belong to values that are semantically >>> rvalues at the language level. It seems to me that we ought to be able to >>> make 'stringA + B + C + D' as efficient as '{ var tmp = stringA; tmp += B; >>> tmp += C; tmp += D; tmp }()' by enabling uniqueness checks and in-place >>> mutation of the unique-by-construction results of +-ing strings. If you >>> think that works under the borrow/inout-in-memory model, then no problem; >>> I'm also trying to understand the design space a bit more. >> >> Ah right, that optimization. The problem here with using borrows is that >> you really want static enforcement that both (1) you've really got ownership >> of a unique reference (so e.g. you aren't just forwarding a borrowed value >> down) and (2) you're not accidentally copying the reference and so ruining >> the uniqueness check. Those are hard guarantees to get with an >> implicitly-copyable type. >> >> I wonder if it would make more sense to make copy-on-write buffer references >> a move-only type, so that as long as you were just working with the raw >> reference (as opposed to the CoW aggregate, which would remain copyable) it >> wouldn't get implicitly copied anymore. You could have mutable and >> immutable buffer reference types, both move-only, and there could be a >> consuming checkUnique operation on the immutable one that, I dunno, returned >> an Either of the mutable and immutable versions. >> >> For CoW aggregates, you'd need some @copied attribute on the field to make >> sure that the CoW attribute was still copyable. Within the implementation >> of the type, though, you would be projecting out the reference immediately, >> and thereafter you'd be certain that you were borrowing / moving it around >> as appropriate. >> >> I dunno. It's an idea. >> >> John. > > So, to project a MutabableArrayStorage we would need to explode an owned > Array into an owned ConstArrayStorage (forwarding its value). Then pass it to: > isUniqueOwned(ConstArrayStorage) -> either<MutableArrayStorage, > ConstArrayStorage> > > Making it move-only should give us the necessary guarantee for Erik's CoW > proposal: Nothing can mutate the storage as long as ConstArrayStorage is > alive. > > Then how would we get MutabableArrayStorage from inout Array? > We can project the address of an inout ConstArrayStorage from the inout > Array. Then we need to magically cast its address to *MutableArrayStorage, > and somehow tie it to the inout ConstArrayStorage scope.
Well, makeUnique would be a ConstArrayStorage -> MutableArrayStorage function, and when you were done, you would demote to ConstArrayStorage and write back. It's perhaps a little ugly. John. _______________________________________________ swift-dev mailing list swift-dev@swift.org https://lists.swift.org/mailman/listinfo/swift-dev