[swift-dev] copy-on-write proposal

Andrew Trick atrick at apple.com
Wed Oct 19 20:36:58 CDT 2016


> On Oct 19, 2016, at 10:13 AM, Dave Abrahams via swift-dev <swift-dev at 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 <dabrahams at apple.com> wrote:
>>> 
>>> 
>>> on Mon Oct 17 2016, Erik Eckstein <eeckstein-AT-apple.com> wrote:
>>> 
>> 
>>>> On Oct 16, 2016, at 2:05 PM, Dave Abrahams via swift-dev <swift-dev at swift.org> wrote:
>>>> 
>>>>> on Thu Oct 13 2016, Joe Groff <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 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.
>>>>>>> <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 at swift.org> wrote:
>>>>> 
>>>>> 
>>>>> on Tue Oct 11 2016, Erik Eckstein <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.
> 
> 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.

-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 at swift.org
>>>>> https://lists.swift.org/mailman/listinfo/swift-dev
>>>> 
>>> 
>>> -- 
>>> -Dave
>> 
>> _______________________________________________
>> swift-dev mailing list
>> swift-dev at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-dev
> 
> -- 
> -Dave
> 
> _______________________________________________
> swift-dev mailing list
> swift-dev at swift.org <mailto:swift-dev at swift.org>
> https://lists.swift.org/mailman/listinfo/swift-dev <https://lists.swift.org/mailman/listinfo/swift-dev>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20161019/7891a0d3/attachment.html>


More information about the swift-dev mailing list