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 (21.4 KB)
----
: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.
in the same way as a programmer can do => just as a programmer can.
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.
modified => modification.
.. 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 : COWBuffermutating 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. 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... 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
"The" is not needed here I think.
``StorageType``, just like how ``unowned`` and ``weak`` is represented.
is represented => are 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_cowAgain, this is similar to ``ref_to_unowned`` and ``unowned_to_ref``.
For example the SIL code for::
var c: COWType
let x = c.b.someDatawould 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 : $*IntThe ``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 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.
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 %4Currently we do some ad-hoc optimizations for array, based on semantics,
like array count propagation. These hacks would not be needed anymore.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- 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 : $MyClassScoping 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 %b2The 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.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 %baddrloop {
%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_bloop {
%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_bloop {
...
}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.
Would this require a new form of function signature?
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
Can you make this a complete example.
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.
On the face this claim is incorrect. I think it is important to be clear here that you mean without any further copying done. It seems to contradict your example above of doing mutable things in bb3.
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
…
}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:
unreachableAn optimizations, which eliminate uniqueness checks, would replace a
``is_unique_br`` by a ``start_unique``.
Question, I imagine that make_mutable is a very common case. Why not just provide such an instruction?
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 : COWBuffermutating 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)
}
}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).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)
}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.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_exclusiveSimliar 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_continuebb_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_addrstrong_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 #0In general this approach looks more "user-friendly" than the first alternative.
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.Dependency between a buffer reference to the scope-begin
--------------------------------------------------------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. 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!
}
From a quick (re-)reading, this proposal still makes sense to me. My largest comment is that I would really like to have some way that the program will assert if the constraints are violated. Otherwise it will be difficult to debug when your invariants are broken. The state machine seems simple enough that I think you could reuse the pinned buffer and (if necessary) 1 additional bit in the object header (or perhaps tagged pointer bits).
Michael
···
On Oct 11, 2016, at 4:48 PM, Erik Eckstein via swift-dev <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.
If you have any comments, please let me know.Erik
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev
I’m having trouble figuring something out: is all of this contingent on all of the relevant operations being completely inlined into a single function at the SIL level? Could failing to inline a standard library function lead to performance cliffs? I understand this is generally true of inlining and dead-code elimination; but I’m wondering how this affects the abstractions we expose. Can we know that some things will “always” work, even if parts aren’t inlined?
···
On Oct 11, 2016, at 7:48 PM, Erik Eckstein via swift-dev <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.Erik
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev
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, 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. 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.
-Joe
···
On Oct 11, 2016, at 4:48 PM, Erik Eckstein via swift-dev <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.: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 : COWBuffermutating 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.
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. What
are the rules for writing code that uses `copy_on_write`?
.. 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_cowAgain, this is similar to ``ref_to_unowned`` and ``unowned_to_ref``.
For example the SIL code for::
var c: COWType
let x = c.b.someDatawould 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 : $*IntThe ``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. 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?”
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 %4Currently 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 : $MyClassScoping 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 %b2The 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 %baddrloop {
%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_bloop {
%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_bloop {
...
}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 %1Another 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
…
}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:
unreachableAn 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 : COWBuffermutating 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.
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.
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_exclusiveSimliar 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_continuebb_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_addrstrong_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 #0In 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.
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.
···
on Tue Oct 11 2016, Erik Eckstein <swift-dev-AT-swift.org> wrote:
--
-Dave
Thanks for the feedback! Here is an updated version of the proposal: https://github.com/eeckstein/swift/blob/cow-proposal/docs/proposals/CopyOnWrite.rst
(you can look at the history to see the changes compared to the previous version)
----
: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.in the same way as a programmer can do => just as a programmer can.
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.modified => modification.
.. 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 : COWBuffermutating 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. 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... 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
"The" is not needed here I think.
``StorageType``, just like how ``unowned`` and ``weak`` is represented.
is represented => are 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_cowAgain, this is similar to ``ref_to_unowned`` and ``unowned_to_ref``.
For example the SIL code for::
var c: COWType
let x = c.b.someDatawould 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 : $*IntThe ``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 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.
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 %4Currently we do some ad-hoc optimizations for array, based on semantics,
like array count propagation. These hacks would not be needed anymore.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- 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 : $MyClassScoping 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 %b2The 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.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 %baddrloop {
%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_bloop {
%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_bloop {
...
}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.Would this require a new form of function signature?
No
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 %1Can you make this a complete example.
I think in this short version it’s easier to understand. But I added a comment beside the is_unique_addr_br for clarification.
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.On the face this claim is incorrect. I think it is important to be clear here that you mean without any further copying done. It seems to contradict your example above of doing mutable things in bb3.
You are right. I rewrote this sentence.
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
…
}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:
unreachableAn optimizations, which eliminate uniqueness checks, would replace a
``is_unique_br`` by a ``start_unique``.Question, I imagine that make_mutable is a very common case. Why not just provide such an instruction?
What should a make_mutable instruction do? Or are you just suggesting to rename start_unique to make_mutable?
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 : COWBuffermutating 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)
}
}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).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)
}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.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_exclusiveSimliar 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_continuebb_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_addrstrong_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 #0In general this approach looks more "user-friendly" than the first alternative.
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.Dependency between a buffer reference to the scope-begin
--------------------------------------------------------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. 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!
}From a quick (re-)reading, this proposal still makes sense to me. My largest comment is that I would really like to have some way that the program will assert if the constraints are violated. Otherwise it will be difficult to debug when your invariants are broken. The state machine seems simple enough that I think you could reuse the pinned buffer and (if necessary) 1 additional bit in the object header (or perhaps tagged pointer bits).
Yeah, we could do this. I think it would just be sufficient to write a null pointer into the cow reference on at the begin-scope and restore it at the end-scope. It’s the same thing as having runtime checks for not violating borrowing rules.
···
On Oct 11, 2016, at 7:57 PM, Michael Gottesman <mgottesman@apple.com> wrote:
Michael
On Oct 11, 2016, at 4:48 PM, Erik Eckstein via swift-dev <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.
If you have any comments, please let me know.Erik
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev
I’m having trouble figuring something out: is all of this contingent on all of the relevant operations being completely inlined into a single function at the SIL level? Could failing to inline a standard library function lead to performance cliffs? I understand this is generally true of inlining and dead-code elimination; but I’m wondering how this affects the abstractions we expose. Can we know that some things will “always” work, even if parts aren’t inlined?
Yes, also these optimizations heavily rely on inlining. I would say that originally almost everything is inside a called function, just think of all the generated getters/setters. But usually this is not a problem because most of the relevant functions are quite small and always inlined anyway.
···
On Oct 12, 2016, at 11:19 AM, Alexis <abeingessner@apple.com> wrote:
On Oct 11, 2016, at 7:48 PM, Erik Eckstein via swift-dev <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.Erik
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev
I’m having trouble figuring something out: is all of this contingent on all of the relevant operations being completely inlined into a single function at the SIL level? Could failing to inline a standard library function lead to performance cliffs? I understand this is generally true of inlining and dead-code elimination; but I’m wondering how this affects the abstractions we expose. Can we know that some things will “always” work, even if parts aren’t inlined?
Well, actually there are two basic approaches that you see within the SIL optimizer. One relies on being able to analyze all instructions between two points in the CFG. That depends on full inlining or deep IPA. The other approach relies on knowledge about aliasing, uniqueness, immutability, and so on reach a conclusion about some opaque region of code.
Some of our optimizations rely on full inlining and conservative analysis, but the more we can capture semantics in SIL, the more we can employ the second approach, which improves the power and robustness of the optimizer.
Erik proposed redundant-load elimination and ARC optimizations that both need to prove the absence of a store to a particular memory location within some region. With the proposed copy-on-write attribute, we can now prove the absence of a store without analyzing any of the instructions in that region. I think this is an good example of the second approach where we can optimize around opaque regions of code. So it’s worth making sure our representation supports that.
It is still true though that enough inlining needs to take place such that we can see a load of the Array storage and access to that storage all in the same function scope.
-Andy
···
On Oct 12, 2016, at 11:19 AM, Alexis via swift-dev <swift-dev@swift.org> wrote:
On Oct 11, 2016, at 7:48 PM, Erik Eckstein via swift-dev <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.Erik
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev
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, 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.
I think this makes sense. Although we would need an attribute on the field as well (what John called the @copied attribute).
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. We can also allow a copy-on-write class to have "mutating" methods, and only allow mutation on unique references.
The only way to get a unique reference would then be to use the isUnique-builtin - or to create a new buffer. This is good, because we could statically check that the programmer can only modify uniquely referenced buffers (although to get full memory safety we would probably have to invalidate the original buffer reference between the is_unique - end_unique scope, e.g. by storing a null pointer into it).
Thinking about this in detail I believe we have to change how a COW is implemented. For example we could not write back the unique reference and use it afterwards:
if let uniqueRef = isUnique(&cow.buffer) {
} else {
uniqueRef = Buffer()
cow.buffer = uniqueRef // <- this would not work. It’s a copy of a unique buffer
}
uniqueRef.someData = ...
Instead this could be done like
if let uniqueRef = isUnique(&cow.buffer) {
} else {
uniqueRef = Buffer()
}
uniqueRef.someData = ...
cow.buffer = uniqueRef // OK, end of lifetime of uniqueRef
It would mean that we write back the buffer even in the unique-case, But I think this is ok.
For the implementation we would need two different reference types in the AST (unique and nonunique), right? Could this be just a different StorageType?
···
On Oct 13, 2016, at 10:36 AM, Joe Groff <jgroff@apple.com> wrote:
On Oct 11, 2016, at 4:48 PM, Erik Eckstein via swift-dev <swift-dev@swift.org> wrote:
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.
-Joe
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.
···
on Thu Oct 13 2016, Joe Groff <swift-dev-AT-swift.org> wrote:
On Oct 11, 2016, at 4:48 PM, Erik Eckstein via swift-dev <swift-dev@swift.org> wrote:
--
-Dave
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.
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 : COWBuffermutating 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.
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:”)
.. 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_cowAgain, this is similar to ``ref_to_unowned`` and ``unowned_to_ref``.
For example the SIL code for::
var c: COWType
let x = c.b.someDatawould 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 : $*IntThe ``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.
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.
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 %4Currently 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 bufferSame 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 : $MyClassScoping 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 %b2The 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 %baddrloop {
%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_bloop {
%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_bloop {
...
}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 %1Another 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
…
}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:
unreachableAn 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 : COWBuffermutating 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_exclusiveSimliar 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_continuebb_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_addrstrong_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 #0In 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.).
···
On Oct 16, 2016, at 2:05 PM, Dave Abrahams via swift-dev <swift-dev@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@swift.org> wrote:
On Oct 16, 2016, at 2:01 PM, Dave Abrahams via swift-dev <swift-dev@swift.org> wrote:
on Tue Oct 11 2016, Erik Eckstein <swift-dev-AT-swift.org> wrote:
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
https://lists.swift.org/mailman/listinfo/swift-dev
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.
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 : COWBuffermutating 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_cowAgain, this is similar to ``ref_to_unowned`` and ``unowned_to_ref``.
For example the SIL code for::
var c: COWType
let x = c.b.someDatawould 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 : $*IntThe ``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.
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 %4Currently 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 bufferSame 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 : $MyClassScoping 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 %b2The 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 %baddrloop {
%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_bloop {
%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_bloop {
...
}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 %1Another 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
…
}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:
unreachableAn 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 : COWBuffermutating 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_exclusiveSimliar 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_continuebb_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_addrstrong_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 #0In 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.
···
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@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@swift.org> wrote:
On Oct 16, 2016, at 2:01 PM, Dave Abrahams via swift-dev <swift-dev@swift.org> wrote:
on Tue Oct 11 2016, Erik Eckstein <swift-dev-AT-swift.org> wrote:
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
https://lists.swift.org/mailman/listinfo/swift-dev
--
-Dave
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.
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 : COWBuffermutating 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_cowAgain, this is similar to ``ref_to_unowned`` and ``unowned_to_ref``.
For example the SIL code for::
var c: COWType
let x = c.b.someDatawould 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 : $*IntThe ``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.
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.
···
On Oct 17, 2016, at 10:21 AM, Dave Abrahams <dabrahams@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@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@swift.org> wrote:
On Oct 16, 2016, at 2:01 PM, Dave Abrahams via swift-dev <swift-dev@swift.org> wrote:
on Tue Oct 11 2016, Erik Eckstein <swift-dev-AT-swift.org> wrote:
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 %4Currently 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 bufferSame 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 : $MyClassScoping 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 %b2The 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 %baddrloop {
%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_bloop {
%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_bloop {
...
}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 %1Another 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
…
}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:
unreachableAn 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 : COWBuffermutating 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_exclusiveSimliar 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_continuebb_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_addrstrong_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 #0In 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
https://lists.swift.org/mailman/listinfo/swift-dev--
-Dave
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.
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 : COWBuffermutating 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_cowAgain, this is similar to ``ref_to_unowned`` and ``unowned_to_ref``.
For example the SIL code for::
var c: COWType
let x = c.b.someDatawould 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 : $*IntThe ``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.
···
on Tue Oct 18 2016, Erik Eckstein <swift-dev-AT-swift.org> wrote:
On Oct 17, 2016, at 10:21 AM, Dave Abrahams <dabrahams@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@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@swift.org> wrote:
On Oct 16, 2016, at 2:01 PM, Dave Abrahams via swift-dev <swift-dev@swift.org> wrote:
on Tue Oct 11 2016, Erik Eckstein <swift-dev-AT-swift.org> wrote:
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 %4Currently 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 bufferSame 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 : $MyClassScoping 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 %b2The 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 %baddrloop {
%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_bloop {
%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_bloop {
...
}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 %1Another 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
…
}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:
unreachableAn 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 : COWBuffermutating 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_exclusiveSimliar 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_continuebb_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_addrstrong_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 #0In 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
https://lists.swift.org/mailman/listinfo/swift-dev--
-Dave_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev
--
-Dave
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.
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 : COWBuffermutating 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_cowAgain, this is similar to ``ref_to_unowned`` and ``unowned_to_ref``.
For example the SIL code for::
var c: COWType
let x = c.b.someDatawould 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 : $*IntThe ``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 likeA 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
···
On Oct 19, 2016, at 10:13 AM, Dave Abrahams via swift-dev <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 <dabrahams@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@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@swift.org> wrote:
On Oct 16, 2016, at 2:01 PM, Dave Abrahams via swift-dev <swift-dev@swift.org> wrote:
on Tue Oct 11 2016, Erik Eckstein <swift-dev-AT-swift.org> wrote:
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 %4Currently 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 bufferSame 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 : $MyClassScoping 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 %b2The 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 %baddrloop {
%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_bloop {
%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_bloop {
...
}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 %1Another 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
…
}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:
unreachableAn 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 : COWBuffermutating 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_exclusiveSimliar 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_continuebb_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_addrstrong_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 #0In 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
https://lists.swift.org/mailman/listinfo/swift-dev--
-Dave_______________________________________________
swift-dev mailing list
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
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.
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 : COWBuffermutating 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_cowAgain, this is similar to ``ref_to_unowned`` and ``unowned_to_ref``.
For example the SIL code for::
var c: COWType
let x = c.b.someDatawould 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 : $*IntThe ``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 likeA 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.
···
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 <dabrahams@apple.com <mailto:dabrahams@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/>> wrote:
On Oct 11, 2016, at 4:48 PM, Erik Eckstein via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
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:
-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 %4Currently 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 bufferSame 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 : $MyClassScoping 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 %b2The 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 %baddrloop {
%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_bloop {
%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_bloop {
...
}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 %1Another 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
…
}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:
unreachableAn 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 : COWBuffermutating 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_exclusiveSimliar 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_continuebb_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_addrstrong_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 #0In 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_______________________________________________
swift-dev mailing list
swift-dev@swift.org <mailto:swift-dev@swift.org>
https://lists.swift.org/mailman/listinfo/swift-dev
We might want to leave some room in the design for a shared atomic cache reference to live in the buffer, FWIW. It would have to be mutable even when the buffer was multiply-referenced
···
Sent from my moss-covered three-handled family gradunza
On Oct 20, 2016, at 8:41 AM, Erik Eckstein <eeckstein@apple.com> wrote:
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> wrote:
on Tue Oct 18 2016, Erik Eckstein <swift-dev-AT-swift.org> wrote:
On Oct 17, 2016, at 10:21 AM, Dave Abrahams <dabrahams@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@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@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> 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 : COWBuffermutating 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_cowAgain, this is similar to ``ref_to_unowned`` and ``unowned_to_ref``.
For example the SIL code for::
var c: COWType
let x = c.b.someDatawould 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 : $*IntThe ``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 likeA 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 %4Currently 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 bufferSame 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 : $MyClassScoping 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 %b2The 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 %baddrloop {
%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_bloop {
%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_bloop {
...
}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 %1Another 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
…
}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:
unreachableAn 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 : COWBuffermutating 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_exclusiveSimliar 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_continuebb_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_addrstrong_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 #0In 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
https://lists.swift.org/mailman/listinfo/swift-dev--
-Dave_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev--
-Dave_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev
In my mind, relying on a move-only reference type is exactly what I was advocating for, but relies on a language feature rather than a “special” compiler verification. This all still needs to work with an ‘inout’ Array. The compiler will effectively be doing the same verification that I was proposing but as a side effect of move-only semantics (type system support makes it much easier). The isUnique builtin would just be a mechanism to get the mutable type, and the endUnique builtin is the mechanism to move the type back. As Dave pointed out, we could provide additional mechanisms for mutation that don’t depend on uniqueness. But the SIL optimizer doesn’t need to be explicitly taught about any of those builtin mechanisms for correctness. More importantly, the user is no longer responsible for some easy-to-violate, unverified property of the data type as a whole.
-Andy
···
On Oct 20, 2016, at 8:41 AM, Erik Eckstein <eeckstein@apple.com> wrote:
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.
We might want to leave some room in the design for a shared atomic cache reference to live in the buffer, FWIW. It would have to be mutable even when the buffer was multiply-referenced
Should be no problem with an attribute on that field. Like ‘mutable' in C++.
···
On Oct 20, 2016, at 8:51 AM, Dave Abrahams <dabrahams@apple.com> wrote:
Sent from my moss-covered three-handled family gradunza
On Oct 20, 2016, at 8:41 AM, Erik Eckstein <eeckstein@apple.com <mailto:eeckstein@apple.com>> wrote:
On Oct 19, 2016, at 6:36 PM, Andrew Trick via swift-dev <swift-dev@swift.org <mailto: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 <dabrahams@apple.com <mailto:dabrahams@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/>> 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 : COWBuffermutating 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_cowAgain, this is similar to ``ref_to_unowned`` and ``unowned_to_ref``.
For example the SIL code for::
var c: COWType
let x = c.b.someDatawould 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 : $*IntThe ``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 likeA 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 %4Currently 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 bufferSame 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 : $MyClassScoping 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 %b2The 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 %baddrloop {
%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_bloop {
%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_bloop {
...
}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 %1Another 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
…
}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:
unreachableAn 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 : COWBuffermutating 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_exclusiveSimliar 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_continuebb_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_addrstrong_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 #0In 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_______________________________________________
swift-dev mailing list
swift-dev@swift.org <mailto:swift-dev@swift.org>
https://lists.swift.org/mailman/listinfo/swift-dev
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.
In my mind, relying on a move-only reference type is exactly what I was advocating for, but relies on a language feature rather than a “special” compiler verification.
Well, I think we are not blocked on this. We could just add a mandatory pass to check that there are no move-only violations. In the future a language feature might do this in a more elegant way in the type checker or whatever. But for now I believe we don’t need more than the attributes on the class type and the COW reference field.
This all still needs to work with an ‘inout’ Array. The compiler will effectively be doing the same verification that I was proposing but as a side effect of move-only semantics (type system support makes it much easier). The isUnique builtin would just be a mechanism to get the mutable type, and the endUnique builtin is the mechanism to move the type back. As Dave pointed out, we could provide additional mechanisms for mutation that don’t depend on uniqueness. But the SIL optimizer doesn’t need to be explicitly taught about any of those builtin mechanisms for correctness. More importantly, the user is no longer responsible for some easy-to-violate, unverified property of the data type as a whole.
I think we are more or less on the same page. All I’m saying is that the mutable reference can only be obtained by the isUnique/is_unique builtin/instruction (or by creating a new buffer).
···
On Oct 20, 2016, at 10:11 AM, Andrew Trick <atrick@apple.com> wrote:
On Oct 20, 2016, at 8:41 AM, Erik Eckstein <eeckstein@apple.com <mailto:eeckstein@apple.com>> wrote:
-Andy