Move Only Values

This document contains a proposal to add a new @_moveOnly attribute to Swift. This will be allowed upon lets, vars, arguments, results, computed properties, and fields of class types. This will allow for System programmers to have more exact control of the performance of their programs. The general outline of our discussion will be:

First we introduce the Swift level syntax for the @_moveOnly attributes and its implications on the Swift level.
We then discuss how when SIL is OSSA form, move only values are naturally represented as values that due to their type are unable to be passed to copy instructions. We will show how we can use the SIL level type system to maintain this property by using the type system. We will also show how we can handle trivial and address only types with this scheme.
Then we will talk about how this goal of representing move only values as uncopyable values conflicts with the current SILGen implementation since it often times is forced to emit copies. We will introduce a strategy for working around this problem using a new diagnostic pass called Diagnostic Copy Propagation that lets us emit copies of move only values in SILGen and then remove those copies as a SIL pass (and emit an error for any that can not be removed).
Then we will introduce the move operator that we will use to end lifetimes of objects at the Swift level. This will require a different diagnostic pass than Diagnostic Copy Propagation.
Finally, we will conclude by proposing a bring up strategy for this feature.

The `@_moveOnly` attribute

In order to represent the @_moveOnly concept at the Swift level, we use the @_moveOnly attribute and allow for it to be placed on let, var bindings, function arguments, return values, as well as class fields. Example:

@_moveOnly let global: Int = ...
@_moveOnly var global2: Klass = ...

class X {
  @_moveOnly let x: Int = ...
}

func foo(@_moveOnly _ x: Klass) -> @_moveOnly Klass {
  // This is going to be a copy since y isn't marked @_moveOnly.
  let y = x
  // This is a move of x into z and x can no longer be used afterwards.
  @_moveOnly let z = x
  ...
}

NOTE: We do not allow for struct fields to be marked @_moveOnly since that would necessarily imply that the struct itself is a move only type (which we do not support yet).

Importantly, we do not actually represent @_moveOnly in the type system at the Swift level. This ensures that the type checker does not need to know about @_moveOnly and avoids the many implementation issues around the type checker that we discovered with inout types. Instead we:

Put a bit in TypeBase that signifies that a type is moveOnly. We do not allow for this bit to be set by the type checker and one can not create such a type at the AST level.
Rely on SILGen and TypeLowering to as appropriate produce values with the moveOnly type so we can enforce no-copying at the SIL level.

Now that we understand how we will represent move only values at the Swift level, lets consider the design space below at the SIL level.

Representing Move Only Values in SIL

NOTE: In the following I am assuming that one has read the Ownership SSA documentation in SIL.rst.

In the following, I first discuss the natural form for representing move only values in SIL. Then I talk about how we extend this model from non-trivial loadable values to trivial loadable values and address only types.

NOTE: In the following section, I am going to use a straw man type attribute (@_moveOnly) to signal that a value (even if normally not move only) is move only. This will just act as a bit on a type at the SIL level.

Move Only Values in OSSA

In order for us to represent move only values, we need to first consider what their form looks like in SIL. Put simply copies in SIL are represented via special instructions (e.x.: copy_value) and a move only value in SIL is a SSA value that is never passed to such an instruction. Instead, we manipulate the value by using forwarding instructions, consuming parameters, and consuming results. Example:

sil @_moveOnly_only_value_example : $@convention(thin) (@owned @_moveOnly Optional<Klass>) -> () {
bb0(%0 : @owned $@_moveOnly Optional<Klass>):
  // Inserting a copy_value of %0 will cause the IR verifier to assert!
  switch_enum %0 : $@_moveOnly Optional<Klass>, case #Optional.some: bb1, case #Optional.none: bb2

bb1(%1 : @owned $@_moveOnly Klass):
  %f = function_ref @myFoo2 : $@convention(thin) (@owned @_moveOnly SubKlass) -> ()
  %2 = unchecked_ref_cast %1 : $@_moveOnly Klass to $@_moveOnly SubKlass
  apply %f(%2) : $@convention(thin) (@owned @_moveOnly SubKlass) -> ()
  br bb3

bb2:
  br bb3

bb3:
  %9999 = tuple()
  return %9999 : $()
}

Naturally, one would in Ownership SSA form ban any value of such a type being an operand to any copy instruction, guaranteeing the property that we wish to preserve.

For memory, we can use a similar methodology, banning instructions like copy_addr from copying a “move only value”. Example:

