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.
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.
When instructions are changed within a pass in a way that affects subsequent alias queries in the same pass run,
their alias analysis information must be invalidated.
Otherwise it can result in miscompiles and/or invalid SIL.
rdar://71924430
to check for improperly nested '@_semantic' functions.
Add a missing @_semantics("array.init") in ArraySlice found by the
diagnostic.
Distinguish between array.init and array.init.empty.
Categorize the types of semantic functions by how they affect the
inliner and pass pipeline, and centralize this logic in
PerformanceInlinerUtils. The ultimate goal is to prevent inlining of
"Fundamental" @_semantics calls and @_effects calls until the late
pipeline where we can safely discard semantics. However, that requires
significant pipeline changes.
In the meantime, this change prevents the situation from getting worse
and makes the intention clear. However, it has no significant effect
on the pass pipeline and inliner.
Add AccesssedStorage::compute and computeInScope to mirror AccessPath.
Allow recovering the begin_access for Nested storage.
Adds AccessedStorage.visitRoots().
Things that have come up recently but are somewhat blocked on this:
- Moving AccessMarkerElimination down in the pipeline
- SemanticARCOpts correctness and improvements
- AliasAnalysis improvements
- LICM performance regressions
- RLE/DSE improvements
Begin to formalize the model for valid memory access in SIL. Ignoring
ownership, every access is a def-use chain in three parts:
object root -> formal access base -> memory operation address
AccessPath abstracts over this path and standardizes the identity of a
memory access throughout the optimizer. This abstraction is the basis
for a new AccessPathVerification.
With that verification, we now have all the properties we need for the
type of analysis requires for exclusivity enforcement, but now
generalized for any memory analysis. This is suitable for an extremely
lightweight analysis with no side data structures. We currently have a
massive amount of ad-hoc memory analysis throughout SIL, which is
incredibly unmaintainable, bug-prone, and not performance-robust. We
can begin taking advantage of this verifably complete model to solve
that problem.
The properties this gives us are:
Access analysis must be complete over memory operations: every memory
operation needs a recognizable valid access. An access can be
unidentified only to the extent that it is rooted in some non-address
type and we can prove that it is at least *not* part of an access to a
nominal class or global property. Pointer provenance is also required
for future IRGen-level bitfield optimizations.
Access analysis must be complete over address users: for an identified
object root all memory accesses including subobjects must be
discoverable.
Access analysis must be symmetric: use-def and def-use analysis must
be consistent.
AccessPath is merely a wrapper around the existing accessed-storage
utilities and IndexTrieNode. Existing passes already very succesfully
use this approach, but in an ad-hoc way. With a general utility we
can:
- update passes to use this approach to identify memory access,
reducing the space and time complexity of those algorithms.
- implement an inexpensive on-the-fly, debug mode address lifetime analysis
- implement a lightweight debug mode alias analysis
- ultimately improve the power, efficiency, and maintainability of
full alias analysis
- make our type-based alias analysis sensistive to the access path
...and avoid reallocation.
This is immediately necessary for LICM, in addition to its current
uses. I suspect this could be used by many passes that work with
addresses. RLE/DSE should absolutely migrate to it.
1. Do a better alias analysis for "function-local" objects, like alloc_stack and inout parameters
2. Fully support try_apply and begin/end/abort_apply
So far we fully relied on escape analysis. But escape analysis has some shortcomings with SIL address-types.
Therefore, handle two common cases, alloc_stack and inout parameters, with alias analysis.
This gives better results.
The biggest change here is to do a quick check if the address escapes via an address_to_pointer instructions.
A key concept in late ARC optimization is "RC Identity". In short, a result of
an instruction is rc-identical to an operand of the instruction if one can
safely move a retain (release) from before the instruction on the result to one
after on the operand without changing the program semantics. This creates a
simple model where one can work on equivalence classes of rc-identical values
(using a dominating definition generally as the representative) and thus
optimize/pair retain, release.
When preparing for late ARC optimization, the optimizer will normalize aggregate
ARC operations (retain_value, release_value) into singular strong_retain,
strong_release operations on leaf types of the aggregate that are
non-trivial. As an example, a retain_value on a KlassPair would be canonicalized
into two strong_retain, one for the lhs and one for the rhs. When this is done,
the optimizer generally just creates new struct_extract at the point where the
retain is. In such a case, we may have that the debug_value for the underlying
type is actually on a reformed aggregate whose underlying parts we are
retaining:
```
bb0(%0 : $Builtin.NativeObject):
strong_retain %0
%1 = struct $Array(%0 : $Builtin.NativeObject, ...)
debug_value %1 : $Array, ...
```
By looking through RC identical uses, we can handle a large subset of these
cases without much effort: ones were there is a single owning pointer like Array.
To handle more complex cases we would have to calculate an inverse access path needed to get
back to our value and somehow deal with all of the complexity therein (I am sure
we can do it I just haven't thought through all of the details).
The only interesting behavior that this results in is that when we emit
diagnostics, we just use the rc-identical transitive use debug_value's name
without a projection path. This is because the source location associated with
that debug_value is with a separate value that is rc-identical to the actual
value that we visited during our opt-remark traversal up the def-use
graph. Consider the following example below, noting the comments that show in
the SIL itself what I attempted to explain above.
```
struct KlassPair {
var lhs: Klass
var rhs: Klass
}
struct StateWithOwningPointer {
var state: TrivialState
var owningPtr: Klass
}
sil @theFunction : $@convention(thin) () -> () {
bb0:
%0 = apply %getKlassPair() : $@convention(thin) () -> @owned KlassPair
// This debug_value's name can be combined...
debug_value %0 : $KlassPair, name "myPair"
// ... with the access path from the struct_extract here...
%1 = struct_extract %0 : $KlassPair, #KlassPair.lhs
// ... to emit a nice diagnostic that 'myPair.lhs' is being retained.
strong_retain %1 : $Klass
// In contrast in the case below, we rely on looking through rc-identity uses
// to find the debug_value. In this case, the source info associated with the
// debug_value (%2) is no longer associated with the underlying access path we
// have been tracking upwards (%1 is in our access path list). Instead, we
// know that the debug_value is rc-identical to whatever value we were
// originally tracking up (%1) and thus the correct identifier to use is the
// direct name of the identifier alone (without access path) since that source
// identifier must be some value in the source that by itself is rc-identical
// to whatever is being manipulated. Thus if we were to emit the access path
// here for na rc-identical use we would get "myAdditionalState.owningPtr"
// which is misleading since ArrayWrapperWithMoreState does not have a field
// named 'owningPtr', its subfield array does. That being said since
// rc-identity means a retain_value on the value with the debug_value upon it
// is equivalent to the access path value we found by walking up the def-use
// graph from our strong_retain's operand.
%0a = apply %getStateWithOwningPointer() : $@convention(thin) () -> @owned StateWithOwningPointer
%1 = struct_extract %0a : $StateWithOwningPointer, #StateWithOwningPointer.owningPtr
strong_retain %1 : $Klass
%2 = struct $Array(%0 : $Builtin.NativeObject, ...)
%3 = struct $ArrayWrapperWithMoreState(%2 : $Array, %moreState : MoreState)
debug_value %2 : $ArrayWrapperWithMoreState, name "myAdditionalState"
}
```
* Remove NewInsts from ARCSequenceOpts
* Remove more instances of InsertPts
* Address comments from #33504
* Make bottom up loop traversal simpler. Use better apis
* Update LoopRegion printer with more info
For use outside access enforcement passes.
Add isUniquelyIdentifiedAfterEnforcement.
Rename functions for clarity and generality.
Rename isUniquelyIdentifiedOrClass to isFormalAccessBase.
Rename findAccessedStorage to identifyFormalAccess.
Rename findAccessedStorageNonNested to findAccessedStorage.
Part of generalizing the utility for use outside the access
enforcement passes.
`DifferentiableFunctionInst` now stores result indices.
`SILAutoDiffIndices` now stores result indices instead of a source index.
`@differentiable` SIL function types may now have multiple differentiability
result indices and `@noDerivative` resutls.
`@differentiable` AST function types do not have `@noDerivative` results (yet),
so this functionality is not exposed to users.
Resolves TF-689 and TF-1256.
Infrastructural support for TF-983: supporting differentiation of `apply`
instructions with multiple active semantic results.
Used to "finalize" an array literal. It's not used, yet. So this is NFC.
Also handle the "array.finalize_intrinsic" function in various array specific optimizations.
The PassManager should transform all functions in bottom up order.
This is necessary because when optimizations like inlining looks at the
callee function bodies to compute profitability, the callee functions
should have already undergone optimizations to get better profitability
estimates.
The PassManager builds its function worklist based on bottom up order
on initialization. However, newly created SILFunctions due to
specialization etc, are simply appended to the function worklist. This
can cause us to make bad inlining decisions due to inaccurate
profitability estimates. This change now updates the function worklist such
that, all the callees of the newly added SILFunction are proccessed
before it by the PassManager.
Fixes rdar://52202680
FSO can handle self-recursive calls.
But this only works if the result of the self-recursive call is actually returned and not used otherwise.
The check for this was missing.
https://bugs.swift.org/browse/SR-12677
rdar://problem/62895040
-sil-verify-all flag will verify analyses before and after a pass to
confirm correct invalidations. But if an analysis was never
constructed or invalidated as per current pass order,
it may never detect insufficient invalidations.
-sil-verify-force-analysis will force construct an analysis so that we
can better check for insufficient invalidations.
It is also terribly slow compared to -sil-verify-all.
For functions which results in > 10000 nodes, just bail and don't compute the connection graph.
The node merging algorithm is quadratic and can result in significant compile times for very large functions.
rdar://problem/56268570
Differentiable activity analysis is a dataflow analysis which marks values in
a function as varied, useful, or active (both varied and useful).
Only active values need a derivative.
This is in prepration for other bug fixes.
Clarify the SIL utilities that return canonical address values for
formal access given the address used by some memory operation:
- stripAccessMarkers
- getAddressAccess
- getAccessedAddress
These are closely related to the code in MemAccessUtils.
Make sure passes use these utilities consistently so that
optimizations aren't defeated by normal variations in SIL patterns.
Create an isLetAddress() utility alongside these basic utilities to
make sure it is used consistently with the address corresponding to
formal access. When this query is used inconsistently, it defeats
optimization. It can also cause correctness bugs because some
optimizations assume that 'let' initialization is only performed on a
unique address value.
Functional changes to Memory Behavior:
- An instruction with side effects now conservatively still has side
effects even when the queried value is a 'let'. Let values are
certainly sensitive to side effects, such as the parent object being
deallocated.
- Return the correct MemBehavior for begin/end_access markers.
Changes:
* Allow optimizing partial_apply capturing opened existential: we didn't do this originally because it was complicated to insert the required alloc/dealloc_stack instructions at the right places. Now we have the StackNesting utility, which makes this easier.
* Support indirect-in parameters. Not super important, but why not? It's also easy to do with the StackNesting utility.
* Share code between dead closure elimination and the apply(partial_apply) optimization. It's a bit of refactoring and allowed to eliminate some code which is not used anymore.
* Fix an ownership problem: We inserted copies of partial_apply arguments _after_ the partial_apply (which consumes the arguments).
* When replacing an apply(partial_apply) -> apply and the partial_apply becomes dead, avoid inserting copies of the arguments twice.
These changes don't have any immediate effect on our current benchmarks, but will allow eliminating curry thunks for existentials.
semantics attribute that is used by the top-level array initializer (in ArrayShared.swift),
which is the entry point used by the compiler to initialize array from array literals.
This initializer is early-inlined so that other optimizations can work on its body.
Fix DeadObjectElimination and ArrayCOWOpts optimization passes to work with this
semantics attribute in addition to "array.uninitialized", which they already use.
Refactor mapInitializationStores function from ArrayElementValuePropagation.cpp to
ArraySemantic.cpp so that the array-initialization pattern matching functionality
implemented by the function can be reused by other optimizations.
setPointsToEdge should assert that its target isn't already merged,
but now that we batch up multiple merge requests, it's fine to allow
the target to be scheduled-for-merge.
Many assertions have been recently added and tightened in order to
"discover" unexpected cases. There's nothing incorrect about how these
cases were handled, but they lack unit tests. In this case I still
haven't been able to reduce a test case. I'm continuing to work on
it, but don't want to further delay the fix.
