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