> On Oct 7, 2016, at 6:04 PM, Michael Gottesman <[email protected]> wrote:
>> On Oct 7, 2016, at 5:09 PM, John McCall <[email protected]
>> <mailto:[email protected]>> wrote:
>>> On Oct 7, 2016, at 2:38 PM, Michael Gottesman <[email protected]
>>> <mailto:[email protected]>> wrote:
>>>
>>> Attached below is an updated version of the proposal. Again a rendered
>>> version is located at:
>>>
>>> https://gottesmm.github.io/proposals/high-level-arc-memory-operations.html
>>> <https://gottesmm.github.io/proposals/high-level-arc-memory-operations.html>
>>>
>>> Michael
>>>
>>> ----
>>>
>>> # Summary
>>>
>>> This document proposes:
>>>
>>> 1. adding the following ownership qualifiers to `load`: `[take]`, `[copy]`,
>>> `[borrow]`, `[trivial]`.
>>> 2. adding the following ownership qualifiers to `store`: `[init]`,
>>> `[assign]`,
>>> `[trivial]`.
>>> 3. requiring all `load` and `store` operations to have ownership qualifiers.
>>> 4. banning the use of `load [trivial]`, `store [trivial]` on memory
>>> locations of
>>> `non-trivial` type.
>>>
>>> This will allow for:
>>>
>>> 1. eliminating optimizer miscompiles that occur due to releases being moved
>>> into
>>> the region in between a `load`/`retain`, `load`/`release`,
>>> `store`/`release`. (For a specific example, see the appendix).
>>> 2. explicitly modeling `load [trivial]`/`store [trivial]` as having `unsafe
>>> unowned` ownership semantics. This will be enforced via the verifier.
>>> 3. more aggressive ARC code motion.
>>>
>>> # Definitions
>>>
>>> ## ownership qualified load
>>>
>>> We propose four different ownership qualifiers for load. Define `load
>>> [trivial]`
>>> as:
>>>
>>> %x = load [trivial] %x_ptr : $*Int
>>>
>>> =>
>>>
>>> %x = load %x_ptr : $*Int
>>>
>>> A `load [trivial]` can not be used to load values of non-trivial type.
>>
>> Should we mandate the reverse as well, that e.g. load [copy] cannot be used
>> to
>> load values of trivial type? That's a little more work for substituting
>> cloners, but it
>> keeps everything nice and canonical.
>
> No. I think that in the trivial case, load [copy] optimizes to load [trivial]
> as a canonicalization. This is just like applying a retain_value to a trivial
> type.
I guess I'm fine with that.
>>> Define
>>> `load [copy]` as:
>>>
>>> %x = load [copy] %x_ptr : $*C
>>>
>>> =>
>>>
>>> %x = load %x_ptr : $*C
>>> retain_value %x : $C
>>>
>>> Then define `load [take]` as:
>>>
>>> %x = load [take] %x_ptr : $*Builtin.NativeObject
>>>
>>> =>
>>>
>>> %x = load %x_ptr : $*Builtin.NativeObject
>>>
>>> **NOTE** `load [take]` implies that the loaded from memory location no
>>> longer
>>> owns the result object (i.e. a take is a move). Loading from the memory
>>> location
>>> again without reinitialization is illegal.
>>>
>>> Next we provide `load [borrow]`:
>>>
>>> %x = load [borrow] %x_ptr : $*Builtin.NativeObject
>>> ...
>>> endBorrow(%x, %x_ptr)
>>>
>>> =>
>>>
>>> %x = load %x_ptr : $*Builtin.NativeObject
>>> ...
>>> endBorrow(%x, %x_ptr)
>>>
>>> `load [borrow]` implies that in the region between the `load` and the
>>> `endBorrow`, the loaded object must semantically remain alive.
>>
>> For consistency with other multi-word SIL instructions, this should be
>> end_borrow.
>
> Sure.
>
>>
>> I wonder whether it might make more sense for load [borrow] to be a
>> different instruction.
>> There's a couple reasons for that first. The first is that it's the only
>> load which introduces
>> a scope, which is a really big difference structurally. The second is that
>> it's the only load
>> which returns a non-owned value, which will be a typing difference when we
>> record
>> ownership in the type system.
>
> I am fine with a load_borrow. If this is the only change left that you want
> can I just send out a proposal with that small change and start implementing.
> I am nervous about perfection being the enemy of the good (and I want to
> start implementing this weekend if possible *evil smile*).
Yes, it's fine to introduce this incrementally.
We can discuss the formation rules on scopes concurrently. I think the same
theoretical
foundation is probably what we'll use for pseudo-linearity,
memory-initialization soundness,
and so on.
John.
>> Anyway, I really like that load [borrow] is scoped.. Are you planning to
>> include the formation
>> restrictions on scopes instructions immediately, or will you do that in a
>> later proposal?
>
> It will be done in a later proposal. We are just trying to set the stage for
> verification.
>
>>
>> The requirements we need from scopes are:
>> - there has to be a well-defined set of IPs that lie within the scope and
>> - there can't be a non-explicit transition into or out of the scope.
>>
>> One way to get the first condition is to say that there has to be a unique
>> scope-ender that
>> post-dominates the scope-beginner, but that's a pretty hard restriction for
>> SILGen to satisfy
>> (as well as the optimizer, I imagine), and it doesn't handle "unreachable"
>> or infinite loops.
>> We need to allow multiple scope-enders, and we need to allow scope-enders to
>> be missing
>> in some cases.
>
> I agree with you here. We definitely want to be able to support multiple
> scope-enders.
>
>> Here's the right formalism, I think:
>>
>> For all walks W beginning from the entry point of the function:
>> For each node B in the CFG which is a scope-beginner:
>> Let E be the set of scope-enders for B, and consider just the
>> sub-sequence S of nodes
>> of W where the node is a member of {B} U E. Then the elements of S at
>> even
>> positions (starting from 0) must be B, and the elements at odd positions
>> must be
>> members of E. Furthermore, if the walk ends in a return or throw
>> instruction, then
>> S must have even length.
>>
>> Note that for this to be true, all the scope-enders must be dominated by the
>> scope-beginner.
>>
>> It is sufficient to just consider the set of "beeline" paths, i.e. acyclic
>> paths ending in either a true
>> terminator (a return, throw, or unreachable) or an edge back to a node
>> already in the path.
>> No such path may include multiple scope-enders for the same scope-beginner.
>> If the path ends
>> in a return or throw, it must include a matching scope-ender after every
>> scope-beginner. If
>> it ends in a loop back, then for every scope-beginner in the path, if the
>> path contains a scope-ender
>> then the loop destination must either precede the scope-beginner or follow
>> the scope-ender;
>> otherwise, the loop destination must follow the scope-beginner.
>>
>> Or, as a decision algorithm in Swift for a single scope-beginner:
>>
>> var blockEntryIsInScope = [Block: Bool]()
>> func scan(startingFrom inst: Instruction, isInScope: Bool) {
>> if inst is ReturnInst || inst is ThrowInst {
>> guard !isInScope else { invalid("ended function while in scope") }
>> return
>> }
>>
>> if let term = inst as? TerminatorInst {
>> for successor in term.successors {
>> guard begin.dominates(successor) else {
>> guard !isInScope else { invalid("branch out of scope while in
>> scope") }
>> continue
>> }
>> if let cachedValue = blockEntryIsInScope[successor] {
>> if cachedValue != isInScope {
>> invalid(isInScope ? "branch out of scope while in scope" :
>> "branch into scope after exiting scope")
>> }
>> } else {
>> blockEntryIsInScope[successor] = isInScope
>> scan(startingFrom: successor.begin, isInScope: isInScope)
>> }
>> }
>> return
>> }
>>
>> if inst.endsScopeOf(begin) {
>> guard isInScope else { invalid("ending scope that was already ended") }
>> scan(startingFrom: inst.next, isInScope: false)
>> } else {
>> scan(startingFrom: inst.next, isInScope: isInScope)
>> }
>> }
>> scan(startingFrom: begin, isInScope: true)
>
> Since this is tangential to the current proposal, can we introduce a side
> thread?
>
>>
>> John.
>>
>>> The `endBorrow` communicates to the optimizer:
>>>
>>> 1. That the value in `%x_ptr` should not be destroyed before endBorrow.
>>> 2. Uses of `%x` should not be sunk past endBorrow since `%x` is only a
>>> shallow
>>> copy of the value in `%x_ptr` and past that point `%x_ptr` may not remain
>>> alive.
>>>
>>> An example of where this construct is useful is when one has a let binding
>>> to a
>>> class instance `c` that contains a let field `f`. In that case `c`'s
>>> lifetime
>>> guarantees `f`'s lifetime meaning that returning `f` over the function call
>>> boundary is safe.
>>>
>>> ## ownership qualified store
>>>
>>> First define a `store [trivial]` as:
>>>
>>> store %x to [trivial] %x_ptr : $*Int
>>>
>>> =>
>>>
>>> store %x to %x_ptr : $*Int
>>>
>>> The verifier will prevent this instruction from being used on types with
>>> non-trivial ownership. Define a `store [assign]` as follows:
>>>
>>> store %x to [assign] %x_ptr : $*C
>>>
>>> =>
>>>
>>> %old_x = load %x_ptr : $*C
>>> store %new_x to %x_ptr : $*C
>>> release_value %old_x : $C
>>>
>>> *NOTE* `store` is defined as a consuming operation. We also provide
>>> `store [init]` in the case where we know statically that there is no
>>> previous value in the memory location:
>>>
>>> store %x to [init] %x_ptr : $*C
>>>
>>> =>
>>>
>>> store %new_x to %x_ptr : $*C
>>>
>>> # Implementation
>>>
>>> ## Goals
>>>
>>> Our implementation strategy goals are:
>>>
>>> 1. zero impact on other compiler developers until the feature is fully
>>> developed. This implies all work will be done behind a flag.
>>> 2. separation of feature implementation from updating passes.
>>>
>>> Goal 2 will be implemented via a pass that transforms ownership qualified
>>> `load`/`store` instructions into unqualified `load`/`store` right after
>>> SILGen.
>>>
>>> ## Plan
>>>
>>> We begin by adding initial infrastructure for our development. This means:
>>>
>>> 1. Adding to SILOptions a disabled by default flag called
>>> "EnableSILOwnershipModel". This flag will be set by a false by default
>>> frontend
>>> option called "-enable-sil-ownership-mode".
>>>
>>> 2. Bots will be brought up to test the compiler with
>>> "-enable-sil-ownership-model" set to true. The specific bots are:
>>>
>>> * RA-OSX+simulators
>>> * RA-Device
>>> * RA-Linux.
>>>
>>> The bots will run once a day until the feature is close to completion.
>>> Then a
>>> polling model will be followed.
>>>
>>> Now that change isolation is borrow, we develop building blocks for the
>>> optimization:
>>>
>>> 1. Two enums will be defined: `LoadInstOwnershipQualifier`,
>>> `StoreInstOwnershipQualifier`. The exact definition of these enums are as
>>> follows:
>>>
>>> enum class LoadOwnershipQualifier {
>>> Unqualified, Take, Copy, Borrow, Trivial
>>> };
>>> enum class StoreOwnershipQualifier {
>>> Unqualified, Init, Assign, Trivial
>>> };
>>>
>>> *NOTE* `LoadOwnershipQualifier::Unqualified` and
>>> `StoreOwnershipQualifier::Unqualified` are only needed for staging
>>> purposes.
>>>
>>> 2. Creating a `LoadInst`, `StoreInst` will be changed to require an
>>> ownership
>>> qualifier. At this stage, this argument will default to `Unqualified`.
>>> "Bare"
>>> `load`, `store` when parsed via textual SIL will be considered to be
>>> unqualified. This implies that the rest of the compiler will not have to be
>>> changed as a result of this step.
>>>
>>> 3. Support will be added to SIL, IRGen, Serialization, SILPrinting, and SIL
>>> Parsing for the rest of the qualifiers. SILGen will not be modified at this
>>> stage.
>>>
>>> 4. A pass called the "OwnershipModelEliminator" will be implemented. It will
>>> blow up all `load`, `store` instructions with non `*::Unqualified`
>>> ownership
>>> into their constituant ARC operations and `*::Unqualified` `load`,
>>> `store`
>>> insts.
>>>
>>> 3. An option called "EnforceSILOwnershipMode" will be added to the
>>> verifier. If
>>> the option is set, the verifier will assert if:
>>>
>>> a. `load`, `store` operations with trivial ownership are applied to
>>> memory
>>> locations with non-trivial type.
>>>
>>> b. `load`, `store` operation with unqualified ownership type are present
>>> in
>>> the IR.
>>>
>>> Finally, we wire up the building blocks:
>>>
>>> 1. If SILOption.EnableSILOwnershipModel is true, then the after SILGen SIL
>>> verification will be performed with EnforceSILOwnershipModel set to true.
>>> 2. If SILOption.EnableSILOwnershipModel is true, then the pass manager will
>>> run
>>> the OwnershipModelEliminator pass right after SILGen before the normal
>>> pass
>>> pipeline starts.
>>> 3. SILGen will be changed to emit non-unqualified ownership qualifiers on
>>> load,
>>> store instructions when the EnableSILOwnershipModel flag is set. We will
>>> use
>>> the verifier throwing to guarantee that we are not missing any specific
>>> cases.
>>>
>>> Then once all of the bots are green, we change
>>> SILOption.EnableSILOwnershipModel
>>> to be true by default. After a cooling off period, we move all of the code
>>> behind the SILOwnershipModel flag in front of the flag. We do this so we can
>>> reuse that flag for further SILOwnershipModel changes.
>>>
>>> ## Optimizer Changes
>>>
>>> Since the SILOwnershipModel eliminator will eliminate the ownership
>>> qualifiers
>>> on load, store instructions right after ownership verification, there will
>>> be no
>>> immediate affects on the optimizer and thus the optimizer changes can be
>>> done in
>>> parallel with the rest of the ARC optimization work.
>>>
>>> But, in the long run, we want to enforce these ownership invariants all
>>> throughout the SIL pipeline implying these ownership qualified `load`,
>>> `store`
>>> instructions must be processed by IRGen, not eliminated by the
>>> SILOwnershipModel
>>> eliminator. Thus we will need to update passes to handle these new
>>> instructions. The main optimizer changes can be separated into the following
>>> areas: memory forwarding, dead stores, ARC optimization. In all of these
>>> cases,
>>> the necessary changes are relatively trivial to respond to. We give a quick
>>> taste of two of them: store->load forwarding and ARC Code Motion.
>>>
>>> ### store->load forwarding
>>>
>>> Currently we perform store->load forwarding as follows:
>>>
>>> store %x to %x_ptr : $C
>>> ... NO SIDE EFFECTS THAT TOUCH X_PTR ...
>>> %y = load %x_ptr : $C
>>> use(%y)
>>>
>>> =>
>>>
>>> store %x to %x_ptr : $C
>>> ... NO SIDE EFFECTS THAT TOUCH X_PTR ...
>>> use(%x)
>>>
>>> In a world, where we are using ownership qualified load, store, we have to
>>> also
>>> consider the ownership implications. *NOTE* Since we are not modifying the
>>> store, `store [assign]` and `store [init]` are treated the same. Thus
>>> without
>>> any loss of generality, lets consider solely `store`.
>>>
>>> store %x to [assign] %x_ptr : $C
>>> ... NO SIDE EFFECTS THAT TOUCH X_PTR ...
>>> %y = load [copy] %x_ptr : $C
>>> use(%y)
>>>
>>> =>
>>>
>>> store %x to [assign] %x_ptr : $C
>>> ... NO SIDE EFFECTS THAT TOUCH X_PTR ...
>>> strong_retain %x
>>> use(%x)
>>>
>>> ### ARC Code Motion
>>>
>>> If ARC Code Motion wishes to move the ARC semantics of ownership qualified
>>> `load`, `store` instructions, it must now consider read/write effects. On
>>> the
>>> other hand, it will be able to now not consider the side-effects of
>>> destructors
>>> when moving retain/release operations.
>>>
>>> ### Normal Code Motion
>>>
>>> Normal code motion will lose some effectiveness since many of the load/store
>>> operations that it used to be able to move now must consider ARC
>>> information. We
>>> may need to consider running ARC code motion earlier in the pipeline where
>>> we
>>> normally run Normal Code Motion to ensure that we are able to handle these
>>> cases.
>>>
>>> ### ARC Optimization
>>>
>>> The main implication for ARC optimization is that instead of eliminating
>>> just
>>> retains, releases, it must be able to recognize ownership qualified `load`,
>>> `store` and set their flags as appropriate.
>>>
>>> ### Function Signature Optimization
>>>
>>> Semantic ARC affects function signature optimization in the context of the
>>> owned
>>> to borrow optimization. Specifically:
>>>
>>> 1. A `store [assign]` must be recognized as a release of the old value that
>>> is
>>> being overridden. In such a case, we can move the `release` of the old
>>> value
>>> into the caller and change the `store [assign]` into a `store [init]`.
>>> 2. A `load [copy]` must be recognized as a retain in the callee. Then
>>> function
>>> signature optimization will transform the `load [copy]` into a `load
>>> [borrow]`. This would require the addition of a new `@borrow` return
>>> value convention.
>>>
>>> # Appendix
>>>
>>> ## Partial Initialization of Loadable References in SIL
>>>
>>> In SIL, a value of non-trivial loadable type is loaded from a memory
>>> location as
>>> follows:
>>>
>>> %x = load %x_ptr : $*S
>>> ...
>>> retain_value %x_ptr : $S
>>>
>>> At first glance, this looks reasonable, but in truth there is a hidden
>>> drawback:
>>> the partially initialized zone in between the load and the retain
>>> operation. This zone creates a period of time when an "evil optimizer" could
>>> insert an instruction that causes x to be deallocated before the copy is
>>> finished being initialized. Similar issues come up when trying to perform a
>>> store of a non-trival value into a memory location.
>>>
>>> Since this sort of partial initialization is allowed in SIL, the optimizer
>>> is
>>> forced to be overly conservative when attempting to move releases passed
>>> retains
>>> lest the release triggers a deinit that destroys a value like `%x`. Lets
>>> look at
>>> two concrete examples that show how semantically providing ownership
>>> qualified
>>> load, store instructions eliminate this problem.
>>>
>>> **NOTE** Without any loss of generality, we will speak of values with
>>> reference
>>> semantics instead of non-trivial values.
>>>
>>> ## Case Study: Partial Initialization and load [copy]
>>>
>>> ### The Problem
>>>
>>> Consider the following swift program:
>>>
>>> func opaque_call()
>>>
>>> final class C {
>>> var int: Int = 0
>>> deinit {
>>> opaque_call()
>>> }
>>> }
>>>
>>> final class D {
>>> var int: Int = 0
>>> }
>>>
>>> var GLOBAL_C : C? = nil
>>> var GLOBAL_D : D? = nil
>>>
>>> func useC(_ c: C)
>>> func useD(_ d: D)
>>>
>>> func run() {
>>> let c = C()
>>> GLOBAL_C = c
>>> let d = D()
>>> GLOBAL_D = d
>>> useC(c)
>>> useD(d)
>>> }
>>>
>>> Notice that both `C` and `D` have fixed layouts and separate class
>>> hierarchies,
>>> but `C`'s deinit has a call to the function `opaque_call` which may write to
>>> `GLOBAL_D` or `GLOBAL_C`. Additionally assume that both `useC` and `useD`
>>> are
>>> known to the compiler to not have any affects on instances of type `D`, `C`
>>> respectively and useC assigns `nil` to `GLOBAL_C`. Now consider the
>>> following
>>> valid SIL lowering for `run`:
>>>
>>> sil_global GLOBAL_D : $D
>>> sil_global GLOBAL_C : $C
>>>
>>> final class C {
>>> var x: Int
>>> deinit
>>> }
>>>
>>> final class D {
>>> var x: Int
>>> }
>>>
>>> sil @useC : $@convention(thin) () -> ()
>>> sil @useD : $@convention(thin) () -> ()
>>>
>>> sil @run : $@convention(thin) () -> () {
>>> bb0:
>>> %c = alloc_ref $C
>>> %global_c = global_addr @GLOBAL_C : $*C
>>> strong_retain %c : $C
>>> store %c to %global_c : $*C
>>> (1)
>>>
>>> %d = alloc_ref $D
>>> %global_d = global_addr @GLOBAL_D : $*D
>>> strong_retain %d : $D
>>> store %d to %global_d : $*D
>>> (2)
>>>
>>> %c2 = load %global_c : $*C
>>> (3)
>>> strong_retain %c2 : $C
>>> (4)
>>> %d2 = load %global_d : $*D
>>> (5)
>>> strong_retain %d2 : $D
>>> (6)
>>>
>>> %useC_func = function_ref @useC : $@convention(thin) (@owned C) -> ()
>>> apply %useC_func(%c2) : $@convention(thin) (@owned C) -> ()
>>> (7)
>>>
>>> %useD_func = function_ref @useD : $@convention(thin) (@owned D) -> ()
>>> apply %useD_func(%d2) : $@convention(thin) (@owned D) -> ()
>>> (8)
>>>
>>> strong_release %d : $D
>>> (9)
>>> strong_release %c : $C
>>> (10)
>>> }
>>>
>>> Lets optimize this function! First we perform the following operations:
>>>
>>> 1. Since `(2)` is storing to an identified object that can not be
>>> `GLOBAL_C`, we
>>> can store to load forward `(1)` to `(3)`.
>>> 2. Since a retain does not block store to load forwarding, we can forward
>>> `(2)`
>>> to `(5)`. But lets for the sake of argument, assume that the optimizer
>>> keeps
>>> such information as an analysis and does not perform the actual
>>> load->store
>>> forwarding.
>>> 3. Even though we do not foward `(2)` to `(5)`, we can still move `(4)` over
>>> `(6)` so that `(4)` is right before `(7)`.
>>>
>>> This yields (using the ' marker to designate that a register has had
>>> load-store
>>> forwarding applied to it):
>>>
>>> sil @run : $@convention(thin) () -> () {
>>> bb0:
>>> %c = alloc_ref $C
>>> %global_c = global_addr @GLOBAL_C : $*C
>>> strong_retain %c : $C
>>> store %c to %global_c : $*C
>>> (1)
>>>
>>> %d = alloc_ref $D
>>> %global_d = global_addr @GLOBAL_D : $*D
>>> strong_retain %d : $D
>>> store %d to %global_d : $*D
>>> (2)
>>>
>>> strong_retain %c : $C
>>> (4')
>>> %d2 = load %global_d : $*D
>>> (5)
>>> strong_retain %d2 : $D
>>> (6)
>>>
>>> %useC_func = function_ref @useC : $@convention(thin) (@owned C) -> ()
>>> apply %useC_func(%c) : $@convention(thin) (@owned C) -> ()
>>> (7')
>>>
>>> %useD_func = function_ref @useD : $@convention(thin) (@owned D) -> ()
>>> apply %useD_func(%d2) : $@convention(thin) (@owned D) -> ()
>>> (8)
>>>
>>> strong_release %d : $D
>>> (9)
>>> strong_release %c : $C
>>> (10)
>>> }
>>>
>>> Then by assumption, we know that `%useC` does not perform any releases of
>>> any
>>> instances of class `D`. Thus `(6)` can be moved past `(7')` and we can then
>>> pair
>>> and eliminate `(6)` and `(9)` via the rules of ARC optimization using the
>>> analysis information that `%d2` and `%d` are th same due to the possibility
>>> of
>>> performing store->load forwarding. After performing such transformations,
>>> `run`
>>> looks as follows:
>>>
>>> sil @run : $@convention(thin) () -> () {
>>> bb0:
>>> %c = alloc_ref $C
>>> %global_c = global_addr @GLOBAL_C : $*C
>>> strong_retain %c : $C
>>> store %c to %global_c : $*C
>>> (1)
>>>
>>> %d = alloc_ref $D
>>> %global_d = global_addr @GLOBAL_D : $*D
>>> strong_retain %d : $D
>>> store %d to %global_d : $*D
>>>
>>> %d2 = load %global_d : $*D
>>> (5)
>>> strong_retain %c : $C
>>> (4')
>>> %useC_func = function_ref @useC : $@convention(thin) (@owned C) -> ()
>>> apply %useC_func(%c) : $@convention(thin) (@owned C) -> ()
>>> (7')
>>>
>>> %useD_func = function_ref @useD : $@convention(thin) (@owned D) -> ()
>>> apply %useD_func(%d2) : $@convention(thin) (@owned D) -> ()
>>> (8)
>>>
>>> strong_release %c : $C
>>> (10)
>>> }
>>>
>>> Now by assumption, we know that `%useD_func` does not touch any instances of
>>> class `C` and `%c` does not contain any ivars of type `D` and is final so
>>> none
>>> can be added. At first glance, this seems to suggest that we can move `(10)`
>>> before `(8')` and then pair/eliminate `(4')` and `(10)`. But is this a safe
>>> optimization perform? Absolutely Not! Why? Remember that since `useC_func`
>>> assigns `nil` to `GLOBAL_C`, after `(7')`, `%c` could have a reference count
>>> of 1. Thus `(10)` _may_ invoke the destructor of `C`. Since this destructor
>>> calls an opaque function that _could_ potentially write to `GLOBAL_D`, we
>>> may be
>>> be passing `%d2`, an already deallocated object to `%useD_func`, an illegal
>>> optimization!
>>>
>>> Lets think a bit more about this example and consider this example at the
>>> language level. Remember that while Swift's deinit are not asychronous, we
>>> do
>>> not allow for user level code to create dependencies from the body of the
>>> destructor into the normal control flow that has called it. This means that
>>> there are two valid results of this code:
>>>
>>> - Operation Sequence 1: No optimization is performed and `%d2` is passed to
>>> `%useD_func`.
>>> - Operation Sequence 2: We shorten the lifetime of `%c` before `%useD_func`
>>> and
>>> a different instance of `$D` is passed into `%useD_func`.
>>>
>>> The fact that 1 occurs without optimization is just as a result of an
>>> implementation detail of SILGen. 2 is also a valid sequence of operations.
>>>
>>> Given that:
>>>
>>> 1. As a principle, the optimizer does not consider such dependencies to
>>> avoid
>>> being overly conservative.
>>> 2. We provide constructs to ensure appropriate lifetimes via the usage of
>>> constructs such as fix_lifetime.
>>>
>>> We need to figure out how to express our optimization such that 2
>>> happens. Remember that one of the optimizations that we performed at the
>>> beginning was to move `(6)` over `(7')`, i.e., transform this:
>>>
>>> %d = alloc_ref $D
>>> %global_d_addr = global_addr GLOBAL_D : $D
>>> %d = load %global_d_addr : $*D (5)
>>> strong_retain %d : $D (6)
>>>
>>> // Call the user functions passing in the instances that we loaded
>>> from the globals.
>>> %useC_func = function_ref @useC : $@convention(thin) (@owned C) -> ()
>>> apply %useC_func(%c) : $@convention(thin) (@owned C) -> ()
>>> (7')
>>>
>>> into:
>>>
>>> %global_d_addr = global_addr GLOBAL_D : $D
>>> %d2 = load %global_d_addr : $*D (5)
>>>
>>> // Call the user functions passing in the instances that we loaded
>>> from the globals.
>>> %useC_func = function_ref @useC : $@convention(thin) (@owned C) -> ()
>>> apply %useC_func(%c) : $@convention(thin) (@owned C) -> ()
>>> (7')
>>> strong_retain %d2 : $D (6)
>>>
>>> This transformation in Swift corresponds to transforming:
>>>
>>> let d = GLOBAL_D
>>> useC(c)
>>>
>>> to:
>>>
>>> let d_raw = load_d_value(GLOBAL_D)
>>> useC(c)
>>> let d = take_ownership_of_d(d_raw)
>>>
>>> This is clearly an instance where we have moved a side-effect in between the
>>> loading of the data and the taking ownership of such data, that is before
>>> the
>>> `let` is fully initialized. What if instead of just moving the retain, we
>>> moved
>>> the entire let statement? This would then result in the following swift
>>> code:
>>>
>>> useC(c)
>>> let d = GLOBAL_D
>>>
>>> and would correspond to the following SIL snippet:
>>>
>>> %global_d_addr = global_addr GLOBAL_D : $D
>>>
>>> // Call the user functions passing in the instances that we loaded
>>> from the globals.
>>> %useC_func = function_ref @useC : $@convention(thin) (@owned C) -> ()
>>> apply %useC_func(%c) : $@convention(thin) (@owned C) -> ()
>>> (7')
>>> %d2 = load %global_d_addr : $*D
>>> (5)
>>> strong_retain %d2 : $D
>>> (6)
>>>
>>> Moving the load with the strong_retain to ensure that the full
>>> initialization is
>>> performed even after code motion causes our SIL to look as follows:
>>>
>>> sil @run : $@convention(thin) () -> () {
>>> bb0:
>>> %c = alloc_ref $C
>>> %global_c = global_addr @GLOBAL_C : $*C
>>> strong_retain %c : $C
>>> store %c to %global_c : $*C
>>> (1)
>>>
>>> %d = alloc_ref $D
>>> %global_d = global_addr @GLOBAL_D : $*D
>>> strong_retain %d : $D
>>> store %d to %global_d : $*D
>>>
>>> strong_retain %c : $C
>>> (4')
>>> %useC_func = function_ref @useC : $@convention(thin) (@owned C) -> ()
>>> apply %useC_func(%c) : $@convention(thin) (@owned C) -> ()
>>> (7')
>>>
>>> %d2 = load %global_d : $*D
>>> (5)
>>> %useD_func = function_ref @useD : $@convention(thin) (@owned D) -> ()
>>> apply %useD_func(%d2) : $@convention(thin) (@owned D) -> ()
>>> (8)
>>>
>>> strong_release %c : $C
>>> (10)
>>> }
>>>
>>> Giving us the exact result that we want: Operation Sequence 2!
>>>
>>> ### Defining load [copy]
>>>
>>> Given that we wish the load, store to be tightly coupled together, it is
>>> natural
>>> to express this operation as a `load [copy]` instruction. Lets define the
>>> `load
>>> [copy]` instruction as follows:
>>>
>>> %1 = load [copy] %0 : $*C
>>>
>>> =>
>>>
>>> %1 = load %0 : $*C
>>> retain_value %1 : $C
>>>
>>> Now lets transform our initial example to use this instruction:
>>>
>>> Notice how now if we move `(7)` over `(3)` and `(6)` now, we get the
>>> following SIL:
>>>
>>> sil @run : $@convention(thin) () -> () {
>>> bb0:
>>> %c = alloc_ref $C
>>> %global_c = global_addr @GLOBAL_C : $*C
>>> strong_retain %c : $C
>>> store %c to %global_c : $*C
>>> (1)
>>>
>>> %d = alloc_ref $D
>>> %global_d = global_addr @GLOBAL_D : $*D
>>> strong_retain %d : $D
>>> store %d to %global_d : $*D
>>> (2)
>>>
>>> %c2 = load [copy] %global_c : $*C
>>> (3)
>>> %d2 = load [copy] %global_d : $*D
>>> (5)
>>>
>>> %useC_func = function_ref @useC : $@convention(thin) (@owned C) -> ()
>>> apply %useC_func(%c2) : $@convention(thin) (@owned C) -> ()
>>> (7)
>>>
>>> %useD_func = function_ref @useD : $@convention(thin) (@owned D) -> ()
>>> apply %useD_func(%d2) : $@convention(thin) (@owned D) -> ()
>>> (8)
>>>
>>> strong_release %d : $D
>>> (9)
>>> strong_release %c : $C
>>> (10)
>>> }
>>>
>>> We then perform the previous code motion:
>>>
>>> sil @run : $@convention(thin) () -> () {
>>> bb0:
>>> %c = alloc_ref $C
>>> %global_c = global_addr @GLOBAL_C : $*C
>>> strong_retain %c : $C
>>> store %c to %global_c : $*C
>>> (1)
>>>
>>> %d = alloc_ref $D
>>> %global_d = global_addr @GLOBAL_D : $*D
>>> strong_retain %d : $D
>>> store %d to %global_d : $*D
>>> (2)
>>>
>>> %c2 = load [copy] %global_c : $*C
>>> (3)
>>> %useC_func = function_ref @useC : $@convention(thin) (@owned C) -> ()
>>> apply %useC_func(%c2) : $@convention(thin) (@owned C) -> ()
>>> (7)
>>> strong_release %d : $D
>>> (9)
>>>
>>> %d2 = load [copy] %global_d : $*D
>>> (5)
>>> %useD_func = function_ref @useD : $@convention(thin) (@owned D) -> ()
>>> apply %useD_func(%d2) : $@convention(thin) (@owned D) -> ()
>>> (8)
>>> strong_release %c : $C
>>> (10)
>>> }
>>>
>>> We then would like to eliminate `(9)` and `(10)` by pairing them with `(3)`
>>> and
>>> `(8)`. Can we still do so? One way we could do this is by introducing the
>>> `[take]` flag. The `[take]` flag on a `load [take]` says that one is
>>> semantically loading a value from a memory location and are taking
>>> ownership of
>>> the value thus eliding the retain. In terms of SIL this flag is defined as:
>>>
>>> %x = load [take] %x_ptr : $*C
>>>
>>> =>
>>>
>>> %x = load %x_ptr : $*C
>>>
>>> Why do we care about having such a `load [take]` instruction when we could
>>> just
>>> use a `load`? The reason why is that a normal `load` has unsafe unowned
>>> ownership (i.e. it has no implications on ownership). We would like for
>>> memory
>>> that has non-trivial type to only be able to be loaded via instructions that
>>> maintain said ownership. We will allow for casting to trivial types as
>>> usual to
>>> provide such access if it is required.
>>>
>>> Thus we have achieved the desired result:
>>>
>>> sil @run : $@convention(thin) () -> () {
>>> bb0:
>>> %c = alloc_ref $C
>>> %global_c = global_addr @GLOBAL_C : $*C
>>> strong_retain %c : $C
>>> store %c to %global_c : $*C
>>> (1)
>>>
>>> %d = alloc_ref $D
>>> %global_d = global_addr @GLOBAL_D : $*D
>>> strong_retain %d : $D
>>> store %d to %global_d : $*D
>>> (2)
>>>
>>> %c2 = load [take] %global_c : $*C
>>> (3)
>>> %useC_func = function_ref @useC : $@convention(thin) (@owned C) -> ()
>>> apply %useC_func(%c2) : $@convention(thin) (@owned C) -> ()
>>> (7)
>>>
>>> %d2 = load [take] %global_d : $*D
>>> (5)
>>> %useD_func = function_ref @useD : $@convention(thin) (@owned D) -> ()
>>> apply %useD_func(%d2) : $@convention(thin) (@owned D) -> ()
>>> (8)
>>> }
>>>
>>>
>>>> On Oct 6, 2016, at 3:03 PM, John McCall <[email protected]
>>>> <mailto:[email protected]>> wrote:
>>>>
>>>>> On Oct 5, 2016, at 4:48 PM, Michael Gottesman <[email protected]
>>>>> <mailto:[email protected]>> wrote:
>>>>>> On Oct 5, 2016, at 4:40 PM, Michael Gottesman via swift-dev
>>>>>> <[email protected] <mailto:[email protected]>> wrote:
>>>>>>
>>>>>>>
>>>>>>> On Oct 4, 2016, at 1:04 PM, John McCall <[email protected]
>>>>>>> <mailto:[email protected]>> wrote:
>>>>>>>
>>>>>>>>
>>>>>>>> On Sep 30, 2016, at 11:54 PM, Michael Gottesman via swift-dev
>>>>>>>> <[email protected] <mailto:[email protected]>> wrote:
>>>>>>>>
>>>>>>>> The document attached below contains the first "Semantic ARC" mini
>>>>>>>> proposal: the High Level ARC Memory Operations Proposal.
>>>>>>>>
>>>>>>>> An html rendered version of this markdown document is available at the
>>>>>>>> following URL:
>>>>>>>>
>>>>>>>> https://gottesmm.github.io/proposals/high-level-arc-memory-operations.html
>>>>>>>>
>>>>>>>> <https://gottesmm.github.io/proposals/high-level-arc-memory-operations.html>
>>>>>>>>
>>>>>>>> ----
>>>>>>>>
>>>>>>>> # Summary
>>>>>>>>
>>>>>>>> This document proposes:
>>>>>>>>
>>>>>>>> 1. adding the `load_strong`, `store_strong` instructions to SIL. These
>>>>>>>> can only
>>>>>>>> be used with memory locations of `non-trivial` type.
>>>>>>>
>>>>>>> I would really like to avoid using the word "strong" here. Under the
>>>>>>> current proposal, these instructions will be usable with arbitrary
>>>>>>> non-trivial types, not just primitive class references. Even if you
>>>>>>> think of an aggregate that happens to contain one or more strong
>>>>>>> references as some sort of aggregate strong reference (which is
>>>>>>> questionable but not completely absurd), we already have loadable
>>>>>>> non-strong class references that this operation would be usable with,
>>>>>>> like native unowned references. "load_strong %0 : $*@sil_unowned T" as
>>>>>>> an operation yielding a scalar "@sil_unowned T" is ridiculous, and it
>>>>>>> will only get more ridiculous when we eventually allow this operation
>>>>>>> to work with types that are currently address-only, like weak
>>>>>>> references.
>>>>>>>
>>>>>>> Brainstorming:
>>>>>>>
>>>>>>> Something like load_copy and store_copy would be a bit unfortunate,
>>>>>>> since store_copy doesn't actually copy the source operand and we want
>>>>>>> to have a load_copy [take].
>>>>>>>
>>>>>>> load_value and store_value seem excessively generic. It's not like
>>>>>>> non-trivial types aren't values.
>>>>>>>
>>>>>>> One question that comes to mind: do we actually need new instructions
>>>>>>> here other than for staging purposes? We don't actually need new
>>>>>>> instructions for pseudo-linear SIL to work; we just need to say that we
>>>>>>> only enforce pseudo-linearity for non-trivial types.
>>>>>>>
>>>>>>> If we just want the instruction to be explicit about ownership so that
>>>>>>> we can easily distinguish these cases, we can make the rule always
>>>>>>> explicit, e.g.:
>>>>>>> load [take] %0 : $*MyClass
>>>>>>> load [copy] %0 : $*MyClass
>>>>>>> load [trivial] %0 : $*Int
>>>>>>>
>>>>>>> store %0 to [initialization] %1 : $*MyClass
>>>>>>> store %0 to [assignment] %1 : $*MyClass
>>>>>>> store %0 to [trivial] %1 : $*Int
>>>>>>>
>>>>>>> John.
>>>>>>
>>>>>> The reason why I originally suggested to go the load_strong route is
>>>>>> that we already have load_weak, load_unowned instructions. If I could
>>>>>> add a load_strong instruction, then it would make sense to assign an
>>>>>> engineer to do a pass over all 3 of these instructions and combine them
>>>>>> into 1 load instruction. That is, first transform into a form amenable
>>>>>> for canonicalization and then canonicalize all at once.
>>>>>>
>>>>>> As you pointed out, both load_unowned and load_weak involve
>>>>>> representation changes in type (for instance the change of weak pointers
>>>>>> to Optional<T>). Such a change would be against the "spirit" of a load
>>>>>> instruction to perform such representation changes versus ownership
>>>>>> changes.
>>>>>>
>>>>>> In terms of the properties that we actually want here, what is important
>>>>>> is that we can verify that no non-trivially typed values are loaded in
>>>>>> an unsafe unowned manner. That can be done also with ownership flags on
>>>>>> load/store.
>>>>>>
>>>>>> Does this sound reasonable:
>>>>>>
>>>>>> 1. We introduce two enums that define memory ownership changes, one for
>>>>>> load and one for store. Both of these enums will contain a [trivial]
>>>>>> ownership.
>>>>>> 2. We enforce in the verifier that non-trivial types must have a
>>>>>> non-trivial ownership modifier on any memory operations that they are
>>>>>> involved in.
>>>>>
>>>>> Sorry for not being explicit. I will not add new instructions, just
>>>>> modifiers. Assuming that this is agreeable to you, I am going to prepare
>>>>> a quick additional version of the proposal document.
>>>>
>>>> That sounds great, thanks.
>>>>
>>>> John.
>
_______________________________________________
swift-dev mailing list
[email protected]
https://lists.swift.org/mailman/listinfo/swift-dev
