[swift-dev] Proposal: SILValue SSA Instructions

[Michael Gottesman]

Are there any more concerns here? The thread has seemed to die down and I would like to begin upstreaming this code if possible.

Michael

> On Dec 6, 2016, at 2:23 PM, John McCall <rjmccall at apple.com> 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.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20161209/4a9fd7b7/attachment.html>