> On Oct 19, 2016, at 6:36 PM, Andrew Trick via swift-dev <swift-dev@swift.org>
> wrote:
>
>>
>> On Oct 19, 2016, at 10:13 AM, Dave Abrahams via swift-dev
>> <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
>>
>>
>> on Tue Oct 18 2016, Erik Eckstein <swift-dev-AT-swift.org
>> <http://swift-dev-at-swift.org/>> wrote:
>>
>>>> On Oct 17, 2016, at 10:21 AM, Dave Abrahams <dabrah...@apple.com
>>>> <mailto:dabrah...@apple.com>> wrote:
>>>>
>>>>
>>>> on Mon Oct 17 2016, Erik Eckstein <eeckstein-AT-apple.com
>>>> <http://eeckstein-at-apple.com/>> wrote:
>>>>
>>>
>>>>> On Oct 16, 2016, at 2:05 PM, Dave Abrahams via swift-dev
>>>>> <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
>>>>>
>>>>>> on Thu Oct 13 2016, Joe Groff <swift-dev-AT-swift.org
>>>>>> <http://swift-dev-at-swift.org/> <http://swift-dev-at-swift.org/
>>>>>> <http://swift-dev-at-swift.org/>>> wrote:
>>>>>>
>>>>>>>> On Oct 11, 2016, at 4:48 PM, Erik Eckstein via swift-dev
>>>>>>>> <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
>>>>>>>>
>>>>>>>> This is a proposal for representing copy-on-write buffers in
>>>>>>>> SIL. Actually it’s still a draft for a proposal. It also heavily
>>>>>>>> depends on how we move forward with SIL ownership.
>>>>>>>> <CopyOnWrite.rst>
>>>>>>>> If you have any comments, please let me know.
>>>>>>>
>>>>>>> The SIL-level design seems sensible to me at a glance. At the language
>>>>>>> level, I think it would make more sense to treat this as an attribute
>>>>>>> on class types rather than on properties in structs using the class. I
>>>>>>> don't think many people reuse class definitions as both shared
>>>>>>> reference types and as value type payloads,
>>>>>>
>>>>>> Foundation does, or would if they could.
>>>>>>
>>>>>>> but beyond that, I think that making it an attribute of classes would
>>>>>>> put us into a better position to leverage the borrow model to enforce
>>>>>>> the "mutable-only-when-unique" aspect of COW implementations. John
>>>>>>> alluded to this in the "SIL address types and borrowing" thread:
>>>>>>>
>>>>>>>> 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.
>>>>>>>
>>>>>>> If 'copy-on-write' were a trait on classes, then we could distinguish
>>>>>>> unique and nonunique references to the class. A unique reference would
>>>>>>> act like a move-only type to prevent accidental loss of uniqueness.
>>>>>>
>>>>>> +1
>>>>>>
>>>>>>> We can also allow a copy-on-write class to have "mutating" methods,
>>>>>>> and only allow mutation on unique references. It seems to me like,
>>>>>>> exploring this direction, we could also come up with a way for the
>>>>>>> high-level value-semantics operations on the struct to statically
>>>>>>> indicate which methods are known to leave the value's buffers in a
>>>>>>> unique state, or which return values that are uniquely owned, which
>>>>>>> would give the optimizer more ability to avoid uniqueness checks
>>>>>>> across calls without relying on inlining and IPO.
>>>>>>
>>>>>> That's pretty cool. However, I think there's nothing to prevent any
>>>>>> mutating method from storing a copy of self in a global, so I think we'd
>>>>>> need some participation from the programmer (either an agreement not to
>>>>>> do that, or an explicit claim of uniqueness on exit) in order to
>>>>>> identify operations that create/preserve uniqueness.
>>>>>
>>>>> If a mutating reference (like self in a mutating method) is move-only
>>>>> then you would not be able to “copy” it to a global.
>>>>
>>>> Yes, a reference to a move-only type would work for this purpose.
>>>>
>>>>
>>>>>> On Oct 16, 2016, at 2:01 PM, Dave Abrahams via swift-dev
>>>>>> <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
>>>>>>
>>>>>>
>>>>>> on Tue Oct 11 2016, Erik Eckstein <swift-dev-AT-swift.org
>>>>>> <http://swift-dev-at-swift.org/>> wrote:
>>>>>>
>>>>>>> This is a proposal for representing copy-on-write buffers in
>>>>>>> SIL. Actually it’s still a draft for a proposal. It also heavily
>>>>>>> depends on how we move forward with SIL ownership.
>>>>>>>
>>>>>>> :orphan:
>>>>>>>
>>>>>>> .. highlight:: sil
>>>>>>>
>>>>>>> ===================================
>>>>>>> Copy-On-Write Representation in SIL
>>>>>>> ===================================
>>>>>>>
>>>>>>> .. contents::
>>>>>>>
>>>>>>> Overview
>>>>>>> ========
>>>>>>>
>>>>>>> This document proposes:
>>>>>>>
>>>>>>> - An ownership attribute to define copy-on-write (COW) buffers in Swift
>>>>>>> data
>>>>>>> types.
>>>>>>>
>>>>>>> - A representation of COW buffers in SIL so that optimizations can take
>>>>>>> benefit
>>>>>>> of it.
>>>>>>>
>>>>>>> The basic idea is to enable the SIL optimizer to reason about COW data
>>>>>>> types
>>>>>>> in the same way as a programmer can do.
>>>>>>> This means: a COW buffer can only be modified by its owning SIL value,
>>>>>>> because
>>>>>>> either it's uniquely referenced or the buffer is copied before modified.
>>>>>>>
>>>>>>> .. note::
>>>>>>> In the following the term "buffer" refers to a Swift heap object.
>>>>>>> It can be any heap object, not necessarily a “buffer” with e.g.
>>>>>>> tail-allocated elements.
>>>>>>>
>>>>>>> COW Types
>>>>>>> =========
>>>>>>>
>>>>>>> The basic structure of COW data types can be simplified as follows::
>>>>>>>
>>>>>>> class COWBuffer {
>>>>>>> var someData: Int
>>>>>>> ...
>>>>>>> }
>>>>>>>
>>>>>>> struct COWType {
>>>>>>> var b : COWBuffer
>>>>>>>
>>>>>>> mutating func change_it() {
>>>>>>> if (!isUniquelyReferenced(b)) {
>>>>>>> b = copy_buffer(b)
>>>>>>> }
>>>>>>> b.someData = ...
>>>>>>> }
>>>>>>> }
>>>>>>>
>>>>>>> Currently the COW behavior of such types is just defined by their
>>>>>>> implementation.
>>>>>>> But there is no representation of this special behavior in the SIL.
>>>>>>> So the SIL optimizer has no clue about it and cannot take advantage of
>>>>>>> it.
>>>>>>>
>>>>>>> For example::
>>>>>>>
>>>>>>> func foo(arr : [Int]) {
>>>>>>> x = arr[0]
>>>>>>> opaque_function()
>>>>>>> y = arr[0] // can RLE replace this with y = x?
>>>>>>> }
>>>>>>>
>>>>>>> If opaque_function() wants to change the contents of the array buffer
>>>>>>> it first
>>>>>>> has to copy it.
>>>>>>
>>>>>> ...or determine that it's uniquely-referenced.
>>>>>
>>>>> In this specific example, if opqaue_function holds a reference to arr’s
>>>>> buffer, the buffer is not
>>>>> uniquely-referenced.
>>>>
>>>> Right.
>>>>
>>>>>>
>>>>>>> But the optimizer does not know it so it has to conservatively assume
>>>>>>> that opaque_function() will write to the location of arr[0].
>>>>>>>
>>>>>>> Copy-on-write Ownership Attribute
>>>>>>> =================================
>>>>>>>
>>>>>>> This section proposes an ownership attribute to define a copy-on-write
>>>>>>> buffer.
>>>>>>>
>>>>>>> Swift Syntax
>>>>>>> ------------
>>>>>>>
>>>>>>> A COW buffer reference can be defined with a new ownership attribute
>>>>>>> for the
>>>>>>> buffer variable declaration (similar to “weak” and “unowned”)::
>>>>>>>
>>>>>>> struct COWType {
>>>>>>> copy_on_write var b : COWBuffer
>>>>>>>
>>>>>>> // ...
>>>>>>> }
>>>>>>>
>>>>>>> The ``copy_on_write`` attribute is purely used for optimization
>>>>>>> purposes.
>>>>>>> It does not change the semantics of the program.
>>>>>>
>>>>>> Presumably, it changes what code you can execute on `b` without invoking
>>>>>> traps or undefined behavior. Otherwise, the optimizer wouldn't be able
>>>>>> to do anything differently to take advantage of the annotation.
>>>>>
>>>>> That’s true.
>>>>>
>>>>>> What are the rules for writing code that uses `copy_on_write`?
>>>>>
>>>>> See below ("The rules for using ``copy_on_write`` and the built-ins are:”)
>>>>
>>>> Yeah, I got there, eventually. But just saying “doesn't change
>>>> semantics” at this point in the proposal leaves a gap, because it does
>>>> change semantic *requirements*. You should mention that.
>>>>
>>>>>>> .. note::
>>>>>>>
>>>>>>> “copy_on_write” is a working title. TODO: decide on the name.
>>>>>>> Maybe it should be a @-attribute, like @copy_on_write?
>>>>>>> Another question is if we should open this attribute for the public or
>>>>>>> just
>>>>>>> use it internally in the library, because violating the implied rules
>>>>>>> (see below) could break memory safety.
>>>>>>>
>>>>>>> Implementation
>>>>>>> --------------
>>>>>>>
>>>>>>> The ``copy_on_write`` references can be represented in the AST as a
>>>>>>> special
>>>>>>> ``StorageType``, just like how ``unowned`` and ``weak`` is represented.
>>>>>>> The canonical type of a ``CopyOnWriteStorageType`` would be the
>>>>>>> referenced
>>>>>>> buffer class type.
>>>>>>>
>>>>>>> In SIL the buffer reference will have type::
>>>>>>>
>>>>>>> $@sil_cow COWBuffer
>>>>>>>
>>>>>>> where ``COWBuffer`` is the type of the referenced heap object.
>>>>>>>
>>>>>>> Two conversion instructions are needed to convert from a ``@sil_cow``
>>>>>>> reference
>>>>>>> type to a regular reference type::
>>>>>>>
>>>>>>> cow_to_ref
>>>>>>> ref_to_cow
>>>>>>>
>>>>>>> Again, this is similar to ``ref_to_unowned`` and ``unowned_to_ref``.
>>>>>>>
>>>>>>> For example the SIL code for::
>>>>>>>
>>>>>>> var c: COWType
>>>>>>> let x = c.b.someData
>>>>>>>
>>>>>>> would be::
>>>>>>>
>>>>>>> %1 = struct_extract %1 : COWType, #COWType.b
>>>>>>> %2 = cow_to_ref %1 : $@sil_cow COWBuffer
>>>>>>> %3 = ref_element_addr %2 : $COWBuffer, #COWBuffer.someData
>>>>>>> %4 = load %3 : $*Int
>>>>>>>
>>>>>>> The ``ref_to_cow`` instruction is needed to store a new buffer
>>>>>>> reference into a
>>>>>>> COW type.
>>>>>>>
>>>>>>> COW Buffers and the Optimizer
>>>>>>> =============================
>>>>>>>
>>>>>>> A reference to a COW buffer gives the optimizer additional information:
>>>>>>>
>>>>>>> *A buffer, referenced by a @sil_cow reference is considered to be
>>>>>>> immutable
>>>>>>> during the lifetime of the reference.*
>>>>>>
>>>>>> This seems like much too broad a rule to allow inplace mutations of
>>>>>> uniquely referenced buffers.
>>>>>
>>>>> The point is that all mutations must be guarded by an is_unique, which
>>>>> takes the _address_ of the buffer reference as argument.
>>>>> And the optimizer considers this instruction as a potential write to the
>>>>> buffer reference.
>>>>> The effect is that the lifetime of a buffer reference (as a SIL value)
>>>>> will not outlive a is_unique - regardless if this is inside a called
>>>>> function or inlined.
>>>>
>>>> I don't see how that allows me to mutate a uniquely referenced buffer held
>>>> in a @sil_cow reference, given what you wrote above.
>>>
>>> You would not be able to get a reference to a mutable buffer by
>>> reading the COW type’s @sil_cow field. Instead you would only get
>>> such a reference as a result of the is_unique instruction/builtin. Or,
>>> of course, by creating a new buffer.
>>>
>>> I’m not sure if this was the question, though.
>>
>> I think it just comes down to precise phrasing. AFAICT, what you really
>> mean to say is something like
>>
>> A buffer cannot be directly mutated through a @sil_cow reference;
>> instead one must mutate it indirectly via the result of is_unique or
>> start_unique.
Exactly, that’s what I wanted to say.
>>
>> Saying that the buffer is “considered to be immmutable during the
>> lifetime of the reference” could be taken to mean that the compiler will
>> assume no mutations of the buffer can occur while the reference exists.
>> IIUC you are not planning to formally end the reference's lifetime at
>> the moment is_unique/start_unique returns.
>
> To clarify: I proposed an alternate approach in which the @sil_cow reference
> is only mutable during the Array’s @inout scope—to be automatically enforced
> by the compiler once @inout scopes are enforced. But the text in question is
> not referring to that approach, so your comments are on target.
After thinking about Joe’s suggestion (having the cow attribute on the class
type and make a reference to that type move-only), I’m more inclined to go with
the isUnique builtin. If such a reference can only be returned by isUnique, it
is really guaranteed that only a uniquely referenced buffer can be mutated.
With the inout approach, the programmer is not forced to make the uniqueness
check before modifying the buffer.
> -Andy
>
>>>
>>> Plus: we will have an explicit conversion instruction (start_unique) to
>>> convert an immutable
>>> reference to a mutable referece.
>>> A SIL optimization can replace an is_unique with this instruction if it can
>>> prove that the reference
>>> is already unique at that point.
>>>
>>>>
>>>>
>>>>>> Unless you mean the reference is
>>>>>> immutable, rather than the storage being referred to by it.
>>>>>>
>>>>>>> This means any address derived from a ``cow_to_ref`` instruction can be
>>>>>>> considered to point to immutable memory.
>>>>>>>
>>>>>>> Some examples of optimizations which will benefit from copy-on-write
>>>>>>> representation in SIL:
>>>>>>>
>>>>>>> - Redundant load elimination
>>>>>>>
>>>>>>> RLE can assume that opaque code does not modify a COW buffer.
>>>>>>
>>>>>> How do you distinguish “opaque code” from “code that is meant to
>>>>>> modify the buffer and might do so in place if it's uniquely-referenced?”
>>>>>
>>>>> Again, the is_unique which takes the address of the reference, will
>>>>> guarantee that during the lifetime of a buffer there are no
>>>>> modifications of the buffer.
>>>>
>>>> Again, that sounds like it rules out inplace modification of uniquely
>>>> referenced buffers.
>>>>
>>>>>
>>>>>
>>>>>>
>>>>>>> Example::
>>>>>>>
>>>>>>> %2 = cow_to_ref %1 : $@sil_cow COWBuffer
>>>>>>> %3 = ref_element_addr %2 : $COWBuffer, #someData
>>>>>>> %4 = load %3 : $*Int
>>>>>>> %5 = apply %foo() // Cannot overwrite memory
>>>>>>> location %3
>>>>>>> %6 = load %3 : $*Int // Can be replaced by %4
>>>>>>>
>>>>>>> Currently we do some ad-hoc optimizations for array, based on semantics,
>>>>>>> like array count propagation. These hacks would not be needed
>>>>>>> anymore.
>>>>>>
>>>>>> W0000000000000000000000t.
>>>>>>
>>>>>>> Note that it’s not required to check if a ``cow_to_ref`` reference (or a
>>>>>>> projected address) escapes. Even if it escapes, it will reference
>>>>>>> immutable
>>>>>>> memory.
>>>>>>>
>>>>>>> - CSE, loop hoisting
>>>>>>>
>>>>>>> Similar to RLE: the optimizer can assume that opaque code cannot modify
>>>>>>> a
>>>>>>> COW buffer
>>>>>>
>>>>>> Same question here as above, then.
>>>>>>>
>>>>>>> - ARC optimization
>>>>>>>
>>>>>>> Knowing that some opaque code cannot overwrite a reference in the COW
>>>>>>> buffer
>>>>>>> can remove retain/release pairs across such code::
>>>>>>>
>>>>>>> %2 = cow_to_ref %1 : $@sil_cow COWBuffer
>>>>>>> %3 = ref_element_addr %2 : $COWBuffer, #someRef
>>>>>>> %4 = load_strong %3 : $*MyClass // Can do a load_strong
>>>>>>> [guarantee]
>>>>>>> %5 = apply %foo() // Cannot overwrite someRef
>>>>>>> and dealloc the object
>>>>>>> // Use %4
>>>>>>> destroy_value %4 : $MyClass
>>>>>>>
>>>>>>> Scoping instructions
>>>>>>> --------------------
>>>>>>>
>>>>>>> To let the optimizer reason about the immutability of the COW buffer,
>>>>>>> it is
>>>>>>> important to *bind* the lifetime of the buffer content to the lifetime
>>>>>>> of the
>>>>>>> buffer reference. For example::
>>>>>>>
>>>>>>> %b1 = load %baddr : $@sil_cow COWBuffer // load the buffer reference
>>>>>>> // load something from %b1
>>>>>>> %a = apply %foo(%baddr : $@sil_cow COWBuffer)
>>>>>>> %b2 = load %baddr : $@sil_cow COWBuffer // load the buffer reference
>>>>>>> again
>>>>>>> // load something from %b2
>>>>>>>
>>>>>>> The question is: can RLE forward the load of the buffer reference and
>>>>>>> replace
>>>>>>> ``%b2`` with ``%b1``? It must not be able to do so if ``foo()``
>>>>>>> modifies the
>>>>>>> buffer.
>>>>>>>
>>>>>>> To enforce this restriction, the scope of any buffer modification must
>>>>>>> be
>>>>>>> enclosed in a pair of SIL instructions. Those instructions define the
>>>>>>> scope
>>>>>>> of the mutation. Both instructions take the *address* of the buffer
>>>>>>> reference as operand and act as a potential write to the buffer
>>>>>>> reference.
>>>>>>>
>>>>>>> The purpose of the scoping instructions is to strictly separate the
>>>>>>> liferanges
>>>>>>> of references to an immutable buffer and references to the mutable
>>>>>>> buffer.
>>>>>>
>>>>>> Looks reasonable.
>>>>>>
>>>>>>> The following example shows why the scoping instructions (specifically
>>>>>>> the
>>>>>>> end-of-scope instruction) are required to prevent loop-hoisting from
>>>>>>> interleaving mutable and immutable liferanges::
>>>>>>>
>>>>>>> // there should be a begin-of-scope %baddr
>>>>>>> %mut_b = load %baddr
>>>>>>> store %x to %mut_b // modification of the buffer
>>>>>>> // there should be a end-of-scope %baddr
>>>>>>>
>>>>>>> loop {
>>>>>>> %b = load %baddr
>>>>>>> %y = load %b // load from the buffer
>>>>>>> ...
>>>>>>> }
>>>>>>>
>>>>>>> If there is no end-of-scope instruction, loop hoisting could do::
>>>>>>>
>>>>>>> %mut_b = load %baddr
>>>>>>> %b = load %baddr // moved out of the loop
>>>>>>> store %x to %mut_b
>>>>>>>
>>>>>>> loop {
>>>>>>> %y = load %b
>>>>>>> ...
>>>>>>> }
>>>>>>>
>>>>>>> Now the optimizer assumes that ``%b`` references an immutable buffer,
>>>>>>> so it could
>>>>>>> also hoist the load::
>>>>>>>
>>>>>>> %mut_b = load %baddr
>>>>>>> %b = load %baddr
>>>>>>> %y = load %b // Wrong! Will be overwritten by the following
>>>>>>> store
>>>>>>> store %x to %mut_b
>>>>>>>
>>>>>>> loop {
>>>>>>> ...
>>>>>>> }
>>>>>>>
>>>>>>>
>>>>>>> The following sections describe two alternatives to implement the
>>>>>>> scoping.
>>>>>>>
>>>>>>> Scoping Alternative 1: Explicit Built-ins
>>>>>>> -----------------------------------------
>>>>>>>
>>>>>>> SIL instructions
>>>>>>> ^^^^^^^^^^^^^^^^
>>>>>>>
>>>>>>> The existing ``is_unique`` instruction is changed to a terminator
>>>>>>> instruction::
>>>>>>>
>>>>>>> bb0:
>>>>>>> is_unique_addr_br %0 : $*@sil_cow COWBuffer, bb1, bb2 // %0 is the
>>>>>>> address of the COWBuffer reference
>>>>>>> bb1(%1 : $COWBuffer): // the true-block. The payload %1 is the unique
>>>>>>> reference. Physically identical to "load %0”
>>>>>>> // usually empty
>>>>>>> br bb3(%1 : $COWBuffer)
>>>>>>> bb2: // the false-block
>>>>>>> // usually contains:
>>>>>>> %2 = apply %copy_buffer
>>>>>>> %3 = cow_to_ref %2
>>>>>>> store_strong %3 to %0 : $*@sil_cow COWBuffer
>>>>>>> br bb3(%2 : $COWBuffer)
>>>>>>> bb3(%4 : $COWBuffer):
>>>>>>> // Modify the buffer referenced by %4
>>>>>>> // ...
>>>>>>>
>>>>>>> The end-of-scope instruction is::
>>>>>>>
>>>>>>> end_unique_addr %0 : $*COWBuffer
>>>>>>>
>>>>>>> It is important that the references to the unique buffers (``%1``,
>>>>>>> ``%2``) must
>>>>>>> not outlive ``end_unique_addr``. In most cases this can be check by the
>>>>>>> SIL
>>>>>>> verifier.
>>>>>>>
>>>>>>> The two instructions must be paired properly but not necessarily in the
>>>>>>> same function.
>>>>>>>
>>>>>>> The purpose of an ``is_unique_addr_br`` - ``end_unique_addr`` pair is to
>>>>>>> separate the lifetimes of mutable and immutable accesses to the COW
>>>>>>> buffer.
>>>>>>> Both instructions take an address to the COW buffer reference and are
>>>>>>> considered as potential stores to the reference.
>>>>>>> This makes sure that the SIL optimizer cannot mix-up buffer reference
>>>>>>> lifetimes
>>>>>>> across these instructions.
>>>>>>> For example, RLE cannot combine two buffer loads which are interleaved
>>>>>>> with
>>>>>>> a ``is_unique_addr_br``::
>>>>>>>
>>>>>>> %1 = load_strong %0 : $*@sil_cow COWBuffer
>>>>>>> // do something with %1
>>>>>>> …
>>>>>>> is_unique_addr_br %0 : $*@sil_cow COWBuffer
>>>>>>> …
>>>>>>> %2 = load_strong %0 : $*@sil_cow COWBuffer // RLE cannot replace this
>>>>>>> with %1
>>>>>>>
>>>>>>> Another important thing is that the COW buffer can only be mutated by
>>>>>>> using the
>>>>>>> reference of the ``is_unique_addr_br`` true-block argument.
>>>>>>> The COW buffer cannot be modified by simply loading/extracting the
>>>>>>> reference
>>>>>>> from the COWType.
>>>>>>> Example::
>>>>>>>
>>>>>>> %1 = load_strong %0 : $*COWBuffer
>>>>>>> %2 = cow_to_ref %1 : $@sil_cow COWBuffer
>>>>>>> %3 = ref_element_addr %2 : $COWBuffer, #someData
>>>>>>> store %7 : $Int to %3 : $*Int // Violation!
>>>>>>>
>>>>>>> Most obvious violations to this constraint can be catched by the
>>>>>>> SILVerifier.
>>>>>>>
>>>>>>> The ``_addr`` variants of the instructions also have a non-addr
>>>>>>> counterpart::
>>>>>>>
>>>>>>> is_unique_br %0 : $COWBuffer, bb1, bb2. // consumes %0 and produces
>>>>>>> the true-block arg as owned
>>>>>>>
>>>>>>> %1 = end_unique %0 : $COWBuffer // consumes %0 and produces %1 as owned
>>>>>>>
>>>>>>> These instructions are generated by Mem2reg (or a similar optimization)
>>>>>>> in case the COW value is stored (in a temporary alloc_stack location)
>>>>>>> just for the sake of passing an address to ``is_unique_addr_br`` and
>>>>>>> ``end_unique_addr``.
>>>>>>> For example in the following code, where the COW data is passed
>>>>>>> as-value and
>>>>>>> all the mutating functions are inlined::
>>>>>>>
>>>>>>> func foo(arr : [Int], x: Int) {
>>>>>>> arr[0] = 27
>>>>>>> …
>>>>>>> y = arr[x]
>>>>>>> …
>>>>>>> }
>>>>>>>
>>>>>>> Finally it’s probably a good idea to add an instruction for converting
>>>>>>> an
>>>>>>> immutable reference to a mutable reference::
>>>>>>>
>>>>>>> %1 = start_unique %0 : $COWBuffer // consumes %0 and produces %1 :
>>>>>>> $COWBuffer as owned
>>>>>>>
>>>>>>> which is basically just a simpler representation of the following
>>>>>>> pattern::
>>>>>>>
>>>>>>> bb0:
>>>>>>> is_unique_br %0 : $@sil_cow COWBuffer, bb1, bb2
>>>>>>> bb1(%1 : $COWBuffer):
>>>>>>> … // main control flow continues here
>>>>>>> bb2:
>>>>>>> unreachable
>>>>>>>
>>>>>>> An optimizations, which eliminate uniqueness checks, would replace a
>>>>>>> ``is_unique_br`` by a ``start_unique``.
>>>>>>>
>>>>>>> Built-ins
>>>>>>> ^^^^^^^^^
>>>>>>>
>>>>>>> A COW type implementor can generate the new instructions by using a set
>>>>>>> of built-ins::
>>>>>>>
>>>>>>> func isUnique<BufferType>(_ buffer: inout BufferType) -> BufferType?
>>>>>>> func endUnique<BufferType>(_ buffer: inout BufferType)
>>>>>>>
>>>>>>> For example::
>>>>>>>
>>>>>>> struct COWType {
>>>>>>> copy_on_write var b : COWBuffer
>>>>>>>
>>>>>>> mutating func makeMutable() -> COWBuffer {
>>>>>>> if let uniqueBuffer = isUnique(&self.b) {
>>>>>>> return uniqueBuffer
>>>>>>> }
>>>>>>> let copiedBuffer = copyBuffer(self.b)
>>>>>>> self.b = copiedBuffer
>>>>>>> return copiedBuffer
>>>>>>> }
>>>>>>>
>>>>>>> mutating func setSomeData(x: Int) {
>>>>>>> let uniqueBuffer = makeMutable()
>>>>>>> uniqueBuffer.someData = x
>>>>>>> endUnique(&self.b)
>>>>>>> }
>>>>>>> }
>>>>>>
>>>>>> This seems reasonable, but it also looks like the compiler could do the
>>>>>> `endUnique` dance for us based, e.g., on the mutability of methods.
>>>>>
>>>>> I agree, that would be ideal, e.g. the compiler could insert the
>>>>> endUnique at the end of an inout
>>>>> scope.
>>>>>
>>>>>>
>>>>>>> The ``isUnique`` built-in returns an optional unique buffer reference.
>>>>>>> Physically this is the COW buffer which is passed as the inout argument.
>>>>>>> The result is nil if the buffer is not uniquely referenced.
>>>>>>> In this case usually the original buffer is copied and the reference to
>>>>>>> the
>>>>>>> copy is written back to the original buffer reference location
>>>>>>> (``self.b = copiedBuffer``).
>>>>>>> Starting at the point of the write-back, the reference to the copy also
>>>>>>> becomes
>>>>>>> a unique buffer reference.
>>>>>>>
>>>>>>> The ``isUnique`` built-in is lowered to the ``is_unique_addr_br``
>>>>>>> pattern which
>>>>>>> constructs the Optional in the successor blocks. Using ``isUnique`` in
>>>>>>> an
>>>>>>> if-let (as shown above) will end up in two consecutive CFG "diamonds".
>>>>>>> Simplify-CFG can combine those into a single ``is_unique_addr_br``
>>>>>>> diamond.
>>>>>>>
>>>>>>> .. note::
>>>>>>> This makes the definition of the unique buffer location lifetime a
>>>>>>> little bit
>>>>>>> problematic, because the false-branch of ``isUnique`` is not equivalent
>>>>>>> to
>>>>>>> the false-branch of the ``is_unique_addr_br`` instruction (before
>>>>>>> SimplifyCFG
>>>>>>> can do its job).
>>>>>>
>>>>>> I don't know what the implications of these diamonds and the problem
>>>>>> described above might be, FWIW.
>>>>>>
>>>>>>> The rules for using ``copy_on_write`` and the built-ins are:
>>>>>>>
>>>>>>> 1. ``isUnique`` must be paired with ``endUnique``, but not necessarily
>>>>>>> in the
>>>>>>> same function.
>>>>>>>
>>>>>>> 2. The COW buffer may only be mutated by using the unique buffer
>>>>>>> reference.
>>>>>>>
>>>>>>> 3. The COW buffer must not be mutated outside the ``isUnique`` -
>>>>>>> ``endUnique``
>>>>>>> pair.
>>>>>>>
>>>>>>> 4. During the lifetime of the unique buffer reference, the original COW
>>>>>>> buffer
>>>>>>> reference must not be used in any way, e.g. for reading from the buffer.
>>>>>>>
>>>>>>> Note that the lifetime of the unique buffer reference does not include
>>>>>>> the
>>>>>>> part between the begin of the ``isUnique`` false-branch and the
>>>>>>> write-back
>>>>>>> of the copy. This means is okay to read from the buffer (using
>>>>>>> ``self.b``)
>>>>>>> for the purpose of copying.
>>>>>>>
>>>>>>> Examples::
>>>>>>>
>>>>>>> mutating func setSomeData(x: Int) {
>>>>>>> let uniqueBuffer = makeMutable()
>>>>>>> uniqueBuffer.someData = x
>>>>>>> // violates rule 1
>>>>>>> }
>>>>>>>
>>>>>>> mutating func setSomeData(x: Int) {
>>>>>>> makeMutable()
>>>>>>> self.b.someData = x // violates rule 2
>>>>>>> endUnique(&self.b)
>>>>>>> }
>>>>>>>
>>>>>>> mutating func setSomeData(x: Int) {
>>>>>>> let uniqueBuffer = makeMutable()
>>>>>>> uniqueBuffer.someData = x
>>>>>>> endUnique(&self.b)
>>>>>>> uniqueBuffer.someData = 27 // violates rule 3
>>>>>>> }
>>>>>>>
>>>>>>> mutating func incrementSomeData() {
>>>>>>> let uniqueBuffer = makeMutable()
>>>>>>> uniqueBuffer.someData = self.b.someData + 1 // violates rule 4
>>>>>>> endUnique(&self.b)
>>>>>>> }
>>>>>>
>>>>>> It would be instructive to write down the *correct* code for these
>>>>>> operations.
>>>>>
>>>>> added to my todo list.
>>>>>
>>>>>>
>>>>>>> The intention of the rules is to ensure that there is no overlap of a
>>>>>>> "read-only" life-range with a "mutable" life-range of the buffer
>>>>>>> reference.
>>>>>>> It’s the responsibility of the implementor to follow the rules.
>>>>>>> But the compiler (a mandatory diagnostics pass and the SIL verifier) can
>>>>>>> statically detect rule violations in obvious cases (with
>>>>>>> inter-procedural
>>>>>>> analysis maybe even in most cases).
>>>>>>>
>>>>>>> This approach would require to change some of the internals of our
>>>>>>> current COW data structures in the stdlib (Array, Dictionary, etc.).
>>>>>>> For example, the Array make_mutable semantic functions currently do not
>>>>>>> return
>>>>>>> the unique buffer.
>>>>>>
>>>>>> No big deal.
>>>>>>
>>>>>>> Scoping Alternative 2: Implicit Inout Scopes
>>>>>>> --------------------------------------------
>>>>>>>
>>>>>>> There is an idea (proposal?) to change the representation of inout
>>>>>>> variables
>>>>>>> in SIL. This is independent of this proposal, but can be helpful for the
>>>>>>> purpose of defining the scope of a COW mutation.
>>>>>>>
>>>>>>> The basic idea is that SILGen inserts scoping instructions for *all*
>>>>>>> inout
>>>>>>> variables. And those scoping instructions can be used to define the
>>>>>>> mutating
>>>>>>> scope of a COW buffer.
>>>>>>>
>>>>>>> The scoping instructions which are inserted by SILGen for an inout
>>>>>>> scope are::
>>>>>>>
>>>>>>> begin_exclusive
>>>>>>> end_exclusive
>>>>>>>
>>>>>>> Simliar to ``is_unique_addr_br`` and ``end_unique_addr``, those
>>>>>>> instructions take the
>>>>>>> address of the inout variable as argument. For the optimizer those
>>>>>>> instructions
>>>>>>> look like potential writes to the inout variable.
>>>>>>>
>>>>>>> The implementor of a COW type has to follow the rule that the COW
>>>>>>> buffer may
>>>>>>> only be modified in mutating functions of the COW type. But this is the
>>>>>>> case
>>>>>>> anyway because any modification needs a uniqueness check and this can
>>>>>>> only be
>>>>>>> done in mutating functions.
>>>>>>>
>>>>>>> Example::
>>>>>>>
>>>>>>> // > mutating func setSomeData(x: Int) {
>>>>>>> // Accepts a unique reference to the array value (avoiding refcount
>>>>>>> operations)
>>>>>>> sil @setSomeData : $(Int, @inout Array) -> () {
>>>>>>> bb_entry(%x : Int, %arrayref : $*Array<T>) // Begin scope #0
>>>>>>>
>>>>>>> // > makeMutable() (inlined)
>>>>>>> // Forward the unique reference to the `self` array value, still
>>>>>>> avoiding refcount operations.
>>>>>>> // Begin the inlined exclusive scope (could be trivially removed).
>>>>>>> begin_exclusive %arrayref : $*Array<T> // Begin scope #1
>>>>>>>
>>>>>>> // > if !isUnique(&self._storage) {
>>>>>>> // Extract a unique inout reference to the class reference to the
>>>>>>> array storage.
>>>>>>> // This begins the isUnique() argument's exclusive scope. The memory
>>>>>>> is already exclusive
>>>>>>> // but the scope helps ensure this is the only alias to _storage.
>>>>>>> %arrayref._storageref = struct_element_addr [exclusive] %arrayref,
>>>>>>> #Array._storage
>>>>>>>
>>>>>>> // Uniqueness checking requires an inout reference to the class
>>>>>>> reference.
>>>>>>> // The is_unique instruction does not need to create a new storage
>>>>>>> reference.
>>>>>>> // It's only purpose is to check the RC count, ensure that the checked
>>>>>>> reference
>>>>>>> // is inout, and prevent the inout scope from being optimized away.
>>>>>>> %isuniq = is_unique %arrayref._storageref : $*@sil_cow ArrayStorage<T>
>>>>>>>
>>>>>>> // End the isUnique argument's exclusive scope (can also be trivially
>>>>>>> removed).
>>>>>>> end_exclusive %arrayref._storageref : $*@sil_cow ArrayStorage<T>
>>>>>>>
>>>>>>> br %isuniq, bb_continue, bb_slow
>>>>>>>
>>>>>>> bb_slow:
>>>>>>> // > self._storage = copyBuffer(self._storage)
>>>>>>> // Produce a new class reference to storage with verifiably unique RC
>>>>>>> semantics.
>>>>>>> %copied_storage_class = alloc_ref ...
>>>>>>> // A begin/end exclusive scope is implicit in store [assign].
>>>>>>> store [assign] %copied_storage_class to %arrayref._storageref
>>>>>>> br bb_continue
>>>>>>>
>>>>>>> bb_continue:
>>>>>>>
>>>>>>> // This marks the end of makeMutable's inout `self` scope. Because
>>>>>>> Array
>>>>>>> // contains a "copy_on_write" property, the SIL verifier needs to
>>>>>>> // prove that %arrayref.#_storage has not escaped at this point. This
>>>>>>> // is equivalent to checking that %arrayref itself is not copied, and
>>>>>>> // checking each projection of the "copy_on_write" storage property
>>>>>>> // (%arrayref._storageref) is not copied. Or, if any copies are
>>>>>>> present,
>>>>>>> // they must be consumed within this scope.
>>>>>>> end_exclusive %arrayref : $*Array<T> // End scope #1
>>>>>>>
>>>>>>> // > self._storage.someData = x
>>>>>>> // An _addr instruction with one load/store use doesn't really need
>>>>>>> its own scope.
>>>>>>> %arrayref._storageref = struct_element_addr %arrayref, #Array._storage
>>>>>>>
>>>>>>> // ARC optimization can promote this to a borrow, replacing
>>>>>>> strong_release with end_borrow.
>>>>>>> %arrayref.cow_storage = load [copy] %arrayref._storageref : $*@sil_cow
>>>>>>> ArrayStorage
>>>>>>> %arrayref._storage = cow_to_ref %arrayref.cow_storage : $@sil_cow
>>>>>>> ArrayStorage
>>>>>>>
>>>>>>> // Write some data into the CoW buffer.
>>>>>>> // (For simplicity, pretend ArrayStorage has a "someData" field).
>>>>>>> // A single-use _addr instruction, so no scope.
>>>>>>> %somedata_addr = ref_element_addr %arrayref._storage, #someData
>>>>>>> // A store with an implicit [exclusive] scope.
>>>>>>> store [assign] %x to %somedata_addr
>>>>>>>
>>>>>>> strong_release %arrayref._storage : $*ArrayStorage<T>
>>>>>>>
>>>>>>> // End the isUnique argument's exclusive scope.
>>>>>>> // The same verification is needed here, but the inner scope would be
>>>>>>> eliminated.
>>>>>>> end_exclusive %arrayref : $*Array<T> // End scope #0
>>>>>>>
>>>>>>> In general this approach looks more "user-friendly" than the first
>>>>>>> alternative.
>>>>>>
>>>>>> Well, I can't really tell, because you haven't shown the Swift code that
>>>>>> generates this SIL.
>>>>>>
>>>>>>> But it depends on implementing the general feature to insert the inout
>>>>>>> scoping instructions. Also, we still have to think through all the
>>>>>>> details of this approach.
>>>>>>
>>>>>> FWIW, I am convinced we will need (and get) a stricter inout model that
>>>>>> would be conducive to inserting the scoping instructions.
>>>>>>
>>>>>>
>>>>>>> Dependency between a buffer reference to the scope-begin
>>>>>>> --------------------------------------------------------
>>>>>>
>>>>>> You can only have a dependency between two things, but as phrased “a
>>>>>> buffer reference to the scope-begin” sounds like one thing. s/to/and/
>>>>>> would fix it.
>>>>>>
>>>>>>> With both alternatives there is no explicit dependency from a buffer
>>>>>>> reference
>>>>>>> to a scope-begin instruction::
>>>>>>>
>>>>>>> %b_cow = load %baddr
>>>>>>> %b = cow_to_ref %b_cow
>>>>>>> %x = load %b // No dependency between this...
>>>>>>> ...
>>>>>>> begin_exclusive %baddr // ... and this instruction.
>>>>>>> ...
>>>>>>>
>>>>>>> So in theory the optimizer is free to reschedule the instructions::
>>>>>>>
>>>>>>> %b_cow = load %baddr
>>>>>>> %b = cow_to_ref %b_cow
>>>>>>> ...
>>>>>>> begin_exclusive %baddr
>>>>>>> %x = load %b // Wrong! Buffer could be modified here
>>>>>>> ...
>>>>>>>
>>>>>>> We still have to figure out how to cope with this.
>>>>>>>
>>>>>>> - We could add an end-of-lifetime instruction for a COW buffer
>>>>>>> reference, which
>>>>>>> the optimizer may not move over a begin-of-scope instruction.
>>>>>>>
>>>>>>> - Or we just define the implicit rule for the optimizer that any use of
>>>>>>> a COW
>>>>>>> reference may not be moved over a begin-of-scope instruction.
>>>>>>>
>>>>>>> Preconditions
>>>>>>> =============
>>>>>>>
>>>>>>> To benefit from COW optimizations in the stdlib Array, Set and
>>>>>>> Dictionary data
>>>>>>> structures we first need eager bridging, meaning getting rid of the
>>>>>>> bridged
>>>>>>> buffer.
>>>>>>
>>>>>> As you know I'm very much in favor of eager bridging, but I don't see
>>>>>> why this would be dependent on it.
>>>>>
>>>>> We could use copy_on_write with eager bridging, but I don’t think it will
>>>>> give any benefits to the
>>>>> optimizer.
>>>>> For example, the SIL code to get from an Array to a native
>>>>> ContiguousArrayStorage reference is pretty hard to understand for the
>>>>> optimizer (involves low level bit operations, etc.).
>>>>
>>>> It wouldn't need to do low-level bit operations if our enums were
>>>> capable/controllable enough. I'm just saying, there's no reason we
>>>> couldn't give the optimizer something to work with that has higher level
>>>> semantics than what we currently do.
>>>>
>>>>>>> At least for Array this is implemented as low-level bit operations and
>>>>>>> optimizations cannot reason about it (e.g. finding a reasonable
>>>>>>> RC-root for the buffer reference).
>>>>>>>
>>>>>>> Another thing is that we currently cannot use ``copy_on_write`` for
>>>>>>> Array
>>>>>>> because of pinning. Array pins it’s buffer when passing an element
>>>>>>> address to
>>>>>>> an inout parameter. This allows the array buffer to be modified even if
>>>>>>> its
>>>>>>> reference count is > 1. With ``copy_on_write``, a programmer could
>>>>>>> break memory
>>>>>>> safety when violating the inout rule. Example::
>>>>>>>
>>>>>>> var arr = [MyClass()] // a global array
>>>>>>>
>>>>>>> foo(&arr[0]) // Pins the buffer of arr during the call
>>>>>>>
>>>>>>> func foo(_ x: inout MyClass) -> Int {
>>>>>>> let b = arr // The ref-count of the buffer is not incremented,
>>>>>>> because it is pinned!
>>>>>>> let r = b[0] // optimizer removes the retain of r because it
>>>>>>> thinks the following code cannot modify b
>>>>>>> arr.removeAll() // does not copy the array buffer and thus
>>>>>>> de-allocates r
>>>>>>> return r.i // use-after-free!
>>>>>>> }
>>>>>>
>>>>>> I only know of one way to resolve inout and pinning:
>>>>>>
>>>>>> * Semantically, references are replaced with a trap value when entering
>>>>>> an inout context so that all inout values are provably unique
>>>>>> references in the absence of unsafe code. We drop pinning and provide
>>>>>> explicit operations that provide simultaneous lvalue accesses to
>>>>>> distinct regions, e.g. c.swap(i1, i2) where i1 and i2 are indices.
>>>>>>
>>>>>> If there are other ideas out there, I'd like to hear them. If not, we
>>>>>> should probably decide that this is what we're doing so that we can move
>>>>>> forward without this looming uncertainty.
>>>>>>
>>>>>> --
>>>>>> -Dave
>>>>>>
>>>>>> _______________________________________________
>>>>>> swift-dev mailing list
>>>>>> swift-dev@swift.org <mailto:swift-dev@swift.org>
>>>>>> https://lists.swift.org/mailman/listinfo/swift-dev
>>>>>
>>>>
>>>> --
>>>> -Dave
>>>
>>> _______________________________________________
>>> swift-dev mailing list
>>> swift-dev@swift.org <mailto:swift-dev@swift.org>
>>> https://lists.swift.org/mailman/listinfo/swift-dev
>>
>> --
>> -Dave
>>
>> _______________________________________________
>> swift-dev mailing list
>> swift-dev@swift.org <mailto:swift-dev@swift.org>
>> https://lists.swift.org/mailman/listinfo/swift-dev
>> <https://lists.swift.org/mailman/listinfo/swift-dev>
> _______________________________________________
> swift-dev mailing list
> swift-dev@swift.org <mailto:swift-dev@swift.org>
> https://lists.swift.org/mailman/listinfo/swift-dev
> <https://lists.swift.org/mailman/listinfo/swift-dev>
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev
