Move the code that sets up the context above all the code that
depends on that context.
This helps keep the relationship straight between several
sub-utilities and gradually clean them up.
Allow quickly checking for valid OSSA value substitution independent
from information about the value's lifetime or scope. Make it a static
member to allow this to check to be done outside of the RAUW
utility. e.g. from SimplifyCFG.
findInnerTransitiveUsesForAddress was incorrectly returning true for
pointer escapes.
Introduce enum AddressUseKind { NonEscaping, PointerEscape, Unknown };
Clients need to handle each of these cases differently.
Recording uses is now optional. This utility is also used simply to
check for PointerEscape. When uses are recorded, they are used to
extend a live range. There could be a large number of transitive uses
that we don't want to pass back to the caller.
This mainly simplifies the utility, but also improves optimization as
a side effect.
Update OSSA RAUW after replacing BorrowedAddress with AddressOwnership.
InteriorPointer is no longer needed. This simplifies the fixup
context. Eventually the fixup context will be very lightweight. This
is just the first step.
This replaces the recent BorrowedAddress utility (the address may not
be borrowed!)
APIs:
AddressOwnership::hasLocalOwnershipLifetime() - convenience on top of
AccessBase::hasLocalOwnershipLifetime().
AddressOwnership::getOwnershipReferenceRoot() - convenience on top of
AccessBase::getOwnershipReferenceRoot().
AddressOwnership::findTransitiveUses() - wrapper API over the internal
helper findTransitiveUsesForAddress()
AddressOwnership::areUsesWithinLifetime() - wrapper adds a quick check
on top of BorrowedValue::areUsesWithinLifetime()
Handle SSA update (phi creation) when extending an owned lifetime over
a borrowed lifetime.
This is a layer of logic above BorrowedValue but below
OwnershipLifetimeExtender and other higher-level utilities.
Ownership rauw uses a shared ownership fixup context to maintain state.
When ownership rauw fails, due to some invalid condition, we leave
behind stale data in this shared ownership fixup context.
This stale context can indvertantly affect the next rauw on addresses.
In addition to setting the ownership fixup context to nullptr, we
should also clear it so that it's internal data structures are
cleared.
Determines whether an address might be inside a borrowed scope. If so,
then any address substitution needs to find that scope boundary to
avoid violating its basic guarantee that all uses are within scope.
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.
This directly adds support to BasicBlockCloner for updating OSSA.
It also adds a much more general-purpose GuaranteedPhiBorrowFixup
utility which can be used for more complicated SSA updates, in which
multiple phis need to be created. More generally, it handles adding
nested borrow scopes for guaranteed phis even when that phi is used by
other guaranteed phis.
Generalize the AccessUseDefChainCloner in MemAccessUtils. It was
always meant to work this way, just needed a client.
Add a new API AccessUseDefChainCloner::canCloneUseDefChain().
Add a bailout for begin_borrow and mark_dependence. Those
projections may appear on an access path, but they can't be
individually cloned without compensating.
Delete InteriorPointerAddressRebaseUseDefChainCloner.
Add a check in OwnershipRAUWHelper for canCloneUseDefChain.
Add test cases for begin_borrow and mark_dependence.
This PR just removes an unnecessary error raised in
OwnershipLifetimeExtender::createPlusOneCopy.
We can ownership rauw a value inside the loop with a value outside the
loop. findJointPostDominatingSet correctly helps create control
equivalent copies inside the loop for replacement.
Instead make `findJointPostDominatingSet` a stand-alone function.
There is no need to keep the temporary SmallVector alive across multiple calls of findJointPostDominatingSet for the purpose of re-using malloc'ed memory. The worklist usually contains way less elements than its small size.
This is necessitated by the SILArgument representation. It has the
tragic property that adding unrelated phis invalidates existing
phis. Therefore, the optimizer can't do book-keeping of phi values by
refering directly to SILValues or Operands. Instead, it must only
refer to SILBasicBlocks and argument indices.
...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.
My goal was to reduce the size of SILLocation. It now contains only of a storage union, which is basically a pointer and a bitfield containing the Kind, StorageKind and flags. By far, most locations are only single pointers to an AST node. For the few cases where more data needs to be stored, this data is allocated separately: with the SILModule's bump pointer allocator.
While working on this, I couldn't resist to do a major refactoring to simplify the code:
* removed unused stuff
* The term "DebugLoc" was used for 3 completely different things:
- for `struct SILLocation::DebugLoc` -> renamed it to `FilePosition`
- for `hasDebugLoc()`/`getDebugSourceLoc()` -> renamed it to `hasASTNodeForDebugging()`/`getSourceLocForDebugging()`
- for `class SILDebugLocation` -> kept it as it is (though, `SILScopedLocation` would be a better name, IMO)
* made SILLocation more "functional", i.e. replaced some setters with corresponding constructors
* replaced the hand-written bitfield `KindData` with C bitfields
* updated and improved comments
A few notes:
1. We already have provide an operator* that does this and even better makes the
conversion explicit in the source.
2. The bool operator checks both that kind is not invalid and that the operand
is non-null. This ensures we can use an `if` to properly check for a valid
BorrowingOperand.
Some notes:
1. I moved the identity round-trip case to InstSimplify since that is where
optimizations like that are.
2. I did not update in this commit the code that eliminates convert_function
when it is only destroyed. In a subsequent commit I am going to implement
that in a general way and apply it to all forwarding instructions.
3. I implemented eliminating convert_function with ownership only uses in a
utility so that I can reuse it for other similar optimizations in SILCombine.
Instead of saving BorrowingOperand on the context save the SILBasicBlock
and index of the terminator operand.
This avoids the use-after-free in eliminateReborrowsOfRecursiveBorrows.
Previously, eliminateReborrowsOfRecursiveBorrows called helper
insertOwnedBaseValueAlongBranchEdge, which can delete a branch
instruction (reborrow) that could have been cached in
recursiveReborrows.
Already, we allow for owned/guaranteed values to be passed to values with
unowned ownership. This just cleans up the SIL a bit.
That being said, we still need unchecked_ownership_conversion for the terminator
case since any owned/guaranteed's value (ignoreing function parameters) will end
before the return meaning that we need some way of escaping it.
The reason why is that addresses from pointer_to_address never have transitive
interior pointer constraints from where ever the pointer originally came
from. This is the issue that was causing a CSE test to fail, so I added a test
to ossa_rauw_test that works this code path.
In OSSA, we enforce that addresses from interior pointer instructions are scoped
within a borrow scope. This means that it is invalid to use such an address
outside of its parent borrow scope and as a result one can not just RAUW an
address value by a dominating address value since the latter may be invalid at
the former. I foresee that I am going to have to solve this problem and so I
decided to write this API to handle the vast majority of cases.
The way this API works is that it:
1. Computes an access path with base for the new value. If we do not have a base
value and a valid access path with root, we bail.
2. Then we check if our base value is the result of an interior pointer
instruction. If it isn't, we are immediately done and can RAUW without further
delay.
3. If we do have an interior pointer instruction, we see if the immediate
guaranteed value we projected from has a single borrow introducer value. If not,
we bail. I think this is reasonable since with time, all guaranteed values will
always only have a single borrow introducing value (once struct, tuple,
destructure_struct, destructure_tuple become reborrows).
4. Then we gather up all inner uses of our access path. If for some reason that
fails, we bail.
5. Then we see if all of those uses are within our borrow scope. If so, we can
RAUW without any further worry.
6. Otherwise, we perform a copy+borrow of our interior pointer's operand value
at the interior pointer, create a copy of the interior pointer instruction upon
this new borrow and then RAUW oldValue with that instead. By construction all
uses of oldValue will be within this new interior pointer scope.
The reason why I am doing this is that I am building up more utilities based on
passing around this struct of context that do not want it for RAUWing
purposes. So it makes sense on a helper (OwnershipRAUWHelper) that composes with
its state.
Just a refactor, should be NFC.
Specifically,
copyAndExtendForLifetimeEndingRAUW -> createPlusOneCopy(value, oldConsumingUse)
copyAndExtendForNonLifetimeEndingRAUW -> createPlusZeroCopy(value, nonLifetimeEndingUses)
copyBorrowAndExtendForRAUW -> createPlusZeroBorrow(value, nonLifetimeEndingUses)
Beyond being shorter, the PlusOne vs PlusZero mnemonic is telling the caller
whether or not the caller is responsible for cleaning up the returned
copy_value. In the PlusZero cases, we assume that all uses are non-lifetime
ending and we need to insert all destroy_value at the liveness points of the
value.
In the PlusOne case in contrast, we are supposed to make a copy of value and the
complete oldConsumingUse's block into a joint post-dominance set of blocks. Then
we insert destroy_values for our new copy into the completion blocks that we
found and leave cleaning up value along paths through oldConsumingUse to our
user. In this sense the value is a PlusOne value that our user must clean up for
us (sorta makes me think about ManagedValue).
The only operational change here is that I needed to be able to grab the module
from the SILValue so I could see if we were in Raw SIL or not. I realized the
only case where we could not get the module is from SILUndef and at this point
in the code we know we are going to bail already for SILUndef. This is because
we already know our new value doesn't have OwnershipKind::None and we don't
replace OwnershipKind::None things with non-OwnershipKind::None things since I
haven't implemented support for that corner case yet (but will with time).
Once I realized the previous paragraph, I was able to add support without issue.
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.
Specifically before this PR, if a caller did not customize a specific callback
of InstModCallbacks, we would store a static default std::function into
InstModCallbacks. This means that we always would have an indirect jump. That is
unfortunate since this code is often called in loops.
In this PR, I eliminate this problem by:
1. I made all of the actual callback std::function in InstModCallback private
and gave them a "Func" postfix (e.x.: deleteInst -> deleteInstFunc).
2. I created public methods with the old callback names to actually call the
callbacks. This ensured that as long as we are not escaping callbacks from
InstModCallback, this PR would not result in the need for any source changes
since we are changing a call of a std::function field to a call to a method.
3. I changed all of the places that were escaping inst mod's callbacks to take
an InstModCallback. We shouldn't be doing that anyway.
4. I changed the default value of each callback in InstModCallbacks to be a
nullptr and changed the public helper methods to check if a callback is
null. If the callback is not null, it is called, otherwise the getter falls
back to an inline default implementation of the operation.
All together this means that the cost of a plain InstModCallback is reduced and
one pays an indirect function cost price as one customizes it further which is
better scalability.
P.S. as a little extra thing, I added a madeChange field onto the
InstModCallback. Now that we have the helpers calling the callbacks, I can
easily insert instrumentation like this, allowing for users to pass in
InstModCallback and see if anything was RAUWed without needing to specify a
callback.
When we are populating transitive users while handling guaranteed values
in ownership rauw, we were including values with none ownership.
Example : rauw of %2 with a dominating value
Here %arg1 was also considered a transitive use
%2 = struct_extract %0 : $StructWithEnum2, #StructWithEnum2.val
%copy = copy_value %2 : $FakeOptional2
switch_enum %2 : $FakeOptional2, case #FakeOptional2.some1!enumelt:bb5, case #FakeOptional2.some2!enumelt:bb6
bb5(%arg1 : $UInt):
br bb7(%arg1 : $UInt)
bb6(%arg2 : @guaranteed $Klass):
%4 = unchecked_trivial_bit_cast %arg2 : $Klass to $UInt
br bb7(%4 : $UInt)
This is incorrect because %arg1 is a trivial value, and this also
leads to ValueLifetimeAnalysis needing a split for finding a frontier
for the use of %arg1 in the branch instruction. In ossa, we should never
have to split edges for finding frontiers, because we do not have critical
edges.
Branch instructions and frontiers can have
LocationKind::ReturnKind/ImplicitReturnKind which are not correct
locations to use for copy_value/destroy_value etc