sil @_moveOnly_only_value_memory_example : $@convention(thin) (@owned @_moveOnly Optional<Klass>) -> () {
bb0(%0 : @owned $@_moveOnly Optional<Klass>):
  %1 = alloc_stack $@_moveOnly Optional<Klass>

  // Store using a move...
  store %0 to [init] %1 : $*@_moveOnly Optional<Klass>

  // load [take] is legal here. A load [copy] would be illegal and would cause the IR
  // verifier to assert.
  %3 = load [take] %1 : $*@_moveOnly Optional<Klass>
  store %3 to [init] %1 : $*@_moveOnly Optional<Klass>

  %2 = alloc_stack $@_moveOnly Optional<Klass>
  // IR verifier would assert if this did not have a [take].
  copy_addr [take] %1 to [initialization] %2 : $*@_moveOnly Optional<Klass>
  ...
}

Modeling Address Only and Trivial Move Only Values

The model above naturally flows from how non-trivial loadable values are represented in OSSA. That being said, we must consider two other types of values that do not fit into that bucket today but that we must support: address only values and trivial loadable values.

Address Only Move Only Values. Since we want to fully take advantage of Ownership SSA and its invariants, we naturally will rely upon opaque values to ensure that beyond temporaries generated by SILGen, move only values will be passed around as loadable values:

sil [ossa] @opaque_value_move_only : $@convention(thin) <T> (@in @_moveOnly T) -> @out @_moveOnly T {
bb0(%0 : @owned $@_moveOnly T):
  %3 = function_ref @opaque_copy : $@convention(thin) <T> (@in_guaranteed @_moveOnly T) -> @out @_moveOnly T
  %4 = apply %3<T>(%2) : $@convention(thin) <T> (@in_guaranteed @_moveOnly T) -> @out @_moveOnly T
  destroy_value %0 : $T
  return %4 : $T
}

Trivial Move Only Values: In order for us to represent trivial move only values in SIL, we must work around the invariant in SIL that only non-trivial values can be copied. In order to prevent breaking these invariants, we will introduce a new SIL instruction that can be used to convert a trivial value into a non-trivial value by adding the @_moveOnly attribute to the type. As a straw man (since we have not talked about unique yet), we will call the instruction make_move_only in the following example. In order to ensure that we do not hurt performance, we will lower away the make_move_only instruction when we lower Ownership SSA allowing for normal optimization of trivial values to occur. Example:

sil [ossa] @trivial_value_move_only : $@convention(thin) (Int) -> () {
bb0(%0 : $Int):
  // %1 is a non-trivial value of type $@_moveOnly Int
  %1 = make_moveOnly %0 : $Int

  %f = function_ref @trivial_use : $@convention(thin) (Int) -> ()
  // We can only pass %0 (not %1) to %f since %f expects an Int, not an @_moveOnly Int.
  apply %f(%0) : $@convention(thin) (Int) -> ()

  %f2 = function_ref @trivial_move_only_use : $@convention(thin) (@owned @_moveOnly Int) -> ()
  // We can pass both %0 and %1 to %f2 since we allow for $Int to be passed as an @owned @_moveOnly Int value.
  apply %f2(%0) : $@convention(thin) (@owned @_moveOnly Int) -> ()
  apply %f2(%1) : $@convention(thin) (@owned @_moveOnly Int) -> ()
  ...
}

By using opaque values and the make_moveOnly instruction, we are able to recast introducing move only values for these two sorts of values in terms of non-trivial loadable values simplifying the implementation.

SILGen, the “Ensure Plus One Problem”, and Copying Move Only Values

Problem: SILGen assumes all values are copyable

A characteristic of SILGen today is that parts of SILGen have been written to assume +0 and others +1 values causing SILGen to have to transition in between such contexts. The natural way to do so is to introduce additional copies into the IR using APIs such as ManagedValue::ensurePlusOne() or creating new ManagedValues without cleanups. This creates a significant problem for bringing up move only types since without significant engineering work, we /cannot/ guarantee that SILGen will not insert copies on a move only value, directly conflicting with the design of move only types at the SIL level that we want to achieve as described above. Instead, we must be creative and come up with a different approach to solve our problem that /works around/ SILGen’s current behavior. Luckily for us a recent technical advance in OSSA SIL can help us to escape from our predicament: Copy Propagation.

Solution: Use Copy Propagation!

