With incomplete lifetimes, a value may have an "incomplete lifetime"--it
may not be destroyed on paths into dead-end regions. When a value lacks
a destroy on a path into a dead-end region, it is effectively destroyed
at its availability boundary (e.g. an `unreachable` instruction).
Indeed, lifetime completion amounts to making such implicit destroys
explicit (with correct nesting).
`SemanticARCOpts`' `performGuaranteedCopyValueOptimization` attempts to
eliminate a `copy_value` of a guaranteed value. To do so, it computes
the live range (`OwnershipLiveRange`) of the copy_value. Among other
things, it checks that all destroys of the copy_value are within the
scope of all guaranteed bases of the copied value. If any destroys are
_not_ within any of those scopes, the copy cannot be eliminated (because
the copy would have been originally live beyond the range which it would
be live in after copy elimination).
A value with an incomplete lifetime is implicitly destroyed at its
availability boundary. So those implicit destroys along the
availability boundary must _also_ be within the scopes of those
guaranteed bases.
Previously, implicit destroys along availability boundaries were not
considered. This resulted in invalid shortening of lifetimes--before
the transformation a value would be unconsumed up to its availability
boundary; after the transformation it would be consumed somewhere before
that. For example:
```
sil [ossa] @f : $@convention(thin) (@owned Outer) -> () {
entry(%o : $*Outer):
%o_borrow = begin_borrow %o : $Outer
%i = struct_extract %o_borrow : $Outer, #Outer.inner
%i_copy = copy_value %i : $Inner
end_borrow %o_borrow : $Outer
destroy_value %o : $Outer
apply @g(%i_copy) : $@convention(thin) (@guaranteed Inner) -> ()
unreachable // %i_copy implicitly destroyed
}
```
Here, `%i_copy` is implicitly destroyed at `unreachable` but `%i` is
consumed at the scope end of `%o_borrow`. That means that an attempt to
RAUW `%i_copy` with `%i` would be invalid because uses of `%i_copy` may
be outside the live range of `%i`.
(Note that this happens not to occur in the above example because
there's a bailout in the case that there are no destroys, but perturbing
the example to include a cond_br on one branch of which the value is
destroyed results in the miscompile described above.)
Here, this is fixed by adding the instructions on the availability
boundary at which the value is implicitly destroyed to the live range.
Do this by adding the instructions on the availability boundary of each
def from which the live range is generated to the live range.
One wrinkle is that the OwnershipLiveRange utility is used in one place
by a utility when SIL is in an invalid state (phi uses have been
replaced with undef so values leaks on those paths). Account for this
by manually fixing up the liveness instance passed to the lifetime
completion utility.
rdar://157291161
Instead of tracking Operands, track UsePoints, i.e.
`Either<Operand, SILInstruction>`s. For now, all use points wil remain
operands. This change is necessary to allow tracking terminators in
dead-end region as implicit uses.
This API computes the re-borrow flags for guaranteed phis based on the presence of forwarding instructions in the incoming values.
This is not correct in all cases, because optimizations can optimize away forwarding instructions.
Fixes a verifier crash: rdar://139280579
Although I don't plan to bring over new assertions wholesale
into the current qualification branch, it's entirely possible
that various minor changes in main will use the new assertions;
having this basic support in the release branch will simplify that.
(This is why I'm adding the includes as a separate pass from
rewriting the individual assertions)
Compute, update and handle borrowed-from instruction in various utilities and passes.
Also, used borrowed-from to simplify `gatherBorrowIntroducers` and `gatherEnclosingValues`.
Replace those utilities by `Value.getBorrowIntroducers` and `Value.getEnclosingValues`, which return a lazily computed Sequence of borrowed/enclosing values.
This is phase-1 of switching from llvm::Optional to std::optional in the
next rebranch. llvm::Optional was removed from upstream LLVM, so we need
to migrate off rather soon. On Darwin, std::optional, and llvm::Optional
have the same layout, so we don't need to be as concerned about ABI
beyond the name mangling. `llvm::Optional` is only returned from one
function in
```
getStandardTypeSubst(StringRef TypeName,
bool allowConcurrencyManglings);
```
It's the return value, so it should not impact the mangling of the
function, and the layout is the same as `std::optional`, so it should be
mostly okay. This function doesn't appear to have users, and the ABI was
already broken 2 years ago for concurrency and no one seemed to notice
so this should be "okay".
I'm doing the migration incrementally so that folks working on main can
cherry-pick back to the release/5.9 branch. Once 5.9 is done and locked
away, then we can go through and finish the replacement. Since `None`
and `Optional` show up in contexts where they are not `llvm::None` and
`llvm::Optional`, I'm preparing the work now by going through and
removing the namespace unwrapping and making the `llvm` namespace
explicit. This should make it fairly mechanical to go through and
replace llvm::Optional with std::optional, and llvm::None with
std::nullopt. It's also a change that can be brought onto the
release/5.9 with minimal impact. This should be an NFC change.
"reborrow" flag on the SILArgument avoids transitive walk over the phi operandsi
to determine if it is a reborrow in multiple utilities.
SIL transforms must keep the flag up-to-date by calling SILArgument::setReborrow.
SILVerifier checks to ensure the flag is not invalidated.
Currently "escaping" is not used anywhere.
Add TermInst::forwardedOperand.
Add SILArgument::forwardedTerminatorResultOperand. This API will be
moved into a proper TerminatorResult abstraction.
Remove getSingleTerminatorOperand, which could be misused because it's
not necessarilly forwarding ownership.
Remove the isTransformationTerminator API, which is not useful or well
defined.
Rewrite several instances of complex logic to handle block arguments
with the simple terminator result API. This defines away potential
bugs where we don't detect casts that perform implicit conversion.
Replace uses of the SILPhiArgument type and code that explicitly
handle block arguments. Control flow is irrelevant in these
situations. SILPhiArgument needs to be deleted ASAP. Instead, use
simple APIs like SILArgument::isTerminatorResult(). Eventually this
will be replaced by a TerminatorResult type.
Andy some time ago already created the new API but didn't go through and update
the old occurences. I did that in this PR and then deprecated the old API. The
tree is clean, so I could just remove it, but I decided to be nicer to
downstream people by deprecating it first.
Add NonTypeDependentOperandToValue predicate for composability.
Add a getNonTypeDependentOperandValues(), which can be used as a functor.
The skipTypeDependentOperands parameter complicated the API.
The reason why I am doing this is that currently checked_cast_br of an AnyObject
may return a different value due to boxing. As an example, this can occur when
performing a checked_cast_br of a __SwiftValue(AnyHashable(Klass())).
To model this in SIL, I added to OwnershipForwardingMixin a bit of information
that states if the instruction directly forwards ownership with a default value
of true. In checked_cast_br's constructor though I specialize this behavior if
the source type is AnyObject and thus mark the checked_cast_br as not directly
forwarding its operand. If an OwnershipForwardingMixin directly forwards
ownership, one can assume that if it forwards ownership, it will always do so in
a way that ensures that each forwarded value is rc-identical to whatever result
it algebraically forwards ownership to. So in the context of checked_cast_br, it
means that the source value is rc-identical to the argument of the success and
default blocks.
I added a verifier check to CheckedCastBr that makes sure that it can never
forward guaranteed ownership and have a source type of AnyObject.
In SemanticARCOpts, I modified the code that builds extended live ranges of
owned values (*) to check if a OwnershipForwardingMixin is directly
forwarding. If it is not directly forwarding, then we treat the use just as an
unknown consuming use. This will then prevent us from converting such an owned
value to guaranteed appropriately in such a case.
I also in SILGen needed to change checked_cast_br emission in SILGenBuilder to
perform an ensurePlusOne on the input operand (converting it to +1 with an
appropriate cleanup) if the source type is an AnyObject. I found this via the
verifier check catching this behavior from SILGen when compiling libswift. This
just shows how important IR verification of invariants can be.
(*) For those unaware, SemanticARCOpts contains a model of an owned value and
all forwarding uses of it called an OwnershipLiveRange.
rdar://85710101
TLDR: This is just an NFC rename in preparation for changing
SILValue::getOwnershipKind() of any forwarding instructions to return
OwnershipKind::None if they have a trivial result despite forwarding ownership
that isn't OwnershipKind::None (consider an unchecked_enum_data of a trivial
payload from a non-trivial enum).
This ensures that one does not by mistake use this routine instead of
SILValue::getOwnershipKind(). The reason why these two things must be
distinguished is that the forwarding ownership kind of an instruction that
inherits from OwnershipForwardingMixin is explicitly not the ValueOwnershipKind
of the result of the instruction. Instead it is a separate piece of state that:
1. For certain forwarding instructions, defines the OwnershipConstraint of the
forwarding instruction.
2. Defines the ownership kind of the result of the value. If the result of the
value is non-trivial then it is exactly the set ownership kind. If the result is
trivial, we use OwnershipKind::None instead. As an example of this, consider an
unchecked_enum_data that extracts from a non-trivial enum a trivial payload:
```
enum Either {
case int(Int)
case obj(Klass)
}
%1 = load_borrow %0 : $*Either
%2 = unchecked_enum_data %1 : $Either, #Either.int!enumelt.1 // Int type
end_borrow %1 : $Either
```
If we were to identify the forwarding ownership kind (guaranteed) of
unchecked_enum_data with the value ownership kind of its result, we would
violate ownership since we would be passing a guaranteed value to the operand of
the unchecked_enum_data that will only accept values with
OwnershipKind::None. =><=.
Migrating to this classification was made easy by the recent rewrite
of the OSSA constraint model. It's also consistent with
instruction-level abstractions for working with different kinds of
OperandOwnership that are being designed.
This classification vastly simplifies OSSA passes that rewrite OSSA
live ranges, making it straightforward to reason about completeness
and correctness. It will allow a simple utility to canonicalize OSSA
live ranges on-the-fly.
This avoids the need for OSSA-based utilities and passes to hard-code
SIL opcodes. This will allow several of those unmaintainable pieces of
code to be replaced with a trivial OperandOwnership check.
It's extremely important for SIL maintainers to see a list of all SIL
opcodes associated with a simple OSSA classification and set of
well-specified rules for each opcode class, without needing to guess
or reverse-engineer the meaning from the implementation. This
classification does that while eliminating a pile of unreadable
macros.
This classification system is the model that CopyPropagation was
initially designed to use. Now, rather than relying on a separate
pass, a simple, lightweight utility will canonicalize OSSA
live ranges.
The major problem with writing optimizations based on OperandOwnership
is that some operations don't follow structural OSSA requirements,
such as project_box and unchecked_ownership_conversion. Those are
classified as PointerEscape which prevents the compiler from reasoning
about, or rewriting the OSSA live range.
Functional Changes:
As a side effect, this corrects many operand constraints that should
in fact require trivial operand values.
I think what was happening here was that we were using one of the superclass
classofs and were getting lucky since in the place I was using this I was
guaranteed to have single value instructions and that is what I wrote as my
first case X ).
I also added more robust checks tieing the older isGuaranteed...* APIs to the
ForwardingOperand API. I also eliminated the notion of Branch being an owned
forwarding instruction. We only used this in one place in the compiler (when
finding owned value introducers), yet we treat a phi as an introducer, so we
would never hit a branch in our search since we would stop at the phi argument.
The bigger picture here is that this means that all "forwarding instructions"
either forward ownership for everything or for everything but owned/unowned.
And for those listening in, I did find one instruction that was from an
ownership forwarding subclass but was not marked as forwarding:
DifferentiableFunctionInst. With this change, we can no longer by mistake have
such errors enter the code base.
This makes it easier to understand conceptually why a ValueOwnershipKind with
Any ownership is invalid and also allowed me to explicitly document the lattice
that relates ownership constraints/value ownership kinds.
Previously, we always inferred the ownership of the switch_enum from its phi
operands. This forced us to need to model a failure to find a good
OperandOwnershipKindMap in OperandOwnership.cpp. We want to eliminate such
conditions so that we can use failing to find a constraint to mean that a value
can accept any value rather than showing a failure.
This makes it clearer that isConsumingUse() is not an owned oriented API and
returns also for instructions that end the lifetime of guaranteed values like
end_borrow.
This is important to do since otherwise, we may be implicitly reducing the
lifetime of a value which we can not do yet since we do not require all interior
pointer instructions to be guarded by borrows (yet). Once that constraint is in
place, we will not have this problem.
Consider a situation where one has a @owned switch_enum on an
indirect box case which is post-dominated by an unreachable that we want
to convert to @guaranteed:
enum MyEnum {
indirect case FirstCase(Int)
...
}
bb0(%in_guaranteed_addr : $*MyEnum):
...
%0 = load [copy] %in_guaranteed_addr : $*MyEnum
switch_enum %0 : $MyEnum, case #MyEnum.FirstCase: bb1, ...
bb1(%1 : @owned ${ var Int }):
%2 = project_box %1 : ${ var Int }, 0
%3 = load [trivial] %2 : $*Int
apply %log(%3) : $@convention(thin) (Int) -> ()
unreachable
In this case, we will not have a destroy_value on the box, but we may
have a project_box on the box. This is ok since we are going to leak the
value. But since we are using all consuming uses to determine the
lifetime, we will want to insert an end_borrow at the head of the
switch_enum dest block like follows:
bb0(%in_guaranteed_addr : $*MyEnum):
...
%0 = load_borrow %in_guaranteed_addr : $*MyEnum
switch_enum %0 : $MyEnum, case #MyEnum.FirstCase: bb1, ...
bb1(%1 : @guaranteed ${ var Int }):
end_borrow %1 : ${ var Int }
%2 = project_box %1 : ${ var Int }, 0
%3 = load [trivial] %2 : $*Int
apply %log(%3) : $@convention(thin) (Int) -> ()
unreachable
which would violate ownership invariants. Instead, we need to realize
that %1 is dominated by a dead end block so we may not have a
destroy_value upon it meaning we should just not insert the end_borrow
here. If we have a destroy_value upon it (since we did not get rid of a
destroy_value), then we will still get rid of the destroy_value if we are
going to optimize this, so we are still correct.
rdar://68096662
