Proposal: SILValue SSA Instructions

Michael_Gottesman · 2016-12-06T00:24:46.000Z

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

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.

----

Joe_Groff · 2016-12-06T18:17:47.000Z

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.

-Joe

···

On Dec 5, 2016, at 4:24 PM, Michael Gottesman via swift-dev <swift-dev@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

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.

John_McCall · 2016-12-06T19:29:50.000Z

I definitely think it should be explicit, as Michael has it.

Michael, does store_borrow go away if/when we eliminate the need for different code patterns for direct vs. indirect arguments?

John.

···

On Dec 6, 2016, at 10:17 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

On Dec 5, 2016, at 4:24 PM, Michael Gottesman via swift-dev <swift-dev@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

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.

Joe_Groff · 2016-12-06T19:35:35.000Z

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.

-Joe

···

On Dec 6, 2016, at 11:29 AM, John McCall <rjmccall@apple.com> wrote:

On Dec 6, 2016, at 10:17 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

On Dec 5, 2016, at 4:24 PM, Michael Gottesman via swift-dev <swift-dev@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

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.

Michael_Gottesman · 2016-12-06T20:32:13.000Z

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

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.

Michael, does store_borrow go away if/when we eliminate the need for different code patterns for direct vs. indirect arguments?

Yes.

···

On Dec 6, 2016, at 11:29 AM, John McCall <rjmccall@apple.com> wrote:

On Dec 6, 2016, at 10:17 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

On Dec 5, 2016, at 4:24 PM, Michael Gottesman via swift-dev <swift-dev@swift.org> wrote:

John.

John_McCall · 2016-12-06T22:23:47.000Z

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.

···

On Dec 6, 2016, at 11:35 AM, Joe Groff <jgroff@apple.com> wrote:

On Dec 6, 2016, at 11:29 AM, John McCall <rjmccall@apple.com <mailto:rjmccall@apple.com>> wrote:

On Dec 6, 2016, at 10:17 AM, Joe Groff via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Dec 5, 2016, at 4:24 PM, Michael Gottesman via swift-dev <swift-dev@swift.org <mailto:swift-dev@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

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.

Andrew_Trick · 2016-12-07T22:52:55.000Z

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.

Andy

···

On Dec 6, 2016, at 2:23 PM, John McCall via swift-dev <swift-dev@swift.org> wrote:

On Dec 6, 2016, at 11:35 AM, Joe Groff <jgroff@apple.com <mailto:jgroff@apple.com>> wrote:

On Dec 6, 2016, at 11:29 AM, John McCall <rjmccall@apple.com <mailto:rjmccall@apple.com>> wrote:

On Dec 6, 2016, at 10:17 AM, Joe Groff via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Dec 5, 2016, at 4:24 PM, Michael Gottesman via swift-dev <swift-dev@swift.org <mailto:swift-dev@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

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.

Michael_Gottesman · 2016-12-10T00:17:10.000Z

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@apple.com> wrote:

On Dec 6, 2016, at 11:35 AM, Joe Groff <jgroff@apple.com <mailto:jgroff@apple.com>> wrote:

On Dec 6, 2016, at 11:29 AM, John McCall <rjmccall@apple.com <mailto:rjmccall@apple.com>> wrote:

On Dec 6, 2016, at 10:17 AM, Joe Groff via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Dec 5, 2016, at 4:24 PM, Michael Gottesman via swift-dev <swift-dev@swift.org <mailto:swift-dev@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

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.

Michael_Gottesman · 2016-12-07T23:16:01.000Z

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

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

···

On Dec 7, 2016, at 2:52 PM, Andrew Trick via swift-dev <swift-dev@swift.org> wrote:

On Dec 6, 2016, at 2:23 PM, John McCall via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Dec 6, 2016, at 11:35 AM, Joe Groff <jgroff@apple.com <mailto:jgroff@apple.com>> wrote:

On Dec 6, 2016, at 11:29 AM, John McCall <rjmccall@apple.com <mailto:rjmccall@apple.com>> wrote:

On Dec 6, 2016, at 10:17 AM, Joe Groff via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Dec 5, 2016, at 4:24 PM, Michael Gottesman via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

Andy
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Joe_Groff · 2016-12-10T00:17:58.000Z

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

No, I agree with John's points. Your design sounds good.

-Joe

···

On Dec 9, 2016, at 4:17 PM, Michael Gottesman <mgottesman@apple.com> wrote:

Michael

On Dec 6, 2016, at 2:23 PM, John McCall <rjmccall@apple.com> wrote:

On Dec 6, 2016, at 11:35 AM, Joe Groff <jgroff@apple.com> wrote:

On Dec 6, 2016, at 11:29 AM, John McCall <rjmccall@apple.com> wrote:

On Dec 6, 2016, at 10:17 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

On Dec 5, 2016, at 4:24 PM, Michael Gottesman via swift-dev <swift-dev@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

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.

Andrew_Trick · 2016-12-07T23:20:55.000Z

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.
-Andy

···

On Dec 7, 2016, at 3:16 PM, Michael Gottesman <mgottesman@apple.com> wrote:

On Dec 7, 2016, at 2:52 PM, Andrew Trick via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Dec 6, 2016, at 2:23 PM, John McCall via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Dec 6, 2016, at 11:35 AM, Joe Groff <jgroff@apple.com <mailto:jgroff@apple.com>> wrote:

On Dec 6, 2016, at 11:29 AM, John McCall <rjmccall@apple.com <mailto:rjmccall@apple.com>> wrote:

On Dec 6, 2016, at 10:17 AM, Joe Groff via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Dec 5, 2016, at 4:24 PM, Michael Gottesman via swift-dev <swift-dev@swift.org <mailto:swift-dev@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

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

Michael_Gottesman · 2016-12-10T00:22:34.000Z

Thanks!

Michael

···

On Dec 9, 2016, at 4:17 PM, Joe Groff <jgroff@apple.com> wrote:

On Dec 9, 2016, at 4:17 PM, Michael Gottesman <mgottesman@apple.com> wrote:

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

No, I agree with John's points. Your design sounds good.

-Joe

Michael

On Dec 6, 2016, at 2:23 PM, John McCall <rjmccall@apple.com> wrote:

On Dec 6, 2016, at 11:35 AM, Joe Groff <jgroff@apple.com> wrote:

On Dec 6, 2016, at 11:29 AM, John McCall <rjmccall@apple.com> wrote:

On Dec 6, 2016, at 10:17 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

On Dec 5, 2016, at 4:24 PM, Michael Gottesman via swift-dev <swift-dev@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

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.

John_McCall · 2016-12-08T00:44:36.000Z

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.

···

On Dec 7, 2016, at 3:20 PM, Andrew Trick <atrick@apple.com> wrote:

On Dec 7, 2016, at 3:16 PM, Michael Gottesman <mgottesman@apple.com <mailto:mgottesman@apple.com>> wrote:

On Dec 7, 2016, at 2:52 PM, Andrew Trick via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Dec 6, 2016, at 2:23 PM, John McCall via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Dec 6, 2016, at 11:35 AM, Joe Groff <jgroff@apple.com <mailto:jgroff@apple.com>> wrote:

On Dec 6, 2016, at 11:29 AM, John McCall <rjmccall@apple.com <mailto:rjmccall@apple.com>> wrote:

On Dec 6, 2016, at 10:17 AM, Joe Groff via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Dec 5, 2016, at 4:24 PM, Michael Gottesman via swift-dev <swift-dev@swift.org <mailto:swift-dev@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

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.