As a result of implementing Ownership SSA (OSSA) in SIL, the Swift compiler can now infer correct lifetimes at compile time of loadable typed values based off of the SSA uses of that value. The inferred lifetimes are able to be statically verified by the compiler as being OSSA correct (1) and allows the compiler to guarantee that a programs ARC traffic will be the local minimal set of operations needed to express the programs semantics. This is done by finding all of the places where the value has lifetime ending uses (consuming uses) and then determining the appropriate places where a copy would be needed if a lifetime ending use is reachable from another lifetime ending use. These are exactly the places where a programmer would need to manually insert an explicit copy when using a move only type! This transformation is called Copy Propagation and is currently implemented just for optimization purposes in a SILOptimizer pass called Performance Copy Propagation. To get a visual sense of how this pass works in action, see the section below called Performance Copy Propagation in Action. The authors have refactored the underlying implementation into a prototype diagnostic pass called Diagnostic Copy Propagation that we can use to implement support for move only values in Swift!

To do so, we allow for values with the “moveOnly” bit set to be copied when we are in Raw SIL. We run Diagnostic Copy Propagation on move only arguments, apply results, and the result of all make_moveOnly instructions. The pass will eliminate any of the extra copies that SILGen inserts and will emit errors in any situation where semantically a copy is required to make the IR correct. Example:

sil [ossa] @flag_double_consume_of_move_value : $@convention(thin) (@owned Klass) -> () {
bb0(%0 : @owned $Klass):
  %1 = make_moveOnly %0 : $Klass // expected-error \{\{'x' consumed more than once}}
  debug_value %1 : $@_moveOnly Klass, let, name "x"
  %2 = copy_value %1 : $@_moveOnly Klass
  %f = function_ref @consume_move_only_value : $@convention(thin) (@owned @_moveOnly Klass) -> ()
  // expected-note @-1 \{\{consuming use}}
  apply %f(%2) : $@convention(thin) (@owned @_moveOnly Klass) -> ()
  // expected-note @-1 \{\{consuming use}}
  apply %f(%1) : $@convention(thin) (@owned @_moveOnly Klass) -> ()
  %9999 = tuple()
  return %9999 : $()
}

The move operator

One thing that we wish to get out of this work is the creation of a move operator. For moveOnly values, this is equivalent to ending the lifetime of the value, e.x.:

@_moveOnly let x = ...
let _ = move(x) // Ends the lifetime of x

Additionally, we want to be able to have something similar for copyable values. This will necessarily imply a different analysis since we want to ensure that when we move a copyable value, there aren’t any further copyable values. This ensures that we can move a copyable value into a move only value and not have to worry about the copyable value having further uses later in the code. Example:

let x = Klass()
@_moveOnly let y = move(x)
// Illegal to use x after this point.

Bring up

I outline the bringup strategy below:

Introduce the moveOnly attributes for let, var, params. Done.
Introduce a Builtin that can be used to emit make_moveOnly. Done.
Use make_moveOnly builtin to bringup the move only value checker. Done.
Implement function return attributes and use that to define @_moveOnly there. In progress.
Implement Type System support for SIL level types that can be marked as moveOnly. Done.
Implement SILGen/TypeLowering support for loading moveOnly values and converting the type as appropriate. Not Done.
Implement the move operator and the copyable analysis.
Prepare a toolchain to give to stakeholders to try out the moveOnly attributes and get feedback. Not done.

Reference: Performance Copy Propagation

As a result of implementing Ownership SSA (OSSA) in SIL, the Swift compiler can now infer the lifetimes at compile time of loadable typed values based off of the SSA uses of that value. The inferred lifetimes are able to be statically verified by the compiler as being OSSA correct (1) and allows the compiler to guarantee theoretically minimal ARC traffic. This is done by finding all of the places where the value has lifetime ending uses (consuming uses) and then determining the appropriate places where a copy would be needed if a lifetime ending use is reachable from another lifetime ending use. These are exactly the places where a programmer would need to manually insert an explicit copy when using a move only type! Today we use this technique in an optimization pass called Performance Copy Propagation that given a value, ignores all current local copies, computes/inserts the minimal set of actual copies needed and deletes all of the old local copies. Lets take a look at some SIL examples to see how PCP works. Consider the following SIL:

class Klass {}

sil [ossa] @myFunc : $@convention(thin) (@guaranteed Klass) -> () {
bb0(%0 : @guaranteed $Optional<Klass>):
  %1 = copy_value %0 : $Optional<Klass>
  switch_enum %1 : $Optional<Klass>, case #Optional.some: bb1, case #Optional.none: bb2 (A)

bb1(%2 : @owned $Klass):
  %f = function_ref @myFoo2 : $@convention(thin) (@guaranteed SubKlass) -> ()
  %3 = unchecked_ref_cast %2 : $Klass to $SubKlass                                      (B)
  apply %f(%3) : $@convention(thin) (@guaranteed SubKlass) -> ()
  destroy_value %3 : $Klass                                                             (C)
  br bb3

bb2:
  br bb3

bb3:
  %9999 = tuple()
  return %9999 : $()
}

