This instructions ensures that all instructions, which need to run on the specified executor actually run on that executor.
For details see the description in SIL.rst.
Add AccesssedStorage::compute and computeInScope to mirror AccessPath.
Allow recovering the begin_access for Nested storage.
Adds AccessedStorage.visitRoots().
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.
`get_async_continuation[_addr]` begins a suspend operation by accessing the continuation value that can resume
the task, which can then be used in a callback or event handler before executing `await_async_continuation` to
suspend the task.
Since the two ExtInfos share a common ClangTypeInfo, and C++ doesn't let us
forward declare nested classes, we need to hoist out AnyFunctionType::ExtInfo
and SILFunctionType::ExtInfo to the top-level.
We also add some convenience APIs on (AST|SIL)ExtInfo for frequently used
withXYZ methods. Note that all non-default construction still goes through the
builder's build() method.
We do not add any checks for invariants here; those will be added later.
Rename the existing pass to AccessedStorageAnalysisDumper.
AccessedStorage is useful on its own as a utility without the
analysis. We need a way to test the utility itself.
Add test cases for the previous commit that introduced
FindPhiStorageVisitor.
Today unchecked_bitwise_cast returns a value with ObjCUnowned ownership. This is
important to do since the instruction can truncate memory meaning we want to
treat it as a new object that must be copied before use.
This means that in OSSA we do not have a purely ossa forwarding unchecked
layout-compatible assuming cast. This role is filled by unchecked_value_cast.
The ``base_addr_for_offset`` instruction creates a base address for offset calculations.
The result can be used by address projections, like ``struct_element_addr``, which themselves return the offset of the projected fields.
IR generation simply creates a null pointer for ``base_addr_for_offset``.
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 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 will make it easier for me with a few further refactors to make the
ownership verifier testing mode emit per function error numbers instead of the
global error number that it is emitting now.
The reason why this is necessary is that today, the verification by
-sil-verify-all causes the errors to be emitted. That verification is done on a
per value level, rather than a per function level, so it is hard to get per
function error numbers without doing unprincipled things like propagating around
state saying what the current function being verified is.
This pass instead will let me make the error counter be per ErrorBuilder which
are created per function.
One thing to be aware of is that this /will/ cause SILValue::verifyOwnership to
not emit any output when the testing flag is enabled. This is to ensure I only
do not get duplicate textual error messages from the SILVerifier.
Add `linear_function` and `linear_function_extract` instructions.
`linear_function` creates a `@differentiable(linear)` function-typed value from
an original function operand and a transpose function operand (optional).
`linear_function_extract` extracts either the original or transpose function
value from a `@differentiable(linear)` function.
Resolves TF-1142 and TF-1143.
Add `differentiable_function` and `differentiable_function_extract`
instructions.
`differentiable_function` creates a `@differentiable` function-typed
value from an original function operand and derivative function operands
(optional).
`differentiable_function_extract` extracts either the original or
derivative function value from a `@differentiable` function.
The differentiation transform canonicalizes `differentiable_function`
instructions, filling in derivative function operands if missing.
Resolves TF-1139 and TF-1140.
In order to allow this, I've had to rework the syntax of substituted function types; what was previously spelled `<T> in () -> T for <X>` is now spelled `@substituted <T> () -> T for <X>`. I think this is a nice improvement for readability, but it did require me to churn a lot of test cases.
Distinguishing the substitutions has two chief advantages over the existing representation. First, the semantics seem quite a bit clearer at use points; the `implicit` bit was very subtle and not always obvious how to use. More importantly, it allows the expression of generic function types that must satisfy a particular generic abstraction pattern, which was otherwise impossible to express.
As an example of the latter, consider the following protocol conformance:
```
protocol P { func foo() }
struct A<T> : P { func foo() {} }
```
The lowered signature of `P.foo` is `<Self: P> (@in_guaranteed Self) -> ()`. Without this change, the lowered signature of `A.foo`'s witness would be `<T> (@in_guaranteed A<T>) -> ()`, which does not preserve information about the conformance substitution in any useful way. With this change, the lowered signature of this witness could be `<T> @substituted <Self: P> (@in_guaranteed Self) -> () for <A<T>>`, which nicely preserves the exact substitutions which relate the witness to the requirement.
When we adopt this, it will both obviate the need for the special witness-table conformance field in SILFunctionType and make it far simpler for the SILOptimizer to devirtualize witness methods. This patch does not actually take that step, however; it merely makes it possible to do so.
As another piece of unfinished business, while `SILFunctionType::substGenericArgs()` conceptually ought to simply set the given substitutions as the invocation substitutions, that would disturb a number of places that expect that method to produce an unsubstituted type. This patch only set invocation arguments when the generic type is a substituted type, which we currently never produce in type-lowering.
My plan is to start by producing substituted function types for accessors. Accessors are an important case because the coroutine continuation function is essentially an implicit component of the function type which the current substitution rules simply erase the intended abstraction of. They're also used in narrower ways that should exercise less of the optimizer.
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.
Add ExecuteSILPipelineRequest which executes a
pipeline plan on a given SIL (and possibly IRGen)
module. This serves as a top-level request for
the SILOptimizer that we'll be able to hang
dependencies off.
The `differentiability_witness_function` instruction looks up a
differentiability witness function (JVP, VJP, or transpose) for a referenced
function via SIL differentiability witnesses.
Add round-trip parsing/serialization and IRGen tests.
Notes:
- Differentiability witnesses for linear functions require more support.
`differentiability_witness_function [transpose]` instructions do not yet
have IRGen.
- Nothing currently generates `differentiability_witness_function` instructions.
The differentiation transform does, but it hasn't been upstreamed yet.
Resolves TF-1141.
For alias analysis query to be generally correct, we need to
effectively merge the escape state and use points for everything in a
defer web.
It was unclear from the current design whether the "escaping" property
applied to the pointer value or its content. The implementation is
inconsistent in how it was treated. It appears that some bugs have
been worked around by propagating forward through defer edges, some
have been worked around by querying the content instead of the
pointer, and others have been worked around be creating fake use
points at block arguments.
If we always simply query the content for escape state and use points,
then we never need to propagate along defer edges. The current code
that propagates escape state along defer edges in one direction is
simply incorrect from the perspective of alias analysis.
One very attractive solution is to merge nodes eagerly without
creating any defer edges, but that would be a much more radical change
even than what I've done here. It would also pose some new issues: how
to resolve the current "node types" when merging and how to deal with
missing content nodes.
This solution of applying escape state to content nodes solves all
these problems without too radical of a change at the expense of
eagerly creating content nodes. (The potential graph memory usage is
not really an issue because it's possible to drastically shrink the
size of the graph anyway in a future commit--I've been able to fit a
node within one cache line). This solution nicely preserves graph
structure which makes it easy to debug and relate to the IR.
Eagerly creating content nodes also solves the missing content node
problem. For example, when querying canEscapeTo, we need to know
whether to look at the escape state for just the pointer value itself,
or also for its content. It may be possible the its content node is
actually part of the same object at the IR level. If the content node
is missing, then we don't know if the object's interior address is not
recognizable/representable or whether we simply never saw an access to
the interior address. We can't simply look at whether the current IR
value happens to be a reference, because that doesn't tell us whether
the graph node may have been merged with a non-reference node or even
with it's own content node. To be correct in general, this query would
need to be extremely conservative. However, if content nodes are
always created for references, then we only need to query the escape
state of a pointer's content node. The content node's flag tells us if
it's an interior node, in which case it will always point to another
content node which also needs to be queried.
and eliminate dead code. This is meant to be a replacement for the utility:
recursivelyDeleteTriviallyDeadInstructions. The new utility performs more aggresive
dead-code elimination for ownership SIL.
This patch also migrates most non-force-delete uses of
recursivelyDeleteTriviallyDeadInstructions to the new utility.
and migrates one force-delete use of recursivelyDeleteTriviallyDeadInstructions
(in IRGenPrepare) to use the new utility.
For alias analysis query to be generally correct, we need to
effectively merge the escape state and use points for everything in a
defer web.
It was unclear from the current design whether the "escaping" property
applied to the pointer value or its content. The implementation is
inconsistent in how it was treated. It appears that some bugs have
been worked around by propagating forward through defer edges, some
have been worked around by querying the content instead of the
pointer, and others have been worked around be creating fake use
points at block arguments.
If we always simply query the content for escape state and use points,
then we never need to propagate along defer edges. The current code
that propagates escape state along defer edges in one direction is
simply incorrect from the perspective of alias analysis.
One very attractive solution is to merge nodes eagerly without
creating any defer edges, but that would be a much more radical change
even than what I've done here. It would also pose some new issues: how
to resolve the current "node types" when merging and how to deal with
missing content nodes.
This solution of applying escape state to content nodes solves all
these problems without too radical of a change at the expense of
eagerly creating content nodes. (The potential graph memory usage is
not really an issue because it's possible to drastically shrink the
size of the graph anyway in a future commit--I've been able to fit a
node within one cache line). This solution nicely preserves graph
structure which makes it easy to debug and relate to the IR.
Eagerly creating content nodes also solves the missing content node
problem. For example, when querying canEscapeTo, we need to know
whether to look at the escape state for just the pointer value itself,
or also for its content. It may be possible the its content node is
actually part of the same object at the IR level. If the content node
is missing, then we don't know if the object's interior address is not
recognizable/representable or whether we simply never saw an access to
the interior address. We can't simply look at whether the current IR
value happens to be a reference, because that doesn't tell us whether
the graph node may have been merged with a non-reference node or even
with it's own content node. To be correct in general, this query would
need to be extremely conservative. However, if content nodes are
always created for references, then we only need to query the escape
state of a pointer's content node. The content node's flag tells us if
it's an interior node, in which case it will always point to another
content node which also needs to be queried.
Otherwise it can happen that e.g. specialization runs between CrossModuleSerializationSetup and serialization, resulting that an inlinable function references a shared function (which doesn't have a public linkage).
The solution is to move serialization right after CrossModuleSerializationSetup. But only do that if cross-module-optimization is enabled (it would be a disruptive change to move serialization in general).
This is the first in a series of patches that reworks
EscapeAnalysis. For this patch, I extracted every change that does not
introduce new features, rewrite logic, or appear to change
functionality.
These cleanups were done in preparation for:
- adding a graph representation for reference counted objects
- rewriting parts to the query logic
- ...which then allows the analysis to safely assume that all
exclusive arguments are unique
- ...which then allows more aggressive optimization of local variables
that don't escape
There are two possible functional changes:
1. getUnderlyingAddressRoot in InstructionUtils now sees through OSSA
instructions: begin_borrow and copy_value
2. The getPointerBase helper in EscapeAnalysis now sees through all of
these reference and pointer casts:
+ case ValueKind::UncheckedRefCastInst:
+ case ValueKind::ConvertFunctionInst:
+ case ValueKind::UpcastInst:
+ case ValueKind::InitExistentialRefInst:
+ case ValueKind::OpenExistentialRefInst:
+ case ValueKind::RawPointerToRefInst:
+ case ValueKind::RefToRawPointerInst:
+ case ValueKind::RefToBridgeObjectInst:
+ case ValueKind::BridgeObjectToRefInst:
+ case ValueKind::UncheckedAddrCastInst:
+ case ValueKind::UnconditionalCheckedCastInst:
+ case ValueKind::RefTo##Name##Inst:
+ case ValueKind::Name##ToRefInst:
This coalesces a whole bunch of nodes together that were just there
because of casts. The existing code was already doing this for one
level of casts, but there was a bug that prevented it from happening
transitively. So, in theory, anything that breaks with this fix could
also break without this fix, but may not have been exposed. The fact
that this analysis coalesces address-to-reference casts at all is what
caused me to spent vast amounts of time debugging any time I tried to
force some structure on the graph via assertions. If it is done at
all, it should be done everywhere consistently to expose issues as
early as possible.
Here is a description of the changes in diff order. If something in
the diff is not listed here, then the code probably just moved around
in the file:
Rename isNotAliasedIndirectParameter to
isExclusiveIndirectParameter. The argument may be aliased in the
caller's scope and it's contents may have already escaped.
Add comments to SILType APIs (isTrivial, isReferenceCounted) that give
answers about the AST type which don't really make sense for address
SILTypes.
Add comments about CGNode's 'Value' field. I spent lots of time
attempting to tighten this down with asserts, but it's only possible
for non-content nodes. For content nodes, the node's value is highly
unpredictable and basically nonsense but needed for debugging.
Add comments about not assuming that the content nodes pointsTo edge
represents physical indirection. This matters when reasoning about
aliasing and it's a tempting assumption to make.
Add a CGNode::mergeProperties placeholder for adding node properties.
Factor out a CGNode::canAddDeferred helper for use later.
Rename `setPointsTo` to `setPointsToEdge` because it actually creates
an edge rather than just setting `pointsTo`.
Add CGNode::getValue() and related helpers to help maintain invariants.
Factor out a `markEscaping` helper.
Clean up the `escapesInsideFunction` helper.
Add node visitor helpers: visitSuccessors, visitDefers. This made is
much easier to prototype utilities.
Add comments to clarify the `pointsTo` invariant. In particular, an
entire defer web may have a null pointsTo for a while.
Add an `activeWorklist` to avoid nasty bugs when composing multiple
helpers that each use the worklist.
Remove the `EA` argument from `getNode`. I ended up needing access to
the `EA` context from the ConnectionGraph many times during
prototyping and passing `this` was all the `getNode` calls was very
silly.
Add graph visitor helpers: backwardTraverse, forwardTraverseDefer,
forwardTraversePointsToEdges, and mayReach for ease in developing new
logic and utilities.
Add isExclusiveArgument helper and distinguish exclusive arguments
from local objects. Confusing these properties could lead to scary
bugs. For example, unlike a local object, an exclusive argument's
contents may still escape even when the content's connection graph
node is non-escaping!
Add isUniquelyIdentified helper when we want to treat exclusive
arguments and local objects uniformly.
getUnderlyingAddressRoot now looks through OSSA instructions.
Rename `getAccessedMemory` to `getDirectlyAccessedMemory` with
comments. This is another dangerous API because it assumes the memory
access to a given address won't touch memory represented by different
graph nodes, but graph edges don't necessarily represent physical
indirection. Further clarify this issue in comments in
AliasAnalysis.cpp.
Factor out a 'findRecursiveRefType' helper from the old
'mayContainReference' for checking whether types may or must contain
references. Support both kinds of queries so the analysis can be
certain when a pointer's content is a physical heap object.
Factor out 'getPointerBase' and 'getPointerRoot' helpers that follow
address projections within what EscapeAnalysis will consider a single
node.
Create a CGNodeWorklist abstraction to safely formalize the worklist
mechanism that's used all over the place. In one place, there were
even two separate independent lists used independently (nodes added to
one list could appear to be in the other list).
The CGNodeMap abstraction did not significantly change, it was just moved.
Added 'dumpCG' for dumping .dot files making it possible to remote debug.
Added '-escapes-enable-graphwriter' option to dump .dot files, since
they are so much more useful than the textual dump of the connection
graph, which lacks node identity!
of OSLogMessage constant evaluable and remove @_transparent annotation
from the methods. Also, improve diagnostics in the OSLogOptimization
pass as now it rely on seeing the appendInterpolation/Literal calls.
https://forums.swift.org/t/improving-the-representation-of-polymorphic-interfaces-in-sil-with-substituted-function-types/29711
This prepares SIL to be able to more accurately preserve the calling convention of
polymorphic generic interfaces by letting the type system represent "substituted function types".
We add a couple of fields to SILFunctionType to support this:
- A substitution map, accessed by `getSubstitutions()`, which maps the generic signature
of the function to its concrete implementation. This will allow, for instance, a protocol
witness for a requirement of type `<Self: P> (Self, ...) -> ...` for a concrete conforming
type `Foo` to express its type as `<Self: P> (Self, ...) -> ... for <Foo>`, preserving the relation
to the protocol interface without relying on the pile of hacks that is the `witness_method`
protocol.
- A bool for whether the generic signature of the function is "implied" by the substitutions.
If true, the generic signature isn't really part of the calling convention of the function.
This will allow closure types to distinguish a closure being passed to a generic function, like
`<T, U> in (*T, *U) -> T for <Int, String>`, from the concrete type `(*Int, *String) -> Int`,
which will make it easier for us to differentiate the representation of those as types, for
instance by giving them different pointer authentication discriminators to harden arm64e
code.
This patch is currently NFC, it just introduces the new APIs and takes a first pass at updating
code to use them. Much more work will need to be done once we start exercising these new
fields.
This does bifurcate some existing APIs:
- SILFunctionType now has two accessors to get its generic signature.
`getSubstGenericSignature` gets the generic signature that is used to apply its
substitution map, if any. `getInvocationGenericSignature` gets the generic signature
used to invoke the function at apply sites. These differ if the generic signature is
implied.
- SILParameterInfo and SILResultInfo values carry the unsubstituted types of the parameters
and results of the function. They now have two APIs to get that type. `getInterfaceType`
returns the unsubstituted type of the generic interface, and
`getArgumentType`/`getReturnValueType` produce the substituted type that is used at
apply sites.
