We were not using the primary benefits of an intrusive list, namely the
ability to insert or remove from the middle of the list, so let's switch
to a plain vector. This also avoids linked-list pointer chasing.
This fixes a correctness issue.
The begin_cow_mutation instruction has dependencies with instructions which retain the buffer operand.
This prevents optimizations from moving begin_cow_mutation instructions across such retain instructions.
`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.
Support differentiation of `is` and `as?` operators.
These operators lower to branching cast SIL instructions, requiring control
flow differentiation support.
Resolves SR-12898.
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.
If the only use of an upcast, unchecked_ref_cast or end_cow_mutation is a destroy/release, just destroy the operand and remove the cast/end_cow_mutation.
This simplifies the handling of the subdirectories in the SIL and
SILOptimizer paths. Create individual libraries as object libraries
which allows the analysis of the source changes to be limited in scope.
Because these are object libraries, this has 0 overhead compared to the
previous implementation. However, string operations over the filenames
are avoided. The cost for this is that any new sub-library needs to be
added into the list rather than added with the special local function.
* a new [immutable] attribute on ref_element_addr and ref_tail_addr
* new instructions: begin_cow_mutation and end_cow_mutation
These new instructions are intended to be used for the stdlib's COW containers, e.g. Array.
They allow more aggressive optimizations, especially for Array.
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
This became necessary after recent function type changes that keep
substituted generic function types abstract even after substitution to
correctly handle automatic opaque result type substitution.
Instead of performing the opaque result type substitution as part of
substituting the generic args the underlying type will now be reified as
part of looking at the parameter/return types which happens as part of
the function convention apis.
rdar://62560867
Move differentiation-related SILOptimizer files to
{include/swift,lib}/SILOptimizer/Differentiation/.
This reduces directory nesting and gathers files together.
Potentially source breaking: SR-11700 Diagnose exclusivity violations
with Dictionary.subscript._modify:
Exclusivity violations within code that computes the `default`
argument during Dictionary access are now diagnosed.
```swift
struct Container {
static let defaultKey = 0
var dictionary = [defaultKey:0]
mutating func incrementValue(at key: Int) {
dictionary[key, default: dictionary[Container.defaultKey]!] += 1
}
}
error: overlapping accesses to 'self.dictionary', but modification requires exclusive access; consider copying to a local variable
dictionary[key, default: dictionary[Container.defaultKey]!] += 1
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
note: conflicting access is here
dictionary[key, default: dictionary[Container.defaultKey]!] += 1
~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
```
This reworks the logic so that four problems end up being fixed:
Fixes three problems related to coroutines:
(1) DiagnoseStaticExclusivity must consider begin_apply as a user of accessed variables. This was an undefined behavior hole in the diagnostics.
(2) AccessedSummaryAnalysis should consider begin_apply as a user of accessed arguments. This does not show up in practice because coroutines don't capture things.
(3) AccessedSummaryAnalysis must consider begin_apply a valid user of
noescape closures.
And fixes one problem related to resilience:
(4) AccessedSummaryAnalysis must conservatively consider arguments to external functions.
Fixes <rdar://problem/56378713> Investigate why AccessSummaryAnalysis is crashing
MSVC does not realize that the switch is exhaustive and requires that
the path is explicitly marked as unreachable. This silences the C4715
warning ("not all control paths return a value").
Add a private scratch context to the ASTContext and allow IntrinsicInfo sole access to it so it can allocate attributes into it. This removes the final dependency on the global context.
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
Tuple, Struct, and Enum MetatypesTypes have a single value. In this
case, replace metatype instructions with arguments of the same
MetatypeType to enable downstream CSE and SILCombines.
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.
In case an unchecked_addr_cast is used to convert between pointer and non-pointer, we missed some escaping values.
This can be the case when using C unions.
https://bugs.swift.org/browse/SR-12427
rdar://problem/60983997
If EscapeAnalysis verification runs on unreachable code, it asserts
with "Missing escape connection graph mapping" because the connection
graph builder only runs on reachable blocks.
Add a ReachableBlocks utility and use it during verification.
Fixes <rdar://problem/60373501> EscapeAnalysis crashes with CFG with
unreachable blocks
Fixes <rdar://60046018> assert: (v->getType().isAddress())
in getAccessedAddress.
MemBehavior compares known memory accesses with some arbitrary value,
which may not be an address. However, we should not call utilities
that work on accessed addresses with an arbitrary value.
This assert is a result of very recent changes to gradually make
memory access utilities more type safe and introduce the concept of a
canonical accessed address. In the future, we may even have a wrapper
type for such a thing. In the SIL optimizer, there are several
different notions of what constitutes the base of a memory
access. Mismatches can lead to subtle bugs.
EscapeAnalysis::mayReleaseContent was recently changed to assert on
address-type arguments. The assert ensures that callers directly pass
the reference being released. If the caller does not have the precise
reference being released, it opens the door to bugs in which the
EscapeAnalysis query looks up the wrong connection graph node.
The original AliasAnalysis logic is just a workaround for the fact
that we don't have information about which builtin's may release
reference-type arguments.
Fixes <rdar://60190962> Escape analysis crashes with "an address is
never a reference" error with -O -thread=sanitize
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.
Change the connection graph builder to map an existential address and
its opened address onto the same node.
Fixes <rdar://59559805> miscompile; use-after-free
Immediate bug: EscapeAnalysis::mayReleaseContent incorrectly returns
'false' when comparing a store into an existential's value with a
release of the existential.
How this was exposed: mayReleaseContent was made more aggressive so
that only the connection graph node representing the released object
is considered to be "released". This fails for existentials because a
separate connection graph node is created for the value within the
existential.
This is just one manifestation of a broader bug. Representing an
existential as two logically distinct objects could also result in
incorrect escaping information and incorrect alias analysis. Note that
copying directly into an existential address and storing into the
opened value in fact modify the same memory. Furthermore, when opening
an existential, no local reference count is used to keep the opened
value "alive" independent from the existential (this is another
assumption made by mayReleaseContent). This is always how existentials
were represented in the connection graph, but issues had never been
exposed.
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.
The most recently added verification exposed an issue where the code
pattern-matches an array.uninitialized call. The pattern matching does
not handle multiple tuple_extracts but the API returned "success" in
some of those cases.
Fixes the verifier assert when building ImagePicker.
Noticed via code inspection. This could potentially miscompile, but we
haven't seen that happen to my knowledge.
Both value_to_bridge_object and strong_copy_XXX need to escape their
resulting value.
The implementation seemed to assume that it is conservatively correct
simply to avoid building a connection graph node for an value. This is
*not* true. Any value that has a pointer type requires a connection
graph node. The only way to be conservative is to create the value
node *and* point it to an escaping content node.
We can always declare that certain special types are not considered
pointer types, but then we need to handle all conversions from those
types to pointer types by escaping the resulting
pointer. BridgeObjects are often on the performance-critical path.
Consistently handle base and derived pointers.
Consistently avoid creating nodes for undef, which breaks
verification.
Be more precise about creating the node based on the derived pointer
type.
Remove a few extraneous helpers.
Fixes <rdar://58445744> swiftc assert during EscapeAnalysis
verification: (EA->isPointer(Nd->mappedValue)), function verify
Defer edges should always point to the more specific SSA value. For
example, the contents of a memory location point to the values stored
in that locations. Tuples point to their elements. BBArgs point to
their source operands. Likewise, array objects should point to their
exposed unsafe pointer (which is effectively a value stored in the
array object). I'm not sure why the defer edges were reversed in the
first place, but it was always confusing me.
Noticed by code inspection during debugging.
Iterator invalidaton could occur because two types of edges, which are
handled independently, actually share the same phyical list.
Fix the visitor utility that iterates over defer edges to be robust
for visitors that change the pointsTo edge. Use a temporary vector to
be safe.