PCP as it runs visits the transitive def-use graph rooted at %0 looking through uses that forward ownership from their operands to results ((A), (B)). It sees that the only true consuming use of %0 is actually the destroy_value (C) and additionally that all of the forwarding uses are able to take a guaranteed value meaning no copies are needed. It then converts the SIL to use guaranteed values and eliminates all of the old copies, yielding the following SIL:

sil [ossa] @myFunc : $@convention(thin) (@guaranteed Klass) -> () {
bb0(%0 : @guaranteed $Optional<Klass>):
  switch_enum %0 : $Optional<Klass>, case #Optional.some: bb1, case #Optional.none: bb2 (A)

bb1(%1 : @guaranteed $Klass):
  %f = function_ref @myFoo2 : $@convention(thin) (@guaranteed SubKlass) -> ()
  %2 = unchecked_ref_cast %1 : $Klass to $SubKlass                                      (B)
  apply %f(%2) : $@convention(thin) (@guaranteed SubKlass) -> ()
  br bb3

bb2:
  br bb3

bb3:
  %9999 = tuple()
  return %9999 : $()
}

Lets now consider a case where we actually need a copy due to a consuming use:

sil [ossa] @myFunc : $@convention(thin) (@guaranteed Klass) -> () {
bb0(%0 : @guaranteed $Optional<Klass>):
  %1 = copy_value %0 : $Optional<Klass>
  switch_enum %1 : $Optional<Klass>, case #Optional.some: bb1, case #Optional.none: bb2 (A)

bb1(%2 : @owned $Klass):
  %f = function_ref @myFoo2 : $@convention(thin) (@owned SubKlass) -> ()
  %3 = unchecked_ref_cast %2 : $Klass to $SubKlass                                      (B)
  apply %f(%3) : $@convention(thin) (@owned SubKlass) -> ()                             (C)
  br bb3

bb2:
  br bb3

bb3:
  %9999 = tuple()
  return %9999 : $()
}

In this case, PCP will again ignore the copy_value in %1 and will compute directly from the uses that a copy is needed at (C). But it will see that it is only needed in bb1, not along bb2. So it will insert a copy_value at (C) and then eliminate the copy_value, yielding the following SIL:

sil [ossa] @myFunc : $@convention(thin) (@guaranteed Klass) -> () {
bb0(%0 : @guaranteed $Optional<Klass>):
  switch_enum %1 : $Optional<Klass>, case #Optional.some: bb1, case #Optional.none: bb2 (A)

bb1(%2 : @guaranteed $Klass):
  %f = function_ref @myFoo2 : $@convention(thin) (@owned SubKlass) -> ()
  %3 = unchecked_ref_cast %2 : $Klass to $SubKlass                                      (B)
  %4 = copy_value %3 : $SubKlass
  apply %f(%4) : $@convention(thin) (@owned SubKlass) -> ()                             (C)
  br bb3

bb2:
  br bb3

bb3:
  %9999 = tuple()
  return %9999 : $()
}

As a final case, lets consider a situation where we need multiple copies:

sil [ossa] @myFunc : $@convention(thin) (@guaranteed Klass) -> () {
bb0(%0 : @guaranteed $Optional<Klass>):
  %1 = copy_value %0 : $Optional<Klass>
  switch_enum %1 : $Optional<Klass>, case #Optional.some: bb1, case #Optional.none: bb2 (A)

bb1(%2 : @owned $Klass):
  %f = function_ref @myFoo2 : $@convention(thin) (@owned SubKlass) -> ()
  %3 = unchecked_ref_cast %2 : $Klass to $SubKlass                                      (B)
  apply %f(%3) : $@convention(thin) (@owned SubKlass) -> ()                             (C)
  br bb3

bb2:
  br bb3

bb3:
  %9999 = tuple()
  return %9999 : $()
}

One part of the discussion below is the proposal to take advantage of this to create a new diagnostic pass based off of the same infrastructure as “performance copy propagation” (PCP), but instead of inserting copies, emits a diagnostic that tells the user about why the copy was needed and as a fixit, where the copy needs to be inserted. This would then make it very easy for the programmer to insert an explicit copy if needed and go on with their day. This theoretical pass I am going to refer to as “Diagnostic Copy Propagation” (DCP).

(1) Ownership SSA correct means that the loadable value is guaranteed to never be consumed twice, leaked, and all uses of the value are within the OSSA lifetime.

The @_moveOnly attribute