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 while
`begin_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 `__shared` convention
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 be
`borrowed` 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 hoist
`destroy_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.
SIL implementation of ownership and borrowingSIL 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 valuesI'm not sure exactly what borrowing will look like in the language, but conceptually there are two things to support:
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 In short, As such, the entire borrow scope will initially need to be protected by SIL exclusivity markers: 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: Where The 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: With a direct convention, we cannot pass a SIL address, so the original SIL would need to be written as: 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: And the code can now be optimized just like before:
Ownership SSA (OSSA) form also introduces
@guaranteed (aka +0) parameter ABIIn the previous section, we saw that a
It is up to the compiler to decide which convention to use for parameters in a given position with a given type. Sometimes __shared parameter modifierThe In the first section, I defined a hypothetical This is legal code today, but If Now this is a static compiler error. Of course, we could introduce an implicit borrow whenever move-only types are passed This becomes much simpler if
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 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 ( U2. Escape the nontrivial contents of the value ( Uses that require an owned value: O3. Propagate the value without consuming it ( O4. Consume the value immediately ( O5. Consume the value indirectly via a move ( Uses that require a borrowed value: B6. Project the borrowed value (
Here, the value of 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 LifetimeA 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
Here is some SIL code with an explicitly dependent lifetime: In this example, the In the next example, the compiler can determine that the dependent value does not escape: In that case both Furthermore, if the 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 Both
|
_______________________________________________ swift-dev mailing list swift-dev@swift.org https://lists.swift.org/mailman/listinfo/swift-dev
