findInnerTransitiveUsesForAddress was incorrectly returning true for
pointer escapes.
Introduce enum AddressUseKind { NonEscaping, PointerEscape, Unknown };
Clients need to handle each of these cases differently.
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
A place to define invariants on OperandOwnership that passes can rely
on for convenience.
Starting with a simple invariant the OperandOwnership::Borrow is a
valid BorrowingOperand.
This is the initial version of a buildable SIL definition in libswift.
It defines an initial set of SIL classes, like Function, BasicBlock, Instruction, Argument, and a few instruction classes.
The interface between C++ and SIL is a bridging layer, implemented in C.
It contains all the required bridging data structures used to access various SIL data structures.
This should be used instead of isLifetimeEnding wherever the code
assumes an owned value is consumed.
isLifetimeEnding should only be used when the code is expected to
handle both owned and guaranteed values.
The API for values is on the ValueBase. SILValue is supposed to be a
pointer-like wrapper class. Accessing a value's API is always done as
'value->api()'. The ValueBase subclasses, like SingleValueInstruction,
need to inherit the API.
I didn't have time to fix all the cases of value.isOwnershipKind()
throughout the code.
This removes the ambiguity when casting from a SingleValueInstruction to SILNode, which makes the code simpler. E.g. the "isRepresentativeSILNode" logic is not needed anymore.
Also, it reduces the size of the most used instruction class - SingleValueInstruction - by one pointer.
Conceptually, SILInstruction is still a SILNode. But implementation-wise SILNode is not a base class of SILInstruction anymore.
Only the two sub-classes of SILInstruction - SingleValueInstruction and NonSingleValueInstruction - inherit from SILNode. SingleValueInstruction's SILNode is embedded into a ValueBase and its relative offset in the class is the same as in NonSingleValueInstruction (see SILNodeOffsetChecker).
This makes it possible to cast from a SILInstruction to a SILNode without knowing which SILInstruction sub-class it is.
Casting to SILNode cannot be done implicitly, but only with an LLVM `cast` or with SILInstruction::asSILNode(). But this is a rare case anyway.
This removes the ambiguity when casting from a SingleValueInstruction to SILNode, which makes the code simpler. E.g. the "isRepresentativeSILNode" logic is not needed anymore.
Also, it reduces the size of the most used instruction class - SingleValueInstruction - by one pointer.
Conceptually, SILInstruction is still a SILNode. But implementation-wise SILNode is not a base class of SILInstruction anymore.
Only the two sub-classes of SILInstruction - SingleValueInstruction and NonSingleValueInstruction - inherit from SILNode. SingleValueInstruction's SILNode is embedded into a ValueBase and its relative offset in the class is the same as in NonSingleValueInstruction (see SILNodeOffsetChecker).
This makes it possible to cast from a SILInstruction to a SILNode without knowing which SILInstruction sub-class it is.
Casting to SILNode cannot be done implicitly, but only with an LLVM `cast` or with SILInstruction::asSILNode(). But this is a rare case anyway.
Sometimes when you are working with SILValues, you need a "next" insertion
point. This creates a problem with the SILValue API since even though one can
get an instruction or an insertion point for a value, to find the appropriate
next instruction one needs to pierce through the API and see if one has a
SILArgument or SILInstruction breaking the whole point of abstraction. The
specific problem here is that a SILArgument's "next instruction" is the first
element of the block (that is ValueBase::getDefiningInsertionPoint()) and
SILInstruction's "next instruction" is
std::next(ValueBase::getDefiningInsertionPoint()). This new
API (ValueBase::getNextInstruction()) handles this case for the compiler writer
and eliminates unnecessary code contortions.
I also did a little cleanup where I moved a doxygen comment from a near by a
const_casting trampoline method to the method that the trampoline called (see
getDefiningInsertionPoint()).
Now that OperandOwnership determines the operand constraints, it
doesn't make sense to distinguish between Borrow and NestedBorrow at
this level. We want these uses to automatically convert between the
nested/non-nested state as the operand's ownership changes. The use
does not need to impose any constraint on the ownership of the
incoming value.
For algorithms that need to distinguish nested borrows, it's still
trivial to do so.
A NonUse operand does not use the value itself, so it ignores
ownership and does not require liveness. This is for operands that
represent dependence on a type but are not actually passed the value
of that type (e.g. they may refer an open_existential). This could be
used for other dependence-only operands in the future.
A TrivialUse operand has undefined ownership semantics aside from
requiring liveness. Therefore it is only legal to pass the use a value
with ownership None (a trivial value). Contrast this with things like
InstantaneousUse or BitwiseEscape, which just don't care about
ownership (i.e. they have no ownership semantics.
All of the explicitly listed operations in this category require
trivially typed operands. So the meaning is obvious to anyone
adding SIL operations and updating OperandOwnership.cpp, without
needing to decifer the value ownership kinds.
Clarify which uses are allowed to take Unowned values. Add enforcement
to ensure that Unowned values are not passed to other uses.
Operations that can take unowned are:
- copy_value
- apply/return @unowned argument
- aggregates (struct, tuple, destructure, phi)
- forwarding operations that are arbitrary type casts
Unowned values are currently borrowed within ObjC deinitializers
materialized by the Swift compiler. This will be banned as soon as
SILGen is fixed.
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 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 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 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.
SILType and SILDeclRef do not actually need anything from SIL/*.h. Also,
a few dependencies can be pushed out of the headers into cpp files to
speed up incremental rebuilds.
This verifier validates that while a load_borrow's value is live (that is until
it is invalidated by its end_borrow), the load_borrow's address source is never
written to.
The reason why this verifier is especially important now is that I am adding
many optimizations that convert `load [copy]` -> `load_borrow`. If that
optimization messes up, we break this invariant [in fact, an optimization I am
working on right now violated the invariant =--(]. So by adding this verifier I
am checking that semantic arc opts doesn't break it as well as eliminating any
other such bugs from the compiler (in the future).
This is just better information to have since one wants to not only know the
instruction, but also the specific value used on the instruction since behavior
can vary depending upon that. The operand is what ties the two together so it is
a natural fit.
Now that this is done, I am going to work on refactoring out converting a
LiveRange from @owned -> @guaranteed. It will be a consuming operation using a
move operator since once the transformation has completed, the LiveRange no
longer exists.
I need this refactored functionality since I am going to need it when
eliminating phi-webs.
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.
This just provides a higher level of abstraction around determining if an
operand consumes its associated value needing to touch the ownership kind
map/etc.
I also refactored parts of the code base where it made sense to use this instead
of messing with the ownership kind map itself.
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.
