[swift-dev] [proposal] SIL implementation of ownership and borrowing

[Andrew Trick]

I'm sending out an updated version of my notes on SIL redesign in support of reasoning about lifetimes, including ownership and borrowing. I sent a very preliminary version of these notes a year ago. Since then, a lot has changed. Work on the SIL representation has been going on "in the background" in several different areas. It's sometimes hard to understand how it all relates to each other.

-Andy


SIL implementation of ownership and borrowing
SIL representation is going through an evolution in several areas: Ownership SSA (OSSA), @guaranteed calling convention, lifetime guarantees, closure conventions, opaque values, borrowing, exclusivity, and __shared parameter modifiers. These are all loosely related, but it's important to understand how they fit together. Here are some notes that I gathered and found useful to write down. (Coroutines support is also related, but I'm avoiding that topic for now.) Disclaimer: None of this is authoritative. I hope that any misunderstandings and misstatements will be corrected by reviewers.

Borrowed (shared) Swift values
I'm not sure exactly what borrowing will look like in the language, but conceptually there are two things to support:

borrow y = x

foo(borrow x)

Both of these operations imply the absence of a copy and read-only access to an immutable value within some scope: either the borrowed variable's scope or the statement's scope. Exclusivity enforcement guarantees that no writes to the borrowed variable occur within the scope, thereby ensuring immutability without copying.

For copyable types, the implementation can always introduce a copy without changing formal program behavior. However, exclusivity still needs to be enforced to preserve the borrow's original semantics. Adding a copy would ensure local immutability, but removing exclusivity would broaden the set of legal programs--it's not a source compatible change.

Maybe the user doesn't care about formal semantics and only requested a borrow as a performance assurance. Exclusivity should still be enforced because it is the only way to reliably avoid copying and provide that assurance.

In short, borrow => exclusively-immutable and no copy.

As such, the entire borrow scope will initially need to be protected by SIL exclusivity markers: begin_access [read] / end_access:

%x_address = project_box ...
// initialize %x_address
%x_access = begin_access [read] %x_address
apply @foo(%x_access) : $(@in_guaranteed) -> ()
end_access %x_access
If the boxed variable is promoted to a SILValue, the exclusivity markers can be trivially eliminated. This is valid because promoting to a SILValue requires static proof of exclusive-immutability. All of the above instructions can be eliminated except the call itself:

apply @foo(%x) : $(@in_guaranteed) -> ()
Where %x is the value that %x_address was initialized to. The only problem is that this breaks the calling convention. The original SIL passes an address as the @in_guaranteed argument and the optimized SIL passes a value. They can't both be right. Knowing which to fix depends on the type of the borrowed variable.

The @in_guaranteed parameter convention passes the value by address, which is required for address-only types. Types that are opaque due to generic abstraction or resilience are address-only. Some move-only types are also address-only.

If the type is not address-only (neither borrowed-move-only nor opaque), then it's possible to pass the value to a function with a direct @guaranteed parameter convention:

apply @foo(%x) : $(@guaranteed AnyObject) -> ()
With a direct convention, we cannot pass a SIL address, so the original SIL would need to be written as:

%x_address = project_box ...
%x_access = begin_access [read] %x_address : $*AnyObject
%x_borrow = load_borrow %x_address : $*AnyObject
apply @foo(%x_borrow) : $(@guaranteed AnyObject) -> ()
end_borrow %x_borrow : $AnyObject
end_access %x_access
We still need to solve the problem of address-only types. A new feature called SIL opaque values does that for us. It allows address-only types to be operated on in SIL just like loadable types. The only difference is that indirect parameter conventions are required. With SIL opaque values enabled, the original code will be:

%x_address = project_box ...
%x_access = begin_access [read] %x_address : $*T
%x_borrow = load_borrow %x_address : $*T
apply @foo(%x_borrow) : $(@in_guaranteed T) -> ()
end_borrow %x_borrow : $T
end_access %x_access : $*T
And the code can now be optimized just like before:

apply @foo(%x) : $(@in_guaranteed T) -> ()
load_borrow is an OSSA feature that allows an addressable formal memory location to be viewed as an SSA value without a separate lifetime. But it has a secondary role. It also allows the compiler to view the borrowed memory address as being reserved for that borrowed value up to the end_borrow. begin_access [read] only enforces the language level guarantee the formal memory is exclusively immutable. load_borrow provides a SIL-level guarantee that physical memory remains exclusively immutable. So whilebegin_access can be eliminated once its conditions are satisfied, load_borrow must remain until address-only values are lowered to a direct representation of the ABI, otherwise known "address lowering". With a normal load, the compiler would still need to bitwise copy the value %x_borrow when passing it @in_guaranteed. Not only does that defeat a performance goal, but it is not possible for some types, such as opaque move-only types, or, hypothetically, move-only types with "mutable" properties, as required for atomics.

