[swift-dev] Proposal: SILValue SSA Instructions

Wed Dec 7 18:44:36 CST 2016

> On Dec 7, 2016, at 3:20 PM, Andrew Trick <atrick at apple.com> wrote:
>> On Dec 7, 2016, at 3:16 PM, Michael Gottesman <mgottesman at apple.com <mailto:mgottesman at apple.com>> wrote:
>>> On Dec 7, 2016, at 2:52 PM, Andrew Trick via swift-dev <swift-dev at swift.org <mailto:swift-dev at swift.org>> wrote:
>>> 
>>> 
>>>> On Dec 6, 2016, at 2:23 PM, John McCall via swift-dev <swift-dev at swift.org <mailto:swift-dev at swift.org>> wrote:
>>>> 
>>>>> On Dec 6, 2016, at 11:35 AM, Joe Groff <jgroff at apple.com <mailto:jgroff at apple.com>> wrote:
>>>>>> On Dec 6, 2016, at 11:29 AM, John McCall <rjmccall at apple.com <mailto:rjmccall at apple.com>> wrote:
>>>>>> 
>>>>>>> On Dec 6, 2016, at 10:17 AM, Joe Groff via swift-dev <swift-dev at swift.org <mailto:swift-dev at swift.org>> wrote:
>>>>>>>> On Dec 5, 2016, at 4:24 PM, Michael Gottesman via swift-dev <swift-dev at swift.org <mailto:swift-dev at swift.org>> wrote:
>>>>>>>> 
>>>>>>>> Hello everyone!
>>>>>>>> 
>>>>>>>> This is a proposal for 2 instructions needed to express borrowing via SSA at the SIL level. The need for these were discovered while I was prototyping a SIL ownership verifier.
>>>>>>>> 
>>>>>>>> A html version of the proposal:
>>>>>>>> 
>>>>>>>> https://gottesmm.github.io/proposals/sil-ownership-value-ssa-operations.html <https://gottesmm.github.io/proposals/sil-ownership-value-ssa-operations.html>
>>>>>>>> 
>>>>>>>> And inline:
>>>>>>>> 
>>>>>>>> ----
>>>>>>>> 
>>>>>>>> # Summary
>>>>>>>> 
>>>>>>>> This document proposes the addition of the following new SIL instructions:
>>>>>>>> 
>>>>>>>> 1. `store_borrow`
>>>>>>>> 2. `begin_borrow`
>>>>>>>> 
>>>>>>>> These enable the expression of the following operations in Semantic SIL:
>>>>>>>> 
>>>>>>>> 1. Passing an `@guaranteed` value to an `@in_guaranteed` argument without
>>>>>>>> performing a copy. (`store_borrow`)
>>>>>>>> 2. Copying a field from an `@owned` aggregate without consuming or copying the entire
>>>>>>>> aggregate. (`begin_borrow`)
>>>>>>>> 3. Passing an `@owned` value as an `@guaranteed` argument parameter.
>>>>>>>> 
>>>>>>>> # Definitions
>>>>>>>> 
>>>>>>>> ## store_borrow
>>>>>>>> 
>>>>>>>> Define `store_borrow` as:
>>>>>>>> 
>>>>>>>>  store_borrow %x to %y : $*T
>>>>>>>>  ...
>>>>>>>>  end_borrow %y from %x : $*T, $T
>>>>>>>> 
>>>>>>>>    =>
>>>>>>>> 
>>>>>>>>  store %x to %y
>>>>>>>> 
>>>>>>>> `store_borrow` is needed to convert `@guaranteed` values to `@in_guaranteed`
>>>>>>>> arguments. Without a `store_borrow`, this can only be expressed via an
>>>>>>>> inefficient `copy_value` + `store` + `load` + `destroy_value` sequence:
>>>>>>>> 
>>>>>>>>  sil @g : $@convention(thin) (@in_guaranteed Foo) -> ()
>>>>>>>> 
>>>>>>>>  sil @f : $@convention(thin) (@guaranteed Foo) -> () {
>>>>>>>>  bb0(%0 : $Foo):
>>>>>>>>    %1 = function_ref @g : $@convention(thin) (@in_guaranteed Foo) -> ()
>>>>>>>>    %2 = alloc_stack $Foo
>>>>>>>>    %3 = copy_value %0 : $Foo
>>>>>>>>    store %3 to [init] %2 : $Foo
>>>>>>>>    apply %1(%2) : $@convention(thin) (@in_guaranteed Foo) -> ()
>>>>>>>>    %4 = load [take] %2 : $*Foo
>>>>>>>>    destroy_value %4 : $Foo
>>>>>>>>    dealloc_stack %2 : $Foo
>>>>>>>>    ...
>>>>>>>>  }
>>>>>>>> 
>>>>>>>> `store_borrow` allows us to express this in a more efficient and expressive SIL:
>>>>>>>> 
>>>>>>>>  sil @f : $@convention(thin) (@guaranteed Foo) -> () {
>>>>>>>>  bb0(%0 : $Foo):
>>>>>>>>    %1 = function_ref @g : $@convention(thin) (@in_guaranteed Foo) -> ()
>>>>>>>>    %2 = alloc_stack $Foo
>>>>>>>>    store_borrow %0 to %2 : $*T
>>>>>>>>    apply %1(%2) : $@convention(thin) (@in_guaranteed Foo) -> ()
>>>>>>>>    end_borrow %2 from %0 : $*T, $T
>>>>>>>>    dealloc_stack %2 : $Foo
>>>>>>>>    ...
>>>>>>>>  }
>>>>>>>> 
>>>>>>>> **NOTE** Once `@in_guaranteed` arguments become passed as values, `store_borrow`
>>>>>>>> will no longer be necessary.
>>>>>>>> 
>>>>>>>> ## begin_borrow
>>>>>>>> 
>>>>>>>> Define a `begin_borrow` instruction as:
>>>>>>>> 
>>>>>>>>  %borrowed_x = begin_borrow %x : $T
>>>>>>>>  %borrow_x_field = struct_extract %borrowed_x : $T, #T.field
>>>>>>>>  apply %f(%borrowed_x) : $@convention(thin) (@guaranteed T) -> ()
>>>>>>>>  end_borrow %borrowed_x from %x : $T, $T
>>>>>>>> 
>>>>>>>>    =>
>>>>>>>> 
>>>>>>>>  %x_field = struct_extract %x : $T, #T.field
>>>>>>>>  apply %f(%x_field) : $@convention(thin) (@guaranteed T) -> ()
>>>>>>>> 
>>>>>>>> A `begin_borrow` instruction explicitly converts an `@owned` value to a
>>>>>>>> `@guaranteed` value. The result of the `begin_borrow` is paired with an
>>>>>>>> `end_borrow` instruction that explicitly represents the end scope of the
>>>>>>>> `begin_borrow`.
>>>>>>>> 
>>>>>>>> `begin_borrow` also allows for the explicit borrowing of an `@owned` value for
>>>>>>>> the purpose of passing the value off to an `@guaranteed` parameter.
>>>>>>>> 
>>>>>>>> *NOTE* Alternatively, we could make it so that *_extract operations started
>>>>>>>> borrow scopes, but this would make SIL less explicit from an ownership
>>>>>>>> perspective since one wouldn't be able to visually identify the first
>>>>>>>> `struct_extract` in a chain of `struct_extract`. In the case of `begin_borrow`,
>>>>>>>> there is no question and it is completely explicit.
>>>>>>> 
>>>>>>> begin_borrow SGTM. Does end_borrow need to be explicit, or could we leave it implicit and rely on dataflow diagnostics to ensure the borrowed value's lifetime is dominated by the owner's? It seems to me like, even if end_borrow is explicit, we'd want a lifetime-shortening pass to shrinkwrap end_borrows to the precise lifetime of the borrowed value's uses.
>>>>>> 
>>>>>> I definitely think it should be explicit, as Michael has it.
>>>>> 
>>>>> Would you be able to elaborate why? I suppose explicit is a more conservative starting point. It feels to me like making it explicit isn't doing much more than imposing more verification and optimization burden on us, but I'm probably missing something.
>>>> 
>>>> Well, for one, that verification burden isn't unimportant.  Under ownership, DI has to enforce things about borrowed values during the lifetime of the borrow.  I expect that to apply to values and not just variables.  Having lifetimes marked out explicitly should make that much saner.
>>>> 
>>>> It's also quite a bit easier to verify things when there's a simple nesting property, e.g.
>>>>   %1 = load_borrow %0
>>>>   %2 = struct_element borrow %1, $foo
>>>>   %3 = blah
>>>>   end_borrow %2
>>>>   end_borrow %1
>>>> as opposed to tracking that uses of %2 implicitly require both %2 and %1 to have remained borrowed.
>>>> 
>>>> For another, it's not obvious that borrowing is a trivial operation.  If borrowing can change representations, as it does in Rust and as we might have to do in Swift (for tuples at least, maybe for arrays/strings/whatever), then something needs to represent the lifetime of that representation, and creating it for an opaque T may be non-trivial.
>>>> 
>>>> And even if we don't need to generate code normally at begin_borrow / end_borrow points, I can pretty easily imagine that being interesting for extra, sanitizer-style instrumentation.
>>>> 
>>>> John.
>>> 
>>> 
>>> Yes, we also need explicit markers for code motion barriers so we don’t need to consider any “use” a potential code barrier.
>>> 
>>> However, in the most recent proposal I’ve seen, I think we plan to have this instead:
>>> 
>>> %1 = load_borrow %0 (alternatively begin_borrow)
>>> %2 = struct_extract %1, #field (implied subobject borrow)
>>> %3 = blah %2
>>> end_borrow %1
>>> 
>>> Note:
>>> - struct_extract only works on a borrowed parent object, so there’s no need for another scope.
>>> - %2 is a dependent value on %1
>>> - You can’t simultaneously shared-borrow one subobject of a value while unique-borrowing another because unique-borrowing requires an address.
>> 
>> Just to be clear, I think what Andy is talking about is whether or not we should suppress borrow sub-scopes.
>> 
>> Whether or not we suppress these subscopes, will not create that much of a difference from the verification point of view since given a borrow of a sub-object from an already borrowed object, we essentially find the load_borrow/begin_borrow, use that to find the sets of end_borrows, and then use that set of end_borrows as part of the verification of the sub-object borrow. The dataflow verifier is implemented to be agnostic to that sort of difference, so it is just a question of how you initialize the dataflow verifier.
>> 
>> This is a trade-off in between verbosity in the IR and simplicity in the verifier and I am ok with going either way if there are strong feelings in either direction.
>> 
>> Michael
> 
> I initially thought each borrowed subobject would need its own scope, but I’m not sure it’s necessary and might get out of hand with deep struct nestings.

I don't think deep struct nestings are that likely, but I agree that it's not necessary to scope a borrowed projection from a borrowed aggregate.  That only applies to *non-unique* projections, though.

John.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20161207/e0b8fe22/attachment.html>