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.
The new "relative" version of AccessStorageWithBase carries additional
information about the walk from the specified address back to the base.
For now, that includes the original address and the most transformative
sort of cast that was encountered.
Add NonTypeDependentOperandToValue predicate for composability.
Add a getNonTypeDependentOperandValues(), which can be used as a functor.
The skipTypeDependentOperands parameter complicated the API.
SemanticARCOptVisitor::performGuaranteedCopyValueOptimization was
converting this SIL
%borrow = begin_borrow %copiedValue
%copy = copy_value %borrow
%borrowCopy = begin_borrow %copy
end_borrow %borrow
end_borrow %borrowCopy
destroy_value %copy
// something something
unreachable
into
%borrow = begin_borrow %copiedValue
%innerBorrow = begin_borrow %borrow
end_borrow %borrow
end_borrow %innerBorrow
// something something
unreachable
Dead-end blocks are simply irrelevant for this
optimization. Unfortunately, there were multiple layers of attempted
workarounds that were hiding the real problem, except in rare cases.
Thanks Nate Chandler for reducing the test.
If a value's lifetime is preserved by a different lexical scope, it is
fine to strip a different scope. Specifically, if it is preserved by
being a guaranteed argument or a nested borrow of an outer lexical
scope, allow a lexical borrow scope to be stripped.
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
Previously, TempRValueElimination would peephole simple alloc_stacks,
even when they were lexical; here, they are left for Mem2Reg to properly
handle.
Previously, SemanticARCOpts would eliminate lexical begin_borrows,
incorrectly allowing the lifetime of the value borrowed by them to be
observably shortened. Here, those borrow scopes are not eliminated if
they are lexical.
Added an executable test that verifies that a local variable strongly
referencing a delegate object keeps that delegate alive through the call
to an object that weakly references the delegate and calls out to it.
This abstraction is heavily used to ask about the current borrow scope
enclosing some uses. Give it the functionality it needs.
Add BorrowedValue::computeLiveness(PrunedLiveness). Get the borrow
scope's live range. A trivial 4-line implementation.
Cleanup BorrowedValue::areUsesWithinScope(). Quick check to see if a set
of uses known to be dominated by the borrow are within the borrow scope.
Add BorrowedValue::hasReborrow(). Is this local borrow scope
reborrowed? If not, then it's local scope-ending operations are the
end of its required lifetime.
Simplify BorrowedValue::gatherReborrows() to use OperandOwnership::Reborrow.
Otherwise, we hit misc crashes. The worklist should have always been filtering
these. I wonder why we have never hit this issue before.
I added a new API that filters out type dependent uses called
ValueBase::getNonTypeDependentUses() to make it easier to perform def->use
worklist traversal ignoring these uses. This mirrors the APIs that we have
created for filtering type dependent operands when performing use->def worklist
traversal.
I also noticed that we are not eliminating a load [copy] that we could in the
test case. I am going to file a separate bug report for that work.
rdar://79781943
Don't allow an owned call argument to be considered a valid BorrowingOperand.
More generally, make sure there is a perfect equivalence between valid
BorrowingOperand and the corresponding OperandOwnership kind.
Without this when constructing an InstModCallback it is hard to distinguish
which closure is meant for which operation when passed to the constructor of
InstModCallback (if this was in Swift, we could use argument labels, but we do
not have such things in c++).
This new value type sort of formulation makes it unambiguous which callback is
used for what when constructing one of these.
This bleeds into the implementation where "guaranteed" is used
everywhere to talk about optimization of guaranteed values. We need to
use mandatory to indicate we're talking about the pass pipeline.
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. =><=.
...for handling borrow scopes:
- find[Extended]TransitiveGuaranteedUses
- BorrowingOperand::visit[Extended]ScopeEndingUses
- BorrowedValue BorrowingOperand::getBorrowIntroducingUserResult()
And document the logic.
Mostly NFC in this commit, but more RAUW cases should be correctly
handled now.
Particularly, ensure that we can cleanly handle all manner of
reborrows. This is necessary to ensure both CanonicalizeOSSA and
replace-all-uses higher-level utilities handle all cases.
This generalizes some of the logic in CanonicalizeOSSA so it can be
shared by other high-level OSSA utilities.
These utilities extend the fundamental BorrowingOperand and
BorrowedValue functionality that has been designed recently. It builds
on and replaces a mix of piece-meal functionality that was needed
during bootstrapping. These APIs are now consistent with the more
recently designed code. It should be obvious what they mean and how to
use them, should be very hard to use them incorrectly, and should be
as efficient as possible, since they're fundamental to other
higher-level utilities.
Most importantly, there were several very subtle correctness issues
that were not handled cleanly in a centralized way. There are now a
mix of higher-level utilities trying to use this underlying
functionality, but it was hard to tell if all those higher-level
utilities were covering all the subtle cases:
- checking for PointerEscapes everywhere we need to
- the differences between uses of borrow introducers and other
guaranteed values
- handling the uses of nested borrow scopes
- transitively handling reborrows
- the difference between nested and top-level reborrows
- forwarding destructures (which can cause exponential explosion)
In short, I was fundamentally confused and getting things wrong before
designing these utilities.
Importantly this also lets us use the analysis framework to validate that we do
properly invalidate DeadEndBlocks, preventing bugs.
I did not thread this all over the compiler. Instead I just used it for now in
SemanticARCOpts just to add some coverage without threading it into too many
places.
Instead, I just added some static helper methods that perform the same
operations without needing to deal with generics/etc on OwnershipForwardingMixin
itself. The reason why I did this is that this Mixin is not part of the SILNode
heirarchy so we shouldn't use utilities tied to the SILNode hierarchy.
This allows for me to do a couple of things improving quality/correctness/ease of use:
1. I reimplemented InstMod's RAUW and RAUW/erase helpers on top of
setUseValue/deleteInst. Beyond allowing the caller to specify less things, we
gain an orthogonality preventing bugs like overriding erase/RAUW but not
overriding erase or having the erase used in erase/RAUW act differently than
the erase for deleteInst.
2. There were a bunch of places using InstModCallback that also were setting
uses without having the ability for InstModCallbacks perform it (since it
only supported RAUW). This is an anti-pattern and could cause subtle bugs to
be introduced by appropriate state in the caller not being updated.
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.
Specifically, we check that all of the unowned's value uses are within the
lifetime of the unchecked_ownership_conversion's operand. If so, we eliminate
it.
Our worklist already uses values, so it makes sense to use a SILValueVisitor. It
will also let me throw in a few ARC dead argument elimination optimizations so
clean up a pattern from my ARC RAUW thing. Once we have simplify-cfg it will not
be needed, but I want to know I am good before I flip the switch.
The specific problem here is that I am going to be adding some code to
SemanticARCOpts that eliminates reborrows and may need to create new phi
arguments and thus add arguments to edges. The weird thing about this is that
doing so actually requires us to create a new terminator!
This means that subtle pointer invalidation issues can occur here. To work
around that we store our terminators as SILBasicBlock, operand number since we
can always immediately find a terminator from its basic block. If we do not have
a terminator, we keep on just storing the SILInstruction itself.
NOTE: This only saves us from additive changes. Deletions are still an issue.
This commit is doing a few things:
1. It is centralizing all decisions about whether an operand's owner instruction
or a value's parent instruction is forwarding in each SILInstruction
itself. This will prevent this information from getting out of sync.
2. This allowed me to hide the low level queries in OwnershipUtils.h that
determined if a SILNodeKind was "forwarding". I tried to minimize the amount of
churn in this PR and thus didn't remove the
is{Owned,Ownership,Guaranteed}Forwarding{Use,Value} checks. Instead I left them
alone but added in asserts to make sure that if the old impl ever returns true,
the neew impl does as well. In a subsequent commit, I am going to remove the old
impl in favor of isa queries.
3. I also in the process discovered that there were some instructions that were
being inconsistently marked as forwarding. All of the asserts in the PR caught
these and I fixed these inconsistencies.
Specifically the optimization that is being performed here is the elimination of
lifetimes that hand off ownership in between two regions of code. Example:
```
%1 = copy_value %0
...
destroy_value %0
...
apply %consumingUser(%1)
```
We really want to handle this case since it is a natural thing that comes up in
programs and will let me eliminate the *evil* usage of emitDestroyValueOperation
in TypeLowering without needing to modify huge amounts of tests.
This split will ensure we are testing only what a specific optimization is doing
rather than all together.
NOTE: The way I split up the tests is I first split up each of the tests by
subject area by hand that I thought were specifically testing one pass. Then any
tests where the FileCheck tests started to fail due to us not running the other
passes, I put back a copy in the original semantic-arc-opts.sil to ensure we do
not regress.
Note, the tests that I copied for each of these passes
are originally from semantic-arc-opts.sil. I left them there as well so we could
see all of the opts together. I also only copied the ones that were testing pass
specific functionality.
This doesn't happen as much as the guaranteed + owned value optimization but can
occur once we start eliminating borrow scopes. I noticed that I needed this when
looking at the arbitrary RAUW for ownership API.
When I originally landed this optimization, I was trying to handle simple cases
without forwarding instructions in my head. In my head, handling this with
forwarding instructions meant using OwnershipLiveRange. Sadly, I didn't realize
at the time that if I didn't use OwnershipLiveRange and just treated forwarding
insts as normal lifetime ending instructions for owned values, everything just
worked (since our check was where %5 in the following was any lifetime ending
instruction for %4c.
```
%4 = copy_value %3 : $Builtin.NativeObject
%4c = copy_value %4 : $Builtin.NativeObject
destroy_value %4 : $Builtin.NativeObject
%5 = enum $FakeOptional<Builtin.NativeObject>, #FakeOptional.some!enumelt, %4c : $Builtin.NativeObject
```
The optimization causes the above to simplified to:
```
%4 = copy_value %3 : $Builtin.NativeObject
%5 = enum $FakeOptional<Builtin.NativeObject>, #FakeOptional.some!enumelt, %4 : $Builtin.NativeObject
```
Notice importantly that we are not shrinking the lifetime of %4, so we can do
this safely without interior pointers being guarded with borrow scopes
everywhere yet.
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.
