<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Oct 8, 2016, at 10:09 AM, Karl <<a href="mailto:razielim@gmail.com" class="">razielim@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="Content-Type" content="text/html charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Could you add this (and John’s previous writeup) to the docs in the repo?</div></div></blockquote><div><br class=""></div><div>Yeah, it’s unfortunate that design discussions are buried in a flood of email. On the flip side, I’ve checked in some premature design docs that are probably nonsense now. I’m currently preparing a type safe memory model design doc to checkin. After that I’ll probably work on a document for SIL SSA with address-only types, which should cover John’s writeup. I’ll have to work with Michael Gottesman and John McCall to get a SIL ownership docs checked in.</div><br class=""><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">I was reasonably along the way to adding unowned optionals a while back but got totally lost in SILGen.</div><div class="">This info looks really valuable, but personally I find that with the mailing list format it’s hard to ever find this kind of stuff when I need it.</div><div class=""><br class=""></div><div class="">Thanks</div><div class=""><br class=""></div><div class="">Karl</div><div class=""><br class=""></div><div class="">P.S. going to pick up that unowned optional stuff soon, once I have time to read the docs about SILGen</div></div></div></blockquote><div><br class=""></div>There are SILGen docs somewhere?</div><div><br class=""></div><div>-Andy</div><div><br class=""><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""><br class=""><div class=""><blockquote type="cite" class=""><div class="">On 8 Oct 2016, at 08:10, Andrew Trick via swift-dev <<a href="mailto:swift-dev@swift.org" class="">swift-dev@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="Content-Type" content="text/html charset=us-ascii" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div style="margin: 0px; line-height: normal;" class="">On swift-dev, John already sent out a great writeup on SIL SSA:</div><div style="margin: 0px; line-height: normal;" class="">Representing "address-only" values in SIL.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">While talking to John I also picked up a lot of insight into how</div><div style="margin: 0px; line-height: normal;" class="">address types relate to SIL ownership and borrow checking. I finally</div><div style="margin: 0px; line-height: normal;" class="">organized the information into these notes. This is not a</div><div style="margin: 0px; line-height: normal;" class="">proposal. It's background information for those of us writing and</div><div style="margin: 0px; line-height: normal;" class="">reviewing proposals. Just take it as a strawman for future</div><div style="margin: 0px; line-height: normal;" class="">discussions. (There's also a good chance I'm getting something</div><div style="margin: 0px; line-height: normal;" class="">wrong).</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">[My commentary in brackets.]</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class=""><b class="">** Recap of address-only.</b></div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Divide address-only types into two categories:</div><div style="margin: 0px; line-height: normal;" class="">1. By abstraction (compiler doesn't know the size).</div><div style="margin: 0px; line-height: normal;" class="">2. The type is "memory-linked". i.e. the address is significant at runtime.</div><div style="margin: 0px; line-height: normal;" class=""> - weak references (anything that registers its address).</div><div style="margin: 0px; line-height: normal;" class=""> - C++ this.</div><div style="margin: 0px; line-height: normal;" class=""> - Anything with interior pointers.</div><div style="margin: 0px; line-height: normal;" class=""> - Any shared-borrowed value of a type with "nonmutating" properties.</div><div style="margin: 0px; line-height: normal;" class=""> ["nonmutating" properties allow mutation of state attached to a value.</div><div style="margin: 0px; line-height: normal;" class=""> Rust atomics are an example.]</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Address-only will not be reflected in SIL types. SIL addresses should</div><div style="margin: 0px; line-height: normal;" class="">only be used for formal memory (pointers, globals, class</div><div style="margin: 0px; line-height: normal;" class="">properties, captures). We'll get to inout arguments later...</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">As with opaque types, when IRGen lowers a memory-linked borrowed type,</div><div style="margin: 0px; line-height: normal;" class="">it needs to allocate storage.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Concern: SILGen has built-in tracking of managed values that automates</div><div style="margin: 0px; line-height: normal;" class="">insertion of cleanups. Lowering address-only types after SILOpt would</div><div style="margin: 0px; line-height: normal;" class="">require rediscovering that information based on CFG analysis. Is this</div><div style="margin: 0px; line-height: normal;" class="">too heroic?</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">This was already described by John. Briefly recapping:</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">e.g. Constructung Optional<Any></div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">We want initialization should be in-place as such:</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">%0 = struct_element_addr .. #S.any</div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">%1 = init_existential_addr %0, $*Any, $Optional<X></div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">%2 = inject_enum_data_addr %1, $Optional<X>.Some</div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">apply @initX(%2)</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">SILValue initialization would look something like:</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">%0 = apply @initX()</div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">%1 = enum #Optional.Some, %0 : $X</div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">%2 = existential %1 : $Any</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">[I'm not sure we actually want to represent an existential container</div><div style="margin: 0px; line-height: normal;" class="">this way, but enum, yes.]</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Lowering now requires discovering the storage structure, bottom-up,</div><div style="margin: 0px; line-height: normal;" class="">hoisting allocation, inserting cleanups as John explained.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Side note: Before lowering, something like alloc_box would directly</div><div style="margin: 0px; line-height: normal;" class="">take its initial value.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class=""><b class="">** SILFunction calling convention.</b></div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">For ownership analysis, there's effectively no difference between the</div><div style="margin: 0px; line-height: normal;" class="">value/address forms of argument ownership:</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">@owned / @in</div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">@guaranteed / @in_guaranteed</div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">return / @out</div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">@owned arg</div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">+ @owned return / @inout</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Regardless of the representation we choose for @inout, @in/@out will</div><div style="margin: 0px; line-height: normal;" class="">now be scalar types. SILFunction will maintain the distinction between</div><div style="margin: 0px; line-height: normal;" class="">@owned/@in etc. based on whether the type is address-only. We need</div><div style="margin: 0px; line-height: normal;" class="">this for reabstraction, but it only affects the function type, not the</div><div style="margin: 0px; line-height: normal;" class="">calling convention.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Rather than building a tuple, John prefers SIL support for anonymous</div><div style="margin: 0px; line-height: normal;" class="">aggregate as "exploded values".</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">[I'm guessing because tuples are a distinct formal type with their own</div><div style="margin: 0px; line-height: normal;" class="">convention and common ownership. This may need some discussion though.]</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Example SIL function type:</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">$(@in P, @owned Q) -> (@owned R, @owned S, @out T, @out U)</div><div style="margin: 0px; line-height: normal; font-family: Menlo; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">%p = apply f: $() -> P</div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">%q = apply g: $() -> Q</div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">%exploded = apply h(%p, %q)</div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">%r = project_exploded %exploded, #0 : $R</div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">%s = project_exploded %exploded, #1 : $S</div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">%t = project_exploded %exploded, #2 : $T</div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">%u = project_exploded %exploded, #3 : $U</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Exploded types requires all their elements to be projected with their</div><div style="margin: 0px; line-height: normal;" class="">own independent ownership.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class=""><b class="">** Ownership terminology.</b></div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Swift "owned" = Rust values = SIL @owned = implicitly consumed</div><div style="margin: 0px; line-height: normal;" class="">Swift "borrowed" = Rust immutable borrow = SIL @guaranteed = shared</div><div style="margin: 0px; line-height: normal;" class="">Swift "inout" = Rust mutable borrow = SIL @inout = unique</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Swift "inout" syntax is already (nearly) sufficient.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">"borrowed" may not need syntax on the caller side, just a way to</div><div style="margin: 0px; line-height: normal;" class="">qualify parameters. Swift still needs syntax for returning a borrowed</div><div style="margin: 0px; line-height: normal;" class="">value.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class=""><b class="">** Representation of borrowed values.</b></div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Borrowed values represent some shared storage location.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">We want some borrowed value references to be passed as SIL values, not SIL addresses:</div><div style="margin: 0px; line-height: normal;" class="">- Borrowed class references should not be indirected.</div><div style="margin: 0px; line-height: normal;" class="">- Optimize borrowing other small non-memory linked types.</div><div style="margin: 0px; line-height: normal;" class="">- Support capture promotion, and other SSA optimizations.</div><div style="margin: 0px; line-height: normal;" class="">- Borrow CoW values directly.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">[Address-only borrowed types will still be passed as SIL addresses (why not?)]</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Borrowed types with potentially mutating properties must be passed by</div><div style="margin: 0px; line-height: normal;" class="">SIL address because they are not actually immutable and their storage</div><div style="margin: 0px; line-height: normal;" class="">location is significant.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Borrowed references have a scope and need an end-of-borrow marker.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">[The end-of-borrow marker semantically changes the memory state, and</div><div style="margin: 0px; line-height: normal;" class="">statically enforces non-overlapping memory states. It does not</div><div style="margin: 0px; line-height: normal;" class="">semantically write-back a value. Borrowed values with mutating fields</div><div style="margin: 0px; line-height: normal;" class="">are semantically modified in-place.]</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">[Regardless of whether borrowed references are represented as SIL</div><div style="margin: 0px; line-height: normal;" class="">values or addresses, they must be associated with formal storage. That</div><div style="margin: 0px; line-height: normal;" class="">storage must remain immutable at the language level (although it may</div><div style="margin: 0px; line-height: normal;" class="">have mutating fields) and the value cannot be destroyed during the</div><div style="margin: 0px; line-height: normal;" class="">borrowed scope].</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">[Trivial borrowed values can be demoted to copies so we can eliminate</div><div style="margin: 0px; line-height: normal;" class="">their scope]</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">[Anything borrowed from global storage (and not demoted to a copy)</div><div style="margin: 0px; line-height: normal;" class="">needs its scope to be dynamically enforced. Borrows from local storage</div><div style="margin: 0px; line-height: normal;" class="">are sufficiently statically enforced. However, in both cases the</div><div style="margin: 0px; line-height: normal;" class="">optimizer must respect the static scope of the borrow.]</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">[I think borrowed values are effectively passed @guaranteed. The</div><div style="margin: 0px; line-height: normal;" class="">end-of-borrow scope marker will then always be at the top-level</div><div style="margin: 0px; line-height: normal;" class="">scope. You can't borrow in a caller and end its scope in the callee.]</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class=""><b class="">** Borrowed and inout scopes.</b></div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">inout value references are also scoped. We'll get to their</div><div style="margin: 0px; line-height: normal;" class="">representation shortly. Within an inout scope, memory is in an</div><div style="margin: 0px; line-height: normal;" class="">exclusive state. No borrowed scopes may overlap with an inout state,</div><div style="margin: 0px; line-height: normal;" class="">which is to say, memory is either shared or exclusive.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">We need a flag for stored properties, even for simple trivial</div><div style="margin: 0px; line-height: normal;" class="">types. That's the only way to provide a simple user model. At least we</div><div style="margin: 0px; line-height: normal;" class="">don't need this to be implemented atomically, we're not detecting race</div><div style="margin: 0px; line-height: normal;" class="">conditions. Optimizations will come later. We should be able to prove</div><div style="margin: 0px; line-height: normal;" class="">that some stored properties are never passed as inout.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">The stored property flag needs to be a tri-state: owned, borrowed, exclusive.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">The memory value can only be destroyed in the owned state.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">The user may mark some storage locations as "unchecked" as an</div><div style="margin: 0px; line-height: normal;" class="">opt-out. That doesn't change the optimizer's constraints. It simply</div><div style="margin: 0px; line-height: normal;" class="">bypasses the runtime check.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class=""><b class="">** Ownership of loaded values.</b></div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">[MikeG already explained possibilities of load ownership in</div><div style="margin: 0px; line-height: normal;" class="">[swift-dev] [semantic-arc][proposal] High Level ARC Memory Operations]</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">For the sake of understanding the model, it's worth realizing that we</div><div style="margin: 0px; line-height: normal;" class="">only need one form of load ownership: load_borrow. We don't</div><div style="margin: 0px; line-height: normal;" class="">actually need an operation that loads an owned value out of formal</div><div style="margin: 0px; line-height: normal;" class="">storage. This makes canonical sense because:</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">- Semantically, a load must at least be a borrow because the storage</div><div style="margin: 0px; line-height: normal;" class=""> location's non-exclusive flag needs to be dynamically checked</div><div style="margin: 0px; line-height: normal;" class=""> anyway, even if the value will be copied.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">- Code motion in the SIL optimizer has to obey the same limitations</div><div style="margin: 0px; line-height: normal;" class=""> within borrow scopes regardless of whether we fuse loads and copies</div><div style="margin: 0px; line-height: normal;" class=""> (retains).</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">[For the purpose of semantic ARC, the copy_value would be the RC</div><div style="margin: 0px; line-height: normal;" class="">root. The load and copy_value would effectively be "coupled" by the</div><div style="margin: 0px; line-height: normal;" class="">static scope of the borrow. e.g. we would not want to move a release</div><div style="margin: 0px; line-height: normal;" class="">inside the static scope of a borrow.]</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">[Purely in the interest of concise SIL, I still think we want a load [copy].]</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class=""><b class="">** SIL value ownership and aggregates</b></div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Operations on values:</div><div style="margin: 0px; line-height: normal;" class="">1. copy</div><div style="margin: 0px; line-height: normal;" class="">2. forward (move)</div><div style="margin: 0px; line-height: normal;" class="">3. borrow (share)</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">A copy or forward produces an owned value.</div><div style="margin: 0px; line-height: normal;" class="">An owned value has a single consumer.</div><div style="margin: 0px; line-height: normal;" class="">A borrow has static scope.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">For simplicity, passing a bb argument only has move semantics (it</div><div style="margin: 0px; line-height: normal;" class="">forwards the value). Later that can be expanded if needed.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">We want to allow simultaneous access to independent subelements of a</div><div style="margin: 0px; line-height: normal;" class="">fragile aggregate. We should be able to borrow one field while</div><div style="margin: 0px; line-height: normal;" class="">mutating another.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Is it possible to forward a subelement within an aggregate? No. But we</div><div style="margin: 0px; line-height: normal;" class="">can fully explode an owned aggregate into individual owned elements</div><div style="margin: 0px; line-height: normal;" class="">and reconstruct the aggregate. This makes use of the @exploded type</div><div style="margin: 0px; line-height: normal;" class="">feature described in the calling convention.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">[I don't think forwarding a subelement is useful anyway except for</div><div style="margin: 0px; line-height: normal;" class="">modeling @inout semantics...]</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">That leads us to this question: Does an @inout value reference have</div><div style="margin: 0px; line-height: normal;" class="">formal storage (thus a SIL address) or is it just a convention for</div><div style="margin: 0px; line-height: normal;" class="">passing owned SSA values?</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class=""><b class="">** World 1: SSA @inout</b></div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Projecting an element produces a new SILValue. Does this SILValue have</div><div style="margin: 0px; line-height: normal;" class="">it's own ownership associated with it's lifetime, or is it derived</div><div style="margin: 0px; line-height: normal;" class="">from it's parent object by looking through projections?</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Either way, projecting any subelement requires reconstructing the</div><div style="margin: 0px; line-height: normal;" class="">entire aggregate in SIL, through all nesting levels. This will</div><div style="margin: 0px; line-height: normal;" class="">generate a massive amount of SILValues. Superficially they all need</div><div style="margin: 0px; line-height: normal;" class="">their own storage.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">[We could claim that projections don't need storage, but that only</div><div style="margin: 0px; line-height: normal;" class="">solves one side of the problem.]</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">[I argue that this actually obscures the producer/consumer</div><div style="margin: 0px; line-height: normal;" class="">relationship, which is the opposite of the intention of moving to</div><div style="margin: 0px; line-height: normal;" class="">SSA. Projecting subelements for mutation fundamentally doesn't make</div><div style="margin: 0px; line-height: normal;" class="">sense. It does make sense to borrow a subelement (not for</div><div style="margin: 0px; line-height: normal;" class="">mutation). It also makes sense to project a mutable storage</div><div style="margin: 0px; line-height: normal;" class="">location. The natural way to project a storage location is by</div><div style="margin: 0px; line-height: normal;" class="">projecting an address...]</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class=""><b class="">** World 2: @inout formal storage</b></div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">In this world, @inout references continue to have SILType $*T with</div><div style="margin: 0px; line-height: normal;" class="">guaranteed exclusive access.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Memory state can be:</div><div style="margin: 0px; line-height: normal;" class="">- uninitialized</div><div style="margin: 0px; line-height: normal;" class="">- holds an owned value</div><div style="margin: 0px; line-height: normal;" class=""> - has exclusive access</div><div style="margin: 0px; line-height: normal;" class=""> - has shared access</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">--- expected transitions need to be handled</div><div style="margin: 0px; line-height: normal;" class=""> - must become uninitialized</div><div style="margin: 0px; line-height: normal;" class=""> - must become initialized</div><div style="margin: 0px; line-height: normal;" class=""> - must preserve initialization state</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">We need to mark initializers with some "must initialize" marker,</div><div style="margin: 0px; line-height: normal;" class="">similar to how we mark deinitializers [this isn't clear to me yet].</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">We could give address types qualifiers to distinguish the memory state</div><div style="margin: 0px; line-height: normal;" class="">of their pointee (uninitialized, shared, exclusive). Addresses</div><div style="margin: 0px; line-height: normal;" class="">themselves could be pseudo-linear types. This would provide the same</div><div style="margin: 0px; line-height: normal;" class="">use-def guarantees as the SSA @inout approach, but producing a new</div><div style="margin: 0px; line-height: normal;" class="">address each type memory changes states would also be complicated and</div><div style="margin: 0px; line-height: normal;" class="">cumbersome (though not as bad as SSA).</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">[[</div><div style="margin: 0px; line-height: normal;" class="">We didn't talk about the alternative, but presumably exclusive</div><div style="margin: 0px; line-height: normal;" class="">vs. shared scope would be delimited by pseudo memory operations as</div><div style="margin: 0px; line-height: normal;" class="">such:</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">%a1 = alloc_stack</div><div style="margin: 0px; line-height: normal; font-family: Menlo; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">begin_exclusive %a</div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">apply foo(%a) // must be marked an initializer?</div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">end_exclusive %a</div><div style="margin: 0px; line-height: normal; font-family: Menlo; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">begin_shared %a</div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">apply bar(%a) // immutable access</div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">end_shared %a</div><div style="margin: 0px; line-height: normal; font-family: Menlo; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">dealloc_stack %a</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Values loaded from shared memory also need to be scoped. They must be</div><div style="margin: 0px; line-height: normal;" class="">consumed within the shared region. e.g.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">%a2 = ref_element_addr</div><div style="margin: 0px; line-height: normal; font-family: Menlo; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">%x = load_borrow %a2</div><div style="margin: 0px; line-height: normal; font-family: Menlo; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class="">end_borrow %x, %a2</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">It makes sense to me that a load_borrow would implicitly transition</div><div style="margin: 0px; line-height: normal;" class="">memory to shared state, and end_borrow would implicitly return memory</div><div style="margin: 0px; line-height: normal;" class="">to an owned state. If the address type is already ($* @borrow T), then</div><div style="margin: 0px; line-height: normal;" class="">memory would remain in the shared state.</div><div style="margin: 0px; line-height: normal;" class="">]]</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">For all sorts of analysis and optimization, from borrow checking to</div><div style="margin: 0px; line-height: normal;" class="">CoW to ARC, we really need aliasing guarantees. Knowing we have a</div><div style="margin: 0px; line-height: normal;" class="">unique address to a location is about as good as having an owned</div><div style="margin: 0px; line-height: normal;" class="">value.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">To get this guarantee we need to structurally guarantee</div><div style="margin: 0px; line-height: normal;" class="">unique addresses.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">[Is there a way to do this with out making all the element_addr</div><div style="margin: 0px; line-height: normal;" class="">operations scoped?]</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">With aliasing guaratees, verification should be able to statically</div><div style="margin: 0px; line-height: normal;" class="">prove that most formal storage locations are properly initialized and</div><div style="margin: 0px; line-height: normal;" class="">uninitialized (pseudo-linear type) by inspecting the memory</div><div style="margin: 0px; line-height: normal;" class="">operations.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Likewise, we can verify the shared vs. exclusive states.</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">Representing @inout with addresses doesn't really add features to</div><div style="margin: 0px; line-height: normal;" class="">SIL. In any case, SIL address types are still used for</div><div style="margin: 0px; line-height: normal;" class="">formal storage. Exclusive access through any of the following</div><div style="margin: 0px; line-height: normal;" class="">operations must be guaranteed dynamically:</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">- ref_element_addr</div><div style="margin: 0px; line-height: normal;" class="">- global_addr</div><div style="margin: 0px; line-height: normal;" class="">- pointer_to_address</div><div style="margin: 0px; line-height: normal;" class="">- alloc_stack</div><div style="margin: 0px; line-height: normal;" class="">- project_box</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">We end up with these basic SIL Types:</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">$T = owned value</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">$@borrowed T = shared value</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">$*T = exclusively accessed</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">$* @borrowed T = shared access</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">[I think the non-address @borrowed type is only valid for concrete</div><div style="margin: 0px; line-height: normal;" class="">types that the compiler knows are not memory-linked? This can be used</div><div style="margin: 0px; line-height: normal;" class="">to avoid passing borrowed values indirectly for arrays and other</div><div style="margin: 0px; line-height: normal;" class="">small, free-to-copy values].</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">[We obviously need to work through concrete examples before we can</div><div style="margin: 0px; line-height: normal;" class="">claim to have a real design.]</div><div style="margin: 0px; line-height: normal; min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class="">-Andy</div><div class=""><br class=""></div></div>_______________________________________________<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=""></div></blockquote></div><br class=""></div></div></div></blockquote></div><br class=""></body></html>