Ownership SSA (OSSA) form also introduces begin_borrow / end_borrow scopes for SILValues, but those are mostly unrelated to borrowing at the language level. SILValue borrowing is not necessary to represent borrowed Swift values (the load_borrow is no longer needed once the Swift value at %x_address is promoted to the SILValue %x). begin_borrow / end_borrow scopes are currently used in situations that are unrelated to Swift borrowing, as explained in below in the OSSA section.

The naming conflict between borrowed Swift values and borrowed SILValues should eventually be resolved. For example, language review may decide that "shared" is a better name than "borrowed". I use the borrow here because I don't want to create more confusion surrounding our existing (unsupported) __shared parameter modifier, which does not currently have semantics that I described above.
@guaranteed (aka +0) parameter ABI
In the previous section, we saw that a @guaranteed convention is required to implement borrowed Swift values simply because the borrowed value cannot be copied or destroyed within the borrow scope. Beyond that, the calling convention is purely an ABI feature unrelated to borrowing at the language level.

@guaranteed (+0) and @owned (+1) conventions determine where copies are needed but otherwise have no effect on variable lifetimes. In the @owned case, lifetime ends before the return, and in the @guaranteed case it ends after the return. From the point of view of both the user and the optimizer, this is semantically the same lifetime. In other words, manually inlining an unadorned pure Swift function cannot affect formal program behavior.

SILValues are currently wrapped in begin_borrow before being passed @guaranteed, but there's no reason to do that other than to avoid inserting the begin_borrow during inlining, and in fact it contradicts the purpose of begin_borrow as described in the OSSA section.
It is up to the compiler to decide which convention to use for parameters in a given position with a given type. Sometimes @owned is clearly best (initializers). Sometimes @guaranteed is clearly best (self, stdlib protocols, closures). Since those decisions are about to become ABI, they're being evaluated carefully. Regardless of the outcome, programmers need a way to override the convention with a parameter attribute or modifier.

__shared parameter modifier
The __shared parameter modifier simply forces the compiler to choose the @guaranteed (+0) convention. This is unsupported but important for evaluating alternative ABI decisions and preparing for ABI compatibility with move-only types.

In the first section, I defined a hypothetical borrow caller-side modifier. To understand the difference between a __sharedconvention and a borrowed value consider this example:

func foo<T>(_ t: __shared T, _ f: ()->()) {
  f()
  print(t)
}

func bar<T>(_ t: inout T) { ... }

func test<T>(_ t: T) {
  var t = move(t)
  foo(t) { bar(&t) }
}
This is legal code today, but t will be copied when passed to foo. This likely defies the user's expectation that they see the value printed after modification by bar.

If T is ever a move-only type, this will simply be undefined without additional exclusivity enforcement. Requiring that a variable beborrowed before being passed __shared catches that:

func test<T>(_ t: T) {
  var t = move(t)
  foo(borrow t) { bar(&t) }
}
Now this is a static compiler error.

Of course, we could introduce an implicit borrow whenever move-only types are passed __shared. But I believe that is too subtle and misleading of a rule to expose to users.

This becomes much simpler if @guaranteed is the default convention that users can override with a __consumed parameter modifier. The allowable argument and parameter pairings would be:

non-borrowed value -> __consumed parameter

borrowed value -> default parameter

copyable value -> default parameter

Ownership SSA (OSSA)
Michael Gottesman is working on extensively documenting this feature. Briefly, a SILValue is a singly defined node in an SSA graph that represents one instance of a Swift value. With OSSA, each SILValue now has an independent lifetime--it has "ownership" of its lifetime. The SILValue's lifetime must be ended by destroying the value (e.g. decrementing the refcount), or moving the value into another SILValue (e.g. passing an @owned argument).

A SILValue can be "borrowed" across some program scope via begin/end_borrow. The borrowed value can then be "projected" out into subobjects or cast to another type. The original value cannot be destroyed within the borrow scope. This representation allows trivial lifetime analysis. There's no need to reason about projections, casts and the like. That's all hidden by the borrow scope.

So, SILValue borrowing isn't required for modeling language level semantics. Instead, it's a convenient way to verify that SIL transformations obey the rules of OSSA. In fact, these instructions are trivially removed as soon as the compiler no longer needs to verify OSSA.

What do we mean by OSSA rules? Here's a quick summary.

The users of SILValues can be divided into these groups.

Uses independent of ownership:

U1. Use the value instantaneously (copy_value, @guaranteed argument)

U2. Escape the nontrivial contents of the value (ref_to_unowned, ref_to_rawpointer, unchecked_trivial_bitcast)

Uses that require an owned value:

O3. Propagate the value without consuming it (mark_dependence, begin_borrow)

O4. Consume the value immediately (store, destroy, @owned argument)

O5. Consume the value indirectly via a move (tuple, struct)

Uses that require a borrowed value:

B6. Project the borrowed value (struct_extract, tuple_extract, ref_element_addr, open_existential_value)

begin_borrow is only needed to handle uses in (B6). Support for struct_extract and tuple_extract was the most compelling need for begin_borrow. It maybe be best though to eliminate those instructions instead using a more OSSA-friendly destructure. Doing this would enable normal optimization of tuples and struct copies.

begin_borrow may still remain useful to make it easier to handle the other uses that fall into (B6). For example, rather than analyzing all uses of ref_element_addr, the compiler can treat the entire scope like a single use at end_borrow.

  %borrow = begin_borrow %0 : $Class
  %addr = ref_element_addr %borrow : $Class, #Class.property
  %value = load %addr
  // Inner Instructions
  end_borrow %borrow : $Class
  // Outer Instructions
  destroy_value %obj
Here, the value of %addr depends on lifetime of %borrow. The compiler can choose to ignore that dependent lifetime and consider the end_borrow a normal use. Even this simplified view of lifetime allows hoisting destroy_value %obj above "Outer Instructions". Alternatively, the compiler can analyze the uses of the dependent value (%addr) and see that it's safe to hoist both the begin_borrow and destroy_value above "Inner Instructions".

So, uses in (O3 - propagate) can be either analyzed transitively or skipped to the end of their scope.

Uses in (U2 - escape) cannot be safely analyzed transitively, requiring some additional mechanism to provide safety, as described in the section "Dependent Lifetime".

Dependent Lifetime
A value's lifetime cannot be verified if a use has escaped the contents that value into a trivial type (U2). In those cases, it is the user's responsibility to designate the value's lifetime. API's like withExtendedLifetime do this by emitting a fix_lifetime instruction. Without fix_lifetime, the compiler would be able to hoist either a destroy or an end_borrow above any uses of the escaped nontrivial value.

fix_lifetime is too conservative for performance critical code. It prevents surrounding code motion and effectively disables dead code elimination. mark_dependence is a more precise instruction that ties an "owner" value lifetime to an otherwise unrelated (likely trivial) "dependent" value. If the compiler is able to analyze the uses of the trivial value, then it can more aggressively optimize the owner's lifetime.

I'll send a separate detailed proposal for a adding an withDependentLifetime API and end_dependence instruction.
Here is some SIL code with an explicitly dependent lifetime:

bb0(%0 : @owned $Class)
  %unowned = ref_to_unowned %obj : $Class to $@sil_unowned Class
  %dependent = mark_dependence %unowned on %obj
  store %dependent to ...
  // Inner Instructions
  end_dependence %dependent
  // Outer Instructions
  destroy_value %obj
In this example, the %dependent value itself escapes, so the compiler knows nothing of its lifetime. However, it can still hoistdestroy_value above "Outer Instructions" because the end_dependence

In the next example, the compiler can determine that the dependent value does not escape:

bb0(%0 : @owned $Class)
  %unowned = ref_to_unowned %obj : $Class to $@sil_unowned Class
  %dependent = mark_dependence %unowned on %obj
  load_unowned %dependent
  // Inner Instructions
  end_dependence %dependent
  // Outer Instructions
  destroy_value %obj
In that case both destroy and end_dependence can be hoisted above "Inner Instructions".

Furthermore, if the %dependent value becomes dead, then the entire mark_dependence scope can be eliminated.

Note that mark dependence does not require the compiler to discover any relationship between the owner and its dependent value. The instruction makes that relationship explicit (in the example below %trivial depends on %copy). This is an important difference between the lifetime propagation of begin_borrow and mark_dependence.

bb0(%0 : @owned $Class)
  %objptr = ref_to_raw_pointer %obj : $Class to $Builtin.RawPointer
  store %objptr to %temp : $*Builtin.RawPointer
  %copy = copy_value %obj
  %trivial = load %temp : $*Builtin.RawPointer
  %dependent = mark_dependence %trivial on %copy
  load_unowned %dependent  
  // Inner Instructions
  end_dependence %dependent
  // Outer Instructions
  destroy_value %obj
Both begin_borrow and mark_dependence instructions open a scope for dependent lifetimes. In both cases, the only dependent values that affect the owner's lifetime are values that directly derive from the begin_borrow or mark_dependence SSA value. The differences are:

The begin_borrow value is simply a borrowed instance of the owner.

The mark_dependence value is any arbitrary trivial or non-trivial value.

Only non-trivial values derived from begin_borrow are considered relevant. Casting the borrowed value to a trivial value will require a separate mark_dependence.

All values derived from mark_dependence are considered, whether trivial or non-trivial.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20171219/f51f9fc4/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: borrow-notes-v2.md
Type: text/markdown
Size: 16265 bytes
Desc: not available
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20171219/f51f9fc4/attachment.bin>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20171219/f51f9fc4/attachment-0001.html>