Specifically I provided a '->' and a '*' operator. So now you can do:
```
borrowedValue->callSILValueMethod();
```
and explicitly cast to SILValue using '*'.
This implies making -> and * return an Operand * instead of an
OwnershipForwardingInst. So one can thus do:
ForwardingOperand op;
op.myForwardingOperandMethod();
op->myOperandMethod();
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.
This is a generic API that when ownership is enabled allows one to replace all
uses of a value with a value with a differing ownership by transforming/lifetime
extending as appropriate.
This API supports all pairings of ownership /except/ replacing a value with
OwnershipKind::None with a value without OwnershipKind::None. This is a more
complex optimization that we do not support today. As a result, we include on
our state struct a helper routine that callers can use to know if the two values
that they want to process can be handled by the algorithm.
My moticiation is to use this to to update InstSimplify and SILCombiner in a
less bug prone way rather than just turn stuff off.
Noting that this transformation inserts ownership instructions, I have made sure
to test this API in two ways:
1. With Mandatory Combiner alone (to make sure it works period).
2. With Mandatory Combiner + Semantic ARC Opts to make sure that we can
eliminate the extra ownership instructions it inserts.
As one can see from the tests, the optimizer today is able to handle all of
these transforms except one conditional case where I need to eliminate a dead
phi arg. I have a separate branch that hits that today but I have exposed unsafe
behavior in ClosureLifetimeFixup that I need to fix first before I can land
that. I don't want that to stop this PR since I think the current low level ARC
optimizer may be able to help me here since this is a simple transform it does
all of the time.
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 originally trafficked in Instructions and for some reason the name was
never changed.
I also changed the result type to be a bool and added the ability for the passed
in closure to signal failure (and iteration stop) by returning false. This also
makes it possible to use visitLocalEndScopeUses in if statements which can be
useful.
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.
A reborrow occurs when a Borrowing Operand ends the lifetime of a borrowed value
and propagates forward a new guaranteed value that continues the guaranteed
lifetime of the value.
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.
This updates how we model reborrow's lifetimes for ownership verification.
Today we follow and combine a borrow's lifetime through phi args as well.
Owned values lifetimes end at a phi arg. This discrepency in modeling
lifetimes leads to the OwnershipVerifier raising errors incorrectly for
cases such as this, where the borrow and the base value do not dominate
the end_borrow:
bb0:
cond_br undef, bb1, bb2
bb1:
%copy0 = copy_value %0
%borrow0 = begin_borrow %copy0
br bb3(%borrow0, %copy0)
bb2:
%copy1 = copy_value %1
%borrow1 = begin_borrow %copy1
br bb3(%borrow1, %copy1)
bb3(%borrow, %baseVal):
end_borrow %borrow
destroy_value %baseVal
This PR adds a new ReborrowVerifier. The ownership verifier collects borrow's
lifetime ending users and populates the worklist of the ReborrowVerifier
with reborrows and the corresponding base value.
ReborrowVerifier then verifies that the lifetime of the reborrow is
within the lifetime of the base value.
I am currently working on updating SimplifyCFG for ownership. One thing that I
am finding that I need is the ability to compute the lifetime of a guaranteed
argument from a checked_cast_br/switch_enum in order to convert said
instructions to a br. The issue comes from br acting as a consuming (lifetime
ending) use of a borrowed value, unlike checked_cast_br/switch_enum (which are
treated like forwarding instructions). This means that during the conversion we
need to insert a begin_borrow on the value before the new br instruction and
then create an end_borrow at the end of the successor block's argument's
lifetime.
By refactoring out this code from the ownership verifier, I can guarantee that
said lifetime computation will always match what the ownership verifier does
internally preventing them from getting out of sync.
Just like br inst, structs are phis in the ownership graph that one can induce
on top of the def-use graph. In this commit, I basically fill in the relevant
blanks in the ADT for such phis for struct so that the optimization for branches
is generalized onto structs.
<rdar://problem/63950481>
This is letting me refactor the implementation of every place that I work with
branches as "ownership phi operands" to instead work with
OwnershipPhiOperand. In a future commit, I am going to use this to add support
for optimizing structs and tuples that have multiple owned incoming values.
<rdar://problem/63950481>
Andy and I for some time have been discussing the right name for these two
"ownership concepts". What we realized is that the "ing" on
BorrowScopeIntroducingValue is very unfortunate since this value is the result
of a new borrow scope being introduced. So the name should be really:
BorrowScopeIntroducedValue. Given that is sort of unsatisfying, we settled on
the name BorrowedValue.
Once we found the name BorrowedValue, we naturally realized that
BorrowScopeOperand -> BorrowingOperand followed. This is because the operand is
the operand of the instruction that is creating the new borrow scope. So in a
sense the Operand is the "Use" that causes the original value to become
borrowed. So a BorrowingOperand is where the action is and is "active".
This means that it can only have a guaranteed object as an operandand that we
validate that all uses of the result address of open_existential_box occur only
within the lifetime of said object's borrow scope.
This is the most simple initial version that I can commit. The hope is that this will help to bring this up in a nice way.
I am going to handle the multiple phi node and load [copy] case later to reduce
code churn.
<rdar://problem/56720436>
These enable robust walking up the def-use ossa graph to find the value that
introduces an independent underlying owned value, looking through forwarding
insts.
This is a similar concept to "rc-identity" that we talk about in the low level
ARC optimizer. The main idea is that all owned values in a program can be
partitioned into two different kinds of values:
1. Introducer values that exist independently of any other local values in the
function. It is a point of truth from which the owned objects lifetime extends
from and is in a certain sense an initialization (in a category theoretic sense)
in the lifetime of the underlying object that we are manipulating.
2. Forwarding values do not represent an object lifetime that is "truly"
independent of any other value locally: its liveness comes from passing on
liveness from some introducer or some other forwarding value.
The reason why I am adding this new construct is that I am beginning to
implement a new form of ARC optimization that enables us to convert @owned SIL
phi arguments to @guaranteed phi arguments. As part of that, I need to have a
way to in a systematic way finding the underlying incoming values (using the
logic used to determine forwarding in the ownership verifier).
This is the first part of that effort, defining the ontology we are going to
work with. Keep in mind this is just a seed ontology, if I missed any "owned
introducers" (I am sure I did), feel free to add them.
Currently, we only classify ref_element_addr and ref_tail_addr. But we should
expand this to project_box, project_existential_box and open_existential_box as
well.
The only reason why BranchPropagatedUser existed was because early on in SIL, we
weren't sure if cond_br should be able to handle non-trivial values in
ossa. Now, we have reached the point where we have enough experience to make the
judgement that it is not worth having in the representation due to it not
holding its weight.
Now that in ToT we have banned cond_br from having non-trivial operands in ossa,
I can just eliminate BranchPropagatedUser and replace it with the operands that
we used to construct them!
A few notes:
1. Part of my motiviation in doing this is that I want to change LiveRange to
store operands instead of instructions. This is because we are interested in
being able to understand the LiveRange at a use granularity in cases where we
have multiple operands. While doing this, I discovered that I needed
SILInstructions to use the Linear Lifetime Checker. Then I realized that now was
the time to just unwind BranchPropagatedUser.
2. In certain places in SemanticARCOpts, I had to do add some extra copies to
transform arrays of instructions from LiveRange into their operand form. I am
going to remove them in a subsequent commit when I change LiveRange to work on
operands. I am doing this split to be incremental.
3. I changed isSingleInitAllocStack to have an out array of Operand *. The only
user of this code is today in SemanticARCOpts and this information is fed to the
Linear Lifetime Checker, so I needed to do it.
OwnershipUtils.h is growing a bit and I want to use it to store abstract higher
level utilities for working with ossa. LinearLifetimeChecker is just a low level
detail of that, so it makes sense to move it out now.
Specifically, I got rid of the constructors for BorrowScopeIntroducingValue and
made it so one can only construct BorrowScopeIntroducingValue from the static
constructor.
I also changed the place where we mapped values from BorrowScopeIntroducingValue
-> BorrowScopeIntroducingValueKind. This simplifies the whole thing.
I added a new API into OwnershipUtils called
getSingleBorrowIntroducingValue. This API returns a single
BorrowScopeIntroducingValue for a passed in guaranteed value. If we can not find
such a BorrowScopeIntroducingValue or we find multiple such, we return None.
Using that, I refactored StorageGuaranteesLoadVisitor::visitClassAccess(...) to
use this new API which should make it significantly more robust since the
routine uses the definitions of "guaranteed forwarding" that the ownership
verifier uses when it verifies meaning that we can rely on the routine to be
exhaustive and correct. This means that we now promote load [copy] ->
load_borrow even if our borrow scope introducer feeds through a switch_enum or
checked_cast_br result (the main reason I looked into this change).
To create getSingleBorrowIntroducingValue, I refactored
getUnderlyingBorrowIntroucingValues to use a generator to find all of its
underlying values. Then in getSingleBorrowIntroducingValue, I just made it so
that we call the generator 1-2 times (as appropriate) to implement this query.
Specifically, this PR adds support for optimizing simple cases where we do not
need to compute LiveRanges with the idea of first doing simple transforms that
involve small numbers of instructions first. With that in mind, we only optimize
cases where our copy_value has a single consuming user and our owned value has a
single destroy_value. To understand the transform here, consider the following
SIL:
```
%0 = ...
%1 = copy_value %0 (1)
apply %guaranteedUser(%0) (2)
destroy_value %0 (3)
apply %cviConsumer(%1) (4)
```
We want to eliminate (2) and (3), effectively joining the lifetimes of %0 and
%1, transforming the code to:
```
%0 = ...
apply %guaranteedUser(%0) (2)
apply %cviConsumer(%0) (4)
```
Easily, we can always do this transform in this case since we know that %0's
lifetime ends strictly before the end of %1's due to (3) being before (4). This
means that any uses that require liveness of %0 must be before (4) and thus no
use-after-frees can result from removing (3) since we are not shrinking the
underlying object's lifetime. Lets consider a different case where (3) and (4)
are swapped.
```
%0 = ...
%1 = copy_value %0 (1)
apply %guaranteedUser(%0) (2)
apply %cviConsumer(%1) (4)
destroy_value %0 (3)
```
In this case, since there aren't any liveness requiring uses of %0 in between
(4) and (3), we can still perform our transform. But what if there was a
liveness requiring user in between (4) and (3). To analyze this, lets swap (2)
and (4), yielding:
```
%0 = ...
%1 = copy_value %0 (1)
apply %cviConsumer(%1) (4)
apply %guaranteedUser(%0) (2)
destroy_value %0 (3)
```
In this case, if we were to perform our transform, we would get a use-after-free
due do the transform shrinking the lifetime of the underlying object here from
ending at (3) to ending at (4):
```
%0 = ...
apply %cviConsumer(%1) (4)
apply %guaranteedUser(%0) (2) // *kaboom*
```
So clearly, if (3) is after (4), clearly, we need to know that there aren't any
liveness requiring uses in between them to be able to perform this
optimization. But is this enough? Turns out no. There are two further issues
that we must consider:
1. If (4) is forwards owned ownership, it is not truly "consuming" the
underlying value in the sense of actually destroying the underlying value. This
can be worked with by using the LiveRange abstraction. That being said, this PR
is meant to contain simple transforms that do not need to use LiveRange. So, we
bail if we see a forwarding instruction.
2. At the current time, we may not be able to find all normal uses since all of
the instructions that are interior pointer constructs (e.x.: project_box) have
not been required yet to always be guarded by borrows (the eventual end
state). Thus we can not shrink lifetimes in general safely until that piece of
work is done.
Given all of those constraints, we only handle cases here where (3) is strictly
before (4) so we know 100% we are not shrinking any lifetimes. This effectively
is causing our correctness to rely on SILGen properly scoping lifetimes. Once
all interior pointers are properly guarded, we will be able to be more
aggressive here.
With that in mind, we perform this transform given the following conditions
noting that this pattern often times comes up around return values:
1. If the consuming user is a return inst. In such a case, we know that the
destroy_value must be before the actual return inst.
2. If the consuming user is in the exit block and the destroy_value is not.
3. If the consuming user and destroy_value are in the same block and the
consuming user is strictly later in that block than the destroy_value.
In all of these cases, we are able to optimize without the need for LiveRanges.
I am going to add support for this in a subsequent commit.
I also added a comment to getAllBorrowIntroducingValues(...) that explained the
situations where one could have multiple borrow introducing values:
1. True phi arguments.
2. Aggregate forming instructions.
This patch implements movable guaranteed scopes in ossa. This pattern is
currently not generated anywhere in the compiler, but my hope is to begin
emitting these in SemanticARCOpts. The idea is that these model true phi nodes
and thus can be used to fuse multiple guaranteed scopes into one using br
instructions. This is treated similarly to how owned instructions are forwarded
through /all/ terminators. This will enable us to use the SILSSAUpdater with
guaranteed arguments as well as enable the expression of sets of borrow scopes
that minimally jointly-dominate a guaranteed argument. This will enable us to
express +0 merge points like the following:
```
bb1:
%0a = begin_borrow %0 : $Klass
br bb3(%0a : $Klass)
bb2:
%1a = load_borrow %1 : $*Klass
br bb3(%1a : $Klass)
bb3(%2 : @guaranteed $Klass)
...
end_borrow %2 : $Klass
```
I describe below what the semantics of guaranteed block arguments were
previously, what they are now, and a little bit of interesting things from a
semantic perspective around implicit sub-scope users.
Before this patch in ossa, guaranteed block arguments had two different sets of
semantics:
1. Given a checked_cast_br or a switch_enum, the guaranteed block argument was
treated like a forwarding instruction. As such, the guaranteed argument's did
not require an end_borrow and its uses were validated as part of the use list
of the switch_enum/checked_cast_br operand's borrow introducer. It also was
not classified as a BorrowScopeValueIntroducer since it was not introducing a
new scope.
2. Given any other predecessor terminator, we treated the guaranteed argument as
a complete sub-scope of its incoming values. Thus we required the guaranteed
argument to have its lifetime eneded by an end_borrow and that all incoming
values of the guaranteed argument to come from a borrow introducer whose set
of jointly post-dominating end_borrows also jointly post-dominates the set of
end_borrows associated with the guaranteed argument itself. Consider the
following example:
```
bb0:
%1 = begin_borrow %foo : $Foo // (1)
%2 = begin_borrow %foo2 : $Foo2 // (2)
cond_br ..., bb1, bb2
bb1:
br bb3(%1 : $Foo)
bb2:
br bb3(%2 : $Foo)
bb3(%3 : @guaranteed $Foo)
...
end_borrow %3 : $Foo // (3)
end_borrow %2 : $Foo // (4)
end_borrow %1 : $Foo // (5)
...
```
Notice how due to SSA, (1) and (2) must dominate (4) and (5) and thus must
dominate bb3, preventing the borrows from existing within bb1, bb2.
This dominance property is actively harmful to expressivity in SIL since it
means that guaranteed arguments can not be used to express (without contortion)
sil code patterns where an argument is jointly-dominated by a minimal set of
guaranteed incoming values. For instance, consider the following SIL example:
```
bb0:
cond_br ..., bb1, bb2
bb1:
%0 = load [copy] %globalAddr : $Foo
br bb3(%0 : $Foo)
bb2:
%1 = copy_value %guaranteedFunctionArg : $Foo
br bb3(%1 : $Foo):
bb3(%2 : @owned $Foo):
apply %useFoo(%2)
destroy_value %2 : $Foo
```
As a quick proof: Assume the previous rules for guaranteed arguments. Then to
promote the load [copy] -> load_borrow and the copy_value to a begin_borrow, we
would need to place an end_borrow in bb3. But neither bb1 or bb2 dominates bb3,
so we would violate SSA dominance rules.
To enable SIL to express this pattern, we introduce a third rule for terminator
in ossa that applies only to branch insts. All other branches that obeyed the
previous rules (cond_br), still follow the old rule. This is not on purpose, I
am just being incremental and changing things as I need to. Specifically,
guaranteed arguments whose incoming values are defined by branch instructions
now act as a move on guaranteed values. The intuition here is that these
arguments are acting as true phis in an SSA sense and thus are just new names
for the incoming values. This implies since it is just a new name (not a
semantic change) that the guaranteed incoming value's guaranteed scopes should
be fused into one scope. The natural way to model this is by treating branch
insts as consuming guaranteed values. This then lets us express the example
above without using copies as follows:
```
bb0:
cond_br ..., bb1, bb2
bb1:
%0 = load_borrow %globalAddr : $Foo
br bb3(%0 : $Foo) // consumes %0 and acts as %0's end_borrow.
bb2:
// We need to introduce a new begin_borrow here since function
// arguments are required to never be consumed.
%1 = begin_borrow %guaranteedFunctionArg : $Foo
br bb3(%1 : $Foo) // consumes %1 and acts as %1's end_borrow
// %2 continues the guaranteed scope of %0, %1. This time fused with one name.
bb3(%2 : @guaranteed $Foo):
apply %useFoo(%2)
// End the lifetime of %2 (which implicitly ends the lifetime of %0, %1).
end_borrow %2 : $Foo
...
```
The main complication for users is that now when attempting to discover the set
of implicit users on an owned or guaranteed value caused by their usage as an
argument of a borrow introducer like begin_borrow. For those who are unaware, a
begin_borrow places an implicit requirement on its parent value that the parent
value is alive for the entire part of the CFG where this begin_borrow is
live. Previously, one could just look for the end_borrows of the
begin_borrow. Now one must additionally look for consuming branch insts. This is
because the original value that is being borrowed from must be alive over the
entire web of guaranteed values. That is the entire web of guaranteed values act
as a liveness requirement on the begin_borrow's operand.
The way this is implemented is given a use that we are validating, if the use is
a BorrowScopeOperand (1), we see if the borrow scope operand consumes the given
guaranteed scope and forwards it into a borrow scope introducer. If so, we add
the list of consuming uses of the borrow scope introducer to the worklist to
visit and then iterate.
In order to avoid working with cycles, for now, the ownership verifier bans
liveness requiring uses that have cycles in them. This still allows us to have
loop carried guaranteed values.
(1) A BorrowScopeOperand is a concept that represents an operand to a SIL
instruction that begins a guaranteed scope of some sort. All BorrowScopeOperand
are thus at a minimum able to compute a compile time the static region in which
they implicitly use their operands. NOTE: We do not require the scope to be
represented as a SILValue in the same function.
We achieve some nice benefit by introducing this. Specifically:
1. We can optimize the pattern I mentioned above. This is a common pattern in
many frameworks that want to return a default object if a computation fails
(with the default object usually being some sort of global or static
var). This will let us optimize that case when the global is a let global.
2. The SSA Updater can now be used with guaranteed values without needing to
introduce extra copies. This will enable predictable mem opts to introduce
less copies and for semantic arc opts to optimize the remaining copies that
PMO exposes but does not insert itself.
rdar://56720519
A branch propagated user that isn't a cond_br is layout compatible with a
SILInstruction *. This helper function converts from ArrayRef<SILInstruction *>
-> ArrayRef<BranchPropagatedUser> but also in asserts builds checks that our
invariant (namely all of the 'SILInstruction *' are not cond_br.
All non cond_br SILInstructions are layout compatible with BranchPropagatedUser
since BPU just stores a PointerIntPair that leaves its low bits as zero unless
one adds a cond_br. Since in these cases, the SILInstructions are all not
cond_br, we can use this alternative API.
I also added some asserts to validate that the assumption that all such
SILInstructions are not cond_br is respected.
By convention, most structs and classes in the Swift compiler include a `dump()` method which prints debugging information. This method is meant to be called only from the debugger, but this means they’re often unused and may be eliminated from optimized binaries. On the other hand, some parts of the compiler call `dump()` methods directly despite them being intended as a pure debugging aid. clang supports attributes which can be used to avoid these problems, but they’re used very inconsistently across the compiler.
This commit adds `SWIFT_DEBUG_DUMP` and `SWIFT_DEBUG_DUMPER(<name>(<params>))` macros to declare `dump()` methods with the appropriate set of attributes and adopts this macro throughout the frontend. It does not pervasively adopt this macro in SILGen, SILOptimizer, or IRGen; these components use `dump()` methods in a different way where they’re frequently called from debugging code. Nor does it adopt it in runtime components like swiftRuntime and swiftReflection, because I’m a bit worried about size.
Despite the large number of files and lines affected, this change is NFC